概率图模型

机器学习最重要的任务,是根据一些已观察到的证据(例如训练样本)来对感兴趣的未知变量(例如类别标记)进行估计和推测.概率模型提供了一种描述框架,将学习任务归结于计算变量的概率分布.在概率模型中,利用已知变量推测未知变量的分布称为”推断”,其核心是如何基于可观测变量推测出未知变量的条件分布.具体来说,假定所关心的变量集合为Y,可观测变量集合为O,其他变量的集合为R,”生成式”模型考虑联合分布P(Y,R,O),”判别式”模型考虑条件分布P(Y,R|O).给定一组观测变量值,推断就是要由P(Y,R,O)或P(Y,R|O)得到条件概率分布P(Y|O).

直接利用概率求和规则消去变量R显然不可行,因为即便每个变量仅有两种取值的简单问题,其复杂度已至少是$O(2^{|Y|+|R|})$.另一方面，属性变量之间往往存在复杂的联系,因此概率模型的学习,即基于训练样本来估计变量分布的参数往往相当困难.为了便于研究高效的推断和学习算法,需有一套能简洁紧凑地表达变量间关系的工具.

概率图模型是一类用图来表达变量相关关系的概率模型,它以图为表示工具，最常见的是用一个结点来表示一个或一组随机变量,结点之间的边表示变量间的概率相关关系,即”变量关系图”.根据边的性质不同,概率图模型可大致分为两类：第一类是使用有向无环图表示变量之间的依赖关系称为有向图模型或贝叶斯网;第二类是使用无向图表示变量间的相关关系,称为无向图模型或马尔可夫网.

隐马尔可夫模型(HMM)

隐马尔可夫模型是结构最简单的动态贝叶斯网,这一种著名的有向图模型,主要用于时序数据建模,在语音识别、自然语言处理等领域有广泛应用.

在实际应用中,人们常关注隐马尔科夫模型的三个基本问题:

给定模型$\lambda=[A,B,\pi]$,如何有效计算其产生观测序列$X={x_1,x_2,…,x_n}$的概率$P(X|\lambda)$?换言之,如何评估模型与观测序列之间的匹配程度？
给定模型$\lambda=[A,B,\pi]$和观测序列$X={x_1,x_2,…,x_n}$,如何找到与此观测序列最匹配的状态序列$Y={y_1,y_2,….,y_n}$?换言之,如何根据观测序列推断出隐藏的模型的状态?
给定观测序列$X={x_1,x_2,…,x_n}$,如何调整模型参数$\lambda=[A,B,\pi]$使得该序列出现得概率$P(X|\lambda)最大？$换言之,如何训练模型使其能最好地描述观测数据?

马尔可夫随机场

马尔可夫随机场(MRF)是典型地马尔可夫网,这是一种著名地无向图模型.图中每个结点表示一个或一组变量,结点之间地边表示两个变量之间的依赖关系.马尔可夫随机场有一组势函数,亦称”因子”.这是定义在变量子集上的非负实函数,主要是用于定义概率分布函数.

在马尔可夫随机场中,多个变量之间的联合概率分布能基于团分解为多个因子的乘积,每个因子仅与一个团相关.具体来说,对于n个变量$X={x_1,x_2,…,x_n}$,所有团构成的集合为C,与团Q∈C对应的变量集合记为$x_Q$,则联合概率P(X)定义为：

$P(x)=\frac{1}{Z}\prod_{Q∈C}\phi_Q(x_Q)$

其中$\phi_Q$为团Q对应的势函数,用于对团Q中的变量关系进行建模,Z=$\sum_x\prod_{Q∈C}\phi_Q(x_Q)$为规范化因子,以确保P(x)是被正确定义的概率.

显然,若变量个数较多,则团的数目将会很多,这就意味着上面的式子会有很多乘积项,显然会给计算带来负担.注意到若团Q不是极大团,则它必被一个极大团$Q^ $所包含,即$x_Q\subseteq x_{Q^ }$这意味着变量$x_Q$之间的不关系不仅仅体现在势函数$\phi_Q$中,还体现在$\phi_{Q^ }$中,于是,联合概率P(x)可基于极大团来定义.假定所有极大团构成的集合为$C^ $则有

