在講隱馬模型之前想许，首先要了解下偿渡，啥是馬爾可夫模型免姿。
馬爾可夫模型
幾個條件
- 當前狀態(tài)只與前一個狀態(tài)相關
- 一個狀態(tài)到所有狀態(tài)的轉(zhuǎn)移概率和為1
- 概率大于等于0小于等于1
- 狀態(tài)起始概率和為1
舉個例子：
在文本中，假設有三個狀態(tài)施符，名詞n，動詞v擂找，形容詞adj，三者之間的轉(zhuǎn)移概率為(瞎編)：
初始化概率為p(adj) = 0.5浩销，p(n)=0.3,p(v)=0.2.
那么贯涎，一個文本詞性為 形容詞，名詞慢洋，動詞塘雳，名詞的概率為：
相當于n-gram語言模型中陆盘，n = 2 的情況。
隱馬爾可夫模型
在上述例子中败明，文本的詞性是明確的隘马，而隱馬模型中，不知道所經(jīng)歷的狀態(tài)序列妻顶，觀察到的序列是隨機的酸员。所以，狀態(tài)轉(zhuǎn)換是隨機的讳嘱，觀測序列也是隨機的幔嗦，雙重隨機過程。
舉個例子：我 吃 飯沥潭。這里我們能夠觀測到的就是邀泉，‘我’，‘吃’钝鸽，‘飯’汇恤。
那么‘我’對應的狀態(tài)有‘動詞’，‘名詞’拔恰，‘形容詞’因谎，‘吃’，‘飯’同理仁连。那么他們的背后詞性序列蓝角，到底是 名動名，還是動動名饭冬，還是形動名不得而知使鹅。這種未知序列稱之為隱狀態(tài)。
所以：隱馬模型三要素昌抠，一個是狀態(tài)轉(zhuǎn)移矩陣（同上）患朱，另一個是觀測狀態(tài)到隱藏狀態(tài)的概率矩陣。還有一個起始狀態(tài)概率炊苫。
隱馬模型的三個問題
- 如何計算 觀測序列O 的概率
- 如和計算 觀測序列O 最優(yōu)的隱狀態(tài)序列
- 參數(shù)如何學習
問題一：
這樣相當于是窮舉所有可能裁厅。即，O1的狀態(tài)概率O2的狀態(tài)概率狀態(tài)之間的概率轉(zhuǎn)移侨艾。這樣执虹，狀態(tài)一多，觀測長度一長唠梨，計算將會指數(shù)增長袋励。
為了優(yōu)化求解時間，采用動態(tài)規(guī)劃的思想，即O1茬故，到O2盖灸，在計算O2，到O3,一次類推磺芭，最終計算到Ot.
那么復雜度即赁炎，O1有N個狀態(tài)，O2有N個狀態(tài)钾腺，那么計算O1到O2徙垫，就需要計算N*N 次，最終算得N個路徑垮庐，通往O3松邪，解釋有點繞∩诓椋總共t次逗抑。隨意復雜度為。具體算法可以查看 前向算法寒亥。大概樣子就是如下所示：
問題二：
一般在問題二在NLP的應用中較多邮府，需要找到當前觀測序列最優(yōu)的標注。
如何快速的找到最優(yōu)的序列溉奕。
維特比算法：
算法原理這里不做闡述褂傀。這篇博客講的非常通俗易懂～
https://blog.csdn.net/athemeroy/article/details/79339546
算法實現(xiàn)：
首先需要一個隱馬模型：
寫了個隨機函數(shù)，生成隱馬模型
def hmmRamdon():
#隱狀態(tài)個數(shù)
yin_num = 5
#觀測概率個數(shù)
guan_num = 10
A = np.zeros((yin_num,yin_num))
for i in range(yin_num):
rows_h = np.random.random(yin_num)
rows_v = np.random.random(yin_num)
for k in range(i):
rows_h[k] = A[i][k]
rows_h[i:] = rows_h[i:] / rows_h[i:].sum() * (1 - rows_h[:i].sum())
A[i] = rows_h
for k in range(i+1):
rows_v[k] = A[k][i]
rows_v[i+1:] = rows_v[i+1:] / rows_v[i+1:].sum() * (1 - rows_v[:i+1].sum())
for j in range(yin_num):
A[j][i] = rows_v[j]
B = np.zeros((yin_num,guan_num))
for i in range(yin_num):
row = np.random.random(guan_num)
B[i] = row / row.sum()
init_yin = np.random.random(yin_num)
pai = init_yin / init_yin.sum()
return A,B,pai
函數(shù)沒有做大于0校驗～加勤，隨出負數(shù)的話記得多隨幾次哈～
看過上述講解維特比算法原理博客的同鞋仙辟，應該記得下圖：
在HMM，中A->B相當于鳄梅，觀測序列的中 第一個序列叠国，B1->B3是隱狀態(tài)，
所以當前A->B的路徑可以初始化為
這里展示方便戴尸，假設HMM模型為
A = np.array([[0.5,0.2,0.3],
[0.3,0.5,0.2],
[0.2,0.3,0.5]])
B = np.array([[0.5,0.5],
[0.4,0.6],
[0.7,0.3]])
pai = np.array([[0.2,0.4,0.4]])
observe = [0,1,0]
a_ex = B[:,observe[0]] * pai
a_ex = a_ex.T
all_way = np.full((yin_num, 1), -1)
print(a_ex)
print(all_way)
[[0.1 ]
[0.16]
[0.28]]
===========
[[-1]
[-1]
[-1]]
a_ex記錄到達上一個觀測狀態(tài)每個隱狀態(tài)最優(yōu)的概率值粟焊。
observe[0]觀測序列第一個，觀測概率各自乘于初始化概率孙蒙。all_way 用于記錄每條路徑經(jīng)過的隱狀態(tài)節(jié)點项棠。0.1 = 0.5 * 0.2，0.16 = 0.4 * 0.4挎峦，0.28 = 0.7 * 0.4.
當計算由B->C時香追，C1，C2坦胶，C3 各自有三條路徑翅阵，歪玲，結(jié)合A-B的路徑，計算出A->C1概率最高的一條路徑掷匠，同理計算到C2，C3的路徑岖圈。
a_new = A1 *a_ex* B1[:,observe[1]]#計算圖中9個路線
a_ex = np.amax(a_new,axis=0) #獲取每個隱狀態(tài)三個路徑中最高的那一個
a_ex = a_ex.reshape(a_ex.shape[0],-1)
way = np.argmax(a_new,axis=0)#找出概率最高的三條路線
way = way.reshape(way.shape[0],-1)
all_way = np.hstack((all_way,way))#路徑更新
a_new:
[[0.025 0.012 0.009 ]
[0.024 0.048 0.0096]
[0.028 0.0504 0.042 ]]
a_ex:
[[0.028 ]
[0.0504]
[0.042 ]]
all_way:
[[-1 2]
[-1 2]
[-1 2]]
所以對應圖中的三條路徑為A-B3-C1讹语，A-B3-C2，A-B3-C3蜂科。
即博客中對應的圖
如此循環(huán)直到最后一個顽决。完整算法代碼如下：
import numpy as np
def viterbi_search(A,B,pai,observe):
yin_num = A.shape[0]
for j in range(len(observe)):
if j == 0:
a_ex = B[:,observe[j]] * pai
a_ex = a_ex.T
all_way = np.full((yin_num, 1), -1)
else:
a_new = A1 *a_ex* B1[:,observe[j]]
a_ex = np.amax(a_new,axis=0)
a_ex = a_ex.reshape(a_ex.shape[0],-1)
way = np.argmax(a_new,axis=0)
way = way.reshape(way.shape[0],-1)
all_way = np.hstack((all_way,way))
result = np.append(all_way[a_ex.argmax()],a_ex.argmax())
return result, a_ex.max()
實驗環(huán)境jupyter，實驗代碼下載鏈接：
鏈接:https://pan.baidu.com/s/1W9zckhKG3yssFeZtahl-5g 密碼:78y5
問題三：參數(shù)估計
最大似然估計：
轉(zhuǎn)移概率：aij = ai 到aj的次數(shù) / ai到所有狀態(tài)的次數(shù)导匣。
觀測概率：bi = ai 到 bi 觀測的次數(shù) / ai到所有觀測的次數(shù)才菠。
一般隱狀態(tài)未知的情況下，可以用最大期望EM贡定，對轉(zhuǎn)移概率進行估計赋访。
