马尔科夫网源自统计物理学中的马尔科夫随机场这一概念.有些资料中将马尔科夫网称之为马尔科夫随机场,指的都是同一个东西.

在介绍马尔科夫网之前,我们先来回顾一下贝叶斯网,对于下面的贝叶斯网:
image.png
可以这样计算他们的联合概率:

P(A,B,C,D) = P(A)P(B | A)P(D | A)P(C | B)P(C | D)

马尔科夫网

考虑这样一个例子,有四位同学要求两两组队来完成作业,A与C合不来,B与D刚刚结束了一段糟糕的恋情.

现在我们把可能的组队关系画出来:

因为事件之间没有因果关系,所以我们使用直线来绘制图形.这种无向图被称为马尔科夫网.

在无向图中,两个相连的事件没有因果关系,所以我们不能使用条件概率来参数化这个模型,直观上,无向边表达的是相关变量之间的亲密关系,我们可以使用一个函数来描述这种亲密关系,这个描述亲密关系的函数\phi被称为因子.

于是我们定义四个因子来描述各变量之间的亲密度:

\phi(A,B),\phi(B,C),\phi(C,D),\phi(D,A)

现在来思考如何通过因子来计算联合概率P(A,B,C,D)?我们非常希望马尔科夫网可以像贝叶斯网那样,局部模型可以以相乘的形式进行组合:

P(A,B,C,D) = \frac{1}{Z}\phi(A,B)\phi(A,D)\phi(B,C)\phi(D,C)

因为之间相乘之后不是一个概率,所以这里添加归一化常数Z将乘积转换为概率.从这里可知马尔科夫中的因子可以类比成贝叶斯网中的条件概率.

对于未归一化的因子乘积,可以表示为一个更大的因子:

\phi(A,B,C,D) = \phi(A,B)\phi(A,D)\phi(B,C)\phi(D,C)

团与极大团

下图是一个简单的马尔科夫网,对于图中结点的一个子集,若其中任意两结点间都有边连接,则称该结点子集为一个"团".若在一个团中加入另外任何一个结点都不再形成团,则称该团为"极大团";换言之,极大团就是不能被其他团所包含的团.例如在下图中,\left\{ x _ { 1 } , x _ { 2 } \right\} , \left\{ x _ { 1 } , x _ { 3 } \right\} , \left\{ x _ { 2 } , x _ { 4 } \right\} , \left\{ x _ { 2 } , x _ { 5 } \right\} , \left\{ x _ { 2 } , x _ { 6 } \right\} , \left\{ x _ { 3 } , x _ { 5 } \right\} , \left\{ x _ { 5 } , x _ { 6 } \right\}都是团,并且除了\left\{ x _ { 2 } , x _ { 5 } \right\} , \left\{ x _ { 2 } , x _ { 6 } \right\}\left\{ x _ { 5 } , x _ { 6 } \right\}之外都是极大团;但是,因为x_2x_3之间缺乏连接,\left\{ x _ { 1 } , x _ { 2 } , x _ { 3 } \right\}并不构成团.显然,每个结点至少出现在一个极大团中.
image.png

最少参数的马尔科夫网

又因为马尔科夫中的因子可以类比成贝叶斯网中的条件概率,对于概率公式:

P(X,Y,Z) = P(X)P(Y|X)P(Z|X)

可以类比成:

\phi(X,Y,Z) = \phi(Y,X)\phi(Z,X)

根据因子的这一性质,对于n个变量\mathbf { x } = \left\{ x _ { 1 } , x _ { 2 } , \ldots , x _ { n } \right\},所构成的集合为\mathcal { C },与团Q \in \mathcal { C }对应的变量集合记为\mathbf { x } _ { Q },则P ( \mathbf { x } )可以写成多个因子相乘的形式:

P ( \mathbf { x } ) = \frac { 1 } { Z } \prod _ { Q \in \mathcal { C } } \phi _ { Q } \left( \mathbf { x } _ { Q } \right)

其中Z = \sum _ { \mathbf { x } } \prod _ { Q \in \mathcal { C } } \phi _ { Q } \left( \mathbf { x } _ { Q } \right)为归一化常数,确保结果是概率.

例如上图中的极大团为:\left\{ x _ { 1 } , x _ { 2 } \right\} , \left\{ x _ { 1 } , x _ { 3 } \right\} , \left\{ x _ { 2 } , x _ { 4 } \right\} ,  \left\{ x _ { 3 } , x _ { 5 } \right\},\{x _ { 2} , x _ { 5 }, x _ { 6 }\}

