关于马尔科夫的那点事（详细介绍马尔科夫模型、马尔科夫链）

1440359316

前言：我发现网上很多博客在讲马尔科夫相关的知识点的时候， 总是讲的不是很清楚，有的纯粹只关注理论，看不太懂，有的一上来就搞几个算例，更是一片懵逼，有的又将一些概念一会儿换一个说法，一会儿是马尔科夫过程，一会儿是马尔科夫模型，一会儿是马尔科夫链，傻傻分不清楚，也不好理解，决定自己抽点时间，好好写一下，会详细介绍马尔科夫模型、马尔科夫链、隐马尔可夫模型、条件随机场等相关的概念和案例，本文为第一篇。文中的理解方式是按照自己的理解方式来叙述的，不适合于每个人。

一、马尔科夫模型
( V) N1 k2 \* _  A1.1 马尔可夫过程

       马尔可夫过程（Markov process）是一类随机过程。由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性：在已知目前状态（现在）的条件下，它未来的演变（将来）不依赖于它以往的演变 (过去 )。例如森林中动物头数的变化构成——马尔可夫过程。在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。（这里虽然我也不清楚这些现象到底是不是，姑且就认为是吧！）
% d2 q0 Z8 l8 @! |
3 d  t4 x" y. ]4 Y( b; I马尔科夫过程中最核心的几个概念：过去，现在，将来。其中最核心的在于“现在”如何理解。

  _- J1 C8 n$ G+ c5 v* c在马尔可夫性的定义中，"现在"是指固定的时刻，但实际问题中常需把马尔可夫性中的“现在”这个时刻概念推广为停时（见随机过程）。例如考察从圆心出发的平面上的布朗运动，如果要研究首次到达圆周的时刻 τ以前的事件和以后的事件的条件独立性，这里τ为停时，并且认为τ是“现在”。如果把“现在”推广为停时情形的“现在”，在已知“现在”的条件下，“将来”与“过去”无关，这种特性就叫强马尔可夫性。具有这种性质的马尔可夫过程叫强马尔可夫过程。在相当一段时间内，不少人认为马尔可夫过程必然是强马尔可夫过程。首次提出对强马尔可夫性需要严格证明的是J.L.杜布。直到1956年，才有人找到马尔可夫过程不是强马尔可夫过程的例子。马尔可夫过程理论的进一步发展表明，强马尔可夫过程才是马尔可夫过程真正研究的对象。

. ~% U& W% L" _' [. F（这段话实在是太过于抽象了，不好理解，心里有数就行，因为这里的过去、现在、将来和我们生活中是有所差别的，不太好理解！）

所以：一个马尔科夫过程就是指过程中的每个状态的转移只依赖于之前的 n个状态，这个过程被称为 n阶马尔科夫模型，其中 n是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态，这也是后面很多模型的讨论基础，很多时候马尔科夫链、隐马尔可夫模型都是只讨论一阶模型，甚至很多文章就将一阶模型称之为马尔科夫模型，现在我们知道一阶只是一种特例而已了。

, N, t4 S7 N5 p' W' u' `9 u% f* G对于一阶马尔科夫模型，则有：
* @; d2 E, X6 V- S1 ]) C4 ^% u
如果第 i 时刻上的取值依赖于且仅依赖于第 i−1 时刻的取值，即
. W- N3 E2 g, C) \8 ]

  A! w* P  P+ B, A
