概率图模型和网络传播的关系

   学概论图模型的目的是为了解释某篇论文的理论依据&＃xff0c;诚然&＃xff0c;概论图模型的理论基础是如此简单。就是概率论中的sum规则和product规则&＃xff0c;但是如此简单的求解过程&＃xff0c;在高维随机变量上&＃xff0c;计算机也就无能为力&＃xff0c;从而为了解决该问题&＃xff0c;研究者提出利用将高维随机变量映射到图中的节点和节点之间条件独立的假设&＃xff0c;再使用置信传播算法&＃xff0c;让指数级别计算减少为O(n&＃xff09;级别&＃xff0c;虽然在树上&＃xff0c;置信传播有精确解&＃xff0c;但是概论图模型仍然有缺陷&＃xff0c;就是其条件独立的假设&＃xff0c;这种假设构成了图的边。但是这种假设是怎么来的呢&＃xff1f;

      概率图模型理论基础&＃xff0c;来自PRML书籍第八章。我们的问题诉求是需要求条件概率、边缘概率或者最大后验概率&＃xff0c;而图的形式可以帮助我们描述了联合概率分布在所有随机变量 上能够分解为⼀组因⼦的乘积的⽅式&＃xff0c;每个因⼦只依赖于随机变量的⼀个⼦集。有向图对于表达随机变量之间的因果关系很有⽤&＃xff0c;⽽⽆向图对 于表⽰随机变量之间的软限制⽐较有⽤。所以用图来帮助高维随机变量计算。

      概率图模型理论基础就上面两个公式&＃xff0c;一个是求和公式&＃xff0c;也就是求随机变量的X的边缘概率。这⾥p(X, Y )是联合概率&＃xff0c;可以表述为“X且Y 的概率”。类似地&＃xff0c;p(Y | X)是条件概率&＃xff0c;可以表 述为“给定X的条件下Y 的概率”&＃xff0c;p(X)是边缘概率&＃xff0c;可以简单地表述为“X的概率”。注意该公式在任何情况下都是成立的。

虽然其理论基础如此简单&＃xff0c;但一旦随机变量过多&＃xff0c;就会造成指数级别计算量&＃xff0c;尤其是计算联合概率&＃xff0c;所以引入图的概念&＃xff0c;让其在图上完成计算。

   考虑三个随机变量a&＃xff0c;b&＃xff0c;c。那么其联合概率分布按照product rule可以写成p(a, b, c) &＃61; p(c | a, b)p(a, b) &＃xff0c;再次使用product rule可以写成p(a, b, c) &＃61; p(c | a, b)p(b | a)p(a)。那么在这里我们求解联合概率的时候已经隐式的选择了一个特定的的顺序(即a&＃xff0c;b&＃xff0c;c&＃xff09;&＃xff0c;不同的选择顺序会导致求解顺序不同&＃xff0c;从而其对应贝叶斯网络也会不同。按照我们的求解顺序&＃xff0c;我们可以画出求解a&＃xff0c;b&＃xff0c;c联合概率的贝叶斯网络。

将其扩展到k个随机变量&＃xff0c;我们有

注意这个公式是任何情况下是成立的&＃xff0c;不依赖贝叶斯网络求解顺序。那么现在假如给定一个7个节点的贝叶斯网络&＃xff0c;如何求其联合概率呢&＃xff1f;如下图

这种按照贝叶斯网络求解联合概率的跟前面求解顺序相反&＃xff0c;我们可以依据贝叶斯网络写出联合概率求解公式

我们发现任何情况下成立的公式P&＃xff08;x1&＃xff0c;x2&＃xff0c;、、、xk&＃xff09;&＃xff0c;如果选择一定的求解顺序&＃xff0c;也就是画出一个贝叶斯网络&＃xff0c;即在一个给定k个节点贝叶斯网络中求解其联合概率公式就变为

      注意x表示所有随机变量&＃xff0c;pak表示k的父亲节点。&＃xff08;那么一个任何情况成立的公式P&＃xff08;x1&＃xff0c;x2&＃xff0c;、、、xk&＃xff09;&＃xff0c;选择一个求解顺序后&＃xff0c;其形式简单化了&＃xff0c;也就是贝叶斯网络帮助我们求解联合概率更简单了。&＃xff09;联合概率表达式由⼀系列条件概率 的乘积组成&＃xff0c;每⼀项对应于图中的⼀个结点。每个这样的条件概率分布只以图中对应结点的⽗结点为条件。但是这里还没有因子的概念。

这部分有关于有向图的三种局部条件独立结构以及D-划分规则&＃xff0c;注意这里的条件独立性和D-划分其实是在图给定的情况下&＃xff08;我们隐式选择某种求解顺序&＃xff09;就已经有的&＃xff0c;不是需要加条件推导出来的。

这个条件独立性有什么用呢&＃xff1f; 它可以帮助我们求解联合概率&＃xff0c;因为条件独立性所以可以使用因子分解这一步骤&＃xff0c;将求联合概率的式子&＃xff0c;按照乘法分配率&＃xff0c;将先积再和替换成先和再积的方式&＃xff0c;直接在图上进行计算。

    ⽆向图的马尔科夫毯的形式相当简单&＃xff0c;因为结点只条件依赖于相邻结点&＃xff0c;⽽条件独⽴于任何 其他的结点。它表⽰⼀个分解⽅式&＃xff0c;也表⽰⼀组条件独⽴关系。

       在马尔可夫随机场中结合网络传播是天然的&＃xff0c;给定任意情况下的联合概率公式&＃xff0c;比如前面的P&＃xff08;x1&＃xff0c;x2&＃xff0c;x3、、、xk&＃xff09;&＃xff0c;那么一个正在传播的无向图就表示某种分解方式。该无向图可以帮助我们使用BP算法去计算高维的联合概率。

4.1 马尔科夫随机场的分解性质

    那么通过无向图的条件独立性&＃xff0c;我们可以重新整理加和与乘积的 顺序&＃xff08;乘法分配率&＃xff09;&＃xff0c;使得需要求解的边缘概率分布可以更加⾼效地计算。例如ψNN -1,N (xN-1, xN )是唯⼀与xN有关系的势函数&＃xff0c;ψ1,2&＃xff08;x1&＃xff0c;x2&＃xff09;是唯一和x1有关系的函数。因此我们可以进⾏下⾯的求和

依次类推&＃xff0c;我们可以得到

也就是如下图所示的含义

我们发现计算p&＃xff08;xn&＃xff09;需要两个信息相乘得到。

      那么在无向图上传播进行这种推断也是很正常的事情&＃xff0c;假如我们没有任何观测节点&＃xff0c;那么每个节点处于某种感染状态的边缘概率分布可以通过联合概率分布计算得到。但是我们需要知道的是&＃xff0c;我们好像并没有相连节点的之间k*k的表&＃xff0c;比如两个节点都有k个状态。怎么办&＃xff1f;虽然图能够方便的帮我们计算联合概率&＃xff0c;但是如何定义势函数是个问题啊&＃xff1f;没有势函数&＃xff0c;联合概率就没有办法求解&＃xff0c;

6.2 树

6.3 因子图

因子图帮助了解有向&＃xff0c;无向图上因子分解更直观。一个有向图或者无向图可能有好几种因子图对应形式&＃xff0c;下面给两个例子

6.4  BP算法

   在树形因子图上推导BP算法会格外的简单&＃xff0c;例如下图

    对于这一部分BP算法&＃xff0c;有个套路就是定义消息的格式后&＃xff0c;再定义好每个节点对消息的处理方式后&＃xff0c;经过从根节点收集所有消息&＃xff0c;然后再从根节点发送到所有节点消息。自然就可以得到每个节点的边缘概率了。