這里首先說(shuō)下隱馬爾可夫模型的相關(guān)知識(shí)。

1. 隱馬爾可夫模型（HMM）

在說(shuō)隱馬爾可夫模型前還有一個(gè)概念叫做“馬爾科夫鏈”，既是在給定當(dāng)前知識(shí)或信息的情況下，觀察對(duì)象過(guò)去的歷史狀態(tài)對(duì)于預(yù)測(cè)將來(lái)是無(wú)關(guān)的。也可以說(shuō)在觀察一個(gè)系統(tǒng)變化的時(shí)候，他的下一個(gè)狀態(tài)如何的概率只需要觀察和統(tǒng)計(jì)當(dāng)前的狀態(tài)即可正確得出。隱馬爾可夫鏈和貝葉斯網(wǎng)絡(luò)的模型思維有些接近，區(qū)別在于隱馬爾可夫的模型更為簡(jiǎn)化。而且隱馬爾可夫鏈?zhǔn)且粋€(gè)雙重的隨機(jī)過(guò)程，不僅狀態(tài)轉(zhuǎn)移之間是一個(gè)隨機(jī)事件，狀態(tài)和輸出之間也是一個(gè)隨機(jī)過(guò)程。

如下圖：

在一個(gè)完整的觀察過(guò)程中有一些狀態(tài)的轉(zhuǎn)換，如X1到XT的轉(zhuǎn)換存在一個(gè)客觀的轉(zhuǎn)換規(guī)律，但是沒(méi)辦法直接觀測(cè)到，觀測(cè)到的只是每個(gè)X狀態(tài)下的輸出O，通過(guò)O1到OT這些輸出值來(lái)進(jìn)行模型建立和計(jì)算狀態(tài)轉(zhuǎn)移的概率。

知乎上一個(gè)很好的例子：
https://www.zhihu.com/question/20962240/answer/33438846

對(duì)于HMM來(lái)說(shuō)，如果前提知道所有的隱含狀態(tài)之間的轉(zhuǎn)換概率和所有隱含狀態(tài)到所有可見(jiàn)狀態(tài)之間的輸出概率，進(jìn)行模擬是很容易的。但是往往會(huì)缺失一部分信息，如何應(yīng)用算法去估計(jì)缺失的信息，就成為了一個(gè)重要的問(wèn)題。

和HMM模型相關(guān)的算法分為3類，分別解決3種問(wèn)題。

• 知道隱含狀態(tài)數(shù)量、轉(zhuǎn)換概率、根據(jù)可見(jiàn)狀態(tài)鏈的結(jié)果想知道隱含狀態(tài)鏈。這個(gè)問(wèn)題在語(yǔ)音識(shí)別領(lǐng)域叫做解碼問(wèn)題，求解這個(gè)問(wèn)題有兩種方法。第一種是求最大最大似然狀態(tài)路徑（一串骰子序列，使其產(chǎn)生的觀測(cè)結(jié)果的概率最大）。第二種解法是求每次擲出的骰子分別是某種骰子的概率。
• 知道隱含狀態(tài)數(shù)量、轉(zhuǎn)換概率、根據(jù)可見(jiàn)狀態(tài)鏈的結(jié)果想知道產(chǎn)生結(jié)果的概率。這個(gè)問(wèn)題的實(shí)際意義在于檢測(cè)觀察到的模型是否和已知的模型吻合。如果很多次結(jié)果都是對(duì)應(yīng)了比較小的概率，那么就說(shuō)明已知的模型很可能是錯(cuò)的。
• 知道隱含狀態(tài)數(shù)量、不知道轉(zhuǎn)換概率、根據(jù)可見(jiàn)狀態(tài)鏈的結(jié)果想反推出轉(zhuǎn)換概率。這個(gè)問(wèn)題是最重要的，因?yàn)槭亲顬槌Ｒ?jiàn)的。很多時(shí)候只有可見(jiàn)結(jié)果，不知道HMM模型中的參數(shù)，需要從可見(jiàn)結(jié)果估計(jì)這些參數(shù)。

2. 維特比算法

當(dāng)馬爾科夫鏈很長(zhǎng)時(shí)，根據(jù)古典概型的分布特點(diǎn)來(lái)計(jì)算概率時(shí)窮舉的數(shù)量太大，就很難得到結(jié)果。這時(shí)就要用到維特比算法。維特比算法就是為了找出可能性最大的隱藏序列，即剛剛提到的第一個(gè)問(wèn)題。這種算法是一種鏈的可能性問(wèn)題，現(xiàn)在應(yīng)用最廣泛的是CDMA和打字提示功能。

維特比算法的整體思路是尋找上一段信息和它跟隨的下一段信息的轉(zhuǎn)換概率問(wèn)題。

2.1 打字輸入提示應(yīng)用

