技术文库

• 

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

  发表者：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 的概念。对于一篇新闻中的所有 实词，我们可以计算出它们的单文本词汇频率/逆文本 ...

  查看全文

• 

  数学应用-Google 阿卡 47 的制造者阿米特.辛格博士

  发表者：Google 研究员，吴军 枪迷或者看过尼古拉斯.凯奇（Nicolas Cage)主演的电影“战争之王”（Lord of War)的人也许还记得影片开头的一段话：（在所有轻武器中，）最有名的是阿卡 47( AK47)冲锋枪(也就是中国的五六式冲锋枪的原型），因为它从不卡壳、从不 损坏、可在任何环境下使用、可靠性好、杀伤力大并且操作简单。 我 认为，在计算机中一个好的算法，应该向阿卡 47 冲锋枪那样简单、有效、 可靠性好而且容易读懂(或者说易操作），而不应该是故弄玄虚。Google 的杰出 工程师阿米特.辛格博士 (Amit Singhal) 就是为 Google 设计阿卡 47 冲 ...

  查看全文

• 

  数学应用-有限状态机和地址识别

  发表者：吴军，Google 研究员 地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方 法，最有效的是有限状态机。 一个有限状态机是一个特殊的有向图（参见有关 图论的系列 ），它包括一些状态 （节点）和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简 单的例子。 每 一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条 弧上带有从一个状态进入下一个状态的条件。比如，在上图中，当前的状态是 “省”，如 果遇到一个词组和（区）县名有关，我们就进入状态“区县”；如 果遇到的下一个词组和城市有关，那么我们就进入“市”的状态，如此等等。如 果一条地址能从状 ...

  查看全文

• 

  数学应用-如何确定网页和查询的相关性

  发表者：吴军，Google 研究员 [我们已经谈过了 如何自动下载网页 、 如何建立索引 、 如何衡量网页的质量 (Page Rank)。我们今天谈谈如何确定一个网页和某个查询的相关性。了解了这四个方 面，一个有一定编程基础的读者应该可以写一个简单的搜索引擎了，比如为您所 在的学校或院系建立一个小的搜索引擎。] 我们还是看上回的例子，查找关于“原子能的应用”的网页。我们第一步是在索 引中找到包含这三个词的网页（详见关于 布尔运算 的系列）。现在任何一个搜索 引擎都包含几十万甚至是上百万个多少有点关系的网页。那么哪个应该排在前面 呢？显然我们应该根据网页和查询“原子能的应用”的相关性对这些网页 ...

  查看全文

• 

  数学应用-贾里尼克的故事和现代语言处理

  发表者：Google 研究员，吴军 读 者也许注意到了，我们在前面的系列中多次提到了贾里尼克这个名字。事实 上，现代语音识别和自然语言处理确实是和它的名字是紧密联系在一起的。我想 在这回的 系列里，介绍贾里尼克本人。在这里我不想列举他的贡献，而想讲一 讲他作为一个普普通通的人的故事。这些事要么是我亲身经历的，要么是他亲口 对我讲的。 弗 莱德里克.贾里尼克(Fred Jelinek)出生于捷克一个富有的犹太家庭。他的父 母原本打算送他去英国的公学（私立学校）读书。为了教他德语，还专门请的一 位德国的家庭女教师，但 是第二次世界大战完全打碎了他们的梦想。他们先是 被从家中赶了出去，流浪到布拉格 ...

  查看全文

• 

  数学应用-信息论在信息处理中的应用

  我们已经介绍了 信息熵 ，它是信息论的基础，我们这次谈谈信息论在自然语言处理中的应用。 先看看信息熵和语言模型的关系。我们在 系列一 中 谈到语言模型时，没有讲如何定量地衡 量一个语言模型的好坏，当然，读者会很自然地想到，既然语言模型能减少语音识别和机器 翻译的错误，那么就拿一个语音识 别系统或者机器翻译软件来试试，好的语言模型必然导 致错误率较低。这种想法是对的，而且今天的语音识别和机器翻译也是这么做的。但这种测 试方法对于研发语 言模型的人来讲，既不直接、又不方便，而且很难从错误率反过来定量 度量语言模型。事实上，在贾里尼克 ( Fred Jelinek ) 的人研究语言模型时，世界上既 ...

  查看全文

• 

  数学应用-图论和网络爬虫 (Web Crawlers)

  发表者: 吴军，Google 研究员 [ 离散数学 是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数 理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算，我们已经 介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句，我们用 Google Trends 来搜索一下“离散数学”这 个词，可以发现不少有趣的现象。比如，武汉、哈尔滨、合肥和长沙市对这一数 学题目最有兴趣的城市。] 我们 上回 谈到了如何建立搜索引擎的索引，那么如何自动下载互联网所有的网页 呢，它要用到图论中的遍历（Traverse) 算法。 图论的起源可 ...

  查看全文

• 

  数学应用-简单之美：布尔代数和搜索引擎的索引

  发表者: 吴军，Google 研究员 [建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多的网页；建立快 速 有 效 的 索 引 ； 根 据 相 关 性 对 网 页 进 行 公 平 准 确 的 排 序 。 我 们 在 介 绍 Google Page Rank (网页排名) 时已经谈到了一些排序的问题，这里我们谈谈索引问题， 以后我们还会谈如何度量网页的相关性，和进行网页自动下载。］ 世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的 运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本 上讲都没有逃出布尔运算的框框。 布尔 （George Boole ...

  查看全文