马尔可夫模型

「马尔可夫模型」是指基于马尔可夫性质的模型,其假设一个给定过程的未来状态仅取决于当前状态。根据系统状态是否完全可被观测以及系统是自动的还是受控的,可以将常见的马尔可夫模型分成四种:马尔可夫链、隐马尔可夫模型(HMM)、马尔可夫决策过程(MDP)和部分可观测马尔可夫决策过程(POMDP)。另外还有马尔可夫随机场(MRF)和马尔可夫链蒙特卡洛(MCMC)这两个模型也常常被用于近似和预测。

来源:机器之心
简介

「马尔可夫模型」是指基于马尔可夫性质的模型,其假设一个给定过程的未来状态仅取决于当前状态。根据系统状态是否完全可被观测以及系统是自动的还是受控的,可以将常见的马尔可夫模型分成四种:马尔可夫链、隐马尔可夫模型(HMM)、马尔可夫决策过程(MDP)和部分可观测马尔可夫决策过程(POMDP),具体可见下表。


系统状态完全可被观测

系统状态不是完全可被观测

系统是自动的

马尔可夫链

隐马尔可夫模型

系统是受控的

马尔可夫决策过程

部分可观测马尔可夫决策过程

最简单的马尔可夫模型是马尔可夫链。它用一个随时间变化的随机变量来模拟系统的状态。在这种情况下,马尔可夫性质表明,这个变量的分布只取决于之前状态的分布。当马尔可夫链的状态只能部分观察到,这就是隐马尔可夫模型。隐马尔可夫模型常用的用途是语音识别,它是大多数现代自动语音识别系统的基础。

马尔可夫决策过程也是马尔可夫链,但其状态转换取决于当前状态和应用于系统的动作向量。通常,使用马尔可夫决策过程来计算行动策略,该行为策略将最大限度地提高与预期奖励相关的某种效用。它与强化学习密切相关,可以用价值迭代法和相关方法解决。

部分可观测马尔可夫决策过程是一个系统的状态只被部分观察到的马尔可夫决策过程,其中系统的状态只被部分观察到。部分可观测马尔可夫决策过程可以用于控制简单代理或机器人。

马尔可夫模型还包括马尔可夫随机场(MRF)和马尔可夫链蒙特卡洛(MCMC)——这两个模型也常常被用于近似和预测—— Tolerant Markov model (TMM)、层级马尔科夫模型(Hierarchical Markov models)、层级隐马尔可夫模型(hierarchicalhiddenMarkov model)等。

