一文搞懂HMM(隐马尔可夫模型)

转载 2019-09-30 11:52  阅读 75 次 评论 0 条

什么是熵(Entropy)

简单来说,熵是表示物质系统状态的一种度量,用它老表征系统的无序程度。熵越大,系统越无序,意味着系统结构和运动的不确定和无规则;反之,,熵越小,系统越有序,意味着具有确定和有规则的运动状态。熵的中文意思是热量被温度除的商。负熵是物质系统有序化,组织化,复杂化状态的一种度量。

熵最早来原于物理学. 德国物理学家鲁道夫·克劳修斯首次提出熵的概念,用来表示任何一种能量在空间中分布的均匀程度,能量分布得越均匀,熵就越大。

  1. 一滴墨水滴在清水中,部成了一杯淡蓝色溶液
  2. 热水晾在空气中,热量会传到空气中,最后使得温度一致

更多的一些生活中的例子:

  1. 熵力的一个例子是耳机线,我们将耳机线整理好放进口袋,下次再拿出来已经乱了。让耳机线乱掉的看不见的“力”就是熵力,耳机线喜欢变成更混乱。
  2. 熵力另一个具体的例子是弹性力。一根弹簧的力,就是熵力。 胡克定律其实也是一种熵力的表现。
  3. 万有引力也是熵力的一种(热烈讨论的话题)。
  4. 浑水澄清[1]

image

于是从微观看,熵就表现了这个系统所处状态的不确定性程度。香农,描述一个信息系统的时候就借用了熵的概念,这里熵表示的是这个信息系统的平均信息量(平均不确定程度)

最大熵模型

我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里,这样可以降低风险。在信息处理中,这个原理同样适用。在数学上,这个原理称为最大熵原理(the maximum entropy principle)。

让我们看一个拼音转汉字的简单的例子。假如输入的拼音是"wang-xiao-bo",利用语言模型,根据有限的上下文(比如前两个词),我们能给出两个最常见的名字“王小波”和“王晓波 ”。至于要唯一确定是哪个名字就难了,即使利用较长的上下文也做不到。当然,我们知道如果通篇文章是介绍文学的,作家王小波的可能性就较大;而在讨论两岸关系时,台湾学者王晓波的可能性会较大。在上面的例子中,我们只需要综合两类不同的信息,即主题信息和上下文信息。虽然有不少凑合的办法,比如:分成成千上万种的不同的主题单独处理,或者对每种信息的作用加权平均等等,但都不能准确而圆满地解决问题,这样好比以前我们谈到的行星运动模型中的小圆套大圆打补丁的方法。在很多应用中,我们需要综合几十甚至上百种不同的信息,这种小圆套大圆的方法显然行不通。

数学上最漂亮的办法是最大熵(maximum entropy)模型,它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥,但是它的原理很简单,我们每天都在用。说白了,就是要保留全部的不确定性,将风险降到最小。

回到我们刚才谈到的拼音转汉字的例子,我们已知两种信息,第一,根据语言模型,wangxiao-bo可以被转换成王晓波和王小波;第二,根据主题,王小波是作家,《黄金时代》的作者等等,而王晓波是台湾研究两岸关系的学者。因此,我们就可以建立一个最大熵模型,同时满足这两种信息。现在的问题是,这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨(Csiszar)证明,对任何一组不自相矛盾的信息,这个最大熵模型不仅存在,而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。下面公式是根据上下文(前两个词)和主题预测下一个词的最大熵模型,其中 w3 是要预测的词(王晓波或者王小波)w1 和 w2 是它的前两个字(比如说它们分别是“出版”,和“”),也就是其上下文的一个大致估计,subject 表示主题。

640_wx_fmt=png&tp=webp&wxfrom=5.webp

我们看到,在上面的公式中,有几个参数 lambda 和 Z ,他们需要通过观测数据训练出来。最大熵模型在形式上是最漂亮的统计模型,而在实现上是最复杂的模型之一。

我们上次谈到用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答,就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式,现在只需要确定指数函数的参数就可以了,这个过程称为模型的训练。

最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂,大致可以概括为以下几个步骤:
1. 假定第零次迭代的初始模型为等概率的均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则,将它们便大。
3. 重复步骤 2 直到收敛。

GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是,这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨(Csiszar)解释清楚的,因此,人们在谈到这个算法时,总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长,需要迭代很多次才能收敛,而且不太稳定,即使在 64 位计算机上都会出现溢出。因此,在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。
八十年代,很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进,提出了改进迭代算法 IIS(improved iterative scaling)。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此,在当时也只有 IBM 有条件是用最大熵模型。

由于最大熵模型在数学上十分完美,对科学家们有很大的诱惑力,因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似,最大熵模型就变得不完美了,结果可想而知,比打补丁的凑合的方法也好不了多少。于是,不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的,是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似,而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题,比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性(名词、动词和形容词等)、句子成分(主谓宾)通过最大熵模型结合起来,做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统,至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中,又看到了用最大熵模型解决复杂的文字信息处理的希望。

但是,最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天,我对我的导师说,我发现一种数学变换,可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时,他没有找出我的推导中的任何破绽,接着他又回去想了两天,然后告诉我我的算法是对的。从此,我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后,为了训练一个包含上下文信息,主题信息和语法信息的文法模型(language model),我并行使用了20 台当时最快的 SUN 工作站,仍然计算了三个月。由此可见最大熵模型的复杂的一面。

最大熵模型,可以说是集简与繁于一体,形式简单,实现复杂。值得一提的是,在Google的很多产品中,比如机器翻译,都直接或间接地用到了最大熵模型。
讲到这里,读者也许会问,当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗?他们在九十年代初贾里尼克离开 IBM 后,也退出了学术界,而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大,但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道,决定股票涨落的因素可能有几十甚至上百种,而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮垂兄弟等科学家在那里,用于最大熵模型和其他一些先进的数学工具对股票预测,获得了巨大的成功。从该基金 1988 年创立至今,它的净回报率高达平均每年 34%。也就是说,如果 1988 年你在该基金投入一块钱,今天你能得到 200 块钱。这个业绩,远远超过股神巴菲特的旗舰公司伯克夏哈撒韦(Berkshire Hathaway)。同期,伯克夏哈撒韦的总回报是 16 倍。
值得一提的是,信息处理的很多数学手段,包括隐含马尔可夫模型、子波变换、贝叶斯网络等等,在华尔街多有直接的应用。由此可见,数学模型的作用。

HMM(隐马尔可夫模型

隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。

是在被建模的系统被认为是一个马尔可夫过程与未观测到的(隐藏的)的状态的统计马尔可夫模型。

下面用一个简单的例子来阐述:

假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子(称这个骰子为D6),6个面,每个面(1,2,3,4,5,6)出现的概率是1/6。第二个骰子是个四面体(称这个骰子为D4),每个面(1,2,3,4)出现的概率是1/4。第三个骰子有八个面(称这个骰子为D8),每个面(1,2,3,4,5,6,7,8)出现的概率是1/8。

image

假设我们开始掷骰子,我们先从三个骰子里挑一个,挑到每一个骰子的概率都是1/3。然后我们掷骰子,得到一个数字,1,2,3,4,5,6,7,8中的一个。不停的重复上述过程,我们会得到一串数字,每个数字都是1,2,3,4,5,6,7,8中的一个。例如我们可能得到这么一串数字(掷骰子10次):1 6 3 5 2 7 3 5 2 4

这串数字叫做可见状态链。但是在隐马尔可夫模型中,我们不仅仅有这么一串可见状态链,还有一串隐含状态链。在这个例子里,这串隐含状态链就是你用的骰子的序列。比如,隐含状态链有可能是:D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

一般来说,HMM中说到的马尔可夫链其实是指隐含状态链,因为隐含状态(骰子)之间存在转换概率(transition probability)。在我们这个例子里,D6的下一个状态是D4,D6,D8的概率都是1/3。D4,D8的下一个状态是D4,D6,D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚,但是我们其实是可以随意设定转换概率的。比如,我们可以这样定义,D6后面不能接D4,D6后面是D6的概率是0.9,是D8的概率是0.1。这样就是一个新的HMM。

同样的,尽管可见状态之间没有转换概率,但是隐含状态和可见状态之间有一个概率叫做输出概率(emission probability)。就我们的例子来说,六面骰(D6)产生1的输出概率是1/6。产生2,3,4,5,6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如,我有一个被赌场动过手脚的六面骰子,掷出来是1的概率更大,是1/2,掷出来是2,3,4,5,6的概率是1/10。

image

image

其实对于HMM来说,如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率,做模拟是相当容易的。但是应用HMM模型时候呢,往往是缺失了一部分信息的,有时候你知道骰子有几种,每种骰子是什么,但是不知道掷出来的骰子序列;有时候你只是看到了很多次掷骰子的结果,剩下的什么都不知道。如果应用算法去估计这些缺失的信息,就成了一个很重要的问题。这些算法我会在下面详细讲。
××××××××××××××××××××××××××××××××××××××××××××××××××××××××
如果你只想看一个简单易懂的例子,就不需要往下看了。
××××××××××××××××××××××××××××××××××××××××××××××××××××××××

说两句废话,答主认为呢,要了解一个算法,要做到以下两点:会其意,知其形。答主回答的,其实主要是第一点。但是这一点呢,恰恰是最重要,而且很多书上不会讲的。正如你在追一个姑娘,姑娘对你说“你什么都没做错!”你要是只看姑娘的表达形式呢,认为自己什么都没做错,显然就理解错了。你要理会姑娘的意思,“你赶紧给我道歉!”这样当你看到对应的表达形式呢,赶紧认错,跪地求饶就对了。数学也是一样,你要是不理解意思,光看公式,往往一头雾水。不过呢,数学的表达顶多也就是晦涩了点,姑娘的表达呢,有的时候就完全和本意相反。所以答主一直认为理解姑娘比理解数学难多了。

回到正题,和HMM模型相关的算法主要分为三类,分别解决三种问题:
      1)知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道每次掷出来的都是哪种骰子(隐含状态链)。
