概率图模型的综合叙述：

特征函数便是图中的conditional。对图简单的说明，综合概述Naive Bayes，Logistic Regression，HMM，Linear-chain CRF之间的关系。Naive Bayes经过条件参数的加入即为Logistic Regression，同时这两者经过序列化即特征函数加入了对相邻状态之间的判断即变为HMM和Linear-chain CRF，最后经过广义图模型的扩展变为最后两者。

马尔科夫随机场综述：

马尔可夫网络（Markov network），PGM（概率图模型）中的无向图模型，也即马尔可夫随机场（ Markov random Field，MRF），是一个可以由无向图表示的联合概率分布，属于生成式模型。与“马尔可夫”有关的随机过程或概率模型般都是基于马尔可夫假设的，也即下一个时间点的状态只与当前的状态有关系，换言之，决定你未来状态的不是你的过去而是你现在的状态。

马尔科夫随机场定义：

马尔可夫网络可用于表示变量之间的依赖关系，与贝叶斯网络不同的是，它可以表示贝叶斯网络无法表示的一些依赖关系，比如循环依赖：另一方面，它不能表示贝叶斯网络能够表示的某些关系，比如推导关系。

首先学习一下随机场的概念，其定义为：当给每一个位置中按照某种分布随机赋予相空间的一个值之后，其全体就叫做随机场。其中两个重要的概念是“位置”和“相空间”。“位置”好比是一亩亩农田“相空间”好比是种的各种庄稼。我们可以给不同的地种上不同的庄稼，这就好比给随机场的每个“位置”，赋予相空间里不同的值。所以，俗气点说，随机场就是在哪块地里种什么庄稼的事情。马尔可夫随机场是具有马尔可夫特性的随机场。拿种地打比方，如果任何一块地里种的庄稼的种类仅仅与它邻近的地里种的庄稼的种类有关，与其它地方的庄稼的种类无关，那么这些地里种的庄稼的集合，就是一个马尔可夫随机场。

图是由结点及连接结点的边组成的集合，结点和边的集合分别记作$V$和$E$，图记作$G=(V，E)$。无向图是指边没有方向的图。PGM就是用图表示概率分布，其中一个结点表示一个随机变量，如果两个随机之间有依赖关系就用一条边将它们连接起来。

假设有联合概率分布$P(Y)$， Y = { y 1 ， y 2 ， … ， y n } Y=\{y_1，y_2，\ldots，y_n\} Y={y1​，y2​，…，yn​}是一组随机变量。由无向图 $G=(V，E)$ 表示概率分布$P(Y)$，即在图$G$中，结点$v\in V$表示一个随机变量$Y$，边$e\in E$表示随机变量之间的概率依赖关系。

首先，定义三个重要的概念

1、成对马尔可夫性：假设$u$和$v$分别是无向图$G$中任意两个没有边连接的结点，结点u和v对应的随机变量分别是$Y_u$和$Y_y$，其他所有结点集合为$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)$

2、局部马尔可夫性：假设$v_{any}\in V$是无向图$G$中任意一个结点，$W$是与$v_{any}$有边连接的所有结点的集合，$O$是除$v_{any}$和$W$以外的所有结点的集合，据此定义，局部马尔可夫性是指在给定$Y_W$的条件下$Y_{vany}$和$Y_O$是条件独立的，即
在 W 情 况 下 现 在 Y v a n y , Y O 的 可 能 P ( ( Y v a n y , Y O ) ∣ Y W ) = P ( Y v a n y ∣ Y W ) P ( Y O ∣ Y W ) 用 在 W , Y O 情 况 下 现 在 Y v a n y 的 可 能 表 示 = = = 在 W 情 况 下 现 在 Y v a n y , Y O 的 可 能 ∵ P ( ( Y v a n y , Y O ) ∣ Y W ) = P ( Y v a n y ∣ ( Y O , Y w ) ) P ( Y O ∣ Y w ) w h e n P ( Y O ∣ Y w ) > 0 ∴ P ( Y v a n y ∣ ( Y O , Y W ) ) = P ( Y v a n y ∣ Y W )

