3.1.1.4 概率图模型
神经网络
原理
14.1 隐马尔可夫模型
-
机器学习最重要的任务，是根据一些已观察到的证据（例如训练样本）来对感兴趣的未知变量（例如类别标记）进行估计和推测。概率模型(probabilistic model)提供了一种描述框架，将学习任务归结于计算变量的概率分布。在概率模型中，利用已知变量推测未知变量的分布称为“推断”(inference)，其核心是如何基于可观测变量推测未知变量的条件分布。具体来说，假定所关心的变量集合为Y，可观测变量集合为O，其他变量的集合为R，“生成式”(generative)模型考虑联合分布 P(Y, R, O)，“判别式”(discriminative)模型考虑条件分布 P(Y, R | O)。给定一组观测变量值，推断就是要由P(Y, R, O)或P(Y, R | O)得到条件概率分布 P(Y | O)。
-
直接利用概率求和规则消去变量R显然不可行，因为即便每个变量仅有两种取值的简单问题，其复杂度已至少是O(2^(|Y|+|R|))。另一方面，属性变量之间往往存在复杂的联系，因此概率模型的学习，即基于训练样本来估计变量分布的参数往往相当困难。
-
概率图模型(probabilistic graphical model)是一类用图来表达变量相关关系的概率模型。它以图为表示工具，最常见的是用一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系，即“变量关系图”。根据边的性质不同，概率图模型可大致分为两类：第一类是使用有向无环图表示变量间的依赖关系，称为有向图模型或贝叶斯网(Bayesian network)；第二类是使用无向图表示变量间的相关关系，称为无向图模型或马尔可夫网(Markov network)。若变量间存在显式的因果关系，则常使用贝叶斯网；若变量间存在相关性，但难以获得显式的因果关系，则常使用马尔可夫网。
-
隐马尔可夫模型(Hidden Markov Model, HMM)是结构最简单的动态贝叶斯网(dynamic Bayesian network)，这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语音处理等领域有广泛的应用。
-
隐马尔可夫模型中的变量可分为两组。第一组是状态变量，通常假定状态变量是隐藏的、不可被观测的，因此状态变量亦称隐变量(hidden variable)。第二组是观测变量。箭头表示了变量间的依赖关系，在任一时刻，观测变量的取值仅依赖于状态变量，与其他状态变量及观测变量的取值无关。
-
“马尔可夫链”(Markov chain)：系统下一时刻的状态仅由当前状态决定，不依赖以往的任何状态。
-
除了结构信息，欲确定一个隐马尔可夫模型还需要以下三组参数：
- 状态转移概率：模型在各个状态间转换的概率，通常记为矩阵A。
- 输出观测概率：模型根据当前状态获得各个观察值的概率，通常记为矩阵B。
- 初始状态概率：模型在初始时刻各状态出现的概率，通常记为π。
-
通过制定状态空间Y、观测空间X和上述三组参数，就能确定一个隐马尔可夫模型，通常用其参数 λ = [A, B, π]来指代。给定隐马尔可夫模型 λ，它按如下过程产生观测序列 {x1, x2, ..., xn}：
- 设置 t = 1，并根据初始状态概率π选择初始状态y1；
- 根据状态 yt 和输出观测概率 B 选择观测变量取值 xt；
- 根据 yt 和状态转移矩阵 A 转移模型状态，即确定 y_t+1；
- 若 t < n，设置 t = t + 1， 并转移到第 2 步，否则停止。
-
在实际应用中，人们常关注马尔可夫模型的三个基本问题：
- 给定模型 λ = [A, B, π]， 如何有效计算其产生观测序列 x = {x1, x2, ..., xn} 的概率 P(x | λ)？换言之，如何评估模型与观测序列之间的匹配程度？例如许多任务需根据以往的观测序列{x1, x2, ..., x_n-1} 来推测当前时刻最有可能的观测值 xn，这显然可转化为求取概率 P(x | λ)。
- 给定模型 λ = [A, B, π] 和观测序列 x = {x1, x2, ..., xn}，如何找到与此观测序列最匹配的状态序列 y = {y1, y2, ..., yn} ？ 换言之，如何根据观测序列推断出隐藏的模型状态？在语音识别等任务中，观测值为语音信号，隐藏状态为文字，目标就是根据观测信号来推断最有可能的状态序列(即对应的文字)。
- 给定观测序列 x = {x1, x2, ..., xn}，如何调整模型参数 λ = [A, B, π] 使得该序列出现的概率 P(x | λ)最大？换言之，如何训练模型使其能最好地描述观测数据？在大多数现实应用中，人工指定模型参数已变得越来越不可行，如何根据训练样本学得最优的模型参数，恰是该问题。
14.2 马尔可夫随机场
-
马尔可夫随机场(Markov Random Field, MRF)是典型的马尔可夫网，这是一种著名的无向图模型。图中每个结点表示一个或一组变量，结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数(potential functions)，亦称“因子”(factor)，这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。
-
对于图中结点的一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个“团”(clique)。若在一个团中加入另外任何一个结点都不再形成团，则称该团委“极大团”(maximal clique)；换言之，极大团就是不能被其他团所包含的团。每个结点至少出现在一个极大团中。
-
在马尔可夫随机场中，多个变量之间的联合概率分布能基于团分解为多个因子的乘积，每个因子仅与一个团相关。
-
显然，若变量个数较多，则团的数目将会很多(例如，所有相互连接的两个变量都会构成团)，这就意味着会有很多乘积项，显然会给计算带来负担。注意到若团Q不是极大团，则它必被一个极大团Q所包含，这意味着变量XQ之间的关系不仅体现在势函数
ψQ 中，还体现在 ψQ 中。于是，联合概率分布P(x)可基于极大团来定义。 -
在马尔可夫随机场中如何得到“条件独立性”呢？同样借助“分离”的概念，若从结点集 A 中的结点到 B 中的结点都必须经过结点集 C 中的结点，则称结点集 A 和 B 被结点集 C 分离，C称为“分离集”(separating set)。对马尔可夫随机场，有
- “全局马尔可夫性”(global Markov property)：给定两个变量子集的分离集，则这两个变量子集条件独立。
- 局部马尔可夫性(local Markov property)：给定某变量的邻接变量，则该变量条件独立于其他变量。
- 成对马尔可夫性(pairwise Markov property)：给定所有其他变量，两个非邻接变量条件独立。
-
马尔可夫随机场中的势函数 ψQ(XQ的作用是定量刻画变量集 XQ 中变量之间的相关关系，它应该是非负函数，且在所偏好的变量取值上有较大的函数值。为了满足非负性，指数函数常被用于定义势函数
14.3 条件随机场
- 条件随机场(Conditional Random Field, CRF)是一种判别式无向图模型。
- 生成式模型是直接对联合分布进行建模，而判别式模型则是对条件分布进行建模。前面介绍的隐马尔可夫模型和马尔可夫随机场都是生成式模型，而条件随机场则是判别式模型
- 条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说，若令 x = {x1, x2, ..., xn} 为观测序列， y = {y1, y2, ..., yn} 为与之相应的标记序列，则条件随机场的目标是构建条件概率模型 P(y | x)。需要注意的是，标记变量 y 可以是结构型变量，即其分量之间具有某种相关性。例如，在自然语音处理的词性标注任务中，观测数据为语句(即单词序列)，标记为相应的词性序列，具有线性序列结构；在语法分析任务中，输出标记则是语法树，具有树形结构。
- 令 G = <V, E> 表示结点与标记变量 y 中元素一一对应的无向图。若图G的每个变量 yv 都满足马尔可夫性，则(y, x)构成一个条件随机场。
- 理论上来说，图 G 可具有任意结构，只要能标记变量之间的条件独立性关系即可。但在现实应用中，尤其是对标记序列建模时，最常用的仍是链式结构，即“链式条件随机场”(chain-structured CRF)。
- 与马尔可夫随机场定义联合概率的方式类似，条件随机场使用势函数和图结构上的团来定义条件概率 P(y | x)。给定观测序列x，链式条件随机场主要包含两种关于标记变量的团，即单个标记变量{yi}以及相邻的标记变量{y_i-1, yi}。选择合适的势函数，即可得到条件概率定义。在条件随机场中，通过选用指数函数并引入特征函数(feature function)。
- 条件随机场和马尔可夫随机场均使用团上的势函数定义概率，两者在形式上没显著区别；但条件随机场处理的是条件概率，而马尔可夫随机场处理的是联合概率。
14.4 学习与推断
-
基于概率图模型定义的联合概率分布，我们能对目标变量的边际分布(marginal distribution)或以某些可观测变量为条件的条件分布进行推断。
- 条件分布我们已经接触过很多，例如在隐马尔可夫模型中药估算观测序列 x 在给定参数 λ 下的条件概率分布。
- 边际分布则是指无关变量求和或积分后得到结果，例如在马尔可夫网中，变量的联合分布被表示成极大团的势函数乘积，于是，给定参数 θ 求解某个变量 x 的分布，就变成对联合分布中其他无关变量进行积分的过程，这称为“边际化”(marginalization)。
-
对概率图模型，还需确定具体分布的参数，这称为参数估计或参数学习问题，通常使用极大似然估计或最大后验概率估计求解。但若将参数视为待推测的变量，则参数估计过程和推断十分相似，可以“吸收”到推断问题中。因此，下面我们只讨论概率图模型的推断方法。
-
具体来说，假设图模型所对应的变量集 x = {x1, x2, ..., xN} 能分为 xE 和 xF 两个不想交的变量集，推断问题的目标就是计算边缘概率 P(xF) 或条件概率 P(xF | xE)。其中联合概率P(xE, xF)可基于概率图模型获得，因此，推断问题的关键就是如何高效地计算边际分布，即P(xE)。
-
概率图模型的推断方法大致可分为两类：
- 第一类是精确推断方法，希望能计算出目标变量的边际分布或条件分布的精确值；遗憾的是，一般情况下，此类算法的计算复杂度随着极大团规模的增长曾指数增长，适用范围有限。
- 第二类是近似推断方法，希望在较低的时间复杂度下获得原问题的近似解；此类方法在现实任务中更常用。
14.4.1 变量消去
- 精确推断的实质是一类动态规划算法，它利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量。变量消去法是最直观的精确推断算法，也是构建其他精确推断算法的基础。
- 变量消去法有一个明显的缺点：若需要计算多个边际分布，重复使用变量消去法将会造成大量的冗余计算。
14.4.2 信念传播
- 信念传播(Belief Propagation)算法将变量消去法中的求和操作看作一个消息传递过程，较好地解决了求解多个边际分布时的重复计算问题。
- 若图结构中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而能计算所有变量上的边际分布：
- 指定一个根结点，从所有叶结点开始向根结点传递消息，直到根结点收到所有邻接结点的消息；
- 从根结点开始向叶结点传递消息，直到所有叶结点均收到消息。
14.5 近似推断
- 精确推断方法通常需要很大的计算开销，因此在现实应用中近似推断方法更为常用。近似推断方法大致可分为两大类：第一类是采样(sampling)，通过使用随机化方法完成近似；第二类是使用确定性近似完成近似推断，典型代表为变分推断(variational inference)。
14.5.1 MCMC采样
- 在很多任务中，我们关心某些概率分布并非因为对这些概率分布本身感兴趣，而是要基于它们计算某些期望，并且还能进一步基于这些期望做出决策。若直接计算或逼近这个期望比推断概率分布更容易，则直接操作无疑将使推断问题的求解更为高效。
- 采样法正是基于这个思路。若样本{x1, x2, ..., xN} 独立，基于大数定律，这种通过大量采样的办法就能获得较高的近似精度。问题的关键是如何采样，对概率图模型来说，就是如何高效地基于图模型所描述的概率分布来获取样本。
- 概率图模型中最常用的采样技术是马尔可夫链蒙特卡洛(Markov Chain Monte Carlo, MCMC)方法。
- 若概率密度函数p(x)很复杂，则构造服从 p 分布的独立同分布样本也很困难。MCMC方法的关键就在于通过构造“平稳分布为 p 的马尔可夫链”来产生样本：若马尔可夫链运行时间足够长(即收敛到平稳状态)，则此时产生的样本 x 近似服从分布 p。
- MCMC方法先设法构造一条马尔可夫链，使其收敛至平稳分布恰为待估计参数的后验分布，然后通过这条马尔可夫链来产生符合后验分布的样本，并基于这些样本来进行估计。这里马尔可夫链转移概率的构造至关重要，不同的构造方法将产生不同的MCMC算法。
- Metropolis-Hastings (MH) 算法是 MCMC 的重要代表。吉布斯采用(Gibbs sampling)有时被视为 MH 算法的特例，它也使用马尔可夫链获取样本。
14.5.2 变分推断
- 变分推断通过使用已知简单分布来逼近需推断的复杂分布，并通过限制近似分布的类型，从而得到一种局部最优、但具有确定解的近似后验分布。
- 在实践中使用变分法时，最重要的是考虑如何对隐变量进行拆解，以及假设各变量子集服从何种分布。显然，若隐变量的拆解或变量子集的分布假设不当，将会导致变分法效率低、效果差。
14.6 话题模型
- 话题模型(topic model)是一种生成式有向图图模型，主要用于处理离散型的数据（如文本集合），在信息检索、自然语言处理等领域有广泛应用。隐狄利克雷分配模型(Latent Dirichlet Allocation, LDA)是话题模型的典型代表。
- 词(word)、文档(document)和话题(topic)：“词”是待处理数据的基本离散单元，例如在文本处理任务中，一词就是一个英文单词或有独立意义的中文词。“文档”是待处理的数据对象，它由一组词组成，这些词在文档中是不计顺序的，例如一篇论文、一个网页都可看作一个文档；这样的表示方式成为“词袋”(bag-of-words)，数据对象只要能用词袋描述，就可使用话题模型。“话题”表示一个概念，具体表示为一系列相关的词，以及它们在该概念下出现的概率。
- 形象地说，一个话题就像是一个箱子，里面装着在这个概念下出现概率较高的那些词。不妨假定数据集中一共包含K个话题和T篇文档，文档中的词来自一个包含N个词的词典。我们用T个N维词向量 W = {w1, w2, ..., wT} 表示数据集(即文档集合)，K个N维向量 βk (k = 1, 2, ..., K) 表示话题。
- 在现实任务中可通过统计文档中出现的词来获得词频向量 wi (i = 1, 2, ..., T)，但通常并不知道这组文档谈论了哪些话题，也不知道每篇文档与哪些话题有关。LDA从生成式模型的角度来看待文档和话题。具体来说，LDA认为每篇文档包含多个话题，不妨用向量 θt 表示文档 t 中所包含的每个话题的比例， θ_t,k 即表示文档 t 中包含话题 k 的比例，进而通过下面的步骤由话题“生成”文档 t：
- 根据参数为 α 的狄利克雷分布随机采用一个话题分布 θt；
- 按如下步骤生成文档中的 N 个词：
a) 根据 θt 进行话题指派，得到文档 t 中词 n 的话题 z_t,n；
b) 根据指派的话题所对应的词频分布 βk 随机采用生成词。
