概率图模型-推断|机器学习推导系列（十一）

作者: 酷酷的群 | 来源:发表于2020-08-17 18:08 被阅读0次

概率图模型-推断|机器学习推导系列（十一）
概率图模型-表示|机器学习推导系列（十）
概率图模型01 简介
概率图模型(PGM)概要
变分推断|机器学习推导系列（十四）
概率推断到机器学习
机器学习-概率图模型初探
近似推断|机器学习推导系列（二十七）
【机器学习】（七）马尔可夫链、马尔可夫随机场、条件随机场
Day 2080：学习

一、概述

总的来说，推断的任务就是求概率。假如我们知道联合概率 $P(x)=P(x_{1},x_{2},\cdots ,x_{p})$ ，我们需要使用推断的方法来求：

$边缘概率：P(x_{i})=\sum_{x_{1}}\cdots\sum_{x_{i-1}} \sum_{x_{i+1}}\cdots \sum_{x_{p}}P(x)$
$条件概率：P(x_{A}|x_{B}),x=x_{A}\cup x_{B}$
$MAP\; Inference：\hat{z}=\underset{z}{argmax}P(z|x)\propto \underset{z}{argmax}P(z,x)$

以下是一些推断的方法：
①精确推断：
Variable Elimination(VE,变量消除法)(针对树结构)；
Belief Propagation(BP,信念传播,Sum-Product Algo)(针对树结构)；
Junction Tree Algorithm(针对图结构)
②近似推断：
Loop Belief Propagation(针对有环图)；
Mente Carlo Inference(例如Importance Sampling,MCMC)；
Variational Inference

二、Variable Elimination（变量消除法）

变量消除法

图结构

对于上述图结构，假如我们希望求边缘概率 $P(d)$ ，我们就可以应用变量消除法：

$P(d)=\sum _{a,b,c}P(a,b,c,d)\\ =\underset{因子分解}{\underbrace{\sum _{a,b,c}P(a)P(b|a)P(c|b)P(d|c)}}\\ =\sum _{b,c}P(c|b)P(d|c)\underset{\phi _{a}(b)}{\underbrace{\sum _{a}P(a)P(b|a)}}\\ =\sum _{c}P(d|c)\underset{\phi _{b}(c)}{\underbrace{\sum _{b}P(c|b)\phi _{a}(b)}}\\ =\sum _{c}P(d|c)\phi _{b}(c)\\ =\phi _{c}(d)$

解释

我们可以通过观察直接将 $P(d)$ 展开计算的形式来理解变量消除法的作用。首先我们假设 $a$ ， $b$ ， $c$ ， $d$ 都是离散的二值随机变量，只能取 $0$ 和 $1$ 两个值，然后直接将 $P(d)$ 展开：

$P(d)=\sum _{a,b,c}P(a,b,c,d)\\ =\sum _{a,b,c}P(a)P(b|a)P(c|b)P(d|c)\\ =P(a=0)P(b=0|a=0)P(c=0|b=0)P(d|c=0)\\ +P(a=0)P(b=0|a=0)P(c=1|b=0)P(d|c=1)\\ +P(a=0)P(b=1|a=0)P(c=0|b=1)P(d|c=0)\\ +P(a=0)P(b=1|a=0)P(c=1|b=1)P(d|c=1)\\ +P(a=1)P(b=0|a=1)P(c=0|b=0)P(d|c=0)\\ +P(a=1)P(b=0|a=1)P(c=1|b=0)P(d|c=1)\\ +P(a=1)P(b=1|a=1)P(c=0|b=1)P(d|c=0)\\ +P(a=1)P(b=1|a=1)P(c=1|b=1)P(d|c=1)\\ =8\cdot 因子积$

如果直接计算上式中的每一项再加起来就会需要相当大的计算量，而且上式只是每个变量都是二值变量的情况下，如果每个变量能取更多的值就会有更大的计算量。变量消除法就是根据某些节点只与图中自己的邻接节点有关这一特性来简化计算，相当于应用了乘法分配律（ $ab+ac=a(b+c)$ ）来避免计算每一项在加起来。变量消除法在上式中的计算过程为：