​ 从这个式子可以看出，xi 仅仅与 xi-1有关，二跟他前面的都没有关系了，这就是一阶过程。
​
( R& q7 R/ f/ r( a
: L' M' S$ E6 e) i, y  m总结：马尔科夫过程指的是一个状态不断演变的过程，对其进行建模后称之为马尔科夫模型，在一定程度上，马尔科夫过程和马尔科夫链可以打等号的。
; s6 N% B. \8 N+ p1 f, h
1.2 马尔科夫性（无后效型）
8 |" D) t: r& [0 c# O* q0 K
在马尔科夫过程中，在给定当前知识或信息的情况下，过去（即当前以前的历史状态）对于预测将来（即当前以后的未来状态）是无关的。这种性质叫做无后效性。简单地说就是将来与过去无关，值与现在有关，不断向前形成这样一个过程。

, ?3 x! v4 E4 {4 b1.3 马尔可夫链
$ M2 c. a7 C- \! D; U% d
1 A" u; g4 K2 q! k, T. o" V' d时间和状态都是离散的马尔可夫过程称为马尔可夫链,简记为Xn=X(n),n=0,1,2…马尔可夫链是随机变量X1,X2,X3…的一个数列。
# i: X' q2 m! K& \+ ~2 v
, Y# m1 c- d0 }' c这种离散的情况其实草是我们所讨论的重点，很多时候我们就直接说这样的离散情况就是一个马尔科夫模型。
3 s& X) ?0 K5 n
（1）关键概念——状态空间

马尔可夫链是随机变量X1,X2,X3…Xn所组成的一个数列，每一个变量Xi 都有几种不同的可能取值，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。

! M" T# c* x" u（2）关键概念——转移概率(Transition Probability）
( B/ g) y& r7 {# T- r
马尔可夫链可以用条件概率模型来描述。我们把在前一时刻某取值下当前时刻取值的条件概率称作转移概率。


; ~! X- y: ]0 k% a- v% f
上面是一个条件概率，表示在前一个状态为s的条件下，当前状态为t的概率是多少。

( @9 O1 b; t; C& j5 Y$ }（3）关键概念——转移概率矩阵

  w: ?# j4 l  N$ N. T" i; [7 W很明显，由于在每一个不同的时刻状态不止一种，所以由前一个时刻的状态转移到当前的某一个状态有几种情况，那么所有的条件概率会组成一个矩阵，这个矩阵就称之为“转移概率矩阵”。比如每一个时刻的状态有n中，前一时刻的每一种状态都有可能转移到当前时刻的任意一种状态，所以一共有n*n种情况，组织成一个矩阵形式如下：
( c; K1 n3 t" n; K* W- v0 h
: \; w3 l1 v9 z0 s# R3 |

7 P0 C- t! a1 b6 R1.4 马尔可夫模型的应用

3 P2 [# {, ~* G  ^) E) }# s2 p( p      马尔可夫模型（Markov Model）是一种统计模型，广泛应用在语音识别，词性自动标注，音字转换，概率文法、序列分类等各个自然语言处理等应用领域。经过长期发展，尤其是在语音识别中的成功应用，使它成为一种通用的统计工具。到目前为止，它一直被认为是实现快速精确的语音识别系统的最成功的方法之一。
0 g4 z; u- Y- j% N3 K
& R5 I% P- I( @4 |* b二、马尔科夫模型的案例之一——天气预报
下面是一个马尔科夫模型在天气预测方面的简单例子。如果第一天是雨天，第二天还是雨天的概率是0.8，是晴天的概率是0.2；如果第一天是晴天，第二天还是晴天的概率是0.6，是雨天的概率是0.4。问：如果第一天下雨了，第二天仍然是雨天的概率是多少？，第十天是晴天的概率是多少？；经过很长一段时间后雨天、晴天的概率分别是多少？
# v* U* _3 M- V) o
首先构建转移概率矩阵，由于这里每一天的状态就是晴天或者是下雨两种情况，所以矩阵是2x2的，如下：


注意：每列和为1，分别对雨天、晴天，这样构建出来的就是转移概率矩阵了。如下：
6 `4 @5 E6 m7 Q$ l1 v3 s- i& H% W
8 o  k9 q9 `6 a) _2 |2 R$ F7 i

假设初始状态第一天是雨天，我们记为
& t; ]4 c) t9 C& G! m
$ K3 H  U3 q8 C5 {4 S

这里【1，0】分别对于雨天，晴天。
. Y5 @7 G/ C2 ^1 N/ C
初始条件：第一天是雨天，第二天仍然是雨天（记为P1）的概率为：
+ ^& \$ j( v! X# N$ y: r
P1 = AxP0

8 P! Y. s  x7 Y* G3 l7 w得到P1 = 【0.8,0.2】，正好满足雨天~雨天概率为0.8，当然这根据所给条件就是这样。

下面计算第十天（记为P9）是晴天概率：
) ~- j+ t& h* g5 |0 G, I

# w% N: N1 h. c8 F3 ~
得到，第十天为雨天概率为0.6668，为晴天的概率为0.3332。
# k4 B. h/ ]6 j  Q
8 T; U' R( p1 C  p& n  Z/ O下面计算经过很长一段时间后雨天、晴天的概率，显然就是下面的递推公式了：
( x: k* y2 j2 E* q$ A2 d" R

) J. [  w$ o) W3 }
$ x/ v& V* L" J! x9 u& n" R- E2.2 递推公式的改进
) z( r5 K$ C4 o9 t
7 ?0 I6 y5 a6 T- ?3 ~' F5 v) ?虽然上面构造了一个递推公式，但是直接计算矩阵A的n次方是很难计算的，我们将A进行特征分解（谱分解）一下，得到：


8 S: \/ C* n+ w2 h  |  q0 Y
6 \8 p& o" }; ~' `' Y' @
$ I/ l+ n7 L$ G% J8 p
" u; t9 c  V) |/ y: J8 q: Z$ G现在递推公式变成了下面的样子：
0 s/ @+ P# D0 |8 o3 t6 c




显然，当n趋于无穷即很长一段时间以后，Pn = 【0.67，0.33】。即雨天概率为0.67，晴天概率为0.33。并且，我们发现：初始状态如果是P0 =【0，1】，最后结果仍然是Pn = 【0.67，0.33】。这表明，马尔科夫过程与初始状态无关，跟转移矩阵有关。


* `, k/ D, y8 R7 A! D, t5 F! |6 S
4 F$ w; A, B! ~4 h& o三、再看一个例子——DAN的CPG岛
5 K0 W6 H; M8 z% x为什么还要看这个例子，因为在上面的天气预报我们是直接给出了概率转移矩阵，但是在实际应用中这个概率转移事先是不知道的，那该怎么办呢？需要自己去做统计才能得到。
7 }( ~% o5 u$ j* n) @5 U/ L
& {0 r+ G4 P$ x+ L) L问题描述：基因组上CpG相对富集的区域被称作CpG岛，接下来我们要从给定的一定DNA序列，判断它是否来自CpG岛，这属于一个两分类问题。——这属于一个序列分类问题。
$ o9 q$ F8 ]7 B* E
DNA序列每个位置上的核苷酸都可以被当作一个有四种可能取值的离散随机变量x={A,T,G,C} 。
; N0 Y! q; K3 q9 H/ h8 n, L在上述问题中我们要考虑连续位置上出现的CpG双核苷酸，可以用马尔科夫模型来表示这种相邻位置之间的依赖关系。如果第
5 M) c4 V/ O; V
i 时刻上的取值依赖于且仅依赖于第i−1时刻的取值，即
) A" b$ ^. k+ B- Q! O! V/ O
* \0 G( M% P6 ^5 {

1 w1 L" F" t: y/ t  ~5 @. s, r则我们把这个串称作一个一阶马尔科夫链（模型）。

3 c2 d, T0 N. K" g
对于DNA序列来说，每一位置的取值有四种，我们把它们称作四种状态，转移概率就是一个4∗4 的矩阵，称作转移概率矩阵或状态转移矩阵，如下图。

* z; c9 A- f/ d6 [6 n2 @

: U! k: }7 Q: p+ S7 i8 ?如果知道两类（CpG岛与非CpG岛）的状态转移矩阵，那么对于一个序列样本，我们就可以用上述公式分别计算每一类模型下观察到该特定序列的可能性或似然度 ，用同样的类别似然比（或对数似然比）来进行类别判断。

3.1 关键问题——状态转移矩阵的确定
$ `5 ]$ g& I& L& L
那么怎样去确定马尔科夫状态转移矩阵（离散概率模型）呢？
: k$ k9 _4 S% ]- _- y8 M
首先收集充分的、有代表性的一些CpG岛序列的片段和一些非CpG岛序列的片段，用它们构成两类训练样本。在每一类样本中，统计在所有位置上出现A、T、C、G的次数，再统计在每个A、T、C、G后面出现A、T、C、G次数，然后用下面两个公式来统计概率：
5 b4 x% g. J2 ?7 W& D


