1
美国61号公路是连接法式风情的新奥尔良，和重重积雪的明尼苏达的一条南北通道，与加州1号公路，阿甘跑过的66号公路并称为三大公路，它对于美国公路文化、公路精神的意义不言而喻。
马尔可夫链在随机过程的重要性也同样如此。统计学家 Peter Whittle 曾说过：
"Any stochastic process can be formulated as a Markov process by an appropriate choice of variables."
随着人工智能的浪潮奔涌，作为技术基石的马尔可夫链也引起了广泛的重视，那么这个看起来无所不能的随机过程模型究竟神奇在哪里呢？
2
大道至简，伟大的作品往往起源于朴素的思想，马尔可夫链的思想就非常的简单，一言以蔽之:
遗忘过去，把握现在，影响将来
让我们用（不严格的）数学语言展开：
假设 Xn[n>=0] 是随机过程，我们称 Xn[n>=0] 为马尔可夫链当 Xn[n>=0] 满足下列条件：
- P (Xn = x|X0, . . . , Xn−1) = P (Xn = x|Xn−1) ∀n∀x.
也就是说，未来的任一状态只和当前状态相关，和其他更早的状态无关。举个例子：
当然数学上马尔可夫性质需要满足一些更为严格的条件，如
- 每个状态的保持时间 (holding time) 满足指数簇分布
- 状态转换必须是平滑的，不能有跳跃 (jump)
在实际应用中一般也很难严格地满足马尔可夫约束，但是道高一丈，对于这些随机过程也可以通过一些统计技术用马尔可夫链来近似。
好的，当马尔可夫性质具备之后，用处在哪呢？这就是马尔可夫链的基本定理的内容：
一个不可约的 (irreducible)、可遍历 (ergodic) 的马尔可夫链有唯一的稳态分布，并且等于它的极限分布。
这就厉害了。不管初始时怎样的状态，最终都会到一个稳定分布，简而言之如下图所示：
3
讲了这些马尔可夫链的性质，它到底有哪些实际的应用呢？
马尔可夫自己就举了一个文艺的例子。
在纪念伯努利200周年诞辰的出版书上，他在自己书后附了一个例子，将马尔可夫链用在普希金的长诗《叶甫盖尼·奥涅金》，并附上了一些有趣的发现：
- 元音的转移概率有一定规律
- 元音的稳态概率约为0.4
这个开创性的工作启发了很多其他领域的学者，哲学家和历史学家 Nikolai
A. Morozov 称赞马尔可夫的方法是
*“a new weapon for the analysis of ancient scripts” *
信息论的奠基人香农进一步扩展了马尔可夫链在语言上的应用，并且可能是历史上最早开始使用 trigrams 的人，同时，香农也引进马尔可夫链到通信系统。
另外一个不那么久远的例子就是谷歌的搜索 PageRank，尽管如今谷歌搜索排序的模型已经极为复杂
"Today we use more than 200 signals, including PageRank, to order websites."
但在当时 PageRank 对搜索结果的影响非常大。在1997-1998年前后，所有互联网上能找到的搜索引擎，每十条结果只有两三条是相关的、有用的。而尚在斯坦福大学实验室襁褓之中的 Google 已经能做到七八条符合， 这个差别，差不多就是 iPhone 和 Nokia 的差别，也在某种程度上表明搜索时代的到来。这使得 Google 能迅速打败以前所有搜索引擎，奠定了其在搜索引擎的霸主地位，从这点来说 PageRank 的意义深远。
4
在马尔可夫链的基础上，衍生了许多统计技术和模型。隐马尔可夫模型 (Hidden Markov Models, HMMs) 就是其中非常重要的一个分支。
顾名思义，HMMs 就是在马尔夫链的基础上加了一层隐层，实际的状态是不可见的，观察的状态结果是由实际状态生成的。
HMMs 在语言识别上大获成功，实际上，在端到端的深度学习技术成熟之前，HMMs 在语言识别、机器翻译等领域一直是首选的基准模型。当然，华尔街上各类对冲基金也早已尝试把相关技术应用到金融投资领域。
但 HMMs 不是我们这次的主角，而是马尔可夫链的另一衍生技术马尔可夫决策过程 (Markov Decision Processes, MDPs)。
MDPs 在马尔可夫链的基础上增加了动作 (action) 的概念，每个状态通过某个动作来转移到其他的状态，并且对于每个状态转移，还有一个回报函数 (rewarding function)。
更数学化地，一个 MDP 由一个四元组构成M = (S, A, Psa, 𝑅)：
- S: 表示状态集 (states)，有 s∈S，si 表示第i步的状态。
- A: 表示一组动作 (actions)，有 a∈A，ai 表示第i步的动作。
- 𝑃sa: 表示状态转移概率。𝑃s𝑎 表示的是在当前 s ∈ S 状态下，经过 a ∈ A 作用后，会转移到的其他状态的概率分布情况。比如，在状态 s 下执行动作 a，转移到s' 的概率可以表示为 p(s'|s,a)。
- R: S×A⟼ℝ ，R是回报函数 (reward function)。有些回报函数状态 S 的函数，可以简化为 R: S⟼ℝ。如果一组 (s,a) 转移到了下个状态 s'，那么回报函数可记为r(s'|s, a)。如果 (s,a) 对应的下个状态 s'是唯一的，那么回报函数也可以记为 r(s,a)。
一个策略 (policy) 的是指的 MDPs 的一系列动作，这些动作能够使得最终（某种形式）的回报函数能够满足我们的要求。由于 MDP 问题的目标通常优化某个长期的结果，具有延迟回报的特点，那么（立即）回报函数没法满足要求，因此需要定义值函数 （value function) 来定义策略的长期效果。
常见的值函数如下所示：
其中 γ∈[0,1] 称为折合因子，表明了未来的回报相对于当前回报的重要程度。
那么一个MDP的最优策略可以由下式表示：
给定策略 π 和初始状态 s，则动作 a=π(s)，下个时刻将以概率 p(s'|s,a) 转向下个状态 s'，那么值函数可以拆开重写为：
MDPs 的求解思路也类似于 HMMs, 本质上动态规划的思想，通过迭代策略（策略估计＋策略优化）来得到最优策略，同时通过值迭代来近似策略迭代的计算。
5
MDPs 一大热门应用就是现在大火的强化学习 (Reinforcement Learning)，简单来说，强化学习要解决的就是马尔可夫决策过程 (MDP)，即执行不同的行为到达不同的状态，它由组成，从而可以围绕着求解环境 (environment)、策略、值函数三者展开的，有时已知环境有时未知环境，有时要显式的算出策略，有时要求的又是动作值函数 (action-value function)。与监督学习不同之处在于 MDP 当前的某个状态下对最终的结果的影响是不确定的，往往是要结合过去的一段行为和将来的一段行为才能确定当前的这个状态的影响，而监督学习在求解过程中会认为当前这个状态对最终结果有确定的影响，所以监督学习无法直接解决 MDP 问题。
这也是为什么有人认为，强化学习（和无监督学习）才是通向强人工智能的正轨，因为这可能符合人类自身学习的一般规律，当前行为对长期结果的影响往往不是那么确定的。
Alpha Go 是一个强化学习（与深度学习）结合取得较大进展的例子，它主要由以下几部分构成：
- 走棋策略神经网络（Policy Network），给定当前局面，预测/采样下一步的走棋。
- 快速走棋策略（Fast rollout），适当牺牲走棋质量的条件下，快速走棋。
- 值函数神经网络（Value Network），给定当前局面，估计是白胜还是黑胜。
- 蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS)，一种启发式搜索算法，连接上述三个部分，形成一个完整的系统。
这里面的走棋过程就是强化学习过程，并且结合深度学习来进行策略和值函数的计算、估计。Alpha Go 相比它的围棋算法前辈能取得巨大成功， 除了强化学习结合了深度学习，利用自我博弈产生海量样本以外，更大的原因其实是来自于研究团队长期的积累，在系统优化细节上倾注了大量的精力。
这也说明了目前尽管强化学习引起了广泛的关注，发展迅猛，但还是旧瓶装新酒（强化学习早在上个世界80年代就已出现），与特定领域、环境息息相关，离真正的强人工智能还有相当的距离。
6
温故知新，马尔可夫链虽然是100年前的技术，但迄今仍然深刻地影响着前沿研究的发展，在人工智能，尤其是强化学习中仍然是最基础的根基。正如 MDP 的思想所言，虽然我们当下的工作无法确定地衡量对将来的影响，但正是靠着不断试错 (trial-and-error)，不断迭代，在往外探索和向内深挖 (exploration-exploitation) 中不断平衡，我们才有可能接近最终的最优解。
在2012年的 MIT 科技评论上曾经批判现在科技发展的方向看起来不是在解决宏观大问题，而是带来了 Facebook、Google 等这样的科技公司。
但现在，我们都看到了 Facebook、Google 等公司在人工智能上的发力与突破，组成了人工智能联盟，加速推进人工智能的进一步发展，同时也促进了人工智能在各个领域更深一步的应用，包括自动驾驶、航空航天都受益于人工智能的发展的红利。
从这个角度看，科技的发展不也是一个 MDP 吗，当下的每一点进展对将来的影响虽然是不确定的，但就是依靠当下的每一点积累，进而才有可能在长期的发展中形成突破。
顺便, 短短4年后，一个叫 Elon Musk 的人说：
We promised Mars Colonies and we're gonna make it real.