$P(d)=\\ (将与a有关的放到一起)\\ ={\color{Red}{P(c=0|b=0)P(d|c=0)\cdot P(a=0)P(b=0|a=0)}}\\ +{\color{Green}{P(c=1|b=0)P(d|c=1)\cdot P(a=0)P(b=0|a=0)}}\\ +{\color{Blue}{P(c=0|b=1)P(d|c=0)\cdot P(a=0)P(b=1|a=0)}}\\ +{\color{Yellow}{P(c=1|b=1)P(d|c=1)\cdot P(a=0)P(b=1|a=0)}}\\ +{\color{Red}{P(c=0|b=0)P(d|c=0)\cdot P(a=1)P(b=0|a=1)}}\\ +{\color{Green}{P(c=1|b=0)P(d|c=1)\cdot P(a=1)P(b=0|a=1)}}\\ +{\color{Blue}{P(c=0|b=1)P(d|c=0)\cdot P(a=1)P(b=1|a=1)}}\\ +{\color{Yellow}{P(c=1|b=1)P(d|c=1)\cdot P(a=1)P(b=1|a=1)}}\\ (应用乘法分配律)\\ ={\color{Red}{P(c=0|b=0)P(d|c=0)\cdot \phi _{a}(b=0)}}\\ +{\color{Green}{P(c=1|b=0)P(d|c=1)\cdot \phi _{a}(b=0)}}\\ +{\color{Blue}{P(c=0|b=1)P(d|c=0)\cdot \phi _{a}(b=1)}}\\ +{\color{Yellow}{P(c=1|b=1)P(d|c=1)\cdot \phi _{a}(b=1)}}\\ (将与b有关的放到一起)\\ ={\color{Red}{P(d|c=0)\cdot P(c=0|b=0)\phi _{a}(b=0)}}\\ +{\color{Green}{P(d|c=1)\cdot P(c=1|b=0)\phi _{a}(b=0)}}\\ +{\color{Red}{P(d|c=0)\cdot P(c=0|b=1)\phi _{a}(b=1)}}\\ +{\color{Green}{P(d|c=1)\cdot P(c=1|b=1)\phi _{a}(b=1)}}\\ (应用乘法分配律)\\ ={\color{Red}{P(d|c=0)\cdot \phi _{b}(c=0)}}\\ +{\color{Green}{P(d|c=1)\cdot \phi _{b}(c=1)}}\\ =\phi _{c}(d)$

缺点

变量消除的缺点很明显：
①计算步骤⽆法存储：每次计算一个边缘概率就要重新计算一遍整个图；
②消除的最优次序是⼀个NP-hard问题：对于复杂的图来说，想要找到一个最优的消除次序是困难的。

三、Belief Propagation（信念传播算法）

Variable Elimination算法的计算重复问题

对于以下图结构：

马尔可夫链

已知联合概率：

$P(a,b,c,d,e)=P(a)P(b|a)P(c|b)P(d|c)P(e|d)$

我们在计算 $e$ 的边缘概率时，使用变量消除法的步骤如下：

$P(e)=\sum_{a,b,c,d}P(a,b,c,d,e)\\ =\sum_{a,b,c,d}P(a)P(b|a)P(c|b)P(d|c)P(e|d)\\ =\underset{m_{d\rightarrow e}(e)}{\underbrace{\sum_{d}P(e|d)\underset{m_{c\rightarrow d}(d)}{\underbrace{\sum_{c}P(d|c)\underset{m_{b\rightarrow c}(c)}{\underbrace{\sum_{b}P(c|b)\underset{m_{a\rightarrow b}(b)}{\underbrace{\sum_{a}P(b|a)P(a)}}}}}}}}$

我们在计算 $c$ 的边缘概率时，使用变量消除法的步骤如下：

$P(c)=\sum_{a,b,d,e}P(a,b,c,d,e)\\ =\sum_{a,b,d,e}P(a)P(b|a)P(c|b)P(d|c)P(e|d)\\ =(\sum_{b}P(c|b)\sum_{a}P(b|a)P(a))\cdot (\sum_{c}P(d|c)\sum_{d}P(e|d))$

