机器学习:马尔可夫模型

后续遇到合适的案例会再补充

1 马尔可夫模型

  马尔可夫模型(Markov Model, MM)是一种统计模型,广泛应用在自然语言处理等领域中。

1.1 数学定义

  考虑一组随机变量序列 X = { X 0 , X 1 , … , X t , …   } X={X_{0},X_{1},dots,X_{t},dots} X={X0,X1,,Xt,},其中 X t X_{t} Xt表示时刻 t t t的随机变量,并且每个随机变量 X t X_{t} Xt的取值集合相同,称为状态空间 S S S S S S可以是离散的,也可以是连续的。
  假设在时刻 0 0 0的随机变量 X 0 X_{0} X0遵循概率分布 P ( X 0 ) = π ( 0 ) P(X_{0})=pi(0) P(X0)=π(0), 即为初始状态分布。若某个时刻 t ≥ 1 tge1 t1的随机变量 X t X_{t} Xt与前一个时刻的随机变量 X t − 1 X_{t-1} Xt1之间有条件分布 F ( X t ∣ X t − 1 ) F(X_{t}|X_{t-1}) F(XtXt1),并且 X t X_{t} Xt只依赖于 X t − 1 X_{t-1} Xt1,而不依赖于过去的随机变量 ( X 0 , X 1 , … , X t − 2 ) (X_{0},X_{1},dots,X_{t-2}) (X0,X1,,Xt2),则 X X X具有马尔可夫性质,称为马尔科夫链。即 P ( X t ∣ X 0 , X 1 , … , X t − 1 ) = P ( X t ∣ X t − 1 ) , t = 1 , 2 , … P(X_{t}|X_{0},X_{1},dots,X_{t-1})=P(X_{t}|X_{t-1}),t=1,2,dots P(XtX0,X1,,Xt1)=P(XtXt1),t=1,2,其中, P ( X t ∣ X t − 1 ) P(X_{t}|X_{t-1}) P(XtXt1)称为马尔科夫链的转移概率分布。
  另外,若条件转移概率分布与时间 t t t无关,则称为时间齐次的马尔可夫链。即 P ( X t + s ∣ X t + s − 1 ) = P ( X t ∣ X t + 1 ) P(X_{t+s}|X_{t+s-1})=P(X_{t}|X_{t+1}) P(Xt+sXt+s1)=P(XtXt+1)  若某个时刻 t ≥ 1 tge1 t1的随机变量 X t X_{t} Xt与前 n n n个状态相关,则称为 n n n阶马尔可夫链。即 P ( X t ∣ X 0 … X t − 1 ) = P ( X t ∣ X t − n X t − n + 1 … X t − 1 ) P(X_{t}|X_{0}dots X_{t-1})=P(X_{t}|X_{t-n}X_{t-n+1}dots X_{t-1}) P(XtX0Xt1)=P(XtXtnXtn+1Xt1)

  除了马尔可夫性外,马尔可夫链还可能具有不可约性、常返性、周期性和遍历性。

1.2 两种马尔可夫链
1.2.1 离散马尔可夫链

  如果上述随机变量 X t ( t = 0 , 1 , 2 , … , ) X_{t}(t=0,1,2,dots,) Xt(t=0,1,2,,)是定义在离散空间 S S S中,则称为离散马尔可夫链,其转移概率分布可以用矩阵表示。若 S = { 1 , 2 , … , n } S={1,2,dots,n} S={1,2,,n}则转移概率分布矩阵为: P = [ p 11 p 12 … p 1 n p 21 p 22 … p 2 n ⋮ ⋮ ⋯ ⋮ p n 1 p n 2 … p n n ] (1) P=begin{bmatrix} p_{11} & p_{12} & dots & p_{1n} \ p_{21} & p_{22} & dots & p_{2n} \ vdots & vdots & cdots & vdots \ p_{n1} & p_{n2} & dots & p_{nn} end{bmatrix} tag{1} P= p11p21pn1p12p22pn2p1np2npnn (1)其中 p i j = P ( X t = i ∣ X t − 1 = j ) p_{ij}=P(X_{t}=i|X_{t-1}=j) pij=P(Xt=iXt1=j)为马尔可夫链在 t − 1 t-1 t1时刻从状态 j j j转移到时刻 t t t的状态 i i i的概率。 p i j ≥ 0 p_{ij} ge 0 pij0 ∑ i p i j = 1 sum_{i}p_{ij}=1 ipij=1
  马尔可夫链在任意时刻 t t t的状态分布,可以由在时刻 t − 1 t-1 t1的状态分布及转移概率分布决定,即 π ( t ) = P π ( t − 1 ) = P ⋅ P π ( t − 2 ) pi(t)=Ppi(t-1)=Pcdot Ppi(t-2) π(t)=Pπ(t1)=PPπ(t2)。依次类推 π ( t ) = P t π ( 0 ) pi(t)=P^{t}pi(0) π(t)=Ptπ(0)

1.2.2 连续马尔可夫链

  如果状态空间 S S S定义在连续空间,则序列 X X X称为连续马尔可夫链。则转移概率分布由概率转移核函数来表示。对任意的 x ∈ S , A ∈ S ) xin S, Ain S) xS,AS), 转移概率 P ( x , A ) = ∫ A p ( x , y ) d y P(x,A)=int_{A} p(x,y)dy P(x,A)=Ap(x,y)dy

参考资料

  1. 《统计学习方法》