基于回歸支持向量機的信息檢索

韓 詠, 齊浩亮, 楊沐昀, 李 生

(1.黑龍江工程學(xué)院計算機科學(xué)與技術(shù)系 黑龍江哈爾濱150050; 2.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 黑龍江哈爾濱150001)

基于回歸支持向量機的信息檢索

韓 詠1, 齊浩亮1, 楊沐昀2, 李 生2

(1.黑龍江工程學(xué)院計算機科學(xué)與技術(shù)系 黑龍江哈爾濱150050; 2.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 黑龍江哈爾濱150001)

使用回歸分析策略以文檔滿足用戶的信息需求程度作為回歸分析的目標(biāo)值,利用回歸支持向量機構(gòu)建了信息檢索模型.新模型不僅提供了融合不同來源特征的靈活框架,而且由于使用回歸支持向量機尋找具有ε不敏感損失的回歸函數(shù),因此具有良好的泛化性能.實驗表明,新模型性能優(yōu)于目前主流的基于語言模型的信息檢索方法.

信息檢索;回歸分析;支持向量機;再采樣

0 引言

隨著信息時代的到來,各種信息資源越來越豐富,信息檢索(info rmation retrieval,IR)系統(tǒng)成為人們獲取信息必不可少的工具.信息檢索的任務(wù)是在待檢索文檔集中依據(jù)用戶信息需求,按相關(guān)程度對文檔進行排序,作為對檢索用戶所提出查詢的回應(yīng).影響信息檢索系統(tǒng)性能的因素有很多,其中最為關(guān)鍵的是信息檢索建模.近年來在許多領(lǐng)域獲得成功的判別學(xué)習(xí)模型也被引入到信息檢索中,成為當(dāng)前研究的主流方法.在信息檢索中應(yīng)用的判別學(xué)習(xí)方法一般采用分類方法和排序方法兩種策略.Nallapati將信息檢索視為分類問題[1],使用了支持向量機(support vector machine,SVM)和最大熵(maximum entropy)兩種算法,結(jié)果并不理想,性能明顯低于語言模型[2];Cooper的分段邏輯回歸算法(staged logistic regression)[3]性能也不佳.將信息檢索視為分類問題存在2個問題:1)分類與檢索的任務(wù)(按文檔的相關(guān)度排序)并不直接相關(guān),僅是弱相關(guān);2)信息檢索中訓(xùn)練樣本太少,且面臨嚴(yán)重的數(shù)據(jù)不平衡(unbalance data).將信息檢索視為對文檔的排序,在排序框架下解決檢索問題是最近幾年的新進展.這方面的工作包括:采用基于感知器算法的排序算法[4],改進Ranking SVM算法[5],微軟公司為信息檢索提出了RankNet算法并進行了應(yīng)用[6-7].文獻[8]使用表排序策略而不是上述這些工作的基于文檔序?qū)?shù)的排序,取得了更好的效果.在排序算法框架下解決檢索與以往的模型相比,提高了與信息檢索任務(wù)的相關(guān)度,但與信息檢索的任務(wù)還不直接相關(guān),影響了檢索性能的進一步提升.

本文將信息檢索視為回歸分析問題,嘗試回歸分析的框架下引入回歸支持向量機這一典型判別學(xué)習(xí)方法[9]解決檢索問題.

1 基于回歸支持向量機的信息檢索

1.1 特征集

本文使用的特征包括一元文法特征、二元文法特征和語言學(xué)特征.文中的特征集包含n個特征fi(q,c, d),i=1,2,…,n,其中的c為概念,例如組塊是一種概念,二元文法中相鄰詞也構(gòu)成概念,q為用戶查詢,d為待檢索的文檔.特征fi(q,c,d)是一個映射,該映射將(q,c,d)映射到一個實數(shù),即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(·)是一元文法特征,是一元文法概率的對數(shù)值,也就是

f2(·)是二元文法特征,是二元文法概率的對數(shù)值,也就是

f3(·)是文檔模型特征,是文檔模型的概率的對數(shù)值,也就是為相關(guān)的概念模型的中心詞(head wo rd);

fi(·)是n-3個概念特征,其中i=4,…,n.它們的值可以是相關(guān)概念模型(例如名詞短語、動詞短語、形容詞短語)的概率的對數(shù)值,也可以根據(jù)啟發(fā)式規(guī)則分配(如factoid).

1.2 基于回歸支持向量機的學(xué)習(xí)

