基于回归支持向量机的信息检索

韩 咏, 齐浩亮, 杨沐昀, 李 生

(1.黑龙江工程学院计算机科学与技术系 黑龙江哈尔滨150050; 2.哈尔滨工业大学计算机科学与技术学院 黑龙江哈尔滨150001)

基于回归支持向量机的信息检索

韩 咏1, 齐浩亮1, 杨沐昀2, 李 生2

(1.黑龙江工程学院计算机科学与技术系 黑龙江哈尔滨150050; 2.哈尔滨工业大学计算机科学与技术学院 黑龙江哈尔滨150001)

使用回归分析策略以文档满足用户的信息需求程度作为回归分析的目标值,利用回归支持向量机构建了信息检索模型.新模型不仅提供了融合不同来源特征的灵活框架,而且由于使用回归支持向量机寻找具有ε不敏感损失的回归函数,因此具有良好的泛化性能.实验表明,新模型性能优于目前主流的基于语言模型的信息检索方法.

信息检索;回归分析;支持向量机;再采样

0 引言

随着信息时代的到来,各种信息资源越来越丰富,信息检索(info rmation retrieval,IR)系统成为人们获取信息必不可少的工具.信息检索的任务是在待检索文档集中依据用户信息需求,按相关程度对文档进行排序,作为对检索用户所提出查询的回应.影响信息检索系统性能的因素有很多,其中最为关键的是信息检索建模.近年来在许多领域获得成功的判别学习模型也被引入到信息检索中,成为当前研究的主流方法.在信息检索中应用的判别学习方法一般采用分类方法和排序方法两种策略.Nallapati将信息检索视为分类问题[1],使用了支持向量机(support vector machine,SVM)和最大熵(maximum entropy)两种算法,结果并不理想,性能明显低于语言模型[2];Cooper的分段逻辑回归算法(staged logistic regression)[3]性能也不佳.将信息检索视为分类问题存在2个问题:1)分类与检索的任务(按文档的相关度排序)并不直接相关,仅是弱相关;2)信息检索中训练样本太少,且面临严重的数据不平衡(unbalance data).将信息检索视为对文档的排序,在排序框架下解决检索问题是最近几年的新进展.这方面的工作包括:采用基于感知器算法的排序算法[4],改进Ranking SVM算法[5],微软公司为信息检索提出了RankNet算法并进行了应用[6-7].文献[8]使用表排序策略而不是上述这些工作的基于文档序对数的排序,取得了更好的效果.在排序算法框架下解决检索与以往的模型相比,提高了与信息检索任务的相关度,但与信息检索的任务还不直接相关,影响了检索性能的进一步提升.

本文将信息检索视为回归分析问题,尝试回归分析的框架下引入回归支持向量机这一典型判别学习方法[9]解决检索问题.

1 基于回归支持向量机的信息检索

1.1 特征集

本文使用的特征包括一元文法特征、二元文法特征和语言学特征.文中的特征集包含n个特征fi(q,c, d),i=1,2,…,n,其中的c为概念,例如组块是一种概念,二元文法中相邻词也构成概念,q为用户查询,d为待检索的文档.特征fi(q,c,d)是一个映射,该映射将(q,c,d)映射到一个实数,即fi(q,c,d)∈R.使用向量表示方法,有f(q,c,d)∈RN,即f(q,c,d)={f1(q,c,d),f2(q,c,d),…,fN(q,c,d)}.这些特征包括:

f1(·)是一元文法特征,是一元文法概率的对数值,也就是

f2(·)是二元文法特征,是二元文法概率的对数值,也就是

f3(·)是文档模型特征,是文档模型的概率的对数值,也就是为相关的概念模型的中心词(head wo rd);

fi(·)是n-3个概念特征,其中i=4,…,n.它们的值可以是相关概念模型(例如名词短语、动词短语、形容词短语)的概率的对数值,也可以根据启发式规则分配(如factoid).

1.2 基于回归支持向量机的学习

支持向量机作为一种新兴的分类算法广泛应用于模式识别的各个分支,已经发展成为机器学习中一个独立的子领域.支持向量机将向量映射到一个更高维的空间里,在这个空间里建立一个最大间隔超平面.在分开数据的超平面的两边建立两个互相平行的超平面,建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化.

支持向量机算法也被扩展到解决回归问题,被称为回归支持向量机.回归支持向量机与传统的回归分析相比,引入了ε不敏感损失函数,它可以忽略真值某个上下范围内的误差,具有优化的泛化界[10].该模型解决了回归问题和时间序列预测问题,在很多领域获得了成功应用.