[描述来源:维基百科URL:https://en.wikipedia.org/wiki/Markov_model]

发展历史

1906年,Andrey Andreyevich Markov为了描述随机过程首次提出了马尔科夫链,并应用在俄语字符序列的计算中。到了1931年,Kolmogorov将其更通用化地应用在有限状态空间。马尔科夫链和两个二十世纪初物理学中重要的理论——布朗运动(Brownian motion)与遍历假说(ergodic hypothesis)均密切相关,从数学的层面对两者进行了建模和阐释,完成了从大数定律(Law of large numbers)到独立事件(dependent events)的扩展,并随后基于此发展出了随机马尔科夫过程。1960年左右Ruslan L. Stratonovich在他的论文中描述了隐马尔科夫模型(hidden markov model,HMM)中使用的向前和向后递归以及边缘平滑概率的计算。并在随后几年由Baum和Petrie发展了HMM理论。1984年,Stuart和Donald Geman兄弟在描述吉布斯采样时同时介绍了马尔可夫随机场(MRF)和最大后验估计(MAP estimate);1991年,Lovejoy 研究了部分可观测马尔可夫决策过程(POMDP)。

马尔可夫模型已经得到了数十年的研究,并在20 世纪70 年代早期进入了应用阶段——1975年,Baker提出了DRAGON系统,将HMM应用于语音识别,这也是HMM最早的实际应用。之后,HMM在生物领域也取得了巨大的成功,特别是1989年Gary A. Churchill 将HMM 用于分析生物序列;自那以后这就成为了这一领域可直接使用的技术。2001年,Bohnenberger 和Jameson在论文中提出在推荐系统中使用决策理论计划方法具有潜在的优势,这些方法可以为依赖于情境的推荐提供最佳策略。他们将MDP 用在了一家机场的推荐系统中。

现在,这些模型在人工智能的不同领域有着广泛的应用,比如预测输入的词(马尔可夫链)、语音识别(HMM)和强化学习(MDP、POMDP)。并且随着深度学习的流行,许多技术也与神经网络结合了起来,比如Yoshua Bengio 等研究者于2017年提出了GibbsNet,旨在通过匹配模型期望的联合分布和数据驱动的联合分布直接定义和学习转换算子(transition operator),然后使用转换算子训练图模型。

年份

事件

相关论文/Reference

1906

Andrey Andreyevich Markov 引入了马尔可夫链的概念

Markov, A. A. (1906). Rasprostranenie zakona bol’shih chisel na velichiny, zavisyaschie drug ot druga. Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 15(135-156), 18.

1960

Ruslan L. Stratonovich 首次描述了HMM

Stratonovich, R.L. (1960). Conditional Markov Processes.Theory of Probability and its Applications. 5 (2): 156–178.

1966

Baum et al. 发展了HMM 理论

Baum, L. E.; Petrie, T.(1966). Statistical Inference for Probabilistic Functions of Finite State Markov Chains. Ann. Math. Statist. 37 (6): 1554—1563.

1975

Baker 将HMM 用于语音识别(HMM 的第一个应用)

Baker, J.(1975). The DRAGON system—An overview.IEEE Transactions on Acoustics, Speech, and Signal Processing. 23: 24–29.

20世纪80年代

HMM 开始用于分析生物序列(DNA)

Bishop, M. and Thompson, E. (1986). Maximum Likelihood Alignment of DNA Sequences.Journal of Molecular Biology. 190 (2): 159–165.

1984

《Stochastic Relaxation, Gibbs Distributions, and the BayesianRestoration of Images》(Stuart Geman 和Donald Geman)介绍了马尔可夫随机场(MRF)、吉布斯采样和最大后验估计(MAP estimate)

Geman, S.; Geman, D.(1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.IEEE Transactions on Pattern Analysis and Machine Intelligence. 6 (6): 721–741.

1989

Gary A. Churchill 将HMM 用于分析生物序列;自那以后这就成为了这一领域可直接使用的技术

Churchill, G. A. (1989).Stochastic models for heterogeneous DNA sequences.Bulletin of mathematical biology. 51(1):79-94.

1991

Lovejoy 研究了部分可观测马尔可夫决策过程(POMDP)

Lovejoy, W. S. (1991).A survey of algorithmic methods for partially observed Markov decision processes.Annals of Operations Research. 28(1):47–65.

2001

Bohnenberger 和 Jameson 将 MDP 用在了一家机场的推荐系统中

Bohnenberger, T. and Jameson, A. (2001). When policies are better than plans: decision-theoretic planning of recommendation sequences.Proceedings of the 6th international conference on Intelligent user interfaces (IUI '01).

2017

Yoshua Bengio 等研究者提出了GibbsNet

Lamb, A. et al. (2017).GibbsNet: Iterative Adversarial Inference for Deep Graphical Models.arXiv:1712.04120.

发展分析

瓶颈

·在应用马尔可夫模型之前需要确保它满足「无记忆(memory-less)」的性质。

·马尔可夫链收敛到静态分布的速度可能很慢。

·隐藏状态之间的关系不是非常明显和清晰。

·因为状态之间的方向问题,模型在使用时可能会出现无限循环。

未来发展方向

·在不久的将来,会有改善收敛速度的新模型/算法出现。也许会有方法能帮助我们清晰准确地确定状态之间的依赖关系和过渡概率。因此,马尔可夫模型可以在更多领域和有更多目标客户的行业得到应用。

Contributor: Yuanyuan Li, Shiyuan Jiang

相关人物
盖瑞 · A. 丘吉尔
盖瑞 · A. 丘吉尔
小鼠遗传学家,现任美国缅因州杰克逊实验室教授。他使用系统化方法研究小鼠体内的健康、疾病以及与疾病相关的复杂性状的基因学。研究方向:糖尿病、基因工具、遗传与基因组学、计算生物学、生物信息学、糖尿病与肥胖。
斯图尔特·格曼
斯图尔特·格曼
生于1949年,美国数学家,以对计算机视觉、统计学、概率论、机器学习和神经科学有影响的贡献而闻名。他和他的兄弟Donald Geman因提出吉布斯采样器以及首次证明模拟退火算法的收敛性而闻名。
James K. Baker
James K. Baker
威廉·S·洛夫乔伊
威廉·S·洛夫乔伊
伦纳德·E·包姆
伦纳德·E·包姆
Leonard Esau Baum是一位美国数学家,以Baum-Welch算法而闻名。他于1953年毕业于哈佛大学的Phi Beta Kappa,并获得博士学位。在1958年哈佛大学的数学中,发表题为“交换半简单Banach代数中的导子”的论文。
安德雷·马尔可夫
安德雷·马尔可夫
简介
相关人物