马尔可夫链

马尔可夫链因俄国数学家Andrey Andreyevich Markov得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。

【描述来源：维基百科 URL：https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE】

下面我们从数学角度进行说明。

一阶马尔可夫链被定义为一系列随机变量z^(1)，...，z^(M)，使得对于m∈{1，...，M-1}， 以下条件满足：

这可以表示为一个链形式的有向图，在之后的例子中我们会进行说明。

然后，我们可以通过给出初始变量的概率分布p(z^(0))和其后变量取转移概率（transition probability）——状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率——的形式的条件概率T_m(z^(m), z^(m + 1)≡p(z^(m + 1)| z^(m))来指定马尔可夫链 。 如果所有m的转移概率都相同，那么马尔可夫链就称为同质链。

一个特定变量的边际概率可以用形式链中前一个变量的边际概率表示：

如果链中的概率分布被限制为相等的，则称分布相对于马尔可夫链是不变的或静止的（invariant or stationary）。 因此，对于一个转移概率为T(z', z)的同质马氏链（homogeneous Markov chain），分布p*（z）是不变的：

值得注意的是，对于任何一个给定的马尔可夫链，都可能有多个不变的分布。 例如，如果转换概率是由同质转换（identity transformation）给定的，那么任何分布都是不变的。对于给定的分布p*（z），确保所需分布满足不变性（invariant）的充分条件（但不是必要的）是选择转移概率来满足细致平衡条件（detailed balance）：

很容易看出，满足细致平衡条件（detailed balance）的转移概率将使分布具有不变性，因为：

满足细致平衡条件（detailed balance）的马尔科夫链被称作可反转的，即从高概率状态向低概率状态转移的概率等于从这个低概率状态向高概率状态转移的概率，这是一个非常重要的特性，特别是在MCMC抽样技术中。

【描述来源：Bishop C. M. (2006). Pattern Recognition and Machine Learning. Springer.】

举例来说，下图中显示了一个简单示例的状态图，使用有向图来描绘状态转换。

这些圆圈中的状态代表假设的股票市场是否在某个特定周内表现出牛市（ bull market），熊市（bear market）或停滞的（ stagnant market）市场走势。 根据这个数字，一个牛市周之后下一周还是牛市周的概率为90％，是熊市概率为7.5％，持平的概率为2.5%。 若我们标记状态空间{1 = bull，2 = bear，3 = stagnant}，则这个例子的转换矩阵是：

状态分布可以写成随机行向量x，其满足关系x^(n + 1)= x^(n)P。 因此，如果在时间n时系统处于状态x（n），则在三个时间段之后，在时间n + 3处的分布应为：

特别是，如果在时间n时系统处于状态2（熊），则在时间n + 3处的分布为：

通过使用转换矩阵，可以计算市场从持平到牛市所需的平均周数等。使用转换概率，稳态概率表明，在给定的周数中，62.5％的周将处于牛市中，31.25％的周将处于熊市中，6.25％的周将停滞，因为：

【图片及描述来源：维基百科 URL：https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE】

发展历史

1906年，Andrey Andreyevich Markov为了描述随机过程首次提出了马尔科夫链，并应用在俄语字符序列的计算中。在随后的半个世纪中，该概念深刻影响了数学，统计，计算机，物理学，生物学，语言学等各个领域，并引申发展出了马尔可夫毯，马尔可夫模型，马尔可夫随机场等多种重要概念。

大名鼎鼎的MCMC本质上是将马尔可夫链用于对蒙特卡洛方法的积分过程中，由梅特罗波利斯于1953年在洛斯阿拉莫斯国家实验室提出。那时美国洛斯阿拉莫斯是当时少数几个拥有大规模计算机的城市，梅特罗波利斯则利用这种计算优势，在蒙特卡洛方法的基础上引入马尔可夫链，用于模拟某种液体在气化之后的平衡状态。1984年Stuart和Donald Geman兄弟对吉布斯采样进行了描述，形成了我们今天所熟悉的版本，而吉布斯采样就是一种简单且广泛适用的马尔可夫链蒙特卡洛（MCMC）算法。

时间再倒回一点，1957年，RICHARD BELLMAN提出了马尔可夫决策过程，这是基于马尔可夫过程理论的随机动态系统的最优决策过程，而马尔可夫过程的原始模型就是马尔科夫链。1980年，《Markov random fields and their applications》出版，详细描述了马尔可夫随机场的理论和应用，马尔可夫随机场实际上是马尔可夫过程的一个多维版本。1988年，Judea Pearl在其著作Probabilistic reasoning in intelligent systems: networks of plausible inference中提出了马尔可夫毯的概念。1991年，Lovejoy 研究了部分可观测马尔可夫决策过程（POMDP）。1995年D. P. Bertsekas 和 J. N. Tsitsiklis讨论了一类用于不确定条件下的控制和顺序决策的动态规划方法。 这些方法具有处理长期以来由于状态空间较大或缺乏准确模型而难以处理的问题的潜力，他们将规划所基于的环境表述为马尔可夫决策过程，这即是目前深度学习领域流行的强化学习的雏形。

1966年起，Leonard E. Baum等学者在一系列研究中提出了隐马尔可夫模型（Hidden Markov Model，HMM），它用来描述一个含有隐含未知参数的马尔可夫过程。1975年，Baker 将 HMM 用于语音识别，从那以后，HMM成为了大多数现代自动语音识别系统的基础。20世纪80年代起，HMM 也开始用于分析生物序列（DNA）。

在经济金融领域，James D. Hamilton 1989年机应用了制转换模型，其中马尔科夫链用来对高GDP增长速度时期与低GDP增长速度时期（换言之，经济扩张与紧缩）的转换进行建模。S.Brin和L.Page提出的谷歌所使用的网页排序算法（PageRank）（1998年），也是由马尔可夫链定义的。如果N是已知的网页数量，一个页面i有k_i个链接到这个页面，那么它到链接页面的转换概率为\alpha/k_i+(1-\alpha)/N，到未链接页面的概率为(1-\alpha)/N， 参数\alpha的取值大约为0.85。

在深度学习领域，Yoshua Bengio 等研究者于2017年提出了 GibbsNet，旨在通过匹配模型期望的联合分布和数据驱动的联合分布直接定义和学习转换算子（transition operator），然后使用转换算子训练图模型，成功将马尔科夫链与神经网络结合起来。同年，Jiaming Song, Shengjia Zhao和Stefano Ermon研究了生成对抗的训练方法来对马尔可夫链（Markov chain）的转移算子（transition operator）进行学习，目的是将其静态分布（stationary distribution）和目标数据分布相匹配。他们提出了一种新型的训练流程，以避免从静态分布中直接采样，但是仍然有能力逐渐达到目标分布。此模型可以从随机噪声开始，是无似然性的，并且能够在单步运行期间生成多个不同的样本。初步试验结果显示，当它临近其静态时，马尔可夫链可以生成高质量样本，即使是对于传统生成对抗网络相关理念中的较小结构亦是如此。

主要事件

发展分析

瓶颈

马尔可夫链收敛到静态分布的速度可能很慢。另外，马尔科夫链的性质是当前状态只与前一步状态相关，这在某些领域的应用中是一个缺点，如在自然语言处理中序列标注问题不仅和单个词相关，而且与观察序列的长度、单词的上下文等都相关。当然，随后提出的一些其他基于马尔科夫链的模型对这些性质有进行改进，如最大熵隐马尔科夫模型（MEMM）可以整个观察序列。

未来发展方向

马尔可夫链作为机器学习领域最重要的概念之一，是几乎各领域算法的基础，目前的研究既可以像上文提到的那样，将已有的基于马尔科夫链的模型与其他模型结合，也可以通过神经网络等手段对转移算子进行学习。通用强化学习（general reinforcement learning）作为目前研究的一个目标，也反应了马尔科夫链的重要性。

Contributor：Yuanyuan LI