【强基固本】从零开始的自然语言处理（基于隐马尔可夫模型的词性标注）

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—alpha君

地址：https://zhuanlan.zhihu.com/p/382099914

「言葉には裏と表があるの。口に出したことがすべてじゃないのよ。人の弱いところね。相手を試すことで自分の存在を確認するの」
“话语的含义有内外两层，说出口的并不是全部。这就是人的弱点。通过试探对方，寻找自己在对方心中的地位。”

由于近年来机器学习的迅猛发展，作为其应用之一的自然语言处理（Natural Language Processing, NLP）也随之成为了一个非常热门的领域。尽管现在在NLP领域突破性的进展都直接与机器学习挂钩，但殊不知，NLP在上个世纪五十年代起，也就是在真空管计算机问世刚刚不久后就已经得到了学者们广泛的研究。虽然现在用机器学习模型解决NLP中的问题已经成为了常规操作，但其实早在机器学习这一概念诞生之前，NLP中的很多问题都已经通过统计模型得到一个很好的解答。

由于自然语言的模糊性和非精确性，NLP中有关认知，翻译，理解的问题大多都是非平凡（non-trivial）的（这就是为什么有些黄油的汉化一眼就能看出来是机翻的）。笔者本身因缺乏相关的基础，所以在这方面并没有多少学习的经验。不过，近期笔者在离散概率模型的相关课程上发现NLP中的词性标注（Part-of-speech Tagging，POS Tagging）问题可以用隐马尔可夫模型（Hidden Markov Model, HMM）这一非常基础的概率模型轻易解决，这让笔者感到非常的意外。这一算法描述起来非常简单，而且不需要任何机器学习以及语言学方面的知识就可以理解并且实现。于是笔者便诞生了执笔这一篇文章的想法，在把它当成自己的学习笔记的同时，也希望更多像笔者一样缺乏语言学和机器学习知识的的读者们也能感受到NLP的魅力。

由于马尔可夫链（Markov Chain）的基本概念在绝大多数的基础概率论课程上都有讲到，笔者便不会在此赘述，而是在马尔科夫链的基础上引入隐马尔可夫模型的概念，并将其应用到对语言的建模上。

在阅读这篇文章之前我需要哪些知识？

• 马尔科夫链的基本概念

• 初中英语

• 基础编程技能

在阅读完这篇文章之后我能做到些什么？

• 编程实现对英语的词性标注

【注】:

如果你要问为什么我在这篇文章中要使用英语而不是中文作为标注的语言，那是因为中文的词性标注要远远比英语的词性标注要困难。英语（以及大部分印欧语系下的语言）里一句话中词与词之间都有空格分割，而中文句子中词语与词语之间并不存在这样的分割。若想对中文文本实现词性标注，则必须先对中文句子进行基于词语的拆分，而这本身就又是一项不简单的任务。

01

什么是词性标注？

词性（part of speech）是句子中各个词汇的语法分类。比如名词（apple, desk, student），动词（swim, eat），形容词（soft, warm）都是大家比较耳熟能详的词性。大家感兴趣的话可以去看一下宾夕法尼亚大学Treebank提供的一个比较完成的英语单词的词性列表：

https://www.ling.upenn.edu/courses/Fall_2003/ling001/penn_treebank_pos.html

而词性标注，顾名思义，就是给句子中每个单词都标注一个最为恰当的词性。实际上，英语中的绝大多数词汇都只有一种词性，我在上面给出的名动形容词的例子都是拥有单一词性的英语单词的例子。这样的单词无论出现在句子的什么地方，有什么样的上下文，我们都只需要给它标记上它唯一拥有的那一种词性便可。然而，不幸的是英文中有很多常见的单词都是拥有多重词性的。

比如单词【can】就有情态动词（表“能够”），名词（罐头），和动词（将……装入罐头）三种词性

1. I can finish my homework today
2. He bought a can from the mart
3. The fishes are canned and shipped

再比如单词【around】就有介词，助词，和副词三种词性

1. Mrs. Shaefer never got around to joining
2. All we gotta do is go around the corner
3. Chateau Petrus costs around 250

而这些单词的存在正是词性标注的难处所在。

02

马尔可夫链

