机器学习笔记之概率图模型(六)推断基本介绍

引言

前面部分分别介绍了贝叶斯网络(Bayessian Network)和马尔可夫随机场(Markov Random Field)的结构表示(Representation)，本节开始将介绍概率图模型的第二部分——推断(Inference)。

回顾：贝叶斯学派与推断

实际上，我们对推断并不陌生，在变分推断基本介绍中就已经介绍了推断的概念。

推断表示从 贝叶斯学派角度实现新样本$\hat{x}$的预测过程中，求解参数的后验概率分布$\mathcal{P}(\theta \mid \mathcal{X})$。
更加泛化的说法：推断的核心是如何基于可观测变量推测未知变量的条件分布。具体数学符号表示如下：

• 贝叶斯学派基于样本集合$\mathcal{X}$对于新样本$\hat{x}$的预测过程：
  $$\begin{array}{rl}\mathcal{P}(\hat{x}\mid \mathcal{X})& ={\int }_{\theta }\mathcal{P}(\hat{x},\theta \mid \mathcal{X})d\theta \\ & ={\int }_{\theta }\mathcal{P}(\hat{x}\mid \theta )\cdot \mathcal{P}(\theta \mid \mathcal{X})d\theta \end{array}$$
• 贝叶斯学派的核心思想是：不关心模型参数$\theta$的具体结果，只关系$\theta$基于$\mathcal{X}$的概率分布$\mathcal{P}(\theta \mid \mathcal{X})$。如果分布$\mathcal{P}(\theta \mid \mathcal{X})$已知的条件下，可以通过期望的形式求解$\mathcal{P}(\hat{x}\mid \mathcal{X})$：
  $$\begin{array}{rl}\mathcal{P}(\hat{x}\mid \mathcal{X})& ={\int }_{\theta }\mathcal{P}(\hat{x}\mid \theta )\cdot \mathcal{P}(\theta \mid \mathcal{X})d\theta \\ & ={\mathbb{E}}_{\theta \mid \mathcal{X}}[\mathcal{P}(\hat{x}\mid \theta )]\end{array}$$

推断的系统介绍

场景构建

样本集合$\mathcal{X}$是$p$维随机变量，并且每一维度是离散型随机变量。它的概率分布/概率模型$\mathcal{P}(\mathcal{X})$表示如下：
$$\mathcal{P}(\mathcal{X})=\mathcal{P}(x_1,x_2,\cdots ,x_p)$$

推断的任务

而推断的任务就是求解变量的概率。
可能是某一个变量的边缘概率/条件概率，也可能是若干个变量组成的联合概率/条件概率。

• 给定$\mathcal{P}(\mathcal{X})$的条件下，某一维度$x_i(i=1,2,\cdots ,p)$的 边缘概率 表示如下：
  概率密度积分公式~
  $$\mathcal{P}(x_i)=\sum _{x_1}\cdots \sum _{i-1}\sum _{i+1}\cdots \sum _{x_p}\mathcal{P}(\mathcal{X})$$
  同理，假设求解$\mathcal{X}$中某一变量集合$x_{\mathcal{A}}$的边缘概率分布，数学符号表示如下：
  x A ∈ { x 1 , x 2 , ⋯   , x p } P ( x A ) = ∑ x j ∉ x A P ( X ) x_{\mathcal A} \in \{x_1,x_2,\cdots,x_p\} \quad \mathcal P(x_{\mathcal A}) = \sum_{x_j \notin x_{\mathcal A}} \mathcal P(\mathcal X) xA​∈{x1​,x2​,⋯,xp​}P(xA​)=xj​∈/xA​∑​P(X)
• 假设随机变量集合 X = { x 1 , x 2 , ⋯   , x p } \mathcal X = \{x_1,x_2,\cdots,x_p\} X={x1​,x2​,⋯,xp​}可分为如下两个子集$x_{\mathcal{A}},x_{\mathcal{B}}$，求解集合间的条件概率分布：
  $$\mathcal{X}=x_{\mathcal{A}}\cup x_{\mathcal{B}}\to \mathcal{P}(x_{\mathcal{A}}\mid x_{\mathcal{B}})$$
