机器学习：马尔可夫模型
后续遇到合适的案例会再补充
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
t≥1的随机变量
X
t
X_{t}
Xt与前一个时刻的随机变量
X
t
−
1
X_{t-1}
Xt−1之间有条件分布
F
(
X
t
∣
X
t
−
1
)
F(X_{t}|X_{t-1})
F(Xt∣Xt−1)，并且
X
t
X_{t}
Xt只依赖于
X
t
−
1
X_{t-1}
Xt−1，而不依赖于过去的随机变量
(
X
0
,
X
1
,
…
,
X
t
−
2
)
(X_{0},X_{1},dots,X_{t-2})
(X0,X1,…,Xt−2)，则
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(Xt∣X0,X1,…,Xt−1)=P(Xt∣Xt−1),t=1,2,…其中，
P
(
X
t
∣
X
t
−
1
)
P(X_{t}|X_{t-1})
P(Xt∣Xt−1)称为马尔科夫链的转移概率分布。
另外，若条件转移概率分布与时间
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+s∣Xt+s−1)=P(Xt∣Xt+1) 若某个时刻
t
≥
1
tge1
t≥1的随机变量
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(Xt∣X0…Xt−1)=P(Xt∣Xt−nXt−n+1…Xt−1)
除了马尔可夫性外，马尔可夫链还可能具有不可约性、常返性、周期性和遍历性。
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=
p11p21⋮pn1p12p22⋮pn2……⋯…p1np2n⋮pnn
(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=i∣Xt−1=j)为马尔可夫链在
t
−
1
t-1
t−1时刻从状态
j
j
j转移到时刻
t
t
t的状态
i
i
i的概率。
p
i
j
≥
0
p_{ij} ge 0
pij≥0且
∑
i
p
i
j
=
1
sum_{i}p_{ij}=1
∑ipij=1。
马尔可夫链在任意时刻
t
t
t的状态分布，可以由在时刻
t
−
1
t-1
t−1的状态分布及转移概率分布决定，即
π
(
t
)
=
P
π
(
t
−
1
)
=
P
⋅
P
π
(
t
−
2
)
pi(t)=Ppi(t-1)=Pcdot Ppi(t-2)
π(t)=Pπ(t−1)=P⋅Pπ(t−2)。依次类推
π
(
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) x∈S,A∈S), 转移概率 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
参考资料
- 《统计学习方法》