支持向量機作為一種新興的分類算法廣泛應(yīng)用于模式識別的各個分支,已經(jīng)發(fā)展成為機器學(xué)習(xí)中一個獨立的子領(lǐng)域.支持向量機將向量映射到一個更高維的空間里,在這個空間里建立一個最大間隔超平面.在分開數(shù)據(jù)的超平面的兩邊建立兩個互相平行的超平面,建立方向合適的分隔超平面使兩個與之平行的超平面間的距離最大化.

支持向量機算法也被擴展到解決回歸問題,被稱為回歸支持向量機.回歸支持向量機與傳統(tǒng)的回歸分析相比,引入了ε不敏感損失函數(shù),它可以忽略真值某個上下范圍內(nèi)的誤差,具有優(yōu)化的泛化界[10].該模型解決了回歸問題和時間序列預(yù)測問題,在很多領(lǐng)域獲得了成功應(yīng)用.

給定包含L個樣本(xi,yi)的訓(xùn)練集,其中xi為n維空間中的向量,yi為實數(shù).設(shè)待估計線性回歸函數(shù)為f(x)=w·x+b,其中,b∈R,x為特征向量,w為權(quán)重向量.回歸支持向量機中ε的不敏感損失函數(shù)等價于支持向量機中的松弛變量,最小化的目標(biāo)函數(shù)為其中,L(y-f(x))為每一個樣本上損失.C為邊界和訓(xùn)練錯誤的折衷,也就是模型的復(fù)雜性(結(jié)構(gòu)風(fēng)險)和經(jīng)驗損失的折衷,模型的復(fù)雜性決定了模型的泛化能力.

在回歸支持向量機中,如果預(yù)測值與觀測值之間的偏差小于ε,則認(rèn)為損失等于零,這樣的損失函數(shù)描述了ε不敏感模型,定義為

考慮3種典型的損失函數(shù):線性ε不敏感損失函數(shù)、平方ε不敏感損失函數(shù)和Huber損失函數(shù).如果噪聲密度是一個對稱光滑函數(shù),那么線性損失函數(shù)最好[11].因此,本文采用線性損失函數(shù),并假設(shè)信息檢索中的噪聲密度是一個對稱光滑函數(shù),線性(一次)ε不敏感損失函數(shù)定義為

由于信息檢索中存在大量難以線性擬合的數(shù)據(jù),為了進一步增強回歸支持向量機的性能,可以在訓(xùn)練時刪除不一致的訓(xùn)練樣本,再重新訓(xùn)練,進一步提升系統(tǒng)的性能.

1.3 再采樣

將回歸支持向量機引入信息檢索中,目的是根據(jù)回歸函數(shù)對待檢索文檔進行排序.但由于在信息檢索中,訓(xùn)練樣本是二值的,被分成相關(guān)和不相關(guān).對于信息檢索而言,存在著嚴(yán)重的數(shù)據(jù)不平衡(unbalance data),即兩類樣本(正例和反例)比例嚴(yán)重不平衡,一類訓(xùn)練樣本占多數(shù),另一類訓(xùn)練樣本占少數(shù).在信息檢索中,相關(guān)文檔的數(shù)量要遠低于不相關(guān)文檔,直接應(yīng)用回歸支持向量機并不合適,需要處理數(shù)據(jù)不平衡問題.

處理數(shù)據(jù)不平衡的方法有3大類:過多采樣(oversamp ling)、欠采樣(undersamp ling)及調(diào)整不同類樣本的損失權(quán)重.過多采樣是重復(fù)比例小的一類樣本提高小比例樣本數(shù)量,再采樣是對大比例的一類樣本進行再采樣降低大比例一類樣本數(shù)量.在使用回歸支持向量機的情況下,由于決定回歸函數(shù)的是支持向量,所以過多采樣并不適用,調(diào)整樣本的權(quán)重也無法直接應(yīng)用到回歸支持向量機.本文采用再采樣技術(shù)解決樣本不平衡問題.采用再采樣技術(shù)不僅可以提高檢索的效果,還可以加速訓(xùn)練過程,并降低存儲開銷.在多種再采樣技術(shù)中,隨機采樣技術(shù)性能優(yōu)異,它取得了比其他采樣技術(shù)更好或者是一樣好的結(jié)果,我們采用了隨機采樣技術(shù).

2 實驗及結(jié)果分析

2.1 實驗環(huán)境

實驗是在TREC測試集上進行的.表1是測試集的一些信息,使用的主題(topic)從201～250,該部分主題只有描述部分(descrip tion field)使用了自然語言組成了查詢語句,每個查詢語句包含10～15個詞.

表1 實驗中使用的TREC語料Tab.1 TREC corpus in the experiment

實驗中,為了獲取所需要的每一個句子的概念序列,我們采用基于隱馬爾科夫模型的組塊分析器對文本進行了分析.

