马尔可夫网络

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

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

形式化定义

形式上，一个马尔可夫网络包括：

• 一个无向图G = (V,E)，每个顶点v ∈V表示一个在集合$X$的随机变量，每条边{u,v} ∈ E表示随机变量u和v之间的一种依赖关系。
• 一个函数集合$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\in {\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\in {\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\neq u)=P(X_{u}=x_{u}|X_{v},v\in N_{u})$

顶点u的最近临节点集合$N_{u}$也称为顶点u的马尔可夫链。

推理

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

条件随机场

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

参见

• 圖模式
• 马尔可夫链
• 马尔可夫逻辑网络