马尔可夫性质、马尔可夫链和马尔可夫过程

前言 研究决策问题就一定听说过马尔可夫过程（Markov Process），这是一类非常重要的方法。现在非常热门的强化学习都是基于马尔可夫过程方法建立的。马尔可夫决策过程是研究随机序贯决策问题的理论基础，属于概率论和运筹学的交叉学科，同时，作为作为最优控制理论，也属于随机系统最优控制的范畴，具有广阔的应用范围和前景。

那么这个方法到底怎么回事呢？最近又有什么研究进展呢？让我们来聊一聊。

马尔可夫其人

先来说说这个方法的提出者，马尔可夫，数学家，全名是安德雷·安德耶维齐·马尔可夫，看名字就猜出来了，这是一位俄国人。马尔可夫所处的时代是俄国数学蓬勃发展的时期，他的老师契比雪夫，是俄国数学从落后到繁荣的重要奠基人，圣彼得堡学派的奠基人和领袖。

圣彼得堡学派源于俄国的一代强人彼得大帝，这哥们当时在欧洲各国溜达了一圈，发现自己的国家实在是落后，方方面面的不如别人，于是在俄国的西边边境上，把靠近西欧国家的圣彼得堡设立为新的首都，作为与西欧强国交流的重要窗口。为了尽快提高俄国的科技水平，彼得大帝找猎头疯狂挖人，把咱们在大学数学中经常听说的伯努利兄弟、欧拉、哥德巴赫等大神们，都请到了圣彼得堡的科学院，迅速拉高了俄国的数学Level。比如欧拉大神，在当时基本上就是数学界的标杆人物，他研究啥大家就跟着关注啥，属于顶级流量了也是。欧拉在图论、微积分等领域都做了非常多开创性工作，这里就不多展开了，感兴趣的可以去了解了解。

就是在这种背景下，俄国的数学逐渐发展，直到契比雪夫，才通过在概率论、解析数论和函数逼近论等领域的开创性工作逐渐让俄国数学界的能力受到西欧同行们的认可。他的徒弟马尔可夫就是属于继承师傅的概率论和数论的衣钵，继续开拓了很多新的成果。马尔可夫链及马尔可夫过程都是非常有代表性的成果之一。目前，马尔可夫过程相关的理论与方法已经被广泛应用于自然科学、工程技术和公用事业中。当然马尔可夫过程后续的很多发展又有诸多大佬作出了完善和改进，并不是马尔可夫一个人的功劳。

马尔可夫本人呢，在当时属于不愿意受世俗约束的性格，大学之前在老师们眼里都属于桀骜不驯的那种，因为那个时代的俄国还是受教会影响较深，马尔可夫就读的学校就是按照传统东正教方式管理的，东正教属于基督教下面的一个分支，是伴随罗马帝国分裂为东西罗马帝国，在东罗马帝国中发展起来的东派正教，而在俄国的发展尤为兴盛，主要是由于著名的莫斯科大公伊凡三世通过迎娶东罗马帝国的末代公主，借此名义来继承罗马帝国遗志，号称第三罗马帝国。由此，东正教成为俄国的国教，教会对于读物和礼仪的要求比较严格，马尔可夫则是比较抵触这种约束的，直到考入圣彼得堡大学的数学系，才进入了比较自由的氛围。

在大学期间，马尔可夫表现优异，师从了前面提到的俄国数学的重要奠基人契比雪夫，可以说是契比雪夫和他的弟子们的成就让俄国在数学世界中占有了一席之地。马尔可夫的主要工作集中在数论和概率论的研究方面，尤其是概率论方面，圣彼得堡学派对概率论这门学科贡献很大，现在学习概率论还经常看到很多苏联时期的书籍，马尔可夫在概率论领域成果颇多，从一开始对大数定理和中心极限定理的研究，逐渐发展到对随机变量的研究，终于提出了大名鼎鼎的马尔可夫链概率模型。

马尔科夫对概率论的研究成果都汇集到了他的著作《概率演算》之中，每次修订再版也会将新的研究成果编辑进去，直到去世之前还在完成第四版的修订。

马尔可夫过程的经典方法

