隱馬爾科夫模型（HMM）
隱馬爾科夫模型（Hidden Markov Model，簡稱HMM）是經(jīng)典的機器學習模型。首先設置兩個狀態(tài)集合：隱藏狀態(tài) S 和觀測狀態(tài) V。
n是所有可能的隱藏狀態(tài)數(shù)，m是所有可能的觀察狀態(tài)數(shù)。定義輸入序列X，輸出序列Y：
狀態(tài)轉(zhuǎn)移矩陣A：包含了一個隱藏狀態(tài)到另一個隱藏狀態(tài)的條件概率。
觀測概率矩陣B：包含了一個隱藏狀態(tài)到一個觀察狀態(tài)的概率。
HMM?模型做了兩個假設：
馬爾科夫假設：輸出序列 Y 中，每個時刻 t 的隱藏狀態(tài)只依賴于前一個時刻 t - 1 的隱藏狀態(tài)。
觀測獨立性假設：輸入序列 X?中，每個時刻?t?的觀測狀態(tài)只依賴于 Y 中當前時刻 t 的隱藏狀態(tài)。
舉個序列詞性預測的例子：
所以概率 p(x,y)?就為如下連乘的形式：
那模型的關鍵就是要得到狀態(tài)轉(zhuǎn)移矩陣和觀測概率矩陣，這兩個矩陣可以從數(shù)據(jù)集中統(tǒng)計出來。
HMM的訓練過程就是對有標簽的數(shù)據(jù)進行統(tǒng)計處理。之后就可以直接進行解碼了,解碼的目標是找出能使 p(y|x) 概率最大的那個序列 Y：
按上式轉(zhuǎn)換之后，最終就要求我們找到一個序列 Y 能使 p(x,y) 概率最大。具體的找法就是窮舉所有的序列 y，計算它們的概率 p(x,y)，最大的那個就是結(jié)果。窮舉的量非常大，尋常的算法時間復雜度很高，HMM 使用的解碼算法是維特比，其時間復雜度為 O(T*|S|*|S|)，T?表示序列 y 的長度, |S| 表示隱藏狀態(tài)數(shù)。我們借助一個網(wǎng)絡圖來理解維特比算法：
紅線表示一條可能的 y 序列，網(wǎng)絡圖最前面還應該有一個start節(jié)點，最后面有一個end節(jié)點，這里未畫出。根據(jù)上面那個公式（寫到下面了）來考慮每個節(jié)點和每條邊該怎么定義概率：
可以看到，每條邊上應該定義隱藏狀態(tài)之間的轉(zhuǎn)移概率，每個節(jié)點上應該定義觀測狀態(tài)到隱藏狀態(tài)的轉(zhuǎn)移概率。對于每個節(jié)點，都有 |S|?條輸入，會有一個走到此處的路徑概率（邊上定義的概率和節(jié)點上定義的概率的連乘），顯然沒有必要保留全部的前綴路徑概率，只需要保留最大的那條就可以了，走到最后的end節(jié)點后，所保留的那個概率就是最大的，然后根據(jù)路徑回溯就可以得到對應的序列Y。
