自然语言处理的数学原理（一）

一个基本的搜索引擎的工作，基本上可以分成以下三个部分：

利用网络爬虫下载网页，分析网页关键词，制成索引备用；
理解用户输入，确定检索关键词；
根据关键词和网页索引，按照相关性排序列出搜索结果。

第一个部分主要涉及网络爬虫技术、图论、自然语言处理等技术；第二个部分主要涉及自然语言处理；第三个部分同样涉及自然语言处理。

自然语言，即是人类用来交流的语言。

由此可见，自然语言处理（NLP, Natural Language Processing）是现代搜索引擎很重要的内容，其终极目的是将自然语言转化为计算机容易处理的形式。

从分词的角度来看文法分析与统计模型

分词是 NLP 需要解决的基础问题，分词算法的好坏直接影响 NLP 的结果。

这里我们先从一个简单的例子说起，逐步探讨合理的分词算法。

从一个简单的句子说起

现在有一个句子，比如：

我去电脑城买了一台电脑。

如果要让计算机对这个句子做分词处理，进而理解这个句子，你会有怎样的思路呢？

大多数人首先会思考一下自己是怎么理解这个句子的。对于中国人来说，这样一个简单的句子，可能不需要什么特殊的思维过程。句子的文字形式和句子背后的含义可以在瞬间反映出来。稍有汉语文法知识的读者，可能会想：

句子可以分成几个部分
- 我 - 主语
- 去电脑城买了一台电脑 - 谓语
  - 去电脑城 - 状语
  - 买了 - 谓语动词
  - 一台电脑 - 动词宾语（名词短语）
- 。 - 句子结束的标识
分别理解每个部分的意思
将意思拼合起来，变成完整的句意

它先通过文法分析，将句子拆分成一个二维的语法树，然后再理解各个部分的含义，最后做拼接。

这样的方案（或者说是算法）是基于文法规则的，清晰明了，也易于实现（在计算机里就是几个循环判断）。对于程序员来说，这样的算法也特别亲切。因为程序员使用的高级编程语言（比如 C++）的语法规则和这样的方案非常相似。

由于这样的算法直观、易于实现，所以人们相信在有了愈加全面的文法概括和愈加强大的计算能力时，人们就能彻底解决自然语言处理的问题了。

文法分析的困境

然而，如果你仔细观察文法分析的过程就会发现，这么一个简单的句子被分成了一个这样复杂的二维树状结构，耗费了六条注释。用计算机来处理这样一个过程当然不难，但是要处理现实生活中遇到的真实句子，往往就不那么容易了：

由于理解（understanding）自然语言，需要关于外在世界的广泛知识以及运用操作这些知识的能力，自然语言认知，同时也被视为一个人工智能完备（AI-complete）的问题。

这个句子依然可以用上述方法来处理：

先分成主谓部分
再仔细拆分谓语部分

比如：

自然语言认知 - 主语 - 偏正短语
- 自然语言 - 名词作定语修饰
- 认知 - 名词
由于理解（understanding）自然语言，需要关于外在世界的广泛知识以及运用操作这些知识的能力 ... 同时也被视为一个人工智能完备（AI-complete）的问题 - 谓语
- 由于理解（understanding）自然语言，需要关于外在世界的广泛知识以及运用操作这些知识的能力 - 原因状语
  - ...
  - ...
- 同时也被视为 - 谓语动词短语
  - 同时 - 状语
  - 也被视为 - 谓语动词
- 一个人工智能完备（AI-complete）的问题 - 动词宾语
  - 一个 - 定语
  - 人工智能完备的 - 定语
  - 问题 - 名词
- 。 - 句子结束的标志

这个句子的语法分析树我没有写完，因为实在太复杂了。显而易见，单纯基于文法分析的分析器是很难处理生活中的真实句子的。

那么问题出在哪里？我认为至少有两个问题。

文法规则数量巨大，上万条语法规则才只能覆盖约 20% 的真实句子；且有些为了处理特殊情况的语法规则和其他规则相互矛盾。
自然语言与程序设计语言不同，自然语言中词汇的具体含义与上下文相关，而程序设计语言则没有这样的歧义性。

从算法复杂度的角度来说，单纯基于文法分析的分析器，用于分析自然语言，其复杂度比分析程序设计语言要高出四个量级。从直观的印象来说，上述句子在一台现代计算机上用文法分析的方式处理，也需要至少一分钟的时间。这种低效是无法接受的。

查字典分词法

在之前的文法分析方法里，分词依赖于文法分析的结果。程序要先输出语法树，然后才能得到分词结果。而这样的方法已经被证明是低效的。

这样的低效来源于复杂的文法分析过程。为了提高效率，人们很自然地想到：是否有办法绕开文法分析，直接尝试分词呢？对于中文分词，北京航空航天大学的梁南元教授提出了查字典分词法。做法相当简单，比如对于下列句子：

