史上最详细最容易理解的HMM文章
分類 隱馬爾科夫模型?
HMM(隱馬爾科夫模型)是自然語言處理中的一個基本模型，用途比較廣泛，如漢語分詞、詞性標注及語音識別等，在NLP中占有很重要的地位。網上關于HMM的介紹講解文檔很多，我自己當時開始看的時候也有點稀里糊涂。后來看到wiki上舉得一個關于HMM的例子才如醍醐灌頂，忽然間明白HMM的三大問題是怎么回事了。例子我借助中文wiki重新翻譯了一下，并對三大基本問題進行說明，希望對讀者朋友有所幫助：
Alice 和Bob是好朋友，但是他們離得比較遠，每天都是通過電話了解對方那天作了什么.Bob僅僅對三種活動感興趣:公園散步,購物以及清理房間.他選擇做什么事情只憑當天天氣.Alice對于Bob所住的地方的天氣情況并不了解,但是知道總的趨勢.在Bob告訴Alice每天所做的事情基礎上,Alice想要猜測Bob所在地的天氣情況.
Alice認為天氣的運行就像一個馬爾可夫鏈. 其有兩個狀態 “雨”和”晴”,但是無法直接觀察它們,也就是說,它們對于Alice是隱藏的.每天,Bob有一定的概率進行下列活動:”散步”, “購物”, 或 “清理”. 因為Bob會告訴Alice他的活動,所以這些活動就是Alice的觀察數據.這整個系統就是一個隱馬爾可夫模型HMM.
Alice知道這個地區的總的天氣趨勢,并且平時知道Bob會做的事情.也就是說這個隱馬爾可夫模型的參數是已知的.可以用程序語言(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代表了Alice對于Bob第一次給她打電話時的天氣情況的不確定性(Alice知道的只是那個地方平均起來下雨多些).在這里,這個特定的概率分布并非平衡的,平衡概率應該接近（在給定變遷概率的情況下）{‘Rainy’: 0.571, ‘Sunny’: 0.429}。 transition_probability 表示馬爾可夫鏈下的天氣變遷情況,在這個例子中,如果今天下雨,那么明天天晴的概率只有30%.代碼emission_probability 表示了Bob每天作某件事的概率.如果下雨,有 50% 的概率他在清理房間;如果天晴,則有60%的概率他在外頭散步。
Alice和Bob通了三天電話后發現第一天Bob去散步了，第二天他去購物了，第三天他清理房間了。Alice現在有兩個問題：這個觀察序列“散步、購物、清理”的總的概率是多少？(注：這個問題對應于HMM的基本問題之一：已知HMM模型λ及觀察序列O，如何計算P(O|λ)？) 最能解釋這個觀察序列的狀態序列（晴/雨）又是什么？（注：這個問題對應HMM基本問題之二：給定觀察序列O=O1,O2,…OT以及模型λ,如何選擇一個對應的狀態序列S = q1,q2,…qT，使得S能夠最為合理的解釋觀察序列O？）
至于HMM的基本問題之三：如何調整模型參數, 使得P(O|λ)最大？這個問題事實上就是給出很多個觀察序列值，來訓練以上幾個參數的問題。
?
HMM學習最佳范例與崔曉源的博客
分類 隱馬爾科夫模型?
“HMM學習最佳范例”與“崔曉源的博客”本來是不搭邊的，由于自己花了幾乎一個晚上瀏覽崔師兄的博客，沒有時間寫文章了，所以最終決定放在這里做成大雜燴，不過我覺得這個大雜燴還是有點價值的。
先說說HMM，通過Google Analytics 發現，讀者經常通過與“隱馬爾科夫模型、HMM”相關的關鍵字訪問52nlp的，因為這里曾經寫了一篇簡單的介紹HMM的文章。事實上，對于HMM，由于自己沒有直接實踐過，僅停留在“紙上得來”的程度，所以心里也虛。某天趕巧遇到了國外這個專門介紹HMM及其相關算法的主頁：http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
里面圖文并茂還動感十足，寫得又通俗易懂，可以說是我見到過的介紹HMM最好的范例了。讀完了立即有翻譯全文的沖動，這樣一方面可以給有需要的讀者以幫助，另一方面翻譯雖然耗時，但卻能仔細把握一下比較細節的地方，這也是我翻譯“MIT自然語言處理”的初衷。不過Google了一下，發現已經有人把這件事做了，這個人就是崔曉源，中文譯名是“隱馬爾科夫模型HMM自學”。
原計劃這一篇博客題目為“HMM學習最佳范例”的，準備介紹這個英文主頁和崔曉源的翻譯，出于尊重譯者勞動的緣故，Google“隱馬爾科夫模型HMM自學”，可是發現其被轉載了很多，除了知道譯者是“崔曉源”外，原始出處似乎被丟失了。不過最終還是找到了原始出處：
http://blogcui.spaces.live.com/blog/cns!46BDB23E24219CE9!144.entry?_c=BlogPart
其實就是崔師兄在msn spaces上的博客，仔細對比了一下原文，發現崔師兄的這個翻譯是一個簡化和縮略版本，有些地方只是概況性的翻譯了一下，省去了一些內容，所以這個介紹HMM主頁還有再翻譯的必要。有可能的話，今后在52nlp上我會慢慢翻譯HMM這個系列。
對比完之后，我就瀏覽開他的博客了，沒想到，一發而不可收，主要在于他的博客多數內容都很有價值。博客最集中更新的一段時間，是在05年5月到9月份他在MSRA-NLC組實習的時候，不過可惜的是，現在幾乎不更新了，但是技術博客的好處再于其有效期更長，所以許多東西仍很可以參考，讀者如果對NLP，IR或者機器學習感興趣，不妨按時間順序讀讀他的日志，定會有不小收獲的，這里絕非廣告。他目前在MSRA工作，以下是他的“About me”：
”A man full of enthusiasm for advanced technology business, natrual language processing, IR and search engine technology. I’m finding my way. You never do a bad job only if you choose the right time. So keep your pace accordingly.“
我在上面最大的發現是這個關于機器學習的英文博客：
?
幾種不同程序語言的HMM版本
分類 隱馬爾科夫模型?
“紙上得來終覺淺，絕知此事要躬行”，在繼續翻譯《HMM學習最佳范例》之前，這里先補充幾個不同程序語言實現的HMM版本，主要參考了維基百科。讀者有興趣的話可以研究一下代碼，這樣對于HMM的學習會深刻很多！
C語言版：
1、 HTK（Hidden Markov Model Toolkit）：
HTK是英國劍橋大學開發的一套基于C語言的隱馬爾科夫模型工具箱，主要應用于語音識別、語音合成的研究，也被用在其他領域，如字符識別和DNA排序等。HTK是重量級的HMM版本。
HTK主頁：http://htk.eng.cam.ac.uk/
2、 GHMM Library：
The General Hidden Markov Model library (GHMM) is a freely available LGPL-ed C library implementing efficient data structures and algorithms for basic and extended HMMs.
GHMM主頁：http://www.ghmm.org/
3、 UMDHMM（Hidden Markov Model Toolkit）：
Hidden Markov Model (HMM) Software: Implementation of Forward-Backward, Viterbi, and Baum-Welch algorithms.
這款屬于輕量級的HMM版本。
UMDHMM主頁：http://www.kanungo.com/software/software.html
Java版：
4、 Jahmm Java Library (general-purpose Java library)：
Jahmm (pronounced “jam”), is a Java implementation of Hidden Markov Model (HMM) related algorithms. It’s been designed to be easy to use (e.g. simple things are simple to program) and general purpose.
Jahmm主頁：http://code.google.com/p/jahmm/
Malab版：
5、 Hidden Markov Model (HMM) Toolbox for Matlab：
This toolbox supports inference and learning for HMMs with discrete outputs (dhmm’s), Gaussian outputs (ghmm’s), or mixtures of Gaussians output (mhmm’s).
Matlab-HMM主頁：http://www.cs.ubc.ca/~murphyk/Software/HMM/hmm.html
Common Lisp版：
6、CL-HMM Library (HMM Library for Common Lisp)：
Simple Hidden Markov Model library for ANSI Common Lisp. Main structures and basic algorithms implemented. Performance speed comparable to C code. It’s licensed under LGPL.
CL-HMM主頁：http://www.ashrentum.net/jmcejuela/programs/cl-hmm/
Haskell版：
7、The hmm package （A Haskell library for working with Hidden Markov Models）：
A simple library for working with Hidden Markov Models. Should be usable even by people who are not familiar with HMMs. Includes implementations of Viterbi’s algorithm and the forward algorithm.
Haskell-HMM主頁：http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmm
注：Haskell是一種純函數式編程語言，它的命名源自美國數學家Haskell Brooks Curry，他在數學邏輯方面上的工作使得函數式編程語言有了廣泛的基礎。
是否還有C++版、Perl版或者Python版呢？歡迎補充！
HMM學習最佳范例一：介紹
隱馬爾科夫模型（HMM）依然是讀者訪問“我愛自然語言處理”的一個熱門相關關鍵詞，我曾在《HMM學習最佳范例與崔曉源的博客》中介紹過國外的一個不錯的HMM學習教程，并且國內崔曉源師兄有一個相應的翻譯版本，不過這個版本比較簡化和粗略，有些地方只是概況性的翻譯了一下，省去了一些內容，所以從今天開始計劃在52nlp上系統的重新翻譯這個學習教程，希望對大家有點用。
一、介紹（Introduction）
我們通常都習慣尋找一個事物在一段時間里的變化模式（規律）。這些模式發生在很多領域，比如計算機中的指令序列，句子中的詞語順序和口語單詞中的音素序列等等，事實上任何領域中的一系列事件都有可能產生有用的模式。
考慮一個簡單的例子，有人試圖通過一片海藻推斷天氣——民間傳說告訴我們‘濕透的’海藻意味著潮濕陰雨，而‘干燥的’海藻則意味著陽光燦爛。如果它處于一個中間狀態（‘有濕氣’），我們就無法確定天氣如何。然而，天氣的狀態并沒有受限于海藻的狀態，所以我們可以在觀察的基礎上預測天氣是雨天或晴天的可能性。另一個有用的線索是前一天的天氣狀態（或者，至少是它的可能狀態）——通過綜合昨天的天氣及相應觀察到的海藻狀態，我們有可能更好的預測今天的天氣。
這是本教程中我們將考慮的一個典型的系統類型。
首先，我們將介紹產生概率模式的系統，如晴天及雨天間的天氣波動。
然后，我們將會看到這樣一個系統，我們希望預測的狀態并不是觀察到的——其底層系統是隱藏的。在上面的例子中，觀察到的序列將是海藻而隱藏的系統將是實際的天氣。
最后，我們會利用已經建立的模型解決一些實際的問題。對于上述例子，我們想知道：
1. 給出一個星期每天的海藻觀察狀態，之后的天氣將會是什么?
2. 給定一個海藻的觀察狀態序列，預測一下此時是冬季還是夏季？直觀地，如果一段時間內海藻都是干燥的，那么這段時間很可能是夏季，反之，如果一段時間內海藻都是潮濕的，那么這段時間可能是冬季。
二、生成模式（Generating Patterns）
1、確定性模式（Deterministic Patterns）
考慮一套交通信號燈，燈的顏色變化序列依次是紅色-紅色/黃色-綠色-黃色-紅色。這個序列可以作為一個狀態機器，交通信號燈的不同狀態都緊跟著上一個狀態。
注意每一個狀態都是唯一的依賴于前一個狀態，所以，如果交通燈為綠色，那么下一個顏色狀態將始終是黃色——也就是說，該系統是確定性的。確定性系統相對比較容易理解和分析，因為狀態間的轉移是完全已知的。
2、非確定性模式（Non-deterministic patterns）
為了使天氣那個例子更符合實際，加入第三個狀態——多云。與交通信號燈例子不同，我們并不期望這三個天氣狀態之間的變化是確定性的，但是我們依然希望對這個系統建模以便生成一個天氣變化模式（規律）。
一種做法是假設模型的當前狀態僅僅依賴于前面的幾個狀態，這被稱為馬爾科夫假設，它極大地簡化了問題。顯然，這可能是一種粗糙的假設，并且因此可能將一些非常重要的信息丟失。
當考慮天氣問題時，馬爾科夫假設假定今天的天氣只能通過過去幾天已知的天氣情況進行預測——而對于其他因素，譬如風力、氣壓等則沒有考慮。在這個例子以及其他相似的例子中，這樣的假設顯然是不現實的。然而，由于這樣經過簡化的系統可以用來分析，我們常常接受這樣的知識假設，雖然它產生的某些信息不完全準確。
一個馬爾科夫過程是狀態間的轉移僅依賴于前n個狀態的過程。這個過程被稱之為n階馬爾科夫模型，其中n是影響下一個狀態選擇的（前）n個狀態。最簡單的馬爾科夫過程是一階模型，它的狀態選擇僅與前一個狀態有關。這里要注意它與確定性系統并不相同，因為下一個狀態的選擇由相應的概率決定，并不是確定性的。
下圖是天氣例子中狀態間所有可能的一階狀態轉移情況：
對于有M個狀態的一階馬爾科夫模型，共有個狀態轉移，因為任何一個狀態都有可能是所有狀態的下一個轉移狀態。每一個狀態轉移都有一個概率值，稱為狀態轉移概率——這是從一個狀態轉移到另一個狀態的概率。所有的個概率可以用一個狀態轉移矩陣表示。注意這些概率并不隨時間變化而不同——這是一個非常重要（但常常不符合實際）的假設。
下面的狀態轉移矩陣顯示的是天氣例子中可能的狀態轉移概率：
-也就是說，如果昨天是晴天，那么今天是晴天的概率為0.5，是多云的概率為0.375。注意，每一行的概率之和為1。
要初始化這樣一個系統，我們需要確定起始日天氣的（或可能的）情況，定義其為一個初始概率向量，稱為向量。
-也就是說，第一天為晴天的概率為1。
現在我們定義一個一階馬爾科夫過程如下：
狀態：三個狀態——晴天，多云，雨天。
向量：定義系統初始化時每一個狀態的概率。
狀態轉移矩陣：給定前一天天氣情況下的當前天氣概率。
任何一個可以用這種方式描述的系統都是一個馬爾科夫過程。
3、總結
我們嘗試識別時間變化中的模式，并且為了達到這個目我們試圖對這個過程建模以便產生這樣的模式。我們使用了離散時間點、離散狀態以及做了馬爾科夫假設。在采用了這些假設之后，系統產生了這個被描述為馬爾科夫過程的模式，它包含了一個向量（初始概率）和一個狀態轉移矩陣。關于假設，重要的一點是狀態轉移矩陣并不隨時間的改變而改變——這個矩陣在整個系統的生命周期中是固定不變的。
三、隱藏模式（Hidden Patterns）
1、馬爾科夫過程的局限性
在某些情況下，我們希望找到的模式用馬爾科夫過程描述還顯得不充分。回顧一下天氣那個例子，一個隱士也許不能夠直接獲取到天氣的觀察情況，但是他有一些水藻。民間傳說告訴我們水藻的狀態與天氣狀態有一定的概率關系——天氣和水藻的狀態是緊密相關的。在這個例子中我們有兩組狀態，觀察的狀態（水藻的狀態）和隱藏的狀態（天氣的狀態）。我們希望為隱士設計一種算法，在不能夠直接觀察天氣的情況下，通過水藻和馬爾科夫假設來預測天氣。
一個更實際的問題是語音識別，我們聽到的聲音是來自于聲帶、喉嚨大小、舌頭位置以及其他一些東西的組合結果。所有這些因素相互作用產生一個單詞的聲音，一套語音識別系統檢測的聲音就是來自于個人發音時身體內部物理變化所引起的不斷改變的聲音。
一些語音識別裝置工作的原理是將內部的語音產出看作是隱藏的狀態，而將聲音結果作為一系列觀察的狀態，這些由語音過程生成并且最好的近似了實際（隱藏）的狀態。在這兩個例子中，需要著重指出的是，隱藏狀態的數目與觀察狀態的數目可以是不同的。一個包含三個狀態的天氣系統（晴天、多云、雨天）中，可以觀察到4個等級的海藻濕潤情況（干、稍干、潮濕、濕潤）；純粹的語音可以由80個音素描述，而身體的發音系統會產生出不同數目的聲音，或者比80多，或者比80少。
在這種情況下，觀察到的狀態序列與隱藏過程有一定的概率關系。我們使用隱馬爾科夫模型對這樣的過程建模，這個模型包含了一個底層隱藏的隨時間改變的馬爾科夫過程，以及一個與隱藏狀態某種程度相關的可觀察到的狀態集合。
2、隱馬爾科夫模型（Hidden Markov Models）
下圖顯示的是天氣例子中的隱藏狀態和觀察狀態。假設隱藏狀態（實際的天氣）由一個簡單的一階馬爾科夫過程描述，那么它們之間都相互連接。
隱藏狀態和觀察狀態之間的連接表示：在給定的馬爾科夫過程中，一個特定的隱藏狀態生成特定的觀察狀態的概率。這很清晰的表示了‘進入’一個觀察狀態的所有概率之和為1，在上面這個例子中就是Pr(Obs|Sun), Pr(Obs|Cloud) 及 Pr(Obs|Rain)之和。（對這句話我有點疑惑？）
除了定義了馬爾科夫過程的概率關系，我們還有另一個矩陣，定義為混淆矩陣（confusion matrix），它包含了給定一個隱藏狀態后得到的觀察狀態的概率。對于天氣例子，混淆矩陣是：
注意矩陣的每一行之和是1。
3、總結（Summary）
我們已經看到在一些過程中一個觀察序列與一個底層馬爾科夫過程是概率相關的。在這些例子中，觀察狀態的數目可以和隱藏狀態的數碼不同。
我們使用一個隱馬爾科夫模型（HMM）對這些例子建模。這個模型包含兩組狀態集合和三組概率集合：
* 隱藏狀態：一個系統的（真實）狀態，可以由一個馬爾科夫過程進行描述（例如，天氣）。
* 觀察狀態：在這個過程中‘可視’的狀態（例如，海藻的濕度）。
*向量：包含了（隱）模型在時間t=1時一個特殊的隱藏狀態的概率（初始概率）。
* 狀態轉移矩陣：包含了一個隱藏狀態到另一個隱藏狀態的概率
* 混淆矩陣：包含了給定隱馬爾科夫模型的某一個特殊的隱藏狀態，觀察到的某個觀察狀態的概率。
因此一個隱馬爾科夫模型是在一個標準的馬爾科夫過程中引入一組觀察狀態，以及其與隱藏狀態間的一些概率關系。
四、隱馬爾科夫模型（Hidden Markov Models）
1、定義（Definition of a hidden Markov model）
一個隱馬爾科夫模型是一個三元組（, A, B）。
：初始化概率向量；
：狀態轉移矩陣；
：混淆矩陣；
在狀態轉移矩陣及混淆矩陣中的每一個概率都是時間無關的——也就是說，當系統演化時這些矩陣并不隨時間改變。實際上，這是馬爾科夫模型關于真實世界最不現實的一個假設。
2、應用（Uses associated with HMMs）
一旦一個系統可以作為HMM被描述，就可以用來解決三個基本問題。其中前兩個是模式識別的問題：給定HMM求一個觀察序列的概率（評估）；搜索最有可能生成一個觀察序列的隱藏狀態訓練（解碼）。第三個問題是給定觀察序列生成一個HMM（學習）。
a) 評估（Evaluation）
考慮這樣的問題，我們有一些描述不同系統的隱馬爾科夫模型（也就是一些(,A,B)三元組的集合）及一個觀察序列。我們想知道哪一個HMM最有可能產生了這個給定的觀察序列。例如，對于海藻來說，我們也許會有一個“夏季”模型和一個“冬季”模型，因為不同季節之間的情況是不同的——我們也許想根據海藻濕度的觀察序列來確定當前的季節。
我們使用前向算法（forward algorithm）來計算給定隱馬爾科夫模型（HMM）后的一個觀察序列的概率，并因此選擇最合適的隱馬爾科夫模型(HMM)。
在語音識別中這種類型的問題發生在當一大堆數目的馬爾科夫模型被使用，并且每一個模型都對一個特殊的單詞進行建模時。一個觀察序列從一個發音單詞中形成，并且通過尋找對于此觀察序列最有可能的隱馬爾科夫模型（HMM）識別這個單詞。
b) 解碼（ Decoding）
給定觀察序列搜索最可能的隱藏狀態序列。
另一個相關問題，也是最感興趣的一個，就是搜索生成輸出序列的隱藏狀態序列。在許多情況下我們對于模型中的隱藏狀態更感興趣，因為它們代表了一些更有價值的東西，而這些東西通常不能直接觀察到。
考慮海藻和天氣這個例子，一個盲人隱士只能感覺到海藻的狀態，但是他更想知道天氣的情況，天氣狀態在這里就是隱藏狀態。
我們使用Viterbi 算法（Viterbi algorithm）確定（搜索）已知觀察序列及HMM下最可能的隱藏狀態序列。
Viterbi算法（Viterbi algorithm）的另一廣泛應用是自然語言處理中的詞性標注。在詞性標注中，句子中的單詞是觀察狀態，詞性（語法類別）是隱藏狀態（注意對于許多單詞，如wind，fish擁有不止一個詞性）。對于每句話中的單詞，通過搜索其最可能的隱藏狀態，我們就可以在給定的上下文中找到每個單詞最可能的詞性標注。
C）學習（Learning）
根據觀察序列生成隱馬爾科夫模型。
第三個問題，也是與HMM相關的問題中最難的，根據一個觀察序列（來自于已知的集合），以及與其有關的一個隱藏狀態集，估計一個最合適的隱馬爾科夫模型（HMM），也就是確定對已知序列描述的最合適的（,A,B）三元組。
當矩陣A和B不能夠直接被（估計）測量時，前向-后向算法（forward-backward algorithm）被用來進行學習（參數估計），這也是實際應用中常見的情況。
3、總結（Summary）
由一個向量和兩個矩陣(,A,B)描述的隱馬爾科夫模型對于實際系統有著巨大的價值，雖然經常只是一種近似，但它們卻是經得起分析的。隱馬爾科夫模型通常解決的問題包括：
1. 對于一個觀察序列匹配最可能的系統——評估，使用前向算法（forward algorithm）解決；
2. 對于已生成的一個觀察序列，確定最可能的隱藏狀態序列——解碼，使用Viterbi 算法（Viterbi algorithm）解決；
3. 對于已生成的觀察序列，決定最可能的模型參數——學習，使用前向-后向算法（forward-backward algorithm）解決。
五、前向算法（Forward Algorithm）
計算觀察序列的概率（Finding the probability of an observed sequence）
1.窮舉搜索（ Exhaustive search for solution）
給定隱馬爾科夫模型，也就是在模型參數（, A, B)已知的情況下，我們想找到觀察序列的概率。還是考慮天氣這個例子，我們有一個用來描述天氣及與它密切相關的海藻濕度狀態的隱馬爾科夫模型(HMM)，另外我們還有一個海藻的濕度狀態觀察序列。假設連續3天海藻濕度的觀察結果是（干燥、濕潤、濕透）——而這三天每一天都可能是晴天、多云或下雨，對于觀察序列以及隱藏的狀態，可以將其視為網格：
網格中的每一列都顯示了可能的的天氣狀態，并且每一列中的每個狀態都與相鄰列中的每一個狀態相連。而其狀態間的轉移都由狀態轉移矩陣提供一個概率。在每一列下面都是某個時間點上的觀察狀態，給定任一個隱藏狀態所得到的觀察狀態的概率由混淆矩陣提供。
可以看出，一種計算觀察序列概率的方法是找到每一個可能的隱藏狀態，并且將這些隱藏狀態下的觀察序列概率相加。對于上面那個（天氣）例子，將有3^3 = 27種不同的天氣序列可能性，因此，觀察序列的概率是：
Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)
用這種方式計算觀察序列概率極為昂貴，特別對于大的模型或較長的序列，因此我們可以利用這些概率的時間不變性來減少問題的復雜度。
2.使用遞歸降低問題復雜度
給定一個隱馬爾科夫模型（HMM），我們將考慮遞歸地計算一個觀察序列的概率。我們首先定義局部概率（partial probability）,它是到達網格中的某個中間狀態時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
假設一個T-長觀察序列是：
2a.局部概率(’s)
考慮下面這個網格，它顯示的是天氣狀態及對于觀察序列干燥，濕潤及濕透的一階狀態轉移情況：
我們可以將計算到達網格中某個中間狀態的概率作為所有到達這個狀態的可能路徑的概率求和問題。
例如，t=2時位于“多云”狀態的局部概率通過如下路徑計算得出：
我們定義t時刻位于狀態j的局部概率為at(j)——這個局部概率計算如下：
t ( j )= Pr(觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
對于最后的觀察狀態，其局部概率包括了通過所有可能的路徑到達這些狀態的概率——例如，對于上述網格，最終的局部概率通過如下路徑計算得出：
由此可見，對于這些最終局部概率求和等價于對于網格中所有可能的路徑概率求和，也就求出了給定隱馬爾科夫模型(HMM)后的觀察序列概率。
第3節給出了一個計算這些概率的動態示例。
2b.計算t=1時的局部概率’s
我們按如下公式計算局部概率：
t ( j )= Pr(觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
特別當t=1時，沒有任何指向當前狀態的路徑。故t=1時位于當前狀態的概率是初始概率，即Pr(state|t=1)=P(state)，因此，t=1時的局部概率等于當前狀態的初始概率乘以相關的觀察概率：
所以初始時刻狀態j的局部概率依賴于此狀態的初始概率及相應時刻我們所見的觀察概率。
2c.計算t>1時的局部概率’s
我們再次回顧局部概率的計算公式如下：
t ( j )= Pr(觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
我們可以假設（遞歸地），乘號左邊項“Pr( 觀察狀態 | 隱藏狀態j )”已經有了，現在考慮其右邊項“Pr(t時刻所有指向j狀態的路徑）”。
為了計算到達某個狀態的所有路徑的概率，我們可以計算到達此狀態的每條路徑的概率并對它們求和，例如：
計算所需要的路徑數目隨著觀察序列的增加而指數級遞增，但是t-1時刻’s給出了所有到達此狀態的前一路徑概率，因此，我們可以通過t-1時刻的局部概率定義t時刻的’s，即：
故我們所計算的這個概率等于相應的觀察概率（亦即，t+1時在狀態j所觀察到的符號的概率）與該時刻到達此狀態的概率總和——這來自于上一步每一個局部概率的計算結果與相應的狀態轉移概率乘積后再相加——的乘積。
注意我們已經有了一個僅利用t時刻局部概率計算t+1時刻局部概率的表達式。
現在我們就可以遞歸地計算給定隱馬爾科夫模型(HMM)后一個觀察序列的概率了——即通過t=1時刻的局部概率’s計算t=2時刻的’s，通過t=2時刻的’s計算t=3時刻的’s等等直到t=T。給定隱馬爾科夫模型(HMM)的觀察序列的概率就等于t=T時刻的局部概率之和。
2d.降低計算復雜度
我們可以比較通過窮舉搜索（評估）和通過遞歸前向算法計算觀察序列概率的時間復雜度。
我們有一個長度為T的觀察序列O以及一個含有n個隱藏狀態的隱馬爾科夫模型l=(,A,B)。
窮舉搜索將包括計算所有可能的序列：
公式
對我們所觀察到的概率求和——注意其復雜度與T成指數級關系。相反的，使用前向算法我們可以利用上一步計算的信息，相應地，其時間復雜度與T成線性關系。
注：窮舉搜索的時間復雜度是，前向算法的時間復雜度是，其中T指的是觀察序列長度，N指的是隱藏狀態數目。
3.總結
我們的目標是計算給定隱馬爾科夫模型HMM下的觀察序列的概率——Pr(observations |)。
我們首先通過計算局部概率（’s）降低計算整個概率的復雜度，局部概率表示的是t時刻到達某個狀態s的概率。
t=1時，可以利用初始概率(來自于P向量）和觀察概率Pr(observation|state)（來自于混淆矩陣）計算局部概率；而t>1時的局部概率可以利用t-時的局部概率計算。
因此，這個問題是遞歸定義的，觀察序列的概率就是通過依次計算t=1,2,…,T時的局部概率，并且對于t=T時所有局部概率’s相加得到的。
注意，用這種方式計算觀察序列概率的時間復雜度遠遠小于計算所有序列的概率并對其相加（窮舉搜索）的時間復雜度。
我們使用前向算法計算T長觀察序列的概率:
其中y的每一個是觀察集合之一。局部（中間）概率(’s)是遞歸計算的，首先通過計算t=1時刻所有狀態的局部概率：
然后在每個時間點，t=2，… ，T時，對于每個狀態的局部概率，由下式計算局部概率:
也就是當前狀態相應的觀察概率與所有到達該狀態的路徑概率之積，其遞歸地利用了上一個時間點已經計算好的一些值。
最后，給定HMM,,觀察序列的概率等于T時刻所有局部概率之和：
再重復說明一下，每一個局部概率（t > 2 時）都由前一時刻的結果計算得出。
對于“天氣”那個例子，下面的圖表顯示了t = 2為狀態為多云時局部概率的計算過程。這是相應的觀察概率b與前一時刻的局部概率與狀態轉移概率a相乘后的總和再求積的結果：
總結（Summary）
我們使用前向算法來計算給定隱馬爾科夫模型（HMM）后的一個觀察序列的概率。它在計算中利用遞歸避免對網格所有路徑進行窮舉計算。
給定這種算法，可以直接用來確定對于已知的一個觀察序列，在一些隱馬爾科夫模型（HMMs）中哪一個HMM最好的描述了它——先用前向算法評估每一個（HMM），再選取其中概率最高的一個。
首先需要說明的是，本節不是這個系列的翻譯，而是作為前向算法這一章的補充，希望能從實踐的角度來說明前向算法。除了用程序來解讀hmm的前向算法外，還希望將原文所舉例子的問題拿出來和大家探討。
文中所舉的程序來自于UMDHMM這個C語言版本的HMM工具包，具體見《幾種不同程序語言的HMM版本》。先說明一下UMDHMM這個包的基本情況，在linux環境下，進入umdhmm-v1.02目錄，“make all”之后會產生4個可執行文件，分別是：
genseq: 利用一個給定的隱馬爾科夫模型產生一個符號序列（Generates a symbol sequence using the specified model sequence using the specified model）
testfor: 利用前向算法計算log Prob(觀察序列| HMM模型)（Computes log Prob(observation|model) using the Forward algorithm.）
testvit: 對于給定的觀察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態序列（Generates the most like state sequence for a given symbol sequence, given the HMM, using Viterbi）
esthmm: 對于給定的觀察符號序列，利用BaumWelch算法學習隱馬爾科夫模型HMM（Estimates the HMM from a given symbol sequence using BaumWelch）。
這些可執行文件需要讀入有固定格式的HMM文件及觀察符號序列文件，格式要求及舉例如下：
HMM 文件格式：
——————————————————————–
M= number of symbols
N= number of states
A:
a11 a12 … a1N
a21 a22 … a2N
. . . .
. . . .
. . . .
aN1 aN2 … aNN
B:
b11 b12 … b1M
b21 b22 … b2M
. . . .
. . . .
. . . .
bN1 bN2 … bNM
pi:
pi1 pi2 … piN
——————————————————————–
HMM文件舉例：
——————————————————————–
M= 2
N= 3
A:
0.333 0.333 0.333
0.333 0.333 0.333
0.333 0.333 0.333
B:
0.5 0.5
0.75 0.25
0.25 0.75
pi:
0.333 0.333 0.333
——————————————————————–
觀察序列文件格式：
——————————————————————–
T=seqence length
o1 o2 o3 . . . oT
——————————————————————–
觀察序列文件舉例：
——————————————————————–
T= 10
1 1 1 1 2 1 2 2 2 2
——————————————————————–
對于前向算法的測試程序testfor來說，運行：
testfor model.hmm（HMM文件） obs.seq（觀察序列文件）
就可以得到觀察序列的概率結果的對數值，這里我們在testfor.c的第58行對數結果的輸出下再加一行輸出：
fprintf(stdout, “prob(O| model) = %fn”, proba);
就可以輸出運用前向算法計算觀察序列所得到的概率值。至此，所有的準備工作已結束，接下來，我們將進入具體的程序解讀。
首先，需要定義HMM的數據結構，也就是HMM的五個基本要素，在UMDHMM中是如下定義的（在hmm.h中）：
typedef struct
{
int N; /* 隱藏狀態數目;Q={1,2,…,N} */
int M; /* 觀察符號數目; V={1,2,…,M}*/
double **A; /* 狀態轉移矩陣A[1..N][1..N]. a[i][j] 是從t時刻狀態i到t+1時刻狀態j的轉移概率 */
double **B; /* 混淆矩陣B[1..N][1..M]. b[j][k]在狀態j時觀察到符合k的概率。*/
double *pi; /* 初始向量pi[1..N]，pi[i] 是初始狀態概率分布 */
} HMM;
前向算法程序示例如下（在forward.c中）：
/*
函數參數說明：
*phmm：已知的HMM模型；T：觀察符號序列長度；
*O：觀察序列；**alpha：局部概率；*pprob：最終的觀察概率
*/
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
int i, j; /* 狀態索引 */
int t; /* 時間索引 */
double sum; /*求局部概率時的中間值 */
/* 1. 初始化：計算t=1時刻所有狀態的局部概率： */
for (i = 1; i <= phmm->N; i++)
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
/* 2. 歸納：遞歸計算每個時間點，t=2，… ，T時的局部概率 */
for (t = 1; t < T; t++)
{
for (j = 1; j <= phmm->N; j++)
{
sum = 0.0;
for (i = 1; i <= phmm->N; i++)
sum += alpha[t][i]* (phmm->A[i][j]);
alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
}
}
/* 3. 終止：觀察序列的概率等于T時刻所有局部概率之和*/
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += alpha[T][i];
}
下一節我將用這個程序來驗證英文原文中所舉前向算法演示例子的問題。
在HMM這個翻譯系列的原文中，作者舉了一個前向算法的交互例子，這也是這個系列中比較出彩的地方，但是，在具體運行這個例子的時候，卻發現其似乎有點問題。
先說一下如何使用這個交互例子，運行時需要瀏覽器支持java，我用的是firefox。首先在Set按鈕前面的對話框里上觀察序列，如“Dry,Damp, Soggy” 或“Dry Damp Soggy”，觀察符號間用逗號或空格隔開；然后再點擊Set按鈕，這樣就初始化了觀察矩陣；如果想得到一個總的結果，即Pr(觀察序列|隱馬爾科夫模型)，就點旁邊的Run按鈕；如果想一步一步觀察計算過程，即每個節點的局部概率，就單擊旁邊的Step按鈕。
原文交互例子（即天氣這個例子）中所定義的已知隱馬爾科夫模型如下：
1、隱藏狀態 (天氣)：Sunny，Cloudy，Rainy；
2、觀察狀態（海藻濕度）：Dry，Dryish，Damp，Soggy；
3、初始狀態概率： Sunny（0.63）， Cloudy（0.17）， Rainy（0.20）；
4、狀態轉移矩陣：
weather today
Sunny Cloudy Rainy
weather Sunny 0.500 0.375 0.125
yesterday Cloudy 0.250 0.125 0.625
Rainy 0.250 0.375 0.375
5、混淆矩陣：
observed states
Dry Dryish Damp Soggy
Sunny 0.60 0.20 0.15 0.05
hidden Cloudy 0.25 0.25 0.25 0.25
states Rainy 0.05 0.10 0.35 0.50
為了UMDHMM也能運行這個例子，我們將上述天氣例子中的隱馬爾科夫模型轉化為如下的UMDHMM可讀的HMM文件weather.hmm：
——————————————————————–
M= 4
N= 3
A:
0.500 0.375 0.125
0.250 0.125 0.625
0.250 0.375 0.375
B:
0.60 0.20 0.15 0.05
0.25 0.25 0.25 0.25
0.05 0.10 0.35 0.50
pi:
0.63 0.17 0.20
——————————————————————–
在運行例子之前，如果讀者也想觀察每一步的運算結果，可以將umdhmm-v1.02目錄下forward.c中的void Forward(…)函數替換如下：
——————————————————————–
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
double sum; /* partial sum */
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
{
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
printf( “a[1][%d] = pi[%d] * b[%d][%d] = %f * %f = %f\n”,i, i, i, O[i], phmm->pi[i], phmm->B[i][O[1]], alpha[1][i] );
}
/* 2. Induction */
for (t = 1; t < T; t++)
{
for (j = 1; j <= phmm->N; j++)
{
sum = 0.0;
for (i = 1; i <= phmm->N; i++)
{
sum += alpha[t][i]* (phmm->A[i][j]);
printf( “a[%d][%d] * A[%d][%d] = %f * %f = %f\n”, t, i, i, j, alpha[t][i], phmm->A[i][j], alpha[t][i]* (phmm->A[i][j]));
printf( “sum = %f\n”, sum );
}
alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
printf( “a[%d][%d] = sum * b[%d][%d]] = %f * %f = %f\n”,t+1, j, j, O[t+1], sum, phmm->B[j][O[t+1]], alpha[t+1][j] );
}
}
/* 3. Termination */
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
{
*pprob += alpha[T][i];
printf( “alpha[%d][%d] = %f\n”, T, i, alpha[T][i] );
printf( “pprob = %f\n”, *pprob );
}
}
——————————————————————–
替換完畢之后，重新“make clean”，“make all”，這樣新的testfor可執行程序就可以輸出前向算法每一步的計算結果。
現在我們就用testfor來運行原文中默認給出的觀察序列“Dry,Damp,Soggy”，其所對應的UMDHMM可讀的觀察序列文件test1.seq：
——————————————————————–
T=3
1 3 4
——————————————————————–
好了，一切準備工作就緒，現在就輸入如下命令：
testfor weather.hmm test1.seq > result1
result1就包含了所有的結果細節：
——————————————————————–
Forward without scaling
a[1][1] = pi[1] * b[1][1] = 0.630000 * 0.600000 = 0.378000
a[1][2] = pi[2] * b[2][3] = 0.170000 * 0.250000 = 0.042500
a[1][3] = pi[3] * b[3][4] = 0.200000 * 0.050000 = 0.010000
…
pprob = 0.026901
log prob(O| model) = -3.615577E+00
prob(O| model) = 0.026901
…
——————————————————————–
黑體部分是最終的觀察序列的概率結果，即本例中的Pr(觀察序列|HMM) = 0.026901。
但是，在原文中點Run按鈕后，結果卻是：Probability of this model = 0.027386915。
這其中的差別到底在哪里？我們來仔細觀察一下中間運行過程：
在初始化亦t=1時刻的局部概率計算兩個是一致的，沒有問題。但是，t=2時，在隱藏狀態“Sunny”的局部概率是不一致的。英文原文給出的例子的運行結果是：
Alpha = (((0.37800002*0.5) + (0.0425*0.375) + (0.010000001*0.125)) * 0.15) = 0.03092813
而UMDHMM給出的結果是：
——————————————————————–
a[1][1] * A[1][1] = 0.378000 * 0.500000 = 0.189000
sum = 0.189000
a[1][2] * A[2][1] = 0.042500 * 0.250000 = 0.010625
sum = 0.199625
a[1][3] * A[3][1] = 0.010000 * 0.250000 = 0.002500
sum = 0.202125
a[2][1] = sum * b[1][3]] = 0.202125 * 0.150000 = 0.030319
——————————————————————–
區別就在于狀態轉移概率的選擇上，原文選擇的是狀態轉移矩陣中的第一行，而UMDHMM選擇的則是狀態轉移矩陣中的第一列。如果從原文給出的狀態轉移矩陣來看，第一行代表的是從前一時刻的狀態“Sunny”分別到當前時刻的狀態“Sunny”，“Cloudy”，“Rainy”的概率；而第一列代表的是從前一時刻的狀態“Sunny”，“Cloudy”，“Rainy”分別到當前時刻狀態“Sunny”的概率。這樣看來似乎原文的計算過程有誤，讀者不妨多試幾個例子看看，前向算法這一章就到此為止了。
HMM學習最佳范例六：維特比算法
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)
對于一個特殊的隱馬爾科夫模型(HMM)及一個相應的觀察序列，我們常常希望能找到生成此序列最可能的隱藏狀態序列。
1.窮舉搜索
我們使用下面這張網格圖片來形象化的說明隱藏狀態和觀察狀態之間的關系：
我們可以通過列出所有可能的隱藏狀態序列并且計算對于每個組合相應的觀察序列的概率來找到最可能的隱藏狀態序列。最可能的隱藏狀態序列是使下面這個概率最大的組合：
Pr（觀察序列|隱藏狀態的組合）
例如，對于網格中所顯示的觀察序列，最可能的隱藏狀態序列是下面這些概率中最大概率所對應的那個隱藏狀態序列：
Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . Pr(dry,damp,soggy | rainy,rainy,rainy)
這種方法是可行的，但是通過窮舉計算每一個組合的概率找到最可能的序列是極為昂貴的。與前向算法類似，我們可以利用這些概率的時間不變性來降低計算復雜度。
2.使用遞歸降低復雜度
給定一個觀察序列和一個隱馬爾科夫模型（HMM），我們將考慮遞歸地尋找最有可能的隱藏狀態序列。我們首先定義局部概率,它是到達網格中的某個特殊的中間狀態時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
這些局部概率與前向算法中所計算的局部概率是不同的，因為它們表示的是時刻t時到達某個狀態最可能的路徑的概率，而不是所有路徑概率的總和。
2a.局部概率’s和局部最佳途徑
考慮下面這個網格，它顯示的是天氣狀態及對于觀察序列干燥，濕潤及濕透的一階狀態轉移情況：
對于網格中的每一個中間及終止狀態，都有一個到達該狀態的最可能路徑。舉例來說，在t=3時刻的3個狀態中的每一個都有一個到達此狀態的最可能路徑，或許是這樣的：
我們稱這些路徑局部最佳路徑(partial best paths)。其中每個局部最佳路徑都有一個相關聯的概率，即局部概率或。與前向算法中的局部概率不同，是到達該狀態（最可能）的一條路徑的概率。
因而(i,t)是t時刻到達狀態i的所有序列概率中最大的概率，而局部最佳路徑是得到此最大概率的隱藏狀態序列。對于每一個可能的i和t值來說，這一類概率（及局部路徑）均存在。
特別地，在t=T時每一個狀態都有一個局部概率和一個局部最佳路徑。這樣我們就可以通過選擇此時刻包含最大局部概率的狀態及其相應的局部最佳路徑來確定全局最佳路徑（最佳隱藏狀態序列）。
2b.計算t=1時刻的局部概率’s
我們計算的局部概率是作為最可能到達我們當前位置的路徑的概率（已知的特殊知識如觀察概率及前一個狀態的概率）。當t=1的時候，到達某狀態的最可能路徑明顯是不存在的；但是，我們使用t=1時的所處狀態的初始概率及相應的觀察狀態k1的觀察概率計算局部概率；即
——與前向算法類似，這個結果是通過初始概率和相應的觀察概率相乘得出的。
2c.計算t>1時刻的局部概率’s
現在我們來展示如何利用t-1時刻的局部概率計算t時刻的局部概率。
考慮如下的網格：
我們考慮計算t時刻到達狀態X的最可能的路徑；這條到達狀態X的路徑將通過t-1時刻的狀態A，B或C中的某一個。
因此，最可能的到達狀態X的路徑將是下面這些路徑的某一個
（狀態序列），…，A，X
（狀態序列），…，B，X
或 （狀態序列），…，C，X
我們想找到路徑末端是AX,BX或CX并且擁有最大概率的路徑。
回顧一下馬爾科夫假設：給定一個狀態序列，一個狀態發生的概率只依賴于前n個狀態。特別地，在一階馬爾可夫假設下，狀態X在一個狀態序列后發生的概率只取決于之前的一個狀態，即
Pr (到達狀態A最可能的路徑) .Pr (X | A) . Pr (觀察狀態 | X)
與此相同，路徑末端是AX的最可能的路徑將是到達A的最可能路徑再緊跟X。相似地，這條路徑的概率將是：
Pr (到達狀態A最可能的路徑) .Pr (X | A) . Pr (觀察狀態 | X)
因此，到達狀態X的最可能路徑概率是：
其中第一項是t-1時刻的局部概率，第二項是狀態轉移概率以及第三項是觀察概率。
泛化上述公式，就是在t時刻，觀察狀態是kt，到達隱藏狀態i的最佳局部路徑的概率是：
這里，我們假設前一個狀態的知識（局部概率）是已知的，同時利用了狀態轉移概率和相應的觀察概率之積。然后，我們就可以在其中選擇最大的概率了（局部概率）。
2d.反向指針，’s
考慮下面這個網格
在每一個中間及終止狀態我們都知道了局部概率，(i,t)。然而我們的目標是在給定一個觀察序列的情況下尋找網格中最可能的隱藏狀態序列——因此，我們需要一些方法來記住網格中的局部最佳路徑。
回顧一下我們是如何計算局部概率的，計算t時刻的’s我們僅僅需要知道t-1時刻的’s。在這個局部概率計算之后，就有可能記錄前一時刻哪個狀態生成了(i,t)——也就是說，在t-1時刻系統必須處于某個狀態，該狀態導致了系統在t時刻到達狀態i是最優的。這種記錄（記憶）是通過對每一個狀態賦予一個反向指針完成的，這個指針指向最優的引發當前狀態的前一時刻的某個狀態。
形式上，我們可以寫成如下的公式
其中argmax運算符是用來計算使括號中表達式的值最大的索引j的。
請注意這個表達式是通過前一個時間步驟的局部概率’s和轉移概率計算的，并不包括觀察概率（與計算局部概率’s本身不同）。這是因為我們希望這些’s能回答這個問題“如果我在這里，最可能通過哪條路徑到達下一個狀態？”——這個問題與隱藏狀態有關，因此與觀察概率有關的混淆（矩陣）因子是可以被忽略的。
2e.維特比算法的優點
使用Viterbi算法對觀察序列進行解碼有兩個重要的優點：
1. 通過使用遞歸減少計算復雜度——這一點和前向算法使用遞歸減少計算復雜度是完全類似的。
2.維特比算法有一個非常有用的性質，就是對于觀察序列的整個上下文進行了最好的解釋（考慮）。事實上，尋找最可能的隱藏狀態序列不止這一種方法，其他替代方法也可以，譬如，可以這樣確定如下的隱藏狀態序列：
其中
這里，采用了“自左向右”的決策方式進行一種近似的判斷，其對于每個隱藏狀態的判斷是建立在前一個步驟的判斷的基礎之上（而第一步從隱藏狀態的初始向量開始）。
這種做法，如果在整個觀察序列的中部發生“噪音干擾”時，其最終的結果將與正確的答案嚴重偏離。
相反， 維特比算法在確定最可能的終止狀態前將考慮整個觀察序列，然后通過指針“回溯”以確定某個隱藏狀態是否是最可能的隱藏狀態序列中的一員。這是非常有用的，因為這樣就可以孤立序列中的“噪音”，而這些“噪音”在實時數據中是很常見的。
3.小結
維特比算法提供了一種有效的計算方法來分析隱馬爾科夫模型的觀察序列，并捕獲最可能的隱藏狀態序列。它利用遞歸減少計算量，并使用整個序列的上下文來做判斷，從而對包含“噪音”的序列也能進行良好的分析。
在使用時，維特比算法對于網格中的每一個單元(cell)都計算一個局部概率，同時包括一個反向指針用來指示最可能的到達該單元的路徑。當完成整個計算過程后，首先在終止時刻找到最可能的狀態，然后通過反向指針回溯到t=1時刻，這樣回溯路徑上的狀態序列就是最可能的隱藏狀態序列了。
1、維特比算法的形式化定義
維特比算法可以形式化的概括為：
對于每一個i，i = 1，… ，n，令：
——這一步是通過隱藏狀態的初始概率和相應的觀察概率之積計算了t=1時刻的局部概率。
對于t=2，…，T和i=1，…，n,令：
——這樣就確定了到達下一個狀態的最可能路徑，并對如何到達下一個狀態做了記錄。具體來說首先通過考察所有的轉移概率與上一步獲得的最大的局部概率之積，然后記錄下其中最大的一個，同時也包含了上一步觸發此概率的狀態。
令：
——這樣就確定了系統完成時(t=T)最可能的隱藏狀態。
對于t=T-1，…，1
令：
——這樣就可以按最可能的狀態路徑在整個網格回溯。回溯完成時，對于觀察序列來說，序列i1 … iT就是生成此觀察序列的最可能的隱藏狀態序列。
2.計算單獨的’s和’s
維特比算法中的局部概率’s的計算與前向算法中的局部概率’s的很相似。下面這幅圖表顯示了’s和’s的計算細節，可以對比一下前向算法3中的計算局部概率’s的那幅圖表：
唯一不同的是前向算法中計算局部概率’s時的求和符號（）在維特比算法中計算局部概率’s時被替換為max——這一個重要的不同也說明了在維特比算法中我們選擇的是到達當前狀態的最可能路徑，而不是總的概率。我們在維特比算法中維護了一個“反向指針”記錄了到達當前狀態的最佳路徑，即在計算’s時通過argmax運算符獲得。
總結(Summary)
對于一個特定的隱馬爾科夫模型，維特比算法被用來尋找生成一個觀察序列的最可能的隱藏狀態序列。我們利用概率的時間不變性，通過避免計算網格中每一條路徑的概率來降低問題的復雜度。維特比算法對于每一個狀態(t>1)都保存了一個反向指針()，并在每一個狀態中存儲了一個局部概率()。
局部概率是由反向指針指示的路徑到達某個狀態的概率。
當t=T時，維特比算法所到達的這些終止狀態的局部概率’s是按照最優（最可能）的路徑到達該狀態的概率。因此，選擇其中最大的一個，并回溯找出所隱藏的狀態路徑，就是這個問題的最好答案。
關于維特比算法，需要著重強調的一點是它不是簡單的對于某個給定的時間點選擇最可能的隱藏狀態，而是基于全局序列做決策——因此，如果在觀察序列中有一個“非尋常”的事件發生，對于維特比算法的結果也影響不大。
這在語音處理中是特別有價值的，譬如當某個單詞發音的一個中間音素出現失真或丟失的情況時，該單詞也可以被識別出來。
仍然需要說明的是，本節不是這個系列的翻譯，而是作為維特比算法這一章的補充，將UMDHMM這個C語言版本的HMM工具包中的維特比算法程序展示給大家，并運行包中所附帶的例子。關于UMDHMM這個工具包的介紹，大家可以參考前向算法4中的介紹。
維特比算法程序示例如下（在viterbi.c中):
void Viterbi(HMM *phmm, int T, int *O, double **delta, int **psi,int *q, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
int maxvalind;
double maxval, val;
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
{
delta[1][i] = phmm->pi[i] * (phmm->B[i][O[1]]);
psi[1][i] = 0;
}
/* 2. Recursion */
for (t = 2; t <= T; t++)
{
for (j = 1; j <= phmm->N; j++)
{
maxval = 0.0;
maxvalind = 1;
for (i = 1; i <= phmm->N; i++)
{
val = delta[t-1][i]*(phmm->A[i][j]);
if (val > maxval)
{
maxval = val;
maxvalind = i;
}
}
delta[t][j] = maxval*(phmm->B[j][O[t]]);
psi[t][j] = maxvalind;
}
}
/* 3. Termination */
*pprob = 0.0;
q[T] = 1;
for (i = 1; i <= phmm->N; i++)
{
if (delta[T][i] > *pprob)
{
*pprob = delta[T][i];
q[T] = i;
}
}
/* 4. Path (state sequence) backtracking */
for (t = T – 1; t >= 1; t–)
q[t] = psi[t+1][q[t+1]];
}
在UMDHMM包中所生成的4個可執行程序中，testvit是用來測試維特比算法的， 對于給定的觀察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態序列。這里我們利用UMDHMM包中test.hmm和test.seq來測試維特比算法，關于這兩個文件，具體如下：
test.hmm：
——————————————————————–
M= 2
N= 3
A:
0.333 0.333 0.333
0.333 0.333 0.333
0.333 0.333 0.333
B:
0.5 0.5
0.75 0.25
0.25 0.75
pi:
0.333 0.333 0.333
——————————————————————–
test.seq：
——————————————————————–
T= 10
1 1 1 1 2 1 2 2 2 2
——————————————————————–
對于維特比算法的測試程序testvit來說，運行：
testvit test.hmm test.seq
結果如下：
————————————
Viterbi using direct probabilities
Viterbi MLE log prob = -1.387295E+01
Optimal state sequence:
T= 10
2 2 2 2 3 2 3 3 3 3
————————————
Viterbi using log probabilities
Viterbi MLE log prob = -1.387295E+01
Optimal state sequence:
T= 10
2 2 2 2 3 2 3 3 3 3
————————————
The two log probabilites and optimal state sequences
should identical (within numerical precision).
序列“2 2 2 2 3 2 3 3 3 3”就是最終所找到的隱藏狀態序列。好了，維特比算法這一章就到此為止了。
HMM學習最佳范例七：前向-后向算法1
分類 隱馬爾科夫模型?
七、前向-后向算法(Forward-backward algorithm)
根據觀察序列生成隱馬爾科夫模型(Generating a HMM from a sequence of obersvations)
與HMM模型相關的“有用”的問題是評估（前向算法）和解碼（維特比算法）——它們一個被用來測量一個模型的相對適用性，另一個被用來推測模型隱藏的部分在做什么（“到底發生了”什么）。可以看出它們都依賴于隱馬爾科夫模型（HMM）參數這一先驗知識——狀態轉移矩陣，混淆（觀察）矩陣，以及向量（初始化概率向量）。
然而，在許多實際問題的情況下這些參數都不能直接計算的，而要需要進行估計——這就是隱馬爾科夫模型中的學習問題。前向-后向算法就可以以一個觀察序列為基礎來進行這樣的估計，而這個觀察序列來自于一個給定的集合，它所代表的是一個隱馬爾科夫模型中的一個已知的隱藏集合。
一個例子可能是一個龐大的語音處理數據庫，其底層的語音可能由一個馬爾可夫過程基于已知的音素建模的，而其可以觀察的部分可能由可識別的狀態（可能通過一些矢量數據表示）建模的，但是沒有（直接）的方式來獲取隱馬爾科夫模型（HMM）參數。
前向-后向算法并非特別難以理解，但自然地比前向算法和維特比算法更復雜。由于這個原因，這里就不詳細講解前向-后向算法了（任何有關HMM模型的參考文獻都會提供這方面的資料的）。
總之，前向-后向算法首先對于隱馬爾科夫模型的參數進行一個初始的估計（這很可能是完全錯誤的），然后通過對于給定的數據評估這些參數的的價值并減少它們所引起的錯誤來重新修訂這些HMM參數。從這個意義上講，它是以一種梯度下降的形式尋找一種錯誤測度的最小值。
之所以稱其為前向-后向算法，主要是因為對于網格中的每一個狀態，它既計算到達此狀態的“前向”概率（給定當前模型的近似估計），又計算生成此模型最終狀態的“后向”概率（給定當前模型的近似估計）。 這些都可以通過利用遞歸進行有利地計算，就像我們已經看到的。可以通過利用近似的HMM模型參數來提高這些中間概率進行調整，而這些調整又形成了前向-后向算法迭代的基礎。
注：關于前向-后向算法，原文只講了這么多，后繼我將按自己的理解補充一些內容。
要理解前向-后向算法，首先需要了解兩個算法：后向算法和EM算法。后向算法是必須的，因為前向-后向算法就是利用了前向算法與后向算法中的變量因子，其得名也因于此；而EM算法不是必須的，不過由于前向-后向算法是EM算法的一個特例，因此了解一下EM算法也是有好處的，說實話，對于EM算法，我也是云里霧里的。好了，廢話少說，我們先談談后向算法。
1、后向算法（Backward algorithm）
其實如果理解了前向算法，后向算法也是比較好理解的，這里首先重新定義一下前向算法中的局部概率at(i)，稱其為前向變量，這也是為前向-后向算法做點準備：
相似地，我們也可以定義一個后向變量Bt(i)（同樣可以理解為一個局部概率）：
后向變量(局部概率)表示的是已知隱馬爾科夫模型及t時刻位于隱藏狀態Si這一事實，從t+1時刻到終止時刻的局部觀察序列的概率。同樣與前向算法相似，我們可以從后向前（故稱之為后向算法）遞歸地計算后向變量：
1）初始化，令t=T時刻所有狀態的后向變量為1：
2）歸納，遞歸計算每個時間點，t=T-1,T-2,…,1時的后向變量：
這樣就可以計算每個時間點上所有的隱藏狀態所對應的后向變量，如果需要利用后向算法計算觀察序列的概率，只需將t=1時刻的后向變量（局部概率）相加即可。下圖顯示的是t+1時刻與t時刻的后向變量之間的關系：
上述主要參考自HMM經典論文《A tutorial on Hidden Markov Models and selected applications in speech recognition》。下面我們給出利用后向算法計算觀察序列概率的程序示例，這個程序仍然來自于UMDHMM。
后向算法程序示例如下（在backward.c中):
void Backward(HMM *phmm, int T, int *O, double **beta, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
double sum;
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
beta[T][i] = 1.0;
/* 2. Induction */
for (t = T - 1; t >= 1; t--)
{
for (i = 1; i <= phmm->N; i++)
{
sum = 0.0;
for (j = 1; j <= phmm->N; j++)
sum += phmm->A[i][j] *
(phmm->B[j][O[t+1]])*beta[t+1][j];
beta[t][i] = sum;
}
}
/* 3. Termination */
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += beta[1][i];
}
好了，后向算法就到此為止了，下一節我們粗略的談談EM算法。
前向-后向算法是Baum于1972年提出來的，又稱之為Baum-Welch算法，雖然它是EM(Expectation-Maximization)算法的一個特例，但EM算法卻是于1977年提出的。那么為什么說前向-后向算法是EM算法的一個特例呢？這里有兩點需要說明一下。
第一，1977年A. P. Dempster、N. M. Laird、 D. B. Rubin在其論文“Maximum Likelihood from Incomplete Data via the EM Algorithm”中首次提出了EM算法的概念，但是他們也在論文的介紹中提到了在此之前就有一些學者利用了EM算法的思想解決了一些特殊問題，其中就包括了Baum在70年代初期的相關工作，只是這類方法沒有被總結而已，他們的工作就是對這類解決問題的方法在更高的層次上定義了一個完整的EM算法框架。
第二，對于前向-后向算法與EM算法的關系，此后在許多與HMM或EM相關的論文里都被提及，其中賈里尼克（Jelinek）老先生在1997所著的書“Statistical Methods for Speech Recognition”中對于前向-后向算法與EM算法的關系進行了完整的描述，讀者有興趣的話可以找來這本書讀讀。
關于EM算法的講解，網上有很多，這里我就不獻丑了，直接拿目前搜索“EM算法”在Google排名第一的文章做了參考，希望讀者不要拍磚：
EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整數據集中對參數進行 MLE 估計，是一種非常簡單實用的學習算法。這種方法可以廣泛地應用于處理缺損數據，截尾數據，帶有討厭數據等所謂的不完全數據(incomplete data)。
假定集合Z = (X,Y)由觀測數據 X 和未觀測數據Y 組成，Z = (X,Y)和 X 分別稱為完整數據和不完整數據。假設Z的聯合概率密度被參數化地定義為P(X，Y|Θ)，其中Θ 表示要被估計的參數。Θ 的最大似然估計是求不完整數據的對數似然函數L(X;Θ)的最大值而得到的：
L(Θ; X )= log p(X |Θ) = ∫log p(X ,Y |Θ)dY ；(1)
EM算法包括兩個步驟：由E步和M步組成，它是通過迭代地最大化完整數據的對數似然函數Lc( X;Θ )的期望來最大化不完整數據的對數似然函數，其中：
Lc(X;Θ) =log p(X，Y |Θ) ； (2)
假設在算法第t次迭代后Θ 獲得的估計記為Θ(t ) ，則在（t+1）次迭代時，
E-步：計算完整數據的對數似然函數的期望，記為：
Q(Θ |Θ (t) ) = E{Lc(Θ;Z)|X;Θ(t) }； (3)
M-步：通過最大化Q(Θ |Θ(t) ) 來獲得新的Θ 。
通過交替使用這兩個步驟，EM算法逐步改進模型的參數，使參數和訓練樣本的似然概率逐漸增大，最后終止于一個極大點。
直觀地理解EM算法，它也可被看作為一個逐次逼近算法：事先并不知道模型的參數，可以隨機的選擇一套參數或者事先粗略地給定某個初始參數λ0 ，確定出對應于這組參數的最可能的狀態，計算每個訓練樣本的可能結果的概率，在當前的狀態下再由樣本對參數修正，重新估計參數λ ，并在新的參數下重新確定模型的狀態，這樣，通過多次的迭代，循環直至某個收斂條件滿足為止，就可以使得模型的參數逐漸逼近真實參數。
EM算法的主要目的是提供一個簡單的迭代算法計算后驗密度函數，它的最大優點是簡單和穩定，但容易陷入局部最優。
參考原文見：http://49805085.spaces.live.com/Blog/cns!145C40DDDB4C6E5!670.entry
注意上面那段粗體字，讀者如果覺得EM算法不好理解的話，就記住這段粗體字的意思吧！
有了后向算法和EM算法的預備知識，下一節我們就正式的談一談前向-后向算法。
隱馬爾科夫模型（HMM）的三個基本問題中，第三個HMM參數學習的問題是最難的，因為對于給定的觀察序列O，沒有任何一種方法可以精確地找到一組最優的隱馬爾科夫模型參數（A、B、）使P(O|)最大。因而，學者們退而求其次，不能使P(O|)全局最優，就尋求使其局部最優（最大化）的解決方法，而前向-后向算法（又稱之為Baum-Welch算法）就成了隱馬爾科夫模型學習問題的一種替代（近似）解決方法。
我們首先定義兩個變量。給定觀察序列O及隱馬爾科夫模型，定義t時刻位于隱藏狀態Si的概率變量為：
回顧一下第二節中關于前向變量at(i)及后向變量Bt(i)的定義，我們可以很容易地將上式用前向、后向變量表示為：
其中分母的作用是確保：
給定觀察序列O及隱馬爾科夫模型，定義t時刻位于隱藏狀態Si及t+1時刻位于隱藏狀態Sj的概率變量為：
該變量在網格中所代表的關系如下圖所示：
同樣，該變量也可以由前向、后向變量表示：
而上述定義的兩個變量間也存在著如下關系：
如果對于時間軸t上的所有相加，我們可以得到一個總和，它可以被解釋為從其他隱藏狀態訪問Si的期望值（網格中的所有時間的期望），或者，如果我們求和時不包括時間軸上的t=T時刻，那么它可以被解釋為從隱藏狀態Si出發的狀態轉移期望值。相似地，如果對在時間軸t上求和（從t=1到t=T-1），那么該和可以被解釋為從狀態Si到狀態Sj的狀態轉移期望值。即：
上一節我們定義了兩個變量及相應的期望值，本節我們利用這兩個變量及其期望值來重新估計隱馬爾科夫模型（HMM）的參數，A及B：
如果我們定義當前的HMM模型為，那么可以利用該模型計算上面三個式子的右端；我們再定義重新估計的HMM模型為，那么上面三個式子的左端就是重估的HMM模型參數。Baum及他的同事在70年代證明了因此如果我們迭代地的計算上面三個式子，由此不斷地重新估計HMM的參數，那么在多次迭代后可以得到的HMM模型的一個最大似然估計。不過需要注意的是，前向-后向算法所得的這個結果（最大似然估計）是一個局部最優解。
關于前向-后向算法和EM算法的具體關系的解釋，大家可以參考HMM經典論文《A tutorial on Hidden Markov Models and selected applications in speech recognition》，這里就不詳述了。下面我們給出UMDHMM中的前向-后向算法示例，這個算法比較復雜，這里只取主函數，其中所引用的函數大家如果感興趣的話可以自行參考UMDHMM。
前向-后向算法程序示例如下（在baum.c中):
void BaumWelch(HMM *phmm, int T, int *O, double **alpha, double **beta, double **gamma, int *pniter, double *plogprobinit, double *plogprobfinal)
{
int i, j, k;
int t, l = 0;
double logprobf, logprobb, threshold;
double numeratorA, denominatorA;
double numeratorB, denominatorB;
double ***xi, *scale;
double delta, deltaprev, logprobprev;
deltaprev = 10e-70;
xi = AllocXi(T, phmm->N);
scale = dvector(1, T);
ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
*plogprobinit = logprobf; /* log P(O |intial model) */
BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
ComputeGamma(phmm, T, alpha, beta, gamma);
ComputeXi(phmm, T, O, alpha, beta, xi);
logprobprev = logprobf;
do
{
/* reestimate frequency of state i in time t=1 */
for (i = 1; i <= phmm->N; i++)
phmm->pi[i] = .001 + .999*gamma[1][i];
/* reestimate transition matrix and symbol prob in
each state */
for (i = 1; i <= phmm->N; i++)
{
denominatorA = 0.0;
for (t = 1; t <= T - 1; t++)
denominatorA += gamma[t][i];
for (j = 1; j <= phmm->N; j++)
{
numeratorA = 0.0;
for (t = 1; t <= T - 1; t++)
numeratorA += xi[t][i][j];
phmm->A[i][j] = .001 +
.999*numeratorA/denominatorA;
}
denominatorB = denominatorA + gamma[T][i];
for (k = 1; k <= phmm->M; k++)
{
numeratorB = 0.0;
for (t = 1; t <= T; t++)
{
if (O[t] == k)
numeratorB += gamma[t][i];
}
phmm->B[i][k] = .001 +
.999*numeratorB/denominatorB;
}
}
ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
ComputeGamma(phmm, T, alpha, beta, gamma);
ComputeXi(phmm, T, O, alpha, beta, xi);
/* compute difference between log probability of
two iterations */
delta = logprobf - logprobprev;
logprobprev = logprobf;
l++;
}
while (delta > DELTA); /* if log probability does not
change much, exit */
*pniter = l;
*plogprobfinal = logprobf; /* log P(O|estimated model) */
FreeXi(xi, T, phmm->N);
free_dvector(scale, 1, T);
}
前向-后向算法就到此為止了。
八、總結(Summary)
通常，模式并不是單獨的出現，而是作為時間序列中的一個部分——這個過程有時候可以被輔助用來對它們進行識別。在基于時間的進程中，通常都會使用一些假設——一個最常用的假設是進程的狀態只依賴于前面N個狀態——這樣我們就有了一個N階馬爾科夫模型。最簡單的例子是N = 1。
存在很多例子，在這些例子中進程的狀態（模式）是不能夠被直接觀察的，但是可以非直接地，或者概率地被觀察為模式的另外一種集合——這樣我們就可以定義一類隱馬爾科夫模型——這些模型已被證明在當前許多研究領域，尤其是語音識別領域具有非常大的價值。
在實際的過程中這些模型提出了三個問題都可以得到立即有效的解決，分別是：
* 評估：對于一個給定的隱馬爾科夫模型其生成一個給定的觀察序列的概率是多少。前向算法可以有效的解決此問題。
* 解碼：什么樣的隱藏（底層）狀態序列最有可能生成一個給定的觀察序列。維特比算法可以有效的解決此問題。
* 學習：對于一個給定的觀察序列樣本，什么樣的模型最可能生成該序列——也就是說，該模型的參數是什么。這個問題可以通過使用前向-后向算法解決。
隱馬爾科夫模型（HMM）在分析實際系統中已被證明有很大的價值；它們通常的缺點是過于簡化的假設，這與馬爾可夫假設相關——即一個狀態只依賴于前一個狀態，并且這種依賴關系是獨立于時間之外的（與時間無關）。
關于隱馬爾科夫模型的完整論述，可參閱：
L R Rabiner and B H Juang, `An introduction to HMMs’, iEEE ASSP Magazine, 3, 4-16.
全文完！
后記：這個翻譯系列終于可以告一段落了，從6月2日起至今，歷史四個多月，期間斷斷續續翻譯并夾雜些自己個人的理解，希望這個系列對于HMM的學習者能有些用處，我個人也就很滿足了。接下來，我會結合HMM在自然語言處理中的一些典型應用，譬如詞性標注、中文分詞等，從實踐的角度講講自己的理解，歡迎大家繼續關注52nlp。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
HMM在自然語言處理中的應用一：詞性標注1
詞性標注（Part-of-Speech tagging 或 POS tagging)是指對于句子中的每個詞都指派一個合適的詞性，也就是要確定每個詞是名詞、動詞、形容詞或其他詞性的過程，又稱詞類標注或者簡稱標注。詞性標注是自然語言處理中的一項基礎任務，在語音識別、信息檢索及自然語言處理的許多領域都發揮著重要的作用。因此，在關于自然語言處理的書籍中，都會將詞性標注單列一章重點講解，對此有興趣的讀者可參考《自然語言處理綜論》第一版第8章或《統計自然語言處理基礎》第10章，本文部分內容也參考自這兩本自然語言處理的經典書籍。
我們以Brown語料庫中的句子為例，詞性標注的任務指的是，對于輸入句子：
The Fulton County Grand Jury said Friday an investigation of Atlanta’s recent primary election produced “ no evidence ” that any irregularities took place .
需要為句子中的每個單詞標上一個合適的詞性標記，既輸出含有詞性標記句子：
The/at-tl Fulton/np-tl County/nn-tl Grand/jj-tl Jury/nn-tl said/vbd Friday/nr an/at investigation/nn of/in Atlanta’s/np$ recent/jj primary/jj election/nn produced/vbn “/“ no/at evidence/nn ”/” that/cs any/dti irregularities/nns took/vbd place/nn ./.
在進行詞性標注時，前提條件之一便是選擇什么樣的標記集？Brown語料庫標記集有87個，而英語中其他標記集多數是從Brown語料庫中的標記集發展而來的，如最常用的Penn Treebank標記集，包含45個標記，是小標記集。漢語標記集中常用的有北大《人民日報》語料庫詞性標記集、計算所漢語詞性標記集等。
關于Brwon語料庫標記集的詳細信息可參考：
http://www.comp.leeds.ac.uk/amalgam/tagsets/brown.html
關于計算所漢語詞性標記集的詳細信息可參考：
http://www.ictclas.org/ictclas_docs_003.html
在確定使用某個標記集之后，下一步便是如何進行詞性標注了！如果每個單詞僅僅對應一個詞性標記，那么詞性標注就非常容易了。但是語言本身的復雜性導致了并非每一個單詞只有一個詞性標記，而存在一部分單詞有多個詞性標記可以選擇，如book這個單詞，既可以是動詞（book that flight)，也可以是名詞(hand me that book)，因此，詞性標注的關鍵問題就是消解這樣的歧義，也就是對于句子中的每一個單詞在一定的上下文中選擇恰如其分的標記。
關于詞性標注歧義問題，對Brown語料庫進行統計，按歧義程度排列的詞型數目（The number of word types in Brown corpus by degree of ambiguity）DeRose(1988)給出了如下的標記歧義表：
無歧義（Unambiguous）只有1個標記： 35,340
歧義（Ambiguous） 有2-7個標記： 4,100
2個標記：3,764
3個標記：264
4個標記：61
5個標記：12
6個標記：2
7個標記：1
可見英語中的大多數單詞都是沒有歧義的，也就是這些單詞只有一個單獨的標記。但是，英語中的最常用單詞很多都是有歧義的，因此，任何一個詞性標注算法的關鍵歸根結底還是如何解決詞性標注中的歧義消解問題。
大多數的標注算法可以歸納為三類：一類是基于規則的標注算法（rule-based tagger)，一類是隨機標注算法（stochastic tagger)，最后一類是混合型的標注算法。基于規則的標注算法一般都包括一個手工制作的歧義消解規則庫；隨機標注算法一般會使用一個訓練語料庫來計算在給定的上下文中某一給定單詞具有某一給定標記的概率，如基于HMM的標注算法；而混合型標注算法具有上述兩種算法的特點，如TBL標注算法。
關于詞性標注的基本問題本節就到此為止了，也算是一點準備工作，下一節我們將進入與HMM相關的詞性標注問題的正題！
HMM在自然語言處理中的應用一：詞性標注2
上一節我們對自然語言處理中詞性標注的基本問題進行了描述，從本節開始我們將詳細介紹HMM與詞性標注的關系以及如何利用HMM進行詞性標注。首先回顧一下隱馬爾科夫模型(HMM)的定義和三大基本問題，并由此與詞性標注的基本問題進行一個對比。
隱馬爾科夫模型(HMM)是什么？說白了，就是一個數學模型，用一堆數學符號和參數表示而已，包括隱藏狀態集合、觀察符號集合、初始概率向量,狀態轉移矩陣A，混淆矩陣B。
隱馬爾科夫模型(HMM)的三大基本問題與解決方案包括：
1. 對于一個觀察序列匹配最可能的系統——評估，使用前向算法（forward algorithm）解決；
2. 對于已生成的一個觀察序列，確定最可能的隱藏狀態序列——解碼，使用維特比算法（Viterbi algorithm）解決；
3. 對于已生成的觀察序列，決定最可能的模型參數——學習，使用前向-后向算法（forward-backward algorithm）解決。
回顧完HMM，這里暫且先放下詞性標注，瞎扯一下數學建模。
記得以前在大學里參加數學建模競賽，本著拿獎的目的，稀里糊涂的就和幾個同學一起組隊參加，并沒有仔細考慮過數學建模的本質到底是什么。反正感覺和平常作數學題不同，數學題都是定義好的，只需給出一個解答就行，而數學建模給的問題都很實際，并沒有按數學題的形式出題，不僅要把這個實際問題轉化為一個合理的數學問題，還要給出一個解答，由于自己概括問題的能力有限，在數學建模競賽上也基本毫無建樹。
我在Google上搜索了一下數學建模的定義，有好幾種解釋，覺得下面這個最符合本質：
把現實世界中的實際問題加以提煉，抽象為數學模型，求出模型的 解，驗證模型的合理性，并用該數學模型所提供的解答來解釋現實問題，我們把 數學知識的這一應用過程稱為數學建模。
好了，這就是數學建模，如果把詞性標注問題作為一個數學建模的題目來出，該如何作答？套用上面的定義，可以解釋為：
1、對詞性標注問題進行提煉：詞性標注本質上是一個分類問題，對于句子中的每一個單詞W，找到一個合適的詞類類別T，也就是詞性標記，不過詞性標注考慮的是整體標記的好壞，既整個句子的序列標記問題；
2、抽象為數學模型：對于分類問題，有很多現成的數學模型和框架可以套用，譬如HMM、最大熵模型、條件隨機場、SVM等等；
3、求出模型的解：上述模型和框架一旦可以套用，如何求解就基本確定好了，就像HMM中不僅描述了三大基本問題，并相應的給出了求解方案一樣；
4、驗證模型的合理性：就是詞性標注的準確率等評測指標了，在自然語言處理中屬于必不可少的評測環節；
5、解釋現實問題：如果詞性標注的各項指標夠好，就可以利用該數學模型構造一個詞性標注器來解決某種語言的標注問題了！
詞性標注的數學建模就這樣了，自然語言處理中的多數分類問題與此相似。這里講得是HMM的應用，所以其他模型暫且不表，以后有機會有條件了我們再說。
如何建立一個與詞性標注問題相關聯的HMM模型？首先必須確定HMM模型中的隱藏狀態和觀察符號，也可以說成觀察狀態，由于我們是根據輸入句子輸出詞性序列，因此可以將詞性標記序列作為隱藏狀態，而把句子中的單詞作為觀察符號，那么對于Brown語料庫來說，就有87個隱藏狀態（標記集）和將近4萬多個觀察符號（詞型）。
確定了隱藏狀態和觀察符號，我們就可以根據訓練語料庫的性質來學習HMM的各項參數了。如果訓練語料已經做好了標注，那么學習這個HMM模型的問題就比較簡單，只需要計數就可以完成HMM各個模型參數的統計，如標記間的狀態轉移概率可以通過如下公式求出：
P（Ti|Tj) = C(Tj,Tk)/C(Tj)
而每個狀態（標記）隨對應的符號（單詞）的發射概率可由下式求出：
P（Wm|Tj) = C(Wm,Tj)/C(Tj)
其中符號C代表的是其括號內因子在語料庫中的計數。
如果訓練語料庫沒有標注，那么HMM的第三大基本問題“學習”就可以派上用處了，通過一些輔助資源，如詞典等，利用前向－后向算法也可以學習一個HMM模型，不過這個模型比之有標注語料庫訓練出來的模型要差一些。
總之，我們已經訓練了一個與語料庫對應的HMM詞性標注模型，那么如何利用這個模型來解決詞性標注問題呢？當然是采用維特比算法解碼了， HMM模型第二大基本問題就是專門來解決這個問題的。
說完了如何建模，下一節我們將利用UMDHMM這個HMM工具包來實現一個toy版本的HMM詞性標注器。
HMM在自然語言處理中的應用一：詞性標注3
原計劃這一節講解如何利用UMDHMM這個HMM工具包來實現一個toy版本的HMM詞性標注器，自己也寫了幾個相關的小腳本，不過由于處理過程中需要借用Philip Resnik教授寫的另外幾個小腳本，所以這里先介紹一下他的工作。
Resnik教授利用UMDHMM寫了一個關于如何使用隱馬爾科夫模型的介紹和練習，主要目標包括以下四個方面：
1、 在一個“似英語”的文本上訓練一個HMM模型（Train an HMM on a sample of English-like text ）；
2、對于訓練好的模型進行檢測（Inspect the resulting model）；
3、根據訓練好的模型隨機生成句子（Generate sentences at random from the model）；
4、對于測試句子尋找最可能隱藏狀態序列（Create test sentences and find the most likely hidden state sequence）。
我的工作和Resnik教授的主要區別再于，他的訓練集沒有進行詞性標注，利用了前向－后向算法生成HMM模型，并且需要讀者有一定想象能力來作虛擬詞性標注；而我所用的訓練集是有標注的，主要是通過統計的方法生成HMM模型，并且對于測試集標注是直觀的。但是，殊途同歸，都是為了建立一個HMM模型，都是為了能利用UMDHMM。
關于如何下載和使用這個工具包具體請參考“Exercise: Using a Hidden Markov Model”，這里我主要講解一些要點和一個例子。
下載這個工具包主要是在命令行方式下利用ftp命令，估計有的讀者不太習慣這種方式，所以我在網絡硬盤上上傳了一個已下載的版本，有需要的讀者可以去這個地址下載：solaris.tar.gz。
首先對這個工具包解壓：tar -zxvf solaris.tar.gz
主要包括幾個perl腳本，UMDHMM編譯后生成的幾個可執行程序以及兩個樣例文件夾，需要注意的是，幾個perl腳本需要根據你所使用的環境修改perl的執行路徑，另外UMDHMM的幾個可執行程序是Resnik教授在Solaris 5.5系統下編譯的，并不適用于其他操作系統，因此最好自己單獨編譯一下UMDHMM，關于UMDHMM的編譯和使用，不太清楚的讀者可以先看一下我之前寫得一點介紹：UMDHMM。
對于這幾個perl腳本，需要作一點預處理，第一使其可執行：chmod u+x *.pl 或 chmod 755 *.pl；第二，修改每個腳本的perl解釋器目錄，由于我用的是ubuntu9.04，所以處理的方法是，注釋掉第一行，將第二行”/usr/local/bin/perl5“修改為“/usr/bin/perl”。
修改完畢perl腳本使其可執行之后，就可以進入example0目錄進行練習了：cd example0
example0目錄下有一個example0.train文件，只有一行，但是包含了一百句英語句子，這一百句英語句子只用了11個單詞和兩個標點符號”.”和“？”生成，是一個“似英語”句子生成器生成的，主目錄下有這個程序，是lisp程序寫的，我不明白怎么使用。如下所示部分句子：
the plane can fly . the typical plane can see the plane . a typical fly can see . who might see ? the large can might see a can . the can can destroy a large can …
對于這個訓練集，Resnik教授建議讀者寫一個簡單的詞性列表，并嘗試為每一個單詞分配一個詞性標記，并且同一個單詞可以有不同的標記。注意這個練習并不是要在這個文件中進行，可以在別的地方，譬如紙上或者心里都可以，不做也行的。我就偷懶了，因為不知道如何標記，并且手工標記的工作量較大，我用了一個基于Brown語料庫訓練的詞性標注器標注了一下，這個之后再詳細說明。
由于UMDHMM這個工具包處理的都是數字而非符號，所以需要先將這個訓練集轉換為數字序列，由create_key.pl這個腳本完成：
../create_key.pl example0.key < example0.train > example0.seq
這一步生成兩個文件：example0.key及example0.seq，前者主要將訓練集中出現的單詞符號映射為數字編號,如：
1 the
2 plane
8 a
4 fly
3 can
7 see
12 large
11 ?
10 might
9 who
6 typical
5 .
13 destroy
后者主要根據example0.key中的編號對訓練集進行轉換，并且形式為UMDHH中的訓練集輸入形式，如：
T= 590
1 2 3 4 5 1 6 2 3 7 1 2 5 8 6 4 3 7 5 9 10 7 11 1 12 3 10 7 8 3 5 1 3 3 13 8 12 3 5 9 10 7 11 9 10 4 11 9 3 4 11 1 3 10 7 5 1 2 3 4 8 6 4 5 9 3 4 11 1 12 4 3 4 5 9 3 7 11 9 3 7 8 3 11…
其中T代表了訓練集中的單詞符號數目。
今晚有點晚了，先到此為止吧，明晚繼續！
HMM在自然語言處理中的應用一：詞性標注4
分類 標注, 自然語言處理, 隱馬爾科夫模型?
在繼續昨晚的工作之前，先聊兩句Philip Resnik教授。作為美國馬里蘭大學的教授，他的主要研究領域是自然語言處理，不過最近他被美國某個網站評為“當代衛生保健領域最具創新性和最有影響力的百位革新者之一(the most creative and influential innovators working in healthcare today)” ,Resnik教授也非常吃驚（Much to my surprise），之所以入選，再于他利用自然語言處理來提高醫用編碼（medical coding）的水平，具體什么是醫用編碼我不太清楚，不過這項工作至少說明自然語言處理還是有相當的應用前景的。
另外，05年的時候，他的一個學生開發了一套統計機器翻譯系統，取名為“Hiero”，在當年NIST機器翻譯評測中表現出色，雖然沒有拿到第一，但是其提出的“層次短語模型”的論文獲得了當年ACL的最佳論文，此人名叫David Chiang ，中文名蔣偉。
一年之前有一段時間我對Web平行語料庫自動采集比較感興趣，就找了很多這方面的paper,其中最有名的當屬Resnik教授的Strand和LDC的BITS了，只是當時沒有仔細考慮過他是何方神圣。今天仔細讀了一下他的個人主頁，覺得他在自然語言處理領域也是一個比較神奇的人物，有興趣的讀者不妨看看他的這個主頁，對于擴展研究思路和把握當前的研究動態還是非常有好處的。好了，以下我們轉入HMM詞性標注的正題。
在將訓練集轉換成UMDHMM需要的形式后，就可以利用UMDHMM中編譯好的可執行程序esthmm來訓練HMM模型了。esthmm的作用是，對于給定的觀察符號序列，利用BaumWelch算法（前向-后向算法）學習隱馬爾科夫模型HMM。這里采用如下的命令訓練HMM模型：
../esthmm -N 7 -M 13 example0.seq > example0.hmm
其中 N指示的隱藏狀態數目，這里代表詞性標記，這個例子中可以隨便選，我選的是7，下一節會用到。注意Resnik教授給出的命令：
esthmm 6 13 example0.seq > example0.hmm
是錯誤的，需要加上”-N”和“-M”。example0.hmm的部分形式如下：
M= 13
N= 7
A:
0.001002 0.001003 0.001000 0.001000 0.462993 0.001000 0.538002
…
B:
0.001000 0.366300 0.420021 0.215676 0.001000 0.001001 0.001001 0.001000 0.001001 0.001000 0.001000 0.001001 0.001000
…
pi:
0.001000 0.001000 0.001005 0.001000 0.001000 0.999995 0.001000
拋開這個HMM模型的效果如何，這里不得不感嘆前向－后向算法或者EM算法的神奇。當然這里只是一個練習，實際處理中需要加上一些輔助手段，譬如詞典之類的，這種無監督的學習是非常有難度的。
有了這個HMM模型，就可以作些練習了。首先我們利用genseq來隨機生成句子：
../genseq -T 10 example0.hmm > example0.sen.seq
其中T指示的是輸出序列的長度，如下所示：
T= 10
8 12 4 5 9 3 7 5 9 3
注意 Resink教授給出的命令仍然是錯的，上面的輸出結果可讀性不好，讀者可以對照著example0.key將這個句子寫出來，不過Resnik教授寫了一個ints2words.pl的腳本，幫助我們完成了這件事：
../ints2words.pl example0.key < example0.sen.seq > example0.sen
example0.sen中包含的就是這個HMM模型隨機生成的句子：
a large fly . who can see . who can
雖然不是一句整句，但是局部還是可讀的，注意這兩步可以利用管道命令合并在一起：
../genseq -T 10 example0.hmm | ../ints2words.pl example0.key
注意每次的結果并不相同。
最后一個練習也是最重要的一個：對于一個測試句子尋找其最可能的隱藏狀態序列（Finding the Hidden State Sequence for a Test Sentence），對于本文來說，也就是詞性序列了。我們使用testvit來完成這個任務，當然，前提是先準備好測試句子。可以根據exampl0.key中的單詞和標點自己組織句子，也可以利用上一個練習隨機生成一個句子，不過我選擇了訓練集中的第91句，比較典型：
the can can destroy the typical fly .
雖然違背了自然語言處理中實驗的訓練集與測試集分離的原則，不過考慮到這只是一個練習，另外也是為下一節做個小準備，我們就以此句話為例建立一個文件example0.test.words。不過UMDHMM還是只認數字，所以Resnik教授有為我們寫了一個words2seq.pl處理此事：
../words2seq.pl example0.key < example0.test.words > example0.test
example0.test就是UMDHMM可以使用的測試集了，如下所示：
T= 8
1 3 3 13 1 6 4 5
現在就可以使用testvit，這次Resnik教授沒有寫錯：
../testvit example0.hmm example0.test
看到結果了嗎？我們得到了一個隱藏狀態序列：
…
Optimal state sequence:
T= 8
6 1 5 2 6 3 1 7
…
如果之前你已經建立好了隱藏狀態與詞性標記的一一映射，那么就可以把它們所對應的詞性標記一個一個寫出來了！這個詞性標注結果是否與你的期望一樣？
如果你還沒有建立這個映射，那么就可以好好發揮一下想象力了！無論如何，恭喜你和52nlp一起完成了Philip Resnik教授布置的這個練習。
HMM在自然語言處理中的應用一：詞性標注5
分類 標注, 自然語言處理, 隱馬爾科夫模型?
上一節我們談完了Resnik教授基于UMDHMM設計的詞性標注的練習，不過自始至終，還沒有見到一個詞性標記的影子。雖然這一過程展示了自然語言處理中EM算法在無監督學習任務中的重要作用，但是這類方法的標注準確性還相對較低，在實際應用中多是那些建立在有詞性標注訓練集基礎上的機器學習算法，如最大熵模型、決策樹等，所學習的詞性標注器能獲得較高的標注準確率。本節我們就以一個標注好的訓練集為基礎，來學習一個最簡單的HMM詞性標注器。
首先就是準備訓練集，作為一個練習，52nlp也本著盡量簡單的原則，所以這里仍然選用Resnik教授所使用的example0.train，這個訓練集雖然包含了一百句“似英語”的句子，但是只有一行，所以我們首先做一個斷句處理，不過這些句子只采用了“.”和“?”作為句尾標志，因此斷句相對簡單。不過實際處理中英文斷句問題比較麻煩，也有很多學者這方面做了很多研究工作。這里52nlp寫了一個簡單的sentsplit.pl腳本來處理這個訓練集：
./sentsplit.pl example0.train example0.sentences
example0.sentences就成了每一句為一行的訓練集，如下所示：
the plane can fly .
the typical plane can see the plane .
a typical fly can see .
who might see ?
the large can might see a can .
the can can destroy a large can .
…
但是，這個訓練集只包含純粹的單詞句子，因此需要做一下詞性標注，當然人工標注并檢查是最好的了，但是我不懂，于是找了一個開源的詞性標注工具對這些句子進行了標注，關于這個詞性標注器的細節，下一節我會具體介紹，先來看標注后得到的包含詞性標記的訓練集example0.all，部分示例如下：
the/at plane/nn can/md fly/vb ./.
the/at typical/jj plane/nn can/md see/vb the/at plane/nn ./.
a/at typical/jj fly/nn can/md see/vb ./.
who/wps might/md see/vb ?/.
the/at large/jj can/nn might/md see/vb a/at can/nn ./.
…
無論什么方法，建立HMM詞性標注器的關鍵就是根據這個訓練集來學習一個合適的HMM模型了。我們先來確定HMM模型中的隱藏狀態（詞性標記）和觀察符號（詞型），這里只考察能從訓練集中觀察的到的詞性標記和詞型，因此上一節用到的create_key.pl這個腳本就可以派上用處了。對于確定訓練集中的詞型，利用example0.sentences就可以:
../create_key.pl words.key < example0.sentences > example0.seq
所得到的words.key就包含了訓練集中的詞型及其數字編號：
1 the
2 plane
8 a
4 fly
3 can
7 see
12 large
11 ?
10 might
9 who
6 typical
5 .
13 destroy
注意另一個副產品example0.seq在這一節里并不需要。同樣我們也需要利用create_key.pl來確定訓練集中的詞性標記及其編號，不過這里我們需要先將example0.all中的詞性標記序列抽取出來。這里52nlp寫了一個簡單的腳本extractpos.pl來處理此事：
./extractpos.pl example0.all example0.pos
所得到的example0.pos文件部分示例如下：
at nn md vb .
at jj nn md vb at nn .
at jj nn md vb .
wps md vb .
at jj nn md vb at nn .
at nn md vb at jj nn .
…
有了這個文件，就可以再次利用create_key.pl了：
../create_key.pl pos.key < example0.pos > example0.posseq
所得到的pos.key就包含了訓練集中的詞性標記及其數字編號：
4 vb
6 jj
3 md
2 nn
7 wps
5 .
1 at
同樣，另一個副產品example0.posseq這里也不需要。
確定好了該HMM模型中的隱藏狀態（詞性標記）和觀察符號（詞型）后，下一步便是要計算HMM模型中其他三個基本要素了，包括初始概率向量,狀態轉移矩陣A，混淆矩陣B。
我們先預處理一下語料庫，主要的目標是對一元詞性、二元詞性及詞型與詞性的組合進行計數，這里52nlp寫了一個腳本pretrain.pl來處理此事：
./pretrain.pl example0.all lex ngram
所得到的lex文件主要是統計詞型及其詞性標記的組合在訓練集中出現的次數：
typical jj 25
large jj 22
might md 42
fly nn 20
a at 58
? . 57
plane nn 34
the at 35
who wps 57
can nn 39
see vb 45
destroy vb 9
fly vb 46
. . 43
can md 58
ngram文件主要包含的是一元詞性及二元詞性在訓練集中的出現次數：
vb 100
jj 47
md 100
nn 93
wps 57
. 100
at 93
vb . 50
md vb 100
vb at 50
at jj 47
wps md 57
nn . 50
at nn 46
jj nn 47
nn md 43
有了這幾個預處理文件，我們就可以訓練一個簡單的HMM詞性標注模型了,這里52nlp寫了一個約100行的腳本hmmtrain.pl來處理此事：
./hmmtrain.pl words.key pos.key ngram lex example.hmm
其中前四個是輸入（準備）文件，最后一個example.hmm是輸出文件，也就是本節的核心目標：一個合適的HMM詞性標注模型，我們來簡單看一下example.hmm：
M= 13
N= 7
A:
0.0100 0.4700 0.0100 0.0100 0.0100 0.4800 0.0100
…
B:
0.3396 0.0094 0.0094 0.0094 0.0094 0.0094 0.0094 0.5566 0.0094 0.0094 0.0094 0.0094 0.0094
…
pi:
0.1576 0.1576 0.1695 0.1695 0.1695 0.0797 0.0966
有興趣的讀者，可以對比一下上一節利用BaumWelch算法（前向-后向算法）所學習的HMM詞性標注模型example0.hmm。
關于這個腳本，其中對于狀態轉移矩陣A，混淆矩陣B的計算采用了最簡單的加一平滑來處理那些在訓練集中的未出現事件，關于加一平滑，不清楚讀者可以在“MIT自然語言處理第三講：概率語言模型（第四部分）” 中找到參考，或者任何一本自然語言處理書中關于ngram語言模型的章節都會介紹的。
現在我們就可以作上一節最后一個詞性標注的練習了，仍然選擇訓練集中的第91句：
the can can destroy the typical fly .
可以利用Resnik教授的words2seq.pl來對此句進行轉換，或者利用上一節已經處理好的UMDHMM可讀的example0.test：
T= 8
1 3 3 13 1 6 4 5
現在就可以使用testvit及剛剛訓練好的example.hmm來作詞性標注了：
../testvit example.hmm example0.test
同樣得到了一個隱藏狀態序列：
…
Optimal state sequence:
T= 8
1 2 3 4 1 6 2 5
…
不過這次我們已經有了詞性標記序列及其數字編號，可以對應著把它們寫出來：
at nn md vb at jj nn .
與測試句子合在一起即是：
the/at can/nn can/md destroy/vb the/at typical/jj fly/nn ./.
對照example.all里的第91句：
the/at can/nn can/md destroy/vb the/at typical/jj fly/nn ./.
二者是一樣的，不過這個絕不能說明此HMM詞性標注器是100％正確的。
好了，本節就到此為止了，這一節的相關例子及小腳本可以單獨按鏈接下載，也可以打包在這里供下載：52nlpexample.zip
不過這套小工具還不足以處理實際問題中的詞性標注問題，下一節我將介紹一個更加健壯的HMM詞性標注開源工具。
HMM在自然語言處理中的應用一：詞性標注6
分類 標注, 自然語言處理, 隱馬爾科夫模型?
有一段時間沒有談HMM和詞性標注了，今天我們繼續這個系列的最后一個部分：介紹一個開源的HMM詞性標注工具并且利用Brown語料庫構造一個英文詞性標注器。
上一節借用umdhmm構造的HMM詞性標注工具是二元語法(bigram)標注器，因為我們只考慮了前一個詞性標記和當前詞性標記，算的上是最基本的馬爾科夫模型標注器。這個HMM詞性標注器可以通過好幾種方式進行擴展，一種方式就是考慮更多的上下文，不只考慮前面一個詞性標記，而是考慮前面兩個詞性標記，這樣的標注器稱之為三元語法（trigram）標注器，是非常經典的一種詞性標注方法，在《自然語言處理綜論》及《統計自然語言處理基礎》中被拿來介紹。
正因為經典， 所以老外已經做足了功課，包括paper以及開源工具，我查了一下，其中比較有名的一個是TnT，作者既寫了一篇“TnT — Statistical Part-of-Speech Tagging”，被引用869次，又開發了一套開源工具(http://www.coli.uni-saarland.de/~thorsten/tnt/)，可謂“知行合一”。但是要獲得這個工具必須填一個表，并且傳真給對方，比較麻煩。不過幸好在英文維基百科關于詞性標注的介紹頁面上有替代品：Part-of-speech_tagging.
在這個頁面的“External links（外部鏈接）”的最后一行，提到了一個名叫Citar的利用C++開發的隱馬爾科夫模型（HMM）三元語法詞性標注器：
“Citar LGPL C++ Hidden Markov Model trigram POS tagger, a Java port named Jitar is also available”
同時，它也提供Java版本的Jitar。不過可惜，這個頁面目前無法直接訪問到。如果讀者對這個詞性標注工具感興趣的話，這里提供一個Citar的下載鏈接： citar-0.0.2.zip
以下是citar的簡要介紹：
Citar is a simple part-of-speech tagger, based on a trigram Hidden Markov Model (HMM). It (partly) implements the ideas set forth in [1]. Citaris written in C++. There is also a Java/JDK counterpart named Jitar,
which is available at: http://code.google.com/p/jitar/
其中[1]指的是“TnT — Statistical Part-of-Speech Tagging”，其具體的實現思想在這篇文章里描述的很細致，我覺得主要需要注意的幾個地方是trigram的平滑算法，未登錄詞的處理方法（主要是針對英文的），以及柱搜索(beam search)解碼算法。
編譯citar直接make就可以了，生成三個可執行文件：train,tag,evaluate。顧名思義，“train”是用來一些必要的文件的，tag則是進行標注的，而evaluate則是用來評價標注結果的。下面我們以Brown語料庫為例來演示如何使用這三個可執行程序。
關于Brown語料庫，我是從NLTK的包中得到的，NLTK提供了兩個版本的語料庫，一個是純文本格式，另外一個是XML格式，都進行了詞性標注，如果你對NLTK不熟悉，可以從下面兩個鏈接直接下載這兩個語料庫：
1、XML格式的brown語料庫，帶詞性標注；
2、普通文本格式的brown語料庫，帶詞性標注；
至于Brown語料庫的具體介紹，大家可以參考這個頁面：BROWN CORPUS MANUAL。在這個練習中，我采用的是純文本格式的brown語料庫，但是這些文件是按照類別分布在很多小文件里，并且包含很多空行，所以我處理了一下這個文件，把它們合并到一個大的文件中，并且去除了行首的空格及空行，共得到57340個帶詞性標注的句子(brown.corpus)。我們首先對這個語料庫進行劃分，從中選取前55340句作為訓練集(brown.train)，選取剩余的2000句作為測試集(brown.test)，現在我們就來運行這三個命令。
首先利用train來訓練：
../train brown.train brown.lex brown.ngram
其中輸入文件是訓練集brown.train，而輸出文件是brown.lex及brown.ngram，如果大家還記著上一節里我也生成了兩個前處理文件lex和ngram的話，那么就不難理解這兩個文件的內容含義了。事實上，我當時就是模仿citar的這個預處理思想做得，只是結果文件里的格式稍有不同而已。
有了上述兩個文件，就可以利用tag進行詞性標注了，我們拿citar里的一個示例句子來實驗一下：
echo “The cat is on the mat .” | ../tag brown.lex brown.ngram
得到如下的結果：
The/at cat/nn is/bez on/in the/at mat/nn ./.
如果對一個沒有標注的文件進行標注，可以利用如下的命令：
../tag brown.lex brown.ngram < input > output
最后，我利用evaluate來驗證一下基于brown.train訓練出來的詞性標注器的準確率,在測試集brown.test上進行測試：
../evaluate brown.lex brown.ngram brown.test
得到如下的結果：
Accuracy (known): 0.964621
Accuracy (unknown): 0.740937
Accuracy (overall): 0.956389
說明這個詞性標注器對于語料庫中已存在的詞的標注準確率是96.46%，對于未登錄詞的標注準確率是74.09%，而整體標注準確慮是95.63%。
好了，關于Citar我們就到此為止，有興趣的讀者可以找一些標注好的語料庫來試試，包括中文的詞性標注語料庫，只不過它用于英文的未登錄詞處理方法對于中文并不合適而已。上面所提到的幾個文件，包括處理好的brown.corpus,訓練集brown.train,測試集brown.test及中間生成的brown.lex,brown.ngram我已經打包放在了網絡硬盤里，可以在如下地址下載：browntest.zip
關于HMM在詞性標注中的應用就說完了，再次回頭說詞性標注時，我會基于其他的模型來作相關的詞性標注練習。下一個關于HMM在自然語言處理的應用，將會談談中文分詞的相關問題，歡迎繼續關注52nlp。
總結
以上是生活随笔為你收集整理的史上最详细最容易理解的HMM文章的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 隐马尔可夫HMM中viterbi算法
- 下一篇： SDN(软件定义网络)