概率图模型

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(x^{|Y|+|R|})$。另一方面，属性变量之间往往存在复杂的联系，因此概率模型的学习，即基于训练样本来估计变量分布的参数往往相当困难，为了便于研究高效的推断和学习算法，需有一套能简洁紧凑地表达变量间关系的工具。

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

隐马尔可夫模型(Hidden Markov Model，简称 HMM)是结构最简单的动态贝叶斯网(dynamic Bayesian network)，这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。

如图所示，隐马尔可夫模型中的变量可分为两组。第一组是状态变量{$y_1,y_2,...,y_n$}，其中$y_i\in Y$表示第i时刻的系统状态。通常假定状态变量是隐藏的、不可被观测的，因此状态变量亦称隐变量(hidden variable)。第二组是观测变量{$x_1,x_2,...,x_n$}，其中$x_i\in X$表示第i时刻的观测值。在隐马尔可夫模型中，系统通常在多个状态{$s_1,s_2,...,s_N$}之间转换，因此状态变量$y_i$的取值范围Y(称为状态空间)通常是有N个可能取值的离散空间。观测变量$x_i$可以是离散型也可以是连续型，为便于讨论，我们仅考虑离散型观测变量，并假定其取值范围X为{$o_1,o_2,...,o_M$}。

图中的箭头表示了变量间的依赖关系。在任一时刻，观测变量的取值仅依赖于状态变量，即$x_t$由$y_t$确定，与其他状态变量及观测变量的取值无关。同时，t时刻的状态$y_t$仅依赖于t-1时刻的状态$y_{t-1}$，与其余n-2个状态无关。这就是所谓的"马尔可夫链"(Markovchain)，即:系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。基于这种依赖关系，所有变量的联合概率分布为

上述问题在现实应用中非常重要。例如许多任务需根据以往的观测序列{$x_1,x_2,...,x_{n-1}$}来推测当前时刻最有可能的观测值$x_n$，这显然可转化为求取概率P(x|λ)，即上述第一个问题;在语音识别等任务中，观测值为语音信号，隐藏状态为文字，目标就是根据观测信号来推断最有可能的状态序列(即对应的文字)，即上述第二个问题;在大多数现实应用中，人工指定模型参数已变得越来越不可行，如何根据训练样本学得最优的模型参数，恰是上述第三个问题值得庆幸的是，基于式(1)的条件独立性，隐马尔可夫模型的这三个问题均能被高效求解。

14.1.1 小结

隐马尔可夫模型（HMM）是一种用于描述含有隐藏未知参数的序列数据的统计模型，它由隐藏状态集合、观测状态集合、初始状态概率分布、状态转移概率矩阵和观测概率矩阵组成。HMM的核心在于通过隐藏状态序列来预测观测状态序列，常用于语音识别、自然语言处理等领域。它主要解决三个问题：评估问题（计算观测序列出现的概率）、解码问题（找到最可能的隐藏状态序列）和学习问题（估计模型参数）。解决这些问题的关键算法包括前向算法、后向算法、维特比算法和鲍姆-韦尔奇算法。HMM在实际应用中可能需要与其他技术结合使用，并且其参数估计和解码过程需要精心设计的算法来保证效果。

14.2 马尔可夫随机场

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

图显示出一个简单的马尔可夫随机场。对于图中结点的一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个“团”(clique)。若在一个团中加入另外任何一个结点都不再形成团，则称该团为“极大团”(maximalclique)；换言之，极大团就是不能被其他团所包含的团。例如，在图中{x1,x2}，{x1,x3}，{x2,x4}，{x2,x5}，{x2,x6}，{x3,x5}，{x3,x6}和{2,5,x6}都是团，并且除了{x2,x5}，{x2,x6}和{x5,x6}之外都是极大团；但是，因为x2和x3之间缺乏连接，{x1,x2,3}并不构成团。显然，每个结点至少出现在一个极大团中。

小结

马尔可夫随机场（MRF）是一种无向图模型，它通过局部马尔科夫性质来描述随机变量集合中每个变量与其邻居变量之间的依赖关系。这种模型在图像处理、计算机视觉和自然语言处理等多个领域中都有应用。MRF可以使用势函数来量化变量间的关系，并通过吉布斯分布进行数学表达。它涉及的关键任务包括概率推理，即推断给定观测数据下变量的潜在状态，以及参数学习，即从数据中估计模型参数。MRF模型的建立和推断通常采用信念传播、蒙特卡洛马尔可夫链等算法。在图像分割、纹理分析等应用中，MRF通过模拟像素间的相互作用来提高分析的准确性。

