For attractive lips，speak words of kindness.魅力的双唇，在于亲切而友善的言谈。For lovely eyes,seek out the good in people.迷人的眼睛，在于善于挖掘他人的优点。For a slim figure，share your foodwith the hungry.苗条的身姿，在于你是否能与饥饿的人共享你的食物。For beautiful hair，let a child run his or her fingers through it once a day.美丽的秀发，在于孩子们每天的抚触。For poise, ...

查看全文

发表者：Google（谷歌）研究员 吴军 今天各种汉字输入法已经很成熟了，随便挑出一种主要的输入法比十几年前最好 的输入法都要快、要准。现在抛开具体的输入法，从理论上分析一下，输入汉字 到底能有多快。 我 们假定常用的汉字在二级国标里面，一共有 6700 个作用的汉字。如果不考 虑汉字频率的分布，用键盘上的 26 个字母对汉字编码，两个字母的组合只能对 676 个汉字编码，对 6700 个汉字编码需要用三个字母的组合，即编码长度为三。 当然，聪明的读者马上发现了我们可以对常见的字用较短的编码对不常见的字用 较长的编码，这样平均起来每 个汉字的编码长度可以缩短。我们假定每一个汉 字的频率是 p ...

查看全文

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

查看全文

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

查看全文

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

查看全文

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

查看全文

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

查看全文

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 中国内 部讲课时用了整整一堂课来讲这个问题，下面的内容是我讲座的摘要。］ 在 包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的 提出者托勒密。虽然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了 五大行星 （金、木、水、火、土）运行的轨迹，以及行星在近日点运动比远日 点快。（下图是在地球上看到的金星的轨迹，看过达芬奇密码的读者知道金星大 约每四年在天上 画一个五角星。） 但是真正创立了天文学， ...

查看全文