山东大学数学学院是中国最好的数学基础教育基地之一。

我们让计算机从左到右扫描整个句子，每扫到一个字，就往字典里查询，遇到字典里有的词就标注出来。于是整个句子就被分割成了这样：

山东|大学|数学|学院|是|中国|最好的|数学|基础|教育|基地|之一。

看起来结果不错。不过细心的读者很快就会发现：山东大学和基础教育都是完整的词，在它们之间不应该再做划分。会出现这种情况也不意外，我们要求计算机从左到右扫描。当计算机遇到「山东」二字的时候，就认为这是一个词了，自然不会再去寻找下一个字去寻求匹配。同理基础教育。

梁教授提出了一个方案，即总是搜寻尽可能长的分词。这在计算机科学领域叫做「贪婪」。运用贪婪的办法，上述句子的分词就会变成：

山东大学|数学|学院|是|中国|最好的|数学|基础教育|基地|之一。

看起来就没什么问题了。

不过，汉语博大精深，这种办法也不能一劳永逸。比如：

大学生活区

正确的分词应该是：

大学|生活区

但是按照贪婪的办法，会被分词成：

大学生|活|区

这就不对了。

又比如：

发展中国家

正确的分词应该是：

发展中|国家

而不是：

发展|中国|家

可见，查字典的办法虽然效率很高，但是时有出错，并不牢靠。

查字典的办法遇到的困境来自于自然语言的歧义性。人类在阅读自然语言时，会结合上下文判断有多个意向的词汇在文中的具体含义，但是计算机却没有这个能力。实际上，中国传统文学里说的「句读」，其目的就是通过分词断句来消除歧义。那么，怎么让计算机具备这样的能力呢？

千呼万唤始出来的统计模型

行文至此，数学终于要第一次展现其威力和美丽。

我们之前提到，对一个句子做分词，其正确与否和词汇的二义性紧密相关。由于计算机无力综合上下文判断词汇含义，解决二义性，所以查字典的办法陷入了困境。

数学中有所谓的「反证法」。在这里我们不讲反证法，但是要讲讲反证法的思想。反证法的核心思想就是「正难则反」：正面突破很困难，那就不走大路，开个后门照样进城。在这里，既然计算机没有能力综合上下文解决词汇的二义性，那么我们就不依赖计算机智能去解决，转而借助人工的力量解决。当然，我说的不是找一个工人实时干预程序的运行，帮助程序作出正确的判断；而是说，让计算机经过大量的文本训练，吸取人类的「分词经验」。而这个方法，就是统计模型。

假定一个句子 $S$ 可以有几种分词的方案，比如有以下三种：

\begin{align}
A_1,,A_2,,A_3,,\ldots,,A_j \label{eq:fenci-1}\\
B_1,,B_2,,B_3,,\ldots,,B_k \\
C_1,,C_2,,C_3,,\ldots,,C_l \\
\end{align}

其中，$A_1$, $A_2$, $B_1$, $B_2$, $C_1$, $C_2$ 等都是汉语的词汇。这样一来，如果 \eqref{eq:fenci-1} 是最好的分词，那么 \eqref{eq:fenci-1} 出现的概率应该最大。也就是说，分词方案 \eqref{eq:fenci-1} 应该满足 \eqref{eq:stat-req}。

\begin{equation}
\label{eq:stat-req}
\begin{cases}
P(A_1,,A_2,,A_3,,\ldots,,A_j) \gt P(B_1,,B_2,,B_3,,\ldots,,B_k) \\
P(A_1,,A_2,,A_3,,\ldots,,A_j) \gt P(C_1,,C_2,,C_3,,\ldots,,C_l) \\
\end{cases}
\end{equation}

答案就是这么简单。

当然，如何处理 \eqref{eq:stat-req} 需要一点统计知识和技巧；得到这些分词方案也需要依靠动态规划算法（不然计算量太大）；还有诸如分词颗粒大小之类的细节问题需要处理。这些内容我们放在后续的小节里讨论，在这里，读者只需要知道这种利用统计的方法处理分词效果好、效率高就可以了。

小结

对于分词来说，统计模型的方法效率比文法分析的方法高，同时效果也要好。这里效率的提升是十分显著的。

此外，我们发现一个优秀算法背后的数学模型是十分简洁优美的。统计模型只需要一个概率不等式组就可以描述，而文法分析模型几乎无法构建一个可读的数学模型。我们在设计算法的时候，要尽可能追求简洁优美的数学模型，从简单粗暴做起，逐步完善完美。正如牛顿爵士所言「真理在形式上总是简单的，而不是复杂含混的」。

最后，文法分析方法是十分容易想到的，十分自然的处理方法，然而这种「自然」也使人误入歧途。这提醒我们，不可固执，不可迷信经验。