男生和女生分別是來自不同星球的科學(xué)事實(shí)已經(jīng)眾所周知的了.男生們總是認(rèn)為,女生們都是迷一樣的生物,他們的情感狀態(tài)浮動(dòng)似乎是以秒單位在變化的,難以理解,更勿論預(yù)測(cè)了! 而女生們覺得男生都是沒有感覺動(dòng)物,完全不能理解什么叫感受-盡管已經(jīng)告訴他們N次了!這種男女之間的根本差別,導(dǎo)致了他們之間的感情關(guān)系是受一種超級(jí)無敵復(fù)雜的系統(tǒng)所支配的.

不過,我們可以用一個(gè)叫隱式馬爾可夫(Hidden Markov Model)的數(shù)學(xué)模型來分析這個(gè)系統(tǒng).

決定性系統(tǒng)

首先我們來看看一種最簡(jiǎn)單的預(yù)測(cè)系統(tǒng) –決定性系統(tǒng).

在這個(gè)系統(tǒng)中,如果我們知道我們目前所在的狀態(tài),那么我們也就能夠毫無疑問地預(yù)測(cè)出下一個(gè)狀態(tài)是什么. 比如一年四季的輪替就是一個(gè)決定性系統(tǒng):每個(gè)季節(jié)的交替是完全可以預(yù)測(cè)的,如果現(xiàn)在是春天,那么下一個(gè)季節(jié)就一定會(huì)是夏天,冬天的前一個(gè)狀態(tài)就一定是秋天等等.另外值得一提的是,冬天過后,下一個(gè)季節(jié)就又會(huì)回到春天,以此循環(huán)…

另外一個(gè)常見的決定系統(tǒng),就是交通燈的輪換: 紅燈過后就應(yīng)該是綠燈. 綠燈過后就應(yīng)該是黃燈,然后又回到紅燈.

這種系統(tǒng)非常常見,人的一生大致也能看作是這種系統(tǒng). 有嬰兒,少年,成年,老年,然后死亡等幾種狀態(tài). 不過不同的是,人的一生又不是完全遵循這種狀態(tài)輪換的, 每個(gè)人都有那么丁點(diǎn)的可能性會(huì)跳過其中一個(gè)或者多個(gè)狀態(tài),直接到達(dá)死亡的狀態(tài)…(更勿論Benjamin Buttons的情況了,呵呵).

講到這里,聰明的男生或許已經(jīng)能想到,我們的世界里最為精妙,最雷人的非決定性系統(tǒng)就是 —你女朋友的情感狀態(tài)!

對(duì)于大部分男生來說,精確地預(yù)測(cè)女朋友的下一種的情感狀態(tài)基本上屬于扯淡.

一個(gè)mm現(xiàn)在可能心情很好,可是下一秒?yún)s進(jìn)入抓狂;她或許某個(gè)時(shí)刻處于悲傷,下個(gè)時(shí)刻卻變得異常興奮.在每個(gè)女生的情感狀態(tài)里面,都有一種基于概率卻又難以預(yù)測(cè)的本質(zhì),這種無序的本質(zhì)直接導(dǎo)致無數(shù)男生直接蹲地畫圈圈……

盡管看上去女生的情感狀態(tài)似乎毫無預(yù)測(cè)性可言,經(jīng)過一段長(zhǎng)時(shí)間的觀察,卻能發(fā)現(xiàn)這種現(xiàn)象是有規(guī)律的! 于是小明,作為一名計(jì)算機(jī)科學(xué)家, 決定要系統(tǒng)地去分析他女朋友的情感不確定性, 挖掘出里面的規(guī)律!

于是乎,小明仔細(xì)地記錄了半年來他女朋友小麗每天的喜怒哀樂變化狀態(tài), 并作了一張圖表(Table1)來表示小麗的歷史情感變化.

小明想知道, 有了這些數(shù)據(jù),他能否從中得出知道, 如果小麗某天的情感狀態(tài)是高興, 那么第二天她更多的是保持好心情呢,還是更多地變得悲傷了.如此等等…