• 如果单从给定联合概率分布，求解某变量的边际概率分布的角度观察，最大后验估计推断(MAP Inference)也可算作一种思路。给定$\mathcal{X}$与含参数的推断变量$\mathcal{Z}$的联合概率分布如下：
  这里定义$\mathcal{Z}$是离散型随机变量。
  $$\mathcal{P}(\mathcal{Z},\mathcal{X})=\mathcal{P}(z_1,\cdots ,z_m,x_1,\cdots ,x_p)$$
  最优参数变量的分布结果$\hat{\mathcal{Z}}$可表示为：
  $$\hat{\mathcal{Z}}=\underset{z_1,\cdots ,z_m}{\mathrm{argmax}}\mathcal{P}(\mathcal{Z}\mid \mathcal{X})\propto \underset{z_1,\cdots ,z_m}{\mathrm{argmax}}\mathcal{P}(\mathcal{Z},\mathcal{X})$$
  因为根据贝叶斯定理：
  $$\mathcal{P}(\mathcal{Z}\mid \mathcal{X})=\frac{\mathcal{P}(\mathcal{X}\mid \mathcal{Z})\cdot \mathcal{P}(\mathcal{Z})}{\mathcal{P}(\mathcal{X})}$$
  分母中的$\mathcal{P}(\mathcal{X})$是关于$\mathcal{X}$的边缘概率分布，与$\mathcal{Z}$无关。从而 $\underset{\mathcal{Z}}{\mathrm{argmax}}\mathcal{P}(\mathcal{Z}\mid \mathcal{X})$与$\underset{\mathcal{Z}}{\mathrm{argmax}}\mathcal{P}(\mathcal{Z},\mathcal{X})$ 的目标相同：
  $$\underset{\mathcal{Z}}{\mathrm{argmax}}\mathcal{P}(\mathcal{Z}\mid \mathcal{X})\propto \underset{\mathcal{Z}}{\mathrm{argmax}}\mathcal{P}(\mathcal{Z},\mathcal{X})$$

推断方法介绍

推断主要分为如下两大类型：

• 精确推断(Precise Inference)：希望能够计算出目标变量的边际分布(通过积分(连续型随机变量)或者求和(离散型随机变量)消去其他变量达获取边缘概率分布的目的) 或者条件概率分布的精确结果。

  这种方法的计算量复杂度随着极大团规模的增加而呈现指数级增长。因此，适用范围有限。
  其常用方法有：

  • 变量消去法(Variable Elimination,VE)，它是精确推断的基本思想，利用模型所描述的条件独立性来消减计算目标概率值所需的计算量。

  • 信念传播(Belief Propagation,BP)，也称和积算法(Sum-Product Alglorithm)。针对计算多个边际分布过程中重复使用变量消去法 而产生的大量冗余计算的问题，将变量消去法中的和积操作看做是消息并保存，从而节省大量的计算资源。

    而信念传播的弊端是只能针对树型结构 进行计算。

  • 结点树算法(Junction Tree Algorithm)：可看做是信念传播在 一般图结构下 的推断方法。

• 近似推断(Approximate Inference)：在计算边际概率分布的过程中，可能出现因潜在空间(可以理解成参数变量的特征空间)维度$\mathcal{K}$过高，以至于对参数变量进行积分需要消耗大量算力和时间代价。数学符号表示如下：
  P ( X ) = ∫ Z P ( X , Z ) d Z = ∫ Z P ( X ∣ Z ) ⋅ P ( Z ) d Z = ∫ z 1 ⋯ ∫ z K P ( X ∣ Z ) ⋅ P ( Z ) d z 1 , ⋯   , z K P(X)=∫ZP(X,Z)dZ=∫ZP(X∣Z)⋅P(Z)dZ=∫z1⋯∫zKP(X∣Z)⋅P(Z)dz1,⋯,zK

  P(X)=∫ZP(X,Z)dZ=∫ZP(X∣Z)⋅P(Z)dZ=∫z1⋯∫zKP(X∣Z)⋅P(Z)dz1,⋯,zK
  P(X)​=∫Z​P(X,Z)dZ=∫Z​P(X∣Z)⋅P(Z)dZ=∫z1​​⋯∫zK​​P(X∣Z)⋅P(Z)dz1​,⋯,zK​​
  从而在使用贝叶斯定理过程中，极难求解出后验概率结果：
  $$\mathcal{P}(\theta \mid \mathcal{X})=\frac{\mathcal{P}(\mathcal{X}\mid \theta )\cdot \mathcal{P}(\theta )}{\mathcal{P}(\mathcal{X})}$$
  因此，为了简化运算，我们并不追求参数的精确分布结果，从而通过一些近似方法求解参数分布$\mathcal{P}(\theta \mid \mathcal{X})$。
  常用方法：
  • 针对有环的图结构：LBP(Loop Belief Propagation)算法
  • 确定性近似推断方法，其主要代表有变分推断(Variational Inference)
  • 随机性近似推断方法，主要代表有基于蒙特卡洛采样方法的近似推断，如重要性采样(Importance Sampling)，马尔可夫链蒙特卡洛方法(Markov Chain Monte Carlo)等。