这个问题呢,在语音识别领域呢,叫做解码问题。这个问题其实有两种解法,会给出两个不同的答案。每个答案都对,只不过这些答案的意义不一样。第一种解法求最大似然状态路径,说通俗点呢,就是我求一串骰子序列,这串骰子序列产生观测结果的概率最大。第二种解法呢,就不是求一组骰子序列了,而是求每次掷出的骰子分别是某种骰子的概率。比如说我看到结果后,我可以求得第一次掷骰子是D4的概率是0.5,D6的概率是0.3,D8的概率是0.2.第一种解法我会在下面说到,但是第二种解法我就不写在这里了,如果大家有兴趣,我们另开一个问题继续写吧。

2)还是知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道掷出这个结果的概率。
看似这个问题意义不大,因为你掷出来的结果很多时候都对应了一个比较大的概率。问这个问题的目的呢,其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率,那么就说明我们已知的模型很有可能是错的,有人偷偷把我们的骰子給换了。

3)知道骰子有几种(隐含状态数量),不知道每种骰子是什么(转换概率),观测到很多次掷骰子的结果(可见状态链),我想反推出每种骰子是什么(转换概率)
这个问题很重要,因为这是最常见的情况。很多时候我们只有可见结果,不知道HMM模型里的参数,我们需要从可见结果估计出这些参数,这是建模的一个必要步骤。

问题阐述完了,下面就开始说解法。(0号问题在上面没有提,只是作为解决上述问题的一个辅助)

0.一个简单问题

其实这个问题实用价值不高。由于对下面较难的问题有帮助,所以先在这里提一下。

知道骰子有几种,每种骰子是什么,每次掷的都是什么骰子,根据掷骰子掷出的结果,求产生这个结果的概率。

image

解法无非就是概率相乘:


1.看见不可见的,破解骰子序列

这里我说的是第一种解法,解最大似然路径问题。

举例来说,我知道我有三个骰子,六面骰,四面骰,八面骰。我也知道我掷了十次的结果(1 6 3 5 2 7 3 5 2 4),我不知道每次用了那种骰子,我想知道最有可能的骰子序列。

其实最简单而暴力的方法就是穷举所有可能的骰子序列,然后依照第零个问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长,当然可行。如果长的话,穷举的数量太大,就很难完成了。

另外一种很有名的算法叫做Viterbi algorithm. 要理解这个算法,我们先看几个简单的列子。

首先,如果我们只掷一次骰子:

image

看到结果为1.对应的最大概率骰子序列就是D4,因为D4产生1的概率是1/4,高于1/6和1/8.

把这个情况拓展,我们掷两次骰子:

image

结果为1,6.这时问题变得复杂起来,我们要计算三个值,分别是第二个骰子是D6,D4,D8的最大概率。显然,要取到最大概率,第一个骰子必须为D4。这时,第二个骰子取到D6的最大概率是

image

同样的,我们可以计算第二个骰子是D4或D8时的最大概率。我们发现,第二个骰子取到D6的概率最大。而使这个概率最大时,第一个骰子为D4。所以最大概率骰子序列就是D4 D6。

