概率图模型之基本概念1

徐静

今后的主页将更新概率图模型及生成学习的内容，我们系统的介绍一下概率图模型的相关知识，为后期的生成学习和生成对抗学习做铺垫。我们默认读者具有了一定的高等数学，高等概率论及高等数理统计的理论基础及信息论的相关基本概念。

1.概率图模型的基本概念

图是一种数据结构，由顶点集$V$和边集$E$构成，记作$G=(V,E)$。 每个随机变量对应一个顶点（或称节点），也就是说，随机变量和顶点时一对一的关系。

无向图：如果一个图$G=(V,E)$

有向图：如果G的所有边是有向的

混合图：如果G既包含有向边，又包含有向边

父节点，子节点，邻节点： 当$X_i \to X_j \in E$称$X_i$在图G中是$X_j$的邻节点。如果对有向图的顶点集进行排序$X_1,X_2,...X_n$,只要$X_i \to X_j \in E$,就有$i < j$,那么称这种排序为一个拓扑序。对图$G$的任意顶点$X \in V$，用$Pa_G(X)$表示$X$的所有父节点，用$Ch_G(X)$表示$X$的所有子节点，用$Nb_G(X)$表示$X$的所有临节点，$X$的边界集定义为：

导出字图,完全字图，团，极大团(最大团): 如果一个图的顶点集$V^{'} \subseteq V$,且该图的边集由$G$中所有与$V$的两个节点相连的边组成，那么称其为$G$的导出字图，记作$G[V^{'}]$。如果$G[V^{'}]$的任意两个节点均由一条边链接，那么称其为完全字图，且此时$V^{'}$称为团。如果对于任意超级$V^{''} \supset V^{'}$,$V^{''}$都不是团，那么$V^{'}$称为极大团（或最大团)

迹，环，弦，路径，圈，有向路径，有向圈，无向圈: 设${X_1,X_2,...,X_n} \subseteq V$。如果$\forall i \in {1,...,n-1}$，$X_i \leftrightarrow X_{i-1}$,则称$X_1,...,X_n$是一条从$X_1$到$X_n$的迹，当$X_n=X_1$时，这条迹又称为环。连接一个环中两个不相邻顶点的边，称为弦。如果$\forall i \in {1,...,n-1}$，$X_i \to X_{i+1} \in E$或$X_i-X_{i+1} \in E$则称其为一条从$X_1$到$X_n$的路径，当$X_n=X_1$时，这条路径又称为圈，如果在这条路径上至少存在一条有向边，则其称为有向路径，当$X_n=X_1$时，又称为有向圈。如果一个圈不存在有向边，则称为无向圈。

后代,祖先: 如果在有向图中，$x_i,X_j \in V (i \ne j)$且存在一条从$X_i$到$X_j$的有向路径，则称$X_i$是$X_j$的祖先($Anc_G(X)$表示$X$的所有祖先，$X_j$是$X_i$的后代($Desc_G(X)$表示$X$的所有后代)，用$NonDesc_G(X)=V-Desc_G(X)$表示$X$的所有非后代集合。

单连通的，叶节点，多重树，森林，树： 如果一个图不包含任何环，那么称这个图为单连通的，在单连通图中，如果一个节点只有一个相邻节点，则称为叶节点。一个单连通的有向图也叫做一棵多重树，一个单连通的无向图则称为一个森林。如果一个森林是连通的，则称为树，如果一个有向图的每个节点至少只有一个父节点，那么这个有向图也称为森林，并且在连通时也称为树。

无圈图，有向无圈图，部分有向无圈图，链图：如果一个图不包含圈，则称为无圈图，一个无圈图是有向的，则称为有向无圈图。一个包含有向边和无向边的无圈图称为部分有向无圈图，部分有向无圈图又称为链图。

弦图: 如果一个无向图中任意长度大于等于4的环都包含一条弦，那么这个无向图称为弦图，弦图通常称为也称为三角剖分图

概率图模型的基本思想是把随机变量之间的条件依赖和独立性质映射到图结构上来描述概率分布。概率图模型主要分为概率有向图模型，概率无向无圈图模型和部分有向无圈图模型。

预告：

2.概率有向图模型

3.概率无向图模型

4.部分有向无圈图模型

5.条件随机场

6.马尔科夫链

7.概率图模型的学习

8.概率图模型的推理

9.MCMC