机器学习的核心思想就是根据已知的内容去推测未知的内容，然后在已知和未知之间建立起联系，这个联系就是机器学习中的各种模型！这和我们的经验系统很像，在第一章中的挑西瓜的例子就是我们利用经验系统来把西瓜的可观测外观信息（根蒂、花纹、声响）和未知信息（是否是好瓜）建立起联系的结果。

说回本章的内容，一种建立已知信息与未知信息联系的方法是对未知信息的概率分布进行推测。概率模型（probabilistic model）提供了一种描述框架，将学习任务归结于计算变量的概率分布。在概率模型中，利用已知变量推测未知变量的分布称为“推断”（inference），其核心是如何基于可观测变量 x 推测出未知变量 c 的条件分布 P( c | x ) 。贝叶斯学习算法就是一个经典的概率模型

具体来说，概率模型有“生成式”和“判别式”两种方式，这两种类型的区别在第七章贝叶斯分类器“一起来读西瓜书：第七章 贝叶斯分类器”中已有过介绍，简单来说，前者是通过计算 P(c, r, x) 来得到 P( c | x )的，后者是直接计算 P(c, r | x) 来得到 P( c | x )的，其中 r 是除了可观测变量和要计算的变量外的其他变量。

上边介绍了那么多，那么到底什么是概率图模型呢？

概率图模型是一类用图来表达变量相关关系的概率模型。使用概率图模型的原因是因为直接利用概率求和规则消去变量 r 计算开销太大，而且属性之间往往存在复杂的关系，而以图为表现工具，对变量间的关系进行简洁紧凑的表达将有助于提高研究推断和学习算法的效率。

概率图模型根据边的性质不同，大致可分为以下两类：第一类是使用有向无环图表示变量之间的依赖关系，称为有向图模型或者贝叶斯网（Bayesian network）；第二类是使用无向图表示变量间的相关关系，称为无向图模型或者马尔可夫网（Markov network）

下边我将分别对概率图模型的不同类型、学习和推断详情以及具体的模型进行介绍，希望通过本章的学习，大伙能对概率图模型有个较为清晰的认识

1）隐马尔可夫模型（Hidden Markov Model，简称 HMM ）

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

隐马尔可夫模型具有两组变量，第一组是系统的状态变量｛y1, y2, ... , yn｝，其中 yi 为第 i 时刻系统的状态。通常假定状态变量是隐藏的、不可被观测的，因此状态变量亦称“隐变量”（hidden variable）。第二组是观测变量｛x1, x2, ... , xn｝，其中 xi 是第 i 时刻的观测值。下图是隐马尔可夫模型的图结构：

图中的箭头表示了变量间的依赖关系。隐马尔可夫模型是建立在这样的前提下的：在任一时刻，观测变量的取值仅依赖于其对应的状态变量，即 xi 由 yi 决定；同时，t 时刻的状态变量只由 t-1 时刻的状态变量决定。

这就是所谓的“马尔可夫链”（Markov Chain）：系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态

基于这种依赖关系，所有变量的联合概率分布为：

P(x1, y1, ... , xn, yn) =

P(y1) P( x1| y1 ) P( y2 | y1 ) P( x2 | y2) ... P( yn | yn-1) P( xn | yn)

除了结构信息，欲确定一个隐马尔可夫模型还需以下三组参数：

［1］状态转移概率：A -> aij = P( yt+1 = sj | yt = si )，系统从一个状态转移到另一个状态的概率

［2］输出观测概率：B -> bij = P( xt = oj | yt = si ) ，系统在当前状态的观测值概率

［3］初始状态概率：∏ -> ∏i = P( y1 = oj )，系统的初始状态概率

通过指定状态空间 Y、观测空间 X 和上述三组概率参数 r = [A, B, ∏] ，就能确定一个隐马尔可夫模型。具体的步骤为：

［1］用初始状态概率 ∏ 算出初始状态 y0

［2］用 B 算出当前状态的观测值 xt

［3］用 A 算出下一个状态 yt+1

［4］重复第二、第三步直到到达停止条件

可在实际应用中，隐马尔可夫模型的参数并不一定都能得到，因此人们常常关注下边三个基本问题：

［1］给定了参数 r，并且知道观测序列 X = {x0, x1, ..., xn-1}，评估模型与观测序列之间的匹配程度，来推测下一状态的观测概率： P( xn | r )

［2］给定了参数 r，并且知道观测序列 X = {x0, x1, ..., xn}，要预测对应的状态序列 Y = {y0, y1, ..., yn}

