数字之美

数字之美
读完《数字之美》一书，让我不由由衷地感叹数学模型之妙。想我还是数学专业出身，历经课程学习、数学建模竞赛、考研、求职季笔试，如人搜考了很多离散数学等，却从未想过这些数学知识在互联网的应用场景。读此书有茅塞顿开的酣畅淋漓之感。
本书笔记摘录如下：
统计语言模型
事实证明，统计语言模型比任何已知的借助某种规则的解决方法都有效。用贝叶斯公式（Google 的中英文自动翻译中使用它）后，李开复用统计语言模型把 997 词语音识别的问题简化成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。
统计语言模型在中文处理中的一个应用。
隐含马尔可夫模型是一个数学模型，到目前为之，它一直被认为是实现快速精确的语音识别系统的最成功的方法。
 
度量信息
1948 年，香农提出了“信息熵”(shāng) 的概念，才解决了对信息的量化度量问题。，信息量的度量就等于不确定性的多少。
在互联网或计算机中，用 “比特”（bit）这个概念来度量信息量。
变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。
 
布尔代数和搜索引擎的索引
世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的框框。
    布尔代数简单得不能再简单了。运算的元素只有两个1 （TRUE， 真) 和 0
（FALSE，假)。基本的运算只有“与”（AND)、“或” (OR) 和“非”（NOT) 三种
。今天的搜索引擎相比之下要聪明的多，它自动把用户的查询语句转换成布尔运算的算式最简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位对应一篇文献，1 代表相应的文献有这个关键字，0 代表没有。整个索引就变得非常之大，以至于不可能用一台计算机存下。大家普遍的做法就是根据网页的序号将索引分成很多份（Shards)，分别存储在不同的服务器中。每当接受一个查询时，这个查询就被分送到许许多多服务器中，这些服务器同时并行处理用户请求，并把结果送到主服务器进行合并处理，最后将结果返回给用户。
 
图论和网络爬虫
离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算，那么如何自动下载互联网所有的网页呢，它要用到图论中的遍历（Traverse) 算法。图论的起源自欧拉。
互联网其实就是一张大图，我们可以把每一个网页当作一个节点，把那些超链接（Hyperlinks)当作连接网页的弧。当你点下去的的时候，浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫。
在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。
 
信息论在信息处理中的应用
信息论中仅次于熵的另外两个重要的概念是“互信息”（Mutual Information) 和“相对熵”（Kullback-Leibler Divergence)。
“互信息”是信息熵的引申概念，它是对两个随机事件相关性的度量。
在自然语言处理中，经常要度量一些语言现象的相关性。比如在机器翻译中，最难的问题是词义的二义性（歧义性）问题。比如 Bush 一词可以是美国总统的名字，也可以是灌木丛。具体的解决办法大致如下：首先从大量文本中找出和总统布什一起出现的互信息最大的一些词，比如总统、美国、国会、华盛顿等等，当然，再用同样的方法找出和灌木丛一起出现的互信息最大的词，比如土壤、植物、野生等等。有了这两组词，在翻译 Bush 时，看看上下文中哪类相关的词多就可以了。
信息论中另外一个重要的概念是“相对熵”，在有些文献中它被称为成“交叉熵”。在英语中是 Kullback-Leibler Divergence，是以它的两个提出者库尔贝克和莱伯勒的名字命名的。相对熵用来衡量两个正函数是否相似，对于两个完全相同的函数，它们的相对熵等于零。在自然语言处理中可以用相对熵来衡量两个常用词（在语法上和语义上）是否同义，或者两篇文章的内容是否相近等等。利用相对熵，我们可以到处信息检索中最重要的一个概念：词频率-逆向文档频率（TF/IDF)。
 
