《数学之美》

吴军 ——《数学之美》2012年6月第一版 豆瓣评分: 第一版 8.7 第二版 9.0

数学在IT技术中的美,特别是语音识别和搜索引擎方面的美。

豆瓣书评有人说这本书应该叫做《数学应用之美》甚至《信息论应用之美》。

序 前言

欣赏美不是终极目的,更值得追求的是创造美的境界。

系统地阐述了与现代科技领域相关的重要的而数学理论的起源、发展及其作用。

数学不是我们一般联想到的枯燥深奥的符号,而是实实在在源于生活的有趣现象和延伸。数学其实无处不在,而且有一种让人惊叹的韵律和美。

简单性和模块化是软件工程的基石;分布式和容错性是互联网的生命。

数学既是对自然界事实的总结和归纳,又是抽象思考的结果。

数学演化的过程实际上是将我们生活中遇到的具体无知以及他们运动的规律不断抽象化的过程。

2017.11.13 阅读

第1章 文字和语言 vs 数字和信息

数字、文字和自然语言一样,都是信息的载体,它们之间原本有着天然的联系。语言和数学的产生都是为了同一个目的——记录和传播信息。香农发明信息论后,才把数学和信息系统自觉地联系起来。

当语言和词汇多到一定程度的时候,人类仅靠大脑已经记不住所有词汇了。这就如同今天没有人能够记住人类所有的知识一样。高效记录信息的需求就产生了,这便是文字的起源。

2017.11.13 阅读

第2章 自然语言处理——从规则到统计

任何一种语言都是一种编码的方式,而语言的语法规则是解编码的算法。这就是语言的数学本质。
虽然传递信息是动物也能做到的,但是利用语言来传递信息是人类的特质。

1946年,现代电子计算机出现。(以冯诺依曼体系的ENIAC为准)
(冯诺依曼是天才中的天才,而且是超级富二代,上天真是不公平,囧哈)

计算机能处理自然语言,而且处理自然语言的方法和人类一样。

最早提出机器智能设想的是计算机科学之父图灵,1950年在《思想》(Mind)上发表了一篇题为《计算的机器和智能》的论文。提出图灵测试:让人和机器进行交流,如果人无法判断自己交流的对象是人还是机器时,就说明这个机器有智能了。

(图灵是天才 二战破译密码拯救了不计其数的士兵生命)

50年代到70年代,科学家们用电脑模拟人脑,局限在人类学习语言的方式上,20多年的成果几乎为零。

70年代后,重新思考问题,找到基于数学模型和统计的方法,自然语言处理进入第二个阶段。30多年来,这个领域取得了实质性的突破,并且让自然语言处理在很多产品中得以广泛应用。

(几十年的发展,不容易,几代的科学家努力的成果)

1956年夏天,麦卡锡、香农等10人开了一个研讨会《达特茅斯夏季人工智能研究会议》,讨论当时计算机科学尚未解决的问题,包括人工智能、自然语言处理和神经网络等。人工智能这个提法便是在这次会议上提出的。

(牛逼大了,当前最火热的技术是60多年前提出和发展而来的,奋斗几十年的成果)

香农作为信息论的发明人,他在科学史上的地位和图灵是相当的,而且通信领域的最高奖就是以他的名字命名的。

可惜在当时,全世界对自然语言处理得研究都陷入了一个误区,这个会议10个最聪明的脑袋也无法免俗。科学总是不断探索、继承和发展的。

让机器模仿人类,是人类认识的普遍规律,是来自直觉的天真想法,惯性思维。
事实上,怀特兄弟发明飞机靠的是空气动力学而不是仿生学。

今天,机器翻译和语音识别已经做得很好,但并不是靠计算机理解了自然语言,而是靠数学,更准确地说是靠统计

学习西方语言,都要学习它们的语法规则、词性和构词法等,这些规则是人类学习语言(尤其是外语)的好工具。而恰恰这些语法规则又很容易用计算机的算法描述,这就更坚定了大家对基于规则的自然语言处理得信心。

但,语义比语法更难在计算机中表达出来,直到70年代,这方面的工作仍然乏善可陈。

80年代以前,自然语言处理工作中的文法规则都是人写的,这和后来采用机器总结的做法大不相同。直到2000年后,很多公司还是靠人来总结文法规则。

