数学之美 系列十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)

11/28/2006 03:18:00 上午

Google 研究员 吴军

自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。

固定链接  |  引用此贴的链接  |

Google（谷歌）全球编程挑战赛中国获奖选手（花絮）

11/20/2006 09:12:00 上午

发表者：吴丹丹，Google 黑板报小组

2006 年 Google（谷歌）全球编程挑战赛刚刚落下帷幕，来自中国的选手王颖夺得本次比赛的第二名，另有 6 名选手进入前 50 名，本次比赛共有 13 名中国选手成功入围前 100 名，据了解，此次中国进入决赛的选手人数仅次于俄罗斯。这里与大家分享一些比赛的小花絮。

“我是中国人！”

“我是中国人！我希望能与中国同胞分享我的喜悦！” 这是来自中国的王颖在获得 2006 Google(谷歌)编程大赛亚军后写给 Google(谷歌)的第一句话。他的自豪溢于言表，这位身高近 1.9 米的年仅 22 岁的小伙子毕业于中山大学，目前正在美国斯坦福大学攻读数学博士学位。

这位说自己不是天才，只在初中跳过一次级的王颖在接受访问时谦虚地说他能获得第二名要归功于好运和不错的临场发挥，但了解了他的经历之后发现他的获奖并不是简单的幸运和临场发挥。王颖可以说是世界顶级编程大赛的常客，多次入围全球著名编程赛事 ACM，Topcoder，微软创新杯等比赛的决赛。在今年的决赛中，王颖凭借自己扎实的数学功底及严谨的逻辑思维，成功地完成了难度值最大的题，并且在最后的 PK 环节胜出。

获得第二名之后，王颖说自己一直就有冠军梦，虽然这次离冠军还有一步之遥，他说他已经很满足了，对自己的冠军梦不会有遗憾了。

“中国造” 的编程神童

除了王颖获奖，来自广东中山的高三学生余江伟也很突出。作为今年决赛中唯一的一名中学生选手，年纪最小的余江伟显得格外的引人注目，在强手林立的决赛中，余江伟最终获得了全球第 96 名的好成绩。

余江伟从小就对编程有浓厚的兴趣，并在这方面展示出了非凡的才能。还在小学就读四年级期间，余江伟就夺得了全国国际象棋冠军，出色的逻辑思维和能力使他在计算机编程方面很早就显示了非凡的才能，在参加 Google（谷歌）的编程大赛之前，他在 7 月份的全国信息学奥林匹克大赛中获得了一等奖。他是无意中在网上获知 Google（谷歌）编程大赛的相关信息，报着试试看的心态报名参加了比赛。在随后的预赛中，余江伟经过三轮‘厮杀’，成功地以预赛第 22名的成绩入围决赛。

在本次比赛中晋级全球百强的 13 名中国选手中，有 11 人来自于高校。4 名来自清华大学的学生全部进入了前 50强，有一位来自复旦大学的学生获得了第十五名的成绩，是仅次于王颖的第二好成绩。

固定链接  |  引用此贴的链接  |

数学之美 系列十六 （下）－ 不要把所有的鸡蛋放在一个篮子里　最大熵模型

11/16/2006 06:50:00 上午

发表者：Google 研究员，吴军

我们上次谈到用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答，就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。

最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤：
1. 假定第零次迭代的初始模型为等概率的均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。
3. 重复步骤 2 直到收敛。

GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨（Csiszar)解释清楚的，因此，人们在谈到这个算法时，总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。

八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有 IBM 有条件是用最大熵模型。

由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理的希望。

但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是对的。从此，我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后，为了训练一个包含上下文信息，主题信息和语法信息的文法模型(language model)，我并行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。

最大熵模型，可以说是集简与繁于一体，形式简单，实现复杂。值得一提的是，在Google的很多产品中，比如机器翻译，都直接或间接地用到了最大熵模型。

讲到这里，读者也许会问，当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗？他们在九十年代初贾里尼克离开 IBM 后，也退出了学术界，而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道，决定股票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮垂兄弟等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预测，获得了巨大的成功。从该基金 1988 年创立至今，它的净回报率高达平均每年 34%。也就是说，如果 1988 年你在该基金投入一块钱，今天你能得到 200 块钱。这个业绩，远远超过股神巴菲特的旗舰公司伯克夏哈撒韦（Berkshire Hathaway)。同期，伯克夏哈撒韦的总回报是 16 倍。

值得一提的是，信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，在华尔街多有直接的应用。由此可见，数学模型的作用。

固定链接  |  引用此贴的链接  |