在講隱馬模型之前，首先要了解下，啥是馬爾可夫模型。
馬爾可夫模型
幾個(gè)條件
- 當(dāng)前狀態(tài)只與前一個(gè)狀態(tài)相關(guān)
- 一個(gè)狀態(tài)到所有狀態(tài)的轉(zhuǎn)移概率和為1
- 概率大于等于0小于等于1
- 狀態(tài)起始概率和為1
舉個(gè)例子：
在文本中，假設(shè)有三個(gè)狀態(tài)，名詞n，動(dòng)詞v，形容詞adj，三者之間的轉(zhuǎn)移概率為(瞎編)：
初始化概率為p(adj) = 0.5，p(n)=0.3,p(v)=0.2.
那么，一個(gè)文本詞性為 形容詞，名詞，動(dòng)詞，名詞的概率為：
相當(dāng)于n-gram語(yǔ)言模型中，n = 2 的情況。
隱馬爾可夫模型
在上述例子中，文本的詞性是明確的，而隱馬模型中，不知道所經(jīng)歷的狀態(tài)序列，觀(guān)察到的序列是隨機(jī)的。所以，狀態(tài)轉(zhuǎn)換是隨機(jī)的，觀(guān)測(cè)序列也是隨機(jī)的，雙重隨機(jī)過(guò)程。
舉個(gè)例子：我 吃 飯。這里我們能夠觀(guān)測(cè)到的就是，‘我’，‘吃’，‘飯’。
那么‘我’對(duì)應(yīng)的狀態(tài)有‘動(dòng)詞’，‘名詞’，‘形容詞’，‘吃’，‘飯’同理。那么他們的背后詞性序列，到底是 名動(dòng)名，還是動(dòng)動(dòng)名，還是形動(dòng)名不得而知。這種未知序列稱(chēng)之為隱狀態(tài)。
所以：隱馬模型三要素，一個(gè)是狀態(tài)轉(zhuǎn)移矩陣（同上），另一個(gè)是觀(guān)測(cè)狀態(tài)到隱藏狀態(tài)的概率矩陣。還有一個(gè)起始狀態(tài)概率。
隱馬模型的三個(gè)問(wèn)題
- 如何計(jì)算 觀(guān)測(cè)序列O 的概率
- 如和計(jì)算 觀(guān)測(cè)序列O 最優(yōu)的隱狀態(tài)序列
- 參數(shù)如何學(xué)習(xí)
問(wèn)題一：
這樣相當(dāng)于是窮舉所有可能。即，O1的狀態(tài)概率O2的狀態(tài)概率狀態(tài)之間的概率轉(zhuǎn)移。這樣，狀態(tài)一多，觀(guān)測(cè)長(zhǎng)度一長(zhǎng)，計(jì)算將會(huì)指數(shù)增長(zhǎng)。
為了優(yōu)化求解時(shí)間，采用動(dòng)態(tài)規(guī)劃的思想，即O1，到O2，在計(jì)算O2，到O3,一次類(lèi)推，最終計(jì)算到Ot.
那么復(fù)雜度即，O1有N個(gè)狀態(tài)，O2有N個(gè)狀態(tài)，那么計(jì)算O1到O2，就需要計(jì)算N*N 次，最終算得N個(gè)路徑，通往O3，解釋有點(diǎn)繞。總共t次。隨意復(fù)雜度為。具體算法可以查看 前向算法。大概樣子就是如下所示：
問(wèn)題二：
一般在問(wèn)題二在NLP的應(yīng)用中較多，需要找到當(dāng)前觀(guān)測(cè)序列最優(yōu)的標(biāo)注。
如何快速的找到最優(yōu)的序列。
維特比算法：
算法原理這里不做闡述。這篇博客講的非常通俗易懂～
https://blog.csdn.net/athemeroy/article/details/79339546
算法實(shí)現(xiàn)：
首先需要一個(gè)隱馬模型：
寫(xiě)了個(gè)隨機(jī)函數(shù)，生成隱馬模型
def hmmRamdon():
#隱狀態(tài)個(gè)數(shù)
yin_num = 5
#觀(guān)測(cè)概率個(gè)數(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ù)沒(méi)有做大于0校驗(yàn)～，隨出負(fù)數(shù)的話(huà)記得多隨幾次哈～
看過(guò)上述講解維特比算法原理博客的同鞋，應(yīng)該記得下圖：
在HMM，中A->B相當(dāng)于，觀(guān)測(cè)序列的中 第一個(gè)序列，B1->B3是隱狀態(tài)，
所以當(dāng)前A->B的路徑可以初始化為
這里展示方便，假設(shè)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記錄到達(dá)上一個(gè)觀(guān)測(cè)狀態(tài)每個(gè)隱狀態(tài)最優(yōu)的概率值。
observe[0]觀(guān)測(cè)序列第一個(gè)，觀(guān)測(cè)概率各自乘于初始化概率。all_way 用于記錄每條路徑經(jīng)過(guò)的隱狀態(tài)節(jié)點(diǎn)。0.1 = 0.5 * 0.2，0.16 = 0.4 * 0.4，0.28 = 0.7 * 0.4.
當(dāng)計(jì)算由B->C時(shí)，C1，C2，C3 各自有三條路徑，，結(jié)合A-B的路徑，計(jì)算出A->C1概率最高的一條路徑，同理計(jì)算到C2，C3的路徑。
a_new = A1 *a_ex* B1[:,observe[1]]#計(jì)算圖中9個(gè)路線(xiàn)
a_ex = np.amax(a_new,axis=0) #獲取每個(gè)隱狀態(tài)三個(gè)路徑中最高的那一個(gè)
a_ex = a_ex.reshape(a_ex.shape[0],-1)
way = np.argmax(a_new,axis=0)#找出概率最高的三條路線(xiàn)
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]]
所以對(duì)應(yīng)圖中的三條路徑為A-B3-C1，A-B3-C2，A-B3-C3。
即博客中對(duì)應(yīng)的圖
如此循環(huán)直到最后一個(gè)。完整算法代碼如下：
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()
實(shí)驗(yàn)環(huán)境jupyter，實(shí)驗(yàn)代碼下載鏈接：
鏈接:https://pan.baidu.com/s/1W9zckhKG3yssFeZtahl-5g 密碼:78y5
問(wèn)題三：參數(shù)估計(jì)
最大似然估計(jì)：
轉(zhuǎn)移概率：aij = ai 到aj的次數(shù) / ai到所有狀態(tài)的次數(shù)。
觀(guān)測(cè)概率：bi = ai 到 bi 觀(guān)測(cè)的次數(shù) / ai到所有觀(guān)測(cè)的次數(shù)。
一般隱狀態(tài)未知的情況下，可以用最大期望EM，對(duì)轉(zhuǎn)移概率進(jìn)行估計(jì)。