1906年，马尔科夫发表《大数定律关于相依变量的扩展》，通过研究扩大极限定理的应用范围，第一次提到这种如同锁链般环环相扣的随机变量序列，其中某个变量各以多大的概率取什么值，完全由它前面的一个变量来决定，而与它更前面的那些变量无关。这就是被后人称作马尔科夫链的著名概率模型。也是在这篇论文里，马尔科夫建立了这种链的大数定律。随着发展，马尔可夫链被扩大到随机过程的一种，即马尔可夫过程。

马尔可夫性质：一句话总结就是“未来只与现在有关”，即给定一个过程当前状态及历史的所有状态，其未来状态仅依赖于当前状态，与历史状态无关，这种性质叫做马尔科夫性质。这里比较有意思的事情是，有些非马尔可夫过程可以通过扩展“现在”和“未来”状态的概念来构造一个马尔可夫过程，这种情况称为二阶马尔可夫过程。以此类推，还可以构造更高阶的马尔可夫过程。

马尔可夫链：是一种最简单的马尔可夫过程，专指离散指数集的马尔可夫过程。经典的马尔可夫链主要是研究当前状态和未来状态之间的转移概率，并可以计算出多次试验之后的每个状态的概率分布，从而将看起来毫无规律的一些随机现象变成了整体有序的状态变化。

用一个通俗的比喻来形容，一只被切除了大脑的白鼠在若干个洞穴间的蹿动就构成一个马尔科夫链。因为这只白鼠已没有了记忆，瞬间而生的念头决定了它从一个洞穴蹿到另一个洞穴；当其所在位置确定时，它下一步蹿往何处与它以往经过的路径无关。

这一模型的哲学意义是十分明显的，用前苏联数学家辛钦（1894－1959〕的话来说，就是承认客观世界中有这样一种现象，其未来由现在决定的程度，使得我们关于过去的知识丝毫不影响这种决定性。这种在已知“现在”的条件下，“未来”与“过去”彼此独立的特性就被称为马尔科夫性，具有这种性质的随机过程就叫做马尔科夫过程，其最原始的模型就是马尔科夫链。

马尔可夫链极其扩展被广泛的应用，如物理学和化学中，马尔可夫链和马尔可夫过程被用于对动力系统进行建模，形成了马尔可夫动力学（Markov dynamics）。在排队论（queueingtheory）中，马尔可夫链是排队过程的基本模型。在信号处理方面，马尔可夫链是一些序列数据压缩算法，例如Ziv-Lempel编码的数学模型，在金融领域，马尔可夫链模型被用于预测企业产品的市场占有率。

马尔可夫决策过程，是将马尔可夫性质应用于时序决策建模的方法，设定智能体的随机性策略和回报符合马尔可夫性质，这样就将智能体在与环境交互中的状态转移计算过程定义为马尔可夫性质的状态转移过程计算。通过使用动态规划、随机采样等方法，MDP可以求解使回报最大化的智能体策略。当今人工智能研究中火热的强化学习方向，方法的基石就是马尔可夫决策过程（Markov Decision Processes, MDP），这个方法是Bellman通过离散随机最优控制模型首次提出的，对于时序决策问题具有很好的建模能力。

马尔可夫性质对于数学后续的发展起到了基石的作用，后续很多数学家在此基础上发展出了更多的扩散模型和随机过程模型。说几个例子。

马尔可夫链蒙特卡罗，将马尔科夫链与蒙特卡洛方法结合，把经典蒙特卡洛方法中统计独立的特性改造为马尔科夫性质的统计相关，在某些情况下对随机现象的建模效果更佳，这种方法在图像处理、信号处理、金融分析等领域有广泛应用。

隐马尔可夫模型，是对马尔可夫模型的扩展，这种模型的思想核心是把马尔科夫的状态转移设定为未知的隐含量，通过可观测的状态转移过程来估计隐含的状态，然后再用隐含状态来预计未来的变化，利用这种方法发现很多实际问题能够得到有效的建模，典型的应用包括了语音识别、生物信息科学的DNA分析和故障诊断等领域。