數(shù)據(jù)勝于雄辯, 小明從這半年的數(shù)據(jù)里面發(fā)現(xiàn),當(dāng)小麗高興的時(shí)候,3/4的情況下第二天她仍然保持著好心情,只有1/4的情況小麗第二天心情會(huì)改變,比如變得氣憤,悲傷等等(小明真TM走運(yùn)!).小明繼續(xù)分析其他各種情感狀態(tài)變化情況,比如從高興到悲傷, 悲傷到氣憤, 高興到氣憤等所有的可能組合.很快小明就得到所有的組合變化數(shù)據(jù),從中得知對(duì)于任意小麗的某天情感狀態(tài)下,下一個(gè)最有可能的情感狀態(tài).

為了便于教學(xué),我們假設(shè)小明只關(guān)心小麗的四種感情狀態(tài): 高興 悲傷 氣憤 還有 憂慮

　　Table 1: 小麗的情緒狀態(tài)變化表

在這個(gè)表格中, 每個(gè)數(shù)字代表了小麗情緒從某列轉(zhuǎn)變到某行的概率. 比方說, 如果小麗某天的情緒是高興,那么她將有0.1的概率下一天她會(huì)變得 悲傷 或者是 氣憤, 有0.05的可能性轉(zhuǎn)變?yōu)?憂慮. 每一行代表了從某種情緒轉(zhuǎn)變到各種情緒的概率,因此每行的概率之和為 1.

同理,每一列代表了由各種情緒轉(zhuǎn)變?yōu)樵摿兴淼那榫w的概率,因此每列的概率總和也應(yīng)該為1.

我們可以畫一個(gè)狀態(tài)圖(圖1)來表示表格1, 每個(gè)圓圈代表著一種心情狀態(tài), 每?jī)煞N心情變化由一個(gè)有向弧,從當(dāng)前的心情狀態(tài)指向下一個(gè)心情狀態(tài)表示,每個(gè)弧上均帶有一個(gè)狀態(tài)轉(zhuǎn)換的概率.

　　Figure 1: 小麗的情緒狀態(tài)變化圖

有了這個(gè)圖表,小明就可以非常直觀地看得到小麗最有可能的下個(gè)心情會(huì)是如何. 她會(huì)很有可能變得悲傷嗎?(準(zhǔn)備好鮮花巧克力),還是更有可能是氣憤?(趕緊閃開!) 每天小明只需要看看哪個(gè)弧指向的心情概率最大就可以了.

這個(gè)過程,同學(xué)們,就是有名的 “馬爾可夫過程” (Markov process)

不過需要注意的是, 馬爾可夫過程有一些假設(shè)的前提. 在我們的例子里面, 預(yù)測(cè)下一天小麗的心情, 我們只依賴當(dāng)天小麗的心情,而沒有去考慮更先前她的心情. 很明顯這種假設(shè)下的模型是遠(yuǎn)不夠精確的. 很多時(shí)候,隨著日子一天一天的過去,女生一般會(huì)變得越來越體諒.經(jīng)常女生生氣了幾天后,氣就會(huì)慢慢消了. 比方說如果小麗已經(jīng)生氣了3天了,那么她第二天變得高興起來的可能性,在多數(shù)情況下,要比她只生氣了一天而第二天變得高興的可能性要高. 馬爾可夫過程并沒有考慮這個(gè), 用行話講, 就是馬爾可夫模型忽略遠(yuǎn)距離歷史效應(yīng) ( long range dependency).

我很佩服各位能堅(jiān)持讀到這里, 不過,還沒完呢, 我仍然沒有說,隱式馬爾可夫模型 (Hidden Markov Model)是什么呢! 諸位如果已經(jīng)有點(diǎn)頭昏腦漲,請(qǐng)就此打住,以免大腦過熱死機(jī)!

隱式馬爾可夫模型 –Hidden Markov Model, or HMM for short.

有些時(shí)候,我們無法直接觀測(cè)一個(gè)事物的狀態(tài). 比方說, 有些女生是很能隱瞞自己的情感而不流露出來的! 他們可能天天面帶微笑但不代表他們就天天高興. 因此我們必須要有竅門, 去依賴某些我們能夠直接觀察到的東西.

