分词算法模型学习笔记(一)——HMM

Hidden Markov Model（HMM，隐马尔科夫模型）

主要参考资料：52nlp

1.HMM的特点

生成式模型

主要研究观察序列Ｘ和隐藏状态序列Y的联合概率分布P(X,Y)
通常为一阶马尔卡夫过程（即当前状态的概率分布只跟前一个状态有关）

HMM模型图示

2.HMM的三个基本用途

1.评估（比如语音识别）
计算某一观测序列Ｘ的出现概率

典型加速算法：前向算法、后向算法

２.解码（比如分词和词性标注）
对于某一观测序列X计算出使其出现概率最大的隐藏状态序列Y

典型加速算法：维特比算法

3.参数学习
基于EM算法的加速算法：前向-后向算法（Baum-Welch算法）

3.前向算法

计算目标：

如果直接利用上面的式子进行编程计算，需要枚举ｙ的所有取值（假设隐藏状态数目为|S|，ｙ则有 |S|T个可能的取值），这种指数级的时间复杂度显然是行不通的。

下来我们考虑引入一个新的中间状态——通常称它为局部概率，从而避免大量不必要的计算（典型的动态规划策略）

这个局部概率的含义可以解释为在对于所有以ｔ时刻si结尾的隐藏状态跳转路径，它们产生观测序列x1⋅⋅⋅xt的概率值之和。

算法步骤（时间复杂度为O|S|2T)：

1. 定义局部概率的初始值（边界值）

1. 利用状态转移方程迭代计算当t=1,···,T-1时的局部概率值

1. 利用计算好了的局部概率值，得到我们的最终目标

具体图例（隐藏状态数|S|=3，序列总长度T=4，t=1）：

4.后向算法

后向算法的局部概率定义刚好跟前向算法恰好相反（值得注意的是前向算法使用的是联合概率，后向算法使用的是条件概率），但它们要解决的问题是一样的。

其含义可以解释为在对于所有以ｔ时刻si开头的隐藏状态跳转路径，它们产生观测序列xt+1⋅⋅⋅xT的概率值之和。

算法步骤（时间复杂度为O|S|2T)：

1. 定义局部概率的初始值（边界值）

1. 利用状态转移方程迭代计算当t=T-1,···,1时的局部概率值

1. 利用计算好了的局部概率值，得到我们的最终目标

具体图例（隐藏状态数|S|=3，序列总长度T=4，t=3）：

５.维特比算法

计算目标：

同样地，为了避免枚举所有可能取值的ｙ，需要采取动态规划策略，引入中间状态δt(x,si)=maxy1⋅⋅⋅yt−1P(x1,⋅⋅⋅,xt,y1,⋅⋅⋅,yt−1,Yt=si)
这个局部概率的含义可以解释为在所有以ｔ时刻si结尾的隐藏状态跳转路径中，产生观测序列x1⋅⋅⋅xt的最大概率值。
同时因为要求的是这个概率值最大的隐藏状态序列本身，而不是它的概率值，因此还需要一个回退指针变量ψ用于记录状态的转移情况。

算法步骤（时间复杂度为O|S|2T)：

1. 定义局部概率的初始值（边界值）

1. 利用状态转移方程迭代计算当t=1,···,T-1时的局部概率值

1. 利用计算好了的局部概率值，确定回退起点

1. 利用回退指针变量ψ，逐个确定目标序列(t = T-1,···,1)

具体图例（隐藏状态数|S|=3，序列总长度T=4）：

６.前向-后向算法

未完待续。。。