$$\begin{array}{c} 在W情况下现在Y_{v_{any}},Y_O的可能 \\{P\left((Y_{v_ {any}}, Y_{O}) | Y_{W}\right)=P\left(Y_{v_{any}} | Y_{W}\right) P\left(Y_{O} | Y_{W}\right)} \\用在W,Y_O情况下现在Y_{v_{any}}的可能表示===在W情况下现在Y_{v_{any}},Y_O的可能 \\ \because P\left((Y_{v_{any}}, Y_{O})| Y_{W}\right)=P\left(Y_{v_{any}} |( Y_{O}, Y_{w})\right) P\left(Y_{O} | Y_{w}\right) \\ when \quad P\left(Y_{O} | Y_{w}\right)>0 \\ \therefore { P\left(Y_{v_{any}} | (Y_{O}, Y_{W})\right)=P\left(Y_{v_{any}} | Y_{W}\right)} \end{array}$$ 在W情况下现在Yvany​​,YO​的可能P((Yvany​​,YO​)∣YW​)=P(Yvany​​∣YW​)P(YO​∣YW​)用在W,YO​情况下现在Yvany​​的可能表示===在W情况下现在Yvany​​,YO​的可能∵P((Yvany​​,YO​)∣YW​)=P(Yvany​​∣(YO​,Yw​))P(YO​∣Yw​)whenP(YO​∣Yw​)>0∴P(Yvany​​∣(YO​,YW​))=P(Yvany​​∣YW​)​

局部马尔科夫示意图：

3、全局马尔可夫性：假设结点集合$A$和$B$是无向图$G$中被结点集合$C$分开的任意结点集合，如下图所示，据此定义，全局马尔可夫性是指在给定$Y_C$的条件下$Y_A$和$Y_B$是条件独立的，即：

$P\left((Y_A，Y_B)|Y_C\right)=P\left(Y_A|Y_C\right)P\left(Y_B|Y_C\right)$

上述成对的、局部的、全局的马尔可夫性定义是等价的。有了上面的基础，我们就可以定义概率无向图模型：设有联合概率分布$P(Y)$，由无向图$G=(V，E)$表示，在图$G$中，结点表示随机变量，边表示随机变量之间的依赖关系;如果联合概率分布$P(Y)$满足成对的、局部的或全局的马尔可夫性，就称此联合概率分布为概率无向图模型，或马尔可夫随机场。

MRF的因式分解：

首先学习团、极大团和最大团的概念：无向图$G$中任何两个结点均有边连接的结点子集称为团;若$C$是无向图$G$的一个团，并且不能再加进任何一个$G$的结点使其成为一个更大的团，则称此$C$为极大团：在所有极大团中，结点最多的称为最大团。三个概念之间是层层递进关系，构成一个团的条件是集合中所有结点必须两两之间有边连接，因此$N$个点的团有$\frac{N(N-1)}{2}$条边，就好比一个团队中所有人必须互相认识：极大团首先是团，然后其所有结点不能被更大的团所包含;最大团首先是极大团，然后所含结点数量最多。举个例子，下图表示一个由4个结点组成的无向图，图中由两个结点组成的团有5个： { Y 1 ， Y 2 } ， { Y 1 ， Y 3 } ， { Y 2 ， Y 3 } ， { Y 3 ， Y 4 } ， { Y 2 ， Y 4 } \{Y_1，Y_2\}，\{Y_1，Y_3\}，\{Y_2，Y_3\}，\{Y_3，Y_4\}，\{Y_2，Y_4\} {Y1​，Y2​}，{Y1​，Y3​}，{Y2​，Y3​}，{Y3​，Y4​}，{Y2​，Y4​} 。有2个极大团： { Y 1 ， Y 2 ， Y 3 } \{Y_1，Y_2，Y_3\} {Y1​，Y2​，Y3​}和 { Y 2 ， Y 3 ， Y 4 } \{Y_2，Y_3，Y_4\} {Y2​，Y3​，Y4​}。特别地，所有极大团恰好全部是最大团。由于$Y_1$和$Y_4$没有边连接，因此 { Y 1 ， Y 2 ， Y 3 ， Y 4 } \{Y_1，Y_2，Y_3，Y_4\} {Y1​，Y2​，Y3​，Y4​}不是一个团。

在MRF中，多个变量之间的联合概率分布能基于团分解为多个因子的乘积，每个因子仅与一个团相关，称为MRF的因式分解。对于$n$个变量， y = { y 1 ， y 2 ， … ， y n } y=\{y_1，y_2，\ldots，y_n\} y={y1​，y2​，…，yn​}，假设无向图$G$中所有团构成集合$C$，与团$Q\in C $对应的变量集合为$Y_Q$，则MRF的联合概率分布$P(Y)$定义为：

