资源描述：
《机器学习 —— 概率图模型(推理：变量消除)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、概率图的一个重要作用是进行推理，针对某个随机变量，告诉我们它到底有没有可能，有多大可能发生。之前在representation相关的内容中，我们更多的关心如何利用概率图减少联合分布的计算量。inference相关的章节就是要介绍如何从联合概率中获得单个随机变量的概率。1.链状变量消除 对于给定的联合分布函数P(A,B,C,D,E)，如果想要知道P(E)，只需要将A,B,C,D边际掉。假设P(E)可以有两种取值P(e1),P(e2)，P(e1)=P(a1,b1,c1,d1,e1)+P(a2,b1,c1,d1,e1)...以此类推，最终可以得到P(e1)与P(e2)的值。在有概
2、率图的情况下，我们可以对变量进行因式分解，因式分解有助于减少求和的次数。 以如下图所示的链状无向图为例： 由马尔科夫图的团势分解定律可知，某个点的团仅与 其及其父节点有关，所以可以对上述联合概率进行因式分解。而仅 Φ(A,B)与A有关。把Φ(A,B)中的A边际掉，也就是T1(B1)=Φ(A1,B1)+Φ(A2,B1).T1(B2)=Φ(A1,B2)+Φ(A2,B2).其结果相当于是一个仅与B取值有关的势函数。同理，这样已知进行下去可以得到仅与E取值有关的函数。 在有了这样的规则以及分布表达后，查询某个变量的概率实际上是非常简单的事情。 2.马尔科夫网的变量消除 对于一
3、个如图所示的马尔科夫网，我们希望对P(J)进行计算。 P(C,D,I,G,S,L,J,H)=P(C)*P(C,D)*P(I)*P(DIG)*P(IS)*P(GL)*P(SLJ)*P(GJH)【这里的P应该表示为Φ】 如果要计算P(J)，那么需要将C,D,I,G,S,L,H全部边际掉。也就是Sum_C,D,I,G,S,L,H P(C,D,I,G,S,L,J,H) Sum_C,D,I,G,S,L,H P(C,D,I,G,S,L,J,H) =Sum_C,D,I,G,S,L,H P(C)*P(C,D)*P(I)*P(DIG)*P(IS)*P(GL)*P(SLJ)*P(G
4、JH) =Sum_C,D,I,G,S,L P(C)*P(C,D)*P(I)*P(DIG)*P(IS)*P(GL)*P(SLJ)*Sum_H P(GJH) =Sum_C,D,I,G,S,L P(C)*P(C,D)*P(DIG)*P(IS)*P(GL)*P(SLJ)*t(GJ) =Sum_C P(C)*P(C,D)*Sum_D,I,G,S,LP(DIG)*P(IS)*P(GL)*P(SLJ)*t(GJ) =Sum_D,I,G,S,LP(DIG)*P(IS)*P(GL)*P(SLJ)*t1(GJ)*t2(D) =Sum_I,G,S,L P(IS)*P(GL)*P(SLJ)*t1
5、(GJ)*Sum_D P(DIG)*t2(D) =Sum_I,G,S,L P(IS)*P(GL)*P(SLJ)*t1(GJ)*t3(GI) =Sum_Gt3(GI)t1(GJ)P(GL)*Sum_ISL*P(SLJ)*P(IS)*t1(GJ) =Sum_ISLP(SLJ)*t4(IJL) 按照此方法即可求出P(J). 3.变量消除的顺序 显然，变量消除的顺序会对算法的复杂程度产生巨大的影响。而好的变量消除顺序则显然与图的结构有关.还是以上一章节的图为例： P(C,D,I,G,L,S,J,H)= P(C)P(D
6、C)P(I)P(G
7、DI)P(S
8、I)P(L
9、G)P(J
10、
11、SL)P(H
12、GJ) 如果使用无向图的势函数表示，则表示为 P(C)*P(C,D)*P(I)*P(DIG)*P(IS)*P(GL)*P(SLJ)*P(GJH)【这里的P应该表示为Φ】 显然，这里需要做一些变化， DIG,GJH是一个团，团里所有的节点应该是两两相连的。那么可得从贝叶斯有向模型推出对偶的无向图模型。 显然，可以以图中节点的顺序来进行消除，由外到内，先消除对结构影响小的再消除会带来结构改变的。这里的结构改变是指某一个变量消除后会得到t(****)，这里的t(****)中每个变量应该是两两相连的。 所以，此图合适的消除顺序是CDIHGSL。 4.消除顺序的计
13、算机解法 实际上，对于一个复杂的图，不可能人为指定消除顺序。应该要有一套合适的算法或者评估机制来决定先消除哪个，后消除哪个。目前已经应用成功的消除顺序算法包括： min-neighber:某个点如果相连节点最少则优先消除（比如C) min-weight :对马尔科夫模型而言，消除因子值之和最小的的边 min-fill :消除某个节点后，需要补充的边最少 weightedmin-fill:补充边的权重最小（边权重可作为两节点权重之积） 对于机器人定位这么一个实际问题，有如下图模型：