話說回來我們的主人公小明, 自從被小麗發(fā)現(xiàn)他這種近乎變態(tài)的科學(xué)分析行為后,變得非常善于隱藏自己的心情,導(dǎo)致某天小明錯(cuò)誤估計(jì)了小麗的心情!在誤以為那天小麗會(huì)心情好的情況下,小明告訴小麗自己不小心摔壞了她心愛的iPod…,小明沒想到其實(shí)那天小麗正因?yàn)榍耙惶戾e(cuò)過了商場(chǎng)名牌打折扣的活動(dòng)而異常氣憤… 一場(chǎng)血雨腥風(fēng)過后,兩個(gè)人最終分手了.

不過很快小明憑著自身的英俊高大瀟灑,很快又交上了另外一個(gè)女朋友 –小玲. 鑒于小明意識(shí)到,女生表面的情感流露非常不可靠, 小明決定要另尋他徑, 繼續(xù)預(yù)測(cè)女朋友的心情! (作為一個(gè)數(shù)據(jù)科學(xué)家,小明的確有著不怕碰壁的精神!)

小明每個(gè)月都幫小玲付信用卡的費(fèi)用(真不明白，有這樣的男朋友，小玲有什么理由不高興啊!), 因此小明每天都可以通過Online banking知道小玲每天都買了什么東西. 小明突然靈機(jī)一動(dòng): “沒準(zhǔn)我能通過觀測(cè)她的購(gòu)物規(guī)律,推導(dǎo)預(yù)測(cè)出小玲的心情!”.聽起來有點(diǎn)匪夷所思,不過這個(gè)過程,的的確確是可以使用叫作隱式馬爾可夫的數(shù)學(xué)模型來表示并分析的.

由于我們需要預(yù)測(cè)的變量 –心情狀態(tài) 是無法直接觀測(cè)的,是隱藏 (Hidden) 起來的.因此這種模型才叫隱式馬爾可夫模型.

在一次和小玲的好朋友們一起吃飯的時(shí)候, 小明得知了以下重要的信息:”小玲高興的時(shí)候經(jīng)常去買一大堆新衣服”, “那天小玲一個(gè)人去超市買了一堆吃的,一定是有什么心事了(憂慮)”, “你千萬不要惹小玲生氣阿,不然她會(huì)刷爆你的信用卡的!”, “小玲好幾次傷心難過的時(shí)候,一整天都宅在家里看雜志.”. 知道了這些信息,小明擴(kuò)展了他原先一直采用的馬爾可夫模型, 為每種隱藏的狀態(tài)(心情)賦予了新的可觀測(cè)狀態(tài)(Observables),這些可觀測(cè)狀態(tài)為:

1. 大部分(>50%)花費(fèi)是Fashion商場(chǎng)(O1)

2. 大部分(>50%)花費(fèi)在超市(O2)

3. Oh my God! 一天刷了5000元以上!!! (O3)

4. Oh yeah! 這一天她都沒花錢(O4)

為圖簡(jiǎn)便,我們假設(shè)小玲和小明的ex小麗,有著同樣的實(shí)際心情轉(zhuǎn)換概率(圖1).

小明通過歸類統(tǒng)計(jì)小玲過往的信用卡帳單(天啊,怎么這么多!),發(fā)現(xiàn)了如表2所示的每天心情與每天信用卡消費(fèi)之間的關(guān)系:

　　Table 2: 小玲的每天情緒狀態(tài)與當(dāng)天信用卡花費(fèi)的關(guān)系概率表

我要加一句的是, 由于概率的歸一性(各種可能性之和為1), 我們?yōu)榱瞬唤档捅疚牡膴蕵犯阈π? 規(guī)定如果某天小玲大部分的花費(fèi)是Fashion或者是在超市,那么她的花費(fèi)不可能超過5000, 這樣我們才有各行的 O1+O2+O3+O4 =1.