大家所熟知的马尔科夫链是由三个部分构成的，即：状态集合，状态转移概率，和初始概率分布。马尔可夫链的一个教科书式经典的例子就要数对天气的概率建模了：

基于马尔科夫链的天气预报（就和基于泰勒展开的股市预测一样可靠）

其实马尔可夫链除了可以用来做天气预报（雾）之外，我们还可以用它来对英语的语法进行描述：

一个简化了的描述英语语法的马尔可夫链（状态转移概率是我瞎编的）

在这个模型下，每一个词性都是一个状态，而英语中所有的词性的集合便构成了状态集合（这里我们只取了六种词性（+结句）作为示范）。而状态转移概率则由图中箭头上的红字给出。就比如说  ，也就是说在句子中，如果上一个词是形容词的话，那么下一个词有80%的可能性是名词；再比如  ，也就是说一个形容词后面还是一个形容词的概率只有5%——比较少见，但也不是不可能。而可能性为0的状态转移就没有在上图中画出来，比如说  ，在英语中代词不可能出现在冠词的后面（比如【The he】,【A she】这样的组合根本不符合英语的语法 ）。

为了模型的完整性，我们还需给出初始概率分布，也就是对于每个词性，我们需要给出英语中句子的第一个单词是这个词性的概率，类似这样（数字也是我瞎编的）：

有了这个模型，我们便可以给出一个英语句子的词性为一个特定序列的概率。比如序列【冠-名-动-名-句号】(例句：The boy drinks water. A cat climbs trees.)出现的概率便为：

再比如序列【形-形-名-动-副-句号】(例句：Ancient Greek philosophers think critically. Colorless green ideas sleep furiously.)出现的概率便为

【注】：这里的第二个例句是有来头的。这个电波感十足的句子【Colorless green ideas sleep furiously.（无色的绿色想法在狂野地睡觉）】常被用做完全符合英语语法但是根本不make any sense的句子的例子。感兴趣的同学可以看看关于这句话的维基百科页面：

https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously

用符号化一点的表示的话，那么对于给定的词性序列  ，一个英语句子的词性等于该序列的概率是

其中  为  上的初始概率（即该句子的第一个词的词性为  的概率），  为  到  的状态转移概率。

当然，这个模型成立的一个重要假设就是英语真的就是一个一阶马尔可夫链，也就是说一个单词为一给定词性的概率完全由上一个单词的词性所决定。其实这个假设真的很经不住推敲，就比如我们这里认为  ，但实际上，如果这个形容词之前接的是一个冠词的话，那么此时应该几乎为零，而  的概率则会大幅提高（比如【a beautiful】后面几乎不可能接句号，而有大概率接一个名词）。为了改善（注意，仅仅是改善，不是解决）这一点，我们可以使用阶数更高的马尔科夫链，即该马尔可夫链的状态集合是一个两个相邻的词性  所组成的pair，而状态转移概率则对于任意的  ，给出下一个词性为  的概率。就拿刚才的例子来说，我们就可以有  ，  。但是由于篇幅限制和为了模型的简洁性，我们这里只拿一阶马尔科夫链说事。

03

隐·马尔可夫模型

上述的模型仅仅是对英语的语法进行了概率建模，而为了达到我们的目的（词性标注），我们还需要将英语中具体的一个个单词加入到我们的模型当中。为了实现这一目的，我们需要引入隐马尔可夫模型（HMM）的概念。其实HMM比起马尔科夫链来，只多出了一个可观测符号集（set of observable symbol）以及从状态到符号的输出概率（emission probability）。

好吧废话不多说了，上图。

数字仍然是我瞎编的

我们该怎么理解这个图？注意到图中的HMM中包含了我们在上一节中用到的马尔可夫链，只不过现在每一个状态（词性）都可以以一定概率输出给定的单词。而此概率对应的便是一个拥有该词性的单词是某个特定单词的概率。比如说，我们看到  ，也就是说如果一个单词在句子中是副词，那么这个词是“fast”的概率为0.01（因为英语中有成千上万的副词，所以实际的概率要远远小于这个值）。注意，不同的状态可以输出同一个单词，就像是fast可以是形容词也可以是副词，green可以是形容词也可以是名词。