- w0 j; u* I" u" a5 G

+ B1 ~# X$ q- j! a
2 w! y$ s) E; m  C  |, B
加号表示的是正样本，减号表示的是负样本。得到如下的转移矩阵：
5 T/ P' z4 |* ]) l
2 _, @, ~. L/ ^( Z# z
/ w/ H) W; E7 \7 x3 J
- y+ ^! i2 K5 Y) g. \2 M+ J对于任意一段待判别的DNA序列，可以根据状态转移矩阵计算它属于CpG岛的似然比，再通过与一定的阈值比较进行判别。大于阈值的为正样本，否则为负样本，计算过程就与上面类似了，建立递推关系。
* W% i( U2 U; P) H
) c* p  {. \1 w0 v& p  d# E- q* W$ f

! G. y3 X; o  ]* h" L四、马尔科夫模型与时间序列的关系与区别
乍一看，马尔科夫模型与时间序列是有一定的关系，有时候甚至有人说马尔科夫过程的状态序列就是一个时间序列，的确，从时间的推移角度来说，这么说好像没很么问题，但是它们之间还是有很多区别的，个人总结以下几点：
5 P$ X) b. W8 ^( n
7 ~( G' J& Z* c3 K; A8 n) [3 Q（1）马尔科夫模型是概率模型。每一个时间点的观测值体现为状态值，所谓状态值就是某一个类别的概率，这跟时间序列显然不一样；
  K  S+ e6 l' A6 K; z. j
（2）马尔科夫模型当前状态与之前状态的关系是通过转移概率、转移概率矩阵来决定的，这也是和时间序列不一样的地方。
3 l% m7 V6 G* o————————————————
8 b+ M# B7 s$ H0 s版权声明：本文为CSDN博主「LoveMIss-Y」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_27825451/article/details/100117715
: p( C8 b$ O9 Z/ v

- K% A  V" l' N* K4 r8 Z3 [