［3］给定观测序列 X = {x0, x1, ..., xn}，如何调整模型参数 r 使得该序列出现的概率最大

2）马尔可夫随机场（Markov Random Field，简称 MRF）

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

马尔可夫随机场是一种具有马尔可夫特性的随机场，要理解什么是马尔可夫随机场，我们得要先理解什么是随机场，而什么又是马尔科夫特性。

［1］什么是随机场

在概率论中, 由样本空间Ω = {0, 1, …, G − 1}n取样构成的随机变量Xi所组成的S = {X1, …, Xn}。若对所有的ω∈Ω下式均成立，则称π为一个随机场。

π(ω) > 0.

当给每一个位置中按照某种分布随机赋予相空间的一个值之后，其全体就叫做随机场。我们不妨拿种地来打个比方。其中有两个概念：位置（site），相空间（phase space）。“位置”好比是一亩亩农田；“相空间”好比是种的各种庄稼。我们可以给不同的地种上不同的庄稼，这就好比给随机场的每个“位置”，赋予相空间里不同的值。所以，俗气点说，随机场就是在哪块地里种什么庄稼的事情

［2］什么是马尔可夫特性

上一节我们提到了马尔可夫链的概念，即系统的下一状态仅由当前状态决定，不依赖于以往的任何状态。马尔可夫特性是这个概念的一个变化，即一个变量只与其邻接变量相关，不依赖于不相邻的任何变量

还是拿种地打比方，如果任何一块地里种的庄稼的种类仅仅与它邻近的地里种的庄稼的种类有关，与其它地方的庄稼的种类无关，那么这些地里种的庄稼的集合，就是一个马尔可夫随机场。

［3］“团”（clique）、“极大团”（maximal clique）及联合概率

下图是一个简单的马尔可夫随机场。对于图中结点的一个子集，若任意两个结点间都有边连接，则称该结点子集为一个团。若在一个团中加入另外任何一个结点都不再构成团，则称该团为极大团

引入团概念的原因是什么呢？其实很简单，就是为了能更方便的计算变量x的联合概率。根据马尔可夫特性，每个变量只与其邻接结点相关，那么多个变量之间的联合概率分布能基于团分解为多个因子的乘积。具体来说，对于 n 个变量 x = {x1, x2, ..., xn}，所有团构成的集合为 C，与团 Q 属于 C 对应的变量集合记为 xQ，则联合概率 P(x) 定义为：

其中 Z 为规范化因子，被连乘的函数代表的是团 Q 对应的势函数，势函数的作用是定量刻画变量集 xQ 中变量之间的相关关系。

3）条件随机场（Conditional Random Field，简称 CRF）

条件随机场是一种判别式无向图模型，它可以被看成是给定观测值的马尔可夫随机场。前边介绍的隐马尔可夫模型和马尔可夫随机场都是“生成式”模型，而条件随机场是“判别式”模型，即给定观测数据｛x1, x2, ..., xn｝以及对应的标记数据｛y1, y2, ..., yn｝，构建条件概率模型 P( y | x )。

对于一个无向图模型，若图中的每个变量 y_v 都满足马尔可夫性，即

则称 (y, x) 构造一个条件随机场

理论上来说，条件随机场的图 G 可具有任意结构，只要能表示标记变量之间的条件独立性即可。但在实际应用中，尤其是对标记序列建模时，最常用的仍是下图所示的链式结构，即“链式条件随机场”（chain-structured CRF）

与马尔可夫随机场类似，条件随机场也使用了合适的“势函数”来计算所要求的条件概率，只不过条件随机场是将势函数引入特征函数（feature function）中来进行计算的。

特征函数通常是实值函数，以刻画数据的一些很可能成立或期望成立的经验特征。比如在下图所示的语法分析任务中，

可以有如下特征函数，

这说明经验上来说，第 i 个观测值为“knock”时，其相应的标记 y_i 和 y_i+1 很可能分别为 [V] 和 [P]

4）学习与推断

在介绍了概率图模型的三种主流结构后，接下来我们继续学习如何在概率图模型中进行学习和推断。

基于概率图模型定义的联合概率分布，我们能对目标变量的边际分布或以某些可观测变量为条件的条件分布进行推断。具体来说，假设图模型所对应的变量集 x = {x1, x2, ..., xn} 能分为 x_E 和 x_F 两个不相交的变量集，推断问题的目标就是计算边际概率 P( x_E ) 或条件概率 P( x_F | x_E )，由条件概率定义有如下公式：

