（《机器学习》完整版系列）第14章 概率图模型——14.5 学习与推断之信念传播（消息传递的画法及消息计算）

信念传播算法是利用图的可视化表达。
有向图时必须是先画完了再计算，因为，后退画出当前传递线时，“余入”并没有画出，当然不知道“余入”的值，故不能计算当前“一出”的值。 无向图是在画的过程中，同时计算出该传递线的消息值。在无向无环图情形下，可采用双向传递线画法。

信念传播

将上述“$m$化”的过程抽象到一般，称之为信念传播算法，中途的任一个“$m$化”由【西瓜书式(14.19)】表达，即
m i j ( x j ) = ∑ x i ψ ( x i , x j ) ∏ k ∈ n ( i ) ∖ { j } m k i ( x i ) \begin{align} m_{ij}{(x_j)}=\sum_{x_i}\psi (x_i,x_j)\prod _{k\in n(i)\setminus \{j\}}m_{ki}(x_i) \tag{14.36} \end{align} mij​(xj​)=xi​∑​ψ(xi​,xj​)k∈n(i)∖{j}∏​mki​(xi​)​(14.36)​

所谓的消息传递，是图上的可视化表达，其实质是依式(14.36)进行的计算。

1.有向无环图

对于有向无环图的情形，我们对照【西瓜书图14.7】的例子进行理解。

（1）画消息传递线：先不考虑图中边的方向，画出所有消息传递线【西瓜书图14.7(b)】，而消息传递线本身是有方向的。

i. 找出最终要求的边际概率结点$x_5$，画出以其为终点，以邻接结点为始点的所有传递线，这种先确定终点的画法称为后退画法，如$x_5\leftarrow x_3$；

ii. 对每个已画的传递线的始结点（如，$x_3$），画出以其为终点，始点为邻接结点（剔除已画线的边）的所有传递线（如，$x_3\leftarrow x_2$，$x_3\leftarrow x_4$，没有$x_3\leftarrow x_5$）；

iii. 对于无环连通图，反复用ii. 后退地画 即可使得图的每条边上都有唯一一条传递线；

iv. 在所有传递线上标上消息记号（$m_{ij}(x_j)$），其中，下标$ij$对应于传递线的方向$x_i\to x_j$，显然，每结点的消息传递线是“一出余入”的，这是后退画法的必然结果。

（2）再确定消息$m_{ij}(x_j)$

为强调有向图的特点，我们将式(14.36)中的$\psi (x_i,x_j)$调整$Q(x_i,x_j)$，即设
m i j ( x j ) = ∑ x i Q ( x i , x j ) ∏ k ∈ n ( i ) ∖ { j } m k i ( x i ) \begin{align} m_{ij}{(x_j)}=\sum_{x_i}Q (x_i,x_j)\prod _{k\in n(i)\setminus \{j\}}m_{ki}(x_i) \tag{14.37} \end{align} mij​(xj​)=xi​∑​Q(xi​,xj​)k∈n(i)∖{j}∏​mki​(xi​)​(14.37)​
从前述画传递线过程可知：对于结点$x_i$而言的“一出余入”消息传递线是：“一出”是指“$x_i\to x_j$”对应于式(14.37)中左侧要计算的消息$m_{ij}$，“余入”是指计算时需要用到其它所有“入边”（即右侧和式${\sum }_{x_i}$），每条“入边”有两个因子：消息积 ∏ k ∈ n ( i ) ∖ { j } m k i ( x i ) \prod _{k\in n(i)\setminus \{j\}}m_{ki}(x_i) ∏k∈n(i)∖{j}​mki​(xi​)和因子$Q$，端点情况特殊。

i. 消息积 ∏ k ∈ n ( i ) ∖ { j } m k i ( x i ) \prod _{k\in n(i)\setminus \{j\}}m_{ki}(x_i) ∏k∈n(i)∖{j}​mki​(xi​)

把消息理解成收到消息的概率，则该“消息积”表示$x_i$收到它应收的所有消息的概率，$x_i$的应收消息为：$x_i$的所有邻接点除$x_j$外（ k ∈ n ( i ) ∖ { j } {k\in n(i)\setminus \{j\}} k∈n(i)∖{j}）都应向它传递消息$m_{ki}(x_i)$（路径“$x_k\to x_i$”）。 如，【西瓜书图14.7(b)】中$x_3$的消息积为 ∏ k ∈ n ( 3 ) ∖ { 5 } m k 3 ( x 3 ) = m 23 ( x 3 ) m 43 ( x 3 ) \prod _{k\in n(3)\setminus \{5\}}m_{k3}(x_3)=m_{23}(x_3)m_{43}(x_3) ∏k∈n(3)∖{5}​mk3​(x3​)=m23​(x3​)m43​(x3​)

ii. 因子$Q$

