Created by potrace 1.13, written by Peter Selinger 2001-2015

马尔科夫网

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

在介绍马尔科夫网之前,我们先来回顾一下贝叶斯网,对于下面的贝叶斯网:

image

可以这样计算他们的联合概率:

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

马尔科夫网

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

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

image

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

在无向图中,两个相连的事件没有因果关系,所以我们不能使用条件概率来参数化这个模型,直观上,无向边表达的是相关变量之间的亲密关系,我们可以使用一个函数来描述这种亲密关系,这个描述亲密关系的函数 \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_2 和 x_3 之间缺乏连接, \left\{ x _ { 1 } , x _ { 2 } , x _ { 3 } \right\} 并不构成团.显然,每个结点至少出现在一个极大团中.

image

最少参数的马尔科夫网

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

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_u 和 Y_v .其他所有节点为O,对应的随机变量组是 Y_O .成对马尔科夫性是指给定随机变量组 Y_O 的条件下随机变量 Y_u 和 Y_v 是条件独立的,即:

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

image

局部马尔科夫性:设 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)

image

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

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

image

以上三种定义是等价的.

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

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