隐马尔可夫模型

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

来源:维基百科
简介

隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。HMM的基础是马尔可夫链。马尔可夫链因俄国数学家Andrey Andreyevich Markov得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。显马尔可夫过程是完全确定性的——一个给定的状态经常会伴随另一个状态。交通信号灯就是一个例子。而马尔科夫模型是仅能部分观察到的马尔可夫链状态。隐马尔可夫模型通过分析可见数据来计算隐藏状态的发生。随后,借助隐藏状态分析,隐马尔可夫模型可以估计可能的未来观察模式。比如高或低气压的概率(这是隐藏状态)可用于预测晴天、雨天、多云天的概率。该模型的难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。

从数学角度来定义,在隐马尔可夫模型(HMM)中,我们观察到一个字符串(或观察序列x,但一般来说,它的标签序列y是隐藏的(未被观察到)。HMM是生成模型,他拟合标记序列y和观察序列x的联合分布。 具体来说,标记序列y由马尔可夫模型生成, 然后从y生成观测值x。y的分布和x条件于y的分布分别为:

其中\sigma_{y,y'}为标签y后跟标签y'的概率,\tau_{y,x}为标签y生成输出x的概率。

这样,x和y的联合分布为:

因此,HMM的生成过程如下:以概率P(y_i | y_{i-1})生成下一个标签y_i,然后以概率P(x_i | y_i)生产序列x_i。

HMM可以使用贝叶斯网络可视化。 在贝叶斯网络中,节点是随机变量,它们之间的边缘表示依赖关系。 如果我们回到HMM的时间步骤隐喻,这个图可以被认为如下:在时间i,HMM在Y_{i-1} = y和Y_i = y'之间转换的概率是\sigma_y,下图中的顶行箭头表示这种依赖性。 然后(在同一时间步骤期间)HMM根据y_i的概率分布生成x_i。 向下箭头的行表示这种依赖性。

[描述来源:Charniak, E. and Johnson, M. (2013). Introduction to Computational Linguistics.]

假设你有一个住得很远的朋友,他每天跟你打电话告诉你他那天做了什么。你的朋友仅仅对三种活动感兴:公园散步,购物以及清理房间。他选择做什么事情只凭天气。你对于他所住的地方的天气情况并不了解,但是你知道总的趋势。在他告诉你每天所做的事情基础上,你想要猜测他所在地的天气情况。

你认为天气的运行就像一个马尔可夫链.其有两个状态 "雨"和"晴",但是你无法直接观察它们,也就是说,它们对于你是隐藏的。每天,你的朋友有一定的概率进行下列活动:"散步"、"购物"、"清理"。因为你朋友告诉你他的活动,所以这些活动就是你的观察数据。这整个系统就是一个隐马尔可夫模型HMM。

[描述来源:维基百科 URL:https://zh.wikipedia.org/wiki/%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8B]

发展历史

1966年起,Leonard E. Baum等学者在一系列研究中提出了隐马尔可夫模型(Hidden Markov Model,HMM),它用来描述一个含有隐含未知参数的马尔可夫过程。1975年,Baker提出了DRAGON系统, 将 HMM 用于语音识别,HMM成为了大多数现代自动语音识别系统的基础。20世纪80年代起,HMM 也开始用于分析生物序列(DNA)。特别是1989年Gary A. Churchill 将 HMM 用于分析生物序列;自那以后这就成为了这一领域可直接使用的技术。2001年Anders Krogh等人基于隐马尔可夫模型描述和验证了一种新的膜蛋白拓扑预测方法TMHMM。他们对TMHMM的性能进行了详细分析,并表明它正确地预测了97-98%的跨膜螺旋。基于这些预测,他们能够估计大多数基因组中所有基因的20-30%编码膜蛋白。

HMM还可以用于词性标注,在20世纪80年代中期,欧洲的研究人员在对Lancaster-Oslo-Bergen语料库进行标记工作时,开始使用隐马尔可夫模型(HMM)来消除词性的歧义。2000年,同年,Andrew McCallum等人提出了MEMM(Maximum Entropy Markov Models),直接学习条件概率。MEMM主要是改进HMM的两个问题,一是其为生成模型(generative model),二是不能使用更加复杂的feature。

John Lafferty等人提出的CRF也常常被认为是HMM的一种替代,作为判别模型,可以解决HMM在某些问题上由于是生成模型不方便计算的问题。HMM其他的应用实例有1997年Thad Starner和Alex Pentland使用HMM,并应用强大的上下文和语法规则识别手语等。

主要事件

年份事件相关论文/Reference
1966Leonard E. Baum等学者在一系列研究中提出了隐马尔可夫模型(Hidden Markov Model,HMM)Baum, L. E.; Petrie, T. (1966). Statistical Inference for Probabilistic Functions of Finite State Markov Chains. The Annals of Mathematical Statistics. 37 (6): 1554–1563.
1975Baker 将 HMM 用于语音识别Baker, J. (1975). The DRAGON system—An overview. IEEE Transactions on Acoustics, Speech, and Signal Processing. 23: 24–29.
20世纪80年代HMM 开始用于分析生物序列(DNA)Bishop, M. and Thompson, E. (1986). Maximum Likelihood Alignment of DNA Sequences. Journal of Molecular Biology. 190 (2): 159–165.
1997Thad Starner和Alex Pentland使用HMM,并应用强大的上下文和语法规则识别手语Starner, T.; Pentland, A. (1997). Real-Time American Sign Language Recognition from Video Using Hidden Markov Models. Motion-Based Recognition. pp 227-243.
2000Andrew McCallum等人提出了MEMM(Maximum Entropy Markov Models)McCallum, A., Freitag, D., and Pereira, F. C. N. (2000). Maximum entropy Markov models for information extraction and segmentation. In ICML 2000, pp. 591–598.
2001Anders Krogh等人基于隐马尔可夫模型描述和验证了一种新的膜蛋白拓扑预测方法TMHMMKrogh, A.; Larsson, B.; von Heijne, G.; Sonnhammer, E. L. L. (2001). Predicting transmembrane protein topology with a hidden markov model: application to complete genomes. Journal of Molecular Biology. 305(3): 567-580.
2001John Lafferty等人提出CRFLafferty, J. D., McCallum, A., and Pereira, F. C. N. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML 2001, Stanford, CA.

发展分析

瓶颈

HMM只依赖于每一个状态和它对应的观察对象,但序列标注问题不仅和单个词相关,而且和观察序列的长度,单词的上下文,等等相关。此外, HMM学到的是状态和观察序列的联合分布P(Y,X),而预测问题中,我们需要的是条件概率P(Y|X)。此外,HMM在训练时计算量比较大,如果应用场景对计算量有限制可能不适用,并且随着维度增大有可能出现维数灾难。

未来发展方向

对HMM的缺点进行改进,比如MEMM可以考虑到相邻状态之间依赖关系,有更强的表达能力;CRF模型是判别模型,能够很好的学习目标函数,并且CRF是全局归一化。另外,将HMM的一些特性(比如说马尔科夫性质)与深度学习结合也是一个方向。

Contributor: Yuanyuan Li

相关人物
安德鲁·麦卡勒姆
安德鲁·麦卡勒姆
Andrew McCallum是马萨诸塞州阿默斯特大学计算机科学系的教授兼研究员。他的主要专业是机器学习,自然语言处理,信息提取,信息整合和社交网络分析。
亚历克斯·彭特兰
亚历克斯·彭特兰
美国计算机科学家,麻省理工学院教授,可穿戴设备先驱,连续创业者。他是计算机科学领域被引用次数最多的作者之一,并帮助创建了麻省理工学院媒体实验室。他的h指数为125。研究重心:社交物理学、大数据和隐私研究。
简介
相关人物