马尔可夫随机场，给随机场定义一种马尔可夫性质，即随机场中每个位置的属性定义是马尔可夫性的，简单理解就是随机场中每个位置的属性只与邻近的位置有关，与其他位置无关。这种方法被应用于图像分割取得较好效果。

基石：随机过程理论

马尔可夫性质的建立是在概率论研究过程提出来的，马尔可夫过程也是一种非常经典且影响深远的随机过程，伴随着相关理论和方法的发展，随机过程理论已经成为对当今社会影响深远的一门学科。

什么是随机过程呢？这是一个不太好理解的概念，我们尝试着把他解读一下。随机过程的背后隐含着一种周期性，即某种现象是可以重复出现的，虽然我们不知道为什么会重复出现，但是可以利用观测到的信息进行统计分析，找到在一个时间段内的重复性规律，比如数据在一段时间内的分布规律具有马尔可夫性质、符合鞅点过程分布、布朗运动分布、泊松过程分布等。

与随机过程概念相对的是确定性理论，或者叫决定论，即把输入参数确定下来，输出就是确定的，比如经典的牛顿力学定律。

举个例子，把速度和时间确定下来，那么距离就可以计算了，但是随机过程中把每个参数都进行了随机化，比如你今天开一辆车出去，速度和时间都不是确定的，具有一定范围的随机性，所以无法对你一次具体的开车速度、时间和距离进行建模和预测，但是如果从一年之中你开车的速度、时间和距离进行分析，可以得到一个概率分布，即你的速度会分布在几个区间，每个区间出现的概率是多少，那么便可以对这个整体过程进行建模和预测了。

随机过程属于概率论的一个重要发展方向，其核心思想区别于确定性的分析，将分析过程建立在一种随机的基础上。发展到现在已经建立了比较完善的理论体系和分析方法，包括测度论、微分方程、半群理论、函数堆和希尔伯特空间等。

但是“随机”这个核心概念至今仍然存在争议，即随机现象的产生到底是因为客观的原因还是主观导致的，随机的不确定性现象背后是否有确定性的原因，仍然是未解之谜，也可能是受到了人类观测和分析世界能力的限制，至今仍然无法触及问题的核心。

说到这儿可以讲讲物理学四大神兽之一，拉普拉斯之妖。

200年前，法国著名科学家拉普拉斯说，我们可以把宇宙现在的状态看作是它历史的果，和未来的因。如果存在这么一个智慧，它在某一时刻，能够获知驱动这个自然运动的所有的力，以及组成这个自然的所有物体的位置，并且这个智慧足够强大，可以把这些数据进行分析，那么宇宙之中从最宏大的天体到最渺小的原子都将包含在一个运动方程之中；对这个智慧而言，未来将无一不确定，恰如历史一样，在它眼前一览无遗”。这种说法之中所强调的就是决定论，即一切都是确定的，可以精确计算和预测的。

在那个时代里确实通过经典力学、电磁学、天文学的发展得到了一次次的印证，直到量子力学、混沌理论的发展，决定论才被打破。混沌理论发现，初始条件的微小变化可以导致未来发展的重大区别，典型的例子就是蝴蝶效应，现实中如天气预报、社会经济的分析十分困难，因为小小的误差就可能导致结果非常不准确。量子力学又发现微小粒子的运动规律变幻莫测，无法按照经典力学的方式分析运动过程，只能通过观测去统计一些重复出现的现象，建立的模型就是随机过程模型，对量子运动的分布规律做分析，形成时间、位置等一系列的概率模型。

直至今日，拉普拉斯之妖仍然没有定论，因为诸多物理学现象的谜团仍未解开，这些谜团到底是因为人类的观测和计算能力限制了决定论方法的发现，还是却是有客观的不确定性存在？不得而知。

在这种现实情况下，随机过程就成为了对这种不确定问题分析的有效手段，而马尔可夫性质又将不确定问题做了很好的简化使其便于计算，于是人们都可以看到一种叫作随机过程的数学模型：从银河亮度的起伏到星系空间的物质分布、从分子的布朗运动到原子的蜕变过程，从化学反应动力学到电话通讯理论、从谣言的传播到传染病的流行、从市场预测到密码破译，随机过程理论及其应用几乎无所不在。人类历史上第一个从理论上提出并加以研究的过程模型是马尔科夫链，它是马尔科夫对概率论乃至人类思想发展作出的伟大贡献。

