《数学之美》记录

简介

之前在云南玩的时候，车上晚上有空的时候把《数学之美》看完了，对吴军他对国民科普的使命感和愿望很敬佩。我向来认为每个人脑中对知识的理解是不一样的，越高深的知识越不一样。将高深的知识化为朴实通俗的语言科普国民，太不容易了。

书中另外写了吴军的科研经历，包括他遇到的各个牛人。想起了我前段时间琢磨大人生意义以及繁殖后代的意义看到的一句话，“为天地立心，为生民立命，为往圣继绝学，为万世开太平”，前两句比较虚，我自己觉得第三句才是说到了个人和人类整个知识传承的重要性。

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

从远古时期的语言发展到今天的一个过程，也阐述了另外一些文明逐渐被淘汰的原因。

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

图灵测试（Turing Test）：让人和机器进行交流，如果人无法判断自己交流的对象是人还是机器时，就说明这个机器有智能了。

自然语言处理分为两个阶段。从20世纪50年代到70年代，是科学家们走弯路的阶段，一直是用电脑模拟人脑的思路，这20多年的成果近乎为零。直到20世纪70年代，开始用基于数学模型和统计的方法，取得实质性的突破。

第一个阶段主要做的基于规则的句法分析，像编译原理一样的分析过程。

第3章 统计语言模型

序列S的合法概率（即是不是一个合法的句子）

P(S) = P(w1,w2,...,wn)
= P(w1)·P(w2|w1)·P(w3|w1,w2)...P(wn|w1,w2,...,wn-1)

马尔可夫方法（二元模型）

P(S)
= P(w1)·P(w2|w1)·P(w3|w2)...P(wi|wi-1)...P(wn|wn-1)

P(wi|wi-1) = P(wi-1,wi)/P(wi-1)

同理，可以推进到N元模型。

卡茨退避法，平滑离散概率曲线

第4章 谈谈中文分词

分词，尽量减少歧义

第5章 隐含马尔可夫模型

马尔可夫链，每一个节点都是一个隐含的状态。

鲍姆 - 韦尔奇算法，迭代收敛。

第6章 信息的度量和作用

这一章，真是觉得大三的信息论没白学，哗哗地看过去。

熵、条件熵、互信息

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

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

布尔代数：与或非

用位数表示索引网页的位置，以及是否满足关键词。

第9章 图论和网络爬虫

广度优先 or 深度优先

这个跟爬虫有关，比较标准的是如果不考虑时间并且互联网静态不变，两者一样，但是现实中这个问题会演变成如何在有限时间里最多地爬下最重要的网页，此时广度优先更适合，因为各个网页最重要的是首页，然后是从首页直接链接的地址，因此爬虫爬网页的顺序的调度程序原理基本上是广度优先；由于爬虫是由成千上万台服务器组成的分布系统，在网络通信中为了避免多次握手降低下载的效率，会让指定服务器下载只负责一个网站，下完一个网站再进行下一个，而不是每个网站先轮流下载5%；综合来看网络爬虫不是简单的深度或者广度，而是需要一个调度系统管理下载的优先级，利用优先级队列，当然如果访问过的会利用hash表记录下来防止重复下载，在工程上和广度优先更相似，因此爬虫中广度优先的成分多一些。

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

一个网页Y的排名来自于所有指向这个网页的其他网页X1，X2，……，Xk的权重之和。例如：pagerank = 0.001 + 0.01 + 0.02 + 0.05 + 0.081。这样形成了一个环，所以解决的方法是因为给出初始的权重，然后迭代计算下一次的权重，直至收敛。

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

搜索关键词权重的科学度量TF-IDF

长的网页总的来讲包含的关键词要多些，所以要根据网页的长度，对关键词的次数进行归一化，也就是用关键词的次数除以网页的总字数，称为“单文本词频”。

关键词词频相加即为该网页的PageRank。

还有一些停止词（Stop Word），比如，”的“，”是“，”和“，”中“，”地“，”得“。

另外地，关键词存在预测主题的能力，能力越强，权重越大；反之，权重越小。
预测主题的能力，可以这样确定，假定一个关键词w在Dw个网页中出现过，那么Dw越大，w的权重越小，反之亦然。称为”逆文本频率指数“（IDF），为log(D/Dw)。所以最后加权求和：

TF1·IDF2 + TF2·IDF2 + ... + TFN·IDFN

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

将地址分割，变为一个状态机。找到一个省，才能确定该省内的市，如果找不到则判断错误。

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

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

将每个网页的关键词按照一定次序（比如字典序），之后其权重形成一个向量。然后衡量余弦角即可判断是否相近，是否属于同一类。

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

将文本词汇表示成矩阵。
奇异值分解。

第16章 信息指纹及其应用

相似哈希，判重

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

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

去噪音，还原出原本网页。

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

简单

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

预测时保留各种可能性，不添加主观假设，这时概率分布的信息熵最大。

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

拼音编码的效率并不是最高的，但是考虑到编码被用户的接受程度。如果采用最有效的编码，用户则需要另外花费大量的时间去背新的编码。

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

第23章 布隆过滤器

如果将每个键值都存起来以备之后判重，内存损耗巨大。

用八个随机数产生器产生8个信息指纹，单纯判断这8个信息指纹所对应的二进制位是否全为1。

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

有些状态不是单纯地从一个状态到另外一个状态，而是交叉的，所以出现了网络。不同状态变换到不同状态涉及到了每个前置状态的概率，所以用到了贝叶斯。

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

我自己理解的条件随机场是将贝叶斯网络的前置状态由一维变成多维的，所以多维前置向量就涉及到了联合概率和条件概率。

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

在上述网络里找出最具可能性的路径

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

类似K均值聚类

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

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

MapReduce