LiLei和HanMeiMei的隐式马尔可夫爱情
為什么80%的碼農都做不了架構師？>>> ??
男生和女生分別是來自不同星球的科學事實已經眾所周知的了.男生們總是認為,女生們都是迷一 樣的生物,他們的情感狀態浮動似乎是以秒單位在變化的,難以理解,更勿論預測了! 而女生們覺得男生都是沒有感覺動物,完全不能理解什么叫感受-盡管已經告訴他們N次了! 這種男女之間的根本差別,導致了他們之間的感情關系是受一種超級無敵復雜的系統所支配的.
不過,我們可以用一個叫隱式馬爾可夫(Hidden Markov Model)的數學模型來分析這個系統.
決定性系統
首先我們來看看一種最簡單的預測系統 - 決定性系統. 在這個系統中,如果我們知道我們目前所在的狀態,那么我們也就能夠毫無疑問地預測出下一個狀態是什么. 比如一年四季的輪替就是一個決定性系統: 每個季節的交替是完全可以預測的,如果現在是春天,那么下一個季節就一定會是夏天, 冬天的前一個狀態就一定是秋天等等.另外值得一提的是,冬天過后,下一個季節就又會回到春天,以此循環...
另外一個常見的決定系統,就是交通燈的輪換: 紅燈過后就應該是綠燈. 綠燈過后就應該是黃燈,然后又回到紅燈.
這種系統非常常見,人的一生大致也能看作是這種系統. 有嬰兒,少年,成年,老年, 然后死亡等幾種狀態. 不過不同的是,人的一生又不是完全遵循這種狀態輪換的, 每個人都有那么丁點的可能性會跳過其中一個或者多個狀態,直接到達死亡的狀態...(更勿論Benjamin Buttons的情況了,呵呵).
講到這里,聰明的男生或許已經能想到,我們的世界里最為精妙,最雷人的非決定性系統就是 --
你女朋友的情感狀態!對于大部分男生來說,精確地預測女朋友的下一種的情感狀態基本上屬于扯淡. 一個mm現在可能心情很好,可是下一秒卻進入抓狂; 她或許某個時刻處于悲傷,下個時刻卻變得異常興奮.在每個女生的情感狀態里面,都有一種基于概率卻又難以預測的本質, 這種無序的本質直接導致無數男生直接蹲地畫圈圈......
盡管看上去女生的情感狀態似乎毫無預測性可言,經過一段長時間的觀察,卻能發現這種現象是有 規律的! 于是LiLei,作為一名計算機科學家, 決定要系統地去分析他女朋友的情感不確定性, 挖掘出里面的規律!
于是乎,LiLei仔細地記錄了半年來他女朋友HanMeiMei每天的喜怒哀樂變化狀態, 并作了一張圖表(Table1)來表示HanMeiMei的歷史情感變化.
LiLei想知道, 有了這些數據,他能否從中得出知道, 如果HanMeiMei某天的情感狀態是高興 , 那么第二天她更多的是保持好心情呢,還是更多地變得悲傷了. 如此等等...
數據勝于雄辯, LiLei從這半年的數據里面發現,當HanMeiMei高興的時候, 3/4的情況下第二天她仍然保持著好心情,只有1/4的情況HanMeiMei第二天心情會改變,比如變得氣憤,悲傷等等(LiLei真TM走運!). LiLei繼續分析其他各種情感狀態變化情況,比如從高興到悲傷, 悲傷到氣憤, 高興到氣憤等所有的可能組合. 很快LiLei就得到所有的組合變化數據,從中得知對于任意HanMeiMei的某天情感狀態下,下一個最有可能的情感狀態.
為了便于教學,我們假設LiLei只關心HanMeiMei的四種感情狀態: 高興 悲傷 氣憤 還有 憂慮
| | 高興 | 悲傷 | 氣憤 | 憂慮 |
| 高興 | 0.75 | 0.1 | 0.1 | 0.05 |
| 悲傷 | 0.05 | 0.5 | 0.25 | 0.2 |
| 氣憤 | 0.15 | 0.2 | 0.4 | 0.25 |
| 憂慮 | 0.05 | 0.2 | 0.25 | 0.5 |
Table 1: HanMeiMei的情緒狀態變化表
在這個表格中, 每個數字代表了HanMeiMei情緒從某列轉變到某行的概率. 比方說, 如果HanMeiMei某天的情緒是高興, 那么她將有0.1的概率下一天她會變得 悲傷 或者是 氣 憤, 有0.05的可能性轉變為 憂慮. 每一行代表了從某種情緒轉變到各種情緒的概率,因此每行的概率之和為 1. 同理,每一列代表了由各種情緒轉變為該列所代表的情緒的概率,因此每列的概率總和也應該為1.
我們可以畫一個狀態圖(圖1)來表示表格1, 每個圓圈代表著一種心情狀態, 每兩種心情變化由一個有向弧,從當前的心情狀態指向下一個心情狀態表示,每個弧上均帶有一個狀態轉換的概率.
Figure 1: HanMeiMei的情緒狀態變化圖
有了這個圖表,LiLei就可以非常直觀地看得到HanMeiMei最有可能的下個心情會是如何. 她會很有可能變得悲傷嗎?(準備好鮮花巧克力),還是更有可能是氣憤?(趕緊閃開!) 每天LiLei只需要看看哪個弧指向的心情概率最大就可以了.
這個過程,同學們,就是有名的 "馬爾可夫過程" (Markov process)
不過需要注意的是, 馬爾可夫過程有一些假設的前提. 在我們的例子里面, 預測下一天HanMeiMei的心情, 我們只依賴當天HanMeiMei的心情, 而沒有去考慮更先前她的心情. 很明顯這種假設下的模型是遠不夠精確的. 很多時候,隨著日子一天一天的過去,女生一般會變得越來越體諒. 經常女生生氣了幾天后,氣就會慢慢消了. 比方說如果HanMeiMei已經生氣了3天了,那么她第二天變得高興起來的可能性,在多數情況下, 要比她只生氣了一天而第二天變得高興的可能性要高. 馬爾可夫過程并沒有考慮這個, 用行話講, 就是馬爾可夫模型忽略遠距離歷史效應(long range dependency).
我很佩服各位能堅持讀到這里, 不過,還沒完呢, 我仍然沒有說,隱式馬爾可夫模型 (Hidden Markov Model)是什么呢! 諸位如果已經有點頭昏腦漲,請就此打住,以免大腦過熱死機!
隱式馬爾可夫模型 - Hidden Markov Model, or HMM for short.
有些時候,我們無法直接觀測一個事物的狀態. 比方說, 有些女生是很能隱瞞自己的情感而不流露出來的! 他們可能天天面帶微笑但不代表他們就天天高興. 因此我們必須要有竅門, 去依賴某些我們能夠直接觀察到的東西.
話說回來我們的主人公LiLei, 自從被HanMeiMei發現他這種近乎變態的科學分析行為后,變得非常善于隱藏自己的心情,導致某天LiLei錯誤估計了HanMeiMei的心情! 在誤以為那天HanMeiMei會心情好的情況下,LiLei告訴HanMeiMei自己不小心摔壞了她心愛的iPod..., LiLei沒想到其實那天HanMeiMei正因為前一天錯過了商場名牌打折扣的活動而異常氣憤... 一場血雨腥風過后,兩個人最終分手了.
不過很快LiLei憑著自身的英俊高大瀟灑,很快又交上了另外一個女朋友 - Lucy. 鑒于LiLei意識到,女生表面的情感流露非常不可靠, LiLei決定要另尋他徑, 繼續預測女朋友的心情! (作為一個科學家,LiLei的確有著不怕碰壁的精神!)
LiLei每個月都幫Lucy付信用卡的費用(真不明白，有這樣的男朋友，Lucy有什么理由不高興啊!), 因此LiLei每天都可以通過Online banking 知道Lucy每天都買了什么東西. LiLei突然靈機一動: "沒準我能通過觀測她的購物規律,推導預測出Lucy的心情!". 聽起來有點匪夷所思,不過這個過程,的的確確是可以使用叫作隱式馬爾可夫的數學模型來表示并 分析的.
由于我們需要預測的變量 - 心情狀態 是無法直接觀測的,是隱藏 (Hidden) 起來的.因此這種模型才叫隱式馬爾可夫模型.
在一次和Lucy的好朋友們一起吃飯的時候, LiLei得知了以下重要的信息:"Lucy高興的時候經常 去買一大堆新衣服", "那天Lucy一個人去超市買了一堆吃的,一定是有什么心事了(憂慮)", "你千萬不要惹Lucy生氣阿,不然她會刷爆你的信用卡的!", "Lucy好幾次傷心難過的時候,一整天都宅在家里看雜志.". 知道了這些信息,LiLei擴展了他原先一直采用的馬爾可夫模型, 為每種隱藏的狀態(心情)賦予了新的可觀測狀態(Observables),這些可觀測狀態為:
為圖簡便,我們假設Lucy和LiLei的exHanMeiMei,有著同樣的實際心情轉換概率(圖1).
LiLei通過歸類統計Lucy過往的信用卡帳單(天啊,怎么這么多!),發現了如表2所示的每天心情與每天信用卡消費之間的關系:
| | 大部分花費為 Fashion (O1) | 大部分花費在超市 (O2) | TMD花了我至少 5000! (O3) | 一分錢沒花 (O4) |
| 高 興 | 0.75 | 0.1 | 0.05 | 0.05 |
| 悲傷 | 0.1 | 0.1 | 0.05 | 0.75 |
| 氣 憤 | 0.05 | 0.15 | 0.65 | 0.15 |
| 憂 慮 | 0.1 | 0.65 | 0.25 | 0.05 |
Table 2: Lucy的每天情緒狀態與當天信用卡花費的關系概率表
我要加一句的是, 由于概率的歸一性(各種可能性之和為1), 我們為了不降低本文的娛樂搞笑性,?規定如果某天Lucy大部分的花費是Fashion或者是在超市,那么她的花費不可能超過5000, 這樣我們才有各行的 O1+O2+O3+O4 =1.
也就是說,當Lucy高興的時候, LiLei發現75%的情況下那些天Lucy基本都買性感小衣衣了(:Q), 也有那么10%的情況下大部分買吃的了, 另LiLei郁悶的是,居然Lucy高興了,還有那么5%的情況,刷了他5000+ ;最后剩下5%的情況Lucy可能因為太高興而顧不上消費了(LiLei暗笑: "對對,就是那次,她心情特好, we *BEEP* all day, it was the best we ever had!" )
自此, Lucy心情的隱式馬爾可夫模型就出來了(圖2).
Figure2: Lucy的隱式馬爾可夫模型
有了這個模型,我們就可以回答這個問題:
"如果我知道了Lucy的信用卡花費規律,我能否找出她最有可能的心情變化序列是什 么?"
具體一點吧, 某次Lucy到外地出差了一個星期, LiLei每天打電話給她問她今天開心嘛? Lucy都說 "開心"...但實際呢?
LiLei自言自語說, 哼你不告訴我, 我就只好算算了! LiLeiLogin到了Lucy信用卡網站,打開statement,統計了一下,發現Lucy
這一個星期的消費規律是:"O2 O1 O4 O2 O3 O1 O4" (對應著消費序列 穿的, 吃的, 沒刷, 吃的, 刷爆, 穿的, 沒刷 )
有了這個消費序列和圖2的模型, 有辦法找出Lucy這7天最有可能的心情序列是什么嗎?
信不信由你, Viterbi search algorithm (維特比搜索算法)就是用來計算出HMM模型中給定觀測序列O(消費規律), 對應的最有可能的隱藏狀態序列(心情變化). 關于Viterbi的原理和實現已經超出本文的講解范圍了,有興趣的同學可以去Wiki 或者動手Google一下. 簡單來說Viterbi屬于動態規劃 (Dynamic programming) 算法的一種, 用來比較高效地計算最優序列.
嗚呼! 至此整個Hidden Markov Model就介紹完了. 當然,中間仍然有很多細節我是直接忽略了. 而且在現實使用當中, HMM模型中的規模要大得多,無論是隱藏的狀態數目,還是可觀測的狀態數目,都超過千計. HMM 及其相關算法被大量廣泛使用在各行各業. 在計算機信息學中, 大量語音識別, 中文分詞,中文拼音漢字轉換系統采用的都是隱式馬爾可夫模型.?
最后Newway忠告大家, 準確預測女孩的心情起伏變化,是比預測天氣,股票指數的升跌要來得更復雜的, 任何試圖采用本文的方法來企圖預測 女朋友/老婆/情人 的心情而導致的任何血腥場面,都是咎由自取的.
轉載于:https://my.oschina.net/nord/blog/102235
總結
以上是生活随笔為你收集整理的LiLei和HanMeiMei的隐式马尔可夫爱情的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 使用DES算法实现加密解密
- 下一篇： 保持本心