14.3 条件随机场

条件随机场(Conditional Random Field，简称 CRF)是一种判别式无向图模型14.1节提到过，生成式模型是直接对联合分布进行建模，而判别式模型则是对条件分布进行建模。前面介绍的隐马尔可夫模型和马尔可夫随机场都是生成式模型，而条件随机场则是判别式模型。

条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说,若令 x = { x 1 , x 2 , . . . , x n } x= \{x_1,x_2,...,x_n\} x={x1​,x2​,...,xn​}为观测序列， y = { y 1 , y 2 , . . . , y n } y=\{y_1,y_2,...,y_n\} y={y1​,y2​,...,yn​}为与之相应的标记序列，则条件随机场的目标是构建条件概率模型P(y|x)。需注意的是标记变量y可以是结构型变量，即其分量之间具有某种相关性。例如在自然语言处理的词性标注任务中，观测数据为语句(即单词序列)，标记为相应的词性序列，具有线性序列结构，如图所示。在语法分析任务中，输出标记则是语法树，具有树形结构，如图所示

14.3.1 小结

条件随机场（CRF）是一种用于序列数据处理的统计模型，主要用于序列标注任务，如词性标注和命名实体识别。CRF模型通过发射特征和转移特征来评估标签序列的概率，并利用动态规划算法找到最可能的标签序列。它能够考虑标签之间的长距离依赖关系，并且输出的是整个标签序列的概率分布，这使得CRF在处理复杂序列数据时非常有效，并且可以提供丰富的信息用于决策。

14.4 学习与推断

基于概率图模型定义的联合概率分布，我们能对目标变量的边际分布(marginal distribution)或以某些可观测变量为条件的条件分布进行推断。条件分布我们已经接触过很多，例如在隐马尔可夫模型中要估算观测序列x在给定参数入下的条件概率分布。边际分布则是指对无关变量求和或积分后得到结果，例如在马尔可夫网中，变量的联合分布被表示成极大团的势函数乘积，于是，给定参数日求解某个变量:的分布，就变成对联合分布中其他无关变量进行积分的过程，这称为"边际化"(marginalization)。

对概率图模型，还需确定具体分布的参数，这称为参数估计或参数学习问题，通常使用极大似然估计或最大后验概率估计求解:但若将参数视为待推测的变量，则参数估计过程和推断十分相似，可以"吸收"到推断问题中。因此下面我们只讨论概率图模型的推断方法。

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

14.4.1 变量消去

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

显然，通过利用乘法对加法的分配律，变量消去法把多个变量的积的求和问题，转化为对部分变量交替进行求积与求和的问题，这种转化使得每次的求和与求积运算限制在局部，仅与部分变量有关，从而简化了计算。

变量消去法有一个明显的缺点:若需计算多个边际分布，重复使用变量消去法将会造成大量的冗余计算。例如在图的贝叶斯网上，假定在计算P($x_5$)之外还希望计算P($x_4$)，若采用{$x_1,x_2,x_5,x_3$}的顺序，则$m_{12}(x_2)$和$m_{23}(x_3)$的计算是重复的。

14.4.2 信念传播

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

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

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

• 指定一个根结点，从所有叶结点开始向根结点传递消息，直到根结点收到所有邻接结点的消息；
• 从根结点开始向叶结点传递消息，直到所有叶结点均收到消息

小结

概率图模型通过精确推断和近似推断方法来进行变量间依赖关系的推断。精确推断方法，如变量消去和信念传播，计算目标变量的边际或条件分布，但计算复杂度随模型复杂性指数增长。近似推断方法在可接受的复杂度内提供推断结果的近似解。参数学习则是确定模型参数的过程，通常结合极大似然或最大后验概率估计。在实际应用中，信念传播因其高效的消息传递机制而被广泛用于无环图结构的精确推断。

14.5 近似推断