语法分析树很复杂很啰嗦,文法规则的数量级会爆炸,算法复杂度极高。。单纯基于文法规则的分析器是处理不了太过复杂的语句的。描述自然语言的文法和计算机高级程序语言的文法不同。词义和上下文相关。即使能够写出涵盖所有自然语言现象的语法规则集合,用计算机解析它也是相当困难的(coding难度大,机器计算能力有限)。

自然语言的多义性很难用规则来描述,严重依赖上下文,甚至是常识和知识。

70年代以后统计语言学的出现使得自然语言处理重获新生,并取得了今天的非凡成就。关键人物:贾里尼克和他领导的IBM华生实验室。

基于规则的自然语言处理和基于统计的自然语言处理得争执后来还持续了15年左右,90年代初,自然语言处理从规则到统计的过渡才完成。(方向很重要,15年啊不容易,挺残忍的)

70年代,基于统计的方法的核心模型是通信系统加隐马尔可夫模型。输入输出都是一维的符号序列,保持原有次序。有局限。只有出现了基于有向图的统计模型才能很好地解决复杂的句法分析。
过去的二三十年里,随着计算能力的提高和数据量的不断增加,过去看似不可能通过统计模型完成的任务,渐渐都变得可能了,包括很复杂的句法分析。90年代末,通过统计得到的句法规则甚至比语言学家总结的更有说服力。

基于统计的方法代替传统的方法,需要等原有的一批语言学家退休。这在科学上也是经常发生的事。不是所有人都乐意改变自己的观点,无论对错。这些人退休后,科学就会以更快地速度发展。(哈,这就是人性,在哪里领域都逃脱不了的人性。)

到今天,自然语言处理得研究也从单纯的句法分析和语义理解,变成了非常贴近应用的机器翻译、语音识别、文本到数据库自动生成、数据挖掘和知识的获取等等。

总结:
基于统计的自然语言处理方法,在数学模型上和通信是相通的,甚至就是相同的。因此,在数学意义上自然语言处理又和语言的初衷——通信联系在一起了。但是,科学家们认识到这个联系却花了几十年的时间。

2017.11.14 阅读

第3章 统计语言模型

自然语言从它产生开始,逐渐演变成一种上下文相关的信息表达和传递方式,因此让计算机处理自然语言,一个基本的问题就是为自然语言这种上下文相关的特性建立数学模型。这个数学模型就是在自然语言处理中常说的统计语言模型,它是今天所有自然语言处理得基础,并且广泛应用于机器翻译、语音识别、印刷体或手写字体识别、拼写纠错、汉字输入和文献查询。

70年代前,科学家们试图判断文字序列时候合乎文法、含义是否正确。这条路走不通。贾里尼克用一个简单的统计模型非常漂亮地搞定了它。贾里尼克的出发点:一个句子是否合理,就看它的可能性大小如何。用概率来衡量。句子又由一连串特定顺序排列的单词组成。用到条件概率。马尔科夫假设。N元模型,N再大也无法覆盖所有语言现象,这是马尔科夫假设的局限性,要采用其他一些长程的依赖性。

训练统计语言模型的艺术就在于解决好统计样本不足时的概率估计问题。
1953年古德和图灵提出了在统计中相信可靠的统计数据,而对不可信的统计数据打折的一种概率估计方法,同事将折扣出来的那一小部分概率给予未看见的事件。还给出了一个很漂亮的重新估算概率的公式。称为古德——图灵估计

小结:
统计语言模型在形式上非常简单,任何人都很容易理解。但是里面的学问却可以很深,一个专家可以在这方面研究很多年。
数学的魅力就在于将复杂的问题简单化。

2017.11.14 阅读

第4章 谈谈中文分词

语言中的歧义性伴随着语言的发展,困扰了学者们上千年。在中国古代,断句和说文解字从根本上讲,就是消除歧义性,而不同学者之间的看法也显然不同。各种春秋的正义或者对论语的注释,就是各家按照自己的理解消除歧义性。分词的二义性是语言歧义性的一部分。

1990年前后,清华大学郭进博士用统计语言模型成功解决了分词二义性的问题,将汉语分词的错误率降低了一个数量级。

分完词后句子出现的概率最大。穷举所有可能的分词方法计算出每种可能性下句子的概率,计算量是相当大的。可以看成动态规划问题,利用维特比算法快速地找到最佳分词。