继续拓展,我们掷三次骰子:

image

同样,我们计算第三个骰子分别是D6,D4,D8的最大概率。我们再次发现,要取到最大概率,第二个骰子必须为D6。这时,第三个骰子取到D4的最大概率是

image

同上,我们可以计算第三个骰子是D6或D8时的最大概率。我们发现,第三个骰子取到D4的概率最大。而使这个概率最大时,第二个骰子为D6,第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。

写到这里,大家应该看出点规律了。既然掷骰子一二三次可以算,掷多少次都可以以此类推。我们发现,我们要求最大概率骰子序列时要做这么几件事情。首先,不管序列多长,要从序列长度为1算起,算序列长度为1时取到每个骰子的最大概率。然后,逐渐增加长度,每增加一次长度,重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了,重新计算的话其实不难。当我们算到最后一位时,就知道最后一位是哪个骰子的概率最大了。然后,我们要把对应这个最大概率的序列从后往前推出来。

2.谁动了我的骰子?

比如说你怀疑自己的六面骰被赌场动过手脚了,有可能被换成另一种六面骰,这种六面骰掷出来是1的概率更大,是1/2,掷出来是2,3,4,5,6的概率是1/10。你怎么办么?答案很简单,算一算正常的三个骰子掷出一段序列的概率,再算一算不正常的六面骰和另外两个正常骰子掷出这段序列的概率。如果前者比后者小,你就要小心了。

比如说掷骰子的结果是:

image

要算用正常的三个骰子掷出这个结果的概率,其实就是将所有可能情况的概率进行加和计算。同样,简单而暴力的方法就是把穷举所有的骰子序列,还是计算每个骰子序列对应的概率,但是这回,我们不挑最大值了,而是把所有算出来的概率相加,得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列(马尔可夫链)。

我们会应用一个和前一个问题类似的解法,只不过前一个问题关心的是概率最大值,这个问题关心的是概率之和。解决这个问题的算法叫做前向算法(forward algorithm)。

首先,如果我们只掷一次骰子:

image

看到结果为1.产生这个结果的总概率可以按照如下计算,总概率为0.18:

image

把这个情况拓展,我们掷两次骰子:

image

看到结果为1,6.产生这个结果的总概率可以按照如下计算,总概率为0.05:

image

继续拓展,我们掷三次骰子:

image

看到结果为1,6,3.产生这个结果的总概率可以按照如下计算,总概率为0.03:

image

同样的,我们一步一步的算,有多长算多长,再长的马尔可夫链总能算出来的。用同样的方法,也可以算出不正常的六面骰和另外两个正常骰子掷出这段序列的概率,然后我们比较一下这两个概率大小,就能知道你的骰子是不是被人换了。

Viterbi algorithm

HMM(隐马尔可夫模型)是用来描述隐含未知参数的统计模型,举一个经典的例子:一个东京的朋友每天根据天气{下雨,天晴}决定当天的活动{公园散步,购物,清理房间}中的一种,我每天只能在twitter上看到她发的推“啊,我前天公园散步、昨天购物、今天清理房间了!”,那么我可以根据她发的推特推断东京这三天的天气。在这个例子里,显状态是活动,隐状态是天气。

任何一个HMM都可以通过下列五元组来描述:

:param obs:观测序列
:param states:隐状态
:param start_p:初始概率(隐状态)
:param trans_p:转移概率(隐状态)
:param emit_p: 发射概率 (隐状态表现为显状态的概率)

6cbb8645gw1egs40a3bpmj208n09574o

伪码如下:

states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}

求解最可能的天气

求解最可能的隐状态序列是HMM的三个典型问题之一,通常用维特比算法解决。维特比算法就是求解HMM上的最短路径(-log(prob),也即是最大概率)的算法。

稍微用中文讲讲思路,很明显,第一天天晴还是下雨可以算出来:

  1. 定义V[时间][今天天气] = 概率,注意今天天气指的是,前几天的天气都确定下来了(概率最大)今天天气是X的概率,这里的概率就是一个累乘的概率了。
  2.     因为第一天我的朋友去散步了,所以第一天下雨的概率V[第一天][下雨] = 初始概率[下雨] * 发射概率[下雨][散步] = 0.6 * 0.1 = 0.06,同理可得V[第一天][天晴] = 0.24 。从直觉上来看,因为第一天朋友出门了,她一般喜欢在天晴的时候散步,所以第一天天晴的概率比较大,数字与直觉统一了。
  3. 从第二天开始,对于每种天气Y,都有前一天天气是X的概率 * X转移到Y的概率 * Y天气下朋友进行这天这种活动的概率。因为前一天天气X有两种可能,所以Y的概率有两个,选取其中较大一个作为V[第二天][天气Y]的概率,同时将今天的天气加入到结果序列中
  4. 比较V[最后一天][下雨]和[最后一天][天晴]的概率,找出较大的哪一个对应的序列,就是最终结果。

