基础学科

• 

  数学应用-谈谈密码学的数学原理

  发表者：Google（谷歌）研究员 吴军 前一阵子看了电视剧《暗算》，蛮喜欢它的构思和里面的表演。其中有一个故事 提到了密码学，故事本身不错，但是有点故弄玄虚。不过有一点是对的，就是当 今的密码学是以数学为基础的。（没有看过暗算的读者可以看一下介绍， 因为我们后面要多次提到这部电视剧。） 密码学的历史大致可以推早到两千年前，相传名将凯撒为了防止敌方截获情报， 用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表， 比如说 这 样，如果不知道密码本，即使截获一段信息也看不懂，比如收到一个的消息 是 EBKTBP，那么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAES ...

  查看全文

• 

  数学应用-布隆过滤器（Bloom Filter）

  发表者：Google（谷歌）研究员 吴军 在 日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一 个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是 要判断它 是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑 名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合 中全部的元素存在计算机中，遇到一个新 元素时，将它和集合中的元素直接比 较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的 好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是 当集合巨大时，哈希表存储效率低的问题就 ...

  查看全文

• 

  数学应用-自然语言处理的教父 马库斯

  发表者：Google 研究员，吴军 我 们在前面的系列中介绍和提到了一些年轻有为的科学家，迈克尔·柯林斯， 艾里克·布莱尔，大卫·雅让斯基，拉纳帕提等等，他们都出自宾夕法尼亚计算 机系米奇 ·马库斯(Mitch Marcus)名下。就像许多武侠小说中描写的，弟子都 成了各派的掌门，师傅一定了不得。的确，马库斯虽然作为第一作者发表的论文 并不多，但是从很多角度 上讲，他可以说是自然语言处理领域的教父。 马库斯教授长期当任宾夕法尼亚大学计算机系主任，直到他在几年前从 AT&T 找 到皮耶尔替代他为止。作为一个管理者，马库斯显示出在自然处理和计算机科学 方面的卓识的远见。在指导博士生时， ...

  查看全文

• 

  数学应用-马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks)

  我们在前面的系列中多次提到 马尔可夫链 (Markov Chain) ， 它描述了一种状态序列，其每个状态值取决于前面有限个状态。这种模型，对很 多实际问题来讲是一种很粗略的简化。在现实生活中，很多事物相互的关系并不能用 一条 链来串起来。它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到，心血管 疾病和它的成因之间的关系是错综复杂的。显然无法用一个链来表 示。 我们可以把上述的 有向图 看 成一个网络，它就是贝叶斯网络。其中每个圆圈表示一个状态。 状态之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病 可能和吸 烟有关。当然，这些关系可以有一个量化的可信 ...

  查看全文

• 

  数学应用-矩阵运算和文本处理中的分类问题

  发表者：Google 研究员，吴军 我 在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还 能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。 后来在 数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。 当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似 的经历。直到 后来长期做自然语言处理的研究，我才发现数学家们提出那些矩 阵的概念和算法，是有实际应用的意义的。 在自然语言处理中，最常见的两类的分 类问题分别是，将文本按主题归类（比 如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如 将各种体育运动的 ...

  查看全文

• 

  数学应用-闪光的不一定是金子–谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)

  Google 研究员 吴军 自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发 现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一 定是金子。 搜索引擎的作弊，虽然方法很多，目的只有一个，就是采用不正当手段提高自己 网页的排名。早期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站， 重复地罗列各种数码相机的品牌，如尼康、佳能和柯达等等。为了不让读者看到 众多讨厌的关键词，聪明一点的作弊者常用很小的字体和与背景相同的颜色来掩 盖这些关键词。其实，这种做法很容易被搜索引擎发现并纠正。 在有了网页排名(page rank)以后，作弊者发现一个网页 ...

  查看全文

• 

  数学应用-不要把所有的鸡蛋放在一个篮子里–最大熵模型（下）

  发表者：Google 研究员，吴军 我们 上次谈到 用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有 回答，就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形 式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。 最 原 始 的 最 大 熵 模 型 的 训 练 方 法 是 一 种 称 为 通 用 迭 代 算 法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂，大致可以概括为以下 几个步骤： 1. 假定第零次迭代的初始模型为等概率的均匀分布。 2. 用第 N 次迭代的模型来估算每种信息特征在训练数 ...

  查看全文

• 

  数学应用-不要把所有的鸡蛋放在一个篮子里–谈谈最大熵模型（上）

  发表者：Google 研究员，吴军 [我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。 在信息处理中，这个原理同样适用。在数学上，这个原理称为 最大熵原理 (the maximum entropy principle)。这是一个非常有意思的题目，但是把它讲清楚要 用两个系列的篇幅。] 前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息 有上百种。更普遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不 完全确定的信息，我们需要用一个统一的模型将这些信息综合起来。如何综合得 好，是一门很大的学问。 让 我们看一个拼音转汉字的简单的例子。假如输入 ...

  查看全文

• 

  数学应用-繁与简 自然语言处理的几位精英

  发表者：吴军，Google 研究员 我 在数学之美系列中一直强调的一个好方法就是简单。但是，事实上，自然语 言处理中也有一些特例，比如有些学者将一个问题研究到极致，执著追求完善甚 至可以说 完美的程度。他们的工作对同行有很大的参考价值，因此我们在科研 中很需要这样的学者。在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 ( Michael Collins ) 就是这样的人。 柯林斯：追求完美 柯 林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后还会多次提 到马库斯），从宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教 授（别看他是副教授，他的水平在当 ...

  查看全文

• 

  数学应用-谈谈数学模型的重要性

  发表者：吴军，Google 研究员 [注：一直关注数学之美系列的读者可能已经发现，我们对任何问题总是在找相 应的准确的数学模型。为了说明模型的重要性，今年七月份我在 Google 中国内 部讲课时用了整整一堂课来讲这个问题，下面的内容是我讲座的摘要。］ 在 包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的 提出者托勒密。虽然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了 五大行星 （金、木、水、火、土）运行的轨迹，以及行星在近日点运动比远日 点快。（下图是在地球上看到的金星的轨迹，看过达芬奇密码的读者知道金星大 约每四年在天上 画一个五角星。） 但是真正创立了天文学， ...

  查看全文

• 

  数学应用-信息指纹及其应用

  发表者：吴军，Google 研究员 任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的 指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就 如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。 我们在 图论和网络爬虫 一 文中提到，为了防止重复下载同一个网页，我们需要 在哈希表中纪录已经访问过的网址（URL)。但是在哈希表中以字符串的形式直接 存储网址，既费内存空间， 又浪费查找时间。现在的网址一般都较长，比如， 如果在 Google 或者百度在查找数学之美，对应的网址长度在一百个字符以上。 下面是百度的链接 m/s?ie= ...

  查看全文

• 

  数学应用-余弦定理和新闻的分类

  发表者：吴军，Google 研究员 余弦定理和新闻的分类似乎是两件八杆子打不着的事，但是它们确有紧密的联 系。具体说，新闻的分类很大程度上依靠余弦定理。 Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放 到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算 法来算出任意两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字 来描述一篇新闻。 我们来看看怎样找一组数字，或者说一个向量来描述一篇新闻。回忆一下我们在 “ 如何度量网页相关性 ” 一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有 实词，我们可以计算出它们的单文本词汇频率/逆文本 ...

  查看全文