Online Bayesian Probit Regression介绍之Factor Graph

下面就开始讲讲概率图中的Factor Graph。概率图博大精深,非我等鼠辈能够完全掌握,我只是通过研究一些通用的模型,对概率图了解了一点皮毛。其实我只是从概率这头神兽身上盲人摸象地抓掉几根毛,我打算就讲讲我抓掉这几根毛。

Factor Graph 是概率图的一种,概率图有很多种,最常见的就是Bayesian Network (贝叶斯网络)和Markov Random Fields(马尔可夫随机场)。在概率图中,求某个变量的边缘分布是常见的问题。这问题有很多求解方法,其中之一就是可以把Bayesian Network和Markov Random Fields 转换成Facor Graph,然后用sum-product算法求解。

Bayesian Network,Bayesian Network比较容易理解,主要是描述随机变量之间的条件依赖,用圈表示随机变量(random variables),用箭头表示条件依赖(conditional dependencies)

Bayesian Network的联合概率分布可以用贝叶斯链式法则来表示

Online Bayesian Probit Regression介绍之Factor Graph

例如:

Online Bayesian Probit Regression介绍之Factor Graph

p(A,B)=p(A)p(B|A)

Online Bayesian Probit Regression介绍之Factor Graph

p(A,B,C)=p(A)p(B|A)p(C|A,B)

Markov Random Fields是无向的概率图,和Bayesian Network一样,用圈表示变量,但是边于是无向的,只是表示变量之间有关系,不一定是条件概率的关系。但是也可以表示变量之间的条件独立性,但是没有有向图那么直观。

对于Markov Random Fields只是看到一些介绍,没又真正试过,所以不敢多说。

下面重点介绍Factor Graph和sum-product的算法

Factor Graph 是个二部图,有两类节点(圆代表variable,方块代表function)和无向边构成

Online Bayesian Probit Regression介绍之Factor Graph

例如上图的Factor Graph可以写成如下的联合概率分布:

Online Bayesian Probit Regression介绍之Factor Graph

其中fA,fB,fC,fD,fE为各函数,表示变量之间的关系,可以是条件概率也也可以是其他关系(如Markov Random Fields中的势函数)。

基于Factor Graph可以用sum-product算法可以高效的求各个变量的边缘分布。

sum-product算法,也叫belief propagation,有两种消息,一种是变量(Variable)到函数(Function)的消息(就是方块到圆的消息):mx→f,另外一种是函数(Function)到变量(Variable)的消息:mf→x

Online Bayesian Probit Regression介绍之Factor Graph

Factor Graph如果是树形的,也就是无环的,一定会存在叶子节点,一般从以下两种情况开始:

Online Bayesian Probit Regression介绍之Factor Graph

这时变量到函数的消息为: mx→f=1

Online Bayesian Probit Regression介绍之Factor Graph

这时变量到函数的消息为:mf→x=f(x)

如果Factor Graph是无环的,从以上两种叶子节点一定可以准确的求出任意一个变量的边缘分布,但是如果是有环的,是无法用sum-product算法准确求出来边缘分布的,但是我们也可以用sum-product算法来求,一般是选择环中的某个消息,随机赋个初值,然后用sum-product算法,迭代下去,因为有环,一定会到达刚才赋初值的那个消息,然后更新那个消息,继续迭代,这样下去,直到没有消息再改变为止,这种算法叫loopy belief propagation。LBF不能保证收敛,但是很多情况下它是收敛的。

举个例子,如下图,我们要求p(x3)

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

这不是偶然现象

Online Bayesian Probit Regression介绍之Factor Graph

Factor Graph和sum-product基本概率就到这里,估计没有学过和用过概率图的,到这步已经是云里雾里了,但是没有关系,我觉得一切理论,只用把它运用到实际中,才能算真正懂得。

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

Online Bayesian Probit Regression介绍之Factor Graph

此条目是由 admin 发表在 BPR 分类目录的。将固定链接加入收藏夹。

上一篇:[Mark] openvswitch megaflow


下一篇:SpringBoot之SOAP WebService