《数学之美》札记

这本书让我意识到大学所学的概率论通信原理具体有什么用处，相见恨晚。也介绍了NLP、搜索方面的基础概念，很有价值。还能见到人工智能的影子。

从语法到统计

原先自然语言分析最开始是基于语法规则来分析的，但是规则太复杂了，计算量也很大，后来才基于统计的方法，看看哪种说法最有可能概率最大，那么就是对的。

这看似不符合直觉，但完全符合外语学习的实际情况，学个十年语法，不如大量输入实际的语句来得有效。这个研究路径反过来指导我们的学习，别光在那看语法背单词，大量真实的用例更有指导意义。

中文分词

目的是为了消除歧义性，找到概率最大的一组分词。可以看成是动态规划的问题，利用维特比算法（下文）找到最佳分词。

机器翻译和搜索中使用不同颗粒大小的分词更好，所以最好支持不同层次的分词器。目的不同手段也要不同，可以同时兼容多种情况。

隐含马尔可夫模型

自然语言处理本质上是通信系统解码问题。要解决的问题是：已知接测信号来找到概率最大的发射信号。

要用到贝叶斯公式，隐藏马尔可夫模型。

概率论从随机变量发展到随机过程（动态），马尔可夫假设，状态只与前一个状态有关，符合这个假设的随机过程称为马尔可夫过程，马尔可夫链。大大简化了模型。

隐含马尔可夫模型：每一个时刻不可见，但是会输出一个符号，只跟状态有关，这个叫做独立输出假设。

最后利用维特比算法找到最大值。

信息的度量和作用

信息熵，与不确定性相关，越不确定熵越大。

根据熵的概念，每个中文只有5比特，理论上可以压缩到最小值，被压缩的那部分叫做冗余度。

条件熵，已知Y时的X的熵。Y和X一起出现的概率，联合概率分布。Y在不同取值的前提下X的概率分布，条件概率分布。可以得到条件熵，小于等于X的信息熵，也就是说信息越多。

互信息，度量两个随机事件的相关性。数值上就是信息熵减去条件熵。可以在机器学习中找到句子中互信息大的词语来消除二义性。

相对熵，衡量两个取值为正数的函数的相似性：

1. 两个完全相同的函数，相对熵为零
2. 相对熵越大，两个函数差异越大
3. 对于概率分布或者概率密度函数，如果取值大于零，相对熵可以度量两个随机分布的差异性

用来衡量同义词等

布尔代数与搜索引擎的索引

搜索需要解决的问题：

1. 自动下载尽可能多的网页
2. 建立快速有效的索引
3. 根据相关性对所有的网页进行公平准确的排序

搜索信息，建立索引，类似于图书馆的索引卡片。使用基于数据库，基于布尔计算的SQL查询语句。

每一个文献占一比特，一串二进制来存储，1表示出现过这个关键字。索引太大，解决方法：分布式存储，建立有级别的索引。

图论和网络爬虫

两种遍历方式：DFS，BFS。一般这两种遍历方式大多都在图里面引出。

构建网络爬虫的工程要点：

1. 用BFS还是DFS

2. • 应当使用BFS，因为最重要的网页都是比较靠近首页的
   • 但是在分布式爬取中，对于某一个网站，一台或几台服务器负责下载，下完一个下载下一个。避免握手次数太多。对于单一网站是DFS
   • 调度系统决定下载优先级，待下载的网站存在优先级队列里

3. 页面的分析和URL的提取

4. • 更多的url是js生成的，所以需要有做浏览器内核的工程师来解析

5. 记录哪些网页已经下载过的小本本—URL表

6. • 用哈希表存储，表过大之后需要有通信问题。
   • 首先明确每台下载器的分工，避免很多服务器都做出判断
   • 每次向哈希表发送一批询问

PageRank谷歌的民主表决式网页排名技术

搜索的排名取决于两个信息：

1. 网页的质量
2. 网页的相关性

PageRank首先解决衡量网页质量的方法。如果一个网页被很多其他网页所链接，说明它收到普遍的承认和信赖，排名就高，继而排名高的权重就大。

如何得到？利用迭代的方法找出每个网站的权重，即它的排名，首先假设所有网站的权重都相同，最后得出实际的权重。

可以利用稀疏矩阵来解决。

确定网页和查询的相关性

首先是词出现的频率，其次是这个词在所有网页中出现的权重，出现次数越多说明越不重要。

两个合起来叫做TF-IDF（Term frequency/ inverse document frequency）。本质上就是信息量大小。

地图和本地搜索的最基本技术

定位和导航功能：

1. 利用卫星定位
2. 地址的识别
3. 根据用户输入的起点和终点，在地图上规划最短路线或者最快路线

地址分析：有限状态机。一个有限状态机是一个特殊的有向图。如果能从起点走到终点则是一条有效的地址。

全球导航：动态规划。不断寻找局部最短路径。

余弦定理和新闻的分类

