贝叶斯网络 Bayesian Network

贝叶斯网络是概率图模型的一种结构，通过有向无环图来表示模型中的关联性。在特定的图结构中，节点表示随机变量，有向边表示相连的变量之间的因果关系。

贝叶斯网的链式法则

$$ P(X_1, X_2, …, X_n) = \Pi_{i=1:n}P(X_i \mid Parents(X_i)) $$

I-Map和P-Map

令P为X上的分布，$I(P)$是满足$(X⊥ Y\mid Z)$的独立性断言的集合。I(G)表示图G上独立性关系的集合，如果$ I(G) \subseteq I(P) $，则可成G为P的I-Map。
显然只要某个图的独立性关机集合是I(P)的子集，其对应的图就是I-Map，所以I-Map有很多个，只有当I(G)=I(P)时，对应的图可以等价的表示这个概率分布，G就叫做P的P-Map(Perfect-Map)。

独立性

局部马尔科夫独立性

记$ Pa_{x_i} $是图G中$ X_i $的父节点，将图G中不是$X_i$后代的子节点变量记为$ NonDescendants_{X_i} $。G满足如下的条件独立性论断$I_l(G)$：$ X_i ⊥ NonDescendants_{X_i}\mid Pa_{x_i}:\forall i$，也就是说在

给定父节点的情况下，子节点间相互独立。

全局马尔科夫独立性

全局的马尔科夫独立性与d-分离有关，如果在给定Z的情况下，节点X和Y独立，则X和Y是D-separation。

迹是三个变量相连的路径，比如X，Y，Z。迹有三种形式：

Causal Trail $ X \to Z \to Y $: 有效当且仅当Z不可观。

Evidential Trail $X \leftarrow Z \leftarrow Y$: 有效当且仅当Z不可观。

Common Cause $X \leftarrow Z \to Y$：有效当且仅当Z不可观。

Common Effect $ X \to Z \leftarrow Y $：有效当且仅当Z（或者是其他后代）可观。

与d-分离想对应的独立性的集合用I(G)表示：
$$I(G)=\lbrace(X ⊥ Y\mid Z):d-sep_G(X;Y\mid Z)\rbrace $$
上面的集合也叫做全局马尔科夫的独立性。

可靠性与完备性

d-分离的可靠性与贝叶斯网络因子分离定理有关,如果分布P根据G因子分解，那么，$I(G)\subseteq I(P)$。
对于任意的分布P根据G因子分解，如果$ (X ⊥ Y|Z) \in I(P)$，那么就有$dsep_G(X; Y\mid Z)\in I(P)$
G是一个贝叶斯网络结构的图，如果给定Z时X和Y不是在图G中d-分离的，那么X和Y在某些图G上的因子分解分布P中相互依赖。
对于几乎所有的在G上的因子分解的分布P，$I(P)=I(G)$。几乎所有指的是对于参数化条件概率空间中除了测度为0的分布。

马尔科夫网络 Markov Network

上面是有向图模型，又叫做贝叶斯网络，下面我们来看一下无向图模型，也被叫做马尔科夫网。
如下的式子必须使用马尔科夫网：
$$A \perp C\mid \lbrace B, D \rbrace, B \perp D\mid \lbrace A, B\rbrace$$

clique就是指的强连通的团，通常翻译为团，每个团会定义一个势函数(potential function)。
无向图模型可以通过一个给定的无向图来表示概率分布$P(X_1,…X_n)$，每一个在图H中的团$c\in C$代表一组正势函数$\psi_c$，比如：
$$P(X_1, …, X_n)=\frac{1}{Z}\prod_{c\in C}\psi_c(X_c)$$

其中Z是配分函数(partition function)，是一个归一化的常数：
$$Z=\sum_{X_1, …, X_n}\prod_{c\in C}\psi_c(X_c)$$

全局马尔科夫独立性

如果在给定节点集B时，任意两个节点A和C中的节点之间没有路径，那么则称B在图H中分离A和B。
如果对于任意不连接的A，B，C，比如B分离A和C，也就说在给定C的情况下，A和C独立，那么该概率分布满足全局马尔科夫独立性。
$$I(H)=\lbrace A \perp C\mid B:sep_H(A;C\mid B)\rbrace$$

完备性

H是一个马尔科夫网结构，如果在给定Z时，X与Y在图H中不可分离，则在给定Z时，X与Y在因子分解的分布中存在依赖关系。

