搜索引擎技術(shù):性能提高遇到瓶頸
|
||
2006-08-10 13:34:17.08 | ||
駱衛(wèi)華 劉群 張俊林 | ||
計(jì)世網(wǎng) 評(píng)估搜索引擎背后的信息檢索技術(shù)的先進(jìn)性,驗(yàn)證互聯(lián)網(wǎng)環(huán)境下大規(guī)模數(shù)據(jù)的信息檢索技術(shù)的系統(tǒng)有效性,,推動(dòng)檢索技術(shù)的進(jìn)步和成果轉(zhuǎn)化,,這是信息檢索技術(shù)評(píng)測(cè)的主要目標(biāo)。
2005.9.20-9.22 相關(guān)網(wǎng)頁(yè)檢索 網(wǎng)上評(píng)測(cè) 北京大學(xué)計(jì)算機(jī)技術(shù)研究所 北京郵電大學(xué)模式識(shí)別實(shí)驗(yàn)室 哈爾濱工業(yè)大學(xué)信息檢索研究室 清華大學(xué)智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室 中國(guó)科學(xué)院自動(dòng)化研究所 表1 2003年度評(píng)測(cè)只有一個(gè)子任務(wù),,即全文檢索核心技術(shù)評(píng)測(cè),,但測(cè)試在小規(guī)模和大規(guī)模兩種數(shù)據(jù)集上進(jìn)行,目的是更為全面地考察系統(tǒng)的性能,。其中小規(guī)模數(shù)據(jù)評(píng)測(cè)主要側(cè)重于奧運(yùn)領(lǐng)域文本的檢索,。檢索題目
以及標(biāo)準(zhǔn)答案委托中科院軟件所人工完成,在精選的數(shù)千篇網(wǎng)頁(yè)上設(shè)計(jì)了20道檢索題目,,其中體育類(lèi) 15道,。大規(guī)模數(shù)據(jù)采用從國(guó)內(nèi)9個(gè)網(wǎng)站采集的約100多萬(wàn)篇網(wǎng)頁(yè)作為評(píng)測(cè)數(shù)據(jù),規(guī)模達(dá)到GB級(jí),。檢索題目由中科院計(jì)算所設(shè)計(jì),,共18道,選題領(lǐng)域廣泛,,包括政治、經(jīng)濟(jì),、文化,、體育等諸多方面。對(duì)大規(guī)模數(shù)據(jù)集,,不可能全部通過(guò)人工方式制作出標(biāo)準(zhǔn)答案,。因此,這里采用了一種稱(chēng)為Pooling的方法,。該方法最早由Jones和Rijsbergen提出,,并在TREC中得到廣泛應(yīng)用和檢驗(yàn),其思想是:針對(duì)每個(gè)查詢(xún)主題,,從參與評(píng)比的各系統(tǒng)所送回的測(cè)試結(jié)果中抽取出前若干篇文檔,,合并形成一個(gè)文檔池(Pool),,視之為該查詢(xún)主題可能的相關(guān)文檔候選集合,將集合中重復(fù)的文檔去除后,,再送給該查詢(xún)集的構(gòu)建者進(jìn)行相關(guān)判斷,。
2004年度評(píng)測(cè)的任務(wù)變?yōu)閮身?xiàng),即文檔檢索和段落檢索,。其中文檔檢索要求參評(píng)者對(duì)每個(gè)查詢(xún)條件返回以文檔為單位的檢索結(jié)果,;而段落檢索要求參評(píng)者以段落為單位給出檢索結(jié)果,段落的具體定義和長(zhǎng)短可由參評(píng)者自由選擇,。為了引導(dǎo)參賽單位研究更具實(shí)用性的技術(shù),,本次測(cè)試還增加了對(duì)檢索速度的評(píng)測(cè)。兩個(gè)任務(wù)的評(píng)測(cè)語(yǔ)料都是由北大天網(wǎng)提供的15GB的中文簡(jiǎn)體網(wǎng)頁(yè),。組織方在這些數(shù)據(jù)上擬定了30個(gè)查詢(xún)條件,。由于參賽隊(duì)伍較少,2003年的評(píng)測(cè)中Pooling技術(shù)沒(méi)有有效發(fā)揮作用,,因此本次評(píng)測(cè)集的答案采用Pooling和人工相結(jié)合的方法生成,,即利用檢索工具以及段落查找輔助工具同時(shí)結(jié)合人工判斷形成了初步標(biāo)準(zhǔn)答案,在各隊(duì)提交了檢索結(jié)果后,,又利用Pooling方法對(duì)初步標(biāo)準(zhǔn)答案進(jìn)行調(diào)整形成最終的標(biāo)準(zhǔn)答案,。 隨著參評(píng)單位來(lái)源的擴(kuò)大以及測(cè)試集規(guī)模的增長(zhǎng),以往把系統(tǒng)在測(cè)試現(xiàn)場(chǎng)安裝,、運(yùn)行并提交結(jié)果的模式面臨很多問(wèn)題,。于是,借鑒國(guó)外著名評(píng)測(cè)會(huì)議的經(jīng)驗(yàn),,2005年的評(píng)測(cè)以網(wǎng)上測(cè)試代替現(xiàn)場(chǎng)測(cè)試,。9月20日,組織方通過(guò)官方網(wǎng)站(www.863data.org.cn)發(fā)布測(cè)試數(shù)據(jù),,要求參評(píng)單位在22日之前提交運(yùn)行結(jié)果,。本屆信息檢索評(píng)測(cè)影響力迅速擴(kuò)大,在組織過(guò)程中得到了中科院軟件所,、北京大學(xué),、微軟亞洲研究院等單位的鼎力協(xié)助。本屆評(píng)測(cè)只安排了相關(guān)網(wǎng)頁(yè)檢索子任務(wù),,要求給定主題,,返回測(cè)試集中與該主題相關(guān)的網(wǎng)頁(yè)并按相關(guān)度排序。參加評(píng)測(cè)的單位通過(guò)自動(dòng)方式和人工方式根據(jù)主題構(gòu)造查詢(xún),。自動(dòng)方式是指在沒(méi)有任何人為因素的影響下根據(jù)主題構(gòu)造查詢(xún)的方式,,除此之外的方式均為人工方式。 本次評(píng)測(cè)的任務(wù)的難度比以往大大增加。首先,,測(cè)試數(shù)據(jù)的規(guī)模達(dá)到了海量級(jí),,采用了北京大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室提供的以中文為主的Web測(cè)試集 CWT100g,共571萬(wàn)個(gè)網(wǎng)頁(yè),,容量為90GB,。其次,查詢(xún)條件的數(shù)量也大幅增加到50個(gè),。本屆評(píng)測(cè)的測(cè)試集構(gòu)造,、評(píng)測(cè)組織實(shí)施和結(jié)果分析,都更加規(guī)范科學(xué),。查詢(xún)條件盡量模擬用戶(hù)的真實(shí)信息需求,。標(biāo)題查詢(xún)域(title)盡量簡(jiǎn)短,一般為2~5個(gè)詞匯,。描述查詢(xún)域(desc)一般為一到兩句自然語(yǔ)言語(yǔ)句,。敘述查詢(xún)域 (narr)進(jìn)一步詳細(xì)描述用戶(hù)的信息需求。部分題目出題時(shí)參考目前互聯(lián)網(wǎng)搜索引擎統(tǒng)計(jì)出的比較熱門(mén)的用戶(hù)需求,。題目涉及領(lǐng)域盡可能全面,。包含政治、經(jīng)濟(jì),、文化,、娛樂(lè)、體育等多個(gè)不同領(lǐng)域,。題目整體難易程度適中,,標(biāo)準(zhǔn)答案數(shù)目不太少也不過(guò)多,從而提高不同系統(tǒng)結(jié)果的區(qū)分度,。此外,,為了使參評(píng)單位的系統(tǒng)調(diào)整到最佳性能,組織方還提前發(fā)布訓(xùn)練集,、開(kāi)發(fā)集和檢索源數(shù)據(jù),。 評(píng)測(cè)結(jié)果分析 作為國(guó)內(nèi)有較大影響的評(píng)測(cè)會(huì)議,863信息檢索評(píng)測(cè)基本上反映了中文信息檢索技術(shù)的發(fā)展水平,。下面我們通過(guò)2005年度最新評(píng)測(cè)結(jié)果來(lái)分析國(guó)內(nèi)的研究現(xiàn)狀,。這次評(píng)測(cè)分為自動(dòng)和手工構(gòu)造查詢(xún)條件兩組。評(píng)測(cè)結(jié)果如下表所示(由于863評(píng)測(cè)結(jié)果發(fā)布采用匿名方式,,因此這里只給出最終結(jié)果而不顯示參賽單位名稱(chēng)): 指標(biāo) System 1 System 2 System 3 System 4 System 5 MAP 0.2727 0.1862 0.3107 0.3175 0.2858 R-PRECISION 0.3320 0.2554 0.3672 0.3605 0.3293 P@10 0.5300 0.5180 0.6240 0.5540 0.6280 表1 信息檢索評(píng)測(cè)結(jié)果—自動(dòng)組 指標(biāo) System 1 System 2 System 3 System 4 System 5 MAP 0.3257 0.1705 0.3538 0.2673 0.3671 R-PRECISION 0.3826 0.2327 0.4078 0.3185 0.4140 P@10 0.5580 0.4640 0.6840 0.4800 0.7040 表2 信息檢索評(píng)測(cè)結(jié)果—手工組 從所有參評(píng)隊(duì)伍的整體檢索效果看,這次評(píng)測(cè)的結(jié)果與以往的評(píng)測(cè)結(jié)果相比,,在各個(gè)指標(biāo)都有了很大提高,。這主要是因?yàn)檠芯空呃昧随溄臃治黾夹g(shù)、錨文本等相關(guān)評(píng)價(jià)因素來(lái)提高準(zhǔn)確率,并針對(duì)評(píng)測(cè)采取有效的技術(shù)
手段來(lái)克服中文檢索中的某些難點(diǎn),,比如命名實(shí)體識(shí)別等,。此外相關(guān)反饋或者重排序技術(shù)對(duì)于提高檢索效果也有一定的幫助。從檢索模型來(lái)說(shuō),,參評(píng)隊(duì)伍采用了向量空間模型,、概率模型、語(yǔ)言模型等基本模型或者混合模型,,同時(shí)利用了PageRank,、鏈入分析等鏈接分析或者頁(yè)面分析技術(shù)來(lái)提高檢索效果。中文檢索相對(duì)英文等其他語(yǔ)種來(lái)說(shuō),,如何正確分詞對(duì)于檢索效果有所影響,,尤其是命名實(shí)體、縮略語(yǔ)以及新詞等未登錄詞的正確識(shí)別對(duì)于某些查詢(xún)來(lái)說(shuō)影響較大?,F(xiàn)在的大部分檢索系統(tǒng)在索引以及查詢(xún)分析階段采用了命名體識(shí)別,,從結(jié)果來(lái)看,取得了比較好的效果,。
當(dāng)前的中文檢索技術(shù)均基于國(guó)際主流的算法,,在評(píng)測(cè)中成績(jī)較好的單位在TREC評(píng)測(cè)中也曾取得不錯(cuò)的成績(jī)??梢钥闯?,這些算法提供了基準(zhǔn)級(jí)的性能,系統(tǒng)級(jí)的創(chuàng)新或改進(jìn)不多,,不過(guò)現(xiàn)有系統(tǒng)都會(huì)針對(duì)中文的特點(diǎn)進(jìn)行改進(jìn),。總體上,,如果用戶(hù)草擬的查詢(xún)條件能夠比較全面準(zhǔn)確地表達(dá)用戶(hù)需求的話(huà),,現(xiàn)有的中文檢索技術(shù)一般能夠提供比較好的檢索結(jié)果,但是對(duì)于以下方面還存在著一些問(wèn)題: * 查詢(xún)條件與文檔詞匯內(nèi)容失配,; * 部分命名體,,新詞以及縮略語(yǔ)識(shí)別還存在著一些問(wèn)題; * 在計(jì)算相似度時(shí),,查詢(xún)?cè)~匯權(quán)重的設(shè)定正確與否也在一定程度上影響檢索效果,。 這些問(wèn)題的存在導(dǎo)致現(xiàn)有檢索系統(tǒng)性能下降,針對(duì)這些問(wèn)題,,現(xiàn)有的檢索技術(shù)還有很大的改善空間來(lái)獲得比較滿(mǎn)意的檢索結(jié)果,。 經(jīng)過(guò)眾多研究者的努力,規(guī)范化評(píng)測(cè)對(duì)信息檢索技術(shù)發(fā)展的重要作用已經(jīng)得到了廣泛認(rèn)同,。雖然和國(guó)外相比起步較晚,,但短短幾年間,,中文信息檢索的規(guī)范化評(píng)測(cè)從無(wú)到有,已經(jīng)取得了令人鼓舞的進(jìn)步,。但是,,總的來(lái)說(shuō),國(guó)內(nèi)仍處于學(xué)習(xí)國(guó)外的相關(guān)評(píng)測(cè)(尤其是TREC系列會(huì)議)的階段,。 規(guī)范化評(píng)測(cè)與公正客觀這個(gè)終極目標(biāo)還有一定的距離,,而如何降低人為因素的影響仍是擺在評(píng)測(cè)組織者面前的一道難題。而國(guó)內(nèi)的信息檢索評(píng)測(cè)無(wú)論是從數(shù)據(jù)規(guī)模還是從評(píng)測(cè)手段來(lái)看,,與國(guó)際知名評(píng)測(cè)仍有較大差距,,這是由我國(guó)目前的科研和應(yīng)用的總體水平?jīng)Q定的。但差距的存在也表明提升的空間巨大,,國(guó)內(nèi)的相關(guān)研究者任重而道遠(yuǎn),。 鏈接 1. Cranfield試驗(yàn) 早期信息檢索技術(shù)評(píng)測(cè)最著名的研究是由Cleverdon在1960年代所進(jìn)行的Cranfield試驗(yàn),它首開(kāi)規(guī)范化評(píng)測(cè)研究之先河,,開(kāi)創(chuàng)了以測(cè)試集(Test Collection)配合測(cè)試標(biāo)準(zhǔn)(Measures)來(lái)評(píng)估系統(tǒng)的模式,。所謂測(cè)試集,是一種在規(guī)范化環(huán)境中測(cè)試系統(tǒng)性能的機(jī)制,,包括測(cè)試問(wèn)題(Queries),、測(cè)試文件集(Document Set)以及相關(guān)判斷(Relevance Assessment)三個(gè)部分。其研究設(shè)計(jì)的概念是假設(shè)在給定的查詢(xún)問(wèn)句與文件集中,,某些文件是與查詢(xún)問(wèn)句相關(guān)的,。系統(tǒng)的目的是檢索出相關(guān)的文件,并拒絕不相關(guān)的文件,。Cranfield研究在評(píng)測(cè)技術(shù)的發(fā)展歷程上具有里程碑意義,,很多思想和做法都成為后人評(píng)測(cè)的基石。然而,,由于剛剛起步,, Cranfield試驗(yàn)還存在很多不足之處。早期所采用的測(cè)試集規(guī)模均不大,,且大多數(shù)是使用同質(zhì)型較高的文件集(例如,,Cranfield二期研究只包含 279個(gè)查詢(xún)問(wèn)句和1400個(gè)文件),因此它與真實(shí)的檢索環(huán)境之間存在著很大差異,?;谶@樣的測(cè)試集所發(fā)展出來(lái)的檢索系統(tǒng),在實(shí)際應(yīng)用中往往受到極大的限制,,效果并不好,。 2.文本檢索會(huì)議TREC
Cranfiled試驗(yàn)之后的20多年間,也有研究機(jī)構(gòu)做了類(lèi)似試驗(yàn),,但都存在兩個(gè)根本缺陷:一是缺少在相同的測(cè)試數(shù)據(jù)上使用相同評(píng)測(cè)方法的跨系統(tǒng)公開(kāi)評(píng)測(cè),;二是缺少真實(shí)的大規(guī)模測(cè)試集,。不過(guò),要建構(gòu)大型測(cè)試集必須耗費(fèi)相當(dāng)可觀的人力,、物力,這對(duì)大多數(shù)單位來(lái)說(shuō)是不堪負(fù)荷的,,因此大規(guī)模的測(cè)試集一直無(wú)法真正實(shí)施,。 20世紀(jì)90年代,基于軍事和反恐情報(bào)處理的需要,,美國(guó)國(guó)防部高級(jí)研究計(jì)劃署(DARPA)提出了TIPSTER文本處理計(jì)劃,,文本檢索會(huì)議(Text REtrieval Conference,簡(jiǎn)稱(chēng)TREC)就是該計(jì)劃的重要組成部分,。1992年,,在美國(guó)國(guó)防部高級(jí)研究與開(kāi)發(fā)機(jī)構(gòu)和DARPA的資助下,NIST召開(kāi)了第一屆TREC會(huì)議,,以后每年舉辦一次,,到2005年已舉辦了14屆。TREC的組織者認(rèn)為,,對(duì)不同系統(tǒng)的比較,,其意義并不在于要證明某個(gè)系統(tǒng)優(yōu)于其他系統(tǒng),而是要把更多不同的技術(shù)放在一起公開(kāi)討論,,這對(duì)技術(shù)的發(fā)展有很大好處,。于是,TREC自開(kāi)辦之初,,就明確提出了四個(gè)目標(biāo): 1. 以大規(guī)模測(cè)試集為基礎(chǔ),,推動(dòng)信息檢索的研究; 2. 通過(guò)建立一個(gè)開(kāi)放式的論壇,,使與會(huì)者交流研究成果與心得,,以增進(jìn)學(xué)術(shù)界、產(chǎn)業(yè)界與政府的交流互通,; 3. 通過(guò)對(duì)真實(shí)檢索環(huán)境的模擬與重要改進(jìn),,加速將實(shí)驗(yàn)室研究技術(shù)轉(zhuǎn)化為商業(yè)產(chǎn)品; 4. 開(kāi)發(fā)適當(dāng)且具有實(shí)用性的評(píng)價(jià)技術(shù),,供各界遵循采用,。 TREC的評(píng)測(cè)機(jī)制基本沿襲Cranfield模式,但它的很多思想和做法也突破了傳統(tǒng)的限制,。首先,,TREC極力強(qiáng)調(diào)數(shù)據(jù)規(guī)模的重要性,并投入了大量人力,、物力去構(gòu)建大規(guī)模測(cè)試集和訓(xùn)練集,,第一屆就提供了2G的數(shù)據(jù)集,;其次,TREC把復(fù)雜的單一目標(biāo)分解為若干明確的測(cè)試項(xiàng)目(稱(chēng)為“Track”),,其中很多項(xiàng)目都以模擬真實(shí)的使用環(huán)境為目標(biāo),;第三,TREC非常重視不同的算法和系統(tǒng)設(shè)計(jì)者之間的交流,,參賽單位除了要提交系統(tǒng)的運(yùn)行結(jié)果之外,,還可以參加研討會(huì),與會(huì)者可以公開(kāi)系統(tǒng)的架構(gòu),,評(píng)估結(jié)果并互相討論切磋,。 TREC發(fā)展到現(xiàn)在,已經(jīng)成為備受矚目的標(biāo)尺性測(cè)試,,對(duì)信息檢索研究領(lǐng)域產(chǎn)生了巨大而深遠(yuǎn)的影響,。今天,在TREC評(píng)測(cè)中名列前茅的算法往往成為大家研究的重點(diǎn),,很多商用搜索引擎所采用的核心技術(shù)就是那些被TREC證明成功的算法發(fā)展而來(lái)的,。TREC論壇成為研究人員互相交流學(xué)習(xí)的重要途徑,很多新的思想和方法正是從這里碰撞產(chǎn)生,。TREC為新的熱點(diǎn)研究提供了急需的數(shù)據(jù)和評(píng)價(jià)體系,,促進(jìn)了這些技術(shù)的快速發(fā)展。鑒于TREC的巨大成功,,現(xiàn)在的眾多評(píng)測(cè),,甚至其他研究領(lǐng)域的評(píng)測(cè),如跨語(yǔ)言檢索評(píng)測(cè)會(huì)議NTCIR,、CLEF,,機(jī)器翻譯評(píng)測(cè)TC-STAR等,都或多或少受到它的影響,。 3. 信息檢索評(píng)價(jià)指標(biāo) 信息檢索評(píng)測(cè)指標(biāo)直接關(guān)系到參評(píng)系統(tǒng)的最終評(píng)價(jià),,指標(biāo)不合理會(huì)導(dǎo)致對(duì)系統(tǒng)的評(píng)價(jià)也不合理,因此規(guī)范化的評(píng)測(cè)會(huì)議對(duì)于評(píng)價(jià)指標(biāo)的選擇都是很慎重的,。 早期常用的評(píng)測(cè)指標(biāo)包括準(zhǔn)確率(Precision),、召回率(Recall)、F1值等,,其意義如下: 召回率=系統(tǒng)檢索到的相關(guān)文件數(shù)/相關(guān)文件總數(shù) 準(zhǔn)確率=系統(tǒng)檢索到的相關(guān)文件數(shù)/系統(tǒng)返回文件總數(shù) 顯而易見(jiàn),,召回率考察系統(tǒng)找全答案的能力,而準(zhǔn)確率考察系統(tǒng)找準(zhǔn)答案的能力,,兩者相輔相成,,從兩個(gè)不同側(cè)面較為全面地反映了系統(tǒng)性能。F1值是一個(gè)把準(zhǔn)確率和召回率結(jié)合起來(lái)的指標(biāo),??紤]到某些情況下不同系統(tǒng)的準(zhǔn)確率和召回率互有高低,,不便于直接比較,而使用F1值就可以更直觀地對(duì)系統(tǒng)性能進(jìn)行排序,。 隨著測(cè)試集規(guī)模的擴(kuò)大以及人們對(duì)評(píng)測(cè)結(jié)果理解的深入,,更準(zhǔn)確反映系統(tǒng)性能的新評(píng)價(jià)指標(biāo)逐漸出現(xiàn),包括: (1) 平均準(zhǔn)確率(Mean Average Precision,,即MAP):?jiǎn)蝹€(gè)主題的MAP是每篇相關(guān)文檔檢索出后的準(zhǔn)確率的平均值,。主題集合的MAP是每個(gè)主題的MAP的平均值。MAP是反映系統(tǒng)在全部相關(guān)文檔上性能的單值指標(biāo),。 (2) R-Precision:?jiǎn)蝹€(gè)主題的R-Precision是檢索出R篇文檔時(shí)的準(zhǔn)確率。其中R是測(cè)試集中與主題相關(guān)的文檔的數(shù)目,。主題集合的R-Precision是每個(gè)主題的R-Precision的平均值,。 (3) P@10:P@10是系統(tǒng)對(duì)于該主題返回的前10個(gè)結(jié)果的準(zhǔn)確率??紤]到用戶(hù)在查看搜索引擎結(jié)果時(shí),,往往希望在第一個(gè)頁(yè)面(通常為10個(gè)結(jié)果)就找到自己所需的信息,因此設(shè)置了這樣一個(gè)擬人化的指標(biāo),,P@10常常能比較有效地反映系統(tǒng)在真實(shí)應(yīng)用環(huán)境下所表現(xiàn)的性能,。 (駱衛(wèi)華、劉群工作單位為中國(guó)科學(xué)院計(jì)算技術(shù)研究所,,張俊林工作單位為中國(guó)科學(xué)院軟件所) |
|
來(lái)自: 鈴兒響叮當(dāng) > 《信息檢索》