为什么要去研究HMM？

首先，HMM这个概率模型，在NLP领域算是一个比较基础的，但很有价值的模型。它的主要思想是：概率分布及其能导向什么结果。关于HMM的理解，在具体的数据场景下是比较容易的，网上也有不少介绍的blog、视频，因而这里不再赘述了。

之前，记得在自然语言处理的课程上，是有提到过HMM模型的，依稀记得是用在句法分析还是词性标注上面。但是由于老师死气沉沉讲的不好，我们院系设置的又不是必选，因而听的也不甚上心，最后也果然没考到，HMM自此埋下伏笔，成为了我的一个知识盲区。后来，应用场景大多是生成文本、或是对文本的内容进行分析，已经没有用到HMM的必要了，像是jieba使用HMM模型作为它的分词器，我只需要懒人使用即可，重点还是后面的内容理解与分析上，因而再也没有接触过这个东西。

实际上，最近，由于准备秋招，深感自身基础不足，在看牛客上的面经，会需要手撕一些基础的分类、聚类、transformer等一些算法。说实话我在这方面是没有准备过、相当薄弱的，因而需要将这些手撕都写一下，我也因此在GitHub上开了一个仓库专门做这个事情。

HMM，本来是不在我的计划范围之内的。但是和朋友聊天的过程中，说到他正在开发的输入法所面临的算法问题，需要用到HMM，感到眼熟的情况下，正好手撕代码也遇到了一些瓶颈，需要再去看一下东西，因而走马观花地浏览了一下HMM，本来还以为会像之前好几次一样看完不懂就扔，没想到这次一下栽了进去出不来了。

为什么呢？主要是因为看到了一份代码，是写了HMM的模型，支持根据观测序列推断HMM三元组。一个class，大概几百行，也不冗余，很快就搞定了。这不也是机器学习算法的一种吗？根据代码来看，fit与predict，何其熟悉的两个函数！因而来了兴致，花了几天去钻研一下子。但是这个数学公式实在是不太熟悉难以看懂，因而是有些痛苦的。

所幸的是，今天，终于理解了一部分，虽然EM算法这个使用拉格朗日乘子与KKF来求解HMM三元组的极大似然的方法仍然是不懂，但至少，对于输入法使用HMM的这个方面，是理解的差不多了。

如何理解HMM？

在这里，需要明晰的一个概念就是：HMM只是一个，根据初始概率分布的List——Pi、每个状态在任意时刻下到所有其他状态的状态转移概率矩阵——A、以及每个状态在任何时刻下所能观测到的的观测概率矩阵——B，来计算观测序列的概率分布的模型。
如果说，有M个状态、每个状态有N种概率，那么Pi的size就是1 * M， A的size就是M * M， B的size就是M * N。如果看这个shape不能直观理解的花，可以去搜一下HMM的例子，网上有很多。
这里需要注意的是，HMM使用是基于两个独立性假设的。

（本来用md想写公式的，看了看有点烦，暂时搁置了，教程网址点这里）

关于HMM，在已知三元组的情况下，求出某个观测序列产生的概率，可以用前向算法或后向算法解决。总之都是硬算。具体公式解析看这篇博客，写的挺好的。代码实现则可以参照这个博客,d但公式解析就不要看了，公式没写好不直观。

前向算法是简单的动态规划即可解决了，就是一层层套娃比较麻烦，而在将概率矩阵用dict保存的这种稀疏矩阵场景下尤甚。
至于后向算法，由于在计算过程中，不仅需要已知三元组，还需要用到前向算法的结果，还需要利用两大假设对公式进行化简、相当不容易直观理解，因而必须在前向算法结束之后才能使用。在这个解决问题的场景下，显得有些幽默。但后向算法的意义似乎不在于此，而在于EM算法评估参数的过程。（EM算法实际上就是极大似然估计法，只是这个算法出现的比极大似然估计早，总不能老子改成儿子的名字吧！）EM算法还是看不太懂公式，但是不要紧！分词和句法分析这类用不到！

Viterbi算法

————前向算法，只不过：计算的是最有可能的路径，且你需要记录你走过的路径，以及当前这个状态最大的状态值

在输入法的这个场景下，由于概率连乘会导致精度消失问题，通常用log转化为加法。那么，可以很好地构想出Viterbi算法的意义了：找到从起始节点到终止节点，sum最小的路径长度。只不过在乘法视角下有些不太直观

那么，在HMM的场景下，我们需要记录什么？需要记录每一步能够到达的状态及其开销（概率）。直到最后一步。同时，在每个时间步记录我们当前时间步为止的最有可能的状态序列；然后，对于我们记录下来的最终的这个状态序列，逐个去查每个状态最有可能的观测值，得到的和状态序列长度相同的观测值序列，就是维比特算法的结果。

输入法场景下，我们会根据输入的字母组合，如“asdasd”这种字符串，去查拼音表进行一个字符串匹配的贪心切分，然后会返回一个或多个切分的结果。根据这个切分的结果，我们将字母decode成汉字。在decode的过程中使用的Viterbi算法。转移概率矩阵及其观测概率矩阵是不同的。如，对于切片结果[‘a’, ‘b’, ‘c’], 初始分布概率Pi是’a’这个字母对应的字的出现频率；到了转移矩阵，则是第二个时间步，也就是开始“decode” b对应的字的时候，这个概率转移向量，就是所有“a”能decode出来的字，后面跟的字以“b”为拼音开头所出现的频率。

也就是说，对于我们去获得HMM的三元组的语料库。我们需要做以下几件事：

对于初始化Pi矩阵：需要获取所有字的拼音，按首字母、全拼音长度两个（或许你也可以统计残缺拼音的频率，但应该会对精确度造成损失。），对拼音对应的字的频数/频率进行统计。以dict的形式保存起来。然后在输入法decode的阶段，查这个dict作为初始Pi矩阵

对于转移概率矩阵，则需要统计，语料库从头到尾，前一个字之后的当前字的拼音及其对应字同时出现的频数/频次（考虑到首字母、全拼音的组合，这个应该是1 * 2种可能？）然后，以前一个字作为key，后一个字{拼音： [字 and 频，字 and 频，字 and 频，字 and 频]}这种形式保存起来，作为后续的状态转移概率矩阵。

对于观测概率矩阵，则是统计拼音对应的字的概率。实际上也是Pi矩阵。这个矩阵只会在上面转移概率发现没有对应的下一个词的统计结果，而只能将目前的拼音与前面割裂开来、当成一个独立的来decode时候，才会使用。实际上也是新一轮的HMM初始化？

因而，输入法的维比特算法，与一般维比特算法的区别在于：转移概率部分替代观测概率。

此外，输入法还需要整合记录其他的路径的内容和概率以便做排序，这个还得再想想……

EM算法

推导还是看不懂，公式和代码死记硬背吧！是《统计学习方法》——李牧里面的。感兴趣可以去看看原书第10章。