作者：路彦雄
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
文本上的算法——深入浅出自然语言处理试读：
前言
现在还记得我当年刚毕业踏入工作的情景——专业知识几乎一张白纸的我，学习欲望非常强烈，工作之余就是看各种书籍，翻阅各种论文，一开始还是在博客上记笔记，后来转到了印象笔记来记录。这些笔记都是我成长的见证，也是我个人的一些总结和思考，但却总是零零散散的，所以我想整理成正式一点的文档，方便查阅。这些知识（去除掉不可公开的内容后）在大家平常的学习和工作中都会用到，整理成文档也可以作为别人的一种参考资料；而且我也希望除了必不可少的公式外，尽量以更口语化的方式表达出来，抛弃繁琐的证明，触及算法的核心，尽可能达到深入浅出。当我把文档整理完成后，就放到了网上，竟然收到了网友的一致好评，算是意外的收获，也令我非常高兴。于是，我就丰富完善了一些内容，写成了这本书。站在更高层面来说，自然语言处理还处在初级阶段，离人理解语言还是相差好远，所以我也希望本书能唤起更多人的兴趣，来共同提高自然语言处理技术的水平。
本书的读者对象包括计算机相关专业的学习者，也包括从事机器学习或者自然语言处理的工作人员，当然，我也希望更多的人来翻阅一下，大致了解文本技术的轮廓并从中受益。
本书主要分两大部分：理论篇和应用篇。第一部分是理论篇，包括前3章。第1章和第2章是为第3章打基础，其中第1章介绍的是一些基础的数学知识，第2章介绍的是最优化理论知识，第3章具体介绍一些机器学习的相关知识。
第二部分是应用篇，包括第4章到第8章。第4章介绍计算性能，算是更偏工程的唯一一章；第5章介绍的是文本处理时的一些基本术语，其中相似度计算的内容非常重要；第6章介绍的是一个工业搜索引擎需要哪些技术点；第7章讲解的是推荐系统的知识点；第8章介绍理解语言的难点，包括两大知识点——自然语言处理和对话系统，当然其中也讨论了人们对人工智能一些看法。
首先非常感谢我的父母和家人的支持，让我进入了一个蓬勃发展的互联网行业，让我有幸见证这个行业的发展，也能为这个行业贡献一份绵薄之力。非常感谢我的老板、同事和朋友们，和他们的交流对我有很大的启发和帮助。非常感谢出版社的编辑对本书的认真修改。最后，感谢在工作和生活中帮助过我的所有人，谢谢你们！
虽然花了一些时间和精力去核对书中的内容，但因为时间仓促，本人水平有限，书中难免会有一些错误和纰漏。如果大家发现什么问题，恳请不吝指出，相关信息可反馈到我的邮箱yanxionglu@gmail.com。|理论篇|● 第1章 你必须知道的一些基础知识● 第2章 我们生活在一个寻求最优解的世界里● 第3章 让机器可以像人一样学习第1章你必须知道的一些基础知识
机器学习是解决很多文本任务的基本工具，本书自然会花不少篇幅来介绍机器学习。要想搞明白什么是机器学习，一定要知道一些概率论和信息论的基本知识，本章就简单回顾一下这些知识（如果读者已经掌握了这些基础知识，可以跳过本章，继续阅读）。1.1 概率论
概率就是描述一个事件发生的可能性。我们生活中绝大多数事件都是不确定的，每一件事情的发生都有一定的概率（确定的事件就是其概率为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。
概率分布的方差定义如下
可以看出，方差是表示随机变量偏离期望的大小，所以它是衡量数据的波动性的，方差越小表示数据越稳定，反之，方差越大表示数据的波动性越大。
另外，你还需要知道的几个常用的概率分布：均匀分布、正态分布、二项分布、泊松分布、指数分布，等等。你还可以了解一下矩阵的知识，因为所有公式都可以表示成矩阵形式。1.2 信息论
假如一个朋友告诉你外面下雨了，你也许觉得不怎么新奇，因为下雨是很平常的一件事情，但是如果他告诉你他见到外星人了，那么你就会觉得很好奇：真的吗？外星人长什么样？同样两条信息，一条信息量很小，一条信息量很大，很有价值，那么怎么量化这个价值呢？这就需要信息熵，一个随机变量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来计算。1.3 贝叶斯法则
贝叶斯法则是概率论的一部分，之所以单独拿出来介绍，是因为它真的很重要。它是托马斯•贝叶斯生前在《机遇理论中一个问题的解》（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：A, A,…, A（A表示词），那么我们就12ki是求条件概率p(A | S)达到最大值的那个分词结果。这个概率不好求出，这时贝叶斯法则就用上派场了，根据贝叶斯公式改写为
显然，p(S)是一个常数，那么公式相当于改写成
其中，p(S | A)表示(A)这种分词生成句子S的可能性；p(A)表示(A)这种分词本身的可能性。
下面的事情就很简单了。对于每种分词计算一下p(S | A)p(A)这个值，然后取最大的，得到的就是最靠谱的分词结果。比如“学历史知识”（用S表示）可以分为如下两种（当然，实际情况就不止两种情况了）：“学历\史\知识”（用A表示，A=学历，A=史，A=知识）和123“学/历史/知识”（用B表示，B=学，B=历史，B=知识），那么我们123分别计算一下p(S | A)p(A)和p(S | B)p(B)，哪个大，就说明哪个是好的分词结果。
但是这个公式并不是很好计算，可以认为就是1，因为由必然能生成S，那么剩下的问题就是如何计算。
在数学中，要想简化数学模型，就要利用假设。我们假设句子中一个词的出现概率只依赖于它前面的那个词（当然可以依赖于它前面的 m 个词），这样，根据全概率公式
就可以改写为
接下来的问题就是如何估计。然而，，这个问题变得很简单，只要数一数（）这对词在统计的文本中前后相邻出现了多少次，以及A本身在同样的文本中出现了i−1多少次，然后用两个数除以它就可以了。
上面计算的过程其实就是统计语言模型，然而真正在计算语言模型的时候，要对公式进行平滑操作。Zipf定律指出：一个单词出现的频率与它在频率表里的排名（按频率从大到小）成反比。这说明对于语言中的大多数词，它们在语料中的出现是稀疏的，数据稀疏会导致所估计的分布不可靠，更严重的是会出现零概率问题，因为的值有可能为0，这样整个公式的值就为0，而这种情况是很不公平的，所以平滑解决了这种零概率问题。具体的平滑算法读者可以参考论文《An Empirical Study of Smoothing Techniques for Language Modeling》。
然而在实际系统中，由于性能等因素，很少使用语言模型来分词消歧，而是使用序列标注模型（后面章节会讲到）、语料中词与词的共现信息、词的左熵（该词左边出现过的所有词的信息熵之和）和右熵（该词右边出现过的所有词的信息熵之和），以及一些词典等方法来消歧。新词发现技术也和这个技术差不多。1.4 问题与思考
1．熵、相对熵和交叉熵的物理意义是什么？
试读结束[说明：试读内容隐藏了图片]