算法的代码可以在github上看到,地址为:

https://github.com/hankcs/Viterbi

运行完成后根据Viterbi得到结果:

Sunny Rainy Rainy

Viterbi被广泛应用到分词,词性标注等应用场景。


1 隐马尔可夫模型HMM

隐马尔科夫模型(Hidden Markov Model,以下简称HMM)是比较经典的机器学习模型了,它在语言识别,自然语言处理,模式识别等领域得到广泛的应用。

当然,随着目前深度学习的崛起,尤其是RNNLSTM等神经网络序列模型的火热,HMM的地位有所下降。

但是作为一个经典的模型,学习HMM的模型和对应算法,对我们解决问题建模的能力提高以及算法思路的拓展还是很好的。

1.1 什么样的问题需要HMM模型

首先我们来看看什么样的问题解决可以用HMM模型。

使用HMM模型时我们的问题一般有这两个特征:

1)我们的问题是基于序列的,比如时间序列,或者状态序列。

2)我们的问题中有两类数据,一类序列数据是可以观测到的,即观测序列;而另一类数据是不能观察到的,即隐藏状态序列,简称状态序列。

有了这两个特征,那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如:我现在在打字写博客,我在键盘上敲出来的一系列字符就是观测序列,而我实际想写的一段话就是隐藏序列,输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话,并把最可能的词语放在最前面让我选择,这就可以看做一个HMM模型了。再举一个,我在和你说话,我发出的一串连续的声音就是观测序列,而我实际要表达的一段话就是状态序列,你大脑的任务,就是从这一串连续的声音中判断出我最可能要表达的话的内容。

从这些例子中,我们可以发现,HMM模型可以无处不在。但是上面的描述还不精确,下面我们用精确的数学符号来表述我们的HMM模型。

1.2 HMM模型的定义

对于HMM模型,首先我们假设Q是所有可能的隐藏状态的集合,V是所有可能的观测状态的集合,即:

其中,N是可能的隐藏状态数,M是所有的可能的观察状态数。

对于一个长度为 \(O\) 是对应的观察序列,即:

HMM模型做了两个很重要的假设如下:

1) 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态。当然这样假设有点极端,因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态,可能是前两个或者是前三个。但是这样假设的好处就是模型简单,便于求解。如果在时刻 \(a_{ij}\) 可以表示为:

这样 \(A\) :

2) 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态,这也是一个为了简化模型的假设。如果在时刻 \(b_{j}(k)\) 满足:

这样 \(B\) :

除此之外,我们需要一组在时刻 \(\Pi\) :

一个HMM模型,可以由隐藏状态初始概率分布 \(\lambda=(A,B,\Pi)\)

1.3 一个HMM模型实例

下面我们用一个简单的实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型,例子来源于李航的《统计学习方法》。

假设我们有3个盒子,每个盒子里都有红色和白色两种球,这三个盒子里球的数量分别是:

按照下面的方法从盒子里抽球,开始的时候,从第一个盒子抽球的概率是0.2,从第二个盒子抽球的概率是0.4,从第三个盒子抽球的概率是0.4。以这个概率抽一次球后,将球放回。然后从当前盒子转移到下一个盒子进行抽球。

规则是:如果当前抽球的盒子是第一个盒子,则以0.5的概率仍然留在第一个盒子继续抽球,以0.2的概率去第二个盒子抽球,以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子,则以0.5的概率仍然留在第二个盒子继续抽球,以0.3的概率去第一个盒子抽球,以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子,则以0.5的概率仍然留在第三个盒子继续抽球,以0.2的概率去第一个盒子抽球,以0.3的概率去第二个盒子抽球。如此下去,直到重复三次,得到一个球的颜色的观测序列:

O={红,白,红}

注意在这个过程中,观察者只能看到球的颜色序列,却不能看到球是从哪个盒子里取出的。