精确推断方法通常需要很大的计算开销，因此在现实应用中近似推断方法更为常用。近似推断方法大致可分为两大类：第一类是采样(sampling)，通过使用随机化方法完成近似；第二类是使用确定性近似完成近似推断，典型代表为变分推断(variational inference)。

14.5.1 MCMC采样

在很多任务中，我们关心某些概率分布并非因为对这些概率分布本身感兴趣，而是要基于它们计算某些期望，并且还可能进一步基于这些期望做出决策例如对图的贝叶斯网，进行推断的目的可能是为了计算变量$x_5$的期望若直接计算或逼近这个期望比推断概率分布更容易，则直接操作无疑将使推断问题的求解更为高效。

采样法正是基于这个思路。具体来说，假定我们的目标是计算函数f(x)在概率密度函数p(z)下的期望

14.5.2 变分推断

小结

近似推断是概率图模型中用于处理复杂推断问题的方法，尤其适用于精确推断计算成本过高的情况。它主要分为两类：1. 采样方法：如马尔科夫链蒙特卡洛（MCMC）采样，通过从目标分布中随机抽取样本来近似计算期望值和其他统计量，适用于复杂分布的推断。2. 确定性近似方法：如变分推断，通过优化一个简单分布来近似目标分布，以最小化两个分布之间的差异。变分推断通过引入一个参数化的分布族，利用优化技术调整参数，使得该分布尽可能接近目标分布，从而简化推断过程。这些方法在实际应用中更为常见，因为它们能在可接受的计算成本下提供有用的推断结果。

14.6 话题模型

话题模型(topic model)是一族生成式有向图模型，主要用于处理离散型的数据(如文本集合)，在信息检索、自然语言处理等领域有广泛应用。隐狄利克雷分配模型(Latent Dirichlet Allocation，简称LDA)是话题模型的典型代表。

我们先来了解一下话题模型中的几个概念:词(word)、文档(document)和话题(topic)。具体来说，"词"是待处理数据的基本离散单元，例如在文本处理任务中，一个词就是一个英文单词或有独立意义的中文词。“文档"是待处理的数据对象，它由一组词组成，这些词在文档中是不计顺序的，例如一篇论文、一个网页都可看作一个文档；这样的表示方式称为"词袋”(bag-of-words)。数据对象只要能用词袋描述，就可使用话题模型。"话题"表示一个概念，具体表示为一系列相关的词，以及它们在该概念下出现的概率。

14.6.1 小结

话题模型是一种自然语言处理技术，用于从大量文档中自动发现隐含的主题结构信息。常见的话题模型包括潜在语义分析（LSA）、概率潜在语义分析（PLSA）和潜在狄利克雷分配（LDA）模型。这些模型可以帮助我们理解文档的主要内容、进行文档分类、提取关键词等。LSA通过构建文档-词矩阵并使用奇异值分解（SVD）来提取潜在的语义信息。PLSA则通过一个生成模型来赋予LSA概率意义上的解释，假设文档中的每个单词都是在潜在话题的指引下生成的。LDA模型进一步发展了这一思想，假设文档是由多个话题的混合生成的，每个话题由一组词的概率分布定义。近年来，基于深度学习的话题模型如BERTopic开始受到关注。BERTopic结合了BERT的语义理解能力和非参数聚类算法HDBSCAN的灵活性，生成高质量、语义丰富的话题。与传统的LDA模型相比，BERTopic能够更好地捕捉文本的复杂语义结构，因为它利用了预训练的BERT模型来嵌入文本。话题模型在多个领域有广泛应用，包括信息检索、文本分类、文档摘要、推荐系统和舆情分析。评估话题模型性能的方法包括内部评估（如困惑度和主题连贯性）和外部评估（如人工评估和下游任务性能）。

总结

概率图模型是一类用图表示变量之间关系的概率模型，包括有向图模型（如贝叶斯网）和无向图模型（如马尔可夫随机场）。这些模型在推断和学习参数方面有广泛应用，如隐马尔可夫模型（HMM）在时序数据建模中的应用，条件随机场（CRF）在序列标注任务中的应用，以及话题模型如LDA在文本挖掘中的应用。推断方法包括精确推断（如变量消去和信念传播）和近似推断（如MCMC采样和变分推断），而参数学习通常使用极大似然或最大后验概率估计。这些模型和方法在信息检索、自然语言处理等领域发挥着重要作用。