一种改进的信息检索排序算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种改进的信息检索排序算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:信息检索的核心问题就是在文档集中为用户检索出最相关的子文档集,并依靠排序算法对检索结果按照相关性进行排序,因此排序算法的优劣直接影响检索的效率.RLR算法改进了正则经验风险模型,大大减少了计算复杂度.通过设定一定范围的允许误差值,采用对称ε-insensitive对数亏损函数作为亏损函数,给出对称ε-insensitive对数亏损函数满足的一些特殊性质,进而改进RLR算法.实验表明新算法对文本排序是有效的.
关键词:信息检索; 排序; 边际; RLR算法
中图分类号:TP393.092
文献标识码:A文章编号:1672-8513(2010)01-0052-04
An Improved Algorithm for Ranking in Information Retrieval
GAO Wei,LIANG Li,XIA Youming
（School of Computer Science and Information Technology, Yunnan Normal University, Kunming 650092, China）
Abstract:
The core function of information retrieval is to find out a subset of the most relevant documents from the files, and to rank the relevance of the results according to the ranking algorithm, so the effectiveness of the ranking algorithm directly affects the efficiency of retrieval. RLR algorithm improves the regularized empirical risk model, and greatly reduces the computational complexity. This has improved the RLR algorithm by allowing certain errors and using the symmetric ε-insensitive logistic loss function, and proved some properties of the symmetric ε-insensitive logistic loss function. Experiments show that the new algorithm is effective for text ranking.
Key words:
information retrieval; ranking; margin; RLR algorithm
信息检索的核心问题就是在文档集中为用户检索出最相关的子文档集,依靠排序算法对检索结果按照相关性进行排序,排序后的结果作为对用户所提出查询的回应.信息检索的性能由诸多因素决定,如查询表达式的质量以及索引、词干提取、无义词的停用、查询扩展等技术的应用等,但根本上它是由排序函数决定的.排序函数以某种准则计算文档表示与用户查询表示的匹配程度,并据此做出文档相对于用户的相关性判断,然后将文档按照相对于用户的相关程度降序排列,返回该有序文档列表作为检索的结果.
经典的网页排序算法是由Page提出的PageRank算法和Kleinberg提出的HITS算法.广义的排序算法不局限于网页的排序,且很多高效的排序算法是通过用已知的训练数据训练得到的,其中著名的算法有RankBoost［1］,Ranking SVMs［2］,RankNet［3］,MFoM［4］.
1 正则经验风险模型及RLR算法分析
1.1 正则经验风险模型
本文中的文件是指检索的基本单位.Q={q1,q2,…,qMQ}是一系列查询的集合,qt由具体应用背景而定,它可以是一组关键词,或详细的文本描述,也可以是图像、声音或视频信息.D={d1,d2,…,dMD}是待查询文件的集合.记D+q与D－q分别表示对查询q相关和不相关的文件集合,D+q=M+D,D－q=M－D.对于查询q和文件d, 可定义相应的排序特征包记为fi(d,q),i=1,2,…,N.其中N为查询q中关键查询元素的基数.许多排序算法来源于如下正则化经验风险模型
这里yj是第j个训练文件dj的二元分类标签, f(dj,qt)代表第j个训练文件dj相对于查询qt的重要程度,yf(d,q)称为边际.L是经验亏损函数,Ω是单调递增正则化函数, v是正则化常数. vΩ(fΗ)是一个罚值项,它是出于如下考虑的：∑MQt=1∑MDj=1L(yjf(dj,qt))部分体现了算法对样本学习的效率,它的值越小越好.但有时会出现过拟合（overfitting）的情况,f的导数的范数很大,上下跳动很快.这使得学习得到的排序函数泛化性很差,影响算法的效率.增加罚值项后,如果出现上述情况, vΩ(fΗ)的值会很大,从而起到了平衡的作用.该模型称为基于边际的风险最小化模型.它的缺点在于：风险最小化即分类误差最小化,但分类和排序没有直接的联系,一个好的分类算法不一定是有效的排序算法.因此文献［6］改进了排序算法好坏的评判标准,引入Kendall系数τ(r1,r2)=1-4QMD(MD－1),其中Q表示在排序函数r1和r2下排序顺序不一致的文件对的数量.要使模型得到的排序函数rf尽可能地逼近目标排序r*,就要减小Q的值,增加τ的值.进而转化为如下基于边际的排序学习模型［6］：
minf=∑qt∈Q∑dj∈D+qt∑dk∈D－qtL(∑ni=1λi［fi(dj,qt)－fi(dk,qt)］)+vΩ(fΗ).(2)
为了方便计算,这里检索函数f(dj,q)为排序特征函数的线性组合,即f(dj,q)=∑ni=1λifi(dj,q),这样可以通过计算每个排序特征函数fi(dj,q)的风险最小估计量λ*i来优化检索函数.通过变换不同的L和Ω可以得到不同的排序学习算法.
1.2 RLR算法
文献［6］提出如下算法：假设亏损函数L是凸函数并满足2 L (x2)≥L(x),在此假设下满足RRprox(f)≥RR′reg(f)≥RRprox(f)－RRprox(－f)2,其中RR′reg(f)是(2)中去掉罚值项部分, RRprox(f)=∑qt∑dj∈D+qtM－DL(fa(dj,qt))+∑dk∈D－qtM+DL(－fa(dk,qt)), fa(dj,q)=∑ni=1λi(fi(dj,q)－α).取亏损函数为对数亏损函数L(x)=log(1+exp(-x)),将最小化RR′reg(f)转换为最小化RRprox(f),运用梯度下降法得到风险最小估计量λ*i,从而得到优化的检索函数.由于该算法使用对数亏损函数（Logistic Loss Function）进行回归,因此称为RLR(Ranking Logistic Regression)算法.
RLR算法有如下优点：①通过变换,大大降低了计算复杂度.在模型(2)中需要对每一对相关和不相关文件进行比较,因此最小化RR′reg(f)的复杂度为O(M+DM－D),但最小化RRprox(f)的复杂度为O(M+D+M－D)；②平衡了数据分布,即平衡正误差和负误差的整体罚值 (在二元分类中,将正类误分为负类称为正误差,反之称为负误差), 因为在RRprox(f)中,根据比例M－DM+D对正误差作出惩罚.
2 RLR算法的改进
在学习过程中,我们总是希望误差很小,甚至为0.但由于存在噪声,在实际中无法得到yi=f(xi)的情况.对此,我们的改进思路是允许学习存在一定程度的误差,设定某个正数ε作为误差的范围,即yi－f(xi)≤ε是允许的.可以通过变换亏损函数在算法上体现上述改进,引入对称ε-insensitive 对数亏损函数［7］:L(x;ε)=log(1+ex-ε)+ log(1+e-x-ε)+2 log(1+e-ε)取代原来的对数亏损函数.
引理1 对某个固定的ε,对称ε-insensitive对数亏损函数是凸函数,且在ε充分小时满足2L(x2)≥L(x).
证明 L′(x)=11+e－x－ε-11+ex－ε,L″(x)=e-x-ε(1+e-x-ε)2+ex－ε(1+ex－ε)2>0.从而L(x)为凸函数.
另一方面,令g(x)= 2L(x2)-L(x)=log(1+ex2－ε)2(1+e－x2－ε)2(1+e－ε)2(1+ex－ε)(1+e－x－ε).再令h(x)=（1+ex2－ε)2(1+e－x2－ε)2(1+e－ε)2-(1+ex－ε)(1+e－x－ε)=2ex2－ε+2e－x2－ε+4e－2ε+4ex2－2ε+4e－x2－4ε+2e－ε+4ex2－ε+8e－3ε+ex－2ε+ex－4ε+e-x－2ε+4ex2－3ε+4ex2－4ε+4e－x2－3ε+5e－4ε+2e－5ε+2ex2－5ε+e-x－4ε+2e－x2－5ε+e－6ε+2ex－3ε+2e－x－3ε-ex－ε-e-x－ε.
注意到2ex－3ε+2e－x－3ε-ex－ε-e-x－ε=(ex－3ε+e－x－3ε)(2-e2ε),从而当ε充分小(可取0≤ε≤12lg 2)时, 2ex－3ε+2e－x－3ε-ex－ε-e-x－ε≥0,从而h(x)>0,即g(x)>0,所以有2L(x2)≥L(x).(实际上,h(x)中正数项很多, ε的值比12lg 2大时也可能使h(x)≥0) (证毕).
由引理1,结合文献［6］附录中定理2的证明可知,在亏损函数取对称 ε-insensitive对数亏损函数下,依然满足RRprox(f)≥RR’reg(f)≥RRprox(f)－RRprox(－f)2.至于参数α选取,我们的策略是减少上式中上界和下界的差值,即取minα=RRprox(f)+RRprox(－f)2.在给出表达式之前,我们需要证明如下结论：
引理2 L(x)+L(-x)≤8log (1+e-ε)+2x
证明 令g(x)= 8log (1+e-ε)+2x-L(x)-L(-x)=2x+4log (1+e-ε)-2 log (1+ex-ε)-2log(1+e-x-ε).注意到函数的对称性,只需要证明G(x)= x+2log (1+e-ε)-log (1+ex-ε)-log (1+e-x-ε)≥0(x≥0).
G′(x)= 1+2e-x-ε+e－2ε1+ex-ε+e－x－ε+e－2ε>0.故G(x)为单调递增函数, G(x)≥G(0)=0.即g(x)≥0. (证毕)
由引理2,我们可以得到
RRprox(f)+RRprox(－f)2=12∑qt{∑dj∈D+qtM－D［L(fa(dj,qt))+L(－fa(dj,qt))］+∑dk∈D－qtM+D［L(－fa(dk,qt))+L(fa(dk,qt))］}≤12∑qt{∑dj∈D+qtM－D(2fa(dj,qt)+8log (1+e-ε))+∑dk∈D－qtM+D(2fa(dk,qt)+8log (1+e-ε))}=12∑qt{∑dj∈D+qt2M－Dfi(dj,qt)－ai+∑dk∈D－qt2M+Dfi(dk,qt)－ai}+4∑qtlog (1+e－ε)M+DM－D=∑qt{∑dj∈D+qtM－Dfi(dj,qt)－ai+∑dk∈D－qtM+Dfi(dk,qt)－ai}+4log (1+e－ε)∑qtM+DM－D.
由于当ε确定时,4log (1+e－ε)∑qtM+DM－D是一个定值,所以问题转化为求
使∑qt∑dj∈D+qtM－Dfi(dj,qt)－ai+∑dk∈D－qtM+Dfi(dk,qt)－ai达到最小的αi的值.
从而优化估计量α*i可以近似地表示成如下求集合平均数的形式：
α*i=average［∪j,t{fi(dj,qt)}M－D∪∪k,t{fi(dk,qt)}M+D］.(3)
这里{x}n表示n个元素的集合,且集合中的每个元素的值均为x.将α*i代入RRprox(f)表达式,并设H为线性函数空间(即f表示为fi的线性组合),Ω(x)=x2.我们得到如下算法计算风险最小估计量λ*i：
minλ∑qt{∑dj∈D+qtM－DL(∑iλif*ijt)+∑dk∈D－qtM+DL(－∑iλif*ikt)}+ v∑iλ2i.(4)
这里f*ijt=fi(dj,qt)-α*i.运用梯度下降法可以得到风险最小估计量λi,从而得到优化的检索函数.
在下面我们将通过实验来说明上述算法对特定的应用领域是有效的.
3 实验分析
本实验实现了一个完整的文本排序过程,包括文本的获取、中文分词、文本特征选择、文本向量表示及其排序.试验采用了Sogou互联网语料库［8］,训练集文档样本数为-1-937-个,测试集文档样本977个.这里,我们将fi(d,q)设置为查询q的第i个关键词在文本d中出现的相对频率,相对频率用TF-IDF公式计算,即：
fi(d,q)=ft(ti,d)×log(N/nt+0.01)∑ti∈d［ft(ti,d)×log(N/nt+0.01)］2 .(5)
其中, fi(d,q)为排序特征函数,理解为查询q的第i个关键词ti在文本d中的权重； ft(ti,d)为词ti在文本d中的词频；N=1-937为训练文本总数；nt为训练文本集中出现t的文本数；分母为归一化因子.
考虑到用户在查看搜索引擎结果时,往往希望在前几个页面（通常为N个结果）就找到自己所需的信息,因此采用P@N［9］准确率对实验结果进行评价,即系统对于某一个查询返回的前N个文档结果的准确率.部分实验结果如下：
4 结语
新算法在理论上不仅保留了原来-RLR-算法的2大优点,并且由于允许了一定程度误差的存在,使新算法有了较强的抗噪能力和更广阔的应用前景.但是由于无法确定正整数ε取何范围时,不等式2ex2－ε+2e－x2－ε+4e－2ε+4ex2－2ε+4e－x2－4ε+ 2e－ε+ 4ex2－ε+ 8e－3ε+ex－2ε+ex－4ε+e-x－2ε +4ex2－3ε+4ex2－4ε+4e－x2－3ε+5e－4ε+ 2e－5ε+2ex2－5ε+ e-x－4ε+2e－x2－5ε+e－6ε+2ex－3ε+2e－x－3ε-ex－ε-e-x－ε≥0在x∈R上恒成立,即ε的值应取多小才能保证2L(x2)≥L(x)成立.因此对于新算法,允许误差的范围还需进一步研究.
参考文献:
［1］CYNTHIA R, ROBERT E, INGRID D. Boosting based on a smooth margin ［C］// In Proceedings of the 16th Annual Conference on Computational Learning Theory. Washington DC, 2004:502-517.
［2］JOACHIMS T. Optimizing search engines using clickthrough data［C］//In Proceedings of the 8th ACM SIGKDD Intl Conference on Knowledge Discovery and Data Mining. New York, 2002:133-142.
［3］BURGES C. Learning to rank using gradient descent［C］//In Proceedings of the 22nd Iintl Conference on Machine Learning.Bonn, 2005：89-96.
［4］CHUA T S, NEO S Y, GOH H K, et al. Trecvid 2005 by nus pris［C］. NIST TRECVID-2005, 2005.
［5］HASTIE T, TIBSHIRANI R, FRIEDMAN J. The elements of statistical learning［M］. Springer Verlag, Basel,2001.
［6］YAN R, HAUPTMANN A G. Efficient margin-based rank learning algorithms for information retrieval［C］//CIVR 2006, Berlin:Springer,2006,4071:113-122.
［7］DEKEL O, SHALEV-SHWARTZ S, SINGER Y. Smooth ε-insensitive regression by loss symmetrization［J］ Machine Learning Research. 2005（6）:711-741.
［8］YIQUN L, YUPENG F, MIN Z, SHAOPING M. Automatic search engine performance evaluation with click-through data analysis［C］// International World Wide Web Conference Proceedings of the 16th international conference on World Wide Web. Banff, Alberta, Canada. 2007:1133-1134.
［9］CRASWELL N, HAWKING D.Overview of the TREC 2003 web track［C］//Text Retrieval Conference (TREC) TREC 2003 proceedings. NIST,2003:1-15.