数学之美读书笔记

大学时代读了吴军的浪潮之巅，我第一次了解了互联网行业的发展，硅谷传奇公司的发展，唤起了我对互联网行业的兴趣，此后经历了移动互联网的快速发展，并最终投身于大数据行业，此时读数学之美，希望这本书能重新唤起我对数学的兴趣，能让我在数据挖掘方向走的更远一些。

读书笔记见幕布：https://mubu.com/doc/2IOprNpA2w

数学之美，就是简单之美，在这本书里又读到了器术道的概念，作者认为本书讲解的是道。

学数学有什么用？数学绝不仅仅是简单的计数，看完本书就理解了，原来大学学的概率论，线性代数的作用这么大，我们日常生活中习以为常的大部分事务，底层都有着数学原理作为支撑。

读完之后，突然有一种我要再回校园重学知识的冲动。

前言
- 今天的电视、手机和互联网，都遵循信息论规律，而整个信息论的基础就是数学。如果往更远看，我们自然语言和文字的起源背后都受到数学规律的支配
- 数学是解决语音识别、机器翻译和自然语言处理等问题最好工具
- 数学的本质常常是简单而直接的
01：文字和语言VS数字和信息
- 数字、文字和自然语言都是信息的载体，而非信息本身
- 语言、文字设计之初就已经不自觉应用到了今天的数学法则，比如解码、校验位、信息编码
- 从象形文字到拼音文字是一个飞跃，因为人类在描述物体的方式上，从物体的外表到抽象的概念，同时不自觉地采用了对信息的编码
02：自然语言处理——从规则到统计
- 语言的数学本质：任何语言都是一种编码方式，语法规则是编解码的算法。
- 1950然后阿兰·图兰在《思想》杂志发表“计算的机器和智能”论文，提出“图灵测试”
- 自然语言处理有两个阶段，第一个阶段希望让计算机像人理解自然语言，需要分析语句和获取语义，第二个阶段，到20世纪70年代，基于数学模型和统计的方法，自然语言处理才进入实质发展阶段
- 自然语言的文法是比较复杂的上下文有关文法，程序语言是认为设计便于计算机理解的上下文无关文法
- 计算复杂度来衡量算法的耗时：对于程序语法，算法复杂度基本上是语句长度的二次方，对于自然语言，基本上是语句长度的六次方
- 语言的初衷是通信
03：统计语言模型
- 计算机处理自然语言，基本问题是考虑自然语言的上下文相关的信息表达和传递特点来建立数学模型，即统计语言模型，其广泛使用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询
- 马尔可夫假设：假设任意一个词wi出现的概率只同它前面出现的词wi-1有关，二元模型
- 统计语言模型主要以概率论和数理统计来分析
04：谈谈分词
- 利用统计语言模型分词的方法，重点是找出多次分词方法中概率最大的，即为最好的分词方法
  - 为避免穷举每种分词方法概率巨大的计算量，可将其看成是动态规划问题，利用维特比算法找到最佳分词
- 利用统计语言模型进行分词，也有其局限性，在于在特定情况下无法保证百分之百准确，但真实文本中几乎不会发生特定情况
- 统计语言模型广泛应用后，不同分词器产生的结果差异要远小于人之间的看法差异
  - 人工分词不一致的原因是在不同应用中，人们对词的颗粒度认识不一
  - 但对于语言模型，与其根据应用构造不同的分词器，不如将分词器支持不同层次的词的切分
- 分词器准确性的问题：
  - 分词错误
    - 越界型错误
    - 覆盖型错误
  - 颗粒度不一致
05：隐含马尔可夫模型
- 成功的解决了复杂的语音识别、机器翻译等问题
- 基于马尔可夫假设和独立输出假设，可计算出某个特定状态产生出输出符号的概率
  - 需要训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特比算法）
- 最早应用于语音识别，后陆续成功应用于机器翻译、拼写纠错、手写体识别、图像处理、基因序列分析等，还可应用于股票预测和投资
- 隐含马尔可夫模型的三个基本问题：
  - 给定一个模型，如何计算某个特定的输出序列的概率
  - 给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列
  - 给定足够量的观测数据，如何估计隐含马尔可夫模型的参数
