机器学习40讲_37_35_精确推断变量消除及其拓展
你好，我是王天一。
今天我和你分享的主题是精确推断变量，消除信息拓展。
在前面的几讲中，我和你分享了概率图，模型里一些具有代表性的模型。
这些模型呢都属于表示的范畴。
他们将变量之间的关系通过节点和有向边精确的表示出来。
接下来呢我们将对概率图模型的推断任务加以介绍。
所谓推断呢，指的是利用图结构表示的联合分布来计算其中某个变量的概率，得到关于目标问题的数字化的结论。
在概率图模型当中，因子分解还有条件独立性。
这两大法宝可以大量的节约概率的运算。
给推断问题呢带来一些简洁而高效的解法。
概率图当中的推断可以分为两类，精确推断和近似推断。
精确推断呢是精确的计算变量的条件概率或者是后验概率，可以在结构比较简单的模型当中实现近似。
推断呢则是在不影响推理正确性的前提之下，通过适当的降低精度来提高计算效率，适用于节点数目多、网络结构复杂这样的涂抹型。
那么在今天这一讲里啊，我们先来分析这个精确的推断，精确推断最基本的方法是变量。
消除这种方法呢是对和待求解的条件概率无关的变量进行边际化处理，也就是中间变量约掉，从而计算出目标的概率。
假设说一个网络当中有ABCD四个节点四个变量，那我要求解节点a或者说变量a的这个概率的话，那我就需要对这个联合分布进行边际化的处理，把BCD这三个变量全都给它约掉。
这种方法呢就是变量消除变量消除的基本思想。
可以通过前面贝叶斯网络当中所举的那个例子来解释啊。
点击文稿。
你可以看到这个网络的图示，所有的鲜验概率和条件概率都已经在图中给出了。
如果要用变量消除法来计算变量HB的分布，就得把除了HB之外，剩下的四个变量挨个的给它消除掉。
消除的方式呢是通过对它进行积分。
由于变量BP只和另一个变量DO相关，所以呢把它作为突破口是一个不错的选择。
将所有和变量BP相关的因子相乘，再对变量BP求和，就可以计算出一个新的因子，把它叫做不塞伊。
这个不塞因的因子呢就包含了所有关于BP的信息。
除了BP之外呢，另一个根节点是FO,它会直接的同时影响LO,还有DO.所以在计算因子的时候呢，需要将这两个变量都考虑进来。
Fo和DO他们之间的关系啊已经由上面计算出来的。
这个因泽的赛伊所定义，它和LO的关系呢则是纯粹的条件概率。
两者结合可以表示成另一个新因子不在二。
此外，由于变量LO只出现在新因子普塞二中，那么消除这个变量的结果就是只和变量DO有关的因子谱塞三。
最后呢根据DO和HB之间的关系，可以将这个变量DO给它消除掉啊，获得最终的结果。
单单听我这个叙述这段文字啊，你可能觉得说哎这个过程云山雾罩。
但点击文稿，你可以看到描述整个过程的公式表示啊，用公式表示出来肯定会更加清晰。
从上面的过程可以看出，变量消除的过程就是不断的对中间变量进行穷举并求和的过程啊，我考虑中间变量所有的可能性啊，再对所有的可能性进行求和。
整个过程呢是通过对因子的操作来实现因子这个概念。
在马尔卡夫飞机场这一讲当中啊有过介绍啊，这里面我们就不重复了。
那么如果说在目标的变量x和单个中间变量y之间啊，共同定义出一个因子斐XY的话，那么我要对这个中间变量y进行穷举求和啊，就可以表示成为对因子函数的边际化。
点击问稿你可以看到一个说明的公式，上面的情况呢是一个简单的情况。
如果说情况复杂一点，随机变量外在多个因子f一、斐二、f三一直到斐n当中啊都有出现的话。
这时呢就需要综合考虑这个变量的整体作用。
怎么考虑呢？将所有包含这个公共变量的不同因子给它乘到一块儿。
这样做呢相当于我把这个单个变量y给它孤立出来。
它能够产生的所有影响对概率图模型，整个所有的影响都体现在这个因子函数的乘积当中。
所以对于所有因子函数的乘积统一进行边际化，这样呢就可以彻底消除掉变量外的所有影响。
也就是把这个变量进行边际化的处理。
将上面两个步骤结合起来就可以得到变量消除完整的过程。
变量消除，首先要根据变量之间的依赖关系，按照从简单到复杂的顺序完成。
在选定一个待消除的变量之后，先得找到和这个变量有关的所有的因子函数，它到底会影响哪些其他的变量啊，要把这些都找出来，找出来之后，把这个因子函数进行相乘，得到对变量影响方式的一个完整的描述啊，这个变量所有的效果都包含在这个乘积当中。
有了这个成绩之后，再对这个变量在不同取值下的联合概率进行求和。
求和的目的是什么呢？计算将它消除之后，得到的边缘概率，这样做可以消除掉单个的中间变量。
那么按照这个顺序，将所有的中间变量都消除之后，哎，就可以计算出我们想要的这个边际概率啊或者说条件概率。
那么不难看出这样的求解方法是建立在因子乘积变量求和这两个步骤的基础上。
所以呢整套的方法也被称为叫合机变量消除。
前面介绍的呢都是利用变量消除来进行因果的推断，也就是解决解释的问题啊，我自上而下的来进行解释。
那么这套方法能不能用来进行自下而上的有果推因呢？当然可以，还是以上面的贝叶斯网络为例，在前面我曾直接给出结论啊，在灯亮，但是狗没有叫的时候，家里有人和没人的概率一半一半。
那这个概率是怎么计算出来的呢？就是利用变量消除来计算。
我们把这个问题形式化的处理一下，它实际上求解的就是一个后验概率啊，这个后验概率的条件是LO等于零，HB等于一这样的两个变量。
那么他的目标呢是FO等于零啊，也就是家里有人的这个概率啊。
当然FO等于一，就是没人概率啊，两个是一样。
由于两个观察变量LO和HB啊，它并不存在子节点。
所以呢他们所定义的因子five FOLO和five DOHB啊就只包含和自身相关的这个条件概率。
那么除了这两个之外，贝叶斯网络当中，其他的三个变量共同构成了汇联结构。
那就得把它们和这个已经固定的这个观察变量给它区分开来。
因为这三者是一块的啊，我们不妨用这三者共同定义出另一个因子。
Five FOBBDO啊，由于这两个观察变量它具有确定的结果。
所以在计算因子关系的时候啊，我们就只需要考虑LO等于零HB等于一的情形啊，其他的情形就不需要考虑了。
这样的话呢就可以将所有的因子啊以列表形式给它表示出来。
那么点击文稿，你可以看到对应的音子表格因子表格当中的左侧三列涵盖了三个未知变量，所有可能的取值总共有二的三次方等于八种。
第四列呢则给出了对应的因子函数值。
这三个变量取不同值的时候，每一组取值都有一个对应的因子函数。
那这个因子函数呢可以通过先验概率，还有条件概率给它计算出来。
当执行变量消除的时候啊，我首先要进行因子的相乘，也就是计算每一行当中所有概率的乘积。
这相当于什么呢？相当于求解在这个贝叶斯网络当中出现LO等于零HB等于一。
所有的可能性。
当其他三个变量取到不同值的时候，都可能会导致这个结果的出现。
那么我这时候就需要把所有导致这个结果的可能性给它列出来，把它全部的展示出来。
那么回答问题，由于问题问的是查询这个变量FO的分布，所以在求出所有可能性再来进行求和的时候啊，我需要对BP和DO进行变量求和，也就是边际化处理。
把这两个变量处理掉之后，那么剩下的就只是FO的影响。
具体做法是什么呢？将所有FO等于零所在的行这些因子进行乘积，乘积之后再来求和。
这求和得到的概率是什么呢？是一个联合概率FO等于零LO等于零HB等于一，三者同时满足的数。
它的概率是我们乘积求和之后的结果，反过来再将所有FO等于一所在行对应的因子进行乘积求和。
这时候得到的联合概率就是FO等于一，LO等于零，HB等于一啊这样一个情况。
那么无论是FO等于零还是FO等于一啊，两个对应的都是四种情况，也就是对四个成绩来进行求和。
求和完了之后呢，求出两个联合概率，我再利用贝斯定理进行一个规划，那么就可以求出两个后验概率，基本上都等于零点五。
这就和贝叶斯网络一讲当中计算出来的结果是完全一致的。
在上面介绍的这个预测问题里呢，已知的LO等于零和HB等于一。
我们把它叫做证据。
基于证据的推断，本质上就是计算非规划的一个联合分布。
这个联合分布既会涉及到我证据的变量，也会涉及到你待求解那个目标变量。
利用贝斯网络的性质可以证明这个分布呢其实就是一个吉布斯分布。
那么起到归一化作用的常数呢，则可以看成是一个约化引起。
这个约化因子有个特点就是除了观测变量以外啊，除了我可以直接观察到结果这个变量以外，所有其他的变量都被穷举求和掉了。
所以这说明什么呢？这个约化因子其实就是我观测到我这个证据，哎，就是观测到我这个现象的一个概率。
基于合积的这个变量。
消去算法呢实际上是利用了乘法，对于加法的分配率，它是把多个变量的乘积再求和分解，成为对部分变量交替的进行求积和求和。
如果图模型的规模较小，节点数目较少的话，直接利用全概率公式进行求和或者求积分，就可以计算出每个节点的边缘概率。
哎，就像我们上面这个例子那样，但是当节点数目增加的时候，合计变量消去，它的计算量会以指数形式增长。
要从运算效力的角度对变量焦距算法加以改进的话，这时得到的就是置信传播。
算法置信传播呢，它也是一种精确推断的算法。
它是将涂模镜当中每个节点的概率分布传递给相邻的节点，以此影响相邻节点的概率分布状态，就像传递接力棒一样，整个网络中啊不同的节点进行接力。
那么接力的内容呢是每个节点的概率信息。
经过一定次数的迭代之后，每个节点的概率分布将会收敛到一个平稳的分布之上。
啊，也就是我们传播得到的最终的结果。
这种算法呢适用于包括贝因斯网络，还有马尔可夫随机上在内的所有的概率图模型。
但是今天呢我们将以一种新的模型因子图为例来说明它的原理。
电子图呢是一个新概念啊，它是一类二分图，它被用来表示对函数的一个因子分解。
这里面的节点呢和前面介绍的不一样，它分成两种，分别代表了变量节点，还有因子节点，有这样两种节点。
相关的节点呢是由无向的边连接起来的啊，没有方向。
那么假定一个因子图表示了一个复杂的函数啊，这个函数等于若干个因子的乘积。
点击文稿，你可以看到它对应的图结构，从这个图结构可以看出来，因子图能够更加直观的刻画函数的可分解性，这是他的优势所在。
那么之前介绍的贝斯网络，还有马尔可夫随机场，也都可以把它表示成因子图的形式。
说完了因子图啊，我们来看看致信传播、致信传播算法的核心概念是消息，它是节点之间信息流动的载体。
在因子图当中啊，我假设有一个变量节点v和一个因子节点a那么从a到a的消息和从a到a的消息是不一样。
从变量v到因子a的消息是来自于除a之外，所有与v相邻的因子，它的消息的乘积不同因子的消息要汇总到这个v当中来啊，那么我再从a出去的话，它就等于所有进来的消息啊进行一个相乘，再让它出去。
如果说v没有除a之外其他邻界因子的话，那么它的消息呢就被直接的设置成为均匀分布。
反过来，从因子a到变量v的消息会复杂一些，它先要对除来自v外所有进入a的变量消息进行相乘。
一个因子它也连着若干个变量。
那么我先要对进入到这个因子的变量消息进行乘积，得到这个乘积之后啊，我再对这个乘积进行编际化边际化掉。
所有除了我这目标变量v之外，其他的所有变量边际化的结果，再作为消息传递给这个目标变量。
每个变量的置信度就是在这种从因子到变量，再从变量到因子的不同的循环流动的过程当中。
那么每个变量的置信度，就是根据这样的准则，把在图结构当中，从变量到因子，从因子到变量，不停的往返流动不断更新。
而这个过程呢，在本质上和变量消除的这个合积算法，它其实是一致的。
如果经过多轮迭代之后，涂抹型的因子它能够收敛到稳态，这时候呢就可以计算单个节点的编辑概率。
每个节点的边界概率都正比于和它相邻的所有因子传递给它消息的乘积。
每个变量呢都会受到和它相邻的因子的影响。
那么这些因子的影响啊，以消息的方式体现这些消息乘到一块，得到的就是这个节点的编辑概率。
那么对这个边辑概率呢进行归一化处理之后，就可以得到真正意义上的概率一个因子所包含的所有变量。
它的联合边际分布啊则正比于因子。
函数本身和来自这些变量的消息的撑起和单个节点一样，这个值呢也需要归一化的处理置。
近传播算法呢它在理论上并不保证对所有图结构都能够收敛。
但是当这个因子图是一个竖结构的时，计算出来的概率分布呢就一定能够保证收敛到真实值，从而呢实现精确的推断。
如果这个图模型是一个无环图的话，那它就会天然的具有竖的特性。
可是即使原始的图当中存在着有向或者无向的一个环路啊，或者叫圈形的这个结构。
它也可以通过让变量聚集成不同的团，来生成类似数的一个结构。
那么这种结构呢，我们把它叫做团数，团数也叫做连接数，是一种通过变量连接的结构。
它特点是什么呢？如果一个变量出现在数结构的两个团当中，那它就一定会出现在连接这两个团路径上的所有团当中。
就叫一个人坐公交车啊，如果说他在始八站上车，在终点站下车，那么在这个途中的每一站他都肯定在车上啊，不存在说下去再上来这种情况。
那么点击文档，你可以看到一个团数的实例。
这样看来呢，每个相连的团都像是古熟的驿站，他们的公共面量就是信氏。
在传递消息的时候，首先要在团数当中选取一个根节点，从这个根节点出发，构造出一棵树。
那么在选择根节点的时候呢，通常是选择包含待查询的目标变量的这个团。
我如果要求解a的这个概率的话，那我就要找一个含a的这个团作为根结点。
以此呢作为消息传递的枢纽，根据这个枢纽生成的树，就是传递消息的这个道路的网络消息的传递需要两个步骤啊。
第一个步骤是收集所有的叶子节点，要向根节点传递消息，直到根节点收到所有邻接节点的消息，这个呢是消息汇总的过程。
第二个步骤是分发，指的是根节点向叶节点传递消息，直到所有的叶子节点都收到消息，这个呢是消息的更新过程。
这样的一来一回呢之后，团数的每条边上都有着不同方向的这两条消息。
那基于这些消息就能够计算出所有变量的一个边际概率啊，就是我们要求解的结果和变量消除。
相比呢置信传播，它的优势在于说提高了计算效率。
变量消除它的缺点在于说一次的变量消除只能求出和本次查询变量相关的这个条件分布，不同的查询将带来大量的重复计算。
啊，比方说这一次我要查询变量b那上一次查询a的结果实际上就不能使用啊，我相当于要重打固定开张重新的计算这个结果。
但是有了团数之后，在团数当中流动的每个消息都相当于对一组关联因子的一个封装查询。
不同变量的时候，只需要调用相关的封装就可以了，从而呢避免了复杂的重复运算。
在PGM派当中，团数被定义为models模块当中的junnon tree,利用batching model当中的two junction tree这样的一个函数啊，可以将现有的贝叶斯网络转换成团数转换出来的团数呢就可以采用influence模块当中的belief propagation类来进行求解用团数和置信传播。
求解上面贝斯网络当中的例子啊，可以得到和变量消除法完全一致的结果。
今天我和你分享了对概率图模型的精确推断啊，相关的方法包括以下四个要点。
第一推断是利用图结构表示的分布，计算、查询变量的概率可以分为精确推断和近似推断。
第二，变量消除，通过对非查询变量的边际化处理实践精确推断，具体的步骤包括因子乘积和变量求和。
第三，置信传播，通过消息传递实现精确推断，具有较高的计算效率。
第四，将涂模型改造成团束结构，可以保证致进传播算法的一个收敛性。
在变量消除当中，选取消除变量的顺序是一个重要问题。
数据选的好的话，那么就可以简化运算，数据选的不好呢反而会事倍功半。
在文章当中的例子里啊，我们在确定交流顺序的时候，依据的原则是最小邻居原则，也就是选择依赖变量最少的这个变量啊，从这些变量开始。
那么除此之外，还有哪些确定消除顺序的好的原则呢？你可以查阅相关资料，并在这里留下你的看法。