Model
HMM是一个序列到序列的模型，支持有监督和无监督两种学习方式，首先先介绍马尔科夫链。
Markov Chain
假设有$n$个状态：$s_1,s_2,…,s_n$，可以认为这是一个时序序列。一个问题是给定这$n$个状态，怎样预测第$n+1$个状态。马尔科夫链是基于以下假设:
下一个状态只与当前状态有关
即
状态很多时候并不能直接观测到，但是状态会有表现形式，第$n$个状态的观测值记为$o_n$,并且$o_n$只与$s_n$有关，即
Notation
- $S$: 状态的集合
- $A$: 状态转移概率矩阵，$a_{i,j}$表示状态$s_i$转移到$s_j$的概率
- $O$: 观测序列
- $s_i$: 第$i$个状态
- $o_i$: 第$i$个观测值
- $\pi_i$: 第$i$个状态的初始概率
- $B$: 状态到观测值的概率，$b_i(o_t)$表示在$s_i$观测到$o_t$的概率
Model
给定一个状态集合$S$和HMM的参数$\theta$(包括状态的初始概率，状态转移概率以及状态到观测值的概率),序列长度是$T$,那么可以计算给定一个状态序列得到给定观测序列的概率，也可以计算给定观测序列对应的状态序列的概率。分别对应两个序列的编码和解码过程。
HMM主要需要解决上述的解码、编码和训练三个问题，下面讨论这三个问题。
Likelyhood Calculation
一个很自然的想法是遍历所有可能的状态序列，给定一个状态序列$s_1,s_2,…,s_T$,观测到$o_1,o_2,..,o_T$的概率是
又由markov假设，
结合$(1)(2)$可以计算,
记一共有$N$个状态，那么这种方法的复杂度是 $O(N^TT)$。
优化方法则是采用DP，记$\alpha_t(i)$表示到$t$时刻并且该时刻状态是第$i$个状态产生前$t$时刻观测值的概率，即
所以有
所以此时有
采用DP后，事件复杂度是
Decode
给定观测序列，确定最大可能的状态序列，即
同样我们可以采用遍历的方法，但是显然复杂度很高，同样在解码上依然可以采用DP算法，只不过此时是产生观测序列中最大可能状态序列的概率，即
有
Train
对于有监督的学习，根据统计方法可以直接计算参数概率，主要考虑无监督的训练，即没有状态标注。
E step
对于无监督的HMM的训练，可以应用EM算法，隐变量是状态序列，此时一个序列是一个样本。记状态序列为$I$,观测序列为$O$,则EM算法中E步往计算$q(\theta,\theta^k)$,
结合$(3)(4)$，
注意到有以下约束条件:
$\tag{*}$式中$L$是观测值集合，$v_l$表示该集合中某种取值，该式对任意一个状态$i$都成立。
M step
对$(5)$式中3部分结合约束条件运用拉格朗日乘子法求导：
记3部分并构造$L1$,$L2$,$L3$,
由(6)，对$i=1,2,…,N$,令导数为0，并结合约束条件，有
所以
接下来更新状态转移概率。
由(7),固定任意一个$i$,令导数为0，并结合第二个约束条件有
结合，有
