1. 賭場風(fēng)云(背景介紹)
最近一個賭場的老板發(fā)現(xiàn)生意不暢，于是派出手下去賭場張望。經(jīng)探子回報，有位大叔在賭場中總能贏到錢，玩得一手好骰子，幾乎是戰(zhàn)無不勝。而且每次玩骰子的時候周圍都有幾個保鏢站在身邊，讓人不明就里，只能看到每次開局，骰子飛出，沉穩(wěn)落地。老板根據(jù)多年的經(jīng)驗(yàn)，推測這位不善之客使用的正是江湖失傳多年的"偷換骰子大法”(編者注:偷換骰子大法，用兜里自帶的骰子偷偷換掉均勻的骰子)。老板是個冷靜的人，看這位大叔也不是善者，不想輕易得罪他，又不想讓他壞了規(guī)矩。正愁上心頭，這時候進(jìn)來一位名叫HMM帥哥，告訴老板他有一個很好的解決方案。
不用近其身，只要在遠(yuǎn)處裝個攝像頭，把每局的骰子的點(diǎn)數(shù)都記錄下來。
然后HMM帥哥將會運(yùn)用其強(qiáng)大的數(shù)學(xué)內(nèi)力，用這些數(shù)據(jù)推導(dǎo)出
1. 該大叔是不是在出千?
2. 如果是在出千，那么他用了幾個作弊的骰子? 還有當(dāng)前是不是在用作弊的骰子。
3. 這幾個作弊骰子出現(xiàn)各點(diǎn)的概率是多少?
天吶，老板一聽，這位叫HMM的甚至都不用近身，就能算出是不是在作弊，甚至都能算出別人作弊的骰子是什么樣的。那么，只要再當(dāng)他作弊時，派人圍捕他，當(dāng)場驗(yàn)證骰子就能讓他啞口無言。
在讓HMM開展調(diào)查活動之前，該賭場老板也對HMM作了一番調(diào)查。
HMM(Hidden Markov Model), 也稱隱性馬爾可夫模型，是一個概率模型，用來描述一個系統(tǒng)隱性狀態(tài)的轉(zhuǎn)移和隱性狀態(tài)的表現(xiàn)概率。
系統(tǒng)的隱性狀態(tài)指的就是一些外界不便觀察(或觀察不到)的狀態(tài), 比如在當(dāng)前的例子里面, 系統(tǒng)的狀態(tài)指的是大叔使用骰子的狀態(tài)，即
{正常骰子, 作弊骰子1, 作弊骰子2,...}
隱性狀態(tài)的表現(xiàn)也就是, 可以觀察到的，由隱性狀態(tài)產(chǎn)生的外在表現(xiàn)特點(diǎn)。這里就是說, 骰子擲出的點(diǎn)數(shù).
{1,2,3,4,5,6}
HMM模型將會描述，系統(tǒng)隱性狀態(tài)的轉(zhuǎn)移概率。也就是大叔切換骰子的概率,下圖是一個例子，這時候大叔切換骰子的可能性被描述得淋漓盡致。
很幸運(yùn)的，這么復(fù)雜的概率轉(zhuǎn)移圖，竟然能用簡單的矩陣表達(dá), 其中a_{ij}代表的是從i狀態(tài)到j(luò)狀態(tài)發(fā)生的概率
當(dāng)然同時也會有，隱性狀態(tài)表現(xiàn)轉(zhuǎn)移概率。也就是骰子出現(xiàn)各點(diǎn)的概率分布, (e.g. 作弊骰子1能有90%的機(jī)會擲到六，作弊骰子2有85%的機(jī)會擲到'小’). 給個圖如下,
隱性狀態(tài)的表現(xiàn)分布概率也可以用矩陣美麗地表示出來，
把這兩個東西總結(jié)起來，就是整個HMM模型。
這個模型描述了隱性狀態(tài)的轉(zhuǎn)換的概率，同時也描述了每個狀態(tài)外在表現(xiàn)的概率的分布?？傊?，HMM模型就能夠描述扔骰子大叔作弊的頻率(骰子更換的概率)，和大叔用的骰子的概率分布。有了大叔的HMM模型，就能把大叔看透，讓他完全在陽光下現(xiàn)形。
總結(jié)起來HMM能處理三個問題，
解碼就是需要從一連串的骰子中，看出來哪一些骰子是用了作弊的骰子，哪些是用的正常的骰子。
比如上圖中，給出一串骰子序列(3,6,1,2..)和大叔的HMM模型, 我們想要計(jì)算哪一些骰子的結(jié)果(隱性狀態(tài)表現(xiàn))可能對是哪種骰子的結(jié)果(隱性狀態(tài)).
學(xué)習(xí)就是，從一連串的骰子中，學(xué)習(xí)到大叔切換骰子的概率，當(dāng)然也有這些骰子的點(diǎn)數(shù)的分布概率。這是HMM最為恐怖也最為復(fù)雜的招數(shù)??！
估計(jì)說的是，在我們已經(jīng)知道了該大叔的HMM模型的情況下，估測某串骰子出現(xiàn)的可能性概率。比如說，在我們已經(jīng)知道大叔的HMM模型的情況下，我們就能直接估測到大叔扔到10個6或者8個1的概率。
估計(jì)是最容易的一招，在完全知道了大叔的HMM模型的情況下，我們很容易就能對其做出估計(jì)。
現(xiàn)在我們有了大叔的狀態(tài)轉(zhuǎn)移概率矩陣A,B就能夠進(jìn)行估計(jì)。比如我們想知道這位大叔下一局連續(xù)擲出10個6的概率是多少? 如下
這表示的是，在一開始隱性狀態(tài)(s0)為1，也就是一開始拿著的是正常的骰子的情況下，這位大叔連續(xù)擲出10個6的概率。
現(xiàn)在問題難就難在，我們雖然知道了HMM的轉(zhuǎn)換概率，和觀察到的狀態(tài)V{1:T}, 但是我們卻不知道實(shí)際的隱性的狀態(tài)變化。
好吧，我們不知道隱性狀態(tài)的變化，那好吧，我們就先假設(shè)一個隱性狀態(tài)序列, 假設(shè)大叔前5個用的是正常骰子, 后5個用的是作弊骰子1.
好了，那么我們可以計(jì)算，在這種隱性序列假設(shè)下擲出10個6的概率.
但是問題又出現(xiàn)了，剛才那個隱性狀態(tài)序列是我假設(shè)的，而實(shí)際的序列我不知道，這該怎么辦。好辦，把所有可能出現(xiàn)的隱狀態(tài)序列組合全都試一遍就可以了。于是,
解碼的過程就是在給出一串序列的情況下和已知HMM模型的情況下，找到最可能的隱性狀態(tài)序列。
用數(shù)學(xué)公式表示就是, (V是Visible可見序列, w是隱性狀態(tài)序列, A,B是HMM狀態(tài)轉(zhuǎn)移概率矩陣)
然后又可以使用估計(jì)(4.1)中的前向推導(dǎo)法，計(jì)算出最大的P(w(1:T), V(1:T)).
在完成前向推導(dǎo)法之后，再使用后向追蹤法(Back Tracking)，對求解出能令這個P(w(1:T), V(1:T))最大的隱性序列.這個算法被稱為維特比算法(Viterbi Algorithm).
這是動態(tài)規(guī)劃算法的一種, 解法都是一樣的, 找到遞歸方程后用前向推導(dǎo)求解.然后使用后向追蹤法找到使得方程達(dá)到最優(yōu)解的組合. 以下是一個計(jì)算骰子序列{1,2,6}最有可能的隱性序列組合.(初始狀態(tài)為1=正常骰子,)
學(xué)習(xí)是在給出HMM的結(jié)構(gòu)的情況下(比如說假設(shè)已經(jīng)知道該大叔有3只骰子，每只骰子有6面),計(jì)算出最有可能的模型參數(shù).
在假設(shè)完HMM的結(jié)構(gòu)以后，就可以使用EM(Expectation Maximization) 算法最大化Likelihood. 這里的最大似然是,
以上舉的例子是用HMM對擲骰子進(jìn)行建模與分析。當(dāng)然還有很多HMM經(jīng)典的應(yīng)用，能根據(jù)不同的應(yīng)用需求，對問題進(jìn)行建模。
但是使用HMM進(jìn)行建模的問題，必須滿足以下條件,
1.隱性狀態(tài)的轉(zhuǎn)移必須滿足馬爾可夫性。(狀態(tài)轉(zhuǎn)移的馬爾可夫性:一個狀態(tài)只與前一個狀態(tài)有關(guān))
2. 隱性狀態(tài)必須能夠大概被估計(jì)。
在滿足條件的情況下,確定問題中的隱性狀態(tài)是什么,隱性狀態(tài)的表現(xiàn)可能又有哪些.
HMM適用于的問題在于，真正的狀態(tài)(隱態(tài))難以被估計(jì)，而狀態(tài)與狀態(tài)之間又存在聯(lián)系。
語音識別問題就是將一段語音信號轉(zhuǎn)換為文字序列的過程. 在個問題里面
隱性狀態(tài)就是: 語音信號對應(yīng)的文字序列
而顯性的狀態(tài)就是: 語音信號.
HMM模型的學(xué)習(xí)(Learning): 語音識別的模型學(xué)習(xí)和上文中通過觀察骰子序列建立起一個最有可能的模型不同. 語音識別的HMM模型學(xué)習(xí)有兩個步驟:
1. 統(tǒng)計(jì)文字的發(fā)音概率,建立隱性表現(xiàn)概率矩陣Ｂ
2. 統(tǒng)計(jì)字詞之間的轉(zhuǎn)換概率(這個步驟并不需要考慮到語音,可以直接統(tǒng)計(jì)字詞之間的轉(zhuǎn)移概率即可)
語音模型的估計(jì)(Evaluation): 計(jì)算"是十四”,"四十四"等等的概率,比較得出最有可能出現(xiàn)的文字序列.
5.2 手寫識別
這是一個和語音差不多,只不過手寫識別的過程是將字的圖像當(dāng)成了顯性序列.
“總所周知，在漢語中，詞與詞之間不存在分隔符（英文中，詞與詞之間用空格分隔，這是天然的分詞標(biāo)記），詞本身也缺乏明顯的形態(tài)標(biāo)記，因此，中文信息處理的特有問題就是如何將漢語的字串分割為合理的詞語序。例如，英文句子：you should go to kindergarten now 天然的空格已然將詞分好，只需要去除其中的介詞“to”即可；而“你現(xiàn)在應(yīng)該去幼兒園了”這句表達(dá)同樣意思的話沒有明顯的分隔符，中文分詞的目的是，得到“你/現(xiàn)在/應(yīng)該/去/幼兒園/了”。那么如何進(jìn)行分詞呢？主流的方法有三種：第1類是基于語言學(xué)知識的規(guī)則方法，如：各種形態(tài)的最大匹配、最少切分方法；第2類是基于大規(guī)模語料庫的機(jī)器學(xué)習(xí)方法，這是目前應(yīng)用比較廣泛、效果較好的解決方案．用到的統(tǒng)計(jì)模型有N元語言模型、信道—噪聲模型、最大期望、HMM等。第3類也是實(shí)際的分詞系統(tǒng)中用到的，即規(guī)則與統(tǒng)計(jì)等多類方法的綜合?！盵1]使用HMM進(jìn)行中文分詞.
拼音輸入法,是一個估測拼音字母對應(yīng)想要輸入的文字(隱性狀態(tài))的過程(比如, ‘pingyin’ -> 拼音)
參考:
http://ai.stanford.edu/~serafim/CS262_2007/notes/lecture5.pdf
https://greenpages.eecs.qmul.ac.uk/courseinfo/elem041/documents/2012-10-HMMs.pdf
