在图的基础上表示概率分布的模型我们称之为概率图模型;而且在图中,我们用结点来表示随机变量,结点之间的边表示结点的概率依赖关系。本文我们介绍概率图模型中一个最基础的模型 —- 贝叶斯网络。
贝叶斯网络(Bayesian network),又称信念网络(Belief Network),或有向无环图模型(directed acyclic graphical model),是一种概率图模型,于1985年由Judea Pearl首先提出。它是一种模拟人类推理过程中因果关系的不确定性处理模型,其网络拓朴结构是一个有向无环图(DAG)。我们将有因果关系(或非条件独立)的变量或命题用箭头来连接(换言之,连接两个节点的箭头代表此两个随机变量是具有因果关系,或非条件独立)。若两个节点间以一个单箭头连接在一起,表示其中一个节点是“因(parents)”,另一个是“果(children)”,两节点就会产生一个条件概率值。 例如,假设节点E直接影响到节点H,即E→H,则用从E指向H的箭头建立结点E到结点H的有向弧(E,H),权值(即连接强度)用条件概率P(H|E)来表示,如下图所示:
把某个研究系统中涉及的随机变量,根据是否条件独立绘制在一个有向图中,就形成了贝叶斯网络。
贝叶斯网络的定义
令G = (I,E)表示一个有向无环图(DAG),其中I代表图形中所有的节点的集合,而E代表有向连接线段的集合,且令X = (Xi)i ∈ I为其有向无环图中的某一节点i所代表的随机变量,若节点X的联合概率可以表示成:
则称X为相对于一有向无环图G 的贝叶斯网络,其中,
表示节点i之“因”,或称pa(i)是i的parents(父母)。
此外,对于任意的随机变量,其联合概率可由各自的局部条件概率分布相乘而得出:
如下图所示,便是一个简单的贝叶斯网络:
因为a导致b,a和b导致c,所以有
2.2 贝叶斯网络的实例
给定如下图所示的贝叶斯网络:
其中,各个单词、表达式表示的含义如下:
- smoking表示吸烟,其概率用P(S)表示,lung Cancer表示的肺癌,一个人在吸烟的情况下得肺癌的概率用P(C|S)表示,X-ray表示需要照医学上的X光,肺癌可能会导致需要照X光,吸烟也有可能会导致需要照X光(所以smoking也是X-ray的一个因),所以,因吸烟且得肺癌而需要照X光的概率用P(X|C,S)表示。
- Bronchitis表示支气管炎,一个人在吸烟的情况下得支气管炎的概率用P(B|S),dyspnoea表示呼吸困难,支气管炎可能会导致呼吸困难,肺癌也有可能会导致呼吸困难(所以lung Cancer也是dyspnoea的一个因),因吸烟且得了支气管炎导致呼吸困难的概率用P(D|C,B)表示。
lung Cancer简记为C,Bronchitis简记为B,dyspnoea简记为D,且C = 0表示lung Cancer不发生的概率,C = 1表示lung Cancer发生的概率,B等于0(B不发生)或1(B发生)也类似于C,同样的,D=1表示D发生的概率,D=0表示D不发生的概率,便可得到dyspnoea的一张概率表,如上图的最右下角所示。
2.3 贝叶斯网络的3种结构形式
给定如下图所示的一个贝叶斯网络,
从图上可以比较直观的看出:
- 1. x1,x2,…x7的联合分布为
- 2. x1和x2独立(对应head-to-head);
- 3. x6和x7在x4给定的条件下独立(对应tail-to-tail)。
根据上图,第1点可能很容易理解,但第2、3点中所述的条件独立是啥意思呢?其实第2、3点是贝叶斯网络中3种结构形式中的其中二种。为了说清楚这个问题,需要引入D-Separation(D-分离)这个概念。
D-Separation是一种用来判断变量是否条件独立的图形化方法。换言之,对于一个DAG(有向无环图)E,D-Separation方法可以快速的判断出两个节点之间是否是条件独立的。
2.3.1 形式1:head-to-head
贝叶斯网络的第一种结构形式如下图所示
所以有:P(a,b,c) = P(a)*P(b)*P(c|a,b)成立,化简后可得:
即在c未知的条件下,a、b被阻断(blocked),是独立的,称之为head-to-head条件独立,对应本节中最开始那张图中的“x1、x2独立”。
2.3.2 形式2:tail-to-tail
贝叶斯网络的第二种结构形式如下图所示
有P(a,b,c)=P(c)*P(a|c)*P(b|c),则:P(a,b|c)=P(a,b,c)/P(c),然后将P(a,b,c)=P(c)*P(a|c)*P(b|c)带入上式,得到:P(a,b|c)=P(a|c)*P(b|c)。
即在c给定的条件下,a,b被阻断(blocked),是独立的,称之为tail-to-tail条件独立,对应本节中最开始那张图中的“x6和x7在x4给定的条件下独立”。
2.3.3 形式3:head-to-tail
贝叶斯网络的第三种结构形式如下图所示:
有:P(a,b,c)=P(a)*P(c|a)*P(b|c)。
化简后可得:
即:在c给定的条件下,a,b被阻断(blocked),是独立的,称之为head-to-tail条件独立。
插一句:这个head-to-tail其实就是一个链式网络,如下图所示:
在xi给定的条件下,xi+1的分布和x1,x2…xi-1条件独立。即:xi+1的分布状态只和xi有关,和其他变量条件独立,这种顺次演变的随机过程,就叫做马尔科夫链(Markov chain)。且有:
OK,今天在总结贝叶斯网络中的上述3种结构时,发现跟河流关系比较相像,比如:
- ①两条小河流入一条大河,叫head-to-head,由P(a,b,c)=P(c|a,b)P(b)P(a),可得:P(a,b) = P(a)*P(b),即c未知的条件下,a、b被阻断(blocked),是独立的。同时,也谓之汇连,且汇连是条件依赖的(C依赖于A、B的联合分布),汇连这种情况也称为一个v-结构;
- ②一条大河到某处分叉成两条支流,称之为tail-to-tail,由P(a,b,c)=P(b|c)P(a|c)P(c) ,可得:P(a,b|c)=P(a|c)*P(b|c),即在c给定的条件下,a,b被阻断(blocked),是独立的。同时,也谓之分连;
- ③一条大河流到底,中间不分叉不汇入其它河流,但可能其中的某段叫什么江,另一段叫什么江,称之为head-to-tail,由P(a,b,c)=P(b|c)P(c|a)P(a) ,化简可得:P(a,b,c)=P(a)*P(c|a)*P(b|c),即在c给定的条件下,a,b被阻断(blocked),是独立的。同时,也谓之顺连;
不知道读者对这个河流的比喻怎么看?^_^
接着,将上述结点推广到结点集,则是:对于任意的结点集A,B,C,考察所有通过A中任意结点到B中任意结点的路径,若要求A,B条件独立,则需要所有的路径都被阻断(blocked),即满足下列两个前提之一:
- A和B的“head-to-tail型”和“tail-to-tail型”路径都通过C;
- A和B的“head-to-head型”路径不通过C以及C的子孙;
最后,举例说明上述D-Separation的3种情况,则是如下图所示:
上图中左边部分是head-to-tail,右边部分的右上角是tail-to-tail,右边部分的右下角是head-to-head。
2.4 因子图
回到2.2节中那个实例上,如下图所示:
对于上图,在一个人已经呼吸困难的情况下,其抽样的概率是多少呢?即:
咱们来一步步计算推导下:
注:解释下上述式子的第二行到最后一行第三行的推导过程。最开始,所有变量都在sigma(d=1,b,x,c)的后面(sigma表示对“求和”的称谓),但由于P(s)和“d=1,b,x,c”都没关系,所以,可以提到式子的最前面。而且P(b|s)和x、c没关系,所以,也可以把它提出来,放到sigma(b)的后面,从而式子的右边剩下sigma(x)和sigma(c)。
此外,Variable elimination表示的是变量消除的意思。为了更好的解决此类问题,咱们得引入因子图的概念。
2.4.1 因子图的定义
wikipedia上是这样定义因子图的:将一个具有多变量的全局函数因子分解,得到几个局部函数的乘积,以此为基础得到的一个双向图叫做因子图(Factor Graph)。
比如,假定对于函数
,有下述式子成立:
其中
,其对应的因子图
包括:
- 变量节点
- 因子(函数)节点
- 边
,边通过下列因式分解结果得到:在因子(函数)节点
和变量节点
之间存在边的充要条件是
存在。
官方正式的定义果然晦涩!我相信你没看懂。通俗来讲,所谓因子图就是对函数进行因子分解得到的一种概率图。一般内含两种节点,变量节点和函数节点。我们知道,一个全局函数通过因式分解能够分解为多个局部函数的乘积,这些局部函数和对应的变量关系就体现在因子图上。举个例子,现在有一个全局函数,其因式分解方程为:
其中fA,fB,fC,fD,fE为各函数,表示变量之间的关系,可以是条件概率也可以是其他关系(如马尔可夫随机场Markov Random Fields中的势函数)。
为了方便表示,可以写成:
其对应的因子图为:
且上述因子图等价于:
所以,在因子图中,所有顶点不是变量节点就是函数节点,边线表示它们之间的函数关系。
但搞了半天,虽然知道了什么是因子图,但因子图到底是干嘛的呢?为何要引入因子图,其用途和意义何在?事实上,因子图跟贝叶斯网络和马尔可夫随机场(Markov Random Fields)一样,也是是概率图的一种。从上文中,我们可以看到,在概率图中,求某个变量的边缘分布是常见的问题。这问题有很多求解方法,其中之一就是可以把贝叶斯网络或马尔科夫随机场转换成因子图,然后用sum-product算法求解。换言之,基于因子图可以用sum-product 算法高效的求各个变量的边缘分布。
先举个例子说明如何把贝叶斯网络(和马尔科夫随机场)转换成因子图。给定下图所示的贝叶斯网络或马尔科夫随机场:
根据各个变量对应的关系,可得:
其对应的因子图为(以下两种因子图的表示方式皆可):
由上述例子总结出由贝叶斯网络构造因子图的方法:
- 贝叶斯网络中的一个因子对应因子图中的一个结点
- 贝叶斯网络中的每一个变量在因子图上对应边或者半边
- 结点g和边x相连当且仅当变量x出现在因子g中
举几个例子。比如,对于如下的一个因子图:
有:
而对于下图所示的马尔科夫链:
有:
另对于如下图所示的隐马尔科夫模型:
有: