深入浅出：隐马尔科夫模型

点击蓝字

关注我们

#TSer#

时间序列知识整理系列，持续更新中 ⛳️

赶紧后台回复"讨论"加入讨论组交流吧 ?

隐马尔科夫模型（Hidden Markov Model，HMM），和回归、分类那些处理相互独立的样本数据的模型不同，它用于处理时间序列数据，即样本之间有时间序列关系的数据。从这一点来说，它和卡尔曼滤波算法很像。事实上，HMM和卡尔曼滤波的算法本质是一模一样的，只不过HMM要假设隐藏变量是离散的，而卡尔曼滤波假设隐藏变量是连续的。隐藏变量是HMM里的关键概念之一，可以理解为无法直接观测到的变量，即HMM中Hidden一词的含义；与之相对的是观测变量，即可以直接观测到的变量；HMM的能力在于能够根据给出的观测变量序列，估计对应的隐藏变量序列是什么，并对未来的观测变量做预测。

举个例子，输入法。就拿中文拼音输入法来说，给你一段从键盘输入的字符，你需要从中推测出用户输入的文字是什么，如果有多种可能的文字，你甚至需要给出每段候选文字的概率是多少。这里输入字符序列就是观测变量，要推断的输入文字就是隐藏变量。我们知道，对单个文字而言，与之对应的字符输入序列是有统计规律的。比如，我要打“张”这个字，一般可能的输入是“zh”、“zhang”、“zhagn”等。另一方面，和语音识别的例子一样，文字与文字之间也是有一些转移规律的。利用单个文字的输入统计规律、以及文字与文字之间的转移规律这两方面的信息，从一段字符序列推断对应的输入文字也不是什么难事了。对HMM而言，一般观测序列越长，推断越准。比如，我想输入“从一段字符序列推断对应的输入文字”这句话，当我输入“cong”时，输入法给我的候选字很多，

因为输入信息太少，模型不知道我要输入的到底是什么，只能按照可能性大小对很多候选字排了个序后给我。当我继续输入“congyiduan”时，

候选文字序列已经少了很多了，但还有三个候选，其中第三个候选的概率我相信背后的模型已经给的很低了，因为从统计上讲，这三个字几乎不会同时出现。当我继续输入“congyiduanzifu”时，

只剩下两个候选，但是如果没有上下文信息，还是不太好确定用户到底想输入的是哪个。当我继续输入“congyiduanzifuxulie”时，

输入法已经可以准确地推断出我要输入的文字是什么了。因为当继续输入“xulie”时，根据前文信息，在“xulie”之前最可能出现的文字是“字符”而不是“支付”，这样就将最优匹配筛选出来了。

其实就是，观测序列越长，模型能得到的信息越多，自然推断的准确性就越高。除了推断隐藏序列，HMM还可用作预测，即给定一段观测序列，预测下一个隐藏序列是什么，拿输入法来说，这就是所谓的联想输入法。不仅如此，HMM还能进一步推断下一个甚至未来多个观测值是什么。

本文开始将和大家聊聊，隐马尔科夫模型的深度逻辑。

马尔科夫模型与HMM

要讲隐马尔科夫模型，需要先从马尔科夫模型讲起。已知N个有序随机变量，根据贝叶斯定理，他们的联合分布可以写成条件分布的连乘积：

（1）

马尔科夫模型是指，假设序列中的任何一个随机变量在给定它的前一个变量时的分布与更早的变量无关，即：

（2）

在此假设下，N个随机变量的联合分布可以简化为：

（3）

该分布通过概率图表达就清楚多了，如下图为一个一阶马尔科夫链，根据概率图模型中的d分离概念，可以很容易确认马尔科夫性。

一阶马尔科夫性只能表达当前变量与前一个变量的关系，然而很多实际问题往往没有这么简单。为了表达当前变量与更早的变量之间的关系，可以引入高阶马尔科夫性。概括来说，M阶马尔科夫性是指当前随机变量在给定其之前的M个变量时与更早的变量无关，用公式表达就是：

（4）