也就是說,當(dāng)小玲高興的時(shí)候, 小明發(fā)現(xiàn)80%的情況下那些天小玲基本都買性感小衣衣了(:Q), 也有那么10%的情況下大部分買吃的了, 令小明郁悶的是,居然小玲高興了,還有那么5%的情況,刷了他5000+ ;最后剩下5%的情況小玲可能因?yàn)樘吲d而顧不上消費(fèi)了(小明暗笑:”對(duì)對(duì),就是那次,她心情特好, we BEEP all day, it was the best we ever had!” )

自此, 小玲心情的隱式馬爾可夫模型就出來了(圖2).

　　Figure2: 小玲的隱式馬爾可夫模型

有了這個(gè)模型,我們就可以回答這個(gè)問題:

“如果我知道了小玲的信用卡花費(fèi)規(guī)律,我能否找出她最有可能的心情變化序列是什么?”

具體一點(diǎn)吧, 某次小玲到外地出差了一個(gè)星期, 小明每天打電話給她問她今天開心嘛? 小玲都說 “開心”…但實(shí)際呢?

小明自言自語說, 哼你不告訴我, 我就只好算算了! 小明Login到了小玲信用卡網(wǎng)站,打開statement,統(tǒng)計(jì)了一下,發(fā)現(xiàn)小玲這一個(gè)星期的消費(fèi)規(guī)律是:”O2 O1 O4 O2 O3 O1 O4″ (對(duì)應(yīng)著消費(fèi)序列 穿的, 吃的, 沒刷, 吃的, 刷爆, 穿的, 沒刷 )

有了這個(gè)消費(fèi)序列和圖2的模型, 有辦法找出小玲這7天最有可能的心情序列是什么嗎?

信不信由你, Viterbi search algorithm (維特比搜索算法)就是用來計(jì)算出HMM模型中給定觀測(cè)序列O(消費(fèi)規(guī)律), 對(duì)應(yīng)的最有可能的隱藏狀態(tài)序列(心情變化). 關(guān)于Viterbi的原理和實(shí)現(xiàn)已經(jīng)超出本文的講解范圍了,有興趣的同學(xué)可以去Wiki或者動(dòng)手Google一下. 簡(jiǎn)單來說Viterbi屬于動(dòng)態(tài)規(guī)劃 (Dynamic programming) 算法的一種,用來比較高效地計(jì)算出一個(gè)轉(zhuǎn)移矩陣及其觀測(cè)矩陣(分別對(duì)應(yīng)我們的Table1 和 Table2)制約下的最大可能的隱藏狀態(tài)轉(zhuǎn)移序列 -如果我們事先知道觀測(cè)序列的話.

根據(jù)以上的轉(zhuǎn)移矩陣(table 1})和觀測(cè)矩陣(table 2), 建立起HMM模型并采用Viterbi算法(HMM還需要添加一個(gè)狀態(tài)起始概率來表示每種狀態(tài)作為起始狀態(tài)的可能性,由于小明沒有辦法知>道這個(gè)數(shù)字,因此只能作最簡(jiǎn)單的假設(shè) –假設(shè)他們都是均勻分布的(uniformly distributed),所以每種狀態(tài)的起始>概率均為1/4).

可以知道,對(duì)應(yīng)以上觀察序列,小玲那七天最為可能的情緒序列為:

憂慮 悲傷 悲傷 憂慮 氣憤 高興 悲傷

概率為 p=1.410^-5

看來小玲這次出差壓力不小啊!

嗚呼! 至此整個(gè)Hidden Markov Model就介紹完了.

當(dāng)然,中間仍然有很多細(xì)節(jié)我是直接忽略了. 而且在現(xiàn)實(shí)使用當(dāng)中,HMM模型中的規(guī)模要大得多,無論是隱藏的狀態(tài)數(shù)目,還是可觀測(cè)的狀態(tài)數(shù)目,都超過千計(jì). HMM 及其相關(guān)算法被大量廣泛使用在各行各業(yè).在計(jì)算機(jī)信息學(xué)中, 大量語音識(shí)別, 中文分詞,中文拼音漢字轉(zhuǎn)換系統(tǒng)采用的都是隱式馬爾可夫模型.