這是常用的搜狗輸入法的示例。在本例中只是考慮最簡(jiǎn)單的因素，下面是模擬輸入法的猜測(cè)方法給出一個(gè)算法示例，先給出各級(jí)轉(zhuǎn)換矩陣。如下：

其實(shí)這些概率矩陣都是由統(tǒng)計(jì)產(chǎn)生，而且每個(gè)雙字詞、三字詞等的輸入矩陣都由這種統(tǒng)計(jì)產(chǎn)生。在輸入雙字詞漢子拼音時(shí)會(huì)根據(jù)轉(zhuǎn)移概率表進(jìn)行計(jì)算。多個(gè)詞相連就是多個(gè)轉(zhuǎn)移矩陣的概率相乘計(jì)算，從而得到概率最大的輸入可能項(xiàng)。

2.2 代碼：

# coding=utf-8 import numpy as npjin = ['近', '斤', '今', '金', '盡'] jin_per = [0.3, 0.2, 0.1, 0.06, 0.03] # 單字詞概率矩陣jintian = ['天', '填', '田', '甜', '添'] jintian_per = [[0.001, 0.001, 0.001, 0.001, 0.001], # 轉(zhuǎn)移矩陣[0.001, 0.001, 0.001, 0.001, 0.001],[0.990, 0.001, 0.001, 0.001, 0.001],[0.002, 0.001, 0.850, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001]]wo = ['我', '窩', '喔', '握', '臥'] wo_per = [0.400, 0.150, 0.090, 0.050, 0.030]women = ['們', '門', '悶', '燜', '捫'] women_per = [[0.970, 0.001, 0.003, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001]]qing = ['請(qǐng)', '晴', '清', '輕', '情'] qing_per = [0.2, 0.12, 0.09, 0.05, 0.02]qinghua = ['話', '畫', '化', '花', '華'] qinghua_per = [[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.950],[0.001, 0.001, 0.850, 0.001, 0.001],[0.003, 0.001, 0.001, 0.002, 0.001]]da = ['大', '打', '達(dá)', '搭', '噠'] da_per = [0.300, 0.130, 0.120, 0.110, 0.090]daxue = ['學(xué)', '雪', '血', '薛', '穴'] daxue_per = [[0.800, 0.140, 0.023, 0.004, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001],[0.001, 0.001, 0.001, 0.001, 0.001]]N = 5# 一個(gè)字的預(yù)測(cè) def found_from_oneword(oneword_per):index = []values = []a = np.array(oneword_per)print 'a:',aprint 'argsort(a):',np.argsort(a)[::-1][:N]for v in np.argsort(a)[::-1][:N]: # 遍歷降序前5的概率索引，index.append(v)values.append(oneword_per[v])return index, values# 一個(gè)詞的預(yù)測(cè) def found_from_twoword(oneword_per, twoword_per):last = 0for i in range(len(oneword_per)):#print oneword_per[i],'\n', twoword_per[i]current = np.multiply(oneword_per[i], twoword_per[i]) # 字概率乘以轉(zhuǎn)移概率if i == 0:last = currentelse:last = np.concatenate((last, current), axis=0) # 字符串拼接#print 'last:',last # 單個(gè)字概率矩陣乘以轉(zhuǎn)移概率矩陣index = []values = []#print np.argsort(last)[::-1][:N]for v in np.argsort(last)[::-1][:N]: # 概率從大到低的排列(前5個(gè))index.append([v / 5, v % 5]) # 由數(shù)組的索引值得到其在矩陣中的坐標(biāo)值values.append(last[v])print 'index:',index,'\n','values:',values return index, values# 字詞的預(yù)測(cè) def predict(word):if word == 'jin':for i in found_from_oneword(jin_per)[0]: # 遍歷概率索引值print jin[i] # 輸出排序后的索引對(duì)應(yīng)的值print '.......................................'elif word == 'jintian':for i in found_from_twoword(jin_per, jintian_per)[0]: # 傳入的是概率矩陣和轉(zhuǎn)移矩陣print 'i:',i# jin[i[0]]：詞組在矩陣中的第一個(gè)字的下標(biāo)；jintian[i[1]]：在矩陣中的列表示后一個(gè)字的下標(biāo)print jin[i[0]] + jintian[i[1]] print '.......................................'elif word == 'wo':for i in found_from_oneword(wo_per)[0]:print wo[i]print '.......................................'elif word == 'women':for i in found_from_twoword(wo_per, women_per)[0]:print wo[i[0]] + women[i[1]]print '.......................................'elif word == 'jintianwo':index1, values1 = found_from_oneword(wo_per)print 'index1, values1:', index1, '\n',values1 # 先得到'wo'的排序index2, values2 = found_from_twoword(jin_per, jintian_per) # 再得到'jintian'排序print 'index2, values2:', index2, '\n',values2last = np.multiply(values1, values1) # 得到'jintian'和'wo'的最大概率乘積for i in np.argsort(last)[::-1][:N]:print jin[index2[i][0]], jintian[index2[i][1]], wo[i]print '.......................................'elif word == 'jintianwomen':index1, values1 = found_from_twoword(jin_per, jintian_per) # 得到'jintian'的排序index2, values2 = found_from_twoword(wo_per, women_per) # 得到'women'的排序last = np.multiply(values1, values1) # 得到'jintian'和'women'相乘的排序for i in np.argsort(last)[::-1][:N]:print jin[index1[i][0]], jintian[index1[i][1]], wo[index2[i][0]], women[index2[i][1]]print '.......................................'else:passif __name__ == '__main__':predict('jin')# 近# 斤# 今# 金# 盡predict('jintian')# 今天# 金田# 近天# 近填# 近田predict('wo')# 近# 斤# 今# 金# 盡predict('women')# 我們# 我悶# 我門# 我燜# 我捫predict('jintianwo')# 今 天 我# 金 田 窩# 近 天 喔# 近 填 握# 近 田 臥predict('jintianwomen')# 今 天 我 們# 金 田 我 悶# 近 田 我 捫# 近 填 我 燜# 近 天 我 門

