隐马尔可夫模型

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

在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中,状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

马尔可夫模型的演化

上边的图示强调了HMM的状态变迁。有时，明确的表示出模型的演化也是有用的,我们用x（t₁）与x（t₂）来表达不同时刻t₁ 和t₂的状态。

圖中箭頭方向則表示不同資訊間的關聯性，因此可以得知 $x(t)$ 和 $x(t-1)$ 有關，而 $x(t-1)$ 又和 $x(t-2)$ 有關。

而每個 $y(t)$ 只和 $x(t)$ 有關，其中 $x(t)$ 我們稱為隱藏變數（hidden variable），是觀察者無法得知的變數。

隱性馬可夫模型常被用來解決有未知條件的數學問題。

假設隱藏狀態的值對應到的空間有 $N$ 個元素，也就是說在時間 $t$ 時，隱藏狀態會有 $N$ 種可能。

同樣的， $t+1$ 也會有 $N$ 種可能的值，所以從 $t$ 到 $t+1$ 間的關係會有 $N^{2}$ 種可能。

除了 $x(t)$ 間的關係外，每組 $x(t),y(t)$ 間也有對應的關係。

若觀察到的 $y(t)$ 有 $M$ 種可能的值，則該馬可夫模型的複雜度為 $O(NM^{2})$

在这个图中,每一个时间块（x(t), y(t)）都可以向前或向后延伸。通常，时间的起点被设置为t=0 或 t=1.

馬可夫模型的機率

假設觀察到的結果為 $Y$

$Y=y(0),y(1),...,y(L-1)$

隱藏條件為 $X$

$X=x(0),x(1),...,x(L-1)$

長度為 $L$ ，則馬可夫模型的機率可以表達為：

$P(Y)=\sum _{X}P(Y\mid X)P(X)\,$

由這個機率模型來看，可以得知馬可夫模型將該時間點前後的資訊都納入考量。

使用隐马尔可夫模型

HMM有三个典型(canonical)问题:

已知模型参数和某一特定输出序列，求最后时刻各个隐含状态的概率分布，即 ${\displaystyle P(x(t)\ |\ y(1),\dots ,y(t))}P(x(t)\ |\ y(1),\dots ,y(t))$ . 通常使用forward算法解决.
已知模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序列.通常使用Viterbi算法解决.
已知输出序列，寻找最可能的状态转移以及输出概率.通常使用Baum-Welch算法以及Reversed Viterbi算法解决.

另外,最近的一些方法使用Junction tree算法来解决这三个问题。

具体实例

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

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

你知道这个地区的总的天气趋势,并且平时知道你朋友会做的事情.也就是说这个隐马尔可夫模型的参数是已知的.你可以用程序语言(Python)写下来:

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},
   }

在这些代码中,start_probability代表了你对于你朋友第一次给你打电话时的天气情况的不确定性(你知道的只是那个地方平均起来下雨多些).在这里,这个特定的概率分布并非平衡的,平衡概率应该接近（在给定变迁概率的情况下）{'Rainy': 0.571, 'Sunny': 0.429}< transition_probability 表示基于马尔可夫链模型的天气变迁,在这个例子中,如果今天下雨,那么明天天晴的概率只有30%.代码emission_probability 表示了你朋友每天做某件事的概率.如果下雨,有 50% 的概率他在清理房间;如果天晴,则有60%的概率他在外头散步.

这个例子在维特比算法页上有更多的解释。

隐马尔可夫模型的应用

语音识别、中文斷詞/分詞或光学字符识别
机器翻译
生物信息学和基因组学
- 基因组序列中蛋白质编码区域的预测
- 对于相互关联的DNA或蛋白质族的建模
- 从基本结构中预测第二结构元素
- 通信中的译码过程
还有更多...

隱馬可夫模型在語音處理上的應用

因為馬可夫模型有下列特色：

時間點 $t$ 的隱藏條件和時間點 $t-1$ 的隱藏條件有關。因為人類語音擁有前後的關聯，可以從語義與發音兩點來看：

單字的發音擁有前後關聯：例如"They are"常常發音成"They're"，或是"Did you"會因為"you"的發音受"did"的影響，常常發音成"did ju"，而且語音辨識中用句子的發音來進行分析，因此需要考慮到每個音節的前後關係，才能夠有較高的準確率。
句子中的單字有前後關係：從英文文法來看，主詞後面常常接助動詞或是動詞，動詞後面接的會是受詞或介係詞。而或是從單一單字的使用方法來看，對應的動詞會有固定使用的介係詞或對應名詞。因此分析語音訊息時需要為了提升每個單字的準確率，也需要分析前後的單字。

馬可夫模型將輸入訊息視為一單位一單位，接著進行分析，與人類語音模型的特性相似。語音系統辨識的單位為一個單位時間內的聲音。利用梅爾倒頻譜等語音處理方法，轉換成一個發音單位，為離散型的資訊。而馬可夫模型使用的隱藏條件也是一個個被封包的 $x(t)$ ，因此使用馬可夫模型來處理聲音訊號比較合適。

历史

隐马尔可夫模型最初是在20世纪60年代后半期Leonard E. Baum和其它一些作者在一系列的统计学论文中描述的。HMM最初的应用之一是开始于20世纪70年代中期的语音识别。^[1]

在1980年代后半期，HMM开始应用到生物序列尤其是DNA的分析中。此后，在生物信息学领域HMM逐渐成为一项不可或缺的技术。^[2]

参见

注解

^ Rabiner, p. 258
^ Durbin

参考书目

Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.
Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1999. ISBN 0521629713.
Kristie Seymore, Andrew McCallum, and Roni Rosenfeld. Learning Hidden Markov Model Structure for Information Extraction. AAAI 99 Workshop on Machine Learning for Information Extraction, 1999. (also at CiteSeer: [1])
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
J. Li, A. Najmi, R. M. Gray, Image classification by a two dimensional hidden Markov model, IEEE Transactions on Signal Processing, 48(2):517-33, February 2000.
隐马尔可夫模型(课件), 徐从富,浙江大学人工智能研究所 [2]

外部链接

Hidden Markov Model (HMM) Toolbox for Matlab (by Kevin Murphy)
Hidden Markov Model Toolkit (HTK) (a portable toolkit for building and manipulating hidden Markov models)
Hidden Markov Models (an exposition using basic mathematics)
GHMM Library (home page of the GHMM Library project)
Jahmm Java Library (Java library and associated graphical application)
A step-by-step tutorial on HMMs (University of Leeds)
Software for Markov Models and Processes (TreeAge Software)

[1] Rabiner, p. 258

[2] Durbin

[1]

[2]