用隐含马尔可夫模型和他的应用
对于序列标注问题，目前主流的方法是条件随机场和长短期记忆网络，而一些简单的任务如分词、词性标注和命名实体识别，应用隐马尔可夫模型能够快速同时高效地进行学习。
模型简介
HMM被认为是解决大多数NLP问题最为快速有效的问题。将语言模型与通信问题联系起来，通信的本质是编解码和传输的过程。一个典型的通信系统包括信息源、信道、接收者、信息、上下文和编码。通信中，如何根据接收端的观测信号o1,o2,o3,…来推测信号源发送的信息s1,s2,s3,…?当然是求条件概率了。
$$
s_1,s_2,s_3,…=ArgMax_{s_1,s_2,s_3,…}{P(s_1,s_2,s_3,…|o_1,o_2,o_3,…)}
$$
根据贝叶斯公式，上述公式也等价于
$$
\frac{P(o_1,o_2,o_3,…|s_1,s_2,s_3,…)\cdot{P(s_1,s_2,s_3,…)}}{P(o_1,o_2,o_3,…)}
$$
公式中，分母可以看做是常数，因此对于通信问题求状态信息概率的问题可以看作是求联合概率$P(o_1,o_2,o_3,…|s_1,s_2,s_3,…)\cdot{P(s_1,s_2,s_3,…)}$,HMM模型通过简化该模型来计算信号源的概率。
HMM模型基于马尔可夫假设和独立输出假设。
符合马尔可夫假设的随机过程称为马尔可夫过程，也称为马尔可夫链。即随机状态中各个状态的概率分布只和前一个状态有关，下图表示一个离散的马尔可夫过程。
其中，模型参数为转移概率，从一个状态转移到下一个状态的概率。随机选择初始状态后，运行一段时间T后，根据马尔可夫链的转移概率可以生成一个状态序列：$s_1,s_2,s_3,…,s_T$。或者可以根据已存在的状态序列，通过计算某一状态的出现次数与转到零一状态的次数之比来估计转移概率。
HMM模型是马尔可夫模型的扩展，每一时刻输出ot,且只与st相关，st是不可见的，只能通过观察ot来估计隐含状态st。
基于马尔可夫假设和独立输出假设，之前的联合概率可写作
$$
P(s_1,s_2,s_3,…,o_1,o_2,o_3,…)=\prod_tP(s_t|s_{t-1})\cdot{P(o_t|s_t)}
$$
其中，$P(s_t|s_{t-1}$称为转移概率，$P(o_t|s_t)$称为生成概率。
HMM模型参数为$<S,O,A,B,\Pi>$
- S表示模型状态，N是状态数量，$S={S_1,S_2,…,S_N}$
- O表示每个状态的观察值，M为所有可能观察值的数量，$O={O_1,O_2,…,O_M}$
- $A={a_{ij}}\in{R^{N*N}}$表示状态转移概率矩阵
- $B={b_j(k)}\in{R^{N*M}}$表示生成概率矩阵
- $\Pi\in{R^N}$表示初始状态概率
由此，通过$\Pi$和A可以生成隐含状态序列，然后由每一时刻的生成概率B可以产生观察序列。设模型参数为$\lambda$,模型给定时，有
$$
P(s|\lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}…a_{i_{T-1}i_T}
$$
$$
P(o|s,\lambda)=b_{i_1o_1}b_{i_2o_2}…b_{i_To_T}
$$
$$
P(o,s|\lambda)=\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}…a_{i_{T-1}}b_{i_To_T}
$$
围绕HMM模型有三个基本问题，不同的任务有不同的算法求解。
给定模型计算输出序列概率
暴力计算
列举出所有可能的状态序列，计算每个序列的联合概率$P(o,s|\lambda)$,然后全部相加，得到观测序列的概率$\sum_i{P(o,s|\lambda)}$。这样的计算方式时间复杂度高。
前向算法
引入前向变量$\alpha_t(i)$,表示在t时刻状态为i时，输出序列为$o_1,o_2,…,o_T$的概率。这样，$P(o)=\alpha_t(1)+\alpha_t(2)+…+\alpha_t(i)$.而t时刻的前向变量可以通过t-1时刻的前向变量计算得到，以此类推，初始化计算出第一次的前向变量时，通过迭代最终可以计算出观察序列的概率。
$$
\alpha_t(i+1)=(\sum_{i=1}^{N}{\alpha_t(i)})b_j{(o_{t+1})},1\leq{t}\leq{T-1}
$$
后向算法
跟前向算法差不多，引入了后向变量$\beta_t(i)$
给定模型和特定观察序列求概率最大的状态序列
维特比算法
可以将此类问题看作是动态规划，用维特比算法求解。
在状态序列中，每一时刻的状态都有N种取值，假设序列长度为T，则一共有$N^T$种可能的状态序列，长序列时很难使用暴力计算来求解最大概率的路径。
维特比算法认为概率最大的路径P经过序列上的任意时刻，从起始点到该时刻的这段路径一定也是到当前时刻的概率最大的路径，因此维特比从第一个时刻开始，依次考察路径的概率，计算得到的概率最大的路径经过的状态即是这一时刻的状态的取值。因此，每一步计算的复杂度都和相邻两个时刻$S_i$和$S_i+1$各自的节点数目$n_i$,$n_i+1$的乘积成正比，即$O(n_i\cdot{n_{i+1}})$.
估计模型参数
已知观察序列和对应的状态序列
观察序列和状态序列都已知的情况下，很好解决。利用样本中出现的各个取值的次数可以计算出大致的模型参数。
$$
P(o_t|s_t)\approx\frac{(o_t,s_t)}{(s_t)}
$$
$$
P(s_t|s_{t-1})\approx\frac{(s_t,s_{t-1})}{(s_{t-1})}
$$
已知观察序列
在已知观察序列未知状态序列的情况下，可以使用鲍姆韦尔奇算法求解，通过期望最大化（EM）算法进行迭代。
首先找到一组能够产生输出序列O的模型参数，根据模型参数计算当前概率最大的状态序列的可能值并作为标注数据，按照3.1的方式重新计算模型参数，再次寻找概率最大的状态序列，一直迭代，直至模型性能收敛。
hmmlearn
hmmlearn是用于学习HMM模型的python库，与scikit-learn的API相似，依赖于scikit-learn,NumPy,SciPy,matplotlib等库。在官方文档中详细描述了hmmlearn中API的使用和一些实例。
hmmlearn的安装和其他模块一样。pip install hmmlearn
hmmlearn实现了三种算法的HMM模型，如下：
| 类 | 说明 |
|---|---|
| hmm.GaussianHMM | 假设观察量呈高斯分布 |
| hmm.GMMHMM | 假设观察量呈高斯混合分布 |
| hmm.MultinomialHMM | 观察量离散分布 |
针对观测序列为连续量的情况，可以使用前两种类，假设观察量呈现高斯分布或高斯混合分布，模型不复杂时使用第一种就足够了。
构建HMM，产生样本
通过传递参数，可以构建HMM对象。
在MultionalHMM类中，主要参数如下
class hmmlearn.hmm.MultinomialHMM(n_components=1, startprob_prior=1.0, transmat_prior=1.0, algorithm='viterbi', random_state=None, n_iter=10, tol=0.01, verbose=False, params='ste', init_params='ste')
n_components: 状态数量N
algorithm: 可选’viterbi’或’map’
n_iter: 模型EM迭代的最大次数
tol: 收敛阈值，最大似然增益小于tol时停止EM迭代
verbose： verbose=True时打印每次迭代的收敛程度
params: 控制哪些参数需要在训练中更新，’ste’的组合，分别代表初始概率分布、转移矩阵和生成矩阵
init_params: 哪些参数需要初始化
MultinomialHMM类的属性
| attribute | describe |
|---|---|
| n_features | 模型观察量的数量 |
| monitor_ | 检验EM收敛的类 |
| transmat_ | 状态的转移概率矩阵 |
| startprob_ | 初始概率分布 |
| emissionprob_ | 生成概率矩阵 |
在GaussianHMM类中，主要参数如下：
class hmmlearn.hmm.GaussianHMM(n_components=1, covariance_type='diag', min_covar=0.001, startprob_prior=1.0, transmat_prior=1.0, means_prior=0, means_weight=0, covars_prior=0.01, covars_weight=1, algorithm='viterbi', random_state=None, n_iter=10, tol=0.01, verbose=False, params='stmc', init_params='stmc')
GaussianHMM类中，参数与离散HMM略有不同，
covariance_type : 用于描述协方差的类型，必须是”spherical”,”diag”,”full”,”tied”的一种，详见
params: ‘cmte’,cm分别代表高斯分布的方差和均值
init_params: ‘cmte’
在属性中，因为是连续量，所以没有emissionprob_，变成了means_和covars_.
下面是构建GaussianHMM实例：1
2
3
4
5
6
7
8
9
10
11
12import numpy as np
from hmmlearn import hmm
np.random.seed(42)
model = hmm.GaussianHMM(n_components=3, covariance_type="full")
model.startprob_ = np.array([0.6, 0.3, 0.1])
model.transmat_ = np.array([[0.7, 0.2, 0.1],
[0.3, 0.5, 0.2],
[0.3, 0.3, 0.4]])
model.means_ = np.array([[0.0, 0.0], [3.0, -3.0], [5.0, 10.0]])
model.covars_ = np.tile(np.identity(2), (3, 1, 1))
X, Z = model.sample(100)
建立确定参数的HMM模型时，需要在构建实例后，传入模型的参数，连续模型是cmte,离散模型是ste。
代码最后，通过model.sample(100)产生长度为100的样本，X，Z分别代表了状态序列和观测序列。
训练HMM参数，估计状态序列
可以通过fit方法来训练HMM参数，输入是联立的观测序列和它的长度序列。
通过方法score可以计算观测序列的概率。
推断状态序列可以用predict方法。
保存和加载模型
有两种方法，标准的pickle模块和scikit-learn中的joblib模块1
2
3
4
5from sklearn.externals import joblib
joblib.dump(remodel, "filename.pkl")
["filename.pkl"]
joblib.load("filename.pkl")
GaussianHMM(algorithm='viterbi',...
参考文献：