中文分词的方法也被应用到英语处理,主要是手写体识别中。因为在识别手写体时,单词之间的空格就不很清楚了。中文分词方法可以帮助判别英语单词的边界。

语言处理得许多数学方法是通用的,和具体的语言无关。

任何方法都有它的局限性,利用统计语言模型进行分词可以取得比人工更好的结果,但也不能做到百分百准确。统计语言模型很大程度上是依照“大众的想法”,或者“多数句子的用法”,而在特定情况下可能是错的。

中文分词现在是一个已经解决了的问题,提高的空间微乎其微,只要采用统计语言模型,效果都查不到哪里去。

小结:
中文分词以统计语言模型为基础,经过几十年的发展和完善,今天基本上可以看做是一个已经解决的问题。
当然不通话的人做的分词器有好有坏,这里面的差别主要在于数据的使用和工程实现的精度。

2017.11.14 阅读

第5章 隐含马尔科夫模型

隐含马尔科夫模型是一个并不复杂的数学模型,是解决大多数自然语言处理问题最为快速、有效的办法。它成功地解决了复杂的语音识别、机器翻译等问题。当我们看到这些复杂的问题是如何通过简单的模型描述和解决时,会不得不由衷地感叹数学模型之妙。

通信的本质是编解码和传输的过程。自然语言处理早期的努力都集中在语法、语义和知识表述上,离通信的原理越走越远,离答案也越来越远。当自然语言处理的问题回归到通信系统中的解码问题时,很多难题都迎刃而解了。

19世纪,概率论的发展从对(相对静态的)随机变量的研究发展到对随机变量的时间序列,即随机过程(动态)的研究。这在哲学的意义上,是人类认识的一个飞跃。但随机过程比随机变量复杂得多。

马尔科夫提出假设来简化问题,随机过程中各个状态的概率分布,只与它的前一个状态有关。给出了很多不好解决的问题的近似解。这就是马尔科夫假设。符合这个假设的随机过程称为马尔科夫链(或马尔科夫过程)。

隐含马尔科夫模型是上述马尔科夫链的一个扩展:任一时刻t的状态s是不可见的。但每个时刻会输出一个符号o,而且o和s相关且仅和s相关。这个称为独立输出假设

基于马尔科夫假设和独立输出假设,可以代入条件概率公式(贝叶斯公式)求解概率。

很多自然语言处理问题是和通信的解码问题等价的,因此它们完全可以由隐含马尔科夫模型来解决。找出概率最大值,可以利用维特比算法。

隐含马尔科夫模型陈宫的应用最早是语音识别。

80年代末李开复博士坚持采用隐含马尔科夫模型的框架,成功地开发了世界上第一个大词汇量连续语音识别系统Sphinx。接下来,隐含马尔科夫模型陆续成功地应用于机器翻译、拼写纠错、手写体识别、图像处理、基因序列分析等很多IT领域,近20多年来,它还广泛应用于股票预测和投资。复杂的语音识别问题居然能如此简单地表述、解决,由衷地感叹数学模型之妙。

小结:
隐含马尔科夫模型最初应用于通信领域,继而推广到语音和语言处理中,成为连接自然语言处理和通信的桥梁。同时,隐含马尔科夫模型也是机器学习主要工具之一。和几乎所有的机器学习的模型工具一样,它需要一个训练算法(鲍姆-韦尔奇算法)和使用时的解码算法(维特比算法),掌握了这两类算法,就基本上可以使用隐含马尔科夫模型这个工具了。

2017.11.15 阅读

第6章 信息的度量和作用

1948年,香农在他的著名论文《通信的数学原理》中提出了信息熵的概念,才解决了信息的度量问题,并且量化出信息的作用。
一条信息的信息量和它的不确定性有着直接的关系。信息量等于不确定性的多少。
32支球队,猜冠军,信息量最大为5 二分法 (球队夺冠概率相同)

信息熵单位是比特
H = -(p1logp1 + p2logp2 + … + p32logp32) (2为底)
上面的值最大不超过5

H(X) = -∑P(x)logP(x)

变量的不确定性越大,熵越大,把它搞清楚所需要的信息量也就越大。
熵跟热力学的熵有很大的相似性。

