早在前几个月我在台湾的时候，就听说《数学之美》是一本非常不错的书，也正好是我喜欢的类型，一直想买。回到北京之后的第一件事就是把我这半年积攒的书单全部兑现，其中包括《数学之美》和《浪潮之巅》。看了之后大叫过瘾，让我好好享受了一回数学之美。

 

文字和数字的起源

很久以前人类以不同的叫声表示不同的信息，达到彼此交流的目的，当所要表达的信息太多时，叫声已经不够用了，于是文字产生了。

 

文字：知道“”石碑的典故。

信息冗余的重要性：当石碑经历风吹日晒，一部分文字被腐蚀掉时，还有另一部分重复的文字作为备份，可以还原石碑的信息。类似的还有人体的DNA，在人体当中，有99%的DNA是无效的，正是这99%保证了人类的正常繁衍，当遇人类遇到辐射时，DNA发生变异的概率是1%.

 

数字：进制的产生

为了表达大数，不同的文明产生了不同的数字表示方法，最终只有使用10进制的文明生存了下来。

10进制：古中国、古印度、阿拉伯

12进制：印度、斯里兰卡

20进制：玛雅，玛雅文明失败的原因之一就是进制太复杂，不利于科学进步，咱们现在要背九九乘法表，他们背的是361路围棋棋盘。

单位进制：罗马（5、10、50、100、500、1000）

 

数字的表示方法（编解码原理）

中国：编解码的密钥是乘除 二百万 = 2 x 100 x 10000

罗马：编解码的密钥是加减 IV = 5-1 = 4  ,要用罗马文字表达10亿的话，一黑板是写不下的。

 

抄圣经的校验方式：将每个字母映射成一个数字。把每一页文字对应的数字按行列加起来，写在每行每列的尾部。在抄写时，把自己的数字和原文的数字进行对照，可以以最快的速度检查是否有抄写错误，而且还能定位行列。这种简单有效的方法已经开始展现出数学之美了

 

自然语言处理的两条路

1、语意理解（失败）：让计算机像人脑一样分析语句的意思，建立语法分析树。

失败原因有两点：

a.当遇到长难句时，计算量大幅增加，计算机的解码是上下文无关的，而自然语言是上下文相关的。

b.要理解语意必须建立大量的语法规则，然而即使规则再多，也不能覆盖全部的自然语言，总会有新的流行语言产生，它们处于语法规则之外。

 

2、数学与统计（成功）：通过隐含马尔可夫模型来估计句子出现的可能性。

马尔可夫假设：在一个句子中，每个词x出现的概率只与它前面的一个词x-1有关，而与更前面的0~x-2个词无关。这是一个偷懒却有效的假设，这个著名的假设使得语言处理的计算速度大幅提升且不失准确。

马尔可夫链是马尔可夫模型的基础。它是一个有向图，各个状态之间有转移概率。同时，马尔可夫链也对概率论的研究产生了巨大贡献。

马尔可夫链的训练：鲍姆-韦尔奇算法

 

统计学陷阱

当统计样本不足时（分母太小），统计结果的说服力将降低，此时可以用古德-图灵方法对统计结果进行打折平滑处理

 

N阶马尔可夫假设：每个词和它前面的N-1个词有关，N元模型的大小是N的指数关系。Google翻译使用的是4阶模型

了解对现代语言处理的贡献

 

信息量与熵

基础：

信息熵：衡量信息的多少和不确定性的大小,可以衡量统计模型的好坏

条件熵：已知一个变量时，另一个变量的信息熵

相对熵：用来衡量两个函数的相似性

信息熵是网页搜索的基础，它可以衡量关键词和网页之间的相关性。

 

搜索引擎

搜索引擎的基础是boolean逻辑运算，“与或非”这三种最快的运算方式使得搜索引擎的速度变的如此之快。一个指令周期如果进行32位的bool运算，计算速度可以达到10亿次/秒

香农提出了将所有数学运算(+ - * / ^ 开方）转换成bool运算的方法

 

构建网络爬虫的要点

1、利用哈希表记载哪个网站被下载过

2、广度优先 vs 深度优先？广度优先是理所应当的，爬虫应该先下载各大网站的首页再去下载它的子页，但是广度优先需要较长的握手时间（下载服务器与网站建立通讯的时间），所以广度优先和深度优先之间要做一定的权衡

3、URL的提取：面对不规则的网站，无法直接从HTML中提取URL

 

Google的网页排名算法：pagerank

以前我在数学建模的比赛中用过这个算法对论文进行排名，所以比较熟悉了

pagerank算法的核心是迭代计算每个网页的权重，然后通过权重的大小对网页排名。

迭代初始时每个网页的权重是一样的，然后通过计算更新每个网页的权重，规则如下：

1、当一个网页被越多的网页引用时，它的权重越大

2、当一个网页的权重越大时，它引用的网页的权重也随之变大

3、当一个网页引用的网页越多时，被它引用的网页获得的权重就越小

如此反复迭代，算法最终会收敛到一个固定的排名。