机器学习 - 隐马尔科夫模型(Hidden Markov Model)

---

1. 马尔可夫模型

下面介绍几个马尔可夫模型中的重要概念：

1.1 一阶马尔可夫假设 (first order Markov assumption)

n时刻的观测值只依赖于n-1时刻的观测值，即：
p(x_n|x_{n-1},x_{n-2},...x_0) = p(x_n|x_{n-1})

1.2 转移概率

a_{i,j} = p(x_n = S_j|x_{n-1} = S_i)

1.3 时不变性

2.隐马尔科夫模型

2.1 引入问题

假设有一个人被锁在房间里待了很多天，但是他想知道外面的天气是什么。他猜测天气的唯一途径就是看每天来照顾他的人有没有带伞。
这样，观测状态(observed state)就是{带伞，不带伞}; 隐藏状态(hidden state)就是{晴，雨}。

2.2 图像化表示

绿色圆圈是hidden state, 这是一个马尔可夫模型；
紫色圆圈是observed state, 只由对应的hidden state决定

2.3 形式化表示

• \{S_1,S_2,...S_N\}表示hidden states的状态
• \{K_1,K_2,...K_N\}表示observation的状态
• \Pi=\{\pi_i\}是初始状态的概率
• A=\{a_{i,j}\}是transition probability a_{i,j}=p(x_n=j |x_{n-1}=i)
• B=\{b_{i,j}\}是observation state probability b_{i,j}=p(y_n=K_j|x_n=S_i)

2.4 HMM 能解决的问题

HMM的初始化模型\mu = \{A,B,\Pi\} , 观测序列为\sigma = \{O_1, O_2,...O_N\}

• 问题一(estimation problem)：计算某个观测序列出现的概率
• 问题二(decoding problem)：已知观测序列，求最有可能的hidden state

2.4.1 问题1(estimation problem)

2.4.1.1 Solution1

使用全概率公式，按照hidden states 拆分：
P(O|\mu) = \sum _{X} P(O,X|\mu)
其中，P(O,X|\mu) = P(X|\mu)P(O | X, \mu)

故：P(O|\mu) = \sum _{X} P(X|\mu) P(O|X,\mu)~~~~(1)

其中，
P(X|\mu) = \pi_{x_1}a_{x_1x_2}a_{x_2x_3}...a_{x_{T-1}x_T}

这是因为P(X|\mu)表示：在HMM 模型的初始条件下，hidden state为X的概率。

还有：
P(O|X,\mu) = b_{x_1o_1}b_{x_2o_2}...b_{x_To_T}

这是因为P(O|X,\mu)表示：在HMM模型的初始条件下，以及hidden states的条件下，观测值为O的概率。由于观测值只和hidden state有关，这里的 \mu 并没有作用。

这个算法的复杂度为 O(2TN^T), 其中T为序列长度，N为状态个数。

2.4.1.2 前向算法 (Forward Algorithm)

上面这种做法的明显不足就是复杂度太高了！前向算法通过动态规划来降低复杂度。

【算法1】前向算法

定义\alpha_t(i) = p(o_1,...o_t,x_t=i|\mu),则 P(O| \mu)= \sum _{i=1}^N \alpha_T(i)

又有：
\alpha_{t+1}(j)=p(o_1,...o_{t+1},x_{t+1}=j|\mu) \\ =\sum _{i=1}^Np(o_1,...o_{t+1},x_{t+1}=j,x_t=i|\mu) ~~~①\\ =\sum _{i=1}^Np(o_1,...o_{t+1},x_{t+1}=j|x_t=i,\mu)p(x_t=i|\mu)~~~~② \\ = \sum _{i=1}^Np(o_1,...o_{t}|x_t=i,\mu)p(o_{t+1},x_{t+1}=j|x_t=i,\mu)p(x_t=i|\mu)③ \\ =\sum _{i=1}^Np(o_1,...o_{t},x_t=i|\mu)p(o_{t+1},x_{t+1}=j|x_t=i,\mu)~~~④ \\ =\sum _{i=1}^Np(o_1,...o_{t},x_t=i|\mu)p(x_{t+1}=j|x_t=i,\mu)p(o_{t+1}|x_{t+1}=j)~~~⑤ \\ = \sum_{i=1}^N \alpha_t(i)a_{ij}b_{j o_{t+1}}
②->③:独立性假设
③->④: 第一项第三项合并
④->⑤: 第二项拆分

这样，有\alpha_{t+1}(j) = \sum_{i=1}^N \alpha_t(i)a_{ij}b_{j o_{t+1}},又有 P(O| \mu)= \sum _{i=1}^N \alpha_T(i),于是复杂度为 O(N^2T)

2.4.2 问题二(decoding problem)

解码问题就是，已知observed state, 求最有可能的hidden state,即
\argmax_{X} P(X|O)

【算法2】viterbi 算法
令 \delta_t(j)= \max _{x_1,...x_{t-1}}p(x_1,...,x_{t-1},x_t=j,o_1,...o_t)
它代表了一个最大概率，如下图所示：
求 \argmax_{X} P(X|O)等价于求\argmax_{X} P(X,O) 等价于求\argmax_{j} \delta_T(j)
递推公式：
\delta_{t+1}(j) = \max_j \delta_t(i)a_{ij}b_{j o_{t+1}}
意思是，每个时刻的前一个时刻一定是概率最大的，在当前时刻也应该选择一个使概率最大的隐藏状态j。这样一步步把使得概率最大的隐藏状态记录下来，就是最后的结果。

2.5 HMM的应用

• 语音识别

• \bigstar 汉语拼音转汉字
  (我大二的时候居然还写过这个，我可真厉害！要好好回忆一下细节…)

• POS (part of speech) tagging

​​
​​​​​​