其实当初写马尔可夫链，只是想介绍下矩阵乘法的一些应用背景，想不到由一道老鼠版Maze Runner问题出发引出的三个思考催生了后续两篇博客，以至于差不多把马尔可夫链问题讲了个大概了. 相信完整读完前三篇博客的读者，现在已经跃跃欲试，尝试在身边寻找可以应用马可尔夫链的实际场景，准备一展身手改变世界了吧. 橘子老君本文将分享一些搜集来的马尔可夫链应用场景供读者参考，希望能带来一些启发. 另外，相关在线课程也正在紧张制作当中，敬请期待！ 回顾目前，我们总计接触了两个马尔可夫链的问题背景，一个是老鼠版Maze Runner问题，一个是Page Rank算法. 下面我们一起回忆下马尔可夫链模型的相关概念. Show
我们用 S_1, S_2, \cdots S_m 表示 m 个研究对象可能处于的状态， 把研究对象经过 n 次转移后处于状态 S_1, S_2, \cdots S_m 的概率所组成的 m 维向量 \mathrm{x}_n 称为状态向量. \mathrm{x}_0 称为初始状态向量. 如果研究对象每一次的状态转移，只与转移前所处的状态有关，与之前的转移无关，即我们用 p_{ij} 表示从状态 S_j 转移到状态 S_i 的概率. 各个状态之间转移的概率所组成的方阵  称为转移矩阵. 于是我们会得到状态向量满足如下递推关系， 不难推得， \mathrm{x_{n}}=P^n \mathrm{x_0} . 场景一: 天气预报如果我们把天气状况简单分为晴、多云、雨天三个状态，通过对某一地区历史气象数据统计发现[^1]，
如果周一是晴天，那么如何预测周五的天气情况. 几乎所有关于马尔可夫链的教材都会有这样的习题或者例题，但实际应用中往往比这个要复杂得多. 而且第二天的天气真的只与当天天气有关，与前一天无关吗？ 当然我们可以改为考虑前两天的天气，只要把连续两天的天气作为一个状态即可，即会有 \mathrm{P}_3^2 个状态. 这样马儿可夫链模型就仍然适用了. 场景二: 病情(艾滋病)预测艾滋病毒感染者病情发展有这样几个阶段(状态)：
某地区艾滋病感染者一年后由一个状态转移到另一个状态的概率如上图所示[^2]. 如果目前该地区感染者处于各状态的比例如下:
那么一年后，该地区感染者处于各状态的比例如何？ [^2]: 图片及数据取自Paul Harper教授发布在Youtube上的公开课. 如果仅仅计算某个感染者的概率，显然病情发展与该患者获得的治疗有着密切关系. 但如果研究某个地区的艾滋病患者，那么在无外界因素干预如国家加大艾滋病治疗投入或艾滋病特效药研发成功等，马尔可夫链模型是个不错的预测模型. 场景三: 分子扩散模型如果将两个充满不同气体的容器相互联通当中仅用薄膜分隔(允许分子在两容器间穿梭)，那么经过一段时间后，两个容器中的混合气体成分如何？ 1907年物理学家 Tatiana 和 Paul Ehrenfest 为了解释热力学第二定律而提出了一个分子扩散模型. 下面老君用尽可能简单的语言来描述下这个模型. 我们把两个容器编号为A和B，两个容器内分子总数设为 m ，我们把容器A内含有分子个数为 0, 1, \cdots, m 看作是 m+1 个状态，当一个分子从一个容器转移到另一个容器，则容器A的状态发生一次转移. 假设每个分子等可能被选中发生转移，即从所在的容器转移到另一个容器. 举个具体的例子，假设总共有 10 个分子，容器A目前有 2 个分子(处于状态2). 那么下一次转移，这 10 个分子等可能地被选中发生转移，即有 \dfrac{2}{10} 的概率容器A中的分子被选中，有 \dfrac{8}{10} 的概率容器B中的分子被选中. 那么转移发生后，有 \dfrac{2}{10} 的概率容器A的一个分子跑到容器B(容器A从状态2转移到状态1)，有 \dfrac{8}{10} 的概率容器 B 中的一个分子跑到容器 A 中(容器A从状态2转移到状态3). 如果用 P_{ij} 表示容器A从状态 j 到状态 i 的概率，则有 当然还有进阶版 Bernoulli-Laplace 模型，考虑两种不同的分子，每次在两个容器中各等可能地取一个分子进行一次交换. 事实上，我在网上还发现不少用这个模型来研究洗牌的. 场景四: 体育比赛每局网球比赛中，选手必须得分4次且比对手多两次得分才能获胜. 当两名选手得分一样且大于等于三次时，称作“平(dauce)”. 假设选手A和选手B在某局比赛达到了“平”，此时选手A再得分一次称作“A占先(advantage A)”，反之选手B再得分一次称作“B占先(advantage B)”. 假设比赛进行到了“A占先”，此时选手A再得分一次即获胜，反之选手B再得分一次则返回“平”. 也就是当比赛进行到“平”后，有这样五个状态：
假设比赛进行到平后，每个球选手A得分的概率都为 p , 则选手A在4个球内获胜的概率多少? 这也是一道很常见的马尔可夫链教材里的习题，其他的一些运动项目如排球、乒乓也有类似的计分规则. 橘子老君比较好奇的是，在这个赛制下得分率 p 的选手获胜的概率 p' ， p 与 p' 满足怎样的关系. 如果调整比赛赛制后，对两者的关系会产生的怎样的影响. 结语橘子老君发现用一个关键字在搜索引擎中能找到的公开课、课件、论文数不胜数，这里当然也无法穷尽所有的应用场景，事实上马尔可夫链在目前相当热门的机器学习领域（如自然语言处理、语音手写识别等）有着广泛的应用，因为往往涉及到升级版“隐马尔可夫链”就没有收录. 但另一方面，能找到的国内中文的资料真的要少很多，也实在不能想象应用马尔可夫链做天气预报那种教科书例题式的文章竟然在16年还发表在国内学术期刊上. 我不知道是国内的学术圈、数学爱好者是都喜欢秘而不宣在小圈子里交流呢，还是应该由度娘的算法来背这个锅(看看过段时间能不能在度娘里找到我的博客检验一下). 导入自橘子老君的博客. 更多适合中学生的趣味科普文章，关注微信公众号：橘子数学
马尔可夫链（英語：Markov chain），又稱離散時間馬可夫鏈（discrete-time Markov chain，縮寫為DTMC[1]），因俄國數學家安德烈·马尔可夫得名，为狀態空間中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作馬可夫性質。马尔科夫链作为实际过程的统计模型具有许多应用。 在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态，也可以保持当前状态。状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的（无论之前漫步路径是如何的）。 介绍[编辑]马尔可夫链是离散状态、离散时间的马尔可夫过程。 形式化定义[编辑]马尔可夫链是满足马尔可夫性质的随机变量序列X1, X2, X3, ...，即给出当前状态，将来状态和过去状态是相互独立的。从形式上看， 如果两边的条件分布有定义（即如果），则。Xi的可能值构成的可数集S叫做该链的“状态空间”。 通常用一系列有向图来描述马尔可夫链，其中图n的边用从时刻n的状态到时刻n+1的状态的概率来标记。也可以用从时刻n到时刻n+1的转移矩阵表示同样的信息。但是，马氏链常常被假定为时齐的（见下文的变种），在这种情况下，图和矩阵与n无关，因此也不表现为序列。 这些描述强调了马尔可夫链与初始分布无关这一结构。当时齐的时候，可以认为马氏链是分配从一个顶点或状态跳变到相邻一个的概率的状态机。可以把机器状态的概率作为仅有元素的状态空间为输入的机器的统计行为分析，或作为初始分布为状态为输入的机器行为，其中是艾佛森括号。 一些状态序列可能会有零概率的事件，对应多连通分量的图，而我们禁止转移概率为0的边。例如，若a到b的概率非零，但a到x位于图的不同连通分量，那么有意义，而无意义。 变种[编辑]
瞬态演变[编辑]用n步从状态i到状态j的概率为 而单步转移是 对于一个时齐马尔可夫链来说： 而 n步转移概率满足查普曼-科尔莫戈罗夫等式，对任意k使得0 < k < n， 其中S为此马尔可夫链的状态空间。 边缘分布Pr(Xn = x)为第n次状态的分布。初始分布为Pr(X0 = x)。用一步转移把过程演变描述为 。注意：上标（n）是索引而非指数。 性质[编辑]可还原性[编辑]马尔可夫链是由一个条件分布来表示的 这被称为是随机过程中的“转移概率”。这有时也被称作是“一步转移概率”。二、三，以及更多步的转移概率可以导自一步转移概率和马尔可夫性质： 同样， 这些式子可以通过乘以转移概率并求次积分来一般化到任意的将来时间。 周期性[编辑]边缘分布是在时间为时的状态的分布。初始分布为。该过程的变化可以用以下的一个时间步幅来描述： 这是Frobenius-Perron equation的一个版本。这时可能存在一个或多个状态分布满足 其中只是为了便于对变量积分的一个名义。这样的分布被称作是“平稳分布”（Stationary Distribution）或者“稳态分布”（Steady-state Distribution）。一个平稳分布是一个对应于特征值为的条件分布函数的特征方程。 平稳分布是否存在，以及如果存在是否唯一，这是由过程的特定性质决定的。“不可约”是指每一个状态都可来自任意的其它状态。当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为是“周期的”。 重现性[编辑]各态历遍性[编辑]具有重现性而不具有周期性叫做遍历的。重现性包括局部重现性。 律动性[编辑]平稳状态分析和极限分布[编辑]平稳状态分析和时齐马尔可夫链[编辑]有限状态空间[编辑]若状态空间是有限的，则转移概率分布可以矩阵表示，该矩阵称为转移矩阵，记为P。其中处于的元素等于 由于P的每一行各元素之和为1，且P中所有的元素都是非负的，因此P是一个右随机矩阵。 稳定分布与特征向量和单纯形的关系[编辑]稳定分布π是一个（行）向量，它的元素都非负且和为1，不随施加P操作而改变，定义为 通过将这个定义与特征向量进行比较，我们看到，这两个概念是相关的，并且 是由（）归一化的转移矩阵P的左特征向量 e的倍数，其特征值为1。如果有多个单位特征向量那么相应稳态的加权和也是稳态。但对于马尔可夫链来说，我们更关心的是作为一些对初始分布的序列分布的极限的稳态。 稳定分布的值与状态空间P有关，它的特征向量保留各自的相对比例。因为π的成分为正且满足约束条件，我们发现π与一个成分全为1的向量的点积是统一的，、π位于一个单纯形上。 有限状态空间内的时齐马尔可夫链[编辑]对于一个离散状态空间，步转移概率的积分即为求和，可以对转移矩阵求次幂来求得。就是说，如果是一步转移矩阵，就是步转移后的转移矩阵。 如果转移矩阵不可约，并且是非周期的，则收敛到一个每一列都是不同的平稳分布，并且， ,独立于初始分布。这是由Perron-Frobenius theorem所指出的。 正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的。矩阵被称为是一个随机矩阵，当且仅当这是某个马尔可夫链中转移概率的矩阵。 注意：在上面的定式化中，元素是由j转移到i的概率。有时候一个由元素给出的等价的定式化等于由i转移到j的概率。在此情况下，转移矩阵仅是这里所给出的转移矩阵的转置。另外，一个系统的平稳分布是由该转移矩阵（每列的和为1）的右特征向量给出的，而不是左特征向量。 转移概率独立于过去的特殊况为熟知的Bernoulli scheme。仅有两个可能状态的Bernoulli scheme被熟知为伯努利过程 趋向稳定分布的收敛速度[编辑]可反转马尔可夫链[编辑]可反转马尔可夫链类似于应用贝叶斯定理来反转一个条件概率： 以上就是反转的马尔可夫链。因而，如果存在一个π，使得： 那么这个马尔可夫链就是可反转的。 这个条件也被称为细致平衡（detailed balance）条件。 对于所有的i求和： 所以，对于可反转马尔可夫链，π总是一个平稳分布。 伯努利方案[编辑]伯努利方案是马尔可夫链的一种特殊情形，其转移概率矩阵有相同的行，即下一状态均匀独立于当前状态（除了独立于过往状态以外）。 仅有两个可能状态的伯努利方案是伯努利过程。 一般的状态空间[编辑]对于一般状态空间上的马尔可夫链的概述，详见文章状态空间可测的马尔可夫链。 Harris链[编辑]局部交互的马尔可夫链[编辑]应用[编辑]物理[编辑]马尔可夫系统广泛出现在热力学和统计力学中， 化学[编辑]测试[编辑]语音识别[编辑]隐马尔科夫模型是大多数现代自动语音识别系统的基础。 資訊科学[编辑]排队理论[编辑]互联网应用[编辑]谷歌所使用的网页排序算法（PageRank）就是由马尔可夫链定义的。如果 是已知的网页数量，一个页面 有 个链接到这个页面，那么它到链接页面的转换概率为，到未链接页面的概率为， 参数 的取值大约为0.85。 马尔可夫模型也被应用于分析用户浏览网页的行为。一阶或者二阶的马尔可夫模型可以用于对一个用户从某一网络链接转移到另一链接的行为进行建模，然后这些模型可以用于对用户之后的浏览行为进行预测。 统计[编辑]经济和金融[编辑]马尔科夫链可以应用于金融与经济中一系列现象的建模，包括资产价值与市场冲击。1974年Prasad等人第一次应用马尔科夫链于金融模型[2]，另一个是James D. Hamilton 1989年应用的机制转换模型[3]，其中马尔科夫链用来对高GDP增长速度时期与低GDP增长速度时期（换言之，经济扩张与紧缩）的转换进行建模[3]。 社会科学[编辑]生物数学[编辑]马尔可夫链也有众多的生物学应用，特别是增殖过程，可以帮助模拟生物增殖过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测（見哈代-溫伯格定律。） 遗传学[编辑]游戏[编辑]音乐[编辑]棒球[编辑]马尔可夫文本生成器[编辑]马尔可夫过程，能为给定样品文本，生成粗略，但看似真实的文本：他们被用于众多供消遣的“模仿生成器”软件。马尔可夫链还被用于谱曲。 信息论[编辑]用于计算马尔可夫信源的极限熵 历史[编辑]马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由俄國數學家柯尔莫果洛夫（俄語：Андре́й Никола́евич Колмого́ров）在1936年给出的。马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。 隱馬可夫模型[编辑]
参看[编辑]
参考文献[编辑]引用[编辑]
来源[编辑]
外部連結[编辑]
|
马尔科夫链应用
版權 © 2024 zh.wiewird Inc.
