序列标注1 HMM
shuaihhx
序列标注是NLP处理中比较常见的需求，分词、词性标注、命名实体识别甚至句法依存分析等都可以转化为序列标注问题，在此领域常用的方法如HMM、最大熵、CRF、深度学习等。其中HMM应该是比较基本，理解上也最为容易的方法，下面记录下自己在这方面的学习。(学习demo)
概念
关于其原始定义，这里就不做考究了。
- 马尔科夫链是一组具有马尔科夫性质的随机状态转移。比如把天气看作具有马尔可夫性，状态空间为{晴天，阴天，雨天}，假如我们记录一年之内每天的天气，则可以做出3X3的转移概率矩阵$a_{i,j}=P_{x->y}(x状态转移到y状态)$。
- 而隐马尔科夫模型则是在此基础上加入了隐含状态，比如将天气看作隐状态，则可以在此基础上加入观测信息，比如有没有星星，是否刮风，温度信息等，构成一个联合模型。此时除状态转移概率矩阵外，还加入了3Xn的观测概率矩阵（有的叫发射概率矩阵）,其中n是观测信息的个数。
参数信息
由上，一个HMM模型，主要有三个参量，即
- 转移矩阵 A
- 发射矩阵 B
- 初始分布（即链开始的状态） $\pi$
即HMM模型 $\lambda=(A,B,\pi)$
建模
对HMM的使用，主要就是对状态和观测的认识，即把所需问题抽象为状态和观测的集合，然后进行建模。以分词为例，可以将分词结果看作状态（一般表示为BMES）,将字序列看作观测。
在给定语料（有标注的分词文档）的前提下，可以通过遍历语料进行统计记录，计算出$A、B、\pi$。
HMM任务
计算概率
即已知模型与观测序列，求观测序列的概率。
对该任务，最直观的解决是列出所有可能的状态序列，在每个序列上计算观测概率，最后加和。但状态序列共有$m^l$个，其中m是状态数，l是序列长度，复杂度过高。
- 因此采用动态规划的思路，使用前向/后向算法，计算量由$m^l$变为$m\times l$
- 前向算法比较直观，容易理解。后向算法需要稍微抛弃一下直观再去理解。（因为HMM本身就是有向图模型，前向计算符合直观感觉）
预测任务
预测任务及在给定HMM模型的基础上，给一句话，给出分词结果。HMM是生成模型，计算分词结果也就是计算状态与观测的联合概率最大：$$P=initProb\times emitProb(i=0)\prod_{i=1}^ntransProb(i-1,i)\times emitProb(i)$$ 同样可以穷举所有状态序列，看哪个概率最大，复杂度高。
- 同样动态规划，使用viterbi解码。beam-search 是一种简化的viterbi算法。
学习问题
即已知观测序列，估计模型参数。使用Baum-Welch算法（EM算法） 。
具体应用场景我还没用过，但该部分在序列标注中一般不用。比较容易理解，这相当于给你一堆句子（未分词的），然后要学习一个模型出来，能够对句子进行分词。能学出来吗？一般来说，模型是能学出来的，但是分词结果基本无法预估。这我觉得有点类似于LDA，分出来了吗？分出来了。但无法预料是从哪个维度分的。