06：信息的度量和作用
- 信息的度量：香农1948年提出的信息熵
- 信息量就等于不确定性的多少，信息的不确定性越大，信息熵也就越大，这是决策树算法的核心
- 信息熵（符号H，单位比特），对于任意一个随机变量，变量的不确定性越大，熵就越大，所需信息量也就越大
- 信息的作用在于消除不确定性，自然语言处理的大量问题就是找相关的信息
- 互信息：两个随机事件“相关性”的度量
07：贾里尼克和现代语言处理
- 弗里德时克·贾里尼克-将数学原理应用于自然语言处理领域的大师
- 贾里尼克的贡献：
  - 上世纪70年代在IBM时提出统计语音识别的框架结构，将语音识别当成通信问题，是今天自然语言处理的基础
  - 发明的BCJR算法是今天数字通信中应用最广的两个算法之一（另一个是维特比算法）
  - 1994年在约翰·霍普金斯大学建立了世界著名的CLSP实验室
    - 两件大事：政府主管申请经费、邀请顶级科学家和学生在实验室工作
    - 两件小事：招募了潜力年轻学者、暑期安排学生到世界最好的公司实习
- 科学家大佬的打怪升级之路
08：简单之美：布尔代数和搜索引擎的索引
- 所有的搜索产品都有：自动下载尽可能多网页（下载）、建立快速有效的索引（索引）、根据相关性进行公平准确的排序（排序）三个基本服务
- 布尔代数是1854年英国的一名中学数学老师布尔发布的《思维规律》，展示用数学方法解决逻辑问题
  - 两个运算元素：1（TURE，真）和0（FALSE,假），三种运算：与（AND)，或（OR),非（NOT)
  - 后来1938年香蕉农在硕士认文中指出布尔代数可实现开关电路，使布尔代数成为数字电路的基础
  - 布尔运算对于搜索的应用主要集中在文献检索，判断是否包含关键词
- 建立有效快速的索引而非扫描所有文本，最简单的索引结构是用很长的二进制判断每篇文献中的关键字
- 布尔代数不仅把逻辑和数学合二为一，还给了我们看待世界的全新视角，开创了今天数字化的时代
09：图论和网络爬虫
- 图论的遍历算法——广度优先搜索、深度优先搜索
- 关于网络爬虫
  - 世界上第一个网络爬虫是由麻省理工学院的学生马休·格雷在1993年写成
  - 一个商业网络爬虫需要成千上万个服务器，并通过高速网络连接，因此如何建立复杂的网络系统，如何协调服务器的任务，就是网络设计和程序设计的艺术
  - 网络爬虫在工程实现需要考虑的细节
    - 用BFS算法还是DFS算法
    - 页面的分析和URL的提取
    - 记录哪些网页已经下载的小本本——URL表
10：PageRank——Googel的民主表决式网页排名技术
- 最先为网站排序的是雅虎的杨致远和费罗，采用目录分类方式，缺点在收录网页很少
- pagerank核心思想：如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么他的排名就高
- Googel的创始人拉里·佩奇和谢尔盖·布林找到计算网页自身质量的完美数学模型——PageRank算法
11:如何确定网页和查询的相关性
- 网页相关性的重要指标：关键词频率=关键词的次数/网页总字数
- 还需要对关键词进行权重分析
  - 相关词对预测主题的能力越强，权重越大；反之权重越小
  - 停止词（的、是、和、地、得等）权重为零
- TF-IDF（词频-逆文本频率指数）是信息检索中最重要的发明，由剑桥大学计算机女科学家斯巴克·琼期发明
  - 用信息论解释IDE即一个特定条件下关键词的概率分布的交叉熵
**12：有限状态机和动态规划–**地图和本地搜索的核心技术
- 智能手机的定位导航功能，其关键技术为：卫星定位、地址识别、最短或最快路线规划
- 使用有限状态机识别地址，关键要解决两个问题：
  - 通过一些有效的地址建立状态机（是基于概率的有限状态机实现模糊匹配）
  - 给定一个有限状态机后，地址字串的匹配算法
- 全球导航的关键算法是计算机科学图论中的动态规划算法
13：Google AK-47 的设计者——阿米特·辛格博士
- 简单哲学：在计算机科学领域，一个好的算法应该像AK-47冲锋枪那样“简单、有效、可靠性好而且容易读懂（或者说易操作）”，而非故弄玄虚
- 先帮助用户解决80%的问题，再慢慢解决剩下的20%的问题。许多失败并不是因为人不优秀，而是做事情的方法不对，一开始追求大而全的解决方案，之后长时间不能完成，最后不了了之
- 辛格博士坚持寻找简单有效的解决方案：
  - 奉行简单的哲学（要有经验，同时要不怕失败大胆尝试）
  - 简单的方案才容易解释每一个步骤和方法背后的道理，便于问题查错和找到改进的目标
14：余弦定理和新闻的分类
- 计算机读不懂新闻，其本质是快速计算
- 第一步是将新闻文字变成按词典顺序组织的数字（特征向量）
- 第二步依据余弘定理计算特征向量的相似性
- 第三步就是设计新闻分类的算法——IBM华生实验室的科学家弗洛里安发明了一个自底向上不断迭代合并的办法
15：矩阵运算和文本处理中的两个分类问题
- 新闻分类其实是一个聚类问题，关键是计算新闻间的相似程度，利用矩阵运算中的奇异值分解（SVD）
  - 将大矩阵分解成三个小矩阵相乘，减少存储量和计算量
  - 优势在于无需一次次迭代，适合处理超大规模文本的粗分类
  - 可在使用奇异值分解后再利用计算向量余弦方法得到比较精确结果