常用的汉字(一级二级国际)大约有7000字。如果每个字等概率,大约需要13比特表示一个汉字,但汉字是不平衡的。实际上前10%的汉字占常用文本的95%以上。所以不考虑上下文的相关性,只考虑每个汉字的独立概率,每个汉字的信息熵大约8-9比特。再考虑上下文的相关性,每个汉字的信息熵只有5比特左右。所以,一本50万字的中文书,信息量大约是250万比特。用一个好的算法压缩一下,整本书可以存成一个320KB的文件。如果直接用两字节的国际编码存储,大约1M,是压缩文件的3倍。这两个数量的差距,在信息论中称作“冗余度”。

不同语言的冗余度差别很大,汉语在所有语言中冗余度是相对小的。汉语是简洁的语言。

信息是消除系统不确定性的唯一办法。在没有获得任何信息前,一个系统就像是一个黑盒子,引入信息,就可以了解黑盒子系统的内部构造。

几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。

网页搜索本质上也是利用信息消除不确定性的过程。合理利用信息,而不是玩弄什么公式和机器学习算法,是做好搜索的关键。

信息的作用在于消除不确定性,自然语言处理的大量问题就是找相关的信息。

信息熵是信息论的基础,信息论在自然语言处理中扮演着指导性的角色。

香农在信息论中提出了一个“互信息”的概念作为两个随机事件“相关性”的量化度量。

相对熵也用来衡量相关性,但和变量的互信息不同,它用来衡量两个取值为正数的函数的相似性。

利用相对熵,可以得到信息检索中最重要的一个概念:词频率-逆向文档频率(TF-IDF)。

熵、条件熵和相对熵这三个概念与语言模型的关系非常密切。
信息熵正是对不确定性的衡量,因此可以想象信息熵能直接用于衡量统计语言模型的好坏。

贾里尼克从条件熵和相对熵出发,定义了一个称为语言模型复杂度的概念,直接衡量语言模型的好坏。复杂度有很清晰的物理含义,它是在给定上下文的条件下,句子中每个位置平均可以选择的单词数量。一个模型的复杂度越小,每个位置的词就越确定,模型越好。

斯坦福大学托马斯科弗专著《信息论基础》。科弗是当今最权威的信息论专家。

小结:
信息熵不仅是对信息的量化度量,而且是整个信息论的基础。它对于通信、数据压缩、自然语言处理都有很强的指导意义。信息熵的物理含义是对一个信息系统不确定性的度量,在这一点上,它和热力学中熵的概念相同,因为后者是对于一个系统无序的度量。这说明科学上很多看似不同的学科之间也会有很强的相似性。(科学之美)

2017.11.16 阅读

第7章 贾里尼克和现代语言处理

在当今物欲横流的中国社会,学术界浮躁,年轻人浮躁,少数有着远大志向的年轻人实际上是非常孤独的。(吴军先生良心点评)

事实上,现代语音识别和自然语言处理确实是跟贾里尼克的名字紧密联系在一起的。

犹太富二代,后来二战家道没落,父亲死于集中营,小时候学习很差,在布拉格流浪,后来努力读书,移民到美国。原本想成为律师、医生、后来去麻省理工电机工程。碰到了信息论的鼻祖香农和语言学大师雅各布森。后来确立利用信息论解决语言问题的研究方向。贾里尼克有幸在年轻的时候遇到了几位大师的指点,在研究境界上比同龄人高出一筹。后面遇到让他反感的一些语言学家,他深痛恶觉,甚至说:“我每开除一名语言学家,我的语音识别系统识别率就会提高一点。”这句话后来在业界广为流传,为每个搞语音识别和语言处理得人所熟知。(说这话得有多么大的仇恨,囧,不过结果证明他这话也貌似没毛病)

在康奈尔大学十年磨一剑,潜心研究信息论,终于悟出自然语言的真谛。后来去领导IBM华生实验室。贾里尼克组件的团队大师阵容空前绝后。在那贾里尼克等人提出统计语音识别的框架结构。贾里尼克之前,科学家们把语音识别问题当作人工智能和模式匹配问题,而贾里尼克把它当成通信问题。并用两个隐含马尔可夫模型(声学模型和语言模型)把语音识别概括得清清楚楚。这个框架对至今的语音和语言处理有着深远的影响,奠定了今天自然语言处理的基础。