那么按照我们上一节HMM模型的定义,我们的观察集合是:

V={红,白},M=2

我们的状态集合是:

Q={盒子1,盒子2,盒子3},N=3

而观察序列和状态序列的长度为3.

初始状态分布为:

\(\Pi=(0.2,0.4,0.4)^{T}\)

状态转移概率分布矩阵为:

观测状态概率矩阵为:

1.4 HMM观测序列的生成

从上一节的例子,我们也可以抽象出HMM观测序列生成的过程。

1.5 HMM模型的三个基本问题

HMM模型一共有三个经典的问题需要解决:

1) 评估观察序列概率。即给定模型 \(P(O|\lambda)\) 。这个问题的求解需要用到前向后向算法,这个问题是HMM模型三个问题中最简单的。

2)模型参数学习问题。即给定观测序列 \(P(O|\lambda)\) 最大。这个问题的求解需要用到基于EM算法的鲍姆-韦尔奇算法, 这个问题是HMM模型三个问题中最复杂的。

3)预测问题,也称为解码问题。即给定模型 \(O=\left\{ o_{1},o_{2},...,o_{T} \right\}\) ,求给定观测序列条件下,最可能出现的对应的状态序列,这个问题的求解需要用到基于动态规划的维特比算法,这个问题是HMM模型三个问题中复杂度居中的算法。

2 前向后向算法评估观察序列概率

2.1 回顾HMM问题一:求观测序列的概率

首先我们回顾下HMM模型的问题一。这个问题是这样的。我们已知HMM模型的参数 \(P(O|\lambda)\) 。

乍一看,这个问题很简单。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率,那么我们是可以暴力求解的。

虽然上述方法有效,但是如果我们的隐藏状态数 \(O(TN^{T})\) 阶的。因此对于一些隐藏状态数极少的模型,我们可以用暴力求解法来得到观测序列出现的概率,但是如果隐藏状态多,则上述算法太耗时,我们需要寻找其他简洁的算法。

前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。

2.2 用前向算法求HMM观测序列的概率

前向后向算法是前向算法和后向算法的统称,这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。

前向算法本质上属于动态规划的算法,也就是我们要通过找到局部状态递推的公式,这样一步步的从子问题的最优解拓展到整个问题的最优解。

在前向算法中,通过定义“前向概率”来定义动态规划的这个局部状态。什么是前向概率呢, 其实定义很简单:定义时刻 \(o_{1},o_{2},...,o_{t}\) 的概率为前向概率。记为:

既然是动态规划,我们就要递推了,假设已经找到了在时刻t时各个隐藏状态的前向概率,现在需要递推出时刻t+1时各个隐藏状态的前向概率。

我们的动态规划从时刻1开始,到时刻 \(o_{1},o_{2},...,o_{T}\) 的概率。

下面总结下前向算法。

从递推公式可以看出,我们的算法时间复杂度是 \(O(TN^{T})\) 少了几个数量级。

2.3 HMM前向算法求解实例

这里用盒子与球的例子来显示前向概率的计算。

首先计算时刻1三个状态的前向概率:

时刻1是红色球,隐藏状态是盒子1的概率为:

隐藏状态是盒子2的概率为:

隐藏状态是盒子3的概率为:

现在可以开始递推了,首先递推时刻2三个状态的前向概率:

时刻2是白色球,隐藏状态是盒子1的概率为:

隐藏状态是盒子2的概率为:

隐藏状态是盒子3的概率为:

继续递推,现在我们递推时刻3三个状态的前向概率:

时刻3是红色球,隐藏状态是盒子1的概率为:

隐藏状态是盒子2的概率为:

隐藏状态是盒子3的概率为:

2.4 用后向算法求HMM观测序列的概率

熟悉了用前向算法求HMM观测序列的概率,现在我们再来看看怎么用后向算法求HMM观测序列的概率。

后向算法和前向算法非常类似,都是用的动态规划,唯一的区别是选择的局部状态不同,后向算法用的是“后向概率”,那么后向概率是如何定义的呢?

这样我们得到了后向概率的递推关系式如下:

现在我们总结下后向算法的流程,注意下和前向算法的相同点和不同点:

此时我们的算法时间复杂度仍然是 \(o(TN^{2})\) 。

2.5 HMM常用概率的计算

利用前向概率和后向概率,可以计算出HMM中单个状态和两个状态的概率公式。

上面这些常用的概率值在求解HMM问题二,即求解HMM模型参数的时候需要用到。