- 奇异值愤分解的优点是能较快的得到结果，因为它不需要一次次的迭代
16：信息指纹及其应用
- 信息指纹在消重、加密、信息压缩和处理中有着广泛的应用
- 使用伪随机数产生器算法（常用为MD5或者SHA-1等），将网址随机映射到128位二进制
- 信息指纹的其一特征“不可逆性”，即无法根据信息指纹推出原有信息
- 信息指纹可应用于反盗版，在计算时无法逐一对比，可选择特征词的集合并计算指纹差异（如为视频反盗版则找到关键帧）
- 信息指纹可理解为将一段信息（文字、图片、音频、视频等）随机地映射到一个多维二进制空间中的一个点（二进制数字），只要该随机函数做得好，不同信息对应的点不会重合，则该二进制数字就成为了独一无二的指纹
17：由电视剧《暗算》所想到的——谈谈密码学的数学原理
- 好的编码方法会使得解密者无法从密码中统计出明码的统计信息
- 根据信息论，密码的最高境界是对方信息量没有增加，要求：
  - 密码之间分布均匀
  - 统计独立，即即使知道了加密算法并且看到了一段密码和明码也无法破解另一段密码
- RSA加密解密原理
18：闪光的不一定是金子——谈谈搜索引擎反作弊问题
- 通信模型对于搜索反作弊依然适用，基本思路为二：
  - 从信息源出发，加强通信（编码）自身的抗干扰能力——通过余弦定理识别虚假出链提升抗干扰
  - 从传输来看，过滤掉噪音，还原信息——通过“图论”发现Clique
- 网页搜索反作弊对于搜索引擎公司来讲是一项长期任务
- 作弊的本质是在网页排名信号中加入噪音，反作弊的关键是去噪音，需根本上提高搜索算法抗作弊能力
- 搜索结果的权威性计算：提及原理
  - 1.句法分析每个网页正文，包含标题
  - 2.互信息找到主题短语和信息源的相关性
  - 3.主题短语进行聚合
  - 4.对网站中的网页进行聚合
19:谈谈数学模型的重要性
- 从天文学的发展来看，数学模型重要性的几个结论如下：
  - 正确的数学模型应当在形式上是简单的
  - 一个正确的模型一开始可能还不如一个精雕细琢过的错误模型来得准确，但如果认定大方向是对的就应该坚持下去
  - 大量准确的数据对研发很重要
  - 正确的模型可能受噪音干扰而显得不准确，此时不应该用凑合的修正方法来弥补，而是找到噪音的根源，也许能通往重大的发现
20：不要把鸡蛋放到一个篮子里——谈谈最大熵模型
- 最大熵模型的原理是保留全部的不确定性，将风险降到最小
- 最大熵原理指出：对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设
- 最大熵模型在形式上是最漂亮、最完美的统计模型，在自然语言处理和金融方面有很多应用
  - 如文艺复兴技术公司利用数学模型实现的稳定高额净回报率
- 最大熵模型在实现上非常复杂，计算量非常大
  - 最原始的模型训练方法是通用迭代算法GIS，但因其不太稳定，很少实际应用
  - 后期达拉皮垂孪生兄弟提出的改进迭代算法IIS才有可能变得实用
  - 今天世界上能有效实现这些算法的也不到100人
21:拼音输入法的数学原理
- 输入法输入汉字的快慢取决于汉字编码的平均长度，即击键次数X寻找该键所需时间，而输入法效率提升在于同时优化这两方面因素而非其一
- 对汉字的编码分为两部分：对拼音的编码（参照汉语拼音标准即可）和消除歧义性的编码
- 早期双拼输入法只优化局部，而伤害了整体，增加了编码上的歧义性（增加击键时间）并让思维在拆字过程中变慢，且容错性不好
- 全接输入法的优势在于不需要专门学习，且与符合思维自然过程，且容错性好，只剩下要排除一音多字的歧义性
- 输入法的进一步优化方向：
  - 以香农第一定理（信息编码长度都不小于它的信息熵）确定每个汉字的击键效率为2.1次键（以词输入为1.7次键）
  - 利用上下文建立大词库（提升关键是准确而有效地建立语言模型）
  - 拼音转汉字的算法和导航中寻找最短路径的算法相同，都是动态规划（数学的妙处在于其工具都具有相当的普遍性，在不同应用中发挥作用）
