马尔可夫网络

维基百科,自由的百科全书
跳转至: 导航搜索

马尔可夫网络,(马尔可夫随机场无向图模型)是关于一组有马尔可夫性质随机变量X的全联合概率分布模型。

马尔可夫网络类似贝叶斯网络用于表示依赖关系。但是,一方面它可以表示贝叶斯网络无法表示的一些依赖关系,如循环依赖;另一方面,它不能表示贝叶斯网络能够表示的某些关系,如推导关系。马尔可夫网络的原型是易辛模型,最初是用来说明该模型的基本假设[1]

形式化定义[编辑]

形式上,一个马尔可夫网络包括:

  • 一个无向图 G = (V,E),每个顶点 vV 表示一个在集合X随机变量,每条边 {u,v} ∈ E 表示随机变量uv之间的一种依赖关系。
  • 一个函数集合 f_k(也称为因子 或者 团因子 有时也称为特征),每一个 f_k 的定义域是图G的团或子团k. 每一个 f_k是从可能的特定联合的指派(到元素k)到非负实数的映射。

联合分布函数[编辑]

联合分布(吉布斯测度)用马尔可夫网络可以表示为:

 P(X=x) = \frac{1}{Z} \prod_{k} f_k (x_{ \{ k \}})

其中x=x_{\{1\}}x_{\{2\}}x_{\{3\}}\cdots是向量,x_{ \{ k \}} = x_{\{k,1\}}x_{\{k,2\}}\cdots x_{\{k,|c_k|\}}是随机变量x在第k个团的状态(|c_k| 是在第k个团中包含的节点数。),乘积包括了图中的所有团。注意马尔可夫性质在团内的节点存在,在团之间是不存在依赖关系的。这里,Z配分函数,有

 Z = \sum_{x \isin \mathcal{X}} \prod_{k} f_k(x_{ \{ k \} }).

实际上,马尔可夫网联络经常表示为对数线性模型。通过引入特征函数 \phi_k,得到

f_k=\exp \left(w_k^{\top} \phi_k (x_{ \{ k \}}) \right)

 P(X=x) = \frac{1}{Z} \exp \left( \sum_{k} w_k^{\top} \phi_k (x_{ \{ k \}}) \right)

以及划分函数

 Z = \sum_{x \isin \mathcal{X}} \exp \left(\sum_{k} w_k^{\top}\phi_k(x_{ \{ k \} })\right)

其中,w_k是权重,\phi_k是势函数,映射团k到实数。这些函数有时亦称为吉布斯势;术语 源于物理,通常从字面上理解为在临近位置产生的势能

对数线性模型是对势能的一种便捷的解释方式。一个这样的模型可以简约的表示很多分布,特别是在领域很大的时候。另一方面,负的似然函数凸函数也带来便利。但是即便对数线性的马尔可夫网络似然函数是凸函数,计算似然函数的梯度仍旧需要模型推理,而这样的推理通常是难以计算的。

马尔可夫性质[编辑]

马尔可夫网络有这样的马尔可夫性质:图的顶点u在状态x_u的概率只依赖顶点u的最近临节点,并且顶点u对图中的其他任何节点是条件独立的。该性质表示为

P(X_u=x_u|X_v, v\ne u) = P(X_u=x_u|X_v, v\isin N_u)

顶点u的最近临节点集合N_u 也称为顶点u马尔可夫毯

推理[编辑]

在贝叶斯网络中,计算节点 V' = \{ v_1 ,..., v_i \} 集合对给出的另外节点 W' = \{ w_1 ,..., w_j \} 集合的条件分布可以通过的所有可能的 u \notin V',W'指派值求和,这是精确推理。精确推理是NP-hard问题,一般相信不存在快速计算方法。近似推理技术如 Markov chain Monte Carlobelief propagation 通常更加可行。一些马尔可夫随机场的子类,如树,有多项式时间复杂度的推理算法,发现这样的子类也是活跃的研究课题。也有一些马尔可夫随机场的子类允许有效最大后验概率估计,或者最可能的指派值;应用的例子包括关联网络。

条件随机场[编辑]

一个马尔可夫网络的重要变体是条件随机场,每个随机变量可以条件依赖于一组全局的观察o。这个模型中,每个函数\phi_k是从指派值到团k和从观察o 到非负实数的映射。这样的马尔可夫网络更适于不对观察建立分布模型的区分性模型,不是生成性模型。

参见[编辑]

参考[编辑]

  1. ^ Ross Kindermann and J. Laurie Snell, 马尔可夫随机场及其应用 (1980) 美国数学协会, ISBN 0-8218-5001-6