3 鲍姆-韦尔奇算法求解HMM参数

HMM模型参数求解的问题,这个问题在HMM三个问题里算是最复杂的。

3.1 HMM模型参数求解概述

HMM模型参数求解根据已知的条件可以分为两种情况。

可见第一种情况下求解模型还是很简单的。但是在很多时候,我们无法得到HMM样本观察序列对应的隐藏序列,只有 \(\left\{ \left( O_{1} \right),\left( O_{2} \right),...,\left( O_{D} \right)\right\}\) 是已知的,此时我们能不能求出合适的HMM模型参数呢?这就是我们的第二种情况,也是我们本文要讨论的重点。

它的解法最常用的是鲍姆-韦尔奇算法,其实就是基于EM算法的求解,只不过鲍姆-韦尔奇算法出现的时代,EM算法还没有被抽象出来,所以我们本文还是说鲍姆-韦尔奇算法。

3.2 鲍姆-韦尔奇算法原理

鲍姆-韦尔奇算法原理既然使用的就是EM算法的原理,那么我们需要在E步求出联合分布 \(\lambda\) 。接着不停的进行EM迭代,直到模型参数的值收敛为止。

3.3 鲍姆-韦尔奇算法的推导

利用前向概率的定义可得:

现在我们来看看A的迭代公式求法。方法和 \(\Pi\) 的类似。由于A只在最大化函数式中括号里的第二部分出现,而这部分式子可以整理为:

现在我们来看看B的迭代公式求法。方法和 \(\Pi\) 的类似。由于B只在最大化函数式中括号里的第三部分出现,而这部分式子可以整理为:

3.4 鲍姆-韦尔奇算法流程总结

这里我们概括总结下鲍姆-韦尔奇算法的流程。

以上就是鲍姆-韦尔奇算法的整个过程。

4 维特比算法解码隐藏状态序列

HMM模型最后一个问题的求解,即给定模型和观测序列,求给定观测序列条件下,最可能出现的对应的隐藏状态序列。

HMM模型的解码问题最常用的算法是维特比算法,当然也有其他的算法可以求解这个问题。同时维特比算法是一个通用的求序列最短路径的动态规划算法,也可以用于很多其他问题,比如用维特比算法来做分词。

本文关注于用维特比算法来解码HMM的的最可能隐藏状态序列。

4.1 HMM最可能隐藏状态序列求解概述

一个可能的近似解法是求出观测序列 \(\gamma_{t}(i)\) ,这个概率可以通过HMM的前向算法与后向算法计算。这样我们有:

近似算法很简单,但是却不能保证预测的状态序列的整体是最可能的状态序列,因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。

而维特比算法可以将HMM的状态序列作为一个整体来考虑,避免近似算法的问题,下面我们来看看维特比算法进行HMM解码的方法。

4.2 维特比算法概述

维特比算法是一个通用的解码算法,是基于动态规划的求序列最短路径的方法。

既然是动态规划算法,那么就需要找到合适的局部状态,以及局部状态的递推公式。在HMM中,维特比算法定义了两个局部状态用于递推。

4.3 维特比算法流程总结

现在我们来总结下维特比算法的流程:

4.4 HMM维特比算法求解实例

下面用盒子与球的例子来看看HMM维特比算法求解。

按照我们上一节的维特比算法,首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态,此时观测状态为1:

现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态,此时观测状态为2:

4.5 HMM模型维特比算法总结

维特比算法的核心是定义动态规划的局部状态与局部递推公式,这一点在中文分词维特比算法和HMM的维特比算法是相同的,也是维特比算法的精华所在。

维特比算法也是寻找序列最短路径的一个通用方法,和dijkstra算法有些类似,但是dijkstra算法并没有使用动态规划,而是贪心算法。同时维特比算法仅仅局限于求序列最短路径,而dijkstra算法是通用的求最短路径的方法。

5 用 \(HMM\)

5.1 hmmlearn概述

hmmlearn安装很简单,"pip install hmmlearn"即可完成。

hmmlearn实现了三种HMM模型类,按照观测状态是连续状态还是离散状态,可以分为两类。GaussianHMM和GMMHMM是连续观测状态的HMM模型,而MultinomialHMM是离散观测状态的模型,也是我们在HMM原理系列篇里面使用的模型。

对于MultinomialHMM的模型,使用比较简单,"startprob_"参数对应我们的隐藏状态初始分布