回顾：隐马尔可夫模型中的推断问题

在隐马尔可夫模型介绍中提到的隐马尔可夫模型解决的三个任务：

• 求值任务(Evaluation)：给定模型参数$\pi ,\mathcal{A},\mathcal{B}$条件下，求解观测序列 O = { o 1 , o 2 , ⋯   , o T } \mathcal O = \{o_1,o_2,\cdots,o_T\} O={o1​,o2​,⋯,oT​}发生的概率。即：
  $$\mathcal{P}(\mathcal{O}\mid \lambda )\to \mathcal{P}(o_1,\cdots ,o_T\mid \pi ,\mathcal{A},\mathcal{B})$$
• 学习任务(Learning)：如何通过观测序列$\mathcal{O}$求解最优模型参数$\hat{\lambda }$：
  $$\hat{\lambda }=\underset{\lambda }{\mathrm{argmax}}\mathcal{P}(\mathcal{O}\mid \lambda )$$
• 解码任务(Decoding)：总体上是给定观测序列，求解状态变量的后验概率：
  $$\hat{\mathcal{I}}=\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(\mathcal{I}\mid \mathcal{O})$$

其中，求值任务、解码任务本质上就是推断任务：

• 求值任务方法本身将 状态变量$\mathcal{I}$引入概率分布再积分的方式求解迭代关系：
  $$\begin{array}{r}\mathcal{P}(\mathcal{O}\mid \lambda )=\sum _{\mathcal{I}}\mathcal{P}(\mathcal{I},\mathcal{O}\mid \lambda )\end{array}$$
  并根据选择的观测序列的差异，延伸出前向算法(Forward Algorithm)和后向算法(Backward Algorithm)。
• 而解码任务方法本身是 选择一组合适的状态序列$\hat{\mathcal{I}}$，使得后验概率$\mathcal{P}(\hat{\mathcal{I}}\mid \mathcal{O},\lambda )$最大：
  $$\hat{\mathcal{I}}=\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(\hat{\mathcal{I}}\mid \mathcal{O},\lambda )$$
  而对应方法是 维特比算法：根据相邻时刻状态变量取值的联合概率分布的关联关系：
  这个操作类似于“最大后验概率推断”。
  这里并没有直接使用条件概率进行比较，而是通过 联合概率分布 进行的比较。
  $$\begin{array}{rl}{\delta }_t(k)& =\underset{i_1,\cdots ,i_{t-1}}{\max }\mathcal{P}(o_1,\cdots ,o_t,i_1,\cdots ,i_{t-1},i_t=q_k\mid \lambda )\\ {\delta }_{t+1}(j)& =\underset{i_1,\cdots ,i_t}{\max }\mathcal{P}(o_1,\cdots ,o_{t+1},i_1,\cdots ,i_{t+1}=q_j)\end{array}$$
  最终找到相邻时刻${\delta }_t(k),{\delta }_{t+1}(j)$之间的关联关系：
  $${\delta }_{t+1}(j)={\delta }_t(k)\cdot a_{ij}\cdot b_j(o_{t+1})$$
  从而得到一组最优状态变量序列。

因而，隐马尔可夫模型也被称为 动态贝叶斯网络(Dynamic Bayessian Network)。

下一节将介绍变量消去法(Variable Elimination)。
相关参考：
概率图模型之精确推断
机器学习-概率图模型7-推断Inference-介绍