网页排序中的随机模型及算法

论文摘要

随着互联网规模的日益增长,搜索引擎已经成为互联网上最有效的信息获取工具.而在众多搜索引擎的背后,是信息检索技术,也即网页排序算法在起作用.网页排序根据所依赖的准则不同,又分为重要性和相关性两类排序.传统的研究方法是将两类问题分离开独立研究的.每类问题都对应着各自的算法,而算法之间没有共同点.通过我们研究发现,尽管这两类问题各不相同,但是都可以通过随机过程来模拟排序的过程.因此,在这个共同的基础上,我们分别讨论了两类排序问题中的随机过程模型,并设计了相应的算法.首先,在网页重要性排序中,我们通过分析用户浏览网页的行为建立了马氏骨架过程的框架.基于该框架发现,用户评价网页重要程度的标准包含两项:访问率和停留时问,而马氏骨架过程的平稳分布（在特殊条件下存在）可以恰当地反映这两项信息.同时在框架内,我们分析了三种不同的随机过程模型对用户行为模拟的合理程度,并设计了名为BrowseRank的一组新算法（本论文中提出了八种实现模型）.通过与传统算法的实验对比,验证了随机过程框架的合理性和BrowseRank的高性能.并且其中一种实现模型在2008年国际信息检索大会（SIGIR）上一经提出,就受到学术界和工业界的高度关注.不仅论文被大会评为唯一一篇最佳学生论文,而且BrowseRank算法作为一项技术也被业界予以高度评价.各大新闻媒体（如CNET.com,WebProNews等）争相报道这一成果,并组织多次访谈节日,邀请各大搜索引擎的运营高层和研究人员从技术角度分析评价该算法,如WebProNews Video的访谈节目《MSN on BrowseRank》等.其次,在网页相关性排序中,我们主要针对排序结果联合问题建立了一个基于马氏链的监督学习框架.通过该框架,我们验证了对联合排序的两个方面的改进.首先是,监督学习方法对排序结果联合问题的必要性,通过将传统方法的监督化,使的原来很难解决的问题变的易于学习.其次是,马氏链方法在模拟排序信息传递过程的高效和高性能,将原来的NP-难问题转化为一个半正定规划问题,提高了效率.通过检验随机过程模型在两类排序问题中的有效性,我们总结出排序过程和随机过程的共同点:1)排序过程中待排网页之间的关系可以通过状态之间的跳转来模拟.2)排序过程就是一个将网页之间各种各样的关系因素综合起来考虑,并最终达到一个稳定状态的过程;而随机过程中,系统在状态之间跳转权衡,直到达到平衡,以马氏过程为例,其平稳概率分布就是跳转达到平衡后的分布.因此,将随机过程的思想应用到排序问题中是个合理的尝试,而我们在两类排序中取得的成果,也验证了这一想法,为以后更多的理解排序问题奠定了基础.

论文目录

• 致谢
• 中文摘要
• 英文摘要
• 第1章 绪论
• 1.1 引言
• 1.2 研究背景
• 1.2.1 信息检索和互联网搜索
• 1.2.2 搜索引擎的结构
• 1.3 本文的主要贡献和创新点
• 第2章 网页排序问题
• 2.1 引言
• 2.2 网页重要性排序
• 2.2.1 问题描述
• 2.2.2 研究发展历史
• 2.3 网页相关性排序
• 2.3.1 问题描述
• 2.3.2 相关课题
• 2.3.3 排序结果联合问题的研究发展历史
• 第3章 网页重要性排序中的随机过程模型
• 3.1 引言
• 3.2 传统的网页重要性排序算法
• 3.2.1 链接分析法
• 3.2.2 基于网络日志信息的方法
• 3.3 随机过程模型
• 3.3.1 用户浏览网页过程
• 3.3.2 马氏骨架过程模型
• 3.4 BrowseRank算法
• 3.4.1 用户信息提取
• 3.4.2 参数估计
• 3.4.3 算法汇总
• 3.5 算法分析与实验
• 3.5.1 算法效果的评价准则
• 3.5.2 网页级别实验分析
• 3.5.3 网站级别实验分析
• 3.6 本章小结
• 第4章 网页相关性排序中的随机过程模型
• 4.1 引言
• 4.2 排序结果联合问题的定义及算法介绍
• 4.2.1 问题定义
• 4.2.2 非监督学习方法
• 4.3 排序联合问题的监督学习框架
• 4.3.1 一般形式
• 4.3.2 对已有算法的扩展
• 4.4 基于马氏链的监督学习算法
• 4.4.1 模型求解
• 4.4.2 算法设计
• 4.5 算法分析与实验
• 4.5.1 在相关性排序中的应用
• 4.5.2 在联合搜索引擎中的应用
• 4.6 本章小结
• 第5章 结论和延展性工作
• 5.1 工作总结
• 5.2 其他相关工作
• 作者简历
• 学位论文数据集