我们发现在计算 $c$ 的边缘概率时的前一部分与在计算 $e$ 的边缘概率时的一部分重复了，可以想象在求其他边缘概率的分布时也会有大量的重复，而Belief Propagation算法就是来解决这个问题。

Belief Propagation的引出

上面我们一直计算的是有向图的马尔可夫链，现在我们将问题从链结构引申到树结构，从有向图引申到无向图（Belief Propagation只针对树状结构）。举例来说，有如下无向树：

无向树

现在我们知道该联合概率的因子分解可以写为：

$P(a,b,c,d)=\frac{1}{Z}\psi _{a}(a)\psi _{b}(b)\psi _{c}(c)\psi _{d}(d)\cdot \psi _{ab}(a,b) \psi _{bc}(b,c) \psi _{bd}(b,d)$

我们要求解边缘概率 $P(a)$ ，也要应用到变量消除法，大体步骤是先消去 $c$ 和 $d$ ，然后再消去 $b$ ，该过程如下所示：

$p(a)=\psi _{a}\underset{m_{b\rightarrow a}(a)}{\underbrace{\sum _{b}\psi _{b}\cdot \psi _{ab}(\underset{m_{c\rightarrow b}(b)}{\underbrace{\sum _{c}\psi _{c}\cdot \psi _{bc}}})(\underset{m_{d\rightarrow b}(b)}{\underbrace{\sum _{d}\psi _{d}\cdot \psi _{bd}}})}}$

我们可以看到求解的过程主要就是求以下两项（这里写得规范一些，比如 $a$ 写作 $x_a$ ）：

