2.4 因子图

    回到2.3节中那个实例上，如下图所示：

 

http://img.blog.csdn.net/20141111005733875

 

    对于上图，在一个人已经呼吸困难（dyspnoea）的情况下，其抽烟（smoking）的概率是多少呢？即：

http://img.blog.csdn.net/20141111005823359

     咱们来一步步计算推导下：

http://img.blog.csdn.net/20141111010027078

    解释下上述式子推导过程：

 

1. 第二行：对联合概率关于b,x,c求和（在d=1的条件下），从而消去b,x,c，得到s和d=1的联合概率。
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）。

    比如，假定对于函数http://img.blog.csdn.net/20141111010913859，有下述式子成立：

http://img.blog.csdn.net/20141111010838872

    其中http://img.blog.csdn.net/20141111010916375包括：

 

1. 变量节点http://img.blog.csdn.net/20141111011033218
2.  因子（函数）节点http://img.blog.csdn.net/20141111010947528
3. 边http://img.blog.csdn.net/20141111011114904存在。

    正式的定义果然晦涩！我相信你没看懂。通俗来讲，所谓因子图就是对函数进行因子分解得到的一种概率图。一般内含两种节点：变量节点和函数节点。我们知道，一个全局函数通过因式分解能够分解为多个局部函数的乘积，这些局部函数和对应的变量关系就体现在因子图上。

    举个例子，现在有一个全局函数，其因式分解方程为：

http://img.blog.csdn.net/20141112103919079

    其中fA,fB,fC,fD,fE为各函数，表示变量之间的关系，可以是条件概率也可以是其他关系（如马尔可夫随机场Markov Random Fields中的势函数）。

    为了方便表示，可以写成：

http://img.blog.csdn.net/20141112104009484

    其对应的因子图为：

 

http://img.blog.csdn.net/20141112104542668

    且上述因子图等价于：

 

http://img.blog.csdn.net/20141112104625484

    所以，在因子图中，所有的顶点不是变量节点就是函数节点，边线表示它们之间的函数关系。

    但搞了半天，虽然知道了什么是因子图，但因子图到底是干嘛的呢？为何要引入因子图，其用途和意义何在？事实上，因子图跟贝叶斯网络和马尔科夫随机场（Markov Random Fields）一样，也是概率图的一种。

    既然提到了马尔科夫随机场，那顺便说下有向图、无向图，以及条件随机场等相关概念。

• 我们已经知道，有向图模型，又称作贝叶斯网络（Directed Graphical Models, DGM, Bayesian Network）。

http://img.blog.csdn.net/20141222112243656

• 但在有些情况下，强制对某些结点之间的边增加方向是不合适的。使用没有方向的无向边，形成了无向图模型（Undirected Graphical Model,UGM）, 又被称为马尔科夫随机场或者马尔科夫网络（Markov Random Field,  MRF or Markov network）。

http://img.blog.csdn.net/20141222112302034

• 设X=(X1,X2…Xn)和Y=(Y1,Y2…Ym)都是联合随机变量，若随机变量Y构成一个无向图 G=(V,E)表示的马尔科夫随机场（MRF），则条件概率分布P(Y|X)称为条件随机场（Conditional Random Field, 简称CRF，后续新的博客中可能会阐述CRF）。如下图所示，便是一个线性链条件随机场的无向图模型：

http://img.blog.csdn.net/20141222111852153

    回到本文的主旨上来。在概率图中，求某个变量的边缘分布是常见的问题。这问题有很多求解方法，其中之一就是把贝叶斯网络或马尔科夫随机场转换成因子图，然后用sum-product算法求解。换言之，基于因子图可以用sum-product 算法高效的求各个变量的边缘分布。

    先通过一些例子分别说明如何把贝叶斯网络（和马尔科夫随机场），以及把马尔科夫链、隐马尔科夫模型转换成因子图后的情形，然后在2.4.2节，咱们再来看如何利用因子图的sum-product算法求边缘概率分布。

    给定下图所示的贝叶斯网络或马尔科夫随机场：

http://img.blog.csdn.net/20141112101407483

    根据各个变量对应的关系，可得：

http://img.blog.csdn.net/20141111092421343

    其对应的因子图为（以下两种因子图的表示方式皆可）：

http://img.blog.csdn.net/20141111092601459

    由上述例子总结出由贝叶斯网络构造因子图的方法：

• 贝叶斯网络中的一个因子对应因子图中的一个结点
• 贝叶斯网络中的每一个变量在因子图上对应边或者半边
• 结点g和边x相连当且仅当变量x出现在因子g中。

    再比如，对于下图所示的由马尔科夫链转换而成的因子图：

http://img.blog.csdn.net/20141111234424734

    有：

http://img.blog.csdn.net/20141111234428132

    而对于如下图所示的由隐马尔科夫模型转换而成的因子图：

 

http://img.blog.csdn.net/20141111234503609

 

    有：

 

http://img.blog.csdn.net/20141111234515031

2.4.2 Sum-product算法

    我们已经知道，对于下图所示的因子图：

http://img.blog.csdn.net/20141111093045895

 

    有：

