五分钟看懂因子图和消息传递算法
文章目录
本文将系统带你理解因子图，以及信息是如何在因子图上传播的（消息传递），其实已经有博客讲了这个问题，但是自己当时在看的时候还是有一些点不明所以，因此继续深入探究了一下， 并把自己的理解列出如下：
为什么要有因子图？
其实在因子图出来之前，还有一个东西叫有向图（用箭头来代表因果关系），可以看成上面这么个玩意1，其实它已经能很好地表示概率的依赖关系了，比如我们可以将其写作：
P ( x ) = P ( x 1 ) P ( x 2 ) P ( x 3 ) P ( x 4 ∣ x 1 , x 2 , x 3 ) P ( x 5 ∣ x 1 , x 3 ) P ( x 6 ∣ x 4 ) P ( x 7 ∣ x 4 , x 5 ) P(x) = P(x_1)P(x_2)P(x_3)P(x_4 \mid x_1,x_2,x_3)P(x_5 \mid x_1,x_3)P(x_6 \mid x_4)P(x_7 \mid x_4,x_5) P(x)=P(x1)P(x2)P(x3)P(x4∣x1,x2,x3)P(x5∣x1,x3)P(x6∣x4)P(x7∣x4,x5)
但是如果用因子图的方式写，就是下面这样子：
P ( x ) = P ( x 1 ) P ( x 2 ) P ( x 3 ) P ( x 4 ∣ x 1 , x 2 , x 3 ) P ( x 5 ∣ x 1 , x 3 ) P ( x 6 ∣ x 4 ) P ( x 7 ∣ x 4 , x 5 ) = f ( x 1 ) f ( x 2 ) f ( x 3 ) f ( x 1 , x 2 , x 3 , x 4 ) f ( x 1 , x 3 , x 5 ) f ( x 4 , x 6 ) f ( x 4 , x 5 , x 7 ) \begin{align*} P(x) &= P(x_1)P(x_2)P(x_3)P(x_4 \mid x_1,x_2,x_3)P(x_5 \mid x_1,x_3)P(x_6 \mid x_4)P(x_7 \mid x_4,x_5)\\ &= f(x_1)f(x_2)f(x_3)f(x_1,x_2,x_3,x_4)f(x_1,x_3,x_5)f(x_4,x_6)f(x_4,x_5,x_7) \end{align*} P(x)=P(x1)P(x2)P(x3)P(x4∣x1,x2,x3)P(x5∣x1,x3)P(x6∣x4)P(x7∣x4,x5)=f(x1)f(x2)f(x3)f(x1,x2,x3,x4)f(x1,x3,x5)f(x4,x6)f(x4,x5,x7)
那问题就来了，为什么有向图可以表示因果关系，还要引出因子图这种写法，最后变成了一个联合分布，也看不出因果对应关系呢？其实“无条件概率”其实是条件概率的一种特殊情况。这里： p ( x 1 ) p(x_1) p(x1), p ( x 2 ) p(x_2) p(x2), p ( x 3 ) p(x_3) p(x3)看似不是条件概率，其实是： p ( x 1 ) = p ( x 1 ∣ P a ( x 1 ) = ∅ ) p(x_1) = p(x_1 | Pa(x_1) = \emptyset) p(x1)=p(x1∣Pa(x1)=∅)，即“没有父节点的节点”，其条件概率就是它本身，我们需要注意以下两点：
【1】BN（贝叶斯网络）的因子有向图必须是合法的条件概率分布。条件概率分布必须满足：
- 必须归一化： ∑ x i p ( x i ∣ p a r e n t s ) = 1 \sum_{x_i} p(x_i | parents) = 1 ∑xip(xi∣parents)=1
- 必须是概率值，取值范围是 [ 0 , 1 ] [0,1] [0,1]
- 必须表达“父变量→子变量”的因果方向
【2】因子图（Factor Graph）的因子是任意非负函数，完全没有这些限制。因子 f ( x 1 , x 2 , x 3 ) f(x_1,x_2,x_3) f(x1,x2,x3)可以是：
- 不归一化
- 值可以是任意正数（10,0.3, e − 3 e^{-3} e−3,99999都行）
- 可以表示能量 e − E e^{-E} e−E
- 完全没有因果含义
它们只需要满足： f ( x ) ≥ 0 f(x) \geq 0