$\left\{\begin{matrix} m_{b\rightarrow a}(x_{a})=\sum _{x_{b}}\psi _{ab}\cdot \psi _{b}\cdot m_{c\rightarrow b}(x_{b})\cdot m_{d\rightarrow b}(x_{b})\\ p(x_{a})=\psi _{a}\cdot m_{b\rightarrow a}(x_{a}) \end{matrix}\right.$

现在我们可以将求解 $x_{a}$ 边缘概率的过程抽象出来得到求解 $x_{i}$ 边缘概率的过程：

$\left\{\begin{matrix} m_{j\rightarrow i}(x_{i})=\sum _{x_{j}}\psi _{ij}\cdot \psi _{j}\cdot \prod _{k\in Neighbor(j)-i}m_{k\rightarrow j}(x_{j})\\ p(x_{i})=\psi _{i}\cdot \prod _{k\in Neighbor(j)} m_{k\rightarrow i}(x_{i}) \end{matrix}\right.$

我们可以继续观察求解 $x_{i}$ 边缘概率的公式，并对一些部分做一下定义：

$\left\{\begin{matrix} m_{j\rightarrow i}(x_{i})=\sum _{x_{j}}\psi _{ij}\cdot\underset{belief(x_{j})}{ \underbrace{\underset{self}{\underbrace{\psi _{j}}}\cdot \underset{children}{\underbrace{\prod _{k\in Neighbor(j)-i}m_{k\rightarrow j}(x_{j})}}}}\\ p(x_{i})=\psi _{i}\cdot \prod _{k\in Neighbor(j)} m_{k\rightarrow i}(x_{i}) \end{matrix}\right.$

因此求解 $m_{j\rightarrow i}(x_{i})$ 需要两步：

$\left\{\begin{matrix} belief(x_{j})=self\cdot children\\ m_{j\rightarrow i}(x_{i})=\sum _{x_{j}}\psi _{ij}\cdot belief(x_{j}) \end{matrix}\right.$

如图展示了求解 $x_{a}$ 的边缘概率的消去（信息传递）过程：

信息传递

可以想象，在求其他边缘概率时势必会有很多重复的消去过程，但是由于我们已经有了计算 $m_{j\rightarrow i}(x_{i})$ 的通项，我们就可以利用这个公式来消除计算上的重复，而Belief Propagation算法正是利用了这个通项解决了这个问题。

Belief Propagation

Belief Propagation算法的思想是：

不要直接求 $P(a)$ 、 $P(b)$ 、 $P(c)$ 、 $P(d)$ ，只需求所有的 $m_{j\rightarrow i}$ 。

Belief Propagation算法首先求所有的信息传递（收集或分发）的过程得到所有的 $m_{j\rightarrow i}$ （图的遍历），然后套用公式计算边缘概率，总的来说也就是 $BP=VE+Caching$ ：

Belief Propagation算法的信息传递

Belief Propagation算法遍历图的一种方法（Sequential Implementation）如下：
①Get root，assume a is root;
②Collect Message:

for $x_i$ in Neighbor(Root):
collectMsg( $x_i$ )

③Distribute Message:

for $x_i$ in Neighbor(Root):
distributeMsg( $x_i$ )

还有另外一种遍历的方法（Parellel Implementation），这是一种应用在分布式计算中的方法，可以并行计算，这里不做过多介绍。

Max-product

事实上，信念传播算法分为Max-product和 Sum-product，上面讲的属于Sum-product，与Sum-product不同的是Max-product只需要将把求和符号换成求最大值 $max$ 的符号即可。Max-product是 Sum-Product算法的改进，也是在HMM中应用到的 Viterbi算法的推⼴。

仍然拿以下图结构来举例，只画出了要求解的节点（ $a$ ， $b$ ， $c$ ， $d$ ），其他节点（ $E$ ）未画出：

无向树

Max-product的作用是用来求一个序列来使得后验概率最大，也就是：

$(x_{a}^{*},x_{b}^{*},x_{c}^{*},x_{d}^{*})=\underset{x_{a},x_{b},x_{c},x_{d}}{argmax}\; P(x_{a},x_{b},x_{c},x_{d}|E)$

求解过程如下：

$①\; m_{c\rightarrow b} =\underset{x_{c}}{max}\; \psi _{c}\cdot \psi _{bc}\\ ②\; m_{d\rightarrow b} =\underset{x_{d}}{max}\; \psi _{d}\cdot \psi _{bd}\\ ③\; m_{b\rightarrow a} =\underset{x_{b}}{max}\; \psi _{b}\cdot \psi _{ab}\cdot m_{c\rightarrow b}\cdot m_{d\rightarrow b}\\ ④\; max\; P(x_{a},x_{b},x_{c},x_{d})=\underset{x_{a}}{max}\; \psi _{a}\cdot m_{b\rightarrow a}$

这里也进行了一次类似收集信息的过程：

信息传递

与Sum-product不同的是，在求解 $max\; P(x_{a},x_{b},x_{c},x_{d})$ 这个过程中我们不需要求 $m_{a\rightarrow b}$ 、 $m_{b\rightarrow c}$ 、 $m_{b\rightarrow d}$ ，因为我们需要的是 $max\; P(x_{a},x_{b},x_{c},x_{d})$ 概率的值和 $x_{a}^{*}$ ， $x_{b}^{*}$ ， $x_{c}^{*}$ ， $x_{d}^{*}$ 这个序列。

四、概念补充

道德图

我们常常想将有向图转为⽆向图，从⽽应⽤更⼀般的表达式。对于有向图中的三种结构，有不同的转换方法：

链式（head to tail）

head to tail

$P(A,B,C)=\underset{\phi (A,B)}{\underbrace{P(A)P(B|A)}}\underset{\phi (B,C)}{\underbrace{P(C|B)}}$

这说明A，B和B，C是团，因此可以直接去掉箭头：

无向图

V形（tail to tail）

tail to tail

$P(A,B,C)=\underset{\phi (A,B)}{\underbrace{P(B)P(A|B)}}\underset{\phi (B,C)}{\underbrace{P(C|B)}}$

这说明A，B和B，C是团，因此可以直接去掉箭头：

无向图

倒V形（head to head）

head to head

$P(A,B,C)=\underset{\phi (A,B,C)}{\underbrace{P(B|A)P(B)P(B|C)}}$

这说明A，B，C是一个团，需要在A，C之间加一条线：

无向图

观察这三种情况可以将有向图到无向图的转换方法的步骤概括为：
①将每个节点的⽗节点两两相连
②将有向边替换为⽆向边

得到的无向图就是道德图。

因子图

对于⼀个有向图，可以通过引⼊环的⽅式，可以将其转换为⽆向图（Tree-like graph），这个图就叫做道德图。但是我们上⾯的 BP 算法只对⽆环图有效，通过因⼦图可以变为⽆环图。

联合概率的因子图分解方法为：

$P(x)=\prod _{S}f_{S}(x_{S})$

其中：
① $S$ ：图的节点子集
② $x_{S}$ : $S$ 的随机变量子集

有以下无向图：

无向图

可以将其转换成一个简单的因子图：

因子图

其中 $f=f(a,b,c)$ ，对比无向图的因子分解 $P(x)=\frac{1}{Z}\psi (a,b,c)$ ，我们可以看到因子分解本身对应一个特殊的因子图。

因子图不是唯一的，可以看做对因子分解的进一步分解，比如以下分解：

因子图

对应的计算公式为 $P(x)=f_{1}(a,b)f_{2}(a,c)f_{3}(b,c)f_{a}(a)f_{b}(b)f_{c}(c)$ ，因式分解不是唯一的，只需要保证乘积等于概率 $P(x)$ 即可。在上面的因式分解中我们可以看做这个因子图分为两层：

分层

也就是说因子图可以做到随机变量节点之间不直接相连，只与因子节点相连，因子节点只与变量节点相连。

概率图模型-推断|机器学习推导系列（十一）
一、概述总的来说，推断的任务就是求概率。假如我们知道联合概率，我们需要使用推断的方法来求：以下是一些推断的方法...
概率图模型-表示|机器学习推导系列（十）
一、概述基本规则概率图模型使用图的形式表示概率分布，首先总结一下几个随机变量分布的一些规则： Sum Rule...
概率图模型01 简介
概率图模型01简介前言最近开始看《模式识别与机器学习》的时候，遇到了一些障碍，所以开始学习概率图模型，为了更好...
概率图模型(PGM)概要
关于(概率图模型)PGM在wiki上的定义：在概率论、统计学及机器学习中，概率图模型是用图论方法以表现数个独立随...
变分推断|机器学习推导系列（十四）
一、概述对于概率模型来说，如果从频率派角度来看就会是一个优化问题，从贝叶斯角度来看就会是一个积分问题。从贝叶斯...
概率推断到机器学习
霍夫丁不等式理解推断到学习形式化公式证明一个假设为验证多个假设，学习条件公式证明结论面对有限多的假设...
机器学习-概率图模型初探
outline 数学基础 HMM CRF 主题模型数学基础贝叶斯公式：联概 = 条概*边概条件概率 = 联合...
近似推断|机器学习推导系列（二十七）
一、推断的动机和困难推断的动机推断问题是在概率图模型中经常遇到的问题，也就是给定观测变量的情况下求解后验，这里...
【机器学习】（七）马尔可夫链、马尔可夫随机场、条件随机场
概率模型与概率图模型概率模型概率模型（probabilistic model）提供了一种描述框架，将学习任务归...
Day 2080：学习
#统计学习最大熵模型：由最大熵原理推导而得最大熵原理是概率模型学习的一个准则，它认为所有可能的概率模型中，熵最...

概率图模型-推断|机器学习推导系列（十一）

一、概述

二、Variable Elimination（变量消除法）

三、Belief Propagation（信念传播算法）

四、概念补充

相关文章

概率图模型-推断|机器学习推导系列（十一）

概率图模型-表示|机器学习推导系列（十）

概率图模型01 简介

概率图模型(PGM)概要

变分推断|机器学习推导系列（十四）

概率推断到机器学习

机器学习-概率图模型初探

近似推断|机器学习推导系列（二十七）

【机器学习】（七）马尔可夫链、马尔可夫随机场、条件随机场

Day 2080：学习

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

人工智能