什么問(wèn)題用HMM解決
現(xiàn)實(shí)生活中有這樣一類(lèi)隨機(jī)現(xiàn)象盼砍，在已知現(xiàn)在情況的條件下尘吗，未來(lái)時(shí)刻的情況只與現(xiàn)在有關(guān)，而與遙遠(yuǎn)的過(guò)去并無(wú)直接關(guān)系浇坐。
比如天氣預(yù)測(cè)睬捶，如果我們知道“晴天，多云近刘，雨天”之間的轉(zhuǎn)換概率擒贸，那么如果今天是晴天，我們就可以推斷出明天是各種天氣的概率觉渴，接著后天的天氣可以由明天的進(jìn)行計(jì)算介劫。這類(lèi)問(wèn)題可以用 Markov 模型來(lái)描述。
進(jìn)一步案淋，如果我們并不知道今天的天氣屬于什么狀況蜕猫，我們只知道今明后三天的水藻的干燥濕潤(rùn)狀態(tài)，因?yàn)樗宓臓顟B(tài)和天氣有關(guān)哎迄，我們想要通過(guò)水藻來(lái)推測(cè)這三天的真正的天氣會(huì)是什么回右，這個(gè)時(shí)候就用 Hidden Markov 模型來(lái)描述。
HMM 模型的本質(zhì)是從觀察的參數(shù)中獲取隱含的參數(shù)信息漱挚，并且前后之間的特征會(huì)存在部分的依賴(lài)影響翔烁。
我們從如何進(jìn)行中文分詞的角度來(lái)理解HMM
根據(jù)可觀察狀態(tài)的序列找到一個(gè)最可能的隱藏狀態(tài)序列
中文分詞，就是給一個(gè)漢語(yǔ)句子作為輸入旨涝，以“BEMS”組成的序列串作為輸出蹬屹，然后再進(jìn)行切詞，進(jìn)而得到輸入句子的劃分白华。其中慨默，B代表該字是詞語(yǔ)中的起始字，M代表是詞語(yǔ)中的中間字弧腥，E代表是詞語(yǔ)中的結(jié)束字厦取，S則代表是單字成詞。
例如：給個(gè)句子
小明碩士畢業(yè)于中國(guó)科學(xué)院計(jì)算所
得到BEMS組成的序列為
BEBEBMEBEBMEBES
因?yàn)榫湮仓豢赡苁荅或者S管搪，所以得到切詞方式為
BE/BE/BME/BE/BME/BE/S
進(jìn)而得到中文句子的切詞方式為
小明/碩士/畢業(yè)于/中國(guó)/科學(xué)院/計(jì)算/所
這是個(gè)HMM問(wèn)題虾攻，因?yàn)槟阆胍玫降氖敲總€(gè)字的位置，但是看到的只是這些漢字更鲁，需要通過(guò)漢字來(lái)推出每個(gè)字在詞語(yǔ)中的位置霎箍，并且每個(gè)字屬于什么狀態(tài)還和它之前的字有關(guān)。
此時(shí)澡为，我們需要根據(jù)可觀察狀態(tài)的序列找到一個(gè)最可能的隱藏狀態(tài)序列漂坏。
五元組，三類(lèi)問(wèn)題媒至，兩個(gè)假設(shè)
五元組
通過(guò)上面的例子顶别，我們可以知道 HMM 有以下5個(gè)要素。
觀測(cè)序列－O：小明碩士畢業(yè)于中國(guó)科學(xué)院計(jì)算所
狀態(tài)序列－S：BEBEBMEBEBMEBES
初始狀態(tài)概率向量－π：句子的第一個(gè)字屬于{B,E,M,S}這四種狀態(tài)的概率
狀態(tài)轉(zhuǎn)移概率矩陣－A：如果前一個(gè)字位置是B塘慕，那么后一個(gè)字位置為BEMS的概率各是多少
觀測(cè)概率矩陣－B：在狀態(tài)B的條件下筋夏，觀察值為耀的概率，取對(duì)數(shù)后是-10.460
備注：示例數(shù)值是對(duì)概率值取對(duì)數(shù)之后的結(jié)果图呢，為了將概率相乘的計(jì)算變成對(duì)數(shù)相加条篷，其中-3.14e+100作為負(fù)無(wú)窮，也就是對(duì)應(yīng)的概率值是0
三類(lèi)問(wèn)題
當(dāng)通過(guò)五元組中某些已知條件來(lái)求未知時(shí)蛤织，就得到HMM的三類(lèi)問(wèn)題：
- 似然度問(wèn)題：參數(shù)(O赴叹，π，A指蚜，B)已知的情況下乞巧，求(π，A摊鸡，B)下觀測(cè)序列O出現(xiàn)的概率绽媒。(Forward-backward算法)
- 解碼問(wèn)題：參數(shù)(O蚕冬，π，A是辕，B)已知的情況下恋技，求解狀態(tài)值序列S豪嚎。(viterbi算法)
- 學(xué)習(xí)問(wèn)題：參數(shù)(O)已知的情況下，求解(π，A脱惰，B)霍衫。(Baum-Welch算法)
中文分詞這個(gè)例子屬于第二個(gè)問(wèn)題器紧，即解碼問(wèn)題韧拒。
我們希望找到 s_1,s_2,s_3,... 使 P (s_1,s_2,s_3,...|o_1,o_2,o_3....) 達(dá)到最大。
意思是贞谓，當(dāng)我們觀測(cè)到語(yǔ)音信號(hào) o_1,o_2,o_3,... 時(shí)限佩，我們要根據(jù)這組信號(hào)推測(cè)出發(fā)送的句子 s_1,s_2,s_3,....，顯然经宏，我們應(yīng)該在所有可能的句子中找最有可能性的一個(gè)犀暑。
兩個(gè)假設(shè)
利用貝葉斯公式得到：
這里需要用到兩個(gè)假設(shè)來(lái)進(jìn)一步簡(jiǎn)化上述公式
有限歷史性假設(shè): si 只由 si-1 決定
獨(dú)立輸出假設(shè)：第 i 時(shí)刻的接收信號(hào) oi 只由發(fā)送信號(hào) si 決定
有了上面的假設(shè)，就可以利用算法 Viterbi 找出目標(biāo)概率的最大值烁兰。
Viterbi算法
根據(jù)動(dòng)態(tài)規(guī)劃原理耐亏，最優(yōu)路徑具有這樣的特性：如果最優(yōu)路徑從結(jié)點(diǎn) i_{t}^* 到終點(diǎn) i_{T}^，那么這兩點(diǎn)之間的所有可能的部分路徑必須是最優(yōu)的沪斟。
依據(jù)這一原理广辰，我們只需從時(shí)刻 t=1 開(kāi)始，遞推地計(jì)算在時(shí)刻 t 狀態(tài)為 i 的各條部分路徑的最大概率主之，直至得到時(shí)刻 t=T 狀態(tài)為 i 的各條路徑的最大概率 P^择吊，最優(yōu)路徑的終結(jié)點(diǎn) i_{T}^* 也同時(shí)得到。之后槽奕，為了找出最優(yōu)路徑的各個(gè)結(jié)點(diǎn)几睛，從終結(jié)點(diǎn) i_{T}^* 開(kāi)始，由后向前逐步求得結(jié)點(diǎn) i_{T-1}*...粤攒，i_{1}所森，進(jìn)而得到最優(yōu)路徑 I^＝i_{1}*...，i_{T}*夯接，這就是維特比算法.
舉個(gè)栗子：
觀測(cè)序列 O＝(紅焕济，白，紅)盔几，想要求狀態(tài)序列S晴弃。
需要定義兩個(gè)變量:
- weight[3][3]，行3是狀態(tài)數(shù)(1，2上鞠，3)际邻，列3是觀察值個(gè)數(shù)(紅，白旗国，紅)枯怖。意思是，在時(shí)刻 t 狀態(tài)為 i 的所有單個(gè)路徑中的概率最大值能曾。
- path[3][3]，意思是肿轨，在時(shí)刻 t 狀態(tài)為 i 的所有單個(gè)路徑中概率最大的那條路徑寿冕，它的第 t-1 個(gè)結(jié)點(diǎn)是什么。比如 path[0][2]=1, 則代表 weight[0][2] 取到最大時(shí)椒袍，前一個(gè)時(shí)刻的狀態(tài)是 1.
1.初始化
t＝1 時(shí)的紅驼唱，分別是在狀態(tài) 1，2驹暑，3 的條件下觀察得來(lái)的概率計(jì)算如下：
此時(shí) path 的第一列全是 0.
2.遞歸
t＝2 時(shí)的白玫恳，如果此時(shí)是在 1 的條件下觀察得來(lái)的話，先計(jì)算此時(shí)狀態(tài)最可能是由前一時(shí)刻的哪個(gè)狀態(tài)轉(zhuǎn)換而來(lái)的优俘，取這個(gè)最大值京办，再乘以 1 條件下觀測(cè)到 白 的概率，同時(shí)記錄 path矩陣：如下圖 weight[0][1]=0.028帆焕，此值來(lái)源于前一時(shí)刻狀態(tài)是3惭婿，所以，
3.終止
在 t＝3 時(shí)的最大概率 P^＝0.0147叶雹，相應(yīng)的最優(yōu)路徑的終點(diǎn)是 i_3^=3.
4.回溯
由最優(yōu)路徑的終點(diǎn) 3 開(kāi)始财饥，向前找到之前時(shí)刻的最優(yōu)點(diǎn)：
在 t＝2 時(shí)，因 i_3^=3折晦，狀態(tài) 3 的最大概率 P＝0.0147钥星，來(lái)源于狀態(tài) 3，所以 i_2^=3.
在 t＝1 時(shí)满着，因 i_2^=3谦炒，狀態(tài) 3 的最大概率 P＝0.042，來(lái)源于狀態(tài) 3漓滔，所以 i_1^=3.
最后得到最優(yōu)路徑為 I*＝(i_{1}编饺，i_{2}^，i_{3}^*)＝(3,3,3)
用Viterbi算法求解中文分詞問(wèn)題
根據(jù)上面講的 HMM 和 Viterbi响驴，接下來(lái)對(duì)中文分詞這個(gè)問(wèn)題透且，構(gòu)造五元組并用算法進(jìn)行求解。
InitStatus：π
TransProbMatrix：A
EmitProbMatrix：B
Viterbi求解
經(jīng)過(guò)這個(gè)算法后，會(huì)得到兩個(gè)矩陣 weight 和 path：
二維數(shù)組 weight[4][15]秽誊，4是狀態(tài)數(shù)(0:B,1:E,2:M,3:S)鲸沮，15是輸入句子的字?jǐn)?shù)。比如 weight[0][2] 代表 狀態(tài)B的條件下锅论，出現(xiàn)'碩'這個(gè)字的可能性讼溺。
二維數(shù)組 path[4][15]，4是狀態(tài)數(shù)(0:B,1:E,2:M,3:S)最易，15是輸入句子的字?jǐn)?shù)怒坯。比如 path[0][2] 代表 weight[0][2]取到最大時(shí)，前一個(gè)字的狀態(tài)藻懒，比如 path[0][2] = 1, 則代表 weight[0][2]取到最大時(shí)剔猿，前一個(gè)字(也就是明)的狀態(tài)是E。記錄前一個(gè)字的狀態(tài)是為了使用viterbi算法計(jì)算完整個(gè) weight[4][15] 之后嬉荆，能對(duì)輸入句子從右向左地回溯回來(lái)归敬，找出對(duì)應(yīng)的狀態(tài)序列。
先對(duì) weight 進(jìn)行初始化鄙早，
使用 InitStatus 和 EmitProbMatrix 對(duì) weight 二維數(shù)組進(jìn)行初始化汪茧。
由 EmitProbMatrix 可以得出
所以可以初始化 weight[i][0] 的值如下：
注意上式計(jì)算的時(shí)候是相加而不是相乘，因?yàn)橹叭∵^(guò)對(duì)數(shù)的原因限番。
然后遍歷找到 weight 每項(xiàng)的最大值舱污，同時(shí)記錄了相應(yīng)的 path
//遍歷句子，下標(biāo)i從1開(kāi)始是因?yàn)閯偛懦跏蓟臅r(shí)候已經(jīng)對(duì)0初始化結(jié)束了
for(size_t i = 1; i < 15; i++)
{
// 遍歷可能的狀態(tài)
for(size_t j = 0; j < 4; j++)
{
weight[j][i] = MIN_DOUBLE;
path[j][i] = -1;
//遍歷前一個(gè)字可能的狀態(tài)
for(size_t k = 0; k < 4; k++)
{
double tmp = weight[k][i-1] + _transProb[k][j] + _emitProb[j][sentence[i]];
if(tmp > weight[j][i]) // 找出最大的weight[j][i]值
{
weight[j][i] = tmp;
path[j][i] = k;
}
}
}
}
如此遍歷下來(lái)扳缕，weight[4][15] 和 path[4][15] 就都計(jì)算完畢慌闭。
確定邊界條件和路徑回溯
邊界條件如下：
對(duì)于每個(gè)句子，最后一個(gè)字的狀態(tài)只可能是 E 或者 S躯舔，不可能是 M 或者 B驴剔。
所以在本文的例子中我們只需要比較 weight[1(E)][14] 和 weight[3(S)][14] 的大小即可。
在本例中：
weight[1][14] = -102.492;
weight[3][14] = -101.632;
所以 S > E粥庄，也就是對(duì)于路徑回溯的起點(diǎn)是 path[3][14]丧失。
進(jìn)行回溯，得到序列
SEBEMBEBEMBEBEB惜互。
再進(jìn)行倒序布讹，得到
BEBEBMEBEBMEBES
接著進(jìn)行切詞得到
BE/BE/BME/BE/BME/BE/S
最終就找到了分詞的方式
小明/碩士/畢業(yè)于/中國(guó)/科學(xué)院/計(jì)算/所
HMM還有哪些應(yīng)用
HMM不只用于中文分詞，如果把 S 換成句子训堆，O 換成語(yǔ)音信號(hào)描验，就變成了語(yǔ)音識(shí)別問(wèn)題，如果把 S 換成中文坑鱼，O 換成英文膘流，就變成了翻譯問(wèn)題絮缅，如果把 S 換成文字，O 換成圖像呼股，就變成了文字識(shí)別問(wèn)題耕魄，此外還有詞性標(biāo)注等等問(wèn)題。
對(duì)于上述每種問(wèn)題彭谁，只要知道了五元組中的三個(gè)參數(shù)矩陣吸奴，就可以應(yīng)用 Viterbi 算法得到結(jié)果。
