男生和女生分別是來自不同星球的科學事實已經眾所周知的了.男生們總是認為,女生們都是迷一樣的生物,他們的情感狀態浮動似乎是以秒單位在變化的,難以理解,更勿論預測了! 而女生們覺得男生都是沒有感覺動物,完全不能理解什么叫感受-盡管已經告訴他們N次了!這種男女之間的根本差別,導致了他們之間的感情關系是受一種超級無敵復雜的系統所支配的.

不過,我們可以用一個叫隱式馬爾可夫(Hidden Markov Model)的數學模型來分析這個系統.

決定性系統

首先我們來看看一種最簡單的預測系統 –決定性系統.

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

另外一個常見的決定系統,就是交通燈的輪換: 紅燈過后就應該是綠燈. 綠燈過后就應該是黃燈,然后又回到紅燈.

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

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

對于大部分男生來說,精確地預測女朋友的下一種的情感狀態基本上屬于扯淡.

一個mm現在可能心情很好,可是下一秒卻進入抓狂;她或許某個時刻處于悲傷,下個時刻卻變得異常興奮.在每個女生的情感狀態里面,都有一種基于概率卻又難以預測的本質,這種無序的本質直接導致無數男生直接蹲地畫圈圈……

盡管看上去女生的情感狀態似乎毫無預測性可言,經過一段長時間的觀察,卻能發現這種現象是有規律的! 于是小明,作為一名計算機科學家, 決定要系統地去分析他女朋友的情感不確定性, 挖掘出里面的規律!

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

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

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

為了便于教學,我們假設小明只關心小麗的四種感情狀態: 高興 悲傷 氣憤 還有 憂慮

　　Table 1: 小麗的情緒狀態變化表

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

同理,每一列代表了由各種情緒轉變為該列所代表的情緒的概率,因此每列的概率總和也應該為1.

我們可以畫一個狀態圖(圖1)來表示表格1, 每個圓圈代表著一種心情狀態, 每兩種心情變化由一個有向弧,從當前的心情狀態指向下一個心情狀態表示,每個弧上均帶有一個狀態轉換的概率.

　　Figure 1: 小麗的情緒狀態變化圖

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

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

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

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

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

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

話說回來我們的主人公小明, 自從被小麗發現他這種近乎變態的科學分析行為后,變得非常善于隱藏自己的心情,導致某天小明錯誤估計了小麗的心情!在誤以為那天小麗會心情好的情況下,小明告訴小麗自己不小心摔壞了她心愛的iPod…,小明沒想到其實那天小麗正因為前一天錯過了商場名牌打折扣的活動而異常氣憤… 一場血雨腥風過后,兩個人最終分手了.

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

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

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

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

1. 大部分(>50%)花費是Fashion商場(O1)

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

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

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

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

小明通過歸類統計小玲過往的信用卡帳單(天啊,怎么這么多!),發現了如表2所示的每天心情與每天信用卡消費之間的關系:

　　Table 2: 小玲的每天情緒狀態與當天信用卡花費的關系概率表

我要加一句的是, 由于概率的歸一性(各種可能性之和為1), 我們為了不降低本文的娛樂搞笑性, 規定如果某天小玲大部分的花費是Fashion或者是在超市,那么她的花費不可能超過5000, 這樣我們才有各行的 O1+O2+O3+O4 =1.

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

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

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

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

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

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

小明自言自語說, 哼你不告訴我, 我就只好算算了! 小明Login到了小玲信用卡網站,打開statement,統計了一下,發現小玲這一個星期的消費規律是:”O2 O1 O4 O2 O3 O1 O4″ (對應著消費序列 穿的, 吃的, 沒刷, 吃的, 刷爆, 穿的, 沒刷 )

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

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

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

可以知道,對應以上觀察序列,小玲那七天最為可能的情緒序列為:

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

概率為 p=1.410^-5

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

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

當然,中間仍然有很多細節我是直接忽略了. 而且在現實使用當中,HMM模型中的規模要大得多,無論是隱藏的狀態數目,還是可觀測的狀態數目,都超過千計. HMM 及其相關算法被大量廣泛使用在各行各業.在計算機信息學中, 大量語音識別, 中文分詞,中文拼音漢字轉換系統采用的都是隱式馬爾可夫模型.