给定包含L个样本(xi,yi)的训练集,其中xi为n维空间中的向量,yi为实数.设待估计线性回归函数为f(x)=w·x+b,其中,b∈R,x为特征向量,w为权重向量.回归支持向量机中ε的不敏感损失函数等价于支持向量机中的松弛变量,最小化的目标函数为其中,L(y-f(x))为每一个样本上损失.C为边界和训练错误的折衷,也就是模型的复杂性(结构风险)和经验损失的折衷,模型的复杂性决定了模型的泛化能力.

在回归支持向量机中,如果预测值与观测值之间的偏差小于ε,则认为损失等于零,这样的损失函数描述了ε不敏感模型,定义为

考虑3种典型的损失函数:线性ε不敏感损失函数、平方ε不敏感损失函数和Huber损失函数.如果噪声密度是一个对称光滑函数,那么线性损失函数最好[11].因此,本文采用线性损失函数,并假设信息检索中的噪声密度是一个对称光滑函数,线性(一次)ε不敏感损失函数定义为

由于信息检索中存在大量难以线性拟合的数据,为了进一步增强回归支持向量机的性能,可以在训练时删除不一致的训练样本,再重新训练,进一步提升系统的性能.

1.3 再采样

将回归支持向量机引入信息检索中,目的是根据回归函数对待检索文档进行排序.但由于在信息检索中,训练样本是二值的,被分成相关和不相关.对于信息检索而言,存在着严重的数据不平衡(unbalance data),即两类样本(正例和反例)比例严重不平衡,一类训练样本占多数,另一类训练样本占少数.在信息检索中,相关文档的数量要远低于不相关文档,直接应用回归支持向量机并不合适,需要处理数据不平衡问题.

处理数据不平衡的方法有3大类:过多采样(oversamp ling)、欠采样(undersamp ling)及调整不同类样本的损失权重.过多采样是重复比例小的一类样本提高小比例样本数量,再采样是对大比例的一类样本进行再采样降低大比例一类样本数量.在使用回归支持向量机的情况下,由于决定回归函数的是支持向量,所以过多采样并不适用,调整样本的权重也无法直接应用到回归支持向量机.本文采用再采样技术解决样本不平衡问题.采用再采样技术不仅可以提高检索的效果,还可以加速训练过程,并降低存储开销.在多种再采样技术中,随机采样技术性能优异,它取得了比其他采样技术更好或者是一样好的结果,我们采用了随机采样技术.

2 实验及结果分析

2.1 实验环境

实验是在TREC测试集上进行的.表1是测试集的一些信息,使用的主题(topic)从201～250,该部分主题只有描述部分(descrip tion field)使用了自然语言组成了查询语句,每个查询语句包含10～15个词.

表1 实验中使用的TREC语料Tab.1 TREC corpus in the experiment

实验中,为了获取所需要的每一个句子的概念序列,我们采用基于隐马尔科夫模型的组块分析器对文本进行了分析.

实验比较了回归支持向量机算法和目前主流的语言模型(一元文法模型)方法.两个模型的参数都是通过交叉检验(two-fold cross validation)获得.一元文法模型的自由参数为平滑参数(插值参数),回归支持向量机的参数为C,参数C(模型的复杂性和经验损失的折衷)是一个变化范围很大的值.为了确定最优的C,设定C的候选集为{2m,2m-1,…,2n},m、n为整数,m

2.2 实验结果及分析

在实验中将回归支持向量机模型和主流的语言模型(一元文法模型)进行了比较,表2是实验的主要结果.

一元文法模型(UGM)是典型的语言模型,查询的生成概率用进行估计,平滑算法采用Jelinek-M ercer算法.

