1

美國61號公路是連接法式風情的新奧爾良罕伯，和重重積雪的明尼蘇達的一條南北通道霹期，與加州1號公路敢课，阿甘跑過的66號公路并稱為三大公路寡喝，它對于美國公路文化糙俗、公路精神的意義不言而喻。

61號公路

馬爾可夫鏈在隨機過程的重要性也同樣如此预鬓。統(tǒng)計學家 Peter Whittle 曾說過：

"Any stochastic process can be formulated as a Markov process by an appropriate choice of variables."

隨著人工智能的浪潮奔涌巧骚，作為技術(shù)基石的馬爾可夫鏈也引起了廣泛的重視，那么這個看起來無所不能的隨機過程模型究竟神奇在哪里呢？

2

大道至簡网缝，偉大的作品往往起源于樸素的思想巨税，馬爾可夫鏈的思想就非常的簡單，一言以蔽之:

遺忘過去粉臊，把握現(xiàn)在草添，影響將來

讓我們用（不嚴格的）數(shù)學語言展開：
假設(shè) Xn[n>=0] 是隨機過程，我們稱 Xn[n>=0] 為馬爾可夫鏈當 Xn[n>=0] 滿足下列條件：

• P (Xn = x|X0, . . . , Xn?1) = P (Xn = x|Xn?1) ?n?x.

也就是說扼仲，未來的任一狀態(tài)只和當前狀態(tài)相關(guān)远寸，和其他更早的狀態(tài)無關(guān)。舉個例子：

馬爾可夫男朋友

當然數(shù)學上馬爾可夫性質(zhì)需要滿足一些更為嚴格的條件屠凶，如

• 每個狀態(tài)的保持時間 (holding time) 滿足指數(shù)簇分布

• 狀態(tài)轉(zhuǎn)換必須是平滑的驰后，不能有跳躍 (jump)

在實際應用中一般也很難嚴格地滿足馬爾可夫約束，但是道高一丈矗愧，對于這些隨機過程也可以通過一些統(tǒng)計技術(shù)用馬爾可夫鏈來近似灶芝。

好的，當馬爾可夫性質(zhì)具備之后唉韭，用處在哪呢夜涕？這就是馬爾可夫鏈的基本定理的內(nèi)容：

一個不可約的 (irreducible)、可遍歷 (ergodic) 的馬爾可夫鏈有唯一的穩(wěn)態(tài)分布属愤，并且等于它的極限分布女器。

這就厲害了。不管初始時怎樣的狀態(tài)住诸，最終都會到一個穩(wěn)定分布驾胆，簡而言之如下圖所示：

天注定

3

講了這些馬爾可夫鏈的性質(zhì)，它到底有哪些實際的應用呢贱呐？
馬爾可夫自己就舉了一個文藝的例子丧诺。
在紀念伯努利200周年誕辰的出版書上，他在自己書后附了一個例子吼句，將馬爾可夫鏈用在普希金的長詩《葉甫蓋尼·奧涅金》锅必，并附上了一些有趣的發(fā)現(xiàn)：

葉甫蓋尼·奧涅金

• 元音的轉(zhuǎn)移概率有一定規(guī)律
• 元音的穩(wěn)態(tài)概率約為0.4

這個開創(chuàng)性的工作啟發(fā)了很多其他領(lǐng)域的學者，哲學家和歷史學家 Nikolai
A. Morozov 稱贊馬爾可夫的方法是

*“a new weapon for the analysis of ancient scripts” *

信息論的奠基人香農(nóng)進一步擴展了馬爾可夫鏈在語言上的應用惕艳，并且可能是歷史上最早開始使用 trigrams 的人搞隐，同時，香農(nóng)也引進馬爾可夫鏈到通信系統(tǒng)远搪。

另外一個不那么久遠的例子就是谷歌的搜索 PageRank劣纲，盡管如今谷歌搜索排序的模型已經(jīng)極為復雜

"Today we use more than 200 signals, including PageRank, to order websites."

但在當時 PageRank 對搜索結(jié)果的影響非常大。在1997-1998年前后谁鳍，所有互聯(lián)網(wǎng)上能找到的搜索引擎癞季，每十條結(jié)果只有兩三條是相關(guān)的劫瞳、有用的。而尚在斯坦福大學實驗室襁褓之中的 Google 已經(jīng)能做到七八條符合绷柒， 這個差別志于，差不多就是 iPhone 和 Nokia 的差別，也在某種程度上表明搜索時代的到來废睦。這使得 Google 能迅速打敗以前所有搜索引擎伺绽，奠定了其在搜索引擎的霸主地位，從這點來說 PageRank 的意義深遠嗜湃。

