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

发布时间：2018-06-11 19:09

本文选题：信息检索 + 排序联合问题　；参考：《中国科学:数学》2011年12期

【摘要】：随着互联网规模的日益增长,搜索引擎已经成为互联网上有效的信息获取工具.而在众多搜索引擎的背后,是信息检索技术,也即网页排序算法在起作用.网页排序包括重要性排序和相关性排序.通过我们研究发现,尽管这两类排序所依据的准则不同,但是都可以通过建立适当的随机过程模型来研究.对于网页重要性排序,我们通过分析用户浏览网页的行为建立了Markov骨架过程的框架.基于该框架我们分析了三种不同的随机过程模型对用户行为模拟的合理程度,并设计了名为BrowseRank的一组新算法,该算法可以根据用户上网行为来计算网页的重要性.在网页相关性排序中,我们主要针对排序结果联合问题建立了一个基于Markov链的监督学习框架.通过将传统方法的监督化,使原来难于解决的问题变的易于学习,将原来的NP-难问题转化为一个半正定规划问题,提高了效率.
[Abstract]:With the increasing scale of the Internet, search engine has become an effective information acquisition tool on the Internet. In many search engines, the information retrieval technology, that is, the sorting algorithm of web pages is at work. Page sorting includes importance sort and relevance sort. It is found from our study that although the criteria for these two types of ordering are different, they can be studied by establishing appropriate stochastic process models. For the importance ranking of web pages, we set up the framework of Markov skeleton process by analyzing the behavior of users browsing web pages. Based on this framework, we analyze the rationality of three different stochastic process models for user behavior simulation, and design a new algorithm called BrowseRank, which can calculate the importance of web pages according to users' online behavior. In order to solve the problem of ranking results, we establish a supervised learning framework based on Markov chain. Through the supervision of the traditional method, the problem that is difficult to solve is easy to learn, and the original NP-hard problem is transformed into a semi-positive definite programming problem, and the efficiency is improved.
【作者单位】：北京交通大学理学院数学系;中国科学院数学与系统科学研究院;
【基金】：国家自然科学基金(批准号:11001010)资助项目
【分类号】：O211.6;TP393.092

【共引文献】