有向图 vs 无向图

贝叶斯网络(信念网络)都是有向的,马尔科夫网络无向.所以,贝叶斯网络适合为有单向依赖的数据建模,马尔科夫网络适合实体之间互相依赖的建模。具体地,他们的核心差异表现在如何求 P=(Y) ,即怎么表示 Y=(y_{1},\cdots,y_{n}) 这个的联合概率。

有向图

对于有向图模型,这么求联合概率: P(x_{1}, {\cdots}, x_{n} )=\prod_{i=0}P(x_{i} | \pi(x_{i}))

举个例子,对于下面的这个有向图的随机变量(注意,这个图我画的还是比较广义的):

image

应该这样表示他们的联合概率:

P(x_{1}, {\cdots}, x_{n} )=P(x_{1})·P(x_{2}|x_{1} )·P(x_{3}|x_{2} )·P(x_{4}|x_{2} )·P(x_{5}|x_{3},x_{4} )

应该很好理解吧。

无向图

对于无向图,我看资料一般就指马尔科夫网络(注意,这个图我画的也是比较广义的)。

image

如果一个graph太大,可以用因子分解将$ P=(Y)$ 写为若干个联合概率的乘积。咋分解呢,将一个图分为若干个“小团”,注意每个团必须是“最大团”(就是里面任何两个点连在了一块,具体……算了不解释,有点“最大连通子图”的感觉),则有:

P(Y )=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} ) 数学公式 $$

, 其中 Z(x) = \sum_{Y} \prod_{c}\psi_{c}(Y_{c} ) ,公式应该不难理解吧,归一化是为了让结果算作概率。

所以像上面的无向图:

P(Y )=\frac{1}{Z(x)} ( \psi_{1}(X_{1}, X_{3}, X_{4} ) · \psi_{2}(X_{2}, X_{3}, X_{4} ) )

其中, \psi_{c}(Y_{c} ) 是一个最大团 C 上随机变量们的联合概率,一般取指数函数的:

\psi_{c}(Y_{c} ) = e^{-E(Y_{c})} =e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)}

好了,管这个东西叫做势函数。注意 e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} 是否有看到CRF的影子。

那么概率无向图的联合概率分布可以在因子分解下表示为:

P(Y )=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} ) = \frac{1}{Z(x)} \prod_{c} e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} = \frac{1}{Z(x)} e^{\sum_{c}\sum_{k}\lambda_{k}f_{k}(y_{i},y_{i-1},x,i)}

注意,这里的理解还蛮重要的,注意递推过程,敲黑板,这是CRF的开端!
这个由Hammersly-Clifford law保证,具体不展开。

posted @ 2018-10-11 13:53:39
评论加载中...
发表评论