其中联合概率 P(x_E, x_F) 可基于概率图模型获得，因此，推断问题的关键就是如何高效的计算边际分布，即上式的分母部分。

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

［1］变量消去

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

我们以下图有向图模型为例来介绍其工作流程：

假定推断目标为边际概率 P( x5 )，显然为了完成此目标，只需通过加法消去变量｛x1, x2, x3, x4｝，即：

其中 mij(xj) 是求加过程的中间结果，下标 i 表示此项是对 xi 求加的结果，下标 j 表示此项中剩下的其它变量。显然 mij(xj) 是 xj 的函数。

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

变量消去法有一个明显的缺点，那就是若需计算多个边际概率，会造成大量冗余计算。下一小节的信念传播算法就很好的解决了这个问题。

［2］信念传播（Belief Propogation）

信念传播算法将变量消去法中的求和操作看作一个消息传递的过程，较好的解决了求解多个边际分布时的重复计算问题。

在变量消去算法的计算过程中，通过求和操作消去变量的过程 mij(xj)，我们可以看作是从 xi 向 xj 传递消息的过程。通过观测不难发现，每次消息的传递操作仅与变量 x 的邻接结点直接相关，换言之，消息传递相关的计算被限制在图的局部进行。

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

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

指定一个根结点，从所有叶结点向根结点传递信息，直到所有根结点收到所有邻接结点的信息

从根结点向叶结点传递消息，直到所有叶结点都接收道消息

例如在下边的图结构中，我们令 x1 为根结点，则 x4 与 x5 为叶结点，则以上两步的消息传递过程如下。此时图的每条边上都有方向不同的两条信息，基于这些消息以及上一小节的公式，即可得到所有变量的边际概率

5）近似推断

像在上一节中介绍的，为了节省计算开销，在现实生活中近似推断更为常用。近似推断方法大致可分为两大类：第一类是采样，通过使用随机化方法完成近似；第二类是使用确定性近似完成近似推断，典型代表是变分推断

［1］MCMC采样（Markov Chain Monte Carlo Sampling，马尔可夫链蒙特卡洛采样）

在很多任务中，我们所关心的其实并非是概率分布本身，而是在该概率分布下某个变量的期望。那么当能通过直接的操作近似逼近这个变量的期望时，我们就不需要大费周章的去推断概率分布了。

简单来说，若已知变量 x 的概率密度函数 p(x)，那么我要要求 y = f(x) 的期望时，我们就不需要去计算出条件概率 P(y|x) 了，只需要计算 f(x) 在多个样本 {x1, x2, x3, ..., xn}上的 f(xi) 的平均值，或者在一定范围取值内的积分。根据大数定理，这种通过大量采样的办法就能获得较高的近似精度。

那么我们关注的问题就从如何求得期望的近似变成要如何高效的获取样本了！

MCMC方法就是概率图模型中最常用的采样技术。对高维多元变量 x，MCMC采样通过构造“平稳分布为 p 的马尔可夫链”来产生样本。

首先，让我们先理解什么是马尔可夫链的平稳状态。直观理解就是，假设在(t-1)时刻，马尔可夫链到达平稳状态，那么其所处的状态尽可能保持稳定。我们假设马尔可夫链的状态转移概率为: T( xi | xj )，表示从状态 xj 转移到状态 xi 的概率，则当马尔可夫链在某个时刻处于平稳状态时，需满足：

这里马尔可夫链状态转移概率的构造至关重要，不同的构造方式将产生不同的MCMC算法。

［2］变分推断（variational inference）

变分推断通过使用已知简单分布来逼近需推断的复杂分布，并通过限制近似分布的类型，从而得到一种局部最优、但具有确定解的近似后验分布。

变分推断使用的近似分布需要具有良好的数值性质，通常是基于连续型变量的概率密度函数来刻画的。

假设有 N 个可观测变量 {x1, x2, ..., xN}，这 N 个变量均依赖于其它变量 z，且 x 与 z 均服从分布参数 θ。那么一般来说，我们根据该概率图模型的推断与学习任务主要是由观测到的变量 x 来估计隐变量 z 和分布参数变量 θ，即求解 p( z | x,θ ) 和 θ

通常我们可以使用极大似然函数和 EM 算法来进行推断，但是在现实任务中，推断的过程可能因为 z 模型复杂而难以进行。此时可借助变分推断，假设隐变量 z 服从分布：q(z) = q1(z1) * q2(z2) * ... * qM(zM)