新的进展

伴随着应用场景的拓展，经典马尔可夫过程逐渐不够用了，于是随着对现实更加准确的描述，大家把其中很多约束条件替换为更为复杂的条件或者叫更加宽泛的条件，发展出了在特定约束条件下的马尔可夫过程。咱们大概说一说，挂一漏万，有熟悉的朋友欢迎多多指点。

状态部分可观测的马可夫决策过程（POMDP），这个方法主要是把状态的观测能力定义为不完全的情况，即对状态的观察存在不确定性，因为现实中确实经常难以准确的观测和定义状态，那么对于状态的定义就要在原来的“状态空间”的基础上增加“观察”和“条件观察概率”这两个设定了，其分析过程就变得复杂了很多，经常需要通过近似计算来求解，即把不确定的因素通过一些方式转换为可以确定的因素来计算。因为POMDP的架构可以更好的模拟不同的真实世界的连续过程，所以正在被越来越多的应用于机器人导航问题、机械维护和不定性规划等领域。

分布式马尔可夫决策过程（DEC-POMDP），这个方向主要针对多智能体经由分布式的计算而达成共同目标的问题，在这类问题中，智能体之间通常不一定拥有良好的通信，或者充足的带宽达到一种信息的完全共享，智能体之间不清楚其他合作者所观察到的信息。换句话说，在同一环境中的不同智能体可能认为自身处于不同的状态（信念状态）。因而，相对单一智能体或者集中式控制信息完全共享的多智能体合作问题，这种信息的不一致性增加了新的困难。

部分可观察的随机博弈（POSG），与上一个问题很接近，随机博弈中各个智能体可以有不同的收益评价方式，所以这种情况下可以与博弈论联系到一起，从一定意义上来说，DEC-POMDP问题可以算是POSG问题的一个特例。POSG问题按照有限步骤和无限步骤的博弈，又可以对应于平稳策略和非平稳策略。

半马尔可夫过程（Semi-Markov Decision Processes），也叫非时齐马尔可夫决策过程，经典的马尔可夫过程是时齐过程，所谓时齐指的是每部可选行动的执行时间是相同的，相邻状态之间转移的时间间隔是一致的。而非齐时则不同，时间间隔上不一致，还可能符合某种概率分布。半马尔可夫决策的主要意义在于它更加接近现实中人类规划并解决问题的方式，通常存在时间的延迟，具有较大尺度的时间范围。

多目标MDP，即将多目标规划与MDP结合起来，把报酬函数变成了向量，对应的目标函数也变成了向量，这样就可以利用MDP做多目标决策的优化，寻找一个可行解。

自适应MDP，这里面主要是假设MDP中的转移率和报酬函数均与某个未知参数有关，当未知参数是固定值时，可以通过渐进折扣最优准则来研究。当未知参数是动态变化的值，则要通过某种方式动态估计未知参数。

受约束的MDP，很多问题的策略制定是在一定约束条件下的，比如费用最小、时间最短等。那么要在传统MDP求解最优平稳策略中，去寻找符合受约束的最优策略。很多经济和工程问题都能用受约束的MDP来描述。

未来的发展

说了这么多，可以看出来马尔可夫决策过程这一理论作为研究决策问题的基石，是不可不察的方向。而伴随着马尔可夫过程在现实决策问题的扩展应用，各种变化的MDP过程被提出来并研究求解的方法，这将是不断扩展的一个重要方向。

另一方面也可以看出数学在其中发挥的重要作用，马尔可夫的生涯伴随了俄国数学的崛起，也就是在这样的背景下，俄国就一直保持着对数学的高度重视，即使是二次大战中遭受了重大的毁坏之后，数学研究院也得到了非常及时的重建，如今俄罗斯的数学界又是人才辈出，多人获得了国际顶尖的数学大奖菲尔兹奖。说明人家非常清楚，数学作为基础学科，对于科技创新的重要意义。也正是因为此，虽然俄罗斯的经济发展一度非常坎坷，但是国防工业和科技创新并没有落后，仍然保持了较高水平。