概率流程计算

01简单介绍概率图模型是图论和概率论结合的产物，它的开创者是鼎鼎大名的JudeaPearl,我十分喜欢概率图模型这个工具，它是一个很有力的多变量而且变量关系可视化的建模工具，主要包括两个大方向：无向图模型和有向图模型。无向图模型又称马氏网络，它的应用很多，有典型的基于马尔科夫随机场的图像处理，图像分割，立体匹配等，也有和机器学习结合求取模型参数的结构化学习方法。严格的说他们都是在求后验概率:p(y|x)，即给定数据判定每种标签y的概率，最后选取最大的后验概率最大的标签作为预测结果。这个过程也称概率推理(probabilisticinference）。而有向图的应用也很广，有向图又称贝叶斯网络(bayesnetworks),说到贝叶斯就足以可以预见这个模型的应用范围咯，比如医疗诊断，绝大多数的机器学习等。但是它也有一些争议的地方，说到这就回到贝叶斯派和频率派几百年的争议这个大话题上去了，因为贝叶斯派假设了一些先验概率，而频率派认为这个先验有点主观，频率派认为模型的参数是客观存在的，假设先验分布就有点武断，用贝叶斯模型预测的结果就有点“水分”，不适用于比较严格的领域，比如精密制造，法律行业等。好吧，如果不遵循贝叶斯观点，前面讲的所有机器学习模型都可以dismiss咯，我们就通过大量数据统计先验来弥补这点“缺陷”吧。无向图和有向图的例子如（图一）所示：图一(a)无向图（隐马尔科夫）(b)有向图概率图模型吸取了图论和概率二者的长处，图论在许多计算领域中扮演着重要角色，比如组合优化，统计物理，经济等。图的每个节点都可看成一个变量，每个变量有N个状态（取值范围），节点之间的边表示变量之间的关系，它除了可以作为构建模型的语言外，图还可以评价模型的复杂度和可行性，一个算法的运行时间或者错误界限的数量级可以用图的结构性质来分析，这句话说的范围很广，其实工程领域的很多问题都可以用图来表示，最终转换成一个搜索或者查找问题，目标就是快速的定位到目标，试问还有什么问题不是搜索问题？树是图，旅行商问题是基于图，染色问题更是基于图，他们具有不同的图的结构性质。对于树的时间复杂度我们是可以估算出来的，而概率图模型的一开始的推理求解方法也是利用图的结构性质，把复杂图转换成树（容易处理的图）的形式来求解，这个算法被称为联合树算法（junctiontreealgorithm）。联合树算法简单的说就是利用图的条件独立性质把图分解，然后以树的形式组织，最后利用树的良好操作性进行推理求解（消息传递），联合树算法是后续章节的重要的推理算法之一。但并不是所有的图都能拆分成树的形式，一般只有合适的稀疏边的图才能转成树，因此联合树算法也有一定的限制。不能构建联合树，那怎么推理求解？好在还有其他几种方法，概率图模型的第二个成分：概率，既然进入了概率空间，那基于蒙特卡洛（MCMC）的采样方法也就可以使用了，反正就是求最大后验概率，MCMC的求解方法也是经常利用的工具，还有一些基于均值场(meanfield)以及变分方法(variationalmethod)的求解工具。这几个求解方法的算法复杂度比较如（图二）所示：(图二)推理求解算法性能比较（图二）中的几种求解方法也都是概率图模型或者统计机器学习里经常使用的方法，MCMC方法和变分方法都起源于统计物理，最近很火的深度学习也算是概率图模型的一个应用，尽管你要反对，我也要把它划到概率图模型下^.^，RBM,CRBM,DBM都是很特殊的概率图模型，整个思路从建模到求解方法都是围绕着求取图模型节点的最大后验概率来开展的。MCMC求解方法就不说了，深度学习里已经用的很多咯，而变分方法（variationalmethod）很有吸引力，andrewng的师傅MichaelJordan认为把变分方法用在统计机器学习中的有希望的方法是把凸分析和极家族分布函数链接起来，既然有凸分析，那么就会伴随着凸松弛(convexrelaxtion),因为数据是离散的，具体可以看前面的关于凸松弛的博文介绍。另外还有一些图模型特有的求解方法，比如beliefpropagation(sum-productalgorithm)n或者expectationpropagation等求解方法。上面算是对概率图模型做了个简单的介绍，接下的来的博文就是按照下面的提纲来记录一下学习笔记，在尽量不违背honorcode的情况下，用原来Daphnekoller教授的作业来做辅助介绍。一、介绍图模型定义二、利用基于变分方法的极家族和凸分析来求边缘概率三、逼近求解方法，如belief-propagation、expectation-propagation等四、均值场求解方法等各种优化求解方法五、结构化学习02概率图模型定义翻开Jordan和Wainwright著作的书，正文开始（第二章）就说概率图模型的核心就是：分解（factorization）。的确是这样的，对于复杂的概率图模型，要在复杂交织的变量中求取某个变量的边缘概率，常规的做法就是套用贝叶斯公式，积分掉其他不相干的变量，假设每个变量的取值状态为N，如果有M个变量，那么一个图模型的配置空间就有N^M，指数增长的哦，就这个配置空间已经让我们吃不消了，不可以在多项式时间内计算完成，求边缘概率就没办法开展下去了。此时分解就派上用场咯，我们想法找到一些条件独立，使得整个概率图模型分解成一个个的团块，然后求取团块的概率，这样就可以把大区域的指数增长降为小区域的指数增长。毕竟100^20这样的计算量比25*（4^20）的计算量大多咯。好了，不说这么抽象了，下面进入正题：（图一）（图二）无向图模型又称马尔科夫随机场（markovrandomfiled）无向图模型的分解就是通过团块（clique）来完成，所谓团块就是全连接的最大子图，如（图二）所示，(a)图的｛1，2，3，4｝，｛4，5，6｝，｛6，7｝都是全连接的最大子图，假设团块用C表示，为每个团块分配一个兼容函数(compatibilityfunction)，它的作用就是把团块取值状态映射到正实值空间，说白了就是给这个团块一个度量，可以是概率，也可以是取值状态和真实标签之间的差值平方和，根据应用而定，这个兼容函数有时又被称为势函数（potentialfunction）,有了兼容函数，无向图模型就可以通过（公式二）分解：（公式二）（公式二）中的Z是归一化的常量，学名叫配分函数(partitionfunction)，一归一化就成概率了，不归一化不满足概率和为1的性质。为了能在图模型中直观的看到团块，可以用因子图（factorgraph）来表示无向图模型，如（图二）(b)所示，和黑块连接的顶点表示全部互相连接（全连接），一个黑块部分表示一个团块，所以上面分解又多了一个名字：因子分解(factorization)。上面说了很多枯燥的定义，目标只有一个，引出两种图模型的分解公式：（公式一）和（公式二），那为什么可以分解成那个样子？现在通过两个小例子说明一下：对于有向图模型，如（图三）所示模型，一个人的聪明程度（Intelligence）可以影响他的年级（Grade:痴呆的读高年级的概率低，聪明的一般走的比较远），而且对他的成绩（SAT）也有高低影响。当我们知道一个人的聪明度后，年级和成绩还有关系吗？二本就根本没有关系，在这里不要想多，其实很简单，给定一个物体后，那么这个物体上的两个属性值就决定了，已经存在的事实，所以二者是独立的。朴素贝叶斯就是根据这个条件独立做的分解。（图三）另外注意一下，这里给定的是父亲节点，（公式一）中也强调了这点，如果不给父亲节点，条件独立就变的稍微复杂一些，如（图四）中有一个比（图三）稍微复杂一些的有向图模型：（图四）在（图四）中Difficulty表示试卷难度，Intelligence表示考生聪明度，如果什么都不给，这二者是独立的，因为试卷难度和考生没有关系，所谓的高考很难，但是这跟我有什么关系？我又不参加高考^.^，但是如果一旦给定空考生的年级（grade）,情况就变得不一样了，比如考生考到了博士，如果他不聪明，那说明啥？说明卷子不难，水的很，如果卷子很难，考生一定很聪明，所以这中间有个因果推理关系。这就是Judeapeal提出的explainaway问题（Eveniftwohiddencausesareindependentintheprior,theycanbecomedependentwhenweobserveaneffectthattheycanbothinfluence）,在前面的博文《目标检测（ObjectDetection）原理与实现(三)》也解释了这个问题，如果这个例子没有解释清楚，可以看下前面的例子。对于无向图模型的条件独立就要简单一些，是从图论的可达性（reachability）考虑，也可从图的马尔科夫性入手，如（图五）所示：（图五）（图五）是个标准的隐马尔科夫模型（HMM），当给定X2时，就相当于在X2除切了一刀，在X2前后之间的变量都相互独立。独立就可以分解了，比如条件概率独立公式：P(A,B|C)=P(A|C)*P(B|C),团块兼容函数也是如此。如果X1-X5我们都给定，那这个模型分解的团块都是相似的，每个图块都可以用一个通用的标记来表示，因此图模型里又提了一种盘子表示法（platenotation），如（图六）所示：（图六）（图六）不是表示的HMM的盘子模型，而是LDA模型的盘子模型，只是让大家了解一下通用分解模版的表示方法，其实很多时候这个表示方法反而不是那么清晰，南加州大学有一个做机器学习的博士生就在吐槽这个表示方法，有兴趣的可以去看看（链接）。今天算是了解一下概率图模型的基本定义和两个分解公式，这两个分解公式只是给出了图模型不好求概率的一个解决方法的切入点，下节就来学习一下概率图模型如何通过分解来进行边缘概率推理求解。03图模型推理算法这节了解一下概率图模型的推理算法（Inferencealgorithm），也就是如何求边缘概率（marginalizationprobability）。推理算法分两大类，第一类是准确推理（ExactInference）,第二类就是近似推理（ApproximateInference）。准确推理就是通过把分解的式子中的不相干的变量积分掉（离散的就是求和）；由于有向图和无向图都是靠积分不相干变量来完成推理的，准确推理算法不区分有向图和无向图，这点也可以在准确推理算法：和积算法（sum-product）里体现出来，值得一提的是有向图必须是无环的，不然和积算法不好使用。如果有向图包含了环，那就要使用近似推理算法来求解，近似推理算法包含处理带环的和积算法（”loopy”sum-product）和朴素均值场算法（naivemeanfield），下面就来了解下这两种推理算法的工作原理。假如给一个无向图，他包含数据节点X和标签Y,它可以分解成（公式一）的形式：（公式一）有些人一开始觉得（公式一）很奇怪，貌似和上一节的无向图分解有点不一样，其实是一样的，稍微有点不同的是把不同的团块区分对待了，这里有两种团块，比如（公式一）右边第一项是归一化常量配分函数，第二项可能是先验概率，而第二项就可能是给定标签时样本的概率。这里用可能这个措辞，表示这些势函数只是一个抽象的函数，他可以根据你的应用来变化，它就是对两种不同团块的度量。如果X的取值状态只有两个，那么配分函数可以写成（公式二）的形式：（公式二）配分函数就是把所有变量都积分掉得到的最终的度量值，如果要求边缘概率就要通过积分掉其他变量得到的度量值除以配分函数，例如我们要求（图一）中的x1的边缘概率P(x1)：（图一）要求取P(x1),我们就要积分掉x2-x6这五个变量，写成数学的形式如（公式三）所示：（公式三）如果你对代数分配率很熟悉，外面的加法符号大sigma可以分开写成（公式四）的样子：（公式四）其实（公式四）就是和积算法的雏形，因为可以很明显的看出又有和又有积。有人可能要问积分掉变量的顺序为什么是那样？其实这个没有准则的，先积分掉哪个变量，积分的顺序也会导致运