可靠性

P为X上的正分布，而H为X上的一个马尔科夫网结构。如果P是在图H上的吉布斯分布，那么H是P的I-Map。
P为X上的分布，而H为X上的一个马尔科夫网结构。如果H是P的一个I-Map，则P是可以再H上分解的一个吉布斯分布。

局部马尔科夫独立性

H=(V,E)是一个马尔科夫网，与H相关的成对独立性定义如下：
$$I_P(H)=\lbrace (X \perp Y \mid V-\lbrace X, Y\rbrace):X-Y\notin H\rbrace$$
对于给定的图H=(V,E),X在H中的马尔科夫毯$$MB_H(X)$$定义为X在H中的近邻。与H相关的局部独立性定义如下：
$$I_l(H)=\lbrace(X \perp V-\lbrace X\rbrace -MB_{H}(X)\mid MB_{H}(X)):X\in V\rbrace$$

局部马尔科夫性与全局马尔科夫性的联系

$$P\models I_l(H)\Rightarrow P\models I_P(H)$$ $$P=I(H)\Rightarrow P\models I_l(H)$$ $$P>0\ and\ P\models I_p(H) \Rightarrow P\models I(H)$$
推论：对于一个正分布P，全局、局部和成对独立性是等价的。

团(cliques)

团是一个完全子图(complete graph)，最大团是最大可能的完全子图。最大的团记作max-clique，不是最大的团记作sub-cliques。

对数线性模型

$$P(X_1,…,X_n)=\frac{1}{Z} exp[-\sum_{i=1}^k \omega_c(X_c)]$$

Perfect Maps

只要分布的分离特性与独立特性一致，马尔科夫网就可以是分布的一个P-Map。然而，就像是贝叶斯网，不是所有的分布都能用无向图来表示。实际上，无向图和有向图不恩能够完全的表达分布的空间。

模型实例

波尔兹曼机

波尔兹曼机的连接方式如下图所示：

波尔兹曼机是一个全连接的图，每条无向边表示一对依赖关系，节点是二值变量。
上图的联合概率分布如下：
$$
P(x_1, x_2, x_3, x_4)=\frac{1}{Z}exp\lbrace \sum_{i,j}\phi_{ij}(x_i, x_j)\rbrace
=\frac{1}{Z}exp\lbrace\sum_{i,j}\theta_{ij}x_ix_j+\sum_i\alpha_i x_i + C \rbrace
=\frac{1}{Z}exp\lbrace(x-\mu)^T\Theta(x-\mu)\rbrace
$$

受限波尔兹曼机

受限波尔兹曼机通常有很多层构成，每个层中有两个子层，一个隐藏层，另一个是可见层。RBM的概率分布函数：
$$P(x,h\mid \theta)=exp\lbrace\sum_i\theta_i\phi_i(x_i)+\sum_j\theta_j\phi_j(h_j)+\sum_{i,j}\theta_{i,j}\phi_{i,j}(x_i,h_j)-A(\theta)\rbrace$$
RBM的因子是边际相关的，在给定可观的节点的情况下因子是条件独立的。可以进行迭代吉布斯采样。

条件随机场

条件随机场是一种判别式的无向图模型，通过观测序列得到标记序列。CRF并没有假定各个特征值之间的独立性，概率分布如下：
$$P_\theta(y\mid x)=\frac{1}{Z}exp\lbrace \sum_{e\in E,k}\lambda_k f_k(e,y\mid_e,s)+\sum_{v\in V,k}\mu_k g_k(v,y\mid_v,x)\rbrace$$
其中，x是观测序列(数据序列)，y是标记序列，v是标记随机变量集V的顶点，e是来自边集E的边。k是特证序号，$f_k$是固定的二值特征函数，$g_k$是给定的二值顶点特征。$\theta=(\lambda_1, …, \lambda_n;\mu_1, …, \mu_n)$是需要估计的参数$y\mid_e$是由e定义的y的集合，$y\mid_v$是由v定义的y的集合。

总结

无向图模型表明了变量间的相互关系（relatedness），而不是因果关系（causality）。
无向图可以定义联合或者独立分布。

参考文献

http://www.cs.cmu.edu/~epxing/Class/10708-14/lecture.html
Koller D, Friedman N. Probabilistic graphical models: principles and techniques[M]. MIT press, 2009.
周志华. 机器学习[M]. 清华大学出版社, 2016.