$P(x)=\frac{1}{Z^* }\prod_{Q∈C^* }\phi_Q(x_Q)$

在马尔可夫随机场中如何得到”条件独立性”？
这里有三个概念：1.全局马尔可夫性2.局部马尔可夫性3.成对马尔可夫性

条件随机场(CRF)

前面提到生成式模型是直接对联合概率分布进行建模,而判别式模型则是对条件分布进行建模.前面提到隐马尔科夫模型和马尔可夫随机场都是生成式模型，而条件随机场则是判别式模型。

条件随机场试图对多个变量在给定观测值后的条件概率进行建模.具体来说,若令$x={x_1,x_2,…,x_n}$为观测序列,$y={y_1,y_2,…,y_n}$为与之相应的标记序列,则条件随机场的目标是构建条件概率模型P(y|x).需注意的是,标记变量y可以是结构型变量,即其分量之间具有某种相关性.

学习与推断

基于概率图模型定义的联合概率分布,我们能对目标变量的边际分布或以某些可观测变量为条件的条件分布进行推断.

对概率图模型,还需确定具体分布的参数,这称为参数估计或参数学习问题,通常适用极大似然估计或最大后验概率估计求解.但若将参数视为待推测的变量,则参数估计过程和推断十分相似,可以”吸收”到推断问题中.

具体来说,假设图模型所对应的变量集X=${x_1,x_2,…,x_N}$能分为$X_E$和$X_F$两个不相交的变量集,推断问题的目标就是计算边际概率$P(X_F)$或条件概率$P(X_F|X_E)$.由条件概率的定义有

$P(X_F|X_E)=\frac{P(X_E,X_F)}{P(X_E)}=\frac{P(X_E,X_F)}{\sum_{X_F}P(X_E,X_F)}$

其中联合概率$P(X_E,X_F)$可基于概率图模型获得,因此,推断问题的关键就是如何高效地计算边际分布,即

$P(X_E)=\sum_{X_F}P(X_E,X_F)$

概率图模型地推断方法大致可分为两类:第一类是精确推断方法,希望能计算出目标变量地边际分布或条件分布的精确值;遗憾地是,一般情况下,此类算法的计算复杂度随着极大团的规模的增长呈指数增长,适用范围有限.第二类是近似推断方法,希望在较低的时间复杂度下获得原问题的近似解;此类在现实任务中更常用.

变量消去

精确推断的实质是一类动态规划算法,它利用图模型所描述的条件独立来削减计算目标概率值所需的计算量.变量消去法是最直观的精确推断算法,也是构建其他精确推断算法的基础.

变量消去法有一个明显缺点:若需计算多个边际分布,重复适用变量消去法将会造成大量的冗余计算.

信念传播

信念传播(Belief Propagation)算法将变量消去法中的求和操作看作一个消去传递过程,较好地解决了求解多个边际分布时重复计算的问题.具体来说,变量消去法通过求和操作

$m_{ij}(x_j)=\sum_{x_i}\phi(x_i,x_j)\prod_{k∈n(i)\\j}m_{ki}(x_i)$

消去变量$x_i$,其中n(i)表示结点$x_i$的邻接结点.在信念传播算法中,这个操作被看作从$x_i$向$x_j$传递一个消息$m_{ij}(x_j)$. 不难发现,每次传递操作仅与变量$x_i$及其邻接结点直接相关,换言之,消息传递相关的计算被限制在图的局部进行.

在信念传播算法中,一个结点仅在接收到来自其他所有结点的消息后才能向另一个结点发送消息,且结点的边际分布正比于它所接收到的消息的乘积,即

$P(x_i)正比于\prod_{k∈n(i)}m_{ki}(x_i)$

若图结构中没有环,则信念传播算法经过两个步骤即可完成所有消息传递,进而能计算所有变量的边际分布:

指定一个根节点,从所有叶结点开始向根节点传递消息,直到根节点受到所有邻接结点的消息
从根节点开始向叶结点传递信息,直到所有叶结点收到消息

近似推断

近似推断方法大致可分为两大类:第一类是采样(sampling),通过使用随机化方法来完成近似;第二类是使用确定性近似完成近似推断,代表为变分推断