如何用简单易懂的例子解释隐马尔可夫模型？ - 知乎 - 作者：Yang Eninala
luopeixiang/named_entity_recognition: 中文命名实体识别（包括多种模型：HMM，CRF，BiLSTM，BiLSTM+CRF的具体实现）
上面三种不同的骰子，假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。
假设我们开始掷骰子，先从三个骰子里面选一个，概率为 1/3，然后掷骰子得到一个数字，反复几次，我们可以得到一串数字 [1, 6, 2, 3]
这串数字叫做观测序列（可见状态链），我们不仅仅有这么个观测序列，还有一串状态序列（HMM中说到的马尔可夫链其实是指隐含状态链），比如 [D4, D6, D8, D8]，在我们这个例子里，D4 的下一个状态是 D4，D6，D8 的概率都是1/3。我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。
'状态序列' -> '观测序列'
[D4,D6,D8,D8] -> [1, 6, 2, 3] 若观测序列为：[1 6 3 5 2 7 3 5 2 4]，状态序列为 [D6 D8 D8 D6 D4 D8 D6 D6 D4 D8]，则：
其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。
隐马尔可夫模型是一种概率图模型。HMM模型中存在两个假设，一是输出观察值之间严格独立，二是状态转移过程中当前状态只与前一状态有关。
我们知道，机器学习模型可以从频率派和贝叶斯派两个方向考虑，在频率派的方法中的核心是优化问题，而在贝叶斯派的方法中，核心是积分问题，也发展出来了一系列的积分方法如变分推断，MCMC 等。概率图模型最基本的模型可以分为有向图（贝叶斯网络）和无向图（马尔可夫随机场）两个方面，例如 GMM，在这些基本的模型上，如果样本之间存在关联，可以认为样本中附带了时序信息，从而样本之间不独立全同分布的，这种模型就叫做动态模型，隐变量随着时间发生变化，于是观测变量也发生变化：
graph LR;
z1-->z2-->z3;
（《统计学习方法》） 隐马尔可夫模型（Hidden Markov Model，HMM）是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列（state sequence）；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observation sequence）。序列的每一个位置又可以看作是一个时刻。
O 是所有可能的状态集合，W 是所有可能观测的集合，N, M 分别是其数量： $$ O=\left{o_{1}, o_{2}, \cdots, o_{N}\right}, \quad W=\left{w_{1}, w_{2}, \cdots, w_{M}\right} $$
在这里，O = {1, 2, 3, 4, 5, 6, 7, 8}，W = {D4, D6, D8}
I是长度为T的状态序列（如 [D6 D8 D8 D6 D4 D8 D6 D6 D4 D8]），O是对应的观测序列（如 [1 6 3 5 2 7 3 5 2 4]）。
$$
I=\left(i_{1}, i_{2}, \cdots, i_{T}\right), \quad O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)
$$
A 是状态转移概率矩阵 $A=[a_{ij}]{N\times N}$ ，其中
$$
a{ij} = P(i_{t+1}=o_j |i_t = o_i),i=1,2,\cdots,N;j=1,2,\cdots,N
$$
是在时刻
B 是观测概率矩阵 $B=[b_{j}(k)]{N\times M}$，其中
$$
b{j}(k)=P\left(o_{t}=w_{k} \mid i_{t}=o_{j}\right), \quad k=1,2, \cdots, M ; j=1,2, \cdots, N
$$
是时刻
隐马尔可夫模型由初始状态概率向量，状态转移概率矩阵以及观测概率矩阵所确定。
上面的定义太过学术看不懂没关系，我们只需要知道，NER本质上可以看成是一种序列标注问题（预测每个字的BIOES标记），在使用HMM解决NER这种序列标注问题的时候，我们所能观测到的是字组成的序列（观测序列），观测不到的是每个字对应的标注（状态序列）。
HMM 的三个状态可以解释为：
- 初始状态分布 是每一个标注作为句子第一个字的标注的概率；
-
状态转移概率矩阵 就是由某一个标注转移到下一个标注的概率；设状态转移矩阵为
$M$ ，则若前一个词标注为${tag}_i$ ，则当前词为 ${tag}j$ 的概率为 $M{ij}$ - 观测概率矩阵 就是指在某个标注下，生成某个词的概率。
HMM 模型的训练过程对应隐马尔可夫模型的学习问题（李航 统计学习方法），实际上就是根据训练数据根据最大似然的方法估计模型的三个要素，即上文提到的初始状态分布、状态转移概率矩阵以及观测概率矩阵。
举个例子帮助理解，在估计初始状态分布的时候，假如某个标记在数据集中作为句子第一个字的标记的次数为 k，句子的总数为 N，那么该标记作为句子第一个字的概率可以近似估计为k/N，很简单对吧，使用这种方法，我们近似估计HMM的三个要素，代码如下
import torch
class HiddenMarkovChain:
def __init__(self, word2id, tag2id):
# 状态转移矩阵：[word_num, word_num]
self.word2id = word2id
self.tag2id = tag2id
tag_num, word_num = len(tag2id), len(word2id)
self.A = torch.zeros(tag_num, tag_num)
# 观测概率矩阵：[tag_num, word_num]
self.B = torch.zeros(tag_num, word_num)
# 初始状态概率矩阵
self.Pi = torch.zeros(tag_num)
self.tag_num, self.word_num = tag_num, word_num
def fit(self, word_lists, tag_lists):
assert len(word_lists) == len(tag_lists)
def MLE_estimate(mat, dim=1):
mat[mat == 0.] = 1e-8
return mat / mat.sum(dim=dim, keepdim=True)
for tag_list in tag_lists:
for i in range(len(tag_list) - 1):
now_id = self.tag2id[tag_list[i]]
next_id = self.tag2id[tag_list[i + 1]]
self.A[now_id, next_id] += 1
self.A = MLE_estimate(self.A)若我们想在从一个句子（n 个单词的序列）
- 单词出现的概率只依赖于标注。因此， $ P({w_1\cdots w_n} | {t_1\cdots t_n}) \approx \prod _{i=1}^n P(w_i |t_i)$
- （二元语法假设）当前标注的概率仅取决于之前标注。因此，$P(t_1\cdots t_n) = \prod_{i=1}^n P(t_i|t_i-1)$
所以我们可以得到： $$ \hat{t}_{1:n} = \underset{t_1\cdots t_n}{\operatorname{argmax}} \prod _{i=1}^n \overbrace {P(w_i |t_i)}^\text{观测概率} \overbrace{P(t_i|t_i-1)}^\text{转移概率} $$
上面提到的
我们最终要求的是，在某个观测序列下，每一个观测在某个未知状态的观测概率，乘以之前状态与当前状态的转移概率，其连乘取得最大值时，这些状态为何。
维特比算法实际是用动态规划解隐马尔可夫模型预测问题，即用动态规划（dynamic programming）求概率最大路径（最优路径）。这时一条路径对应着一个状态序列。也是一种图最短路算法——针对篱笆网络（Lattice Network）这一特殊的有向无环图。时间复杂度为
如上图所示，这是一个部分的篱笆网络，中间我们假设有
既然穷举法太过暴力，自然我们想试试能不能用动态规划来解决。
首先，篱笆网络有这么一个特点，就是假设我们从第一列走到最后一列，我们一定会经过其中的第
第二，如果说最短路径P经过某个节点
有了这两个特性，终于可以试试动态规划了。同样我们从最左边的S节点出发，到第1列的4个节点，因为各只有一段距离，那自然这4个距离
而这个保存中间结果的过程，很明显地体现出了前文所述的动态规划的特点。接下来，我们继续走到第3列，同样的，S节点到第3列某个节点的距离为$d(S, x_{3k})=d(S, x_{2j}) + d(x_{2j}, x_{3k})$。
这个时候我们发现，等式右边的第一项，可以直接取我们刚刚保存的中间结果。对于
class HiddenMarkovChain:
# ...
def predict(self, input_word_list):
# viterbi decoding
# 避免概率很小
# 转置 观测概率矩阵：[word_num, tag_num]
A, B_t, Pi = torch.log(self.A), torch.log(self.B).t(), torch.log(self.Pi)
viterbi = torch.zeros(self.tag_num, len(input_word_list))
back_pointer = torch.zeros_like(viterbi).long()
start_word_id = self.word2id.get(input_word_list[0], None)
b_t = B_t[start_word_id] if start_word_id else torch.log(torch.full([self.tag_num], 1 / self.tag_num))
# 观测概率log + 初始概率log
viterbi[:, 0] = b_t + Pi
back_pointer[:, 0] = -1
# viterbi = (前一个字的标注 s' 的概率 x s' 到 s 的转移概率 x s的观测为该字的概率) 遍历 s' 取最大值
# back-pointer = viterbi遍历到最大时的参数
for i in range(1, viterbi.shape[1]):
word_id = self.word2id.get(input_word_list[i], None)
# 该字对应的标注概率（观测概率）
b_t = B_t[word_id] if word_id else torch.log(torch.full([self.tag_num], 1 / self.tag_num))
for tag_id in range(len(self.tag2id)):
max_prob, max_id = torch.max(
viterbi[:, i - 1] + A[:, tag_id], dim=0
)
viterbi[tag_id, i] = max_prob + b_t[tag_id]
back_pointer[tag_id, i] = max_id
best_path_prob, best_path_pointer = torch.max(viterbi[:, viterbi.shape[1] - 1], dim=0)
# 回溯，求最优路径
best_path_pointer = best_path_pointer.item()
best_path = [best_path_pointer]
for back_step in range(viterbi.shape[1] - 1, 0, -1):
best_path_pointer = back_pointer[best_path_pointer, back_step]
best_path_pointer = best_path_pointer.item()
best_path.append(best_path_pointer)
# 将tag_id组成的序列转化为tag
assert len(best_path) == len(input_word_list)
id2tag = dict((id_, tag) for tag, id_ in self.tag2id.items())
tag_list = [id2tag[id_] for id_ in reversed(best_path)]
return tag_listStrengths and weaknesses of hidden Markov models
- 调优的HMM通常比简单的马尔可夫模型提供更好的压缩，允许显著地发现更多序列。
- The models are fairly readable (at least when drawn rather than just listed). A high-quality model for REPs (compressing previously unseen REPs to about 1.25 bits/base) may have around 200 states and 300 edges, rather than the counts of the order-8 simple Markov model. The low ratio of edges to states means that large parts of the model are simple straight-line sequences, which are easy to draw and to understand. 边缘与状态的低比率意味着模型的大部分是简单的直线序列，易于绘制和理解。
- The HMMs can be used for generating alignments, with each state of the machine corresponding to one column in the alignment. The best path found by the Viterbi algorithm identifies a state for each position, and that in turn can specify the column. HMMs are a bit more powerful than alignments, since the same state can be used repeatedly in a path, but each column can only be used once in an alignment. This results in ambiguous alignments if a column alignment model is used, but can be quite convenient for describing phenomena like random numbers of repeats of a short subsequence. 非常方便地描述像短时间的重复的随机数量的现象。
-
The Viterbi algorithm is expensive, both in terms of memory and compute time. For a sequence of length n, the dynamic programming for finding the best path through a model with s states and e edges takes memory proportional to sn and time proportional to en. For the REP searches, doing a search with a hidden Markov model is about 10 times slower than using a simple Markov model--for larger HMMs (needed for longer target sequences) the penalty would grow. 维特比算法计算速度慢。用于隐马尔可夫模型的其他算法，如forward-backward算法，甚至更昂贵。
-
HMM只依赖于每一个状态和它对应的观察对象：序列标注问题不仅和单个词相关，而且和观察序列的长度，单词的上下文，等等相关。
-
目标函数和预测目标函数不匹配：HMM学到的是状态和观察序列的联合分布P(Y,X)，而预测问题中，我们需要的是条件概率P(Y|X)。
-
无法处理未知的标注。
-
It would be great to have ways to add arbitrary features tohelp with this, perhaps based on capitalization or morphology (words starting withcapital letters are likely to be proper nouns, words ending with-edtend to be pasttense (VBD or VBN), etc.) Or knowing the previous or following words might be auseful feature (if the previous word isthe, the current tag is unlikely to be a verb). Although we could try to hack the HMM to find ways to incorporate some ofthese, in general it’s hard for generative models like HMMs to add arbitrary featuresdirectly into the model in a clean way. 很难添加特征。
于是我们就有了 CRF。