高阶马尔科夫性虽然达到了关联当前变量与更早的变量的目的，但有一个问题就是指数爆炸问题，即参数数量随着M的增大呈指数增长。那么，有没有一种方法即能将当前变量与更早的变量关联起来，又不需要那么多参数呢？当然，这里有一种非常强大的手段，即引入隐变量，这是机器学习中用简单的基础部件表达丰富的模型的有力手段。这里如果假设隐变量构成一阶马尔科夫模型，而每个观测变量与一个隐变量关联，则可以得到一类模型的基础结构，即状态空间模型。如下图，Z为隐藏变量，X为观测变量.

该类模型的关键是隐藏变量之间满足如下条件独立性：

这类模型的联合分布可以表示为：

（5）

可见，看似很复杂的模型被分解成了简单的三部分，这三者分别叫做初始概率模型、转移概率模型和发射概率模型，对状态空间模型建模实际就是对这三者进行建模。而且此时观测变量之间不再具有任何马尔科夫性，这样就将一个变量与其之前所有的变量关联起来了。这就是隐变量的能力。

当X为离散变量时，该状态空间模型即为隐马尔科夫模型。现在可以解释一下“隐马尔科夫”这个名字的含义了。“马尔科夫”自然是表示随机变量之间构成一个马尔科夫链了。而“隐”是指我们要推测的变量是未知的、隐藏的。正是这些隐藏的变量构成了马尔科夫链，所以就叫“隐马尔科夫”了。

模型表示

以下分别介绍HMM中初始概率模型、转移概率模型和发射概率模型的表示。

首先说转移概率模型。由于Z是离散的，假设有K个状态，则可以表示为一个K维变量，每一维对应一个状态，其中每一维只能取0或1两个值，并且有且仅有一维的值为1。因此，对于分布可以用一张表、或矩阵表示，其中第j行 、第k列元素表示在已知Z_n-1为第j个状态的条件下，取第k个状态的条件概率 。由于这些元素表示概率值，因此可以构成矩阵。这样，我们就可以将条件分布写成：

（6）

其次说初始概率模型：由于第一个隐藏变量Z_1没有父节点，因此它的分布可以用一个概率向量π表示，其中第k个元素表示π取第k个状态的概率。这样，我们可以将初始概率分布写成：

（7）

最后说发射概率模型：发射概率可以表示为：

（8）

这里只定义了发射概率的基本形式，不限制其具体形式。事实上，HMM的发射概率的具体形式可以有很多种， 当观测变量也是离散的时，发射概率可以表示为一张类似转移概率的二维表。如果观测变量为连续的，则发射概率可以是高斯或混合高斯模型，甚至是神经网络模型。

有了以上初始概率模型、转移概率模型、发射概率模型的表示，那么所有变量的联合分布可以表示为：

（9）

任何机器学习模型都有学习（Learning）和推理（Inference）两部分。学习是为了从一堆已知样本中得到模型的参数，推理是为了拿学习好的模型对未知的事件进行预测，这也是我们建模的最终目的。

学习

HMM的参数学习采用最大似然法。在不知道其它更多信息的情况下，最大似然法是最通用也最合理的方法了，这也是大部分概率模型采用的学习方法。最大似然法的基本思想其实很简单、很直接，“已发生的即是概率最大的”，也就是说，它的目的是找到一组参数，使得在这组参数下，已观测到的事件或数据的联合概率最大。这一点从最大似然法的命名也好理解，“似”即“像”，表示概率；“然”即“这样”，表示已观测到的数据。“最大似然”即找到一组参数，使得“像这样”的概率最大。

然而与其它一些模型不同，用最大似然法求解HMM参数学习问题时，由于有隐变量的存在，无法直接求得参数的解析解，必须采用EM（Expectation Maximization）算法，逐步迭代直至收敛从而求得模型参数。值得庆幸的是，在实际应用中，EM算法收敛速度很快，基本经过一二十轮迭代、甚至几轮迭代即可达到收敛。

EM算法分E步和M步两部分：在E步，假设已知模型参数，从而求得隐变量的后验分布；在M步，计算全数据的对数似然的在此后验分布下的期望的最大值，此即算法名称Expectation Maximization的来由。该期望是一个关于模型参数的函数，其定义为

（10）

通过最大化该期望函数，可以得到参数的解，然后以此解作为新的参数带入E步，如此迭代直至最后收敛即可。

结合前面对HMM初始概率模型、转移概率模型和发射概率模型的表示，全数据的对数似然可以表示为

