（计算机软件与理论专业论文）基于神经网络的网页排序学习算法研究.pdf

基于神经网络的网页捧序学习算法研究摘要 论文题目：基于神经网络的网页排序学习算法研究 专业：计算机软件与理论 硕士生：吴桂宾 指导教师：汤庸教授、舒忠梅讲师 摘要 随着互联网的发展，搜索弓l 擎的重要性与日俱增。如何有效的查找需要的信 息是非常关键的，一个好的搜索引擎可以极大的节省用户查找信息的时间。搜索 引擎包含多个组成部分，其中网页排序是搜索引擎设计的核心问题，排序结果的 准确率直接决定了搜索引擎的性能和用户体验。信息检索领域中有许多的网页排 序算法，其中以样本对级别方法的模型应用比较广泛。在样本对级别方法的模型 中，有一类是基于神经网络结构的，其中以r a n k n e t 算法比较具有代表性。 r a n k n e t 算法虽然简单易用，却也存在着样本对级别方法本身固有的不足：查询 之间不具备平等性；每一个文档序对是平等的，各文档序对之间没有优先关系。 这是与网页评价标准的原则相违背的。 本文提出了对基于样本对级别方法的神经网络排序算法的改进思路。文章以 r a n k n e t 算法为例，对其进行了改进。一是构造了新的误差函数，对误差函数加 一入查询的平等性信息，并结合神经网络的特点，分析了不对其加入文档位置权重 信息的原因；二是对神经网络的训练过程也进行了改进，通过扩充训练样本集， 使其加入查询的平等性信息和文档位置权重信息，使模型的学习过程更符合网页 评价标准的原则，以达到提高排序精度的目的。 本文在l e t o r ( t r e c 2 0 0 3 ，t r e c 2 0 0 4 ，o h s u m e d ) 数据集上进行了实验，分 别利用2 层神经网络模型和3 层神经网络模型来进行学习。并且通过交叉校验的 方法来避免过拟合。实验采取了多个评估指标进行衡量。实验结果表明改进算法 比起原有的r a n k n e t 算法能够有效的提高网页排序的精度。 关键词：网页排序、样本对级射、查询平等性、文档位置权重、神经网络 基于神经网络的网页排序学习算法研究 a b 锄a c t t i t l e ：r e s e a r c ho nl e a r n i n gt or a n kf o rw e bs e a r c h b a s e do nn e u r a ln e t w o r k m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：缪台g u i b i n s u p e r v i s o r ：p r o f e s s o rt a n gy o n g ol e c t u r e rs h uz h o n g m e i a b s t r a c t a si n t e m e td e v e l o p sr a p i d l y , s e a r c he n g i n eb e c o m e sm o r ea n dm o r ei m p o r t a n t i t sc r i t i c a lt os e a r c hi n f o r m a t i o ne f f e c t i v e l y , t h e r e f o r eag o o ds e a r c he n g i n ec a ns a v e u s e r s t i m e s e a r c he n g i n ei n c l u d e san u m b e ro fc o m p o n e n t s ，a n dt h ek e yp o i i l ti s p a g e 珊蝇t h e r e s u l to fp a g er a n k i n gd e t e r m i n e st h es e a r c he n g i n e sp e r f o r m a n c e a n du s e l s te x p e r i e n c e t h e r ea l em a n yp a g er a n k i n ga l g o r i t h m si nt h ef i e l do f i n f o r m a t i o nr e t r i e v a l ，w h i l et h em o d e l su s i n gp a i r w i s em e t h o da r em o r ep o p u l a r i n t h e s em o d e l s , s o m ea r eb a s eo nn e u r a ln e t w o r k ，a n dr a n k n c ti so n eo ft h e s em o d e l s r a n k n e ti ss i m p l e ，b u ta l s oh a ss h o r t c o m i n g s ：q u e r i e sa l en o te q u a l ，a n dd o c u m e n t p a i r sa r ee q u a l ，w h i c hi sc o n t r a r yt ot h ep r i n c i p l eo fp a g er a n k i n ge v a l u a t i o nc r i t e r i a t h i sp a p e rp r o p o s e sm e t h o d st oi m p r o v ep a g er a n k i n ga l g o r i t h m sb a s eo n p a l l w i s ea n dn e u r a ln e t w o r k , a n du s e sr a n k n e ta sa ne x a m p l et oi l l u s t r a t e f i r s t l yi t d e s i g n sa n e wl o s sf u n c t i o n 晰t l li n f o r m a t i o na b o u te q u a l i t yo fq u e r i e s ，a n da n a l y z e s w h yn o ti n c l u d i n gi n f o r m a t i o na b o u tw e i g h t so fd o c u m e n t s p o s i t i o n s s e c o n d l yi t i m p r o v e st h et r a i n i n gp r o c e s so fn e u r a ln e t w o r k , b ye x p a n d i n gt h es i z eo ft r a i n i n g s a m p l es e t , m a k i n gt h et r a i n i n gp r o c e s si n c l u d i n gi n f o r m a t i o na b o u te q u a l i t yo f q u e r i e sa n dw e i g h t so fd o c u m e n t s p o s i t i o n st om e e tt h ep r i n c i p l eo fp a g er a n k i n g e v a l u a t i o nc r i t e r i a , i no r d e rt oi m p r o v ea c c u r a c yo f p a g er a n k i n g t h i sp a p e ru s e st h el e t o r ( t r e c 2 0 0 3 ，t r e c 2 0 0 4 ，o h s u m e d ) d a t a s e tt od o t h ee x p e r i m e n li tr e a l i z e st h e2l a y e r sn e u r a ln e t w o r ka n d3l a y e r sn e l l r a ln e t w o r k ， a n dl l t st h em e t h o do fc r o s sv a l i d a t i o nt oa v o i do v e r f i t t i n g i tu s e sas e r i e so f e v a l u a t i n gi n d i c a t o r st oj u d g et h ea c c u r a c y t h ee x p e r i m e n t ss h o w t h a tt h ei m p r o v e d l h 基于神经网络的网页排序学习算法研究 a l g o r i t h mi sm o r ee f f e c t i v et h a nr a n k n e t k e yw o r d s ：p a g er a n k i n g , p a i r w i s e ，q u e r i e s e q u i t y , w e i g h t so fd o c u m e n t s p o s i t i o n s ，n e u r a l i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：撇 日期：z ! 竺? 至乡刀锣 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：罢栏害 日期：l o o7 年嗲月1 上日 聊签名：勺、厂仰 日期：2 口d j 7 r 年岁月】z 日 基于神经网络的网页捧序学习算法研究第l 章引言 第1 章引言 本章首先介绍网页排序的应用背景信息检索，以及在此基础上产生的网 页排序问题，并介绍了搜索引擎的原理，阐述了研究网页排序问题对提高搜索 引擎性能的重要性。接着介绍了在网页排序闯题领域常用的各种评价标准。最 后给出了论文的文章组织结构。 1 1 网页排序简介 当今是一个信息时代，信息的数量呈指数级增长，记载着人们需要的信息 和知识的已经不仅仅是传统的书籍和报刊，个人电脑、数字通信设备、网络都 储存着大量的信息。根据统计，当今世界的信息量保持着每年约3 0 的速度增 长，而其中有9 0 以上的信息数据是存储在诸如硬盘之类的电子存储设备上。 人们缺乏的已经不是信息，而是如何有效的在大量的信息里快速寻找到自己需 要的信息。如果没有有效的检索手段，那大量的信息对人们来说只能是冗余的 文字和符号而已。 信息检索是自然语言处理问题其中的一个子领域。自然语言处理( n l p ： n a t u r a ll a n g u a g ep r o g e s s i n g ) 研究涉及的范围相当广泛，其中包括了语言分析、 机器翻译、信息检索、文本分类等领域。而其中信息检索( i n f o r m a t i o nr e t r i e v a l ) 是一个重要的应用领域。信息检索用于通过特定算法或模型从文档中搜索有价 值的信息，它的一般做法是用户通过输入一个表述需求信息的查询字段，系统 则会以一个包含所需信息的文档列表作为回复，这一类问题可以称为特定信息 的检索问题( a d - h o cr e t r i e v a lp r o b l e m ) t 。 网页排序又是信息检索领域的一个特定的方向。在现今已经有诸如g o o o e 、 百度、雅虎、m i c r o s o f t 等公司提供搜索引擎以方便用户快速有效的进行检索查 询需要的信息。而网页作为互联网上最主要的信息表示方式，各大搜索引擎主 要会根据用户输入的查询条件，返回包含大量的网页的相关列表。对于用户来 说，该相关列表的信息量依然是十分巨大的。因此搜索引擎会对搜索到的网页 进行排序，根据网页与用户查询条件的相关度，相关度越大的网页排在越前边， 相关度越小的网页排在越后边。一个搜索引擎的性能，很大程度上取决于网页 基于神经网络的网页排序学习算法研究 第1 章引言 排序的精度。以g o o s e 公司的搜索引擎为例，该引擎几乎每天都会对其网页 排序的相关算法进行调整，每年调整的次数可以达到4 0 0 次以上。 根据对用户行为的调查，还可以发现用户利用搜索引擎进行检索时，会有 一些特定的行为，对于提高搜索引擎性能和网页排序精度提高帮助。例如：用 户对搜索引擎返回的结果列表的点击，可以反应出搜索引擎的精度。举例来说， 如果绝大多数用户往往先点击排在第2 位的网页，那么说明第2 位的网页很有 可能比排在第1 位的网页更符合用户的查询条件。而用户在每个网页页面停留 的时间长短，也可以间接反映该网页是否符合用户的查询条件。 1 2 搜索引擎原理 当用户向搜索引擎提交了关键字后，搜索引擎在极短的时间内( 毫秒级) 返 回大量的相关网页列表。但搜索引擎并非实时的根据关键字去搜索网页，而是 在后台进行了大量的离线( o f f - l i n e ) 的预处理工作，然后才是实时的( o n - l i n e ) 的处 理用户的具体查询。其工作原理图如下： * 曩 蠊 天擘 图1 - 1 搜索引擎原理 搜索引擎具体工作过程可以分为几个步骤： 1 网页收集阶段搜索引擎首先会派出网络爬虫( 又叫网络蜘蛛) 1 2 通过一 定的策略去获得大量的网页。所谓网络爬虫，实质是一个自动提取网页的程序， 2 基于神经网络的网页捧序学习算法研究第1 章弓i 言 它利用网页之间的超链接关系，通过一定的策略，获取到大量的网页，并交给 搜索引擎进行存储，为下一步应用准备信息。网络爬虫一般需要尽可能的覆盖 多的网页链接，以尽可能获取更多的网页信息。除了通用的网络爬虫外，也有 专门针对某一些主题的聚焦爬虫，它并不追求更大的覆盖面，而是根据某个主 题去获取相应的网页。但不管是哪种爬虫，都是从一个或者若干个初始的u r l 开始，通过网页问的超链接，获得更多的u r l ，并将其放进一个等待队列，按 一定的次序和策略对队列的u r l 进行遍历。在遍历过程中，需要考虑到去掉 重复遍历的u r l ，以免照成死循环。当今的网络爬虫多种多样，很多的搜索公 司都有自己的网络爬虫，例如g o o g l ec r a w l e r 【3 1 ，f a s tc r a w l e r 4 j ，p o l y b o t i s ， r b s e l 6 1 ，w e b c r a w l e r l 7 1 ，w o r l dw i d ew e bw o r m i s ，w e b r a c e i g l 等等。 2 索引建立阶段对于网页爬虫获得的网页数据，会存储到数据库。而网 页的数量是非常庞大的。搜索弓 擎会对其建立索引。在信息检索领域，一般是 对网页建立倒排索i j l ( i n v e r t e di n d e x ) 1 0 1 。倒排索引利用关键字的值来查找相应 的记录( 网页) ，它具有高速的效率，是目前搜索引擎公司最常用的信息存储方 式。倒排索引的建立，需要几个步骤：首先，建立倒排表，通过遍历数据文档 ( 爬虫获得的网页) ，并利用一定的分词技术，对每个关键字的出现频率和位置 信息进行记录。这样可以构建起一张记录每个关键字信息的表格，叫倒排表。 它相当于整个数据文档的“目录表 。其次，当爬虫获得了更多的网页信息后， 倒排索弓 可以重新建立或者增量更新。增量更新可以大大节省索引的建立时 间，提高索弓f 建立的效率。利用倒排索引，可以把对记录的查询转换为地址的 运算，使得查找速度有了极大的提高。 3 网页排序阶段通过倒排索引找到的包含用户关键字的文档数量是非常 多的，对于一个常用的关键字，包含该关键字的文档可能有成千上万，而用户 不可能对每个文档进行查询。所以搜索引擎需要对这些文档也就是网页，根据 它们和关键字的相关度进行排序。这个步骤叫做网页排序，它是搜索引擎的核 心，也是难度最高的一个部分。对于爬虫或者倒排索引技术，发展已经相对成 熟，各个搜索引擎在其做法上不会有太大的差别。而对于网页排序，则有相当 多的方法来处理。网页排序是评价一个搜索引擎精度最主要的指标。比如对于 g o o f l e 的搜索引擎，在网页排序上它的更新速度相当频繁，以确保其在网页排 基于神经网络的网页排序学习算法研究第1 章引言 序的精度上的领先性。对于网页排序，有各种不同策略和算法，将在后文详细 介绍。 4 实时更新阶段之前三个步骤已经建立起搜索引擎，并且可以投入使用 中。这三个步骤进行的是离线的处理，耗时也是比较多的。当投入使用后，用 户可以进行查询。而在同时，搜索引擎也可以获得更多的信息，比如通过判断 用户的使用习惯和查询日志可以实时调整搜索引擎模型的一些参数。这个过程 的调整是在线的，其时间要比离线部分的处理少得多。这样也才能保证搜索引 擎的效率。 1 3 网页排序评价标准 不同的网页排序模型的比较，需要有统一的标准进行评价，才能比较出各 个模型的好坏。在网页排序这一领域存在着多种不同的评价标准，方便根据不 同的应用需求来对排序模型的好坏进行评价。要对一个模型进行评价，首先需 要有一个测试集，测试集里包含多个查询( q u e r y ) ，每个查询与多个文档相关联， 并且每个文档有一个标签，标记了这个文档与该查询的相关度。有了以上准备， 就可以利用模型根据每个查询对其相关联的文档进行打分，并利用不同的评价 标准计算出每个查询的准确度，然后对每个查询的准确度进行平均，就可以得 到该模型的准确度。 对于文档的标记( 与查询相关度的标签) ，主要有几种标记方法【】： 二元标签每个文档有一个标签，分别是“相关”( r e l e v a n t ) ，或者“不相关 ( i r r e l e v a n t ) 多元标签每个文档有一个标签，当标签有多种，例如按照相关度，可以分 为“完美”( p e r f e c t ) 、“优秀”( e x c e l l e n t ) 、“好( g o o d ) 、“一般( f a i r ) 、“差 ( b a d ) 等。 文档序对优先关系：这种方法不需要对单独的文档进行标记，而只是对于 由两个文档组成的文档序对，只标记这两个文档中哪一个与查询的相关度更 高。例如，标签 就表示a 比b 与查询有更高的相关度。 现今主要的评价标准主要有以下几种类型【l l 】： 1 m a p ( m e a na v e r a g ep r e c i s i o n ) 1 1 1 】对于m a p 的计算，可以分为以下步 4 基于神经网络的网页捧序学习算法研究第1 章引言 骤： 计算位置n 的精度： p刀：#relevantdocuments i nt o pn r e s u l t s n ( 1 。1 ) 公式计算出在第n 个位置之前相关的文档的个数，然后计算出一个查询的 平均精度： 单个查询的平均精度： ap：=pn*idocuments ni sr e l e v a n t # r e l e v a n td o c u m e n t s ( 1 2 ) 团圆圈囡团圆圈 图2 - 2 捧序实例 以图l - 2 为例，每个方格代表一个文档，y 表示的是和查询相关的文档，n 表示的是不相关的文档，左边的文档表示排在越前面。对于该查询，其a p 的 计算如下： a p ：! ( ! + 三+ 三+ ! ) 0 7 1 4 、1357 7 以上是单独一个查询的平均精度，对于多个查询，计算出在测试集上所有 查询的平均精度，就是m a p ： 多个查询的平均精度： 脚2 吉军肥 ( 1 - 3 ) 刀t，1 2 、 2 n d c g ( n o r m a l i z e dd i s c o u n t e dc u m u l a t i v eg a i n ) 【1 1 ，1 2 】n d c g 的计算公 式为( 对查询9 f ) ： 工 n d c g = m ( 2 r j 一1 ) l o g ( 1 + 力0 - 4 ) = l 其中，( 歹) 是位置为，的文档的相关度分数，归一化因子m 可以使得最佳的 排序的n d c g 为1 。三是标签的维数。以下举例说明如何计算单个查询的n d c g 值。多个查询的最终n d c g 值只要平均计算即可获得。 s 基于神经网络的网页排序学习算法研究第1 章引言 单个查询n d c g 的计算例子，可以分为以下步骤。 计算g ( g a i n ) ：以5 元标签为例，一共有5 个不同等级的标签，则每个等级 的得分计算如下： 表1 - 1 相关度得分 相关度( r e l e v a n c er a t i n g )得分( g a i n ) p e r f e c t 2 5 1 = 3 1 e x c e l l e n t2 4 1 = 1 5 g o o d 2 3 1 = 7 f a i r 2 2 1 = 3 b a d2 - 1 = 0 计算d c g ( d i s c o u n t e dc u m u l a t i v eg a i n ) ：首先说明c g ( c u m u l a t i v ec a i n ) 的计算方法。c g 是不考虑位置权重的算法，它对每个位置的文档得分按照相 同的权重相加，得到一个总分。以查询g = 1 6 3 为例，用户输入1 6 3 ，搜索引 擎返回大量的网页列表。其中一部分结果如表格中的u r l 一栏所示。而根据 网页和关键词 1 6 3 ) 的相关度( 比如用户很可能是想查询网易公司的相关信息) ， 可以给每个网页给定不同得分，再计算c g 。 表1 - 2 计算c g p o s i f i o nu r lg a i nc g 1 h t t p ：w w w 16 3 c o m 3 13 1 2 h t t p ：w w w 16 3 c l u b o r g 1 53 1 + 1 5 = 4 6 3 h t t p ：m a i l 16 3 c o m 3 14 6 + 3 1 = 7 7 4 h t t p ：d 1 p c o n l i n e c o m c n t a g s 16 3 37 7 + 3 = 8 0 5 h t t p ：b o o k s g o o g l e c n b o o k s ? i d = 16 3 9 o8 0 + 0 = 8 0 6 而对于d c g ，计算方法类似，只是对不同位置的文档( 网页) 赋予不同的权 重。位置靠前的文档权重大，位置靠后的文档权重小，每个位置的文档需要乘 以一个折扣因子( d i s c o u n t i n gf a c t o r ：) ：l o g ( 2 ) ( 1 0 甙l + r a n k ) ) 。 6 基于神经网络的网页排序学习算法研究第1 章引言 表1 - 3 计算d c g p o s i t i o i lu r l g a i nd c g l h t t p ：w w w 16 3 c o m 3 13 l 1 = 3 1 2 h t t p ：w w w 16 3 c l u b o r g 1 53l + 15 o 6 3 = 4 0 4 5 3 h t t p ：m a i l 16 3 c o m 3 14 0 4 5 + 31 + 0 5 = 5 5 9 5 4 h t t p ：d 1 p c o n l i n e c o m c n t a g s 16 3 35 5 9 5 + 3 宰o 4 3 = 5 7 2 4 5 h t t p ：b o o k s g o o g l e c n b o o k s ? i d = 16 3 9 o 5 7 2 4 + 0 * 0 3 9 = - 5 7 2 4 6 计算m a xd c g ( m a xd i s c o u n t e dc u m u l a t i v eg a i n ) ：将网页列表中的文档 按照相关度从高到底排序，然后计算其d c g ，就可以获得最大d c g ，为下一 个计算步骤最准备。依然以上述查询为例，其计算表格为： 表1 - 4 计算m a xd c g p o s i t i o nu r l g a i nm a x d c g 1 h t t p ：w w w 16 3 c o m 3 13 1 幸1 = 3 l 2 h t t p ：m a i l 16 3 c o m 3 13 1 + 3 l 毒0 6 3 = 5 0 5 3 3 h t t p ：w w w 16 3 c l u b o r g 1 55 0 5 3 + 15 * 0 5 = 5 8 0 3 4 h t t p ：d 1 p c o n l i n e c o m c n t a g s 1 6 3 1 35 8 0 3 + 3 木o 4 3 = 5 9 3 2 5 h t t p ：b o o k s g o o g l e c n b o o k s ? i d = 16 3 9 o5 7 2 4 十0 0 3 9 = - 5 9 3 2 6 计算n d c g ( n o r m a l i z e dd i s c o u n t e dc u m u l a t i v eg a i n ) ：将d c g 规范化到 0 和l 之间的范围，用来表示查询的精度，每个位置的n d c g 值是通过该位置 的d c g 值除以该位置的m a xd c g 值得到的。 7 基于神经网络的网页排序学习算法研究第1 章引言 表l _ 4 计算n d c g p o s i t i o nu r lg a i nd c gm a xn d c g d c g l h t t p ：w w w 16 3 c o r n 3 13 13 11 2 h t t p ：w w w 16 3 c l u b o r g 1 54 0 4 5 5 0 5 3 o 8 3 h t t p ：m a i l 16 3 c o m 3 15 5 9 55 8 0 30 9 6 4 h t t p ：d 1 p e o n l i n e c o r n c n t a g s 16 3 35 7 2 45 9 3 20 9 6 5 h t t p ：b o o k s g o o g l e e n b o o k s ? i d = 1 6 3 9 0 5 7 2 4 5 9 3 2 o 9 6 6 3 m r r ( m e a nr e c i p r o c a lr a n k ) t 1 1 ，1 3 1 比起以上两种评价标准，m r r 的计 算方法是比较简单的。对于一个查询，找出排在最前的一个相关的文档，假设 它排在列表的第r 位，则该查询的精度就为1 r ，然后再对多个查询的精度进行 平均，就可以得到m r r 。 4 帐( w i n n e r st a k ea 1 1 ) 【l l 】这是最简单的一种评价标准。如果对于一个 查询，排在最前边的文档是和查询相关的，则该查询的精度为1 。如果排在最 前边的文档是和查询不相关的，则该查询的精度为o 。然后对多个查询- 的精度 进行平均，就可以得到w t a 。 除了上述介绍的几种网页排序评价标准外，还存在着其它些标准。在网 页排序领域，用得相对较多，而且也比较科学的评价标准主要有m a p ，n d c g 。 其中又以n d c g 的应用更加广泛。对于上述多个评价标准，具有一些共同的特 占 t q ， 1 查询的平等性对于评价网页排序模型的精度，都是在测试集的每个查询 上按照评价标准进行计算，然后同等对待每个查询，进行平均计算。这样可以 避免由于过拟合造成的评价不稳定性。 2 位置权重的考虑对于网页排序，不同位置的文档的重要性是不同的，所 以在评价标准中也都体现了不同位置权重的考虑。一般都是排在越前的文档权 重越高，越后的文档权重越低。 3 不光滑性每一个评价标准都是基于文档的位置来计算精度的，这样就造 成了评价标准的计算公式都是不可导和不可微的。也就是其函数曲线是不光滑 8 基于神经网络的网页排序学习算法研究第l 章引言 的。当排序模型对文档打分出现了微小的变化时，只要文档之间的位置关系没 有发生变化，则评价出来的精度也没有变化。而如果某些文档位置关系发生了 变化，则会造成评价精度变化比较大。这对于排序模型的训练来说是一个要克 服的问题。特别是对于神经网络这种基于梯度下降的训练方法，要求其误差函 数是可导可微的。所以在利用神经网络进行网页排序模型的训练时，需要将评 价标准转化或模拟为可导可微的函数。但也有算法【1 4 】提出了不必利用可导可微 函数作为误差函数的方法，将在后文中进行描述。 1 4 研究的内容和方法 本文的研究的问题是针对样本对级别方法下的神经网络排序算法本身存在 的不足来进行改进。r a n k n e t 算法是一种比较典型的样本对级别方法下的神经 网络排序算法，其准确度和运行效率在众多网页排序算法中是比较好的，但由 于样本对级别方法本身会造成不同查询不平等，违背了网页评价标准的原则， 使得r a n k n e t 算法在排序精度方面受到了影响。除此之外，r a n k n e t 算法的训 练过程是同等对待每个文档序对的，这样体现不出不同位置的文档的重要度不 同。 本文对r a n k n e t 算法的改进，主要针对以上两个不足来进行。利用重新设 计的误差函数和在训练时候扩大样本集，让不同查询的平等性得到体现，也在 训练过程中对位置靠前的文档进行进一步优化。并分析了误差函数的特点，对 其进行改进，使其更符合神经网络的训练过程。 理论上的改进，需要通过实践的检验。在进行算法改进设计之后，在不同 的数据集上采用不同结构的神经网络模型进行训练，对比r a n k n e t 算法和改进 算法的排序精度，通过实验来证明理论设计的可行性。 1 5 本论文的组织 正文共分为5 章。 第l 章对研究网页排序问题的意义进行了阐述，介绍了研究网页排序算法 对于提高搜索引擎性能的重要性，介绍了些比较常见的网页排序评价标准， 9 基于神经网络的网页排序学习算法研究第1 章引言 并指出了本文研究的出发点。 第2 章首先介绍了对网页排序问题国内外的研究现状，分别介绍了传统的 模型以及机器学习方法。并结合本文的研究方向，主要介绍了基于神经网络的 网页排序算法。 第3 章首先简要介绍了砒l n l 斟e t 算法，并分析了该算法的不足。针对其缺 点，阐述了本文中主要工作的理论部分：通过查询的平等性、文档位置的权重 信息来改进误差函数和训练过程，并分析了误差函数的变化特点，使其设计更 符合神经网络的训练过程。 第4 章详细介绍了本文的实验部分：介绍了实验的实现步骤，利用交叉校 验，分别通过2 层的神经网络和3 层的神经网络，在3 个不同的数据集上，从 多个指标比较了l i l l n e t 算法和改进算法的网页排序精度，以及给出运行效率 的对比。然后分析了实验的结果和给出实验结论。 第5 章总结了全文的研究结论和成果，分析了算法的不足，并对下一步的 研究工作做出展望。 1 0 基于神经网络的网页捧序学习算法研究第2 章基于神经网络的网页捧序算法 第2 章基于神经网络的网页排序算法 本章首先介绍了网页排序问题国内外的研究现状，分别介绍了传统的模型 以及机器学习方法。并结合本文的研究方向，主要介绍了基于神经网络的网页 排序算法，其中包括了基于样本对级别和列表级别的方法，以及直接优化网页 评价标准的方法。 2 1 国内外研究现状 处理网页排序问题主要有传统的模型以及机器学习方法。传统的模型相对 比较成熟，方法也比较简单。而机器学习方法则有更好的性能。 传统的模型有上百种，其中有代表性的有b m 2 5 1 5 ，1 6 ，1 7 1 ，p a g e r a n k i s , 1 9 ， h i t s 瑚, 2 q 等等。传统的模型往往利用词频圈、逆向文档频率( i d d 圈，文档 长度( d l ，超链接关系等来进行建模。以b m 2 5 为例，其计算公式为【1 5 】： 删n 9 2 喜删。石f ( q 等k i 施bb - - - - - 5 7 , _ 扭1 j ，功+ ( 1 一+ 。、 a v g a t ( 2 1 ) 其中，( 吼，功是仍在文档d 中的词频，该项越大则表明仍与文档d 关联 的可能性越大。i d i 是文档长度( 文档包含的单词数) ，叫鲫是平均文档长度， 指的是支本集中各个文档的平均长度( 文档包含的单词数) 。i d f ( q ，) 是吼的逆向 文档频率，它表示的是文本集的文档总数除以包含q i 的文档总数，再取对数得 到。在一些应用中，也会对其公式进行变形，增加一些常数项。它衡量的是某 个词语在文档集合中的某个文档中的重要性。而毛，b 两个是自由调节的参数， 往往选择局_ 2 0 ，6 = o 7 5 进行计算。以b m 2 5 为代表的一类模型，都是利用了 词频，逆向文件频率和文档长度的各种组合来进行网页排序的，它们可以称之 为传统模型中的概率模型( p r o b a b i l i s t i em o d e l s ) h i 。 另一类传统模型以p a g e r a n k ，h i t s ( h y p e r l i n k - - i n d u c e dt o p i cs e a r c h ) 为代 表。它们都是基于超链接的，所以可以说属于传统模型里的基于超链接模型 基于神经网络的网页排序学习算法研究第2 章基于神经网络的网页排序算法 ( h y p e r l i n k b a s e dm o d e l s ) 1 1 】。p a g e r a n k 基于这样一种思想：如果一个网页被其 它很多网页引用( 重要的网页进行引用有更大的权重) ，那么该网页的重要性会 比较高，而如果一个网页被引用次数少，则其重要性也就相对比较小。h i t s 算法的思想与p a g e r a n k 类似，但其考虑的全面性更高：如果一个网页就算不 被很多网页引用，但其被很重要的网页引用，则该网页也重要。所以对于网页 来说，增加了一个叫做权威值( a u t h o r i t y ) 的属性。h i t s 另一个思想是：一个网 页就算不被很多网页引用，但其本身集合了大量指向其它重要网页，则这个网 页可能是某个主题的站点链接集合，所以其重要性也高。所以网页又多了一个 属性，叫做中心值( h u b ) 。p a g e r a n k ，h i t s 各有特点，其应用范围也很广泛。 以上是一些比较传统的处理网页排序问题的模型，虽然具有简单方便的优 点，但也有其不足之处1 1 l 】： 1 对于一个特定的模型，其参数的调节比较困难，特别是模型包含了多个 参数的时候。 2 对于一个特定的测试集，对于不同模型的比较比较困难，因为有的模型 可能有过拟合现象，而有的模型没有。 3 传统的模型有很多，想要组合它们非常困难，并没有很好的方法来有效 的把它们组合起来。 对于上述不足，解决其困难的方法可以利用机器学习来解决，机器学习具 有传统模型没有的优点【1 1 】：可以避免过拟合问题，能够联合多种特征来组合不 同模型的优点( 例如在l e t o r 数据集里，就把b m 2 5 的值作为文档向量的一个 特征) 。另外对于参数的调节也可以自动调整，避免了多个参数选择的困难。 机器学习的方法，按照误差函数的设计，可以分为样本点级另l j ( p o i n t w i s e ) ， 样本对级别( p a i r w i s e ) ，列表级另l j ( 1 i s t w i s e ) 三种方法。而如果按照学习模型来分 类，也有支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) ，b o o s t ，神经网络( n e u r a l n e t w o r k ，n n ) 三种主要的方法。 样本点级别方法的思想是，对于训练样本，标记其标签，而排序模型对文 档进行打分，使得分数和其标签代表的数值接近，并利用其差距作为误差评判 标准。在训练过程中，也是以每个文档作为原子单位进行训练的。该方法的优 点是简单直接，但其不足之处也很明显：网页的排序只需要根据文档分数从高 1 2 基于神经网络的网页捧序学习算法研究第2 章基于神经网络的阿页排序算法 到低排即可，而没有要求每个文档的分数需要打多少分。也就是说，并不需要 知道文档具体该打多少分，而只需要知道文档之间的位置关系即可。在此思想 上，产生了样本对级别方法。 样本对级别方法的思想是：只需要知道两个文档的位置关系，看哪个排在 前哪个排在后，当任意两个文档之间的位置关系都知道的时候，网页排序的结 果也就已经出来。在训练的过程中，是以文档对为原子单位进行训练的。该方 法的优点是减少了对文档分数的具体要求，而只要对文档的打分能体现出优先 关系就可以。目前，应用样本对级别方法的模型是最多的，而且在实际使用中， 样本对级别方法也是应用得比较广泛的。 列表级别方法的思想是：既然网页排序的结果就是一个文档列表，那么把 整个文档列表作为一个整体来训练则是最自然的，也是最能体现结果好坏的。 在训练过程中，是以整个文档排列作为原子单位进行训练的。其优点是训练的 是一个文档排列的整体，和最后呈现的结果一样，往往可以取得较好的结果。 列表级别方法的思想应用于网页排序虽然时间不长，但其思想早在1 9 7 5 年的 文献】中就已经应用于其它领域。当将其引入网页排序之后，也取得了较好的 实验结果。 利用机器学习来进行网页排序最多的三种模型是支持向量机，b o o s t ，神 经网络。对于神经网络，将在后文详细描述，而对于支持向量机，是一种基于 结构风险最小化的方法。其能力要优化一些传统的方法，它是一种有效的小样 本学习算法，但随着样本数量增多，其时间效率则相对比较差。而b o o s t 算法 是一种将多个弱学习算法结合成一个强学习算法的方法。 2 2 经验风险最小化 对于神经网络进行网页排序问题，一般是利用经验风险最小化来处理。首 先利用人工标记好的训练样本，得到排序模型。对于全监督的情况，假设对于 某个排序问题，给出的训练样本如下：瓴，乃) ，w 2 ，y ：) ，亿，y 。) ，其中d 为文档，y 为相关度。而对于排序模型( 排序函数) ，将对每个文档进行打分， 文档排序就根据文档的分数从高到低进行排列。对于误差函数，要求其在训练 1 3 基于神经网络的网页排序学习算法研究第2 章基于神经网络的网页排序算法 过程中，对于训练样本的总误差达到最小值，也即最小化误差函数。计算损失 的期望值也就是风险( r i s k ) 会更符合实际情况，t g r 删( 2 - 2 ) t ：4 ： r ( 叻2j 三( y ，厂( d ，w ) ) d p ( d ，y ) ( 2 其中工表示实际输入和应用输入之间的损失( 误差) ，p ( d ，力为d 与y 的联 合分布。但由于p ( d ，力= p ( y ld ) 尸( 力是未知的，所以实际风险是难以计算的。 所以在实际中，往往利用有限的训练样本，用经验风险来近似代替实际风险值。 而为了保证不会造成过拟合现象，可以利用交叉校验的方法来避免。 对于样本点级别方法，要求最小化公式( 2 3 ) ： 一 足唧( 叻= 三( 儿，f ( d i ，w ) ) 1 ( 2 - 3 ) 其中，w 代表了模型的参数，厂为排序模型( 打分函数) ，三根据不同模型计 算方法不同，是衡量单个文档误差的函数。 对于样本对级别方法，要求最小化公式( 2 4 ) ： 尺唧( 叻= 三( ( 4 ) ，f ( d j ) ，l a b e l ，w ) 1 ( 2 4 ) 其中，w 和厂跟公式( 2 3 ) 里的参数一样，坳p ， 是人工标识好的文 档珥，d ，的优先关系，三根据不同模型计算方法不同，是衡量两个文档组成的 文档对的误差的函数。 对于列表级别方法，要求最小化公式( 2 5 ) ： ( 叻= l ( p e r m u t a t i o n ( d , ，畋，吃) ，w ) ( 2 - 5 ) 其中，w 和跟公式( 2 3 ) 里的参数一样，p e r m u t a t i o n ( d 1 ，畋，以) 是文档 的一个排列，工根据不同模型计算方法不同，是衡量整个文档排列误差的函数。 2 3 神经网络的研究发展 人工神经网络( a n i f i c i a ln e u r a ln e t w o r k s ，简称m 是模仿人类大脑运行机 制设计的一种机器或者软件，它是一种具有大量连接的并行分布式处理器1 2 5 】， 1 4 基于神经网络的网页捧序学习算法研究第2 章基于神经网络的网页捧序算法 其知识是分散在连接的带权重的各条边上的。 神经网络的工作过程分为两个方面，首先是训练期( 也叫做学习期) ，通过 教师信号的指导( 有监督的情况) ，根据训练样本不断调整网络中的边的连接权