概率图推断之信念传播
在《概率图推断之变量消除算法》中，我们讲了变量消除算法如何对有向图和无向图求 P ( Y ∣ E = e ) P(Y \mid E = e) P(Y∣E=e)的边缘概率。
然而变量消除算法有个致命的缺陷：如果我们问模型另一个请求，比如 P ( Y 2 ∣ E 2 = e 2 ) P(Y_2 \mid E_2 = e_2) P(Y2∣E2=e2)，我们需要从头开始重新启动算法。这样会非常浪费资源，并且在计算上很麻烦。
幸运的是，事实证明，这个问题也很容易避免。当计算边缘概率时，变量消除算法会产生许多中间因子 τ \tau τ；事实证明，这些因子与计算其他边缘概率所需的因子相同。通过在第一次运行变量消除算法后缓存这些因子，我们可以轻松地计算新的边缘概率查询，基本上不需要额外的成本。
从本文开始，我会用两篇文章来介绍该算法的两种变体：信念传播（BP）和全联结树算法。信念传播适用于树结构图，而联结树算法适用于一般网络。
让我们先从信念传播算法开始。
将变量消除视为信息传递
首先，思考一下在树上执行变量消除算法计算边缘概率 p ( x i ) p(x_i) p(xi)都发生了什么？不难发现将 x i x_i xi作为根节点然后遍历后续节点是解决此问题的最优排序。
我们说这个排序最优是因为变量消除过程中形成的最大团的大小为2。每一步，我们消除 x j x_j xj。这会引发计算因子 τ k ( x k ) = ∑ x j ϕ ( x k , x j ) τ j ( x j ) \tau_k(x_k) = \sum_{x_j} \phi(x_k, x_j) \tau_j(x_j) τk(xk)=∑xjϕ(xk,xj)τj(xj) ，其中 x k x_k xk 是 x j x_j xj 的父节点。紧跟着下一步， x k x_k xk 会被消除， τ k ( x k ) \tau_k(x_k) τk(xk)会被传递给 x k x_k xk 的父节点 x l x_l xl 用以在边缘化之前与因子 ϕ ( x l , x k ) \phi(x_l, x_k) ϕ(xl,xk)相乘。因子 τ j ( x j ) \tau_j(x_j) τj(xj)可以认为是 x j x_j xj传给 x k x_k xk的消息，其汇总了以 x j x_j xj为根节点的子树下的所有信息。
在变量消除的最后， x i x_i xi收到其所有直接子节点的信息，然后对这些信息边缘化，我们就得到最终的边缘概率。
现在假设计算完 p ( x i ) p(x_i) p(xi)，我们还想计算 p ( x k ) p(x_k) p(xk)，我们需要将 x k x_k xk作为跟节点重新执行变量消除算法，直到 x k x_k xk收到所有子节点的信息。这里的核心洞察是：无论 x k x_k xk为跟节点还是 x i x_i xi为根节点， x k x_k xk从 x j x_j xj收到的信息是一样的。
信息传递算法
这里的关键问题是：如何精确计算出所有需要的信息？
答案很简单：每当 x i x_i xi收到除邻居 x j x_j xj外所有节点的信息时， x i x_i xi传递消息给邻居 x j x_j xj。有趣的是在树上总有节点要传递信息，直到所有信息都传递出去。这个过程需要 2 ∣ E ∣ 2|E| 2∣E∣步，因为每条边只会接收信息2次：一次 x i → x j x_i \rarr x_j xi→xj，一次反方向 x i ← x j x_i \larr x_j xi←xj。
最后，这个算法之所以正确是因为这些信息在变量消除算法中被定义为中间因子。
下面我们给信念传播算法下个正式的定义，该算法2个变种，分别适用于不同的任务：
- 加总乘积信息传递：用于边缘推断，例如计算 p ( x i ) p(x_i) p(xi)
- 最大乘积信息传递：用于最大后验推断，例如计算 max x 1 , … , x n p ( x 1 , … , x n ) \max_{x_1, \dotsc, x_n} p(x_1, \dotsc, x_n) maxx1,…,xnp(x1,…,xn)
加总乘积信息传递
加总乘积信息传递算法定义如下：若节点 x i x_i xi可以传递到 x j x_j xj，传递信息
m i → j ( x j ) = ∑ x i ϕ ( x i ) ϕ ( x i , x j ) ∏ ℓ ∈ N ( i ) ∖ j m ℓ → i ( x i ) m_{i\to j}(x_j) = \sum_{x_i} \phi(x_i) \phi(x_i,x_j) \prod_{\ell \in N(i) \setminus j} m_{\ell \to i}(x_i) mi→j(xj)=xi∑ϕ(xi)ϕ(xi,xj)ℓ∈N(i)∖j∏mℓ→i(xi)
这里 N ( i ) ∖ j N(i) \setminus j N(i)∖j表示除 j j j以外 i i i的所有邻居的集合。观察上面公式可以发现，为了计算 p ( x j ) p(x_j) p(xj)所做的一轮变量消除中 x i x_i xi传递给 x j x_j xj的信息就是因子 τ \tau τ 。
基于此观察，计算出所有信息后，我们可以通过下面公式在常数时间内给出 x i x_i xi上所有边缘查询
p ( x i ) ∝ ϕ ( x i ) ∏ ℓ ∈ N ( i ) m ℓ → i ( x i ) . p(x_i) \propto \phi(x_i) \prod_{\ell \in N(i)} m_{\ell \to i}(x_i). p(xi)∝ϕ(xi)ℓ∈N(i)∏mℓ→i(xi).
因子树上的加总乘积信息传递
加总乘积信息传递稍作修改也可以适用于因子树。因子图是一个二分图，由边连接变量和因子，表示某因子依赖某变量。
在因子图上有两类信息：变量到因子信息 ν \nu ν和因子到变量信息 μ \mu μ。二者都需要计算乘积，但只有因子到变量信息 μ \mu μ需要加总。
ν v a r ( i ) → f a c ( s ) ( x i ) = ∏ t ∈ N ( i ) ∖ s μ f a c ( t ) → v a r ( i ) ( x i ) μ f a c ( s ) → v a r ( i ) ( x i ) = ∑ x N ( s ) ∖ i f s ( x N ( s ) ) ∏ j ∈ N ( s ) ∖ i ν v a r ( j ) → f a c ( s ) ( x j ) \nu_{var(i)\to fac(s)}(x_i) = \prod_{t\in N(i)\setminus s}\mu_{fac(t)\to var(i)}(x_i) \\ \mu_{fac(s)\to var(i)}(x_i) = \sum_{x_{N(s)\setminus i}}f_s(x_{N(s)})\prod_{j\in N(s)\setminus i}\nu_{var(j)\to fac(s)}(x_j) νvar(i)→fac(s)(xi)=t∈N(i)∖s∏μfac(t)→var(i)(xi)μfac(s)→var(i)(xi)=xN(s)∖i∑fs(xN(s))j∈N(s)∖i∏νvar(j)→fac(s)(xj)
该算法过程与无向图上的算法过程相同：只要有因子（或变量）可以传递信息给变量（或因子），那就以上面公式的形式传递相应因子到变量（或者变量到因子）信息。
最大乘积信息传递
信念传播算法的第二个变种是最大乘积信息传递，用于最大后验推断 max x 1 , … , x n p ( x 1 , … , x n ) \max_{x_1, \dotsc, x_n} p(x_1, \dotsc, x_n) maxx1,…,xnp(x1,…,xn)。
上面介绍的边缘推断框架也可以让我们轻松进行最大后验推断。关键点在于求和和求最大值运算都作用于乘积上，因此将边缘推断中的求和替换为求最大值，即可解决最大后验推断问题。
例如，我们可以通过下面公式计算马尔科夫随机场链的配分函数：
Z = ∑ x 1 ⋯ ∑ x n ϕ ( x 1 ) ∏ i = 2 n ϕ ( x i , x i − 1 ) = ∑ x n ∑ x n − 1 ϕ ( x n , x n − 1 ) ∑ x n − 2 ϕ ( x n − 1 , x n − 2 ) ⋯ ∑ x 1 ϕ ( x 2 , x 1 ) ϕ ( x 1 ) . \begin{align*} Z &= \sum_{x_1} \cdots \sum_{x_n} \phi(x_1) \prod_{i=2}^n \phi(x_i, x_{i-1}) \\ &= \sum_{x_n} \sum_{x_{n-1}} \phi(x_n, x_{n-1}) \sum_{x_{n-2}} \phi(x_{n-1}, x_{n-2}) \cdots \sum_{x_1} \phi(x_2 , x_1) \phi(x_1). \end{align*} Z=x1∑⋯xn∑ϕ(x1)i=2∏nϕ(xi,xi−1)=xn∑xn−1∑ϕ(xn,xn−1)xn−2∑ϕ(xn−1,xn−2)⋯x1∑ϕ(x2,x1)ϕ(x1).
要计算 p ( x 1 , … , x n ) p(x_1, \dotsc, x_n) p(x1,…,xn)上的最大值 p ∗ p^* p∗，只需要将求和替换为求最大值即可：
p ∗ = max x 1 ⋯ max x n ϕ ( x 1 ) ∏ i = 2 n ϕ ( x i , x i − 1 ) = max x n max x n − 1 ϕ ( x n , x n − 1 ) max x n − 2 ϕ ( x n − 1 , x n − 2 ) ⋯ max x 1 ϕ ( x 2 , x 1 ) ϕ ( x 1 ) . \begin{align*} p^* &= \max_{x_1} \cdots \max_{x_n} \phi(x_1) \prod_{i=2}^n \phi(x_i, x_{i-1}) \\ &= \max_{x_n} \max_{x_{n-1}} \phi(x_n, x_{n-1}) \max_{x_{n-2}} \phi(x_{n-1}, x_{n-2}) \cdots \max_{x_1} \phi(x_2 , x_1) \phi(x_1). \end{align*} p∗=x1max⋯xnmaxϕ(x1)i=2∏nϕ(xi,xi−1)=xnmaxxn−1maxϕ(xn,xn−1)xn−2maxϕ(xn−1,xn−2)⋯x1maxϕ(x2,x1)ϕ(x1).
因为二者采用相同方式分解，我们可以直接复用边缘推断的机制到最大后验推断。注意，这个思路同样适用于因子树。
这里有一小点需要注意，我们通常需要的不只最大分布，例如 max x p ( x ) \max_x p(x) maxxp(x)，还需要其最可能赋值，例如 arg max x p ( x ) \arg\max_x p(x) argmaxxp(x)。这个问题可以通过在优化过程中保存反向指针来轻松解决。例如，上面例子中，对每一个 x 2 x_2 x2的赋值，我们可以保存 x 1 x_1 x1最优赋值的反向指针，同理对每一个 x 3 x_3 x3赋值，我们可以保存 x 2 x_2 x2最优赋值的反向指针，以此类推。
总结
以上就是信念传播算法的介绍。信念传播算法适用于树形结构，而我们的问题往往是更一般的图。在图上做推断会更加困难，但我们可以尝试将图分解为近似树型结构，然后执行信息传递算法。根据此思想发展出了联结树算法。下一章我会重点介绍联结树算法，敬请期待。