找出一组实词，按词汇表位置排列，计算出对应的TF-IDF值，形成特征向量。用余弦定理找到向量的夹角，看是否属于同一主题。

如果没有具体的新闻类别的特征向量，可以计算两两的余弦相似性，然后相似性大于一个阈值的合并成一个小类，然后计算小类的特征向量，再比较小类的余弦，不断迭代。

最初为了分发论文而创造了这种算法，可见磨刀不误砍柴工，说不定还有别的收获。

大数据量时的余弦计算（一些优化）：

1. 分母部分可以存储，不需要重复计算
2. 分子中只需要考虑非零元素
3. 删除虚词
4. 位置加权，开头结尾处的重要性更大

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

1. 将文本按主题归类
2. 将词汇表的字词归类

奇异值分解（Singular value decomposition）。

关联矩阵A，每一行对应一篇文章，每一列对应一个词。

奇异值分解，将这个关联矩阵分成三个，分成三个矩阵，XBY：

X：对词分类，每一行表示一个词，每一列表示一个语义相近的词类，每一行的每个非零元素表示这个词在这个词类中的重要性

Y：对文本分类，每一列对应一个文本，每一行对应一个主题

B：表示词的类和文章的类之间的相关性。每一列的词义类，每一行的主题类

X是一个酉矩阵，Y则是一个酉矩阵的共轭矩阵。

酉矩阵的定义是它和它的共轭矩阵转置相乘等于单位阵，B是一个对角阵。

这个方法的问题是存储量较大，矩阵都需要存在内存里，余弦定理的聚类不需要。

信息指纹及应用

加密，信息压缩和处理。一段文字包含的信息就是它的信息熵，无损压缩编码后理论上最短长度就是它的信息熵。

任何一个信息，都可以对应一个不太长的随机数，作为区别它和其他信息的指纹。

爬虫中URL表使用哈希表来存储，效率不高。将网址信息变化成一个信息指纹，存储到哈希表中。

步骤：

1. 将字符串看作是一个特殊的长度很长的整数

2. 伪随机数产生器算法 PRNG ：将任意很长的整数转换成特定长度伪随机数

3. 1. 梅森旋转算法

加密，信息指纹有不可逆性，无法根据信息指纹推测处原有信息。HTTPS是对Cookies加密也加密。

互联网上加密使用基于加密的伪随机数产生器 CSPRNG，常用算法有MD5或者SHA-1等标准，将不定长的信息变成定长的128位或者160位二进制随机数。

信息指纹的用途

1. 判定集合相同

2. 1. 一一判断，O(N^2)
   2. 哈希表，O(NlogN)，但是额外用N的空间
   3. 使用信息指纹判断，O(N)

3. 判定集合基本相同

4. 1. 找出IDF最大的几个词的信息指纹，使用相似哈希

5. Youtube反盗版

6. 1. 视频里的关键帧，用信息指纹表示

密码学的数学原理

根据信息论，敌方在截获密码后，信息量没有增加，这是坠吼滴。

一般来讲，当密码之间分布均匀且统计独立，提供的信息量最少。

均匀分布使敌方无从统计，统计独立保证敌方看到一段密码和明码后，不能破译另外一段密码。

现在通用的是公开密钥的方法。（

搜索引擎反作弊

利用PageRank链接引用越多就越靠前的漏洞可以作弊。

消除作弊类似于通信中的解决噪音干扰，基本思路：

1. 从信息源出发，加强通信自身的抗干扰能力
2. 从传输来看，过滤掉噪音，还原信息

反作弊的第一条就是增强排序算法的抗噪声能力，其次去噪声，还原真实的排名

原始的信号混入噪音，数学上相当于给两个信号做卷积，噪音消除的过程是一个解卷积的过程，只要知道噪音的频率就行了。

作弊网站有大量出链，彼此之间余弦距离为1，因为都是一个人建的。另一个工具是图论，作弊网站互相链接形成Clique，可以一次清楚。

数学模型的重要性

摘录一些结论：

1. 一个正确的数学模型应当形式上是简单的
2. 一个正确的模型一开始可能不如一个精雕细琢过的错误模型来得准确，但是大方向正确，就应当坚持下去
3. 大量准确的数据对研发很重要
4. 正确的模型也有可能受噪音干扰，而显得不准确，应当找到噪音的根源

最大熵模型

保留全部的不确定性，将风险降低到最小——把鸡蛋放到不同的篮子里。

最大熵原理指出，需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设，在这种情况下，概率分布最均匀，预测的风险最小，信息熵最大。

最大熵模型的训练：

通用迭代算法GIS

1. 假定第零次迭代的初始模型为等概率的均匀分布
2. 用第N次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小
3. 重复步骤2直到收敛

不稳定——改进迭代算法IIS。

拼音输入法的数学原理

输入汉字的快慢取决于对汉字编码的平均长度，击键次数乘以寻找这个键所需的时间。目的是同时优化两个。