我们通过使用相对简单或结构更好的的分布 q 去近似 z 的后验分布 p( z | x,θ ) 即能在节省计算开销的情况下得到所要概率分布

6）话题模型（topic model）

话题模型是一族生成式有向图模型，主要用于处理离散型的数据（如文本集合），在信息检索、自然语言处理等领域有广泛应用。

隐狄利克雷模型（Latent Dirichlet Allocation，简称LDA）是话题模型的典型代表。

［1］基本概念

按照由小到大的顺序，话题模型涉及到的以下几个概念：

词（word）：待处理数据的基本离散单元

文档（document）：待处理的数据对象，它由一组词组成

话题（topic）：话题表示一个概念，具体表示为一系列与该概念相关的词，以及它们在该概念下出现的概率

词袋（bag-of-words）：文档的表示方式，将文档中的词不计顺序的存储成一个词的集合

比如在文本处理领域，LDA算法处理的对象是一篇篇文章，不妨假设数据集中包含 K 个话题，T篇文档，文档中的词来自于一个包含 N 个词的词典。文档以词袋的形式表示 W = {w1, w2, ..., wt}，wi表示第 i 篇文档中 N 个词分别的词频；同理 K 个 N 维向量 B = {b1, b2, ..., bk} 用来表示 K 个话题

［2］模型介绍

在现实任务中，我们可以通过统计文档中的词来获得词频向量 W，但我们通常不清楚这组文档都谈论了哪些话题，也不知道每篇文档与哪些话题有关。

狄利克雷模型以生成式模型的角度来看待文档和话题，认为文档的话题分布满足参数为 α 的 K 维狄利克雷分布，话题词频则依赖于参数为 η 的 N 维狄利克雷分布

通过 α 和 η，我们可以分别得到文档的话题分布 Θt 以及话题词频 Bk，由此可得到话题指派 z_tn （z_tn 表示第 t 个文档的第 n 个词所属于的话题分布）以及最终的文档词频 wt

实际上，我们唯一能观测到的变量只有 wt，但是通过极大似然估计以及变分法来进行近似推断，我们能获得参数 α 和 η 的取值。

2. 基础知识

1）狄利克雷函数

狄利克雷函数（英语：dirichlet function）是一个定义在实数范围上、值域不连续的函数。

2）边际分布（marginal distribution）

边际分布是指对无关变量求和或积分的结果。例如对于 (x, y) 构成的联合概率分布中，对于 x 的边际分布为：

P(x) = P{ X < x } = P{ X < x, Y < 正无穷 }

3）大数定理

大数定律(law of large numbers)，是一种描述当试验次数很大时所呈现的概率性质的定律。在随机事件的大量重复出现中，往往呈现几乎必然的规律，这个规律就是大数定律。通俗地说，这个定理就是，在试验不变的条件下，重复试验多次，随机事件的频率近似于它的概率。偶然中包含着某种必然。

3. 总结

1）概率模型是一种将学习任务归结于计算变量的概率分布的描述框架，概率模型的学习即基于训练样本来估计变量的分布。

2）概率图模型是一类用图来表达变量相关关系的概率模型

3）概率图模型根据边的性质不同，大致可分为有向图模型和无向图模型

4）隐马尔可夫模型是结构最简单的一种著名的有向图模型，其每一个节点代表系统所处的状态，且该状态只与其前置状态有关

5）马尔可夫随机场是一种著名的无向图模型，其用图模型来表示属性之间的相互独立性，并且根据马尔可夫性，属性的联合概率可由极大团的势函数的乘积获得

6）条件随机场可以被看成是给定观测值的马尔可夫随机场，其将势函数引入特征函数中来对条件概率进行计算

7）基于概率图模型定义的联合概率分布，我们需要对其中的目标变量或者条件分布进行推断，根据推断方法的不同可分为精确推断，以及近似推断

8）精确推断包括利用乘法对加法的分配律，把多个变量的积的求和问题转换为对部分变量交替进行求积和求和的问题的变量消去法，以及将变量消去法中的求和操作看作一个消息传递的过程，较好的解决了求解多个边际分布时的重复计算问题的信念传播法

9）近似推断包括采样以及变分推断两种方法，前者是通过采样来对目标分布的期望进行近似，后者是通过将目标变量的分布分解为更为简单或者结构更好的分布的乘积来进行近似

10）话题模型是一个具体的用在自然语言处理上的有向图模型，通过使用极大似然估计法以及各种近似推断方法来获得训练样本集的模型分布