从Page排名到浏览排名

色盲

www.ddhw.com

马志明：从佩奇排名到浏览排名 数学为因特网建立秩序

 

科学时报 2009-6-9 记者：王丹红

 www.ddhw.com

5月16日上午，中国科学院数学与系统科学院公众科学日院士论坛现场，中国数学会理事长、中国科学院院士马志明发表了演讲。 大屏幕上出现了谷歌的网页，搜索框中的关键词是：数学与系统科学院。在排列着含有这个关键词的各种网页中，中国科学院数学与系统科学研究院的网页位居第一……www.ddhw.com 在搜索框下，马志明用红笔圈了两句话：一句是“约有1860000项符合……的查询结果”，另一句是“搜索时间0.2秒”。然后他问听众：“我们每天都在上网，但什么是互联网信息检索呢？大家看，这里的关键词是‘数学与系统科学院’，谷歌只用0.2秒就查出186万多项相关网页。我的问题是：如果将这186万项信息平铺在你面前，你会得到什么信息呢？” 短暂的停顿后，他自己回答：“你什么都得不到，但对这些网页进行排序后，你知道了什么是最重要的或人们最感兴趣的网页。那么，计算机是如何在0.2秒的时间里就查出这些网页并将它们按序列排出来，而且排得这么好呢？”www.ddhw.com 用这样的开场白，马志明牵出了自己的演讲题目——数学在互联网信息检索中的应用。 “希望能给大家讲懂。”马志明说。 在整个演讲中，从谷歌的“佩奇排名”到最新提出的“浏览排名”概念，马志明向听众讲述了十多年间数学为网络建立新秩序的真实故事。 数学博士生和计算机教授www.ddhw.com 世界上第一个网站是英国计算机专家蒂姆·伯纳斯-李于1991年8月6日创立的，它解释互联网是什么，如何使用网页浏览器和如何建立一个网页服务器。 到1995年，网络文件总数据估计已达1000万张，但对互联网上网页的排名，人们几乎没有什么办法。“当时，也有一些搜索引擎公司希望为用户服务，输入关键词后，就会有相关网页排出来。但是，人们的做法是将页面读懂，再根据页面内容来决定它的重要性和排序。”马志明说。www.ddhw.com “但大家想想，这么多的页面，怎么能在很短的时间内读出来呢？而且，页面的内容重要还是不重要，也是见仁见智的事，没有统一标准。所以在那段时期，这个问题很混乱，不知道该怎么办，直至1998‘链接分析法’的出现。其中，最著名的算法就是佩奇排名和HITS算法，才革命性地改变了网络世界。” 实际上，网络研究的学术革命开始于1995年。这一年春天，在斯坦福大学校园，计算机科学院的新博士生拉里·佩奇遇见了博士二年级的谢尔盖·布林。 佩奇大学毕业于密歇根大学安娜堡分校，他的父亲是密歇根州立大学的计算机专业教授。www.ddhw.com 佩奇从父亲那里了解到，博士论文可以成为一个人学术生涯的基础。在斯坦福大学的第一年，他选择用户界面研究先驱特里·威诺格做他的导师，开始寻找一个有研究价值的博士论文题目。 最初，佩奇只是因网络的数学特征而对网络产生了兴趣。他发现每台计算机都是一个节点，网页上的每一条链接就是这些节点间的联系，这样就构成了一个经典的图结构。“计算机科学家最喜欢图”，他认为互联网很可能是有史以来人类创造出的最大的图，这张图的节点中隐藏着很多启示，他决定探索互联网中的数学特征。而导师威诺格鼓励他这样做。 佩奇后来回忆说：“这是我得到的最好的建议。”www.ddhw.com 佩奇开始思索网络中链接结构的奥妙，他发现尽管跟着链接可以从一张网页转到另一张网页，但沿着这些链接往回走就不行了。他想找到一种方法，可以让各个网页能轻松找出并说明指向它们的链接。 美国文献引用分析之父加菲尔德的学术思想给了他启发。www.ddhw.com 加菲尔德认为，发表论文是研究人员最重要的工作之一，基本上每篇论文的结论都建立在谨慎构建的引文基础上，而每篇新论文也可能成为新的文献被他人引用，因此，文献的引用和被引用体现了学术发展的逻辑性结构；一篇论文的重要性可以根据有多少篇论文通过引用而同它建立联系来确定，这个体系为已出版的论文提供了一种等级评定的方法。 正是基于这种引用和被引用的思想，蒂姆·伯纳斯-李在计算机上通过技术和超文本链接发明了万维网。佩奇则发现，链接就是万维网上的引用和被引用，整个网络就是由引用和注评构成的松散体系，而早期的网络超链接文本有一个缺陷：不能反向追踪链接。佩奇想，如果能找到一种方法来计算反向链接的数量并衡量它的质量，那么，“网络就会成为一个更有价值的地方”。www.ddhw.com 佩奇将自己的研究项目命名为“反向链接”（BackRub），这个项目的宗旨是追踪并发现网络中的链接，存储它们并进行分析，然后在网络上重新发布它们。佩奇估计，当时网络文件的数量大约为10000万张，而它们的链接数量则可能达1亿。这个项目的复杂性和规模吸引了还在确定论文选题的布林，于是他加入这个项目，从此，两人开始合作。 在完成网络搜索并存储了链接图之后，还需要找到评定等级的方法。这时，佩奇发现，对所有指向某网页的链接数量的计算对于确定该网页的等级具有指导意义，这种方法带来了新的挑战——困难而复杂的递归性数学运算。布林的数学天赋提供了帮助。他们发明了一种新算法，基于重要的来源链接来评价网页的重要性，这种算法以佩奇的姓（Page）命名，因此叫佩奇排名（PageRank）。www.ddhw.com 当佩奇和布林在斯坦福的校园埋头研究网页排名的算法时，在IBM位于圣何塞市的阿尔马登研究中心，来自康奈尔大学的计算机教授乔恩·克莱因伯格正在这里做访问科学家，他也在研究网络评级方法，他提出了中心网页和权威网页的评级系统，并完成了创造性著作《权威性来源》的草稿。 1998年革命性的论文 一本记录谷歌公司成长的书《搜》中，作者约翰·巴利特说，“PageRank促成谷歌建立神秘技术配方……尽管当时佩奇和布林还不知道，但他们早期的评级系统为一个全新网络生态环境的形成开辟了道路。”www.ddhw.com 在佩奇和布林发明了PageRank算法后，他们编写了一个PageRank搜索工具，然后用PageRank来为结果的相关性排序。他们发现，网络越大，链接越多，这个引擎提供的结果就越准确，于是，他们将新引擎命名为Google，这是Googol的变体，Googol是一个数字名词，表示10的100次方。1996年8月，他们在斯坦福的网站上发布了第一个Google版本。 1997年夏天，克莱因伯格在斯坦福会见了佩奇，交换了关于搜索的观点和各自的工作，克莱因伯格鼓励佩奇发表一篇关于PageRank的论文，但佩奇“担心有人窃取他的思想”，因此对发表论文的态度很谨慎。最后，学术名声战胜了产权保护的冲击，双方同意在彼此的论文中相互引用。www.ddhw.com 克莱因伯格的论文《超链接环境下权威来源》发表在1998年出版的《第九届ACM-SIAM离散算法会刊》上。他在这篇文章中提出的中心网页和权威网页的评价系统，被巴利特评价为“最著名的网络评级方式”。巴利特说，“在学术性网络研究这个自成一体的世界里，这篇文章的影响仅次于佩奇和布林介绍谷歌的论文。” 1998年初，佩奇将他的第一篇论文，也就是对PageRank算法的总结介绍，提交给美国计算机学会（ACM）信息提取特别兴趣组，但论文被拒绝了。一位评审专家的意见是：“论文的整体结构缺乏连贯性……文章应侧重于信息的提取而不是网络分析。”佩奇坚持投稿，最后，这篇论文作为斯坦福大学数字图书馆项目的一部分被发表了。www.ddhw.com 不久后，佩奇和布林联合发表了一篇关于谷歌的论文——《大规模超文本网络搜索引擎剖析》，如今，这篇论文已经成为目前世界上被引用最广泛的搜索类文献。 1998年底，佩奇和布林决定要开办一家公司，当第一位投资人准备为他们开支票时，两人还没有想好公司的名字，这位投资人建议他们就用这项搜索服务的名字Google，两人同意了。几分钟后，他们得到了一张10万美元的支票。 2001年9月，PageRank被授予美国专利，专利被正式颁发给斯坦福大学，佩奇作为发明人列于文件中；2006年，国际数学联盟将“奈望林纳奖”授予克莱因伯格，以表彰他在计算机科学的数学方面的杰出贡献。www.ddhw.com 马志明说，1998年后，信息检索领域出现了“链接分析法”，PageRank和HITS是其中最著名的算法，实际上，这两个算法就是用数学原理在对网页进行排序。他说：“一个看似很困难的实际问题，用一个巧妙的数学方法就解决了，所以，数学的用处有时真是不可估量。” 让用户为页面重要性投票 马志明指出了PageRank在网页排序中的局限性。www.ddhw.com “从1998年到现在，PageRank经过11年运转，取得了巨大成功，同时它的缺点也暴露出来了。因为它对网页的排序是静态的，只考虑页面在整个互联网中的拓扑结构，所以，有人可以作弊，通过多做一些超级链接来显示页面的重要性，因此有这样的公司，自己搞个服务器，让许多页面互相链接，如果对方给钱，公司就将你的页面链接上去，从而恶意提高页面排序。谁能控制超级链，谁就能控制页面的重要性。但这不符合实际情况。”www.ddhw.com “实际情况是，我们在上网时会有自己的感情，当我们观察一个页面时，如果这个页面重要，我们会静下心来仔细阅读它；如果这个页面不重要，我们很快就会离开它，所以，用户才是判断页面重要性真正的标准。但用户的感情、上网时间因素在PageRank中是没有的，这是它的缺点，许多搜索引擎公司也都在想办法克服这个缺点。” 2008年7月，在新加坡召开的第31届国际信息检索大会上，一位年轻人报告了他们的论文——《浏览排序：让因特网用户为页面重要性投票》，论文获得了会议设立的唯一最佳学生论文奖。 这位年轻人就是马志明的博士生刘玉婷，那时她正在微软亚洲研究院做实习生。www.ddhw.com 论文的基本思想是，利用大量用户访问网页的信息来估计网页的重要性。每个搜索引擎公司都有大量的不含隐私的用户上网记录。“不同的人对于用户上网记录有不同的解读”，马志明说。 据马志明介绍，他本人是研究随机过程的，他从用户上网记录中看到了一个真实的过程。这个过程是一个随机过程，可以称为浏览过程（Browsing Process）。这个过程在不同的网页之间跳来跳去，从数学上可以将其归类为跳过程，或者随机点过程（把网页看作点）。数学家对于随机点过程有许多研究，已经有丰富的研究成果。www.ddhw.com 马志明分析：当用户浏览一个网页时，他下一步跳转到哪一个网页，停留多长时间跳转，大概只依赖于当前的状态，而与他浏览网页的过去历史无关。因此从数学上，这应该是一个马氏过程（给定现在，将来与过去无关）。 再有，用户在一个网页的停留时间，以及他下一步跳转到哪一个网页，都只与他正在浏览的网页内容以及网页的超级链接有关，大概与他在什么时间点（8点或9点，上午或下午）浏览此网页无关。因此，这个马氏过程应该是时间可推移的，或者说是时间齐次的。再加上浏览过程的状态是有限的（网页的总数是有限），因此，浏览过程很可能是一个有限状态时间齐次马氏过程，即Q过程。www.ddhw.com 对于中国的概率学家而言，Q过程是一个熟悉的数学对象，中国学者在这个方向有世界领先的研究成果。当然，实践是检验真理的唯一标准，浏览过程是否时间齐次马氏过程，还需要用实际数据作统计检验。一个可行的检验方法，是验证用户在网页上的停留时间是否服从负指数分布。因为根据数学理论，Q过程在每个状态的停留时间必然服从负指数分布。 由刘玉婷设计算法，微软亚洲研究院的相关研究组用真实数据作了大量实验模拟，发现用户在网页的停留时间基本服从负指数分布。通过反复论证，确信随机过程中的Q过程理论可以很好地对这个问题进行建模。Q过程的平稳分布，也就是在时间趋于无穷时的极限分布，在理论上正好是用户在某页面平均停留时间与再次回访此页面平均间隔时间之比。网页越重要，平均停留时间就越长，该网页的平稳分布值就越大；网页越重要，再次回访此网页的平均间隔时间就越短，该网页的平稳分布值就越大。因此，浏览过程的平稳分布可以作为衡量网页重要性的指标。这个浏览过程的平稳分布，就是我们所说的浏览排序（Browse Rank）。www.ddhw.com 当然，要设计一套可行的算法真正计算出浏览排序，并非易事。微软亚洲研究院的相关课题组克服了重重困难，每一步都在课题组内反复论证，深入探讨，反复模拟实验。这里含有许多奇思构想和巧妙的数学。微软亚洲研究院从产品部门调来大量数据，做了大规模模拟实验。 据马志明介绍，在新加坡获奖的这篇论文，从第一版写出来以后，在微软的课题组内反复修改了81次才成为最终稿。 新加坡会议后，“浏览排序”成了业内热门话题，在互联网搜索工业界引起广泛关注和讨论。www.ddhw.com 马志明强调，“作为一个数学工作者，我认为Browsing Process（浏览过程）的重要性应该不亚于Browse Rank。这是第一个刻画真实的用户上网行为的数学框架。我相信今后人们在研究用户上网行为时，一定会想到Browsing Process，应用并发展Browsing Process的理论和实践。在这一方向还有许多课题需要进一步研究。” 最后，马志明希望学生们能把这个网页排序的故事讲给自己的亲朋好友，让他们知道“数学非常好用”。www.ddhw.com

 

 

 

www.ddhw.com

 

  本贴由[色盲]最后编辑于：2009-6-17 3:7:7  

www.ddhw.org---

据说这世界是彩色的？

 

tcpip004

学习了。www.ddhw.com