http://img.blog.csdn.net/20141111093054537

    下面，咱们来考虑一个问题：即如何由联合概率分布求边缘概率分布。

    首先回顾下联合概率和边缘概率的定义，如下：

• 联合概率表示两个事件共同发生的概率。A与B的联合概率表示为http://img.my.csdn.net/uploads/201212/17/1355742607_7553.png。
• 边缘概率（又称先验概率）是某个事件发生的概率。边缘概率是这样得到的：在联合概率中，把最终结果中不需要的那些事件合并成其事件的全概率而消失（对离散随机变量用求和得全概率，对连续随机变量用积分得全概率）。这称为边缘化（marginalization）。A的边缘概率表示为P(A)，B的边缘概率表示为P(B)。 

    事实上，某个随机变量fk的边缘概率可由x1,x2,x3, ..., xn的联合概率求到，具体公式为：

http://img.blog.csdn.net/20141111235305570

    啊哈，啥原理呢？原理很简单，还是它：对xk外的其它变量的概率求和，最终剩下xk的概率！

    此外，换言之，如果有

http://img.blog.csdn.net/20141111235735656

    那么

http://img.blog.csdn.net/20141111235745640

    上述式子如何进一步化简计算呢？考虑到我们小学所学到的乘法分配率，可知a*b + a*c = a*(b + c)，前者2次乘法1次加法，后者1次乘法，1次加法。我们这里的计算是否能借鉴到分配率呢？别急，且听下文慢慢道来。

    假定现在我们需要计算如下式子的结果：

http://img.blog.csdn.net/20141112000434217

    同时，f 能被分解如下：

http://img.blog.csdn.net/20141112000519707

    借鉴分配率，我们可以提取公因子：

http://img.blog.csdn.net/20141112000839984

     因为变量的边缘概率等于所有与他相连的函数传递过来的消息的积，所以计算得到：

http://img.blog.csdn.net/20141112000843006

    仔细观察上述计算过程，可以发现，其中用到了类似“消息传递”的观点，且总共两个步骤。

    第一步、对于f 的分解图，根据蓝色虚线框、红色虚线框围住的两个box外面的消息传递：

http://img.blog.csdn.net/20141112001129256

    计算可得：

http://img.blog.csdn.net/20141112001150643

    第二步、根据蓝色虚线框、红色虚线框围住的两个box内部的消息传递：

 

http://img.blog.csdn.net/20141112001808913

    根据http://img.blog.csdn.net/20141112001819443，我们有：

 

http://img.blog.csdn.net/20141112001830316

    就这样，上述计算过程将一个概率分布写成两个因子的乘积，而这两个因子可以继续分解或者通过已知得到。这种利用消息传递的观念计算概率的方法便是sum-product算法。前面说过，基于因子图可以用sum-product算法可以高效的求各个变量的边缘分布。

    到底什么是sum-product算法呢？sum-product算法，也叫belief propagation，有两种消息：

• 一种是变量(Variable)到函数(Function)的消息：http://img.blog.csdn.net/20141112163109597，如下图所示

http://img.blog.csdn.net/20141112164507756

• 另外一种是函数(Function)到变量(Variable)的消息：http://img.blog.csdn.net/20141112163122468。如下图所示：

http://img.blog.csdn.net/20141112164805362

    以下是sum-product算法的总体框架：

 

• 1、给定如下图所示的因子图：

 

 

http://img.blog.csdn.net/20141112154537627

 

 

 

http://img.blog.csdn.net/20141112154545692

 

• 3、根据sum-product定理，如果因子图中的函数f 没有周期，则有：

 

http://img.blog.csdn.net/20141112154606750

    值得一提的是：如果因子图是无环的，则一定可以准确的求出任意一个变量的边缘分布，如果是有环的，则无法用sum-product算法准确求出来边缘分布。

    比如，下图所示的贝叶斯网络：

 

http://img.blog.csdn.net/20141112183526203

 

    其转换成因子图后，为：

 

http://img.blog.csdn.net/20141112183557236

 

    可以发现，若贝叶斯网络中存在“环”（无向），则因此构造的因子图会得到环。而使用消息传递的思想，这个消息将无限传输下去，不利于概率计算。
    解决方法有3个：

• 1、删除贝叶斯网络中的若干条边，使得它不含有无向环

• 2、重新构造没有环的贝叶斯网络
• 3、选择loopy belief propagation算法（你可以简单理解为sum-product 算法的递归版本），此算法一般选择环中的某个消息，随机赋个初值，然后用sum-product算法，迭代下去，因为有环，一定会到达刚才赋初值的那个消息，然后更新那个消息，继续迭代，直到没有消息再改变为止。唯一的缺点是不确保收敛，当然，此算法在绝大多数情况下是收敛的。

    此外，除了这个sum-product算法，还有一个max-product 算法。但只要弄懂了sum-product，也就弄懂了max-product 算法。因为max-product 算法就在上面sum-product 算法的基础上把求和符号换成求最大值max的符号即可！

    最后，sum-product 和 max-product 算法也能应用到隐马尔科夫模型hidden Markov models上，后面有机会的话可以介绍。本文完。

 

 

3 参考文献和推荐阅读