【统计学习算法】隐马尔可夫模型HMM

隐马尔可夫模型（hidden Markov model）

是可以用于标注问题的统计学习模型，描述由隐藏的马尔可夫链生成观测序列的过程，属于生成模型。

马尔可夫模型

具有三个参数，状态集合（状态转移概率矩阵），观测集合（观测概率矩阵），初始状态概率向量。

这三个参数：
$\lambda:N$λ:N个参数
$A:N*N$A:N∗N 对应状态的转移
$B:N*M$B:N∗M 对应每种状态可能的观测值

• 基本假设：齐次性，观测独立性

三个基本问题

1. 概率计算问题：$P(O|\lambda)$P(O∣λ) 给定了一个参数，出现这种观测的概率是多少
2. 学习问题：$argmax_{\lambda}P(\lambda|O)$argmaxλ​P(λ∣O) 给了一个观测值，寻找参数。采用极大似然估计
3. 预测问题：$argmax_{I}P(I|O)$argmaxI​P(I∣O) 给了观测变量，推断隐变量，也就是状态。让计算机去标注词性

概率计算问题

直接计算的方法复杂度太高$O(TN^T)$O(TNT)
前向算法，给定了前向概率，即t时刻的状态和前面的观测序列。这种方法的复杂度是$O(TN^2)$O(TN2)

同样后向算法，是给定了后向概率，即t时刻的状态和之后观测值。

学习算法

监督学习算法：知道观测还知道每个观测对应的状态

非监督算法：BW算法（本质是EM算法）

其中需要带入

预测问题

近似算法

计算出每个时刻的最大的概率的状态，作为实际状态。

存在的问题是，每次都是孤立的考虑，没有考虑前后状态的影响。不是全局最优的。

维特比算法

目标是全局最优$argmaxP(I|O,\lambda)$argmaxP(I∣O,λ)。采用了动态规划的思想，每次只需要考虑前一个状态就可以。

算法中$\delta_t(i)$δt​(i)当前t时刻的状态是qi，且满足观测的最大概率（这个最大概率是说从前面转移来的最大概率/最优路径）。
$\psi_t(i)$ψt​(i)表示这个最优路径是从前一个的哪个状态传递得来的。最后进行回溯就可以得到最优的序列。