poster471

马尔可夫链的应用

5877
2
本文将分享一些搜集来的马尔可夫链应用场景供读者参考,希望能带来一些启发.
马尔可夫链的应用
7 人挑战成功
返回挑战
challenge-problem-icon

完成本期挑战需要达到:

本科数学水平

7 / 14 读者挑战成功
题目

有一个两年的社区大学, 学生可以有四个状态选择, 分别是, 其中表示学生在上一年级或二年级, 表示毕业, 表示退学. 假设不同的状态转移只与转移前所处的状态有关, 与之前的转移无关, 已知不同状态之间转移的概率用如下矩阵表示, 矩阵的元素表示从状态转移到状态的概率. 其中, .

那么一年级学生能毕业的概率是__________.

选项

跳过看答案

本文将分享一些搜集来的马尔可夫链应用场景供读者参考,希望能带来一些启发.

马尔可夫链回顾

目前,我们总计接触了两个马尔可夫链的问题背景,一个是老鼠版Maze Runner问题,一个是Page Rank算法. 下面先回顾下马尔可夫链模型的相关概念.

我们用表示个研究对象可能处于的状态

把研究对象经过次转移后处于状态的概率所组成的维向量称为状态向量. 称为初始状态向量.

如果研究对象每一次的状态转移,只与转移前所处的状态有关,与之前的转移无关 [1],即我们用表示从状态转移到状态的概率. 各个状态之间转移的概率所组成的方阵

称为转移矩阵.

于是我们会得到状态向量满足如下递推关系,

不难推得,.

场景一: 天气预报

如果我们把天气状况简单分为晴、多云、雨天三个状态,通过对某一地区历史气象数据统计发现 [2]

  • 如果当天是晴天,则第二天是晴天的概率[3],是阴天的概率为,是雨天的概率为.
  • 如果当天是多云,则第二天是晴天的概率为,是阴天的概率为,是雨天的概率为.
  • 如果当天是雨天,则第二天是晴天的概率为,是阴天的概率为,是雨天的概率为.

如果周一是晴天,那么如何预测周五的天气情况.

几乎所有关于马尔可夫链的教材都会有这样的习题或者例题,但实际应用中往往比这个要复杂得多. 而且第二天的天气真的只与当天天气有关,与前一天无关吗?

当然我们可以改为考虑前两天的天气,只要把连续两天的天气作为一个状态即可,即会有个状态. 这样马尔可夫链模型就仍然适用了.

场景二: 病情(艾滋病)预测

艾滋病毒感染者病情发展有这样几个阶段(状态):

  • 无临床症状(HIV asymptomatic)
  • 有临床病状(HIV symptomatic)
  • 获得性免疫缺陷综合征(AIDS)
  • 死亡(death)

image

某地区艾滋病感染者一年后由一个状态转移到另一个状态的概率如上图所示 [4]. 如果目前该地区感染者处于各状态的比例如下:

  • 85% asymptomatic
  • 10% symptomatic
  • 5% AIDS
  • 0% death

那么一年后,该地区感染者处于各状态的比例如何?

如果仅仅计算某个感染者的概率,显然病情发展与该患者获得的治疗有着密切关系. 但如果研究某个地区的艾滋病患者,那么在无外界因素干预如国家加大艾滋病治疗投入或艾滋病特效药研发成功等,马尔可夫链模型是个不错的预测模型.

场景三: 分子扩散模型

image

如果将两个充满不同气体的容器相互联通当中仅用薄膜分隔(允许分子在两容器间穿梭),那么经过一段时间后,两个容器中的混合气体成分如何?

1907年物理学家 _Tatiana_ 和 _Paul Ehrenfest_ 为了解释热力学第二定律而提出了一个分子扩散模型 [5]. 下面我们用尽可能简单的语言来描述下这个模型.

我们把两个容器编号为A和B,两个容器内分子总数设为,我们把容器A内含有分子个数为看作是个状态,当一个分子从一个容器转移到另一个容器,则容器A的状态发生一次转移. 假设每个分子等可能被选中发生转移,即从所在的容器转移到另一个容器.

举个具体的例子,假设总共有个分子,容器A目前有个分子(处于状态2). 那么下一次转移,这个分子等可能地被选中发生转移,即有的概率容器A中的分子被选中,有的概率容器B中的分子被选中. 那么转移发生后,有的概率容器A的一个分子跑到容器B(容器A从状态2转移到状态1),有的概率容器中的一个分子跑到容器中(容器A从状态2转移到状态3).

如果用表示容器A从状态到状态的概率,则有

当然还有进阶版 _Bernoulli-Laplace_ 模型,考虑两种不同的分子,每次在两个容器中各等可能地取一个分子进行一次交换. 事实上,我在网上还发现不少用这个模型来研究洗牌的.

场景四: 体育比赛

每局网球比赛中,选手必须得分4次且比对手多两次得分才能获胜. 当两名选手得分一样且大于等于三次时,称作“平(dauce)”. 假设选手A和选手B在某局比赛达到了“平”,此时选手A再得分一次称作“A占先(advantage A)”,反之选手B再得分一次称作“B占先(advantage B)”. 假设比赛进行到了“A占先”,此时选手A再得分一次即获胜,反之选手B再得分一次则返回“平” [6].

也就是当比赛进行到“平”后,有这样五个状态:

  • A占先
  • B占先
  • A胜
  • B胜

假设比赛进行到平后,每个球选手A得分的概率都为, 则选手A在4个球内获胜的概率多少?

这也是一道很常见的马尔可夫链教材里的习题,其他的一些运动项目如排球、乒乓也有类似的计分规则. 我们关心的是,在这个赛制下得分率的选手获胜的概率满足怎样的关系. 如果调整比赛赛制后,对两者的关系会产生的怎样的影响.

结语

关于马尔科夫链能找到的公开课、课件、论文数不胜数,本文当然无法穷尽所有的应用场景,事实上马尔可夫链在目前相当热门的机器学习领域(如自然语言处理、语音手写识别等)也有着广泛的应用,因为往往涉及到升级版“隐马尔可夫链”就没有收录. 有兴趣的读者可以自行搜索了解更多马尔科夫链的应用.


  1. 这是适用马尔可夫链模型的重要条件.
  2. 这里的数据纯属瞎掰,感兴趣的读者可以免费使用中国气象数据网的API获得相关数据. 中国气象数据网API
  3. 这里的概率指的是统计得出频率,只要样本足够多在实际应用中,我们都称作概率.
  4. 图片及数据取自Paul Harper教授发布在Youtube上的公开课.
  5. 埃伦费斯特模型,详见维基百科
  6. 网球比赛计分规则,详见维基百科
0

发布于1 年前
慕容玖
level0
展开所有评论
发表评论
0

发布于1 年前
Luo DK
level0
0这里的P貌似要转置Luo DK发表于1 年前
展开所有评论
发表评论