IBM的科学家最初是通过电传业务的文本开始进行自然语言处理研究的。

IBM有足够强大的计算功能和数据,贾里尼克等人在领域的多年理论研究,天时地利人和。诞生了统计自然语言。

BCJR算法、维特比算法,今天数字通信中应用得最广的两个算法。

后来团队多数去了华尔街,赚够了花不完的钱。但他晚年去约翰霍普金斯大学组建世界著名的CLSP实验室。短短两三年成为一流的研究中心。带出了一批杰出的科学家和学生,确立了他在这个学术领域的世界级领导地位。

一个闲不住的人,70岁后依然头脑敏锐,并每天按时上班,周末经常到实验室加班,后来心脏病发作在办公桌前去世。

贾里尼克提高了吴军在学术上的境界。

学习是一辈子的事,贾里尼克坚持到生命最后一天。令人敬佩的科学家。

2017.11.20 阅读

第8章 简单之美——布尔代数和搜索引擎的索引

技术分为术和道,具体的做事方法是术,做事的原理和原则是道。这本书的目的是讲道而不是术。
技术中,追求术的人一辈子很辛苦,只有掌握了技术的本质和精髓才能一直游刃有余。(大师的境界就是高)
真正做好一件事没有捷径,需要一万小时的专业训练和努力。

搜索引擎要做的事:自动下载尽可能多的网页;建立快速有效的索引;根据相关性对网页进行公平准确地排序。
搜索的道:下载、索引和排序。

索引最基础,也最重要。

直到1938年香农在他的硕士论文中指出用布尔代数来实现开关电路,才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算,加减乘除、乘方、开方等等,都能转换成二值的布尔运算。(史上分量最重的硕士论文不是盖的)

逻辑推理和计算合二为一。

布尔代数对于数学的意义等同于量子力学对于物理的意义,它们将我们对世界的认识从连续状态扩展到离散状态。现代物理的研究成果表明,我们的世界实实在在是量子化的而不是连续的。我们的宇宙的基本粒子数目是有限的,而且远比google数(10的100次方)要小得多。

计算机做布尔运算是非常非常快的。

为了保证对任何搜索都能提供相关的网页,主要的搜索引擎都是对所有的词进行索引。
保守地假设互联网有100亿个有意义的网页,词汇表大小30万,索引大小至少是3000万亿。考虑到大多数词只出现在一部分文本中,压缩比100:1,也是30万亿的量级。为了网页排名方便,索引中还需存有大量附加信息,诸如每个词出现的位置、次数等等。因此,整个索引就变得非常之大。这些索引通过分布式的方式存储到不同的服务器上。普遍的做法就是根据网页的序号将索引分成很多份(Shards),分别存储在不同的服务器中。每当接受一个查询时,这个查询就被分发到许许多多的服务器中,同时并行处理用户请求,并把结果送到主服务器合并处理,最后将结果返回给用户。

即便是Google,对数据也会感到压力。因此,根据需要网页的重要性、质量和访问的频率建立常用和非常用等不同级别的索引。常用的索引需要访问速度快、附件信息多,更新也快;非常用的要求就低多了。

小结:
布尔代数非常简单,但对数学和计算机发展得意义重大,它不仅把逻辑和数学合二为一,而且给了我们一个全新的视角看待世界,开创了今天数字化的时代。牛顿说过:“人们发觉真理在形式上从来是简单的,而不是复杂和含混的。”

2017.11.22 阅读

第9章 图论和网络爬虫

离散数学是当代数学的一个重要分支,也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。
欧拉证明七桥问题,是图论的开始。1736年。

一个图的度要是偶数才能每条边不重复地遍历一遍回到原点。

BFS vs DFS

网络爬虫对网页的遍历次序不是简单的BFS或DFS,而是有一个相对复杂的下载优先级排序的方法。管理这个优先级别排序的系统称为调度系统。未下载放在优先级队列里,采用这种方式遍历整个互联网,在工程上更像BFS。因此,爬虫中BFS成分多一些。

互联网的出现,使得图论有了用武之地。很多数学方法就是这样,看上去没有什么实际用途,但随着时间的推移会一下子派上用场。这恐怕是世界上还有很多人毕生研究数学的原因。

2017.11.23 阅读

第10章 PageRank——Google的民主表决式网页排名技术