4

在馬爾可夫鏈的基礎(chǔ)上奈应，衍生了許多統(tǒng)計技術(shù)和模型。隱馬爾可夫模型 (Hidden Markov Models, HMMs) 就是其中非常重要的一個分支购披。

顧名思義杖挣，HMMs 就是在馬爾夫鏈的基礎(chǔ)上加了一層隱層，實際的狀態(tài)是不可見的刚陡，觀察的狀態(tài)結(jié)果是由實際狀態(tài)生成的惩妇。

隱馬爾可夫模型

HMMs 在語言識別上大獲成功，實際上筐乳，在端到端的深度學習技術(shù)成熟之前屿附，HMMs 在語言識別、機器翻譯等領(lǐng)域一直是首選的基準模型哥童。當然，華爾街上各類對沖基金也早已嘗試把相關(guān)技術(shù)應用到金融投資領(lǐng)域褒翰。

但 HMMs 不是我們這次的主角贮懈，而是馬爾可夫鏈的另一衍生技術(shù)馬爾可夫決策過程 (Markov Decision Processes, MDPs)。

MDPs 在馬爾可夫鏈的基礎(chǔ)上增加了動作 (action) 的概念优训，每個狀態(tài)通過某個動作來轉(zhuǎn)移到其他的狀態(tài)朵你，并且對于每個狀態(tài)轉(zhuǎn)移，還有一個回報函數(shù) (rewarding function)揣非。

更數(shù)學化地抡医，一個 MDP 由一個四元組構(gòu)成M = (S, A, Psa, ??)：

• S: 表示狀態(tài)集 (states)，有 s∈S早敬，si 表示第i步的狀態(tài)忌傻。
• A: 表示一組動作 (actions)，有 a∈A搞监，ai 表示第i步的動作水孩。
• ??sa: 表示狀態(tài)轉(zhuǎn)移概率。??s?? 表示的是在當前 s ∈ S 狀態(tài)下琐驴，經(jīng)過 a ∈ A 作用后俘种，會轉(zhuǎn)移到的其他狀態(tài)的概率分布情況秤标。比如，在狀態(tài) s 下執(zhí)行動作 a宙刘，轉(zhuǎn)移到s' 的概率可以表示為 p(s'|s,a)苍姜。
• R: S×A?? ，R是回報函數(shù) (reward function)悬包。有些回報函數(shù)狀態(tài) S 的函數(shù)衙猪，可以簡化為 R: S??。如果一組 (s,a) 轉(zhuǎn)移到了下個狀態(tài) s'玉罐，那么回報函數(shù)可記為r(s'|s, a)屈嗤。如果 (s,a) 對應的下個狀態(tài) s'是唯一的，那么回報函數(shù)也可以記為 r(s,a)吊输。

馬爾可夫決策過程

一個策略 (policy) 的是指的 MDPs 的一系列動作饶号，這些動作能夠使得最終（某種形式）的回報函數(shù)能夠滿足我們的要求。由于 MDP 問題的目標通常優(yōu)化某個長期的結(jié)果季蚂，具有延遲回報的特點茫船，那么（立即）回報函數(shù)沒法滿足要求，因此需要定義值函數(shù) （value function) 來定義策略的長期效果扭屁。

常見的值函數(shù)如下所示：

其中 γ∈[0,1] 稱為折合因子算谈，表明了未來的回報相對于當前回報的重要程度。

那么一個MDP的最優(yōu)策略可以由下式表示：