實驗比較了回歸支持向量機算法和目前主流的語言模型(一元文法模型)方法.兩個模型的參數(shù)都是通過交叉檢驗(two-fold cross validation)獲得.一元文法模型的自由參數(shù)為平滑參數(shù)(插值參數(shù)),回歸支持向量機的參數(shù)為C,參數(shù)C(模型的復(fù)雜性和經(jīng)驗損失的折衷)是一個變化范圍很大的值.為了確定最優(yōu)的C,設(shè)定C的候選集為{2m,2m-1,…,2n},m、n為整數(shù),m

2.2 實驗結(jié)果及分析

在實驗中將回歸支持向量機模型和主流的語言模型(一元文法模型)進行了比較,表2是實驗的主要結(jié)果.

一元文法模型(UGM)是典型的語言模型,查詢的生成概率用進行估計,平滑算法采用Jelinek-M ercer算法.

在訓(xùn)練中,相關(guān)文檔的回歸值設(shè)為2,不相關(guān)文檔的回歸值設(shè)為1.使用SVMlight(http://svm light. joachim s.o rg)對回歸支持向量機進行了多組實驗,分別是:

實驗1:再采樣,刪除不一致的樣本,訓(xùn)練C,設(shè)ε=0.2;

實驗2:再采樣,刪除不一致的樣本,訓(xùn)練C,設(shè)ε=0;

實驗3:再采樣,保留不一致的樣本,訓(xùn)練C,設(shè)ε=0.2;

實驗4:不再采樣,刪除不一致的樣本,使用同實驗1相同的C,ε=0.2;

實驗5:再采樣,刪除不一致的樣本,設(shè)C=0,ε=0.2.

觀察表2的實驗結(jié)果,可以看出,再采樣、刪除不一致的樣本并重新訓(xùn)練時回歸支持向量機的性能最優(yōu),高于語言模型方法.對比實驗可以看出,合理的設(shè)置ε有助于檢索性能的提升;刪除不一致的訓(xùn)練樣本對檢索系統(tǒng)的性能有微弱的正面影響;再采樣對檢索技術(shù)是至關(guān)重要的;C值的大小決定了模型的復(fù)雜性和經(jīng)驗損失的比例.在兩種極端情況下,C=0時忽略經(jīng)驗損失,C=∞時忽略模型的復(fù)雜性,即顯示了模型的泛化能力.

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

觀察實驗結(jié)果,我們注意到在兩組測試集上的提升幅度顯著不同.其原因可能在于測試集和訓(xùn)練集的劃分不均衡.實驗中使用了交叉檢驗方法,即按查詢將語料兩等分(查詢201～225為一組,查詢226～250為一組),但由于某些查詢在相應(yīng)的文檔集上沒有相關(guān)文檔或相關(guān)文檔很少,造成了訓(xùn)練集和測試集不平衡,最終影響了檢索性能.另外,從信息檢索的任務(wù)(待檢索文檔集中依據(jù)用戶信息需求,按相關(guān)程度對文檔進行排序)出發(fā),只要將用戶最關(guān)心的文檔排在最前面就可以高效地滿足用戶需求,因此,對回歸分析后的值進行調(diào)整,與查詢相關(guān)文檔的排序向前移,與查詢無關(guān)文檔的排序向后移,再重新訓(xùn)練回歸分析器,反復(fù)多次,直至收斂或達到指定次數(shù),這種處理方式預(yù)期可以進一步提升信息檢索系統(tǒng)的性能,也是我們未來工作的重點.

在對比研究中,將檢索視為分類,在相同的特征集、相同的訓(xùn)練集和測試集下,應(yīng)用支持向量機模型,其性能不佳,遠不如語言模型和回歸支持向量機模型.這個工作同Nallapati的工作[1]一樣都使用了支持向量機,不同的是使用的特征集不一樣,但結(jié)果類似,都不理想.從理論分析和這些實驗結(jié)果可以看出,導(dǎo)致支持向量在信息檢索應(yīng)用不成功的原因不在于特征集,而是模型本身不適合于信息檢索.

從實驗結(jié)果可以看出,用回歸支持向量機模型在信息檢索中取得了很好的結(jié)果,回歸支持向量機是典型的判別學(xué)習(xí)模型,本文的方法也具有判別學(xué)習(xí)的優(yōu)勢.

[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

國家自然科學(xué)基金資助項目,編號60873105;國家自然科學(xué)基金重點資助項目,編號60736044.

韓詠(1975-),女,講師,碩士,主要從事信息檢索與信息過濾研究,E-mail:hyhyqhl@sina.com.