# 概率图模型--变量消元法与团树传播算法 -- 潘登同学的Machine Learning笔记 @
简单回顾概率图模型的推理任务
求解边缘概率 $$ p(\bf{x_a}) = \sum_{\bf{x \diagdown x_{\alpha}}} $$
求最大后验概率状态 $$ X^{*} = \argmax_{\bf{x}\in \chi} p(\bf{x}) $$
求归一化因子 $$ Z = \sum_{\bf{x}} \prod_{c} \phi_c(\bf{x}_c) $$
概率推理是核心问题, 概率推理相当于模型求解;
变量消元算法
- 思路 > 通过从联合概率分布逐步消除变量, 来求解边缘概率
(就是最基础的$P(A, B)=\sum_{C、D}P(A,B,C,D)$ 的形式)
我们从例子来理解变量消元算法
MRF应用变量消元算法
考虑这样一个链式MRF
$$ \begin{aligned} P(E) &\propto \sum_D \sum_C \sum_B \sum_A \tilde{P}(A,B,C,D,E)\ &= \sum_D \sum_C \sum_B \sum_A \phi_1(A,B) \phi_2(B,C) \phi_3(C,D) \phi_4(D,E) \ &= \sum_D \sum_C \sum_B \phi_2(B,C) \phi_3(C,D) \phi_4(D,E)(\sum_A \phi_1(A,B)) & \text {注意}\ &= \sum_D \sum_C \sum_B \phi_2(B,C) \phi_3(C,D) \phi_4(D,E)\tau_1(B) \ &= \sum_D \sum_C \phi_3(C,D) \phi_4(D,E) \sum_B \phi_2(B,C)\tau_1(B) \ &= \cdots \ &= \tau_4(E) \ &\Rightarrow 归一化 \Rightarrow 概率值 \end{aligned} $$
注意
- 能把$\sum_A$移到右边的原因:其他项中都不含A;
- 前面之所以用$\propto$是因为还没归一化;
贝叶斯网络应用变量消元算法
考虑这样一个贝叶斯网络
- 目标: 求J的边缘概率
消元顺序1(没有固定的说法, 一般从少的开始消)
消元顺序： C,D,I,H,G,S,L $$ \begin{aligned} P(J) &= \sum_{L,S,G,H,I,D,C} \phi_C(C)\phi_D(C,D)\phi_I(I)\phi_G(G,I,D)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J) \ &= \sum_{L,S,G,H,I,D}\phi_I(I)\phi_G(G,I,D)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\sum_{C}\phi_C(C)\phi_D(C,D) \ &= \sum_{L,S,G,H,I,D}\phi_I(I)\phi_G(G,I,D)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\tau_1(D) \ &= \sum_{L,S,G,H,I}\phi_I(I)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\sum_{D}\phi_G(G,I,D)\tau_1(D) \ &= \sum_{L,S,G,H,I}\phi_I(I)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\tau_2(G,I) \ &= \sum_{L,S,G,H}\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\sum_{I}\phi_I(I)\phi_S(S,I)\tau_2(G,I) \ &= \sum_{L,S,G,H}\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\tau_3(G,S) \ &= \cdots \ &= \tau_7(J) {(因为贝叶斯网络中的势函数就是条件概率, 无需归一化, 所以tau_7(J)就是P(J)}\ \end{aligned} $$
- 表格展示(消元顺序) > C,D,I,H,G,S,L
| 步骤 | 消元变量 | 涉及因子 | 涉及变量 | 新因子 |
|---|---|---|---|---|
| 1 | C | $\phi_C(C)\phi_D(C,D)$ | C,D | $\tau_1(D)$ |
| 2 | D | $\tau_1(D)\phi_G(G,I,D)$ | G,I,D | $\tau_2(G,I)$ |
| 3 | I | $\tau_2(G,I)\phi_I(I)\phi_S(S,I)$ | G,S,I | $\tau_3(G,S)$ |
| 4 | H | $\phi_H(H,G,J)$ | H,G,J | $\tau_4(G,J)$ |
| 5 | G | $\tau_3(G,S)\tau_4(G,J)\phi_L(L,G)$ | S,G,J,L | $\tau_5(S,L,J)$ |
| 6 | S | $\tau_5(S,L,J)\phi_J(J,L,S)$ | S,L,J | $\tau_6(L,J)$ |
| 7 | L | $\tau_6(L,J)$ | L,J | $\tau_7(J)$ |
消元顺序2
G,I,S,L,H,C,D
这里就不再写公式了, 直接用表格展示
| 步骤 | 消元变量 | 涉及因子 | 涉及变量 | 新因子 |
|---|---|---|---|---|
| 1 | G | $\phi_G(G,I,D)\phi_L(L,G)\phi_H(H,G,J)$ | G,I,D,L,H,J | $\tau_1(I,D,L,H,J)$ |
| 2 | I | $\phi_I(I)\phi_S(S,I)\tau_1(I,D,L,H,J)$ | S,I,D,L,H,J | $\tau_2(D,L,S,H,J)$ |
| 3 | S | $\phi_J(J,L,S)\tau_2(D,L,S,H,J)$ | S,D,L,H,J | $\tau_3(D,L,H,J)$ |
| 4 | L | $\tau_3(D,L,H,J)$ | D,L,H,J | $\tau_4(D,H,J)$ |
| 5 | H | $\tau_4(D,H,J)$ | D,H,J | $\tau_5(D,J)$ |
| 6 | C | $\tau_5(D,J)\phi_C(C)\phi_D(C,D)$ | D,J,C | $\tau_6(D,J)$ |
| 7 | D | $\tau_6(D,J)$ | D,J | $\tau_7(J)$ |
可以看到, 这种消元方法：在前面几步的时候运算量很大, 就有可能增加算法的复杂度, 但是具体增加还是减少要具体分析, 下面会分析算法复杂度;
算法：变量消元法
$Sum-Product-VE(\Phi,Z)$ $$ \begin{aligned} &\qquad /input: \Phi为因子集, Z为消元变量集\ &\mathbf{1} 令变量消元顺序为Z_1, \ldots, Z_k\ &\mathbf{2} \quad for \quad i=1\ldots k \ & \qquad\qquad \Phi \leftarrow Sum-Product-Eliminate-Var(\Phi, Z_i) &\text{每次消一个元}\ &\mathbf{3} \quad return \prod_{\phi\in\Phi}\phi \end{aligned} $$
$Sum-Product-Eliminate-Var(\Phi, Z)$ $$ \ \begin{aligned} &\qquad /input: \Phi为因子集, Z为消元变量\ &\mathbf{1} \Phi' \leftarrow {\phi\in\Phi:Z\in Scope[\phi]}& \text {从因子集中挑出与消元变量Z有关的因子}\ &\mathbf{2} \Phi'' \leftarrow \Phi-\Phi'&\text{因子集做差：与消元变量Z无关的因子}\ &\mathbf{3} \psi \leftarrow \prod_{\phi\in\Phi'}\phi &\text{对每种情况的势函数做连乘}\ &\mathbf{4} \tau \leftarrow\sum_{Z}\psi &\text{将所有情况加起来}\ &\mathbf{5} \quad return \;\Phi'' \cup {\tau}&\text{返回消元后的因子集} \end{aligned} $$
算法复杂度分析
- 假设概率图模型有n个随机变量, m个因子, 假设变量消元法执行n步；
- 每一步, 消去一个变量$x_i$, (包含$x_i$的因子相乘得到$\psi$，再对$\psi$求和，消去变量)
- 令$N_i$为因子\psi_i的参数个数，$N_{max}=\max_i N_i$;则变量消元法的乘法计算次数就是$O(mN_{max})$, 加法计算次数$O(nN_{max})$
- 更一般的, 假设每个变量的可能取值数最多为v, 因子$\psi$的变量个数最多为K,则整个算法的复杂度为$O(mv^K)$,
团树传播算法
团树传播算法和变量消元算法在本质上是一样的, 从不同角度出发;
变量消元算法把全局概率推理转化为局部因子之间的
乘积和求和运算; 团树传播算法先构造一个团树, 把概率推理计算转化为团树节点之间的消息传递, 消息传递本质上也是因子之间的乘积和求和运算;
问题: 既然是一样的， 为什么要创建一个这样的算法?
因为当实现变量消元算法的时候, 其实要构造图来进行变量消元, 而这个图经过优化之后就是团树传播算法;
聚类图
定义
对于给定的概率图模型, 因子集$\Phi = {\phi}$，变量集为$\chi$。聚类图是定义在概率图模型上的一个无向图, 每个节点$i$是变量集的子集, 即$C_i\subseteq\chi$。 聚类图必须满足
族保持， 即每个因子$\phi$必须与一个节点$C_i$关联, 使得$Scope[\phi]\subseteq C_i$。 一对节点$C_i$和$C_j$之间的每条边与一个割集$S_{i,j}$关联, 其中$S_{i,j}\subseteq C_i\cap C_j$;例子:
由变量消元法导出团树传播算法
- 回到上面的那个例子:
- 变量消元算法
| 步骤 | 消元变量 | 涉及因子 | 涉及变量 | 新因子 |
|---|---|---|---|---|
| 1 | C | $\phi_C(C)\phi_D(C,D)$ | C,D | $\tau_1(D)$ |
| 2 | D | $\tau_1(D)\phi_G(G,I,D)$ | G,I,D | $\tau_2(G,I)$ |
| 3 | I | $\tau_2(G,I)\phi_I(I)\phi_S(S,I)$ | G,S,I | $\tau_3(G,S)$ |
| 4 | H | $\phi_H(H,G,J)$ | H,G,J | $\tau_4(G,J)$ |
| 5 | G | $\tau_3(G,S)\tau_4(G,J)\phi_L(L,G)$ | S,G,J,L | $\tau_5(S,L,J)$ |
| 6 | S | $\tau_5(S,L,J)\phi_J(J,L,S)$ | S,L,J | $\tau_6(L,J)$ |
| 7 | L | $\tau_6(L,J)$ | L,J | $\tau_7(J)$ |
- 团树消元算法
由变量消元构造团树
- 每一步涉及的变量, 作为节点
- 每个节点间通过有新因子相连
注意:节点1虽然看上去是C、D, 但是C、D本身没有含义, 节点其实是$\phi_C(C)\phi_D(C,D)$
结合定义深刻理解聚类图的构造
每个节点$i$是变量集的子集, 即$C_i\subseteq\chi$
对应回上图发现, 每个节点都是变量集${C,D,I,H,G,S,L}$的子集
即每个因子$\phi$必须与一个节点$C_i$关联, 使得$Scope[\phi]\subseteq C_i$
以
3:G、I、S为例, 因子$\phi_I(I)、\phi_S(S,I)$与该节点关联一对节点$C_i$和$C_j$之间的每条边与一个割集$S_{i,j}$关联, 其中$S_{i,j}\subseteq C_i\cap C_j$
以
1:C、D和2:D、I、G为例, 边是$D$，而$D\subseteq {C、D}\cap {D、I、G}$
深刻理解新因子就是消息传递
回想变量消元法的过程, 如第一步：消去变量C， 那就对涉及C、D的因子做乘积求和， 然后C的信息就蕴含在新因子$\tau_1(D)$中了；
那么后续第二步, 当想消去变量D的时候, 因为与变量C有关的那部分D的信息蕴含在$\tau_1(D)$中了, 所以这个因子就作为一个消息传递到2:D、I、G中;
关键还是要理解前面的注意:
- 节点看上去是C、D, 但实际上是与C、D有关的因子;
进而:
- 一旦产生了新因子$\tau_1(D)$, 其实这个新因子既可以属于
1:C、D也可以属于2:D、I、G(根据定义判断即可), 所以这个新因子就充当了消息传递的边出现;
又因为:
- 外表其实不能是因子(还是根据定义), 所以就用D当作边, 但是我们心里清楚D其实没啥含义, 关键是$\tau_1(D)$这个新因子;
由变量消元法构造的聚类图满足什么性质？
性质1: 树状图, 在变量消元过程中, 每个中间因子被使用一次, 每个聚类图的节点传递一个消息给唯一的另一个节点, 因此整个变量消元的过程产生的聚类图为一个树状图(因为树的特点就是: N个点的树有N-1条边, 就是连接N个点的最小边数);
性质2: 族保持(每个因子$\phi$必须与一个节点$C_i$关联, 使得$Scope[\phi]\subseteq C_i$), 概率图模型的每个因子必须出现在某个消元步骤, 所以满足族保持性质;
性质3：执行交叉性质(对于聚类图, 如果对于任意变量$X\in C_i, X\in C_j$， 若$X$也出现在两个节点之间唯一路径上的两个节点, 则该聚类图满足执行交叉性质)
团树
如果聚类图满足上述三个性质, 则聚类图定义为团树；
显然, 由变量消元法得到的聚类图为团树;
算法: 团树传播算法
(算法)团树传播算法
计算变量X的边缘概率
输入： 变量消元法的结果(包括消元顺序， 涉及变量， 涉及因子， 新因子)
输出： X的边缘概率
- 利用变量消元构造团树, 团树节点势函数初始化
- 选取变量X所在的节点作为根节点
- 计算叶子节点到根节点的消息
- 根节点的势函数乘以来自邻接点的消息
- 计算变量X所在节点的边缘概率
注意 之所以能把X作为根节点, 是因为树就是有这个特性, 树的任意一个节点都能作为根节点；
例子: 求J的边缘概率
利用变量消元构造团树
团树节点势函数初始化
选取最右边那个空的节点作为根节点
- 计算叶节点到根节点的消息
$$\delta_{i \rightarrow j} = \sum_{C_i-S_{i,j}}\prod_{k\in(Nb_{C_r}-{j})}\delta_{k \rightarrow i}$$
- $\delta_{1 \rightarrow 2}(D) = \sum_{C}\psi_1(C_1)$
- $\delta_{2 \rightarrow 3}(G,I) = \sum_{D}\psi_2(C_2)\times\delta_{1 \rightarrow 2}$
- $\delta_{3 \rightarrow 5}(G,S) = \sum_{I}\psi_3(C_3)\times\delta_{2 \rightarrow 3}$
- $\delta_{4 \rightarrow 5}(G,J) = \sum_{H}\psi_4(C_4)\times\delta_{2 \rightarrow 3}$
- $\delta_{5 \rightarrow 6}(J,S,L) = \sum_{G}\psi_5(C_5)\times\delta_{4 \rightarrow 5}\times\delta_{3 \rightarrow 5}$
- $\delta_{6 \rightarrow 7}(J,L) = \sum_{S}\psi_6(C_6)\times\delta_{5 \rightarrow 6}$
- $P(J) = \sum_{L}\delta_{5 \rightarrow 6}$
说白了就是变量消元法的程序实现罢了;
如何求概率图所有节点的边缘概率
一种很自然的想法就是， 对所有节点作为根节点， 多次计算边缘概率；
但是有更好的方法, 基于树的特性：
- 任取一个节点作为根节点;
- 先从叶节点传递消息至根节点， 再从根节点传递消息至叶节点， 每个节点分别计算自身势函数乘以来自邻节点的信息;
- (对于含有m个节点的团树, 2(m-1)次消息传递就能计算所有节点的边缘概率)
画图来说明:
- 左边两种是选择目标节点作为根节点计算边缘概率密度
- 而右边的是任取一个节点(4)当作根节点, 然后传递两次, 可以在图中看到任何节点的边缘概率密度都能被计算出来， 如节点2, 可以用1→2的蓝色箭头, 和3→2的紫色箭头的消息来计算边缘概率密度;
变量消元法与团树传播算法就是这样了, 继续下一章吧！pd的Machine Learning
