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