详情
本书主要围绕自然语言处理展开，包括理论篇和应用篇，理论篇主要讲解一些基础知识，机器学习等，应用篇就会围绕自然语言处理的任务来讲解，比如搜索引擎、推荐系统、对话系统等等。本书主要分两大部分：第一部分是理论篇，主要介绍机器学习的基础和一些具体算法；第二部分应用篇，主要是一些NLP的应用，如搜索引擎原理是什么？它为什么要建索引？有什么理论基础吗？
书名：文本上的算法——深入浅出自然语言处理
ISBN：978-7-115-47587-9
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
编 著 路彦雄
责任编辑 陈冀康
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书结合作者多年学习和从事自然语言处理相关工作的经验，力图用生动形象的方式深入浅出地介绍自然语言处理的理论、方法和技术。本书抛弃掉繁琐的证明，提取出算法的核心，帮助读者尽快地掌握自然语言处理所必备的知识和技能。
本书主要分两大部分。第一部分是理论篇，包含前3章内容，主要介绍一些基础的数学知识、最优化理论知识和一些机器学习的相关知识。第二部分是应用篇，包含第4章到第8章，分别针对计算性能、文本处理的术语、相似度计算、搜索引擎、推荐系统、自然语言处理和对话系统等主题展开介绍和讨论。
本书适合从事自然语言处理相关研究和工作的读者参考，尤其适合想要了解和掌握机器学习或者自然语言处理技术的读者阅读。
现在还记得我当年刚毕业踏入工作的情景——专业知识几乎一张白纸的我，学习欲望非常强烈，工作之余就是看各种书籍，翻阅各种论文，一开始还是在博客上记笔记，后来转到了印象笔记来记录。这些笔记都是我成长的见证，也是我个人的一些总结和思考，但却总是零零散散的，所以我想整理成正式一点的文档，方便查阅。这些知识（去除掉不可公开的内容后）在大家平常的学习和工作中都会用到，整理成文档也可以作为别人的一种参考资料；而且我也希望除了必不可少的公式外，尽量以更口语化的方式表达出来，抛弃繁琐的证明，触及算法的核心，尽可能达到深入浅出。当我把文档整理完成后，就放到了网上，竟然收到了网友的一致好评，算是意外的收获，也令我非常高兴。于是，我就丰富完善了一些内容，写成了这本书。站在更高层面来说，自然语言处理还处在初级阶段，离人理解语言还是相差好远，所以我也希望本书能唤起更多人的兴趣，来共同提高自然语言处理技术的水平。
本书的读者对象包括计算机相关专业的学习者，也包括从事机器学习或者自然语言处理的工作人员，当然，我也希望更多的人来翻阅一下，大致了解文本技术的轮廓并从中受益。
本书主要分两大部分：理论篇和应用篇。第一部分是理论篇，包括前3章。第1章和第2章是为第3章打基础，其中第1章介绍的是一些基础的数学知识，第2章介绍的是最优化理论知识，第3章具体介绍一些机器学习的相关知识。
第二部分是应用篇，包括第4章到第8章。第4章介绍计算性能，算是更偏工程的唯一一章；第5章介绍的是文本处理时的一些基本术语，其中相似度计算的内容非常重要；第6章介绍的是一个工业搜索引擎需要哪些技术点；第7章讲解的是推荐系统的知识点；第8章介绍理解语言的难点，包括两大知识点——自然语言处理和对话系统，当然其中也讨论了人们对人工智能一些看法。
首先非常感谢我的父母和家人的支持，让我进入了一个蓬勃发展的互联网行业，让我有幸见证这个行业的发展，也能为这个行业贡献一份绵薄之力。非常感谢我的老板、同事和朋友们，和他们的交流对我有很大的启发和帮助。非常感谢出版社的编辑对本书的认真修改。最后，感谢在工作和生活中帮助过我的所有人，谢谢你们！
虽然花了一些时间和精力去核对书中的内容，但因为时间仓促，本人水平有限，书中难免会有一些错误和纰漏。如果大家发现什么问题，恳请不吝指出，相关信息可反馈到我的邮箱yanxionglu@gmail.com。
机器学习是解决很多文本任务的基本工具，本书自然会花不少篇幅来介绍机器学习。要想搞明白什么是机器学习，一定要知道一些概率论和信息论的基本知识，本章就简单回顾一下这些知识（如果读者已经掌握了这些基础知识，可以跳过本章，继续阅读）。
概率就是描述一个事件发生的可能性。我们生活中绝大多数事件都是不确定的，每一件事情的发生都有一定的概率（确定的事件就是其概率为100%而已）。天气预报说明天有雨，那么它也只是说明天下雨的概率很大。再比如掷骰子，我把一个骰子掷出去，问某一个面朝上的概率是多少？在骰子没有做任何手脚的情况下，直觉告诉你任何一个面朝上的概率都是1/6，如果你只掷几次，是很难得出这个结论的，但是如果你掷上1万次或更多，那么必然可以得出任何一个面朝上的概率都是1/6的结论。这就是大数定理：当试验次数（样本）足够多的时候，事件出现的频率无限接近于该事件真实发生的概率。
假如我们用概率函数来表示随机变量x∈X的概率分布，那么就要满足如下两个特性
联合概率p(x,y)表示两个事件共同发生的概率。假如这两个事件相互独立，那么就有联合概率p(x,y) = p(x)p(y)。
条件概率p(y | x)是指在已知事件x发生的情况下，事件y发生的概率，且有p(y | x) = p(x,y)/p(x)。如果这两个事件相互独立，那么p(y | x)与p(y)相等。
联合概率和条件概率分别对应两个模型：生成模型和判别模型。我们将在下一章中解释这两个模型。
概率分布的均值称为期望，定义如下
期望就是对每个可能的取值x，与其对应的概率值p(x)，进行相乘求和。假如一个随机变量的概率分布是均匀分布，那么它的期望就等于一个固定的值，因为它的概率分布p(x)=1/N。
概率分布的方差定义如下
可以看出，方差是表示随机变量偏离期望的大小，所以它是衡量数据的波动性的，方差越小表示数据越稳定，反之，方差越大表示数据的波动性越大。
另外，你还需要知道的几个常用的概率分布：均匀分布、正态分布、二项分布、泊松分布、指数分布，等等。你还可以了解一下矩阵的知识，因为所有公式都可以表示成矩阵形式。
假如一个朋友告诉你外面下雨了，你也许觉得不怎么新奇，因为下雨是很平常的一件事情，但是如果他告诉你他见到外星人了，那么你就会觉得很好奇：真的吗？外星人长什么样？同样两条信息，一条信息量很小，一条信息量很大，很有价值，那么怎么量化这个价值呢？这就需要信息熵，一个随机变量X的信息熵定义如下
信息越少，事件（变量）的不确定性越大，它的信息熵也就越大，搞明白该事件所需要的额外信息就越多，也就是说搞清楚小概率事件所需要的额外信息较多，比如说，为什么大多数人愿意相信专家的话，因为专家在他专注的领域了解的知识（信息量）多，所以他对某事件的看法较透彻，不确定性就越小，那么他所传达出来的信息量就很大，听众搞明白该事件所需要的额外信息量就很小。总之，记住一句话：信息熵表示的是不确定性的度量。信息熵越大，不确定性越大。
联合熵的定义为
联合熵描述的是一对随机变量X和Y的不确定性。
条件熵的定义为
条件熵衡量的是：在一个随机变量X已知的情况下，另一个随机变量Y的不确定性。
相对熵（又叫KL距离，信息增益）的定义如下
相对熵是衡量相同事件空间里两个概率分布（函数）的差异程度（而前面的熵衡量的是随机变量的关系）。当两个概率分布完全相同时，它们的相对熵就为0，当它们的差异增加时，相对熵就会增加。相对熵又叫KL距离，但是它不满足距离定义的3个条件中的两个：（1）非负性（满足）；（2）对称性（不满足）；（3）三角不等式（不满足）。它的物理意义就是如果用q分布来编码p分布（一般就是真实分布）的话，平均每个基本事件编码长度增加了多少比特。
两个随机变量X和Y，它们的互信息定义为
互信息是衡量两个随机变量的相关程度，当X和Y完全相关时，它们的互信息就是1；反之，当X和Y完全无关时，它们的互信息就是0。
对于x和y两个具体的事件来说，可以用点互信息（Pointwise Mutual Information）来表示它们的相关程度。后面的章节就不做具体区分，都叫作互信息。
互信息和熵有如下关系
互信息和KL距离有如下关系
如果X和Y完全不相关，
，则
，互信息也为0。可以看出互信息是KL距离的期望。
交叉熵的定义如下
它其实就是用分布q来表示X的熵，也就是说用分布q来编码X（它的完美分布是p）需要多少比特。
好了，介绍了这么多概念公式，那么我们来个实际的例子，在文本处理中，有个很重要的数据就是词的互信息。前面说了，互信息是衡量两个随机变量（事件）的相关程度，那么词的互信息，就是衡量两个词的相关程度，例如，“计算机”和“硬件”的互信息就比“计算机”和“杯子”的互信息要大，因为它们更相关。那么如何在大量的语料下统计出词与词的互信息呢？公式中可以看到需要计算3个值：p(x)、p(y)和p(x,y)。它们分别表示x独立出现的概率，y独立出现的概率，x和y同时出现的概率。前两个很容易计算，直接统计词频然后除以总词数就知道了，最后一个也很容易，统计一下x和y同时出现（通常会限定一个窗口）的频率，除以所有无序对的个数就可以了。这样，词的互信息就计算出来了，这种统计最适合使用Map-Reduce来计算。
贝叶斯法则是概率论的一部分，之所以单独拿出来介绍，是因为它真的很重要。它是托马斯•贝叶斯生前在《机遇理论中一个问题的解》（An Essay Towards Solving a Problem in Doctrine of Chance）中提出的一个当时叫“逆概率”问题。贝叶斯逝世后，由他的一个朋友替他发表了该论文，后来在这一理论基础上，逐渐形成了贝叶斯学派。
贝叶斯法则的定义如下
p(x | y)称为后验概率，p(y | x)称为似然概率，p(x)称为先验概率，p(y)一般称为标准化常量。也就是说，后验概率可以用似然概率和先验概率来表示。这个公式非常有用，很多模型以它为基础，例如贝叶斯模型估计、机器翻译、Query纠错、搜索引擎等等。在后面的章节中，大家经常会看到这个公式。
好了，这个公式看着这么简单，到底能有多大作用呢？我们先拿中文分词来说说这个公式如何应用的。
中文分词在中文自然语言处理中可以算是最底层、最基本的一个技术了，因为几乎所有的文本处理任务都要首先经过分词这步操作，那么到底要怎么对一句话分词呢？最简单的方法就是查字典，如果这个词在字典中出现了，那么就是一个词。当然，查字典要有一些策略，最常用的就是最大匹配法。最大匹配法是怎么回事呢？举个例子来说，要对“中国地图”来分词，先拿“中”去查字典，发现“中”在字典里（单个词肯定在字典里），这时肯定不能返回，要接着查，“中国”也在字典里，然后再查“中国地”，发现它没在字典里，那么“中国”就是一个词了；然后以同样的方法处理剩下的句子。所以，最大匹配法就是匹配在字典中出现的最长的词。查字典法有两种：正向最大匹配法和反向最大匹配法，一个是从前向后匹配，一个是从后向前匹配。但是查字典法会遇到一个自然语言处理中很棘手的问题：歧义问题。如何解决歧义问题呢？
我们就以“学历史知识”为例来说明，使用正向最大匹配法，我们把“学历史知识”从头到尾扫描匹配一遍，就被分成了“学历\史\知识”，很显然，这种分词不是我们想要的结果；但是如果我们使用反向最大匹配法从尾到头扫描匹配一遍，那就会分成“学/历史/知识”，这才是我们想要的分词结果。可以看出用查字典法来分词，就会存在二义性，一种解决办法就是分别从前到后和从后到前匹配。在这个例子中，我们分别从前到后和从后到前匹配后，将得到“学历\史\知识”和“学/历史/知识”，很显然，这两个分词都有“知识”，那么说明“知识”是正确的分词，然后就看“学历\史”和“学/历史”哪个是正确的。从我们的角度看，很自然想到“学/历史”是正确的，为什么呢？因为（1）在“学历\史”中“史”这个词单独出现的概率很小，在现实中我们几乎不会单独使用这个词；（2）“学历”和“史”同时出现的概率也要小于“学”和“历史”同时出现的概率，所以“学/历史”这种分词将会胜出。这只是我们人类大脑的猜测，有什么数学方法证明呢？有，那就是基于统计概率模型。
我们的数学模型表示如下：假设用户输入的句子用S表示，把S分词后可能的结果表示为A：A1, A2,…, Ak（Ai表示词），那么我们就是求条件概率p(A | S)达到最大值的那个分词结果。这个概率不好求出，这时贝叶斯法则就用上派场了，根据贝叶斯公式改写为
显然，p(S)是一个常数，那么公式相当于改写成
其中，p(S | A)表示(A)这种分词生成句子S的可能性；p(A)表示(A)这种分词本身的可能性。
下面的事情就很简单了。对于每种分词计算一下p(S | A)p(A)这个值，然后取最大的，得到的就是最靠谱的分词结果。比如“学历史知识”（用S表示）可以分为如下两种（当然，实际情况就不止两种情况了）：“学历\史\知识”（用A表示，A1=学历，A2=史，A3=知识）和“学/历史/知识”（用B表示，B1=学，B2=历史，B3=知识），那么我们分别计算一下p(S | A)p(A)和p(S | B)p(B)，哪个大，就说明哪个是好的分词结果。
但是
这个公式并不是很好计算，
可以认为就是1，因为由
必然能生成S，那么剩下的问题就是如何计算
。
在数学中，要想简化数学模型，就要利用假设。我们假设句子中一个词的出现概率只依赖于它前面的那个词（当然可以依赖于它前面的 m 个词），这样，根据全概率公式
就可以改写为
接下来的问题就是如何估计
。然而，
，这个问题变得很简单，只要数一数（
）这对词在统计的文本中前后相邻出现了多少次，以及Ai−1本身在同样的文本中出现了多少次，然后用两个数除以它就可以了。
上面计算
的过程其实就是统计语言模型，然而真正在计算语言模型的时候，要对公式进行平滑操作。Zipf定律指出：一个单词出现的频率与它在频率表里的排名（按频率从大到小）成反比。这说明对于语言中的大多数词，它们在语料中的出现是稀疏的，数据稀疏会导致所估计的分布不可靠，更严重的是会出现零概率问题，因为
的值有可能为0，这样整个公式的值就为0，而这种情况是很不公平的，所以平滑解决了这种零概率问题。具体的平滑算法读者可以参考论文《An Empirical Study of Smoothing Techniques for Language Modeling》。
然而在实际系统中，由于性能等因素，很少使用语言模型来分词消歧，而是使用序列标注模型（后面章节会讲到）、语料中词与词的共现信息、词的左熵（该词左边出现过的所有词的信息熵之和）和右熵（该词右边出现过的所有词的信息熵之和），以及一些词典等方法来消歧。新词发现技术也和这个技术差不多。
1．熵、相对熵和交叉熵的物理意义是什么？
2．贝叶斯法则的优缺点是什么，有哪些应用？
