引言
文章根據(jù)udacity自然語(yǔ)言處理進(jìn)行整理，提供給初學(xué)者進(jìn)行參考诱篷。主要圍繞隱馬爾可夫的基本實(shí)現(xiàn)原理和維特比算法進(jìn)行介紹。
相關(guān)參考學(xué)習(xí)視頻：
udacity--自然語(yǔ)言處理（PS：國(guó)外導(dǎo)師視頻課程尤泽，中文字幕脆淹。課程簡(jiǎn)潔易懂签杈、生動(dòng)形象瘫镇。具有項(xiàng)目實(shí)戰(zhàn)、導(dǎo)師項(xiàng)目審核特色答姥。比較推薦入門铣除。點(diǎn)擊此處可獲得課程優(yōu)惠券）
1. 概述
在自然語(yǔ)言中，一個(gè)句子通常是由多個(gè)詞組成鹦付、包含形容詞尚粘、名詞、動(dòng)詞等等敲长。如下面的這個(gè)句子：Mary had a little lamb 郎嫁。如何找出每個(gè)詞對(duì)應(yīng)的詞性是問題的重點(diǎn)。這里將探討如何使用隱馬爾可夫模型進(jìn)行詞性標(biāo)注祈噪。
隱馬爾可夫模型還用于語(yǔ)音識(shí)別和語(yǔ)音生成泽铛、機(jī)器翻譯、生物信息學(xué)基因識(shí)別和計(jì)算機(jī)視覺人類手勢(shì)識(shí)別辑鲤，等等盔腔。
2. 隱馬爾可夫模型
介紹馬爾可夫模型的基本原理。
假設(shè)標(biāo)記句子 “Jane will spot Will ” 的方式是名詞月褥、情態(tài)動(dòng)詞弛随、動(dòng)詞、名詞宁赤。
需要計(jì)算兩種概率舀透，一是轉(zhuǎn)移概率，即名詞后面是情態(tài)動(dòng)詞决左、情態(tài)動(dòng)詞后面是動(dòng)詞愕够、動(dòng)詞后面是名詞的概率；另一種是發(fā)射概率哆窿，即 N 名詞是Jane链烈、情態(tài)動(dòng)詞是 will 等等的概率厉斟。如下圖
發(fā)射概率的計(jì)算
如下圖的一些句子挚躯，可以看作是語(yǔ)料。每個(gè)句子做了標(biāo)注擦秽。
發(fā)射概率的計(jì)算码荔，如果單詞是n(名詞) 漩勤，那該單詞是 Mary 或 Jane 的概率。為此缩搅，可先創(chuàng)建一個(gè)這樣的表格越败，如下圖所示。N硼瓣、M究飞、V 分別表示詞性。其中 Mary 在語(yǔ)料句子中作為 N 出現(xiàn)了 4次堂鲤。
之后將每列除以條目之和亿傅，獲得這些數(shù)字。如此就計(jì)算出了相應(yīng)的發(fā)射概率瘟栖。注意單詞可以重復(fù)出現(xiàn)葵擎，例如 will 即是名詞又是情態(tài)動(dòng)詞。
轉(zhuǎn)移概率的計(jì)算
首先需要給每個(gè)句子添加一個(gè)開始和結(jié)束的標(biāo)簽半哟。當(dāng)然這些標(biāo)簽也可以作為詞性〕曷耍現(xiàn)在創(chuàng)建計(jì)數(shù)表，計(jì)算每個(gè)詞性出現(xiàn)的次數(shù)寓涨。如下圖的 3 盯串，表示名詞N 后面出現(xiàn)的情態(tài)動(dòng)詞 M 的次數(shù)為 3 次。
為了計(jì)算概率缅茉，需要將每行中的條目除以行中條目的和嘴脾。如下圖情態(tài)動(dòng)詞動(dòng)詞M之后是名詞N的概率為 1/4； M情態(tài)動(dòng)詞之后是動(dòng)詞V的概率為 3/4 蔬墩。這個(gè)就是轉(zhuǎn)移概率译打。
最后一步就是將轉(zhuǎn)移概率和發(fā)射概率合并。形成馬爾可夫模型拇颅。如下圖所示
根據(jù)上圖的馬爾可夫模型奏司。來看具體的實(shí)現(xiàn)原理。從 <S> 開始樟插， <S> 到 N 的概率為 韵洋，即轉(zhuǎn)移概率為 3/4 。當(dāng) Jane 為 N 名詞時(shí)概率為 2/9 黄锤，即發(fā)射概率 2/9 搪缨。
再?gòu)?N 轉(zhuǎn)移到 M 的，轉(zhuǎn)移概率為1/3 鸵熟，生成 Will 的發(fā)射概率為 3/4 副编。然后再到 V ，最后后到 <E> 結(jié)束流强。如此計(jì)算痹届，便得到了一條句子的所有概率呻待。
之后將所有概率進(jìn)行相乘。得到了這個(gè)句子的概率為 0.0003858 队腐。這個(gè)值可能比較小蚕捉，但考慮到可以生成大量長(zhǎng)度不等的句子，該值已經(jīng)很大了柴淘。
通常做法是從所有可能的詞性組合中選擇生成概率最高的句子迫淹。如在下面的兩個(gè)句子中，生成的句子一樣为严，但詞性不同 千绪，導(dǎo)致概率也不一樣。選擇最大概率的組合作為最終的句子梗脾。
路徑裁剪
如果從所有可能的詞性組合中選擇生成概率最高的句子荸型。假如有這樣的一個(gè)句子： Jane will spot Will? 和 對(duì)應(yīng)的三種詞性 N、M炸茧、V瑞妇。找出所有可能的詞性組合。這里得到的詞性組合就等于 3 的4次方梭冠，即 81 種辕狰。這呈現(xiàn)一種指數(shù)計(jì)算，如果句子越長(zhǎng)控漠，那句子組合數(shù)量也將越大蔓倍。最終是需要找到概率最大的路徑，如果有 81 種路徑組合盐捷，意味著需要計(jì)算 81 次偶翅。這會(huì)影響計(jì)算效率到此需要使用 維特比算法來減少計(jì)算量。
在使用維特比算法之前碉渡，先進(jìn)行裁剪聚谁。我們計(jì)算概率是將所有的發(fā)射概率和轉(zhuǎn)移概率相乘，但如果路徑中有0 值滞诺，則可不用計(jì)算形导，因?yàn)?0 乘以任何數(shù)都為 0 。 如下圖中的概率值：
（備注： 下圖中僅對(duì) Jane will spot Will 做了發(fā)射概率的標(biāo)示习霹，即 Jane 是 N 名詞的概率為 2/9 朵耕。對(duì)照發(fā)射概率表為 2/9 。）
到此刪除發(fā)射概率和轉(zhuǎn)移概率中只要有 0 出現(xiàn)的路徑×芤叮現(xiàn)在可得到如下圖的模型阎曹。到此裁剪后的路徑為 4 條。
將4條路徑上的概率相乘，得到的結(jié)果進(jìn)行比較芬膝。可得到概率最大的路徑形娇，也就是最后需要的路徑锰霜。
維特比算法
在上面使用路徑裁剪的方式，將 81 種詞性組合路徑刪減為 4 種伟骨。還有一種算法歉摧，只查看兩個(gè)路徑并合并他們安聘。
如下圖，在 N 這個(gè)點(diǎn)上友存。有兩種路徑可以到達(dá)√招疲可分別計(jì)算兩種路徑的概率屡立，可發(fā)現(xiàn)左邊的路徑比右邊的路徑概率小很多。因此將忽略左邊的路徑搀军，而采用右邊的路徑膨俐。這是維特比算法的基本思想。
來看維特比算法的具體實(shí)現(xiàn)罩句。再利用上圖中使用的? Jane will spot Will 句子和 N焚刺、M、V 詞性门烂。
根據(jù)發(fā)射概率表和轉(zhuǎn)移概率表乳愉。從 <S> 到 N 的轉(zhuǎn)移概率為 3/4 。 對(duì)應(yīng)的 Jane 是 N 的概率為 2/9 屯远。同樣的 <S> 到 M 的轉(zhuǎn)移概率為 1/4 蔓姚，Jane 是 N 的概率為 0 。<S> 到 V 的轉(zhuǎn)移概率為 0 慨丐，Jane 是 V 的概率為 0 赂乐。
因此生成節(jié)點(diǎn)的概率是 發(fā)射概率 * 轉(zhuǎn)移概率。即 <S> 到 N 的轉(zhuǎn)移概率和 Jane 是N的發(fā)射概率 ：? (3/4) * (2/9) = 1/6 咖气。同理計(jì)算? <S> 到 M 的轉(zhuǎn)移概率和 Jane 是M的發(fā)射概率分別為 0 挨措。
再轉(zhuǎn)到下個(gè)單詞 will ，有三個(gè)路徑指向 N崩溪、即轉(zhuǎn)移概率分別是 1/9浅役、1/4 和 1。同時(shí) will 是 N 的發(fā)射概率為 1/9 伶唯。如此再計(jì)算三個(gè)路徑上概率值觉既，保留最大的概率值。似乎 1/6 * 1/9 * 1/9 是最大值。
同樣的方式計(jì)算M和V瞪讼，并保留最大的概率值钧椰。重復(fù)的方式進(jìn)行，知道句子末尾符欠。如此可得到如下的結(jié)果嫡霞，忽略0的路徑
如何找到最佳路徑，可從后往前追蹤希柿。即 <E> -> N -> V -> M -> M -> N -> <S> 這便是最佳路徑诊沪。
3. 相關(guān)文獻(xiàn)
語(yǔ)音和語(yǔ)言處理圖書的隱馬爾可夫模型和詞性標(biāo)注。
4. 項(xiàng)目實(shí)現(xiàn)
在 notebook 中曾撤，使用?Pomegranate?庫(kù)構(gòu)建隱馬爾可夫模型端姚，并使用通用標(biāo)簽集進(jìn)行詞性標(biāo)注。在使用更大型的標(biāo)簽集對(duì)實(shí)際文本語(yǔ)料庫(kù)進(jìn)行標(biāo)注時(shí)挤悉，隱馬爾可夫模型的準(zhǔn)確率達(dá)到了 96% 以上渐裸。隱馬爾可夫模型還用于語(yǔ)音識(shí)別和語(yǔ)音生成、機(jī)器翻譯装悲、生物信息學(xué)基因識(shí)別和計(jì)算機(jī)視覺人類手勢(shì)識(shí)別橄仆，等等。
項(xiàng)目可訪問此 github 衅斩，使用 jupyter notebook 打開盆顾。