在训练中,相关文档的回归值设为2,不相关文档的回归值设为1.使用SVMlight(http://svm light. joachim s.o rg)对回归支持向量机进行了多组实验,分别是:

实验1:再采样,删除不一致的样本,训练C,设ε=0.2;

实验2:再采样,删除不一致的样本,训练C,设ε=0;

实验3:再采样,保留不一致的样本,训练C,设ε=0.2;

实验4:不再采样,删除不一致的样本,使用同实验1相同的C,ε=0.2;

实验5:再采样,删除不一致的样本,设C=0,ε=0.2.

观察表2的实验结果,可以看出,再采样、删除不一致的样本并重新训练时回归支持向量机的性能最优,高于语言模型方法.对比实验可以看出,合理的设置ε有助于检索性能的提升;删除不一致的训练样本对检索系统的性能有微弱的正面影响;再采样对检索技术是至关重要的;C值的大小决定了模型的复杂性和经验损失的比例.在两种极端情况下,C=0时忽略经验损失,C=∞时忽略模型的复杂性,即显示了模型的泛化能力.

表2 回归支持向量机在信息检索上的性能Tab.2 The perfo rmance of SVM regression on IR%

观察实验结果,我们注意到在两组测试集上的提升幅度显著不同.其原因可能在于测试集和训练集的划分不均衡.实验中使用了交叉检验方法,即按查询将语料两等分(查询201～225为一组,查询226～250为一组),但由于某些查询在相应的文档集上没有相关文档或相关文档很少,造成了训练集和测试集不平衡,最终影响了检索性能.另外,从信息检索的任务(待检索文档集中依据用户信息需求,按相关程度对文档进行排序)出发,只要将用户最关心的文档排在最前面就可以高效地满足用户需求,因此,对回归分析后的值进行调整,与查询相关文档的排序向前移,与查询无关文档的排序向后移,再重新训练回归分析器,反复多次,直至收敛或达到指定次数,这种处理方式预期可以进一步提升信息检索系统的性能,也是我们未来工作的重点.

在对比研究中,将检索视为分类,在相同的特征集、相同的训练集和测试集下,应用支持向量机模型,其性能不佳,远不如语言模型和回归支持向量机模型.这个工作同Nallapati的工作[1]一样都使用了支持向量机,不同的是使用的特征集不一样,但结果类似,都不理想.从理论分析和这些实验结果可以看出,导致支持向量在信息检索应用不成功的原因不在于特征集,而是模型本身不适合于信息检索.

从实验结果可以看出,用回归支持向量机模型在信息检索中取得了很好的结果,回归支持向量机是典型的判别学习模型,本文的方法也具有判别学习的优势.

[1] Nallapati R.Discriminativemodels for information retrieval[C]//Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Sheffield,2004:67-71.

[2] Ponte J,Croft W B.A languagemodeling app roach to info rmation retrieval[C]//Proceedingsof the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Melbourne,1998:275-281.

[3] Cooper W S,Gey F C,Dabney D P.Probabilistic retrieval based on staged logistic regression[C]//Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Info rmation Retrieval.Copenhagen, 1992:198-210.

[4] Gao J,Qi H,Xia X,et al.Linear discriminantmodel for information retrieval[C]//Proceedingsof the 28th Annual International ACM SIGIR Conference on Research and Development in Info rmation Retrieval.Salvado r,2005:290-297.

[5] Cao Y,Xu J,Liu T.Adapting ranking SVM to document retrieval[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Info rmation Retrieval.Washington,2006:186-193.

[6] Burges C J C,Shaked T,Renshaw E,et al.Learning to rank using gradient descent[C]//Proceedingsof the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Salvador,2005:89-96. [7] Richardson M,Prakash A,Brill E.Beyond pagerank:machine learning for static ranking[C]//Proceedingsof the 15th International Conference on Wo rld Wide Web.Edinburgh,2006:707-715.

[8] Xia F,Liu T,Wang J,et al.Listw ise app roach to learning to rank:theo ry and algo rithm[C]//The 25th International Conference on Machine Learning.Helsinki,2008:1192-1199.

[9] Vapnik V N.Statistical Learning Theory[M].New Yo rk:Wiley,1998.

[10] Shawe T J,Bartlett PL,William son R C,et al.Structural risk minimization over data-dependent hierarchies[J].IEEE Trans Inf Theory,1998,44:1926-1940.

[11] Huber P J.Robust estimation of a location parameter[J].Ann M ath Statist,1964,35:73-101.

Information Retrieval Based on Support Vector Machine Regression

HAN Yong1, Q IHao-liang1, YANGM u-yun2, L ISheng2
(1.Department of Com puter Science&Technology,Heilongjiang Institute of Technology, Harbin 150050,China;2.School of Com puter Science&Technology, Harbin Institute of Technology,Harbin 150001,China)

The regression method is exp lored for IR,and the degree is used as regression target value.Support vector machine regression(SVMR)is adop ted in the framework because it p rovides a flexible framewo rk to inco rpo rate arbitrary features.SVM R is used to find a regression function w ithεinsensitive loss,w hich allow s good generalization.Results show that the new model outperform s the state-of-the-art language modeling app roaches.

information retrieval;regression analysis;SVM;resamp le

TP 391.3

A

1671-6841(2010)02-0018-04

2009-01-04

国家自然科学基金资助项目,编号60873105;国家自然科学基金重点资助项目,编号60736044.

韩咏(1975-),女,讲师,硕士,主要从事信息检索与信息过滤研究,E-mail:hyhyqhl@sina.com.