其联合概率可以表示为:

P (x _ { 1 } , x _ { 2 },x _ { 3 } , x _ { 4 },x _ { 5 } , x _ { 6 })=\frac { 1 } { Z }\phi(x _ { 1 } , x _ { 2 })\phi(x _ { 1 } , x _ { 3 })\phi(x _ { 2 } , x _ { 4 })\phi(x _ { 3} , x _ { 5 })\phi(x _ { 2} , x _ { 5 }, x _ { 6 })

Z = \sum _ { x _ { 6 } } \sum _ { x _ { 5 } }\sum _ { x _ { 4 } }\sum _ { x _ { 3 } } \sum _ { x _ { 2 } } \sum _ { x _ { 1 } }\phi(x _ { 1 } , x _ { 2 })\phi(x _ { 1 } , x _ { 3 })\phi(x _ { 2 } , x _ { 4 })\phi(x _ { 3} , x _ { 5 })\phi(x _ { 2} , x _ { 5 }, x _ { 6 })

显然,若变量个数较多,则团的数目将会很多,这意味着上式会有很多乘积,注意到若团Q不是极大团,则必然被一个极大团所包含,这意味着变量\mathbf { x } _ { Q }之间的关系不仅体现在\phi_Q中,而且体现在包含Q的极大团中.所以联合概率P ( \mathbf { x } )可基于极大团来定义,即假定上式中的Q都为极大团.

对数线性模型

马尔科夫网中的因子函数\phi(D)可以任意指定,因子是表示两个变量之间关系的亲密程度的一个值,越亲密,值越大,反之越小.并且因子要保证不能为负.满足这个条件的函数有很多,我们定义如下:

\phi(D) = exp(-\epsilon(D))

我们看到其实\phi(D)的大小其实取决于\epsilon(D),那么为什么不直接把\epsilon(D)定义为因子呢?因为我们想利用指数把乘法变成加法:

P(X_1,X_2,...,X_n) = \frac{1}{Z}exp[-\sum_{i=1}^k \epsilon_i(D_i)]

k为极大团个数,\epsilon(D)被称为能级函数,变量之间相关性越高,能级函数越大.试想一下一个可能的能级函数:

\epsilon(A,B)=\begin{cases} -3,& A = B \newline  0,& other \end{cases}

能级函数可以写成特征函数与权值乘积的形式:

\epsilon(D) = \omega f(D)

特征函数通常取0或1:

f(A,B)=\begin{cases} 1,& A = B \newline  0,& other \end{cases}

于是:

P(X_1,X_2,...,X_n) = \frac{1}{Z}exp[-\sum_{i=1}^k \omega_i f_i(D_i)]

马尔科夫网中的独立性

成对马尔科夫性:设u和v是无向图G中任意两个没有直接相连的结点,结点u和v分别对应随机变量Y_uY_v.其他所有节点为O,对应的随机变量组是Y_O.成对马尔科夫性是指给定随机变量组Y_O的条件下随机变量Y_uY_v是条件独立的,即:

P(Y_u,Y_v | Y_O) = P(Y_u | Y_O)P(Y_v | Y_O)

局部马尔科夫性:设v\in V是无向图G中任意一个节点,W是与v有边连接的所有节点,O是v,W以外的其他所有节点.v表示的随机变量是Y_v,W表示的随机变量组是Y_W,O表示的随机变量组是Y_O.局部马尔科夫性是指在给定随机变量组Y_W的条件下随机变量Y_v与随机变量组Y_O是独立的,即:

P(Y_v,Y_O | Y_W) = P(Y_v | Y_W)P(Y_O | Y_W)

全局马尔科夫性:设节点及A,B是在无向图G中被节点集合C分开的任意节点集合,节点集合A,B,C所对应的随机变量组分别是Y_A,Y_B,Y_C.全局马尔科夫性是指给定随机变量组Y_C条件下随机变量组Y_AY_B是条件独立的.即:

P(Y_A,Y_B | Y_C) = P(Y_A | Y_C)P(Y_B | Y_C)

以上三种定义是等价的.


参考:
Daphne Koller<概率图模型>

posted @ 2018-10-21 20:53:16
评论加载中...

发表评论