第1章
概率图模型基础知识
1.1概述
1.1概述
概率图模型是图模型理论和概率论相结合的产物，它为利用数学和工程的方法来解决不确定性和复杂系统问题提供了自然的工具。作为建模和推理工具，概率图模型理论使用直观、有效、灵活的图结构来表达多个随机变量的概率分布。在图结构中，结点代表了随机变量，结点间的连接（边）代表了随机变量之间的统计关系。图结构刻画了随机变量间的条件依赖和独立关系，从系统的角度揭示变量间的不确定性，并为不确定性的传递提供手段。基于概率图模型，联合概率分布可以分解成多个随机变量子集的函数，这个因式分解极大地简化了多变量联合概率分布模型。基于概率论，概率图模型算法利用图结构有效的计算边缘概率或其他条件概率。
在讨论概率图模型的基本原理和学习方法之前，本章就图论、概率论和信息论的相关概念予以介绍。
1.2图论的相关基本概念
1.2图论的相关基本概念
为了理解概率图模型，需要先了解一些图论的基本知识。
1. 无向图
一个无向图U是一个二元组<N,E>，即U=<N,E>，其中：
N是一个非空集合的顶点集，N中的元素称为顶点或结点。
E是无序积N×N的多重子集(元素可多次出现)，称E为U的边集，E中的元素称为无向边或简称边。
在一个图U=<N,E>中，为了表示N和E分别为U的顶点集和边集。常将N记成N(U)，而将E记成E(U)。
2. 有向图
一个有向图D是一个二元组<N,E>，即D=<N,E>，其中：
N是同无向图一样的顶点集。
E是卡氏积的多重子集，其元素称为有向边，也简称边或弧； 有时用N(D)、E(D)分别表示图D的顶点集和边集。
在实际应用中，不论是无向图还是有向图，一般只画出它的图形，而不写出N和E的集合表达式。下面分别列出无向图和有向图的图形表示和对应的集合表示。
无向图U=<N,E>如图1.1所示，有
N={n1,n2,n3,n4,n5}
E={(n1,n2),(n2,n2),(n2,n3),(n1,n3),(n1,n4)}
有向图U=<N,E>如图1.2所示，有
N={n1,n2,n3,n4,n5}
E={<n1,n1>,<n2,n3>,<n3,n2>,<n3,n4>,
<n2,n4>,<n4,n5>,<n5,n4>,<n1,n2>}
图1.1无向图
图1.2有向图
3. 混合图
如果在图中一些边是有向边，另一些边是无向边，则称这个图是混合图。
4. 邻接集(Adracency Set)
在一个图中，若两个结点由一条有向边或一条无向边关联，则称这两个结点互为邻接点。给定一个无向图U=<N,E>和图的一个结点ni∈N，则ni的邻接集就是在图中直接和ni相连的结点集合，即Adr(ni)={nj|(ni,nj)∈E}。根据邻接点的概念，在有向图中也存在邻接集。根据有向边描述的方向性，在有向图中ni的邻接集又可以分为两部分。邻接集的概念给出了图中结点间的邻域关系，用Ω(ni)来表示结点ni的邻域集合。
例如，在图1.1中，各个结点的邻接集为
Adr(n1)={n2,n3,n4};
Adr(n2)={n1,n2,n3};
Adr(n3)={n1,n2};
Adr(n4)={n1};
Adr(n5)=;
5. 有限图、m阶图和平凡图
设G=<N,E>为一个有向图或无向图，可定义以下概念：
(1) 有限图。若N、E都是有穷集合，则称G是有限图(在概率图模型中，只涉及有限图)。
（2） m阶图。若|N|=m(|N|表示集合N的元素个数)，则称G为m阶图。
（3） 平凡图。若E=，则称G为零图。特别是，若此时又有|N|=1，则称G为平凡图。
6. 平行边
在图中，连接同一对结点间的多条边称为平行边。含有平行边的任何一个图被称为多重图。
7. 简单图
不含有平行边和自环的图称为简单图（本书讨论的都是简单图）。
8. 无向完全图
设G=<N,E>是n阶无向简单图，若G中任何顶点都与其余的n－1个顶点相邻，则称G为n阶无向完全图。
9. 有向完全图
有向完全图G=<N,E>设为n阶有向简单图，若对于任意的顶点u,v∈N,u≠v，既有有向边<u,v>又有<v,u>，则称D是n阶有向完全图。
10. 子图和完全子图
设G=<N,E>，G′=<N′,E′>是两个图，若N′N且E′E，则称G′是G的子图，G是G′的母图。记做G′G。如果G′是完全图，则称G′是G的完全子图。
11. 极大完全子图与簇(Clique)或团
给定一个无向图G，如果一个完全子图不是其他任何一个完全子图的真子图，则称为极大完全子图。极大完全子图的结点构成的集合又称为簇或团。
容易知道，完全图的任意子图都可能是完全图，只要所有连接子图结点的边都在子图内。一个图可能有很多子图。这其中应该会有一些“极大的”完全子图。
12. 通路和回路
给定图G=<N,E>，设G中的顶点和边的交替序列为Γ=n0e1n1e2…nLeL,若Γ满足以下条件： ni-1和ni是ei的端点(在G是有向图时，要求ni-1是ei的始点，ni是ei的终点)(i=1,2,…,L)，则称Γ为顶点n0至nL的通路。n0和nL分别称为此通路的起点和终点，Γ中边的数目L称为Γ的长度。当n0=nL时，此通路称为回路。
13. 无环图和有环图
如果图中没有回路，则称为无环图(Unloopy Graph)。对应有回路的图称为有环图(Loopy Graph)。
给定的概率图模型是否有环路，对信念传播算法非常重要。如果是无环图，信念传播算法可以得到准确的计算，其收敛性可以证明。如果是有环图，信念传播算法则大多采用一种近似算法。
14. 连通性和可达性
在一个无向图U中，若从顶点ni到nj存在通路(当然从nj 到ni也存在通路)，则称点ni与nj是连通的。规定点nj到自身总是连通的。在一个有向图D中，若从顶点ni到nj存在通路，则称点ni到nj可达。规定点ni到自身总是可达的。
15. 连通图和非连通图
若无向图U是平凡图，或U中任意两个顶点都是连通的，则称U是连通图； 否则，称U是非连通图。
16. 连通分支
无向图中，顶点间的连通关系是等价关系。设U为一个无向图，R是U中顶点之间的连通关系，按照R可将N(U)划分成k(k≥1)个等价类，记为N1,N2,…,Nk。由它们导出的子图称为U的连通分支，其个数记为P(U)。
17. 点割集与割点
设无向图U=<N,E>，若存在顶点子集N′N，使U删除N′ (将N′中的顶点及关联的边都删除)后，所得U-N′的连通分支数与U的连通分支数满足p(U-N′)>p(U)，而删除N′后的任何真子集N″后，由p(U-N″)=p(U)则称N′为U的点割集。若点割集中只有一个顶点n，则称n为割点。
18. 相关性分割(D-Separation)
设A、B、C为有向图D中两两不相交的结点集，且A、B间的任意路径都被C阻塞，则称A、B被C相关性分割，而C称为A、B的切割集。
19. 父结点与子结点
在有向图中，连接同一条弧(边)的两个端点，根据弧的方向分为弧尾和弧头。有时也称弧尾结点是弧头结点的父结点，弧头结点是弧尾结点的子结点。
1.3概率论的相关基本概念
1.3概率论的相关基本概念
本节主要介绍概率论中与概率图模型密切相关的一些基本概念。
1.3.1随机变量与概率函数
1. 随机变量
如果对于试验的样本空间Ω={ω}中的每一个样本点ω，变量X都有一个确定的实数值与之对应，则变量X是样本点ω的实函数，记做X=X(ω)，称这样的变量X为随机变量。常用大写字母X、Y、Z等表示随机变量，用小写字母x、y、z等表示其取值。
随机变量的取值情况又可把其分为两类，即离散随机变量和连续随机变量。
2. 概率函数
设X为一随机变量，x是它的一个取值。在样本空间中，所有使X取值为x的原子事件组成一个事件，记做ΩX=x={ω∈Ω|X(ω)=x}，也记做“X=x”。事件“X=x”的概率P(X=x)依赖于X的取值x，让x在随机变量X的状态空间ΩX上变动，P(X=x)就成为ΩX的一个取值于［0，1］的函数，称之为随机变量X的概率质量函数，记做P(X)。
离散随机变量有概率质量函数与之对应，连续随机变量有概率密度函数与之对应。
1.3.2古典概率与主观概率
在古典概率中，如果基本事件的总数为n，事件X所包含的基本事件个数为r(r≤n），则定义事件X的概率P(X)为r/n，即
P(X)=rn=X中包含的基本事件个数基本事件总数(1.1)
主观概率又称为似然率，是人们对某一事件X发生信任程度大小的主观评价，即
P(X)=［对X发生的信用度］(1.2)
1.3.3联合概率分布
设(X,Y)是二维随机变量，对于任意实数x,y，事件{X≤x},{Y≤y}同时发生的概率为
F(x,y)=P{X=x,Y=y}(1.3)
称其为二维随机变量(X,Y)的分布函数，或称其为随机变量X和Y的联合分布函数。
1. 离散型随机变量的联合概率分布
如果二维随机变量(X,Y)只取有限个或可列个数对(xi,yj)，则称(X,Y)为二维离散型随机变量，称
P{X=xi,Y=yj}=piji=1,2,…; j=1,2,…(1.4)
为(X,Y)的概率分布，或X与Y的联合概率分布。
2. 连续型随机变量的联合概率分布
如果存在二元非负函数f(x,y)，使得二维随机变量(X,Y)的联合分布函数F(x,y)可表示为
F(x,y)=∫x-∞∫y-∞f(x,y)dxdy(1.5)
则称(X,Y)为二维连续型随机变量,称f(x,y)为(X,Y)的概率密度，或X与Y的联合概率密度。
1.3.4边缘概率分布
设二维随机变量(X,Y)具有分布函数F(x,y)。X和Y都是一维随机变量，也各有对应的分布函数FX(x)和FY(y)，依次称为二维随机变量(X,Y)关于X和关于Y的边缘分布函数。
易知
FX(x)=P{X≤x}=P{X≤x,Y<+∞}=limy→+∞F(x,y)=F(x,+∞)(1.6)
FY(x)=P{Y≤y}=P{X<+∞，Y≤y}=limx→+∞F(x,y)=F(+∞,y)(1.7)
1. 二维离散型随机变量的边缘分布
设二维离散型随机变量(X,Y)的联合分布为
P{X=xi,Y=yj}=piji=1,2,…; j=1,2,…
则称
pi=P{X=xi}=∑∞j=1piji=1,2,…(1.8)
为(X,Y)关于X的边缘分布。
称
pj=P{Y=yj}=∑∞i=1pijj=1,2,…(1.9)
为(X,Y)关于Y的边缘分布。
2. 二维连续型随机变量的边缘概率密度
……