$P(Y)=P\left(y_1，\dots ，y_n\right)=\frac{1}{Z}{\prod }_{g\in C}{\psi }_Q\left(Y_{\theta }\right)$

其中${\psi }_Q$为与团$Q$对应的势函数，用于对团Q中的变量关系进行建模，$Z$为规范化因子，以确保$P(Y)$构成一个概率分布，其表达式为

$Z={\sum }_Y{\prod }_{Q\in C}{\psi }_Q\left(Y_Q\right)={\sum }_{y_1，\dots ，y_n}{\prod }_{\theta \in C}{\psi }_{\theta }\left(Y_{\theta }\right)$

就是把所有可能的$n$个随机变量的取值分别带入求归一化。

显然，若变量个数较多，则团的数目将会很多，这将会给计算带来很大的负担。我们注意到，如果团$Q$不是即极大团，则它必然会被一个极大团$Q^{\ast }$所包含，即$Y_Q\in Y_{Q^{\ast }}$，这意味着变量$Y_Q$之间的关系不仅体现在势函数${\psi }_Q$中，还体现在${\psi }_{Q^{\ast }}$中。因此，我们可以简单一点直接基于极大团来定义联合概率分布$P(Y)$。假设所有极大团构成的集合为$C^{\ast }$，则有：

$P(Y)=P\left(y_1，\dots ，y_n\right)=\frac{1}{Z^{\ast }}{\prod }_{\theta \in C^{\ast }}{\psi }_Q\left(Y_Q\right)$

其中，$z^{\ast }$的表达式为：

$Z^{\ast }={\sum }_Y{\prod }_{Q\in {\mathcal{C}}^{\ast }}{\psi }_Q\left(Y_Q\right)={\sum }_{y_1，\dots ，y_n}{\prod }_{Q\in {\mathcal{C}}^{\ast }}{\psi }_Q\left(Y_Q\right)$

接下来说一下势函数${\psi }_Q$，为了保证${\psi }_Q$的非负性，通常定义为指数函数：

ψ Q ( Y Q ) = exp ⁡ { − E ( Y Q ) } \psi_{Q}\left(Y_{Q}\right)=\exp \left\{-E\left(Y_{Q}\right)\right\} ψQ​(YQ​)=exp{−E(YQ​)}

其中，$E\left(Y_{\theta }\right)$称为$Y_Q$的能量函数，是一个定义在变量$Y_Q$上的实质函数，常见的形式为：

$E\left(Y_Q\right)={\sum }_{u，v\in Q，v̸=V}{\alpha }_{uv}{y}_u{y}_v+{\sum }_{v\in Q}{\beta }_v{y}_v$

其中，${\alpha }_{UV}$和${\alpha }_V$均为参数，第一项考虑每一对节点的关系，第二项考虑每一个单独节点的关系。

一个简单的例子：

如图所示简单马尔科夫随机场：

图中极大团： { x 2 ， x 5 ， x 6 } ， { x 1 ， x 2 } ， { x 2 ， x 4 } ， { x 1 ， x 3 } ， { x 3 ， x 5 } \left\{\mathrm{x}_{2}， \mathrm{x}_{5}， \mathrm{x}_{6}\right\}，\left\{\mathrm{x}_{1}， \mathrm{x}_{2}\right\}，\left\{\mathrm{x}_{2}， \mathrm{x}_{4}\right\}，\left\{\mathrm{x}_{1}， \mathrm{x}_{3}\right\}，\left\{\mathrm{x}_{3}， \mathrm{x}_{5}\right\} {x2​，x5​，x6​}，{x1​，x2​}，{x2​，x4​}，{x1​，x3​}，{x3​，x5​}

联合概率分布表达式：
$$\begin{gathered} P(X)=P\left(x_1,x_2,x_3,x_4,x_5,x_6\right) \\ =\frac{1}{Z}{\psi }_{256}\left(X_2,X_5,X_6\right){\psi }_{12}\left(X_1,X_2\right){\psi }_{24}\left(X_2,X_4\right){\psi }_{13}\left(X_1,X_3\right){\psi }_{35}\left(X_3,X_5\right) \end{gathered}$$