《数学之美》学习笔记

学习材料：数学之美

学习计划：每天1~2章

学习时长：7.20左右【超时，预计8月初完成】

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

• 香农：信息论之父
• 非洲是人类文明的摇篮
• 汉字大约有十万个，常用的七千个
• 信息的载体不仅可以是文字，也可以是数字（0和1）
• 信息冗余，虽然麻烦但是信息会更安全。比如有多个语言的书
• 十进制的原因是人类有十根手指
• 古印度人创造了阿拉伯数字，而不是阿拉伯人
• 实践是检验真理的唯一标准

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

• 任何一种语言都是一种编码方式，语言的语法规则是编解码的算法[一种很好理解算法的描述方式]
• 机器翻译和语音识别不是靠理解自然语言工作的，而是数学统计模型

第三章 统计语言模型

• 判断一个句子是否合理，通过概率实现。贾里尼克，马尔可夫解决了概率难算的问题（二元模型）
• 数学的魅力在于把复杂问题简单化。而编程的魅力在于可以创造一个完全逻辑的世界

第四章 谈谈分词

• 想实现分词，ABCDE,如果AB可以连起来AB一组，如果ABC可以连起来就ABC一组，以此类推
• 颗粒度，经常看到这个词，指的是划分的块大小，专业的描述法
• 对于暴力实现分词的方法。有更好的实现方法，先按最小颗粒度划分，再到复合词表去优化。具体细节不清楚，只知道有这个方法去做

第五章 隐含马尔可夫模型

• 通信的本质是一个编码和解码的过程
• 隐含马尔可夫模型是机器学习的主要工具之一

第六章 信息的度量和作用

• 信息熵和变量的不确定性成正比；互信息 = 加入一个信息后的信息熵改变量；相对熵，两个函数的差异越小，相对熵越小。凭借这个原理可以实现查重
• 信息的作用：消除不确定性

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

• 我一直认为，一个人想要在自己的领域走到世界一流，他的周围必须有非常多的一流人物

第八章 简单之美

• 所有的数学和逻辑运算，加减乘除，乘方开发全都可以转化成二进制运算
• 假设当前有n个网页，m个词，那就会有一张m*n的索引表，当索引多个关键词的时候，就可以进行&操作，判断哪个文章有我们想要的数据，然而数据太大，采用分布式，相当多个服务器分担压力

第九章 图论和网络爬虫

• 上一章说了如何建立索引，这章分析如何加载所有的网站（作为资源库）
• 网络爬虫：把每一个网页当作一个节点，超链接当作弧；实现：BFS + 优先队列
• 欧拉图：从一个顶点出发，每条边不重复地遍历每一个顶点。要求每个顶点的度为2。证明：一进一出
• 情景：表信息太大，性能遇到瓶颈怎么办？首先分布式，明确每台下载服务器的分工，这样一看到某个tag就知道这个URL要往哪个服务器去搜索。往服务器发数据的时候，把多个小数据合在一起再发，减少TCP启动，结束（三次握手，四次挥手）带来的时间消耗

第十章 PageRank

• 本章目的是介绍度量网页质量的方法。PageRank算法：一个网页如果被很多其他网页链接，说明它受到普遍的信赖和认可。PageRank算法的实现：矩阵乘法，证明最后收敛，再进行平滑处理，得到最后的迭代公式

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

• 如今搜索引擎进行搜索和排序的主要依据有：完备的搜索引擎，网页质量的度量（PageRank），用户偏好（很多浏览器下载完成之后会提示输入感兴趣的话题），确定一个网页和某个查询的相关性算法（TF-IDF）
• TF-IDF公式为；D指网页总数，D_w指和关键词w相关的网页数。用IDF作为w的权重

第十二章 有限状态机和动态规划

• 顺便复习了一下Dijkstra，终于理解了算法的核心思想：S->....->A->B，假设是S到B的最短路，那么S->A此时也一定是最短路，否则肯定有从S->B更短的路径。因此，每次从当前距离远点最小的点开始更新，扩散到附近的点，一定是S->now->next最短的路径。而dis最小的点，也肯定不能被其他dis比他大的点所更新

第十三章 Google AK-47的设计者

• AK-47冲锋枪，从不卡壳，不易损坏，可以在任何环境下使用，可靠性好，杀伤力大，操作简单
• 许多失败并不是因为人不优秀，而是做事情的方法不丢，一开始追求大而全的解决方案
• 寻找简单有效的解决方案，相信简单哲学（经过深思熟虑，给出合理的解释）

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

• 新闻的分类，很大程度上是依靠余弦定理，用余弦值确定关联

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

• 对于一个矩阵A，使用奇异值分解可以将其分解为A = X * B * Y，即三个矩阵的乘积，这样可以减少计算量。在实际应用中，可以先进行奇异分解得到粗分类结果，再利用向量余弦方法进行迭代

第十六章 信息指纹及其应用

• 哈希，散列表，密码，时间复杂度，空间复杂度

第十七章 谈谈密码学的数学原理

• RSA算法证明https://www.jianshu.com/p/93c0f26cf00c

第十八章 谈谈搜索引擎反作弊问题和搜搜结果的权威性问题

• 噪音存在于任何通信系统，而好的通信系统需要过滤掉噪音，还原真实信号。搜索引擎是一个特殊的通信系统，反作弊和确定权威性就是去噪音的过程。而这一过程背后依靠的是数学模型和方法
• 原始的信号混入噪音相当于给两个信号做卷积，噪音消除相当于是解卷积的过程

第十九章 谈谈数学模型的重要性

• 近日点运行比远日点快？
  • 开普勒定律：相同时间内，日地连线扫过的面积相等
• 一个正确的数学模型应该足够简单
  • 思考：就像一个工程框架应该足够清晰一样
• 正确的模型可能会存在噪音的干扰，而不正确，这时候不应该采用一种“凑活的修正方法加以弥补”，而是找到噪音的根源，这也许能通往重大的发现
  • 思考：当在开发过程中，碰到BUG应该认真找出问题的根源，而不是特判，仅仅着眼于眼前的问题

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

• 最大熵：保留全部的不确定性，将风险降到最小。他可以解决将各种信息整合到一个统一的模型中的问题，它有很多良好的特性：形式简单，效果好
• 不要把鸡蛋放到一个篮子里是一个最大熵模型

第二十一章 语音输入法的数学原理

• 不同的问题，可能背后的原理，数学模型是相同的

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

• 马库斯让他的学生自选题目去研究。典型有两种数学模型：追求完美和简单才美。一种是复杂但优化到极致，一种是简单效果好

第二十三章 布隆过滤器（散列表强化版本）

• 布隆过滤器的原理是用多个随机数对用的bit都为1的概率去judge，用少量空间存储大量信息
  • 思考：设计思路比较暴力。。 我的第一反应是用字典树，如果只允许使用字母和数字的情况下，36层，每层36种可能。每次查找的复杂度是O(36)

第二十四章 马尔可夫链的扩展（贝叶斯网络）