再回到我们刚才的术语上，在上图的HMM中，具体的英语单词（fast, furiously, boy, green, sleep, run, ...）便构成了我们的可观测符号集。而每个词性输出给定单词的概率便是我们的输出概率。因为阅读一个英语句子时，我们看到的只是一个个的单词，而无法直接看到单词所对应的词性，所以单词的集合才被称为可观测符号集，而该HMM的状态，也就是词性，则常常被称为隐藏状态（hidden states）。我们可以将隐藏在背后的马尔科夫链（故有“隐”马尔可夫模型）看成是一种机制（比如：英语语法），而这个机制会产生一些表象（比如：英语句子），我们能观察到的只有表象，而观察不到表象之下的机制。而根据表象（句子中的单词）来推测表象之下的机制（句子中单词的词性）便是我们希望解决的问题的核心。

像这样给定一个现象，求在给定模型中，该现象最好的解释的问题被成为HMM的解码(most likely explanation)问题，它与预测(filter)问题和平滑(smoothing)问题一同被称为HMM的三大典型(canonical)问题（对其他两个问题感兴趣的同学可以去看看这个维基页面(https://zh.wikipedia.org/wiki/隐马尔可夫模型)和这个油管(https://youtube.com/playlist?list=PLix7MmR3doRo3NGNzrq48FItR3TDyuLCo)播放列表）。关于解码问题的算法我会在下一节里讲到。

有了HMM，我们便可以计算形如的概率，即给定词性序列  后，英文句子  出现的概率。根据概率的乘法原理，我们有

比如说我们知道一个句子的词性序列是【冠-名-动-副】，而我们想计算该句子刚好是【the boy runs fast】的概率（句号我就懒得打了），那么我们有

再比如序列【形-形-名-动-副】生成句子“Colorless green ideas sleep furiously”的概率为

大家可以注意到上式的可能性并不完全为零，而直觉告诉我们在正常情况下英语中出现这样一句话的概率为零。

"Chomsky writes in his 1957 book Syntactic Structures:
(1) Colorless green ideas sleep furiously.
(2) *Furiously sleep ideas green colorless.
It is fair to assume that neither sentence (1) nor (2) (nor indeed any part of these sentences) has ever occurred in an English discourse. Hence, in any statistical model for grammaticalness, these sentences will be ruled out on identical grounds as equally "remote" from English."
——摘自英文维基百科条目“Colorless green ideas sleep furiously”

这就说明英语并不能够用HMM进行完美的描述，而公式

其实也是为了使我们的模型成立的又一个重要假设。虽然这一假设一眼看上去似乎比之前的那个假设要合理一些，但是其实这一假设仅仅在语法上是合理的，而并没有考虑到语义。比如给定词性序列【冠-名-动-冠-名】，句子The student took the test(学生参加了考试)出现的概率为

而同样的序列生成The student took the test(考试参加了学生)这样电波感十足的句子的概率是

仔细观察，不难发现两个概率是相等的（实数的乘法满足交换律），但是显然是不合理的，因为第一句话出现的可能性应该远远高于第二句话。两句话的区别仅仅在于交换了两个名词的位置，这样的两句话在语法上是完全相等的，但是由于两个名词的位置不同，导致第一句话表达了一个非常合理的意思，而第二句话你就是在《素晴日》中也不会看到。

不过，为了模型的简洁性，我们就暂且承认这个假设吧（暴言

04

Viterbi算法

词性标注，说的严谨一点就是一个最优化问题：我们有给定的一句话，它是一个单词的序列  ，给定一个描述英语的HMM，求词性序列  使  最大化。贝叶斯定理告诉我们 

但因为  序列是给定的，所以  不过是一个常数，所以最大化  ，和最大化是等价的。其中就是词性序列出现的概率，而则为序列产生的概率。而我们在之前的两节中都已经详细描述了如何通过HMM来计算这两个概率。我们有

既然我们已经知道如何计算，那么为了最大化这个值，我们不可以遍历所有的序列，然后找出哪个序列能够将最大化吗？这个方案在理论上是可行的，然而实际上却根本行不通，因为这种遍历实在是太暴力了。设我们一共有  个不同的状态，那么所有可能的序列就多达  。即使是对于  ，我们就需要遍历10^20个序列，这程序在《樱之刻》发售之前应该是跑不完了。

扶她老贼你快把樱刻给我吐出来啊！！

为了解决这一问题，我们需要使用到动态规划（Dynamic Programming, DP）的技巧（打过NOI，ICPC的同胞们让我看到你们的双手！!）。

我们定义函数为在  的情况下，能够取到的最大值（    ）。再定义  等于能够让取到最大值的  的值（  ）。

用符号化一点的表示，那就是

可以看到，如果我们能够计算出  对于所有的  ，那么，我们所需要最大化的概率便是

而我们所求的  序列可以由回溯递归式

 给出（上小标星号代表最优解）。

对于除了i=1之外的所有i，我们可以通过以下递归式计算v和bt

如果你之前没有接触过递归或是动态规划，那么我建议你可以去看看这个(https://zh.wikipedia.org/wiki/动态规划)，然后再回来多看上几遍上面的公式。

至于  的情况，我们只需要根据定义，将  设成  即可。

上述的算法就是著名的Viterbi算法，它的时间复杂度是，比起  来说是一个巨大的进步。完整的Viterbi的伪代码由下给出（注意在伪代码中，数组采用从零开始的编码）：

05

隐马尔可夫模型的构建

至此，我们已经给出了根据HMM给句子进行词性标注算法的完整描述。

观众：啊好的那我们赶紧开始写代码实现吧！（棒读）

待って待って，其实我们还缺失一个小小的细节。

我们只讲了怎么用HMM来算概率，我们还没讲HMM是从哪儿来的啊？？！！HMM不是天上掉下来的啊kora！！

凡是对机器学习稍有了解的读者都明白为了构（tiao）造（jiao）一个机器学习模型，除了要将神经网络的架构搭好，还要向这个模型中灌入大量的训练数据，让模型都变成训练数据的形状，到最后模型除了训练数据之外什么都不会想了❤。在这一点上，HMM和神经网络并没有什么不同。

我们可以通过已经被标注了的英语文献来训练我们的HMM。

被标注了的训练数据，文件我会放到文章的最后。需要的话请自取

令  为训练数据中单词  被标记成  的次数，   为  相继出现的次数，  为  出现的次数，  为  作为句子中的第一个标记出现的次数。根据概率论中的频度/频度的方法计算概率，我们有

这三套参数完整地给出我们所需要的HMM的描述。

06

算法实现，运行结果，以及写完代码后贤者模式时的一些哲学探讨

在写这个算法有一点必须要注意的是，在写Viterbi的时候，由于我们要计算一连串  的值的连乘，所以计算的中途我们处理的都是极其接近0的实数。由于计算机无法精确地表示实数，这会让数组  中本来不应为零的值变成真正的零（这种现象被称为算术下溢），使我们无法进行极小量之间的比较，而导致错误的结果。为了解决这一问题，我们可以将所有的  值取自然对数，这样我们在计算的时候只需要将数字相加而不是相乘了。

另外，无论是多么庞大的训练数据，都无法避免在测试数据中出现训练时没见过的单词（比如人名，地名，术语这样高度具体的单词）。如果我们只是依靠训练数据所调教出来的模型，那么这个模型会单纯地认为只要一句话中包含它之前没见过的单词，那么这句话出现的可能就为零，使Viterbi失效。为了避免这一情况发生，我们可以在跑Viterbi之前先预处理一遍测试数据，找出模型之前没见过的单词，然后人为地让每个状态都能够以一个极小的概率（这样的）输出这个新的单词。

上述的两点只要注意一下，基于HMM的词性标注便不难实现（我写的C++两百行代码就能解决）。有兴趣的读者不妨可以自己动手写一下。

那么这个算法到底有多准确呢？

在把运行结果放出来之前，我觉有必要在这里先讨论一下一个更加naive的词性标注的算法，然后将两个算法做一个比较。毕竟，在没有比较的情况下，我们很难对一个结果做出客观的评估，而在有比较的情况下我们才能更好地理解一个算法的表现以及它的implications。

我们在文章的一开始有提到过，英语中其实多数的单词都只有一种词性。所以仅仅是基于这一点，我们就可以轻松地给英语中的大多数单词进行标注。受这一点的启发，我们可以自然地提出这样一个naive的算法。即对于训练数据中出现的每一个单词  ，找出它最经常拥有的词性  ，然后在处理测试数据的时候，看到  就输出  ，而看到没见过的单词的话就输出训练数据中最常出现的词性。

这个算法非常容易理解，处理测试文本的时间复杂度只有  （n为单词的数量），而且实现起来也只用了HMM不到一半的代码。

我用长度为~2200000个单词的训练数据训练了HMM和naive算法的两个模型，之后分别用两个模型跑了一个长度为974个单词的测试数据，结果如下：

可以看到，基于HMM的词性标注给出了一个让人非常满意的高达97%的准确率。但让人几乎有些诧异的是，上述的简单的naive算法也给出了一个高达93%的准确率。你可能会觉得不高兴，我们花了那么多时间和精力研究复杂的算法，而且搞出来的东西的时间复杂度还要高出一截子，结果才把准确率提高了不到4%？！

关于这个问题，我有两点想说的。一是词性标注本来就是NLP中最简单的一类问题。所以一个非常初等的approach能够有如此高的表现也没什么好奇怪的。当一个东西的准确性接近100%的时候，单看提升的百分比的绝对值就没有什么意义了。就比如一个准确性为99.5%的测试和一个准确性为99.99%的测试，两者之间虽然只差了不到0.5%，但是大家都可以看到两者在准确性上是有着天壤之别的。再看我们的这两个算法，前者的误差率为2.98%，后者的误差率为6.57%，前者的误差只有后者的43%，这可以说是一个很大的进步了。

我第二个想说的就是，如果我们想给现实生活中复杂的现象进行建模，那么我们的模型就不可避免地会存在误差。著名估计学家George E. P. Box曾说过一句话“all models are wrong, but some are useful”。如果我们想要提高模型的精度，就必须牺牲模型的简洁性，在解算模型的时候也要付出时间的代价。为了能够对现实世界中的现象做出准确的预测，我们追求“更好”的模型，但什么叫做更好？天下没有免费的午餐，如果你在模型的某一些方面追求更高的表现，那么你就必然地会在其他的一些方面付出代价。你在选择模型，选择算法的时候就必须做出取舍。你到底想从这个模型中得到什么？更高的精确度是否值得你付出计算量的代价？如果值，那么它值得你付出多少？就像是我之前提到的二阶HMM，它虽然可以进一步提升词性标注的准确度，但是这同时也会让Viterbi的时间复杂度变为  （通过适当的优化可以改善到  ）。这是你可以接受的吗？你对模型的准确性到底有多挑剔？再比如说我在我的上一篇文章

https://zhuanlan.zhihu.com/p/372837854

中提到的，浅水方程常被用来对大面积的水体进行建模，但是浅水方程的成立有诸多假设，而现实中的水体的运动并不会严格遵循这些假设，这就导致了我们模型的不准确性。当然，我们可以使用更加复杂，维度更高的的方程，但随之而来的便是成指数增长的代码量以及运行时间。所以在浅水方程在实际应用中还是很受青睐的，因为，对于很多的情况，浅水方程给你的准确性已经能够满足应用中的绝大多数需要了。

解决实际问题的时候，你所使用的模型和数值方法并不是精确越好。而你要考虑精确度对你来水究竟有多重要。你手里的数值模型是否关系到数千人的性命，是否关系到上亿美元的经济利益？这世界上没有“最好”的数值模型和方法，只有对你想要解决的问题“性价比”最高的模型和算法。所以，说到底，还是要具体问题具体分析（政治课代表发言）。

我常在我的同学面前自称是一位applied mathematician。当然，这就意味着我的世界不会像我学纯粹数学的同学的世界那样纯粹和美好。但是，我觉得，我们生活所的世界的复杂性，非线性性，不完美性和非精确性正是这个世界有意思的地方。

以下git repository包含我的所有代码，训练数据以及测试数据

https://github.com/Alpha-kun/postagging

其中main.cpp给出了我的HMM+Viterbi实现，而naive.cpp则给出了上述naive算法的实现。

相关文献及资料

1. https://en.wikipedia.org/wiki/Natural_language_processing

2. https://en.wikipedia.org/wiki/Part_of_speech

3. https://en.wikipedia.org/wiki/Hidden_Markov_model

4. https://en.wikipedia.org/wiki/Part-of-speech_tagging

5. https://en.wikipedia.org/wiki/Viterbi_algorithm

D. Jurafasky and J.H. Martin, 2009. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Second Edition. Pearson, Prentice-Hall.

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！