如何确定网页和查询的相关性
短语“原子能的应用”可以分成三个关键词：原子能、的、应用。根据我们的直觉，我们知道，包含这三个词多的网页应该比包含它们少的网页相关。当然，这个办法有一个明显的漏洞，就是长的网页比短的网页占便宜，因为长的网页总的来讲包含的关键词要多些。因此我们需要根据网页的长度，对关键词的次数进行归一化，也就是用关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”，或者“单文本词汇频率”（Term Frequency)，比如，在某个一共有一千词的网页中“原子能”、“的”和“应用”分别出现了 2 次、35 次 和 5 次，那么它们的词频就分别是 0.002、0.035 和 0.005。我们将这三个数相加，其和 0.042 就是相应网页和查询“原子能的应用”。
相关性的一个简单的度量。概括地讲，如果一个查询包含关键词 w1,w2,...,wN, 它们在一篇特定网页中的词频分别是: TF1, TF2, ..., TFN。 （TF: term frequency)。 那么，这个查询和该网页的相关性就是:
TF1 + TF2 + ... + TFN。
它对确定网页的主题几乎没有用。我们称这种词叫“应删除词”（Stopwords)，也就是说在度量相关性是不应考虑它们的频率。在汉语中，“应用”是个很通用的词，而“原子能”是个很专业的词，后者在相关性排名中比前者重要。因此我们需要给汉语中的每一个词给一个权重，这个权重的设定必须满足下面两个条件：
1. 一个词预测主题能力越强，权重就越大，反之，权重就越小。
2. 应删除词的权重应该是零。
在信息检索中，使用最多的权重是“逆文本频率指数” （Inverse document frequency 缩写为ＩＤＦ），它的公式为ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部网页数。
 
有限状态机和地址识别
地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方法，最有效的是有限状态机。
一个有限状态机是一个特殊的有向图。每一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。
使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。好在。有了关于地址的有限状态机后，我们就可又用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，我们也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找的内容：当用户输入的地址不太标准或者有错别字时，有限状态机会束手无策，因为它只能进行严格匹配
为了解决这个问题，我们希望有一个能进行模糊匹配、并给出一个字串为正确地址的可能性。为了实现这一目的，科学家们提出了基于概率的有限状态机。
 
余弦定理和新闻的分类（初中的知识啊）
Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字来描述一篇新闻。
对于一篇新闻中的所有实词，我们可以计算出它们的单文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率高，TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。如果单词表中的某个次在新闻中没有出现，对应的值为零。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。
我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。
学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角了。
当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；当夹角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不相关。
 
信息指纹及其应用
任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹。
信息指纹在加密、信息压缩和处理中有着广泛的应用。
在哈希表中纪录已经访问过的网址（URL)。但是在哈希表中以字符串的形式直接存储网址，既费内存空间，又浪费查找时间。现在的网址一般都较长。可以找到一个函数，样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降低到原来的 1/6。这个16 个字节的随机数，就称做该网址的信息指纹。
产生信息指纹的关键算法是伪随机数产生器算法。
信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说, 无法根据信息指纹推出原有信息，这种性质， 正是网络加密传输所需要的。比如说，一个网站可以根据用户的Cookie 识别不同用户，这个 cookie 就是信息指纹。
 
不要把所有的鸡蛋放在一个篮子里-谈谈最大熵模型
在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为最大熵原理。说白了，就是要保留全部的不确定性，将风险降到最小。
最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。
如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。
闪光的不一定是金子 -- 谈谈搜索引擎问题
自从有了搜索引擎，就有了针对搜索引擎网页排名的作   弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。
搜索引擎的作    弊，虽然方法很多，目的只有一个，就是采用不正当手段提高自己网页的排名。早期最常见的方法是重复关键词。
 
矩阵运算和文本处理中的分类问题
在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种分类问题都可用通过矩阵运算来圆满地、同时解决余弦定理和新闻分类中介绍的方法，。从理论上讲，这种算法非常好。但是计算时间特别长在文本分类中，另一种办法是利用矩阵运算中的奇异值分解。
我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，TF/IDF)。
奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的矩阵B，和一个一百乘以五十万的矩阵Y相应的存储量和计算量都会小三个数量级以上。
三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。
 
马尔可夫链的扩展 贝叶斯网络
有向图看成一个网络，它就是贝叶斯网络 在网络中每个节点概率的计算，可以用贝叶斯公式来进行，贝叶斯网络因此而得名。由于网络的每个弧有一个可信度，贝叶斯网络也被称作信念网络 (belief networks)。
使用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。
 
布隆过滤器
计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，即多哈希映射Bloom哈希。
 
基于拼音的简单输入法占统治地位的原因：事实上，汉语全拼的平均长度为 2.98，只要基于拼音的输入法能利用上下文彻底解决一音多字的问题，平均每个汉字输入的敲键次数应该在三次左右，每分钟输入 100 个字完全有可能达到。
 
摩尔定理：每十八个月，计算机等 IT 产品的性能会翻一番；或者说相同性能的计算机等 IT 产品，每十八个月价钱会降一半。
一个 IT 公司如果今天和十八个月前卖掉同样多的、同样的产品，它的营业额就要降一半。IT 界把它称为反摩尔定理。