概率图模型笔记(8)——Inference Variable Elimination

8.1 Overview-Conditional Probability Queries

8.1.1 Conditional Probability Queries

　　定义如下三个内容:

　　(1)证据： E=e

　　(2)问题：变量集 Y

　　(3)任务：计算P(Y|E=e)

8.1.2 和-积

　　除了问题变量所在的因子，在每个因子上轮流取不同的值并将各个因子做乘积，不同的取值的因子积之和为问题变量的联合分布 P ，如果不进行归一化则记为P~。

8.1.3 证据：减少因子

　　对于给定了证据的计算任务 P(Y|E=e) ，其计算方法和8.1.2小结的方法基本类似，不同在于需要在因子中划去 E=e 以外的分布。

　　需要注意到的是，可以先计算 P(y,e)=∑wP(y,e,w) ，然后利用 P(e)=∑yP(y,e) 来进行计算，并在最后重新进行归一化。其中 w 是变量中除了y和 e 以外的变量集。

8.1.4 条件概率的算法

　　(1)Push summations into factor product

　　例如变量消除法，它是精确推理的一种，同时也被称为动态工程。

　　(2)message passing over a graph

　　例如信念传播，变分近似。

　　(3)Random sampling instantiations

　　例如MCMC以及重要性抽样。

8.2 Overview-MAP Inference

8.2.1 定义

　　(1)证据：E=e。

　　(2)问题：除 E 以外的其他变量Y。

　　(3)任务：计算 MAP(Y│E=e)=argmaxyP(Y=y|E=e)

　　需要注意的是，可能有多个解存在。

　　应用：信息编码，即最有可能传播的信息；图像分割，最有可能的分割情况。

8.2.2 MAP不是边缘概率的最大值

8.2.3 计算方法

　　其本质上是个优化问题，即：

P(Y│E=e)=P(Y,E=e)P(E=e)∝P(Y,E=e)=1Z∏kφk(Dk)∝∏kφk(Dk)

在上式中， φk(Dk) 是除 E 以外的因子，而因为P(E=e)、 Z 独立于Y，所以可以省略并写作正比形式。

8.2.4 算法

　　(1)Push maximization into factor product

　　例如变量消除。

　　(2)Message passing over a graph

　　例如最大乘积信念传播。

　　(3)Using methods for integer programming

　　(4)对于一些特殊的网络:graph-cut methods

　　(5)Combinatorial search

8.3 Variable Elimination Algorithm

8.3.1 Elimination in Chains

　　对于一个无向链A-B-C-D-E，我们有如下变量消除法则：

P(E)∝∑D∑C∑B∑Aφ(A,B)φ(B,C)φ(C,D)φ(D,E)

=∑D∑C∑Bφ(B,C)φ(C,D)φ(D,E)∑Aφ(A,B)

=∑D∑C∑Bφ(B,C)φ(C,D)φ(D,E)τ1(B)

当需要消除变量B时需包含 φ(B,C) 与 τ1(B) ，并最后定义累加结果为 τ2(C) ，视为与自变量为 C 的函数，依次类推。

8.3.2 Variable Elimination

　　对于有向的贝叶斯网络来说，每个节点联合其父节点为一个因子，当对某一变量进行消除时，把与该变量有关的因子放到对应的连加符号右边，其他的变量与连加符号放到该连加符号左边。将所需消除的连加符号以及连加符号右边的式子，写成以右边因子中所存在的所有变量为自变量的函数τ。

　　注意，该步骤之后所有因式的辖域中均不存在被消除的变量。

　　马尔可夫网的变量消除法与上述方法相同。

8.3.3 Variable Elimination with evidence

　　先对于给定的证据变量进行如8.1节所示的因式缩减，然后根据8.3.2的方法进行变量消除。最后归一化。

8.3.4 总结

　　变量消除算法步骤如下：

　　(1)根据所有的证据进行因式缩减(reduce)

　　(2)对于需要消除的变量 Z ，把所有含有Z的变量放到 Z 的连加右边，并连同连加符号换成一个因式τ。

　　(3)把得到的 τ 和剩下的因式乘起来。

　　(4)重新归一化得到分布。

8.4 Complexity Analysis

8.4.1 单次消除乘积次数

　　对于第k次变量消除ψk(Xk)=∑mki=1φi，其进行乘积算法的次数不高于因子的个数 mk 减一乘以最后所得因子的行数 Nk ： (mk−1)Nk 。

　　例如有3个因子，只需两次自然连接乘积即可得到最后的结果，每次自然连接乘积的乘积次数不会高于最后得到的因子的行数。

8.4.2 单次消除加法次数

　　对每个因子做乘积之后需求本次消除的因子的边缘分布，即把乘积所得分布的行中的相同消除因子的值加起来。由于分布中每行只会被加一次，所以加法次数不会高于分布中的行数。即 Nk 。

8.4.3 总时间复杂度

　　(1)消除次数 m 必然小于或等于变量个数n；

　　(2)最开始的初始因子数(a)对于贝叶斯网络来说必然小于变量个数n;(b)对于马尔可夫网来说可能会大一些，最多的情况是马尔可夫网是完全图；

　　(3)每一次变量消除生成1个新因子，并假设因子的最大数量是 m∗ 。

　　(4)令 N=max(Nk)

　　那么我们有如下结论：

　　(1)乘法操作的次数为： ∑k(mk−1)Nk≤N∑k(mk−1)≤Nm∗

　　(2)加法操作的次数为： ∑kNk=Nm≤Nn

　　我们可以看到，变量消除法的复杂度线性于 N 、n和 m∗ 。但是我们可以看到， Nk=O(drk) ， d 是变量个数，变量k有 rk 种取值。所以其时间复杂度是指数级的。

8.4.4 时间复杂度与选择消除的变量顺序有非常大的关系。

8.5 Graph-Based Perspective

8.5.1 贝叶斯网转马尔可夫网： 将有向图转化为无向图后(参见6.5)，每当消除一个变量时，依旧存在的与被消除变量有连接的边之间发生新的边，因为当新的因子生成的时候它们都是该因子的辖域。

8.5.2 导出图(Induced Graph)

　　定义 IΦ,α 为给定因子集 Φ 以及消除顺序α的导出图，可以发现，消除顺序 α 所新生成的因子的辖域与生成该因子所消除的变量的集合在导出图中构成了派别(clique)。

8.5.3 导出图的宽度

　　即该导出图中最大派别的节点个数减1，对应整个消除变量过程中最大的因子相乘次数(即mk−1)。

8.6 Finding Elimination Orderings

　　由于最优的算法是NP难问题，所以可以采用贪心算法来减少计算量，而一般有如下的损失函数：

　　(1)最小邻居：其在当前图中拥有的近邻的数目。

　　(2)最小权重：其及其近邻的权重(即可选的值的数目)的乘积，例如有辖域是两个可取100种值的变量以及五个有2个取值的变量，那么后者的权重乘积明显较小。

　　(3)最小填充：由于消除这个顶点而需要新增边的数目。

　　(4)加权最小填充：由于消除这个丁点而需要新增边的权重和。

　　值得注意的是，由于导出图是由多个完全图拼接而成，即每个点都一定隶属于一个派别里，所以其实以上算法的目的都在于找出一个导出图宽度最小的三角划分方式。