概率图模型介绍与计算

1、概率图模型介绍与计算01 简单介绍概率图模型是图论和概率论结合的产物，它的开创者是鼎鼎大名的Judea Pearl,我十分喜欢概率图模型这个工具，它是一个很有力的多变量而且变量关系可视化的建模工具，主要包括两个大方向：无向图模型和有向图模型。无向图模型又称马氏网络，它的应用很多，有典型的基于马尔科夫随机场的图像处理，图像分割，立体匹配等，也有和机器学习结合求取模型参数的结构化学习方法。严格的说他们都是在求后验概率:p(y|x)，即给定数据判定每种标签y的概率，最后选取最大的后验概率最大的标签作为预测结果。这个过程也称概率推理(probabilistic inference）。而有向图的应用也很

2、广，有向图又称贝叶斯网络(bayes networks),说到贝叶斯就足以可以预见这个模型的应用范围咯，比如医疗诊断，绝大多数的机器学习等。但是它也有一些争议的地方，说到这就回到贝叶斯派和频率派几百年的争议这个大话题上去了，因为贝叶斯派假设了一些先验概率，而频率派认为这个先验有点主观，频率派认为模型的参数是客观存在的，假设先验分布就有点武断，用贝叶斯模型预测的结果就有点“水分”，不适用于比较严格的领域，比如精密制造，法律行业等。好吧，如果不遵循贝叶斯观点，前面讲的所有机器学习模型都可以dismiss咯，我们就通过大量数据统计先验来弥补这点“缺陷”吧。无向图和有向图的例子如（图一）所示：图一 (

3、a)无向图（隐马尔科夫） (b)有向图概率图模型吸取了图论和概率二者的长处，图论在许多计算领域中扮演着重要角色，比如组合优化，统计物理，经济等。图的每个节点都可看成一个变量，每个变量有N个状态（取值范围），节点之间的边表示变量之间的关系，它除了可以作为构建模型的语言外，图还可以评价模型的复杂度和可行性，一个算法的运行时间或者错误界限的数量级可以用图的结构性质来分析，这句话说的范围很广，其实工程领域的很多问题都可以用图来表示，最终转换成一个搜索或者查找问题，目标就是快速的定位到目标，试问还有什么问题不是搜索问题？树是图，旅行商问题是基于图，染色问题更是基于图，他们具有不同的图的结构性质。对于树的

4、时间复杂度我们是可以估算出来的，而概率图模型的一开始的推理求解方法也是利用图的结构性质，把复杂图转换成树（容易处理的图）的形式来求解，这个算法被称为联合树算法（junction tree algorithm）。联合树算法简单的说就是利用图的条件独立性质把图分解，然后以树的形式组织，最后利用树的良好操作性进行推理求解（消息传递），联合树算法是后续章节的重要的推理算法之一。但并不是所有的图都能拆分成树的形式，一般只有合适的稀疏边的图才能转成树，因此联合树算法也有一定的限制。不能构建联合树，那怎么推理求解？好在还有其他几种方法，概率图模型的第二个成分：概率，既然进入了概率空间，那基于蒙特卡洛（MCM

5、C）的采样方法也就可以使用了，反正就是求最大后验概率，MCMC的求解方法也是经常利用的工具，还有一些基于均值场(mean field)以及变分方法(variational method)的求解工具。这几个求解方法的算法复杂度比较如（图二）所示：(图二) 推理求解算法性能比较（图二）中的几种求解方法也都是概率图模型或者统计机器学习里经常使用的方法，MCMC方法和变分方法都起源于统计物理，最近很火的深度学习也算是概率图模型的一个应用，尽管你要反对，我也要把它划到概率图模型下.，RBM,CRBM,DBM都是很特殊的概率图模型，整个思路从建模到求解方法都是围绕着求取图模型节点的最大后验概率来开展的。M

6、CMC求解方法就不说了，深度学习里已经用的很多咯，而变分方法（variational method）很有吸引力，andrew ng的师傅Michael Jordan认为把变分方法用在统计机器学习中的有希望的方法是把凸分析和极家族分布函数链接起来，既然有凸分析，那么就会伴随着凸松弛(convex relaxtion),因为数据是离散的，具体可以看前面的关于凸松弛的博文介绍。另外还有一些图模型特有的求解方法，比如belief propagation(sum-product algorithm)n或者expectation propagation等求解方法。上面算是对概率图模型做了个简单的介绍，接下

7、的来的博文就是按照下面的提纲来记录一下学习笔记，在尽量不违背honor code的情况下，用原来Daphne koller教授的作业来做辅助介绍。一、介绍图模型定义二、利用基于变分方法的极家族和凸分析来求边缘概率三、逼近求解方法，如belief-propagation、expectation-propagation等四、均值场求解方法等各种优化求解方法五、结构化学习02 概率图模型定义翻开Jordan和Wainwright著作的书，正文开始（第二章）就说概率图模型的核心就是：分解（factorization）。的确是这样的，对于复杂的概率图模型，要在复杂交织的变量中求取某个变量的边缘概率，常规

8、的做法就是套用贝叶斯公式，积分掉其他不相干的变量，假设每个变量的取值状态为N，如果有M个变量，那么一个图模型的配置空间就有NM，指数增长的哦，就这个配置空间已经让我们吃不消了，不可以在多项式时间内计算完成，求边缘概率就没办法开展下去了。此时分解就派上用场咯，我们想法找到一些条件独立，使得整个概率图模型分解成一个个的团块，然后求取团块的概率，这样就可以把大区域的指数增长降为小区域的指数增长。毕竟10020这样的计算量比25*（420）的计算量大多咯。好了，不说这么抽象了，下面进入正题：（图一）（图二）无向图模型又称马尔科夫随机场（markov random filed）无向图模型的分解就是通过团

9、块（clique）来完成，所谓团块就是全连接的最大子图，如（图二）所示，(a)图的1，2，3，4，4，5，6，6，7都是全连接的最大子图，假设团块用C表示，为每个团块分配一个兼容函数(compatibility function)，它的作用就是把团块取值状态映射到正实值空间，说白了就是给这个团块一个度量，可以是概率，也可以是取值状态和真实标签之间的差值平方和，根据应用而定，这个兼容函数有时又被称为势函数（potential function）,有了兼容函数，无向图模型就可以通过（公式二）分解：（公式二）（公式二）中的Z是归一化的常量，学名叫配分函数(partition function)，一归

10、一化就成概率了，不归一化不满足概率和为1的性质。为了能在图模型中直观的看到团块，可以用因子图（factor graph）来表示无向图模型，如（图二）(b)所示，和黑块连接的顶点表示全部互相连接（全连接），一个黑块部分表示一个团块，所以上面分解又多了一个名字：因子分解(factorization)。上面说了很多枯燥的定义，目标只有一个，引出两种图模型的分解公式：（公式一）和（公式二），那为什么可以分解成那个样子？现在通过两个小例子说明一下：对于有向图模型，如（图三）所示模型，一个人的聪明程度（Intelligence）可以影响他的年级（Grade:痴呆的读高年级的概率低，聪明的一般走的比较远），

11、而且对他的成绩（SAT）也有高低影响。当我们知道一个人的聪明度后，年级和成绩还有关系吗？二本就根本没有关系，在这里不要想多，其实很简单，给定一个物体后，那么这个物体上的两个属性值就决定了，已经存在的事实，所以二者是独立的。朴素贝叶斯就是根据这个条件独立做的分解。（图三）另外注意一下，这里给定的是父亲节点，（公式一）中也强调了这点，如果不给父亲节点，条件独立就变的稍微复杂一些，如（图四）中有一个比（图三）稍微复杂一些的有向图模型：（图四）在（图四）中Difficulty表示试卷难度，Intelligence表示考生聪明度，如果什么都不给，这二者是独立的，因为试卷难度和考生没有关系，所谓的高考很难

12、，但是这跟我有什么关系？我又不参加高考.，但是如果一旦给定空考生的年级（grade）,情况就变得不一样了，比如考生考到了博士，如果他不聪明，那说明啥？说明卷子不难，水的很，如果卷子很难，考生一定很聪明，所以这中间有个因果推理关系。这就是Judea peal提出的explain away问题（Even if two hidden causes are independent in the prior, they can become dependent when we observe an effect that they can both influence）,在前面的博文目标检测（Objec

13、tDetection）原理与实现(三)也解释了这个问题，如果这个例子没有解释清楚，可以看下前面的例子。对于无向图模型的条件独立就要简单一些，是从图论的可达性（reachability）考虑，也可从图的马尔科夫性入手，如（图五）所示：（图五）（图五）是个标准的隐马尔科夫模型（HMM），当给定X2时，就相当于在X2除切了一刀，在X2前后之间的变量都相互独立。独立就可以分解了，比如条件概率独立公式：P(A,B|C)=P(A|C)*P(B|C),团块兼容函数也是如此。如果X1-X5我们都给定，那这个模型分解的团块都是相似的，每个图块都可以用一个通用的标记来表示，因此图模型里又提了一种盘子表示法（pla

14、te notation），如（图六）所示：（图六）（图六）不是表示的HMM的盘子模型，而是LDA模型的盘子模型，只是让大家了解一下通用分解模版的表示方法，其实很多时候这个表示方法反而不是那么清晰，南加州大学有一个做机器学习的博士生就在吐槽这个表示方法，有兴趣的可以去看看（链接）。今天算是了解一下概率图模型的基本定义和两个分解公式，这两个分解公式只是给出了图模型不好求概率的一个解决方法的切入点，下节就来学习一下概率图模型如何通过分解来进行边缘概率推理求解。03 图模型推理算法这节了解一下概率图模型的推理算法（Inference algorithm），也就是如何求边缘概率（marginalizat

15、ion probability）。推理算法分两大类，第一类是准确推理（Exact Inference）,第二类就是近似推理（Approximate Inference）。准确推理就是通过把分解的式子中的不相干的变量积分掉（离散的就是求和）；由于有向图和无向图都是靠积分不相干变量来完成推理的，准确推理算法不区分有向图和无向图，这点也可以在准确推理算法：和积算法（sum-product）里体现出来，值得一提的是有向图必须是无环的，不然和积算法不好使用。如果有向图包含了环，那就要使用近似推理算法来求解，近似推理算法包含处理带环的和积算法（”loopy” sum-product）和朴素均值场算法（na

16、ive mean field），下面就来了解下这两种推理算法的工作原理。假如给一个无向图，他包含数据节点X和标签Y,它可以分解成（公式一）的形式：（公式一）有些人一开始觉得（公式一）很奇怪，貌似和上一节的无向图分解有点不一样，其实是一样的，稍微有点不同的是把不同的团块区分对待了，这里有两种团块，比如（公式一）右边第一项是归一化常量配分函数，第二项可能是先验概率，而第二项就可能是给定标签时样本的概率。这里用可能这个措辞，表示这些势函数只是一个抽象的函数，他可以根据你的应用来变化，它就是对两种不同团块的度量。如果X的取值状态只有两个，那么配分函数可以写成（公式二）的形式：（公式二）配分函数就是把所

17、有变量都积分掉得到的最终的度量值，如果要求边缘概率就要通过积分掉其他变量得到的度量值除以配分函数，例如我们要求（图一）中的x1的边缘概率P(x1)：（图一）要求取P(x1),我们就要积分掉x2-x6这五个变量，写成数学的形式如（公式三）所示：（公式三）如果你对代数分配率很熟悉，外面的加法符号大sigma可以分开写成（公式四）的样子：（公式四）其实（公式四）就是和积算法的雏形，因为可以很明显的看出又有和又有积。有人可能要问积分掉变量的顺序为什么是那样？其实这个没有准则的，先积分掉哪个变量，积分的顺序也会导致运算量大小不一样，求取最优的积分变量顺序是NP-hard的，下面用图示演示下积分消除变量发

18、生的事情。(01)(02)(03)(04)(05)（图二）（图二）中注意观察下每次积分掉一个变量后，原来的团块就因为少了一个变量变成了一个新的团块，新的团块使得图被三角剖分了，尤其在倒数第二个图更明显，消除变量x4后形成新的团块（x2,x3）,使得x2,x3之间建立了一条连接（蓝线所示），这个三角化添加的边在图论里被成为弦（chord），全部完成三角化的图也称端正图（moral graph）。而边缘概率计算量的复杂度取决于剩下的变量形成的团块大小，如（图二）中红色的部分，变量消除的顺序也会影响新团块的大小，寻找一个最优的变量消除顺序十分必要，但是寻找最优的变量消除顺序是NP-hard的，眼看着

19、问题就没法解决了，但如果图模型是树呢？树这种图模型具有良好的性质，他的计算量不大，下面先叉开下话题去看下树结构的图模型的边缘概率求解方法：假设树结构的图模型如（图三）所示：（图三）和（公式一）类似，这个树结构的图模型的分布可以分解成（公式一）的形式，因为树可简单的分解成节点和边，那么它分解的形式如（公式五）所示：（公式五）把上面所述的和积算法写成一个通用的形式公式,如（公式六）所示：（公式六）这里注意下大sigma下标中的竖线表示排除Xs这个变量，积分掉其他变量，最终得到Xs的边缘概率。现在问题来了，在（图三）中，如果要求变量Xs的边缘概率就要积分掉Xs周围的其他四个变量（Xt,Xw,Xu,X

20、v），这是由(公式五)中的团块决定的（有边相连）,而要积分掉这周围的四个变量就要继续积分掉这四个变量周围除Xs以外的其他相邻变量，这是个递归过程。而动态规划其实也是递归，所以本质上和积算法（sum-product）是个非连续的动态规划算法。下面用数学语言更进一步的梳理下这个递归算法流程，先做几个定义：对于任意的属于V的节点变量s,它的临域可以定义成（公式七）的样子：（公式七）用表示和要计算边缘概率节点变量相连的子树，如变量s,但是子树不能越过变量s,如（图三）中的Tt,Tw,Tu,Tv都是子树，每个子树上的变量用表示，那么每个子树又可以做团块分解，如（公式八）所示：（公式八）有了这些定义，我们

21、就可以再重新梳理下刚才的递归过程，要计算变量Xs的边缘概率，就要计算其临域上的边缘概率，然后再临域的临域上的边缘概率，其实就是子树上的边缘概率，最终会递归到整个树的叶子节点上，叶子节点计算完成后传到父亲节点，以后依次向上传，最终传递到变量Xs上，这个过程其实叫消息传递（Message-Passing）,有时也叫置信传播（BeliefPropagation）,有了消息的概念，那（公式八）就可以变成（公式九）的样子：（公式九）（公式九）中k表示归一化常量，Mts表示从变量Xt传向Xs的消息，其实就是从子树上传递过来的，然后P表示子树的子树上传递过来的消息，引入消息的好处就是容易描述这个递归过程，另

22、外也容易扩展到其他带环的图上，因为动态规划是递归的，递归用消息传播来表示，那么带环的图用消息传递的方法求解，我们就说其实用了动态规划算法，这个话题就不扯远了。另外有了消息传播机制，上述的计算边缘概率的方法还可以扩展一下，使得可以同时计算所有节点的边缘概率，这就使得计算速度大大提高。我们可以让每个节点都同时沿着边向其临域传送消息，消息如（公式十）所示：（公式十）这样其实是传播了2倍于边数的消息，然后开始迭代，第二轮迭代时用第一轮传播来过来的子树上的消息更新当前消息，然后依次迭代下去，迭代n次后，消息值收敛，这样每个变量周围的消息都已确定，就不需要递归了，套用下（公式九）就可以计算边缘概率了。计算最大边缘概率（max-marginal）也是类似的方法，只不过是在收敛收选取最大的边缘概率而已，虽然简单，但是应用范围很广，因为很多时候都是在寻找个极值，比如立