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

隐马尔可夫模型（hidden Markov model）是可以用于标注问题的统计学习模型，描述由隐藏的马尔可夫链生成观测序列的过程，属于生成模型。
马尔可夫模型具有三个参数，状态集合（状态转移概率矩阵），观测集合（观测概率矩阵），初始状态概率向量。

文章图片

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

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

三个基本问题

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

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

文章图片

文章图片

同样后向算法，是给定了后向概率，即t时刻的状态和之后观测值。
学习算法
监督学习算法：知道观测还知道每个观测对应的状态

文章图片

文章图片

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

文章图片

文章图片
其中需要带入

文章图片

文章图片

预测问题
近似算法计算出每个时刻的最大的概率的状态，作为实际状态。

文章图片

存在的问题是，每次都是孤立的考虑，没有考虑前后状态的影响。不是全局最优的。
维特比算法目标是全局最优 a r g m a x P ( I ∣ O , λ ) argmaxP(I|O,\lambda) argmaxP(I∣O,λ)。采用了动态规划的思想，每次只需要考虑前一个状态就可以。

文章图片

文章图片

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