真正找到计算网页自身质量的完美数学模型的是Google的创始人拉里佩奇和谢尔盖布林。

在互联网上,如果一个网页被很多其他网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。这就是PageRank的核心思想。

网页排名高的网站贡献的链接权重大。

算法思想来自佩奇。布林用矩阵相乘并迭代排名解决了算法的难题。

2003年,Google的工程师发明了MapReduce这个并行计算的工具,PageRank的并行计算完全自动化,大大缩短了计算时间,网页排名的更新周期比以前短了很多。

PageRank在Google所有的算法中依然是至关重要的。在学术界,这个算法被公认为是文献检索中最大的贡献之一。

佩奇也因为这个算法在30岁时当选为美国工程院院士,是继乔布斯和盖茨之后又一位当选院士的辍学生。

2017.11.23 阅读

第11章 如何确定网页和查询的相关性

TF: Term Frequency 关键词的频率/单文本词频
IDF: Inverse Document Frequency 逆文本频率指数

TF-IDF的概念被公认为信息检索中最重要的发明。

现在的搜索引擎对TF-IDF进行了不少细微的优化,使得相关性的度量更加准确了。如果结合网页排名算法(PageRank),那么给定一个查询,有关网页的综合排名大致由相关性和网页排名的乘积决定。

一个词的信息量越多,TF-IDF值越大。跟信息量结合起来了。(科学的共通性)

TF-IDF是对搜索关键词的重要性的度量,从理论上讲,它有很强的理论根据。现在各家搜索引擎对关键词重要性的度量,都是在TF-IDF的基础上有些改进和微调。但是,在原理上TF-IDF相差不远。

2017.11.23 阅读

第12章 地图和本地搜索的最基本技术——有限状态机和动态规划

2008.09.23,Google、T-Mobile和HTC第一款Android的3G手机G1。杀手级功能是利用全球卫星定位系统实现全球导航。

地址的识别(地址是否有效)—— 有限状态机(特殊的有向图)

输入的地址不太标准或有错别字(支持模糊匹配)—— 基于概率的有限状态机(和离散的马尔可夫链基本上等效)

中国公路网——加权图,权重对应于距离或行车时间、过路费等

图论常见问题,找出一个图中给定两点的最短路径笨方法是所有可能的路线看一遍,然而这个复杂度是指数级别的,每增加一个城市,复杂度扩大一倍。解决方法——建立动态规划的数学模型,正确的数学模型可以将一个计算量看似很大的问题的计算复杂度大大降低。这是数学的妙用。(算法复杂度对应数学模型)

有限状态机和动态规划的应用非常广泛,远不止识别地址、导航等地图服务相关领域。还有语音识别、拼写和语法纠错、拼音输入法、工业控制、生物序列分析等。

2017.11.24 阅读

第13章 Google AK-47的设计者——阿米特辛格博士

一个好的算法应该像AK47那样,简单、有效、可靠性好而且容易读懂(或者说易操作)。
先解决用户80%的问题,再慢慢解决剩下的20%的问题。许多失败并不是因为人不优秀,而是做事情的方法不对。一开始追求大而全的解决方案,之后长时间不能完成,最后不了了之。

在Google,辛格一直坚持寻找简单有效的解决方案,因为他奉行简单的哲学。

辛格总是能找到那些简单有效的方法,不是靠直觉,更不是撞大运,这首先靠他丰富的研究经验。

2012年,辛格当选美国工程院院士,并出任主管Google搜索的高级副总裁。

2017.11.24 阅读

第14章 余弦定理和新闻的分类

余弦定理与新闻分类有着紧密的联系。
计算机根本读不懂新闻,虽然一些商业人士和爱炫耀自己才学的计算机专家宣称计算机能读懂新闻。计算机本质上只能做快速计算。
(吴先生很实在,敢讲真话)

先把文字的新闻变成可以计算的一组数字,然后设计一个算法来算出任意两篇新闻的相似性。

和新闻主题有关的实词TF-IDF值很大。

所有词的TF-IDF值组成特征向量。如果两篇新闻属于同一类,那么它们的特征向量在某几个维度的值都比较大,其他维度的值都比较小。向量的方向比大小有参考价值,方向接近,说明用词比例基本一致。两个向量的夹角越小,是同一个新闻分类的可能性越大。而计算向量的夹角就自然用到余弦定理了。

