PRML学习笔记（八）第八章 图模型
PRML 和 ESL 的学习基本上是学十得一。稳扎稳打再来一次
图模型
概率分布的图形表示被称为概率图模型，它提供了几个有用的性质：
- 提供了一种简单的方式将概率模型的结构可视化，可以用于设计新的模型。
- 通过观察图形，可以更深刻地认识模型的性质，包括条件独立性质。
- 高级魔性的推断和学习过程中的复杂计算可以根据图计算表达，图隐式地承载了背后的数学表达式。
在概率图模型中，每个节点表示一个随机变数，链接表示这些变数之间的概率关系。这样，图描述了联合概率分布在所有随机变数上，能够分解为一组因子乘积的方式，每个因子只依赖于随机变数的一个子集。
概率图分为又想吐和无向图两大类。有向图模型也就是贝叶斯网路，图之间的链接有一个特定的方向，使用箭头表示。另一大类是马尔科夫随机场，也被称为无向图模型，这个模型中，链接没有箭头，没有方向性质。有向图对于表达随机变数之间的因果关系很有用，而无向图对于表示随机变数之间的软限制比较有用。为了求解推断问题，通常比较方便的做法是把有向图和无向图都转化为一个不同的表示形式，被称为因子图。
8.1 贝叶斯网路
一个简单的贝叶斯网路如下图所示：
让我们来分析它，首先，每个节点对应于一个随机变数a, b, c。每个带箭头的链接的起点表示条件概率中随机变数对应的节点。对于没有输入链接的节点a,则表示为p(a)。因此上图表示的概率为：
由此可见上图表示了方程的右侧。同时我们注意到方程的左侧是对称的，但右侧不是，因此对弈一个联合概率，我们可能会得到不同的分解方式。上面这个图我们说它是全连接的，因为每对节点之间都存在一个链接。与之对应，也就存在链接缺失的情况，如：
更一般地，在图的所有节点上定义的联合概率分布由每个节点上的条件概率分布的乘积表示，每个条件概率分布的条件都是图中节点的父节点所对应的变数。因此，对于一个有K个节点的图，联合概率为：
其中 表示
父节点的集合，
。上式表示有向图的联合概率分布的分解属性。
我们考虑的有向图要满足一个重要的限制，即不能存在有向环，这种没有有向环的图被称为有向无环图，或者DAG。
8.1.1 例子：多项式回归
对于多项式回归，我们有多项式系数向量w，观测数据t，输入数据x，杂讯方差 以及w的高斯先验精度
。当我们显示地写出模型的参数和随机变数时，联合概率分布可写为：
对应的概率分布图如下图所示：
其中随机变数由空心圆表示，确定性参数由小的实心圆表示，蓝色框被称为板，来表示变数的集合。
8.1.4 线性高斯模型
现在我们将说明多元高斯分布如何表示为一个对应于成分变数上的线性高斯模型的有向无环图。
考虑D个变数上的任意的有向无环图，其中节点i表示服从高斯分布的一元连续随机变数 。这个分布的均值是节点i的父节点
的状态的线性组合，即：
其中 和
是控制均值的参数，
是
的条件概率分布的方差。这样，联合概率分布的对数为图中所有节点上的这些条件分布的乘积的对数，因此形式为：
可以看出联合概率分布是一个多元高斯分布。我可以递归地计算它的均值和方差，首先计算 的均值和方差：
而后从序号最低的节点开始，沿著图递归的计算，就可以求出 的各个元素和协方差的各个元素。
假设图中不存在链接时，图由D个孤立的节点组成，此时不存在参数 因此只有D个参数
和D个参数
。根据递归关系，我们看到p(x)的均值为
，协方差矩阵是一个对角矩阵，形式为
。联合概率分布总计由2D个参数，表示D个独立的一元高斯分布的集合。
当图为全连接时，其中每个节点的序号都低于其父节点的序号。 对应于下三角矩阵，
对应于一个一般的对称协方差矩阵。
复杂度处于二者之间的对应于协方差矩阵取特定形式的联合高斯分布。
8.2 条件独立
多变数概率分布的一个重要概念是条件独立。如下图所示，考虑三个变数a, b, c，并且假定给定b,c的条件下a的条件概率分布不依赖于b的值，即：
我们说，在给定c的条件下，a条件独立于b。
采用条件独立标记表示为：
在模式识别中，使用概率模型时，条件独立性起著重要的作用。它简化了模型的结构，降低了模型的训练和推断的计算量。根据图模型，联合概率分布的条件独立性可以直接从图中读出来，不用进行任何计算。完成这件事的一般框架被称为"d-划分"，其中d表示有向。
8.2.2 d-划分
考虑一个一般的有向图，其中 A, B, C是任意无交集的节点集合(它们的并集可能比图中节点的完整集合要小)。我们希望知道，一个有向无环图是否暗示了一个特定的条件依赖表述 。
为此我们考虑从A中任意节点到B中任意节点的所有可能的路径。我们说这样的路径被阻隔，如果它包含一个节点满足下面两个性质中的任何一个：
- 路径上的箭头以头到尾或者尾到尾的方式交汇于这个节点，且这个节点在集合C中。
- 箭头以头到头的方式交汇于这个节点，且这个节点和它的所有后继都不在集合C中。
如果所有的路径都被阻隔，那么我们说C把A从B中d-划分开，且图中所有变数上的联合概率分布都将会满足 。
8.3 马尔科夫随机场
前面看到有向图模型表示将一组变数上的联合概率分布分解为局部条件概率分布的乘积的一种分解方式。有向图也定义了一组条件独立性质，根据图进行分解的任何概率分布都必须满足这些条件独立性质。现在我们考虑无向图模型，与之前一样，它表示一种分解方式，也表示一组条件独立关系。
一个马尔科夫随机场，也被称为马尔科夫网路或者无向图模型，包含一组节点，每个节点都对应著一个变数或者一组变数。链接是无向的，即不含有箭头。
8.3.1 条件独立性质
假设在一个无向图中，我们有三个节点集合，记做 A, B, C。考虑链接集合A的节点和集合B的节点所有可能的路径。如果所有这些路径都用过集合C中的一个或多个节点，那么所有这样的路径都被阻隔，因此条件独立性质成立。由此可见，无向图的条件独立检测更加简单。
8.3.2 分解性质
分解即将联合概率分布p(x)表示为在图的局部范围内的变数集合上定义的函数的乘积。为此我们首先给局部性一个合适的定义。团块定义为图中节点的一个子集，使得在这个子集中的每对接点之间都存在链接，即全连接的。一个最大团块即不可能将图中任何一个其他的节点包含到这个团块中而不破坏团块的性质。
于是，我们可以将联合概率分布分解的因子定义为团块中变数的函数。让我们将团块记做C，将团块中的变数的集合记做 。这样，联合概率分布可以写成图的最大团块的势函数
的乘积的形式：
其中 Z 有时被称为划分函数，是一个归一化的常数，等于：
归一化常数的存在是无向图的一个主要的缺点，因为归一化项涉及到 个状态的求和。对于参数学习来说，划分函数是必要的，因为划分函数是控制势函数
的任意参数的函数。
现在我们形式化地描述条件独立性和无向图的分解形式，我们将限制势函数严格为正，即对于任意的 的选择都永远不等于零也不取负值的势函数。这样我们可以给出分解和条件独立间的精确关系。
考虑下图所示的滤波器模型：
它表示将变数x的集合上的所有可能的概率分布p(x)输入到滤波器中，那么通过滤波器的概率分布的子集被记做 ，表示有向分解。
对于无向图模型，我们定义 为满足下面条件的概率分布的集合：从使用图划分的方法得到的图中可以读出条件独立性质，这个概率分布应该与这些条件独立性质相容。类似地，我们定义
为：可以表示为关于图中最大团块的分解的形式的概率分布。Hammersley-Clifford 定理表明，集合
和
是完全相同的。
由于我们将势函数限制为严格大于0，因此将是函数表示为指数形式更方便，即：
其中 被称为能量函数，指数表示被称为玻尔兹曼分布。联合概率分布被定义为势函数的乘积，因此总的能量可以通过将每个最大团块的能量相加的方法得到。
8.3.4 与有向图的关系
将有向图转化为无向图，我们首先在图中每个节点的所有父节点之间添加额外的无向链接，然后去掉原始链接的箭头，得到道德图。之后，我们将道德图的所有团块势函数初始化为1。接下来，我们拿出原始有向图中所有的条件概率分布因子，将它乘到一个团块势函数中去。由於伦理步骤存在，总会存在至少一个最大的团块，包含因子中所有的变数。注意，在所有情形下，划分函数都等于1。
将有向图转化为无向图的过程在精确推断方法中起著重要作用，例如联合树演算法。从一个无向图转化到有向图表示不太常用，通常表示归一化限制中出现的问题。
8.4 图模型中的推断
现在考虑图模型中的推断问题，图中的一些节点被限制为观测值，我们想要计算其他节点中的一个或多个子集的后验概率分布。本章我们集中精力与精确推断，第十章考虑近似推断。
8.4.1 链推断
考虑下图所示的节点链
对于图b的联合概率分布形式为：
现在考虑寻找边缘概率分布 这一推断问题，其中
是链上的一个具体的节点。如果我们对势函数求和进行分组，就可以将需要求解的边缘概率密度写成：
根据上式，我们将边缘概率分布 的表达式分解成了两个因子的乘积乘以归一化常数：
我们把 看成从节点
到节点
的沿著链向前传递的信息。类似地，
可以看做从节点
到节点
的沿著链向后传递的信息。注意，每条信息由K个值的集合构成，每个值对应于
的一种选择，因此两条信息的乘积可以被看做两条信息的元素之间的点积，得到另外K个值的信息。
和
可以递归的计算，我们先计算：
如果图中的某些节点被观测到，那么对应的变数简单地被限制为观测值即可，不需要求和。
现在假设我们想计算节点链中两个相邻节点的联合概率分布 。这类似于计算单一结点的边缘概率分布，区别于现在由两个变数没有被求和出来。因此：
一旦我们完成了计算边缘概率分布所需的信息传递，我们就可以直接得到每个势函数中的所有变数上的联合概率分布。为了在并非所有的变数都被观测到的情况下学习势函数的参数，我们可以使用EM演算法。可以证明，以任意观测数据为条件，团块的局部联合概率分布恰好是E步骤所需要的的。
8.4.3 因子图
有向图和无向图都使得若干变数的一个全局函数能够表示为这些变数的子集上的因子的乘积。因子图显式地表示出了这个分解。方法是：在表示变数的节点的基础上，引入额外的节点表示因子本身。
在因子图中，概率分布中的每个变数都有一个节点，这与有向图和无向图的情形相同。还存在其他的节点(用小正方形表示)，表示联合高绿分布中的每个因子 。最后，在每个因子节点和因子所以来的变数之间，存在无向链接。由于因子图由两类不同的节点组成，且所有的链接都位于两类不同的节点之间，因此因子图被称为二分的。一个因子图的例子如下图所示：
它对应于概率分布：
8.4.4 加和乘积演算法
关于有向无环图的精确推断，有一个被称为置信传播的演算法，它等价于加和-乘积演算法的一个具体情形。另外，对加和-乘积演算法稍作修改，使得概率最大的状态被找到就引出了最大加和演算法。
假设原始的图是一个无向树或者有向树或者多树，从而对应的因子图有一个树结构。首先，我们将原始的图转化为因子图，使得我们可以使用同样的框架处理有向模型和无向模型。我们的目标是利用图完成两件事：1)得到一个高效的精确推断演算法来寻找边缘概率，2)在需要求解多个边缘概率的情形，计算可以高效地共享。
加和-乘积演算法总结如下：
1) 将变数节点x看成因子图的根节点，使用下面的公式初始化图的叶节点的信息。
现在假设我们项寻找图中每个变数节点的边缘概率分布，其过程如下。任意选择一个节点(变数或因子节点)，然后将其指定为跟几点。像之前一样，我们从叶节点向根节点传递信息。现在根节点会接收来自所有相邻节点的信息。因此，它可以向所有的相邻节点发送信息。反过来，这些节点之后会收到来自所有相邻节点的信息，因此可以沿著远离根节点的链接发送信息。以此类推，通过这种方式，信息可以从根节点向外传递到叶节点。现在信息已经在两个方向上沿著图中所有的链接传递完毕，并且每个节点都已经接收到了来自所有相邻节点的信息。因为每个变数节点会收到来自所有相邻节点的信息，所以我们可以计算图中每个变数的边缘概率分布。
8.4.5 最大加和演算法
我们想在想找到变数的具有最大概率的一个设置，以及找到这个概率的值。它可以通过最大加和演算法完成，它可以被看做动态规划在图模型中的一个应用。
为了求得最大化联合概率分布p(x)的x的值，我们首先将因子图表达式 带入下式：
然后交换乘积与最大化的计算顺序。这种计算的结构与加和-乘积演算法完全相同，因此我们能够简单地将那些结果转化到当前的问题中。特别地，假设令图中的一个特定的变数节点为根节点。之后，我们计算起始的一组信息，然后从树的叶节点向内部传递到根节点。对于每个节点，一旦它接收到来自其他相邻节点的输入信息，那么它就向根节点发送信息。最后对所有到达根节点的信息的乘积进行最大化，得出p(x)的最大值。这可以被称为最大化乘积演算法，与加和-乘积演算法完全相同，唯一的区别是求和被替换为了求最大值。
在实际应用中，许多小概率的乘积可以产生数值下溢的问题，因此更方便的做法是对联合概率的对数进行操作。取对数后唯一的效果是把最大化乘积演算法中的乘积替换成了加和，因此我们得到了最大化加和演算法。结果为：
最开始的由叶节点发送的信息可以由类比得到：
在根节点处的最大概率可以类比得到：
对于求解联合概率达到最大值的变数的配置，我们可采用如下方法： 如果一条信息从因子节点f出发送到变数节点x，那么最大化针对的是因子节点的全部其他变数节点 ，使用公式：
当我们进行最大化时，我们记录了给出最大值的变数 的值。这样找到了
之后，我们在反向跟踪步骤中可以使用这些存储的值，为相容的最大状态
的值。只要因子图是树，最大加和演算法以及反向跟踪方法就可以给出变数的精确最大化配置。这种方法的一个重要应用就是寻找隐马尔科夫模型中隐含状态的最可能序列，这种情况下被称为Viterbi演算法。
8.4.6 一般图的精确推断
信息传递框架可以被推广到任意的图拓扑结构，从而得到一个精确的推断步骤，被称为联合树演算法。这里给出各个阶段的大致思想。
- 如果我们的起始点是一个有向图，那么我们首先通过伦理步骤，将其转化为无向图。而如果起始点是无向图，那么这个步骤就不需要了。
- 接下来图被三角化，这涉及到寻找包含四个或者更多节点的无弦环，然后增加额外的链接来消除无弦环。
- 而后三角化的图被用于构建新的树结构无向图，被称为联合树，它的节点对应于三角花的图的最大团块，它的链接将具有相同变数的团块链接在了一起。这种方法中连接哪对团块是很重要的问题。正确的做法是选择能得到最大生成树的连接方式。
- 最后，一个二阶段的信息传递演算法，或者等价的加和-乘积演算法，现在可以被应用于这个联合树，得到边缘概率分布和条件概率分布。
联合树演算法对于任意的图都是精确地、高效的。对于一个给定的图，通常不存在计算代价更低的演算法。
推荐阅读：