22:自然语言处理的教父马库斯和他的优秀弟子们
- 米奇·马库斯更早发现建立标准语料库在自然语言处理研究中的重要性
- 马库斯通过在宾夕法尼亚大学建立LDC语料库，为全世界自然语言处理科学家共享
- 马库斯的优秀弟子：
  - 柯林斯追求完美制作文法分析器，是“务于精纯”的精深专才
  - 布莱尔善于寻找简单却有效的方法，是“观其大略”的通才
23：布隆过滤器
- 布隆过滤器背后的数学原理在于两个完全随机的数字相冲突的概率很小
- 布隆过滤器只城要哈希表1/8到1/4的大小就能解决同样的问题，其实质上是一个很长的二进制向量和一系列随机映射函数，其好处在于快速、省空间，但有一定的误识别率。补救方法是再建立一个小的白名单，存储那些可能被误判的邮件地址
24：马尔可夫链的扩展——贝叶斯网络
- 贝叶斯网络：每一个状态只和它直接相连的状态有关，而和它间接相连的状态没有直接关系
- 其拓扑结构比马尔可夫链灵活，不受马尔可夫链的链状结构的约束，可更准确地描述事件之间的相关性
- 马尔可夫链时贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广
- 先确定网络的拓扑结构（结构训练），还要知道各个状态之间的概率（参数训练）
- 在文本分类、概念抽取、生物统计、图像处理、决策支持系统和博弈论中有广泛应用
25：条件随机场、文法分析及其他
- 布朗大学计算机系的计算语言学家尤金·查尼阿克统计出文法规则的概率，在选择文法规则时，坚持一个原则——让被分析的句子的语法树概念达到最大，无形中在数学和句法分析中搭建了一个桥梁。其学生拉纳帕提用最大熵模型实现了语法成分的统计，还用一个统计模型来预测句子成分的种类。
- 条件随机场：是隐含马尔可夫模型的一种扩展，是一种特殊的概率图模型，是用于预测的统计模型，在模式识别、机器学习和生物统计中都有很成功的应用（形式简单，但实现复杂）
26：维特比和他的维特比算法
- 维特比算法：是一个特殊但应用最广的动态规划算法，针对篱笆网络的有向图的最短路径问题而提出，包括数字通信、语音识别、机器翻译、拼音转汉字、分词等都可用其来解码
- 3G手机和移动互联网最关键的通信技术是码分多址（CDMA）技术，由业余发明家（本职为演员）海蒂·拉玛尔和维特比发明并普及贡献
- 频分多址：对频率进行切分，每一路通信使用一个不同的频率（如对讲机）
- 2007年，维特比作为数学家和计算机科学家，被授予美国科技界最高成就奖——国家科学奖
27：上帝的算法——期望最大化算法
- 期望最大化算法：通过几次迭代收敛完成聚类，不需要任何人工干预和先验经验
- 就是机器学习中常用的聚类算法
28：逻辑回归和搜索广告
- 搜索广告的三个阶段：
  - 第一阶段：广告主出价高低竞价排名
  - 第二阶段：结合出价和点击率预测（CTR）来决定广告投放
  - 第三阶段：全局优化
- 点击率预估的最好办法，就是根据以前经验值来预测——使用逻辑回归模型（将一个事件出现的概率适应到一条逻辑曲线）
- 两个技巧：
  - 一是如何选取与广告点击相关的信息，这些是专门从事搜索广告的工程师和数据挖掘专家的工作；
  - 二是如何决定这些参数，训练最大熵模型的IIS方法可以直接训练逻辑回归函数的参数
29：各个击破算法和Google云计算的基础
- 云计算的关键问题：如何将一个非常大的计算问题，自动分解到许鑫计算能力不是很强大的计算机止，共同完成（Google提出MapReduce程序），基本原理就是分治算法，mapreduce，当前大数据的基础算法
- 分治算法原理：将一个复杂问题，分成若干个简单的子问题进行解决；然后，对子问题的结果进行合并，得到原有问题的解
- MapReduce：将一个大任务拆分成小的子任务，并且完成子任务的计算（Map），将中间结果合并成最终结果（Reduce)
- 真正有用的方法往往简单而又朴实
30：Google大脑和人工神经网络
- 人工神经网络本质时一种特殊的有向图
- 人工神经网络与贝叶斯网络的关系
  - 都是有向图，遵从马尔可夫假设
  - 训练方法类似
  - 对于模式分类问题，两种方法在效果上类似
  - 训练计算量都特别大
- 人工神经网络是一个形式上非常简单但分类功能强大的机器学习工具
31.大数据的威力
- 在没有数据之前，不要给出任何结论，因为日常的很多感觉与数据给出的结论是相反的
- 大数据的好处远不是成本和准确性的问题，它的优势还在于多维度
数学之美，就是简单之美