運(yùn)行結(jié)果：

a: [ 0.3 0.2 0.1 0.06 0.03] argsort(a): [0 1 2 3 4] 近 斤 今 金 盡 ....................................... index: [[2, 0], [3, 2], [0, 0], [0, 1], [0, 2]] values: [0.099000000000000005, 0.050999999999999997, 0.00029999999999999997, 0.00029999999999999997, 0.00029999999999999997] i: [2, 0] 今天 i: [3, 2] 金田 i: [0, 0] 近天 i: [0, 1] 近填 i: [0, 2] 近田 ....................................... a: [ 0.4 0.15 0.09 0.05 0.03] argsort(a): [0 1 2 3 4] 我 窩 喔 握 臥 ....................................... index: [[0, 0], [0, 2], [0, 1], [0, 3], [0, 4]] values: [0.38800000000000001, 0.0012000000000000001, 0.00040000000000000002, 0.00040000000000000002, 0.00040000000000000002] 我們 我悶 我門 我燜 我捫 ....................................... a: [ 0.4 0.15 0.09 0.05 0.03] argsort(a): [0 1 2 3 4] index1, values1: [0, 1, 2, 3, 4] [0.4, 0.15, 0.09, 0.05, 0.03] index: [[2, 0], [3, 2], [0, 0], [0, 1], [0, 2]] values: [0.099000000000000005, 0.050999999999999997, 0.00029999999999999997, 0.00029999999999999997, 0.00029999999999999997] index2, values2: [[2, 0], [3, 2], [0, 0], [0, 1], [0, 2]] [0.099000000000000005, 0.050999999999999997, 0.00029999999999999997, 0.00029999999999999997, 0.00029999999999999997] 今 天 我 金 田 窩 近 天 喔 近 填 握 近 田 臥 ....................................... index: [[2, 0], [3, 2], [0, 0], [0, 1], [0, 2]] values: [0.099000000000000005, 0.050999999999999997, 0.00029999999999999997, 0.00029999999999999997, 0.00029999999999999997] index: [[0, 0], [0, 2], [0, 1], [0, 3], [0, 4]] values: [0.38800000000000001, 0.0012000000000000001, 0.00040000000000000002, 0.00040000000000000002, 0.00040000000000000002] 今 天 我 們 金 田 我 悶 近 田 我 捫 近 填 我 燜 近 天 我 門 .......................................

從運(yùn)行結(jié)果可以看出其實(shí)就是通過(guò)統(tǒng)計(jì)得到的概率矩陣和轉(zhuǎn)移矩陣的乘積之后的排序計(jì)算。

3. 筆記

3.1 for v in np.argsort(a)[::-1][:N]的用法：

In [7]: a=array([1, 2, 3])In [8]: a Out[8]: array([1, 2, 3])In [9]: a[::-1] Out[9]: array([3, 2, 1])In [10]: a[::-1][:3] Out[10]: array([3, 2, 1])

3.2 last = np.concatenate((last, current), axis=0)的使用：

>>> import numpy as np >>> a = np.array([[1, 2], [3, 4]]) >>> a array([[1, 2],[3, 4]]) >>> b = np.array([[5, 6]]) >>> np.concatenate((a, b), axis=0) array([[1, 2],[3, 4],[5, 6]])

參考：《白話大數(shù)據(jù)與機(jī)器學(xué)習(xí)》

總結(jié)

以上是生活随笔為你收集整理的维特比算法—打字输入预测的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。