对汉字的编码分为两个部分，对拼音的编码和消除歧义性的编码。前期都把功夫放到了对拼音编码上。

香农第一定理：对于一个信息，任何编码的长度都不小于它的信息熵。

一个汉字最少2.1次，利用上下文降低到1.3，这是理想化的。

拼音转汉字的算法，动态规划。把一个拼音串对应的汉字从左到右连起来，就是一张有向图，称为网格图或者篱笆图。找到最优的句子，就是找一条最短的路径。利用维特比算法。

布隆过滤器

用来判断一个元素是否在集合中。

使用哈希表，空间消耗过大，布隆过滤器，只需要哈希表1/8到1/4的大小。这是一个很长的二进制向量和一系列随机映射函数。

对于每一串数字，产生8个不同的随机数信息指纹，映射到8个位置，每个位置置1，这样以后就可以检测了。问题是有一定的误识别率，但不是很大。

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

马尔可夫链：描述一种状态序列，每个状态取决于前面有限个状态。

当各种状态成为一个网络，且马尔可夫假设成立（每个状态只和它直接相连的状态有关，和间接相连的状态没有直接关系），叫做贝叶斯网络。

但是仍然会间接地影响，有相关性，有一个可信度，用概率描述，弧上有附加的权重。

网络中的每一个节点概率的计算，都可以用贝叶斯公式进行。

使用贝叶斯网络必须先确定这个网络的拓扑结构，还要知道各个状态之间的相关的概率，这些都需要训练。

贝叶斯网络可以表示语义相近的词之间的关系，可以用基于统计的模型分析文本，从中抽取概念，分析主题。这样的模型称为主题模型，通过特征向量计算余弦距离是一种。通过贝叶斯网络可以建立另外一种，将文章主题关键词联系成一个贝叶斯网络

条件随机场和句法分析

条件随机场是计算联合概率分布的有效模型。

只需要对语句进行浅层分析，主要词组之间的关系。条件随机场是隐含马尔可夫模型的一种扩展，是一种特殊的概率图模型，变量之间遵循马尔可夫假设，取决于相邻状态。条件概率场是无向图。

量化模型是两个集合的联合概率分布，比如看到词组和背后语法作用。

不能获得足够多的数据来用大数定理直接估计，因此只能通过一些边缘分布来找出一些符合所有这些条件的概率分布函数。

根据最大熵原则，希望找到一个符合所有边缘分布同时熵最大的模型，是指数函数。

维特比算法

解码算法，动态规划算法，解决任何一个图中的最短路径问题。维特比算法针对篱笆网络的有向图的最短路径问题。凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，非常重要。

算法基础：

1. 如果概率最大的路径经过某点，那么这条路径上从起始点到这一段子路径，一定是这之间的最短路径
2. 假定第i个时刻有k个状态，那么记录了起始点到所有k个节点的最短路径，最终的最短路径一定经过其中一条
3. 计算下一个状态时只需要考虑这些最短路径就可以了

维特比算法

1. 从S出发，第一状态的最短路径就是起点到状态的连线
2. 最后的长度等于前一个状态的最短路径到现在两个相邻路径的的长度，最小值
3. 每个相邻路径都如此计算

CDMA技术， 码分多址，根据密码筛选出自己能够解码的内容。

期待值最大化算法

用于文本自动分类。文本自收敛分类，不需要事先设定分类，也不需要对文本两两比较进行合并。

随机挑选一些类的中心，然后优化这些中心。随机挑选中心，计算所有点到聚类中心的距离，重新计算每一类中心，新的中心会有一个位移，知道位移很小，即收敛了。

算法：

1. 根据现有聚类结果，对所有数据重新进行划分，如果把最终得到的分类结果看作是一个数学模型，那么这类聚类的中心，以及每一个点和聚类的隶属的关系，可以看成是这个模型的参数
2. 根据重新划分的结果，得到新的聚类
3. 目标函数

期望值计算过程和最大化过程，称为EM算法。目标函数是凸函数，那么有全局最优解

逻辑回归和搜索广告

点击率和出价有关，所以要最大化点击率，分析影响它的因素。点击率，经验值，与广告新旧有关，位置有关。将所有因素线性组合，影响的各种变量乘上回归参数，表示重要性。

逻辑回归模型，变量取无穷大，但是值域范围限制在0-1。训练模型和最大熵一样。

各个击破算法是Google云计算的基础，分治算法，分成若干个子问题，对结果进行合并。Mapreduce，利用矩阵切分。

计算复杂度

如果一个算法的计算量是N的多项式，则认为这个算法是多项式函数复杂度的。

如果一个问题存在一个多项式函数复杂度的算法，则这个问题为P问题。

如果计算量大于N的多项式函数，实际上不可计算，称为NP问题。

对于一个NP问题，对于一个算法可以在多项式函数复杂度的时间里证实这个方法正确与否，称为NP-complete问题。

如果一个问题，计算复杂度至少为NP-complete，那么称为NP-hard问题。