需要结合有向图的方向确定因子$Q$
$$\begin{array}{r}Q(x_i,x_j)=\{\begin{array}{l}P(x_i|x_j),\text{（有向图中有边xj→xi）}\\ P(x_j|x_i),\text{（有向图中有边xi→xj）}\end{array}\end{array}\text{\hspace{1em}(14.38)}$$
如，【西瓜书图14.7(a)】知，$Q(x_3,x_5)=P(x_5|x_3)$

上述公式表明：在画消息传递线时，并不考虑有向图中边的方向，而是在计算式(14.37)中的因子$Q(x_i,x_j)$，通过式(14.38)使边的方向起作用。

结合上述i.和ii.中的举例，由式(14.37)有
m 35 ( x 5 ) = ∑ x 3 Q ( x 3 , x 5 ) ∏ k ∈ n ( 3 ) ∖ { 5 } m k 3 ( x 3 ) = ∑ x 3 P ( x 5 ∣ x 3 ) m 23 ( x 3 ) m 43 ( x 3 ) \begin{align*} m_{35}{(x_5)} & =\sum_{x_3}Q (x_3,x_5)\prod _{k\in n(3)\setminus \{5\}}m_{k3}(x_3)\notag \\ & =\sum_{x_3}P (x_5\,|\,x_3)m_{23}(x_3)m_{43}(x_3) \end{align*} m35​(x5​)​=x3​∑​Q(x3​,x5​)k∈n(3)∖{5}∏​mk3​(x3​)=x3​∑​P(x5​∣x3​)m23​(x3​)m43​(x3​)​

iii. 端点情况

特别，当结点$x_i$为图中的端点时，结点$x_i$只有一个邻近结点，设它为$x_j$，即 n ( i ) ∖ { j } = ∅ n(i)\setminus \{j\}=\varnothing n(i)∖{j}=∅，式(14.37)中“连积”定义为
∏ k ∈ n ( i ) ∖ { j } = ∅ m k i ( x i ) = { 1 , （图的有向边为 x j → x i ,消息逆向） P ( x i ) , （图的有向边为 x i → x j ,消息顺向） \begin{align} \prod _{k\in n(i)\setminus \{j\}=\varnothing}m_{ki}(x_i)= \begin{cases} 1, & \text{（图的有向边为$x_j\rightarrow x_i$,消息逆向）} \\ P(x_i), & \text{（图的有向边为$x_i\rightarrow x_j$,消息顺向）} \\ \end{cases} \tag{14.39} \end{align} k∈n(i)∖{j}=∅∏​mki​(xi​)={1,P(xi​),​（图的有向边为xj​→xi​,消息逆向）（图的有向边为xi​→xj​,消息顺向）​​(14.39)​
如，【西瓜书图14.7(a)(b)】中由式(14.37)、式(14.39)有
m 12 ( x 2 ) = ∑ x 1 Q ( x 1 , x 2 ) ∏ k ∈ n ( 1 ) ∖ { 2 } m k 1 ( x 1 ) = ∑ x 1 P ( x 2 ∣ x 1 ) P ( x 1 ) （【西瓜书图14.7(a)】中 x 1 → x 2 ） = P ( x 2 ) m 43 ( x 3 ) = ∑ x 4 Q ( x 4 , x 3 ) ∏ k ∈ n ( 4 ) ∖ { 3 } m k 4 ( x 4 ) = ∑ x 4 P ( x 4 ∣ x 3 ) （有向图中 x 3 → x 4 ） m 35 ( x 5 ) = ∑ x 3 Q ( x 3 , x 5 ) ∏ k ∈ n ( 3 ) ∖ { 5 } m k 3 ( x 3 ) = ∑ x 3 P ( x 5 ∣ x 3 ) P ( x 3 ) （有向图中 x 3 → x 5 ） = P ( x 5 ) \begin{align*} m_{12}{(x_2)} & =\sum_{x_1}Q (x_1,x_2)\prod _{k\in n(1)\setminus \{2\}}m_{k1}(x_1) \\ & =\sum_{x_1}P (x_2\,|\,x_1)P(x_1)\quad \text{（【西瓜书图14.7(a)】中$x_1\to x_2$）} \\ & =P(x_2)\\ m_{43}{(x_3)} & =\sum_{x_4}Q (x_4,x_3)\prod _{k\in n(4)\setminus \{3\}}m_{k4}(x_4) \\ & =\sum_{x_4}P (x_4\,|\,x_3)\quad \text{（有向图中$x_3\to x_4$）}\\ m_{35}{(x_5)} & =\sum_{x_3}Q (x_3,x_5)\prod _{k\in n(3)\setminus \{5\}}m_{k3}(x_3) \\ & =\sum_{x_3}P (x_5\,|\,x_3)P(x_3)\quad \text{（有向图中$x_3\to x_5$）} \\ & =P(x_5) \end{align*} m12​(x2​)m43​(x3​)m35​(x5​)​=x1​∑​Q(x1​,x2​)k∈n(1)∖{2}∏​mk1​(x1​)=x1​∑​P(x2​∣x1​)P(x1​)（【西瓜书图14.7(a)】中x1​→x2​）=P(x2​)=x4​∑​Q(x4​,x3​)k∈n(4)∖{3}∏​mk4​(x4​)=x4​∑​P(x4​∣x3​)（有向图中x3​→x4​）=x3​∑​Q(x3​,x5​)k∈n(3)∖{5}∏​mk3​(x3​)=x3​∑​P(x5​∣x3​)P(x3​)（有向图中x3​→x5​）=P(x5​)​
故有【西瓜书式(14.16)】的计算式。

2.无向无环图

在无向无环图中，针对具体需要求的边际概率结点，可仿前述有向图的传递线画法处理，但换一个边际概率结点又要再画，对应的计算量就重复了，能否有与所求边际概率结点无关的画法呢？在无向无环图情形下，可采用双向传递线画法【西瓜书图14.8(a)(b)】对应的画法：

i. 建树： 对于无向无环图，任取一个结点为根，将其拎起来，则形成一棵树（倒立的）；

ii. 向上画：先从叶子结点向根的方向前进地画传递线，即画以叶子结点为起点的传递线，逐层前进到根，形成一个从底向上指向的有向图。 注：在有向图时采用的是后退式（先定终点，“终点$\leftarrow$起点”）画法，而无向图采用的是前进式（先定起点，“起点$\to$终点”）画法。

在画的过程中，同时计算出该传递线的消息值。
注：这也是与有向图的区别：有向图时必须是先画完了再计算，因为，后退画出当前传递线时，“余入”并没有画出，当然不知道“余入”的值，故不能计算当前“一出”的值。 无向图是在画的过程中，同时计算出该传递线的消息值。

如图14.8 (a)中，虚线表示当前所画传递线，非端点结点处的消息均依式(14.36)采用“一出余入”方式计算：“一出”指需要计算的虚线消息$m_{ij}(x_j)$，“余入”指需要用到该结点其余所有边上的消息 ∏ k ∈ n ( i ) ∖ { j } m k i ( x i ) \prod _{k\in n(i)\setminus \{j\}}m_{ki}(x_i) ∏k∈n(i)∖{j}​mki​(xi​)，对比有向图时的式(14.37)，这时，将其中的$Q(x_i,x_j)$调整成了势函数$\psi (x_i,x_j)$，同样地， k ∈ n ( i ) ∖ { j } {k\in n(i)\setminus \{j\}} k∈n(i)∖{j}体现了“一出余入”的要求。

iii. 向下画：再从根结点向叶子的方向（前进地）画传递线，即画以根结点为起点的传递线，逐层前进到叶子。 在画的过程中，同时计算出该传递线的消息值。 如图14.8 (b)中，虚线表示当前所画传递线，依式(14.36)计算“一出”的虚线消息$m_{ij}(x_j)$时，“余入”不足（右边枝上没有“入”），因此，需要借用图14.8 (a)中向上以画的的“入”，为示区别我们在图14.8 ©图用粗线表示，形成©图后，即可用“一出余入”方式计算了。 因此，ii. 与iii. 画的次序不要弄反了，否则在分叉前进时没有“借”的了。

上述依式(14.36)计算时，端点$x_i$处会出现 k ∈ n ( i ) ∖ { j } = ∅ {k\in n(i)\setminus \{j\}}=\varnothing k∈n(i)∖{j}=∅，需要作出合理规定：
∏ k ∈ n ( i ) ∖ { j } m k i ( x i ) = 1 \begin{align} \prod _{k\in n(i)\setminus \{j\}}m_{ki}(x_i)=1 \tag{14.40} \end{align} k∈n(i)∖{j}∏​mki​(xi​)=1​(14.40)​

消息的双向传递（画图并计算）后，则可用【西瓜书式(14.20)】计算图上任一结点变量的边际概率分布（的正比例），
如，【西瓜书图14.8(b)】中：
$$\begin{array}{r}P(x_2)\propto m_{12}(x_2)m_{32}(x_2)\end{array}\text{\hspace{1em}(14.41)}$$
如何把“$\propto$”变为“$=$”呢？这就是找规范因子$Z$，设$x_2$的所有取值为$x_2^t,t=1,2,\cdots ,k$，则
$$\begin{array}{rl}& \sum _{t=1}^{k}P(x_2=x_2^t)=1\\ \text{即： }& \frac{1}{Z}\sum _{t=1}^k{m}_{12}(x_2^t)m_{32}(x_2^t)=1\\ \text{即： }& Z=\sum _{t=1}^k{m}_{12}(x_2^t)m_{32}(x_2^t)\end{array}$$
一般地，【西瓜书式(14.20)】的规范化因子为
$$\begin{array}{r}Z=\sum _{x_i}\prod _{k\in ni}{m}_{ki}(x_i)\end{array}\text{\hspace{1em}(14.42)}$$

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：14.4 学习与推断之变量消去法（“边际化”，“m化”逐步消元）
下一篇：14.6 采样：马尔可夫链蒙特卡罗MCMC方法（为何要采样？如何变通采样？）