\(\Pi\) , "transmat_"对应我们的状态转移矩阵A, "emissionprob_"对应我们的观测状态概率矩阵B。

对于连续观测状态的HMM模型,GaussianHMM类假设观测状态符合高斯分布,而GMMHMM类则假设观测状态符合混合高斯分布。一般情况下我们使用GaussianHMM即高斯分布的观测状态即可。以下对于连续观测状态的HMM模型,我们只讨论GaussianHMM类。

在GaussianHMM类中,"startprob_"参数对应我们的隐藏状态初始分布 \(\Pi\) , "transmat_"对应我们的状态转移矩阵A, 比较特殊的是观测状态概率的表示方法,此时由于观测状态是连续值,我们无法像MultinomialHMM一样直接给出矩阵B。而是采用给出各个隐藏状态对应的观测状态高斯分布的概率密度函数的参数。

如果观测序列是一维的,则观测状态的概率密度函数是一维的普通高斯分布。如果观测序列是

N维的,则隐藏状态对应的观测状态的概率密度函数是N维高斯分布。高斯分布的概率密度函数参数可以用μ表示高斯分布的期望向量,Σ表示高斯分布的协方差矩阵。在GaussianHMM类中,“means”用来表示各个隐藏状态对应的高斯分布期望向量μ形成的矩阵,而“covars”用来表示各个隐藏状态对应的高斯分布协方差矩阵Σ形成的三维张量。

5.2 MultinomialHMM实例

下面我们用我们在原理篇中的例子来使用MultinomialHMM跑一遍。

首先建立HMM的模型:

import numpy as np
from hmmlearn import hmm
 
states = ["box 1", "box 2", "box3"]
n_states = len(states)
 
observations = ["red", "white"]
n_observations = len(observations)
 
start_probability = np.array([0.2, 0.4, 0.4])
 
transition_probability = np.array([
  [0.5, 0.2, 0.3],
  [0.3, 0.5, 0.2],
  [0.2, 0.3, 0.5]
])
 
emission_probability = np.array([
  [0.5, 0.5],
  [0.4, 0.6],
  [0.7, 0.3]
])
 
model = hmm.MultinomialHMM(n_components=n_states)
model.startprob_=start_probability
model.transmat_=transition_probability
model.emissionprob_=emission_probability

现在我们来跑一跑HMM问题三维特比算法的解码过程,使用和原理篇一样的观测序列来解码,代码如下:

输出结果如下:

  • ('The ball picked:', 'red, white, red')
  • ('The hidden box', 'box3, box3, box3')

可以看出,结果和我们原理篇中的手动计算的结果是一样的。

也可以使用predict函数,结果也是一样的,代码如下:

大家可以跑一下,看看结果是否和decode函数相同。

现在我们再来看看求HMM问题一的观测序列的概率的问题,代码如下:

输出结果是:

-2.03854530992

要注意的是score函数返回的是以自然对数为底的对数概率值,我们在HMM问题一中手动计算的结果是未取对数的原始概率是0.13022。对比一下:

现在我们再看看HMM问题二,求解模型参数的问题。由于鲍姆-韦尔奇算法是基于EM算法的近似算法,所以我们需要多跑几次,比如下面我们跑三次,选择一个比较优的模型参数,代码如下:

结果这里就略去了,最终我们会选择分数最高的模型参数。

以上就是用MultinomialHMM解决HMM模型三个问题的方法。

5.3 GaussianHMM实例

下面我们再给一个GaussianHMM的实例,这个实例中,我们的观测状态是二维的,而隐藏状态有4个。因此我们的“means”参数是4×2的矩阵,而“covars”参数是4×2×2的张量。

建立模型如下:

注意上面有个参数covariance_type,取值为"full"意味所有的μ,Σ都需要指定。取为“spherical”则

Σ的非对角线元素为0,对角线元素相同。取值为“diag”则Σ的非对角线元素为0,对角线元素可以不同,"tied"指所有的隐藏状态对应的观测状态分布使用相同的协方差矩阵Σ

我们现在跑一跑HMM问题一解码的过程,由于观测状态是二维的,我们用的三维观测序列, 所以这里的 输入是一个3×2×2的张量,代码如下:

输出结果如下:

[0 0 1]

再看看HMM问题一对数概率的计算:

输出如下:

-41.1211281377

以上就是用hmmlearn学习HMM的过程。

本文地址:http://51blog.com/?p=3810
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 cloudsky ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情