美国人做事的一个习惯:美国人总是倾向于用机器代替人工来完成任务。虽然短期要做一些额外的工作,但长期来看可以节省很多时间。

大数据量时的余弦计算很慢很慢。简化方法:避免重复计算、只考虑向量中的非零元素、删除虚词。

位置的权重不同。

本章介绍得这种新闻归类方法,准确性很好,适合于百万这个数量级,亿级的就很慢了。

2017.12.04 阅读

第15章 矩阵运算和文本处理中的两个分类问题

用余弦定理(向量的方向)两两计算新闻的分类问题,需要进行很多次迭代,耗时特别长,尤其新闻的数量特别大,同时词表也很大的时候。

一次性就能把所有的相关性计算出来:运用矩阵运算中的奇异值分解(SVD)。

奇异值分解就是把一个大矩阵,分解成三个小矩阵相乘。元素的数量和存量量都骤减。

2007年,Google中国的张智威博士带队实现了奇异值分解的并行算法,这是Google中国对世界的一个贡献。

奇异值分解得到的分类结果略显粗糙,适合处理超大规模文本的粗分类。然后在粗分类的基础上用计算向量余弦的方法进行几次迭代,得到比较精确的结果。充分利用了两种方法的优势。

2017.12.04 阅读

第16章 信息指纹及其应用

信息指纹可以理解成将一段信息(文字、图片、音频、视频等)随机地映射到一个多维的二进制空间中的一个点(一个二进制数字)。只要这个随机函数做得好,那么不同的信息对应的这些点不会重合,因此这些二进制的数字就成了原来信息所具有的独一无二的指纹。

为了防止重复下载同一个网页,需要在哈希表中记录已经访问过的网址。但哈希表中直接存储字符串的网址,浪费存储空间和查找的时间。解决方案是存储映射过后的等长的随机数。这样存储空间小了很多,查找也快了很多。

伪随机数产生器算法(PRNG):通过它将任意很长的整数转换成特定长度的伪随机数。常用的有梅森旋转算法。

信息指纹的用途远不止网址的消重,由于它的特征是不可逆性,常用语密码加密和网络加密传输。为了安全性,一些网站(比如银行)采用https,并且用户访问产生的cookie本身也要加密。

从加密的角度讲梅森旋转算法还不够好,它产生的随机数还有一定的相关性。在互联网上加密要使用基于加密的伪随机数产生器(CSPRNG)。常用的算法有MD5和SHA-1等标准,它们可以将不定长的信息变成定长的128位或160位二进制随机数。指的一提的是SHA-1以前被认为是没有漏洞的,现在已经被中国的王小云教授证明存在漏洞。但大家不必恐慌,因为这和黑客能真正攻破你的注册信息是两回事。

怎么判断两个集合是否相同?

笨方法,一一比较,复杂度O(N^2)

稍微好,排序后顺序比较,复杂度O(NlogN)

同样稍好的方案:将一个集合放于哈希表再遍历另外一个集合,元素一一比较,复杂度O(N),
但额外使用了O(N)的空间,而且代码实现复杂。

最佳方案:计算两个集合的指纹,然后直接比较。加法的交换律,保证顺序无关,集合相同,指纹之和一定相同。不同元素的指纹相同的概率极低,工程上可以忽略不计。复杂度O(N),不需要额外的空间。

视频相同?

关键帧的提取和特征的提取,如同主题词对于新闻。用一组信息指纹来表示关键帧。盗版视频上传后广告分成属于原版作者,Youtube从技术上最大限度减少了盗版和拷贝。

2017.12.21 阅读

第17章 由电视剧《暗算》所想到的——谈谈密码学的数学原理

第18章 闪光的不一定是金子——谈谈搜索引擎反作弊问题

第19章 谈谈数学模型的重要性

第20章 不要把鸡蛋放到一个篮子里——谈谈最大熵模型

第21章 拼音输入法的数学原理

第22章 自然语言处理的教父马库斯和他的优秀弟子们

第23章 布隆过滤器

第24章 马尔科夫链的扩展——贝叶斯网络

第25章 条件随机场和句法分析

第26章 维特比和他的维特比算法

第27章 再谈文本自动分类问题——期望最大化算法

第28章 逻辑回归和搜索广告

第29章 各个击破算法和Google云计算的基础