马尔科夫链和隐马模型HMM
- 1. Markov chain
- 2. 计算
- 3. Hidden Markov Model
- 4. 两个假设
- 5. 问题1：evaluation
- 6. Forward 算法
- 7. 问题2：Decoding
- 8. Viterbi算法
- 9. 问题3：Learning
- 10. 期望最大化算法Expectation Maximization
1. Markov chain
马尔可夫链是描述从一种状态到另一种状态的转换序列的模型，其中每种状态的概率仅取决于前一种状态
假设：
任何具体状态的概率只取决于之前的状态（不取决于更早的历史）。
2. 计算
前三天分别是 Sunny, cloudy, sunny, 第二天是sunny的概率是？
P[tomorrow=Sunny | S, C, S ] = P[tomorrow = Sunny | today = Sunny] = 0.8
表格可以用图表示，箭头指向下一个状态。 
加入初始状态概率的计算
P的|后面是前一个状态
P(Sunny, sunny, cloudy, rainy)
= P(sunny)(sunny|sunnny)(cloudy|sunny)(rainy|cloudy)
= 0.1 * 0.8 * 0.1 *0.2 = 0.0016
3. Hidden Markov Model
马尔可夫模型在需要计算可直接观测状态的概率时很有用。
隐马尔可夫模型用于我们无法直接观察状态（它们是隐藏的），但我们可以根据间接信息对其进行判断的情况。
什么是隐藏的？天气
你能看到什么？衬衫夹克、连帽衫
λ = (π, A, A0)
π 是N个可能的隐藏状态
A是每个状态转换的概率矩阵
A0是每个状态的初始概率
4. 两个假设
- 齐次性假设: 即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于它在前一时刻的状态, 与其他时刻的状态和观测无关, 也与时刻t本身无关
- 观测独立性假设: 即假设任意时刻的观测值只依赖于该时刻的马尔可夫链的状态, 与其他观测及状态无关
5. 问题1：evaluation
给定一个λ = (π, A, A0)HMM模型和一个观测序列X = x1, x2, x3, …计算序列出现概率。
计算 X = shirt, Hoodie的概率
A中的每个概率都要计算X=shirt，Hoodie的概率
在9种组合里先计算Rainy,Cloudy
P(X, {Rainy, Cloudy})
- 初始状态是Rainy = 0.6
- 从Rainy 到 Cloudy = 0.3
- 观测概率
- 在Rainy的时候，Shirt的概率是0.8
- 在Cloudy的时候，Hoodie的概率是0.1
结果为0.6 * 0.3* 0.8*0.1 = 0.0144
计算9种组合相加，得到最终概率。
计算的复杂度为2TN^T。T是时间步长，N是状态个数
6. Forward 算法
直接案例理解
- 初始化：计算在t=1的时候，每个状态的前向概率
f k ( 1 ) = A 0 ( k ) e k ( x 1 ) f_k(1) = A_0(k)e_k(x_1) fk(1)=A0(k)ek(x1)
f r a i n y ( 1 ) = A 0 ( r a i n y ) e r a i n y ( S h i r t ) = 0.6 ∗ 0.8 f_{rainy}(1) = A_0(rainy)e_{rainy}(Shirt)= 0.6 * 0.8 frainy(1)=A0(rainy)erainy(Shirt)=0.6∗0.8
可以得到cloud和sunny的f（1）为0.15和0.001 - 迭代
f k ( i ) = e k ( x i ) ∑ j f j ( i − 1 ) a j k f_k(i) = e_k(x_i)\sum_j f_j(i-1)a_{jk} fk(i)=ek(xi)j∑fj(i−1)ajk
f r a i n y ( 2 ) = e r a i n y ( H o o d i e ) ( f r a i n y ( 1 ) a ( r a i n y , r a i n y ) + f c l o u d y ( 1 ) a ( c l o u d y , r a i n y ) + f s u n n y ( 1 ) a ( s u n n y , r a i n y ) ) = 0.01 ∗ ( 0.48 ∗ 0.6 + 0.15 ∗ 0.4 + 0.001 ∗ 0.1 ) = 0.0035 f_{rainy}(2) = e_{rainy}(Hoodie)(f_{rainy}(1)a(rainy,rainy)+f_{cloudy}(1)a(cloudy,rainy)+f_{sunny}(1)a(sunny,rainy)) = 0.01*(0.48*0.6+0.15*0.4+0.001*0.1) = 0.0035 frainy(2)=erainy(Hoodie)(frainy(1)a(rainy,rainy)+fcloudy(1)a(cloudy,rainy)+fsunny(1)a(sunny,rainy))=0.01∗(0.48∗0.6+0.15∗0.4+0.001∗0.1)=0.0035
3.最后一个步长就等于最后的所有f_k(i)相加，这里是f(2)的和，三个状态，就是cloud,sunny,rainy,各自一个f(2)
7. 问题2：Decoding
问题1是：给定一个λ = (π, A, A0)HMM模型和一个观测序列X = x1, x2, x3, …计算序列出现概率。
问题2是：给定一个λ = (π, A, A0)HMM模型和一个观测序列X = x1, x2, x3, …计算最可能的隐藏序列
8. Viterbi算法
- 初始化
计算每个状态的Viterbi分数
V k ( 1 ) = A 0 ( k ) e k ( x 1 ) V_k(1) = A_0(k)e_k(x_1) Vk(1)=A0(k)ek(x1)
V
r
a
i
n
y
(
1
)
=
A
0
(
R
a
i
n
y
)
e
R
a
i
n
y
(
S
h
i
r
t
)
=
0.6
∗
0.8
=
0.48
V_{rainy}(1) = A_0(Rainy)e_{Rainy}(Shirt) = 0.6 *0.8 = 0.48
Vrainy(1)=A0(Rainy)eRainy(Shirt)=0.6∗0.8=0.48
同理得到cloud和sunny的v1为0.15，0.001
2.迭代
计算状态k在时间i的vierbi得分
V
k
(
i
)
=
e
k
(
x
i
)
m
a
x
j
V
j
(
i
−
1
)
a
j
k
V_k(i) = e_k(x_i)max_jV_j(i-1)a_{jk}
Vk(i)=ek(xi)maxjVj(i−1)ajk
记录回溯路径
P
t
r
k
(
i
)
=
a
r
g
m
a
x
j
V
j
(
i
−
1
)
a
j
k
Ptr_k(i) = argmax_jV_j(i-1)a_{jk}
Ptrk(i)=argmaxjVj(i−1)ajk
V
r
a
i
n
y
(
2
)
=
e
r
a
i
n
y
(
H
o
o
d
i
e
)
∗
m
a
x
(
V
r
a
i
n
y
(
1
)
a
r
a
i
n
y
,
r
a
i
n
y
,
V
c
l
o
u
d
y
(
1
)
a
c
l
o
u
d
y
,
r
a
i
n
y
,
V
s
u
n
n
y
(
1
)
a
s
u
n
n
y
,
r
a
i
n
y
)
=
0.01
∗
m
a
x
(
0.48
∗
0.6
,
0.15
∗
0.4
,
0.001
∗
0.1
)
=
0.0029
V_{rainy}(2) = e_{rainy}(Hoodie) * max(V_{rainy}(1)a_{rainy,rainy}, V_{cloudy}(1)a_{cloudy,rainy},V_{sunny}(1)a_{sunny, rainy}) = 0.01 * max(0.48*0.6, 0.15*0.4, 0.001*0.1) = 0.0029
Vrainy(2)=erainy(Hoodie)∗max(Vrainy(1)arainy,rainy,Vcloudy(1)acloudy,rainy,Vsunny(1)asunny,rainy)=0.01∗max(0.48∗0.6,0.15∗0.4,0.001∗0.1)=0.0029
Ptr的最大索引是rainy，1（假设）
3.终止
Ptr2是rainy
Ptr3 = argmax(V_k(2))，最大是Sunny
所以最终答案是Rainy，sunny
9. 问题3：Learning
问题1是：给定一个λ = (π, A, A0)HMM模型和一个观测序列X = x1, x2, x3, …计算序列出现概率。
问题2是：给定一个λ = (π, A, A0)HMM模型和一个观测序列X = x1, x2, x3, …计算最可能的隐藏序列
问题3是：给定一个一个观测序列X = x1, x2, x3, …找到λ = (π, A, A0)HMM模型
10. 期望最大化算法Expectation Maximization
- λ = (π, A, A0) 随机初始化
- 计算每个状态下的概率分布
- 利用2中的概率更新λ = (π, A, A0)，使得给定预测数据的似然函数最大化，涉及预测最可能序列并于实际观测序列进行比较
- 如果模型更新后，p(x|λ)增加，就回第二步继续迭代，否则停止
