概率图
引:贝叶斯网络三种形式D划分如何训练马尔可夫网络引:
概率图模型中,概率指的是对数据的一个抽象,图代表的是各种结构。
概率图模型关注的是高维的随机变量P(xi,...,xp),P(x_i,...,x_p),P(xi,...,xp),的求解,一般对概率图模型,可以求得其边缘概率P(xi)P(x_i)P(xi)或者是条件概率P(xj∣xi)P(x_j|x_i)P(xj∣xi)
概率图模型的求解准则:
加法准则P(x1)=∫P(x1,x2)dx2P(x_1)=\int P(x_1,x_2)dx_2P(x1)=∫P(x1,x2)dx2
乘法准则P(x1,x2)=p(x1)P(x2∣x1)=p(x2)P(x1∣x2)P(x_1,x_2)=p(x_1)P(x_2|x_1)=p(x_2)P(x_1|x_2)P(x1,x2)=p(x1)P(x2∣x1)=p(x2)P(x1∣x2)
链式法则P(xi,...,xp)=∏i=1PP(xi∣xi,...,xp)P(x_i,...,x_p)=\prod_{i=1}^{P}P(x_i|x_i,...,x_p)P(xi,...,xp)=∏i=1PP(xi∣xi,...,xp)
贝叶斯定理P(x2∣x1)=P(x1,x2)P(x1)=P(x1,x2)∫P(x1,x2)dx2=P(x2)P(x1∣x2)∫P(x2)P(x1∣x2)dx2P(x_2|x_1)=\frac {P(x_1,x_2)}{P(x_1)}=\frac {P(x_1,x_2)}{\int P(x_1,x_2)dx_2}=\frac {P(x_2)P(x_1|x_2)}{\int P(x_2)P(x_1|x_2)dx_2}P(x2∣x1)=P(x1)P(x1,x2)=∫P(x1,x2)dx2P(x1,x2)=∫P(x2)P(x1∣x2)dx2P(x2)P(x1∣x2)
然而数据维度过高的话处理起来也更加困难,高维数据的困境就是求解联合概率P(xi,...,xp)P(x_i,...,x_p)P(xi,...,xp)时的计算量太大,维度越高计算量就越大。
为了简化高维情况下的运算,前人们做出了很多的假设:比如假设不同维度之间都是相互独立的,也就是P(xi,...,xp)=∏i=1pP(xi),P(x_i,...,x_p)=\prod _{i=1}^{p}P(x_i),P(xi,...,xp)=∏i=1pP(xi),朴素贝叶斯就是采用了这样假设的,假设不同维度之间都是无关系的。
如果维度之间的无关性没有那么强,可以将维度之间的关系假设成马尔可夫假设,也就是给定当前时刻为xi,令j<i,xj⊥xi+1x_i,令j<i,x_j\perp x_{i+1}xi,令j<i,xj⊥xi+1;如果马氏性质不能满足需求,或者可以推断到条件独立性假设,xA⊥xB∣xC,其中xA,xB,xCx_A\perp x_B|x_C,其中x_A,x_B,x_CxA⊥xB∣xC,其中xA,xB,xC都是互不相交的集合;也就是给定c的情况下,a和b是无关的。
贝叶斯网络
贝叶斯网络(Bayesian network),又称信念网络(Belief Network),或有向无环图模型(directed acyclic graphical model),是一种概率图模型,于1985年由Judea Pearl首先提出。它是一种模拟人类推理过程中因果关系的不确定性处理模型,其网络拓朴结构是一个有向无环图(DAG)。
朴素贝叶斯分类假定类条件独立。即给定元组的类标号,属性的值可以条件的相互独立。这一假设的直接目的就是简化运算。然而,实际情况中变量之间基本都会有依赖关系。继而又提出了信念网络,允许在变量的子集间定义类条件独立性。
贝叶斯网络由有向无环图和条件概率表两个成分定义。图中的每个变量条件独立于它的非后代。类比到一个具体的有向无环图中,如果一个节点XXX关于某个事件已经发生,那么他的父节点在这个事件上发生或者不发生都不会对XXX在这个事件上再产生影响;而在XXX没有发生某个事件P(xi)P(x_i)P(xi)之前,其发生的概率也只能受其父节点影响。
所以在贝叶斯网络中,当前节点只能影响其子节点。也就是条件概率P(X∣Parents(Y))P(X|Parents(Y))P(X∣Parents(Y)).
设元组X=(x1,...,xn),X=(x_1,...,x_n),X=(x1,...,xn),其对应的父节点是属性Y1,..,Yn.Y_1,..,Y_n.Y1,..,Yn.既然每个变量都条件独立于它的非后代,那么联合概率分布可以表示为:P(x1,...,xn))=∏i=1nP(xi∣Yi)P(x_1,...,x_n))=\prod_{i=1}^nP(x_i|Y_i)P(x1,...,xn))=i=1∏nP(xi∣Yi)
利用上述规则可以在现实生活中回答实证式查询的概率,比如抽烟的人患肺癌的概率多大。
贝叶斯网络隐含了条件独立性,条件独立性构成了贝叶斯网络。
三种形式
1.head to head
默认情况下,a⊥ca\perp ca⊥c。路径式阻塞的;如果b被观测了,那么路径就是通的。
2.tail to tail
b⊥c∣ab\perp c|ab⊥c∣a
如果a被观测到,b和c独立。
3.head to tail
a⊥c∣ba\perp c|ba⊥c∣b
如果b被观测到,a和c相互独立。
所有的贝叶斯网络都可以用这三种形式表示出来。
D划分
D划分的作用:给定集合,判断其条件独立性。
定义A,B,C是三个没有交集的集合。假设A,B,C是head to tail结构,并且A和C之间有很多顺连的路径,也就是有b在路径上。
如果b满足head to tail或者tail to tail形式,那么这个b必须在xbx_bxb内部。
但是当b满足head to head形式的话,那么b必须在xbx_bxb外部;并且b的后继节点都不会属于xbx_bxb
扩展开来,上述内容就是全局马尔可夫性。
如何训练
可以用梯度下降法更新权重:
wijk<−wijk+(l)∂lnPw(D)∂wijkw_{ijk}<-w_{ijk}+(l)\frac{\partial lnP_w(D)}{\partial w_{ijk}}wijk<−wijk+(l)∂wijk∂lnPw(D)。其中lll代表学习率,建议设置为0.001.
马尔可夫网络
信念网络是有向图模型,而马尔可夫网络是无向图模型。
马尔可夫的条件独立性体现在三个方面:
1.全局马尔可夫性(global Markov):xA⊥xC∣xBx_A\perp x_C|x_BxA⊥xC∣xB.前提条件:从A到C的路径必须经过B,当BBB被观测到时,A和C相互独立。
2.局部马尔可夫性(local Markov):在给定邻居的情况下,a和除了邻居之外的点都是相互独立的。
图中的a只和其直接相邻的节点b、c、d有关;也就是给定b、c、d的前提下,a和其他节点都相互独立。
3.成对马尔可夫性:xi⊥xj∣x全局−i−jx_i\perp x_j|x_{全局-i-j}xi⊥xj∣x全局−i−j.
因子分解:
团:一个关于节点的集合,集合的节点之间都相互连通。
如果一个概率分布可以写成团上的因式分解,那么这个玩意就是 Markov随机场。