給定策略 π 和初始狀態(tài) s料滥，則動作 a=π(s)然眼，下個時刻將以概率 p(s'|s,a) 轉(zhuǎn)向下個狀態(tài) s'，那么值函數(shù)可以拆開重寫為：

MDPs 的求解思路也類似于 HMMs, 本質(zhì)上動態(tài)規(guī)劃的思想葵腹，通過迭代策略（策略估計＋策略優(yōu)化）來得到最優(yōu)策略高每，同時通過值迭代來近似策略迭代的計算。

策略迭代

5

MDPs 一大熱門應用就是現(xiàn)在大火的強化學習 (Reinforcement Learning)践宴，簡單來說鲸匿，強化學習要解決的就是馬爾可夫決策過程 (MDP)，即執(zhí)行不同的行為到達不同的狀態(tài)阻肩，它由組成带欢，從而可以圍繞著求解環(huán)境 (environment)、策略烤惊、值函數(shù)三者展開的乔煞，有時已知環(huán)境有時未知環(huán)境，有時要顯式的算出策略柒室，有時要求的又是動作值函數(shù) (action-value function)瘤缩。與監(jiān)督學習不同之處在于 MDP 當前的某個狀態(tài)下對最終的結(jié)果的影響是不確定的，往往是要結(jié)合過去的一段行為和將來的一段行為才能確定當前的這個狀態(tài)的影響伦泥，而監(jiān)督學習在求解過程中會認為當前這個狀態(tài)對最終結(jié)果有確定的影響剥啤，所以監(jiān)督學習無法直接解決 MDP 問題锦溪。

這也是為什么有人認為，強化學習（和無監(jiān)督學習）才是通向強人工智能的正軌府怯，因為這可能符合人類自身學習的一般規(guī)律刻诊，當前行為對長期結(jié)果的影響往往不是那么確定的。

Alpha Go 是一個強化學習（與深度學習）結(jié)合取得較大進展的例子牺丙，它主要由以下幾部分構(gòu)成：

• 走棋策略神經(jīng)網(wǎng)絡（Policy Network）则涯，給定當前局面，預測/采樣下一步的走棋冲簿。
• 快速走棋策略（Fast rollout）粟判，適當犧牲走棋質(zhì)量的條件下，快速走棋峦剔。
• 值函數(shù)神經(jīng)網(wǎng)絡（Value Network）档礁，給定當前局面，估計是白勝還是黑勝吝沫。
• 蒙特卡羅樹搜索（Monte Carlo Tree Search呻澜，MCTS)，一種啟發(fā)式搜索算法惨险，連接上述三個部分羹幸，形成一個完整的系統(tǒng)。

Alpha Go

這里面的走棋過程就是強化學習過程辫愉，并且結(jié)合深度學習來進行策略和值函數(shù)的計算栅受、估計。Alpha Go 相比它的圍棋算法前輩能取得巨大成功恭朗， 除了強化學習結(jié)合了深度學習窘疮，利用自我博弈產(chǎn)生海量樣本以外，更大的原因其實是來自于研究團隊長期的積累冀墨，在系統(tǒng)優(yōu)化細節(jié)上傾注了大量的精力。

這也說明了目前盡管強化學習引起了廣泛的關(guān)注涛贯，發(fā)展迅猛诽嘉，但還是舊瓶裝新酒（強化學習早在上個世界80年代就已出現(xiàn)），與特定領(lǐng)域弟翘、環(huán)境息息相關(guān)虫腋，離真正的強人工智能還有相當?shù)木嚯x。

6

溫故知新稀余，馬爾可夫鏈雖然是100年前的技術(shù)悦冀，但迄今仍然深刻地影響著前沿研究的發(fā)展，在人工智能睛琳，尤其是強化學習中仍然是最基礎(chǔ)的根基盒蟆。正如 MDP 的思想所言踏烙，雖然我們當下的工作無法確定地衡量對將來的影響，但正是靠著不斷試錯 (trial-and-error)历等，不斷迭代讨惩，在往外探索和向內(nèi)深挖 (exploration-exploitation) 中不斷平衡，我們才有可能接近最終的最優(yōu)解寒屯。

在2012年的 MIT 科技評論上曾經(jīng)批判現(xiàn)在科技發(fā)展的方向看起來不是在解決宏觀大問題荐捻，而是帶來了 Facebook、Google 等這樣的科技公司寡夹。

但現(xiàn)在处面，我們都看到了 Facebook、Google 等公司在人工智能上的發(fā)力與突破菩掏，組成了人工智能聯(lián)盟魂角，加速推進人工智能的進一步發(fā)展，同時也促進了人工智能在各個領(lǐng)域更深一步的應用患蹂，包括自動駕駛或颊、航空航天都受益于人工智能的發(fā)展的紅利。

從這個角度看传于，科技的發(fā)展不也是一個 MDP 嗎囱挑，當下的每一點進展對將來的影響雖然是不確定的，但就是依靠當下的每一點積累沼溜，進而才有可能在長期的發(fā)展中形成突破平挑。

順便, 短短4年后，一個叫 Elon Musk 的人說：

We promised Mars Colonies and we're gonna make it real.