为了后面公式的简介，先引入两个记号γ和ξ分别表示Z_n的后验分布以及Z_n和Z_n-1的联合后验分布：

（12）

由于0-1二值变量的值取1的概率等于它的期望，所以：

M步

将式（11）右边的三部分依次带入式（10）中，其中第一部分带入的结果为：

（14）

第二部分带入的结果为：

（15）

第三部分带入的结果为：

（16）

综上，

对参数γ和ξ求极值比较容易，运用拉格朗日法可得：

对参数π和A初始值的选取只要保证满足归一化条件、并且值为非0即可。因为如果初始值为0则在以后每步迭代该值始终为0，无法更新。

E步

该步要求γ和ξ，这部分会涉及到更多的公式推导，不过推导过程并不复杂，主要利用了HMM中的一些条件独立特性。因此在此有必要先将这些条件独立等式列出来。由于HMM也是概率图模型（Probabilistic Graphic Model，PGM）的一种特例，PGM中判断条件独立性最方便的莫过于利用d分离（d-separation）的概念了，在此做简单介绍。

在概率图中有三种基本的连接方式，分别是顺连、分连和汇连，如下图所示，d分离正是针对这三种连接情况的条件独立性判断准则。

• 顺连是指箭头从一边进入连接节点，并从另一边分出。当已知连接节点c时，随机变量a和b相互独立。可以理解为当已知c时，从a到b的通路被阻塞，不确定性无法从a传递到b，因此a和b相互独立。
• 分连是指两个箭头同时从连接节点分出，指向其他变量。同顺连的情况类似，当已知连接节点c时，a和b也相互独立。
• 汇连是指两个箭头同时从其它变量指向连接节点。与顺连和分连的情况不同，在汇连的情况下，如果已知连接节点c，a和b不相互独立。相反，在c未知时，a和b才相互独立。

在此，就可以利用d分离的概念给出HMM中的一些条件独立式。为了方便对照着图形判断条件独立性，在此再次贴出HMM的概率图表示，如下图：

（21）

因为当已知Z_n时，从(x1...xn)到(xn+1...xN)之间通路被阻塞，因此两组变量条件独立。

（22）

同理，

（23）

利用的同样的道理，还可以推出以下条件独立式，不再赘述：

当一切准备工作做好之后，可以开始计算 γ和ξ了。根据γ的定义，利用贝叶斯定理则有：

（31）

利用条件独立式(21)和贝叶斯定理，进一步变形为：

（32）

其中，定义了

利用条件独立式（22）和（23）：

（35）

根据α的定义，可以得到关于α的递推式为：

（36）

由于需要从前往后依次计算每一个α，因此该过程又称为前向计算。根据定义，前向计算的初始条件为：

（37）

同样，利用条件独立式（24）（25）：

根据β的定义，可以得到关于β的递推式为：

（39）

与求α的过程正好相反。该过程又称为后向计算。

由于采用的是最大似然法，因此在EM算法的迭代过程中往往需要观测似然值的变化，以似然值不再增加作为迭代停止的条件，所以，能够计算似然值也非常重要。根据式（32），等式的左侧为Zn的条件概率，对Zn求和结果为1，因此似然值

（40）

由于对任意n计算结果相同，不妨令n=N，可得

（41）

同样，利用条件独立式（26）：

（42）

因此，在完成前向计算和后向计算之后，ξ可以直接得到。至此，γ和ξ均已求出。

推理

给定一组观测序列，根据以上描述的学习方法即可求出HMM的参数。然而大部分时候，求得模型的参数还不够，我们的最终目的往往是根据学习到的模型回答一些关心的问题，即推理。在HMM中，有两个问题是我们比较关心的，第一个是预测问题，即给定一组观测变量，要预测下一个观测变量，该问题利用HMM的条件独立式和前述前向计算的结果可直接得到；第二个是最大可能隐藏序列问题，即给定一组观测序列，如何找到与之对应的可能性最大的隐藏序列，该问题用维特比（Viterbi）算法可以高效求出。

预测问题

该问题要回答条件概率分布是多少。利用条件独立式（27）（28）：

首先利用前向计算逐步递归计算到α，然后依照上式分别对ZN和ZN+1求和，其中求和结果又可以作为中间结果计算出α，从而可以进一步预测。