信息檢索的概率模型

1、信息檢索的概率模型一、 綜述一、 信息檢索技術(shù)由于以因特網(wǎng)為主體的信息高速公路的不斷普及和發(fā)展，信息技術(shù)已經(jīng)滲透到我們社會生活的各個角落，正以前所未有的速度和能力改變著我們的生活的工作方式，我們真正處于一個“信息爆炸”的時代。一方面，因特網(wǎng)上面蘊(yùn)含的海量信息遠(yuǎn)遠(yuǎn)超過人們的想象；另一方面，面對信息的汪洋大海，人們往往感到束手無策，無所適從，出現(xiàn)所謂的“信息過載”和“信息迷向”的現(xiàn)象。于是一個極富挑戰(zhàn)性的課題：如何幫助人們有效地選擇和利用所感興趣的信息，盡量剔除不相關(guān)的信息。同時保證人們在信息選擇方面的個人隱私權(quán)利？成為學(xué)術(shù)界和企業(yè)界所十分關(guān)注的焦點(diǎn)。隨著在線文本的日益增多，其中包括新聞、電子雜志

2、、電子郵件、技術(shù)報告、文檔以及網(wǎng)上圖書館。如此眾多的信息，僅僅依靠大腦來收集和整理所需要的信息顯然是不夠的。所以，自動收集和整理所需要的各類信息成為信息產(chǎn)業(yè)面臨新的挑戰(zhàn)和新的發(fā)展契機(jī)。根據(jù)不同的應(yīng)用背景和不同的使用目的，信息處理技術(shù)已經(jīng)演化信息檢索、信息過濾、信息分類、問題回答等方向。由于目前網(wǎng)上信息的表現(xiàn)形式大多數(shù)為文本，而且文本也是廣大用戶所習(xí)慣接收的形式。因此我們在下面主要討論中文文本檢索和相關(guān)的評價方案。1、信息檢索技術(shù)的發(fā)展信息檢索（information retrieval）是指信息按一定的方式組織起來，并根據(jù)信息用戶的需要找出有關(guān)的信息的過程和技術(shù)。狹義的信息檢索就是信息檢索過程

3、的后半部分，即從信息集合中找出所需要的信息的過程。信息檢索起源于圖書館的參考咨詢和文摘索引工作，從19世紀(jì)下半葉首先開始發(fā)展，至20世紀(jì)40年代，索引和檢索成已為圖書館獨(dú)立的工具和用戶服務(wù)項目。1945年，vannevar bush的論文就像我們可能會想的第一次提出了設(shè)計自動的，在大規(guī)模的存儲數(shù)據(jù)中進(jìn)行查找的機(jī)器的構(gòu)想。這被認(rèn)為是現(xiàn)在信息檢索技術(shù)的開山之作。進(jìn)入50年代后，研究者們開始為逐步的實現(xiàn)這些設(shè)想而努力。在50年代中期，在利用電腦對文本數(shù)據(jù)進(jìn)行檢索的研究上，研究者取得了一些成果。其中最有代表性的是luhn在ibm公司的工作，他提出了利用詞對文檔構(gòu)建索引并利用檢索與文檔中詞的匹配程度進(jìn)行

4、檢索 的方法，這種方法就是目前常用的倒排文檔技術(shù)的雛形。在著名的國際文本檢索會議(text retrieval conference,trec)上，有兩個最重要的研究方向：routing task和ad hoc task。其熱點(diǎn)問題包括從早期的文本檢索、文本過濾到當(dāng)前的問題回答。文本信息檢索就是根據(jù)用戶提出的具體查詢，在大量相對穩(wěn)定的文本源中，檢索出符合用戶查詢條件的文本，并按其滿足查詢的程度排序列出。文本檢索技術(shù)的發(fā)展已經(jīng)有四十多年的歷史，取得了很大的成就，產(chǎn)生了大批實用的檢索系統(tǒng)，積累了很多成熟的技術(shù)。1992年，nist(美國國家標(biāo)準(zhǔn)和技術(shù)研究所)與darpa聯(lián)合贊助了每年一次的trec

5、，對于文本檢索和文本過濾和問題回答等專題傾注了極大的熱忱。目前隨著因特網(wǎng)的迅速發(fā)展，需求的不斷增加，文本檢索以及相關(guān)技術(shù)方面取得了長足的進(jìn)展，成為信息產(chǎn)業(yè)新的增長點(diǎn)。2、信息檢索技術(shù)的簡介信息檢索系統(tǒng)流程大致如下圖所示：總體上，系統(tǒng)可分為四個部分：數(shù)據(jù)預(yù)處理，索引生成，查詢處理，檢索。下面我們分別對各個部分采用的技術(shù)加以介紹。1. 數(shù)據(jù)預(yù)處理目前檢索系統(tǒng)的主要數(shù)據(jù)來源是web，格式包括網(wǎng)頁、word 文檔、pdf 文檔等，這些格式的數(shù)據(jù)除了正文內(nèi)容之外，還有大量的標(biāo)記信息，因此從多種格式的數(shù)據(jù)中提取正文和其他所需的信息就成為數(shù)據(jù)預(yù)處理的主要任務(wù)。此外，眾所周知，中文字符存在多種編碼，比如gb2

6、312、big5、unicode（cjk 區(qū)），而原始數(shù)據(jù)集往往包含多種編碼，因此要正確地檢索到結(jié)果必須進(jìn)行統(tǒng)一編碼轉(zhuǎn)換。研究者們對預(yù)處理部分要提取哪些信息并沒有共識，這與后續(xù)處理所需的信息密切相關(guān)，一般來說，正文、錨文本和鏈接地址都是要提取出來的。2. 索引生成對原始數(shù)據(jù)建索引是為了快速定位查詢詞所在的位置，為了達(dá)到這個目的，索引的結(jié)構(gòu)非常關(guān)鍵。目前主流的方法是以詞為單位構(gòu)造倒排文檔表，其結(jié)構(gòu)大致如下圖所示：每個文檔都由一串詞組成，而用戶輸入的查詢條件通常是若干關(guān)鍵詞，因此如果預(yù)先記錄這些詞出現(xiàn)的位置，那么只要在索引文件中找到這些詞，也就找到了包含它們的文檔。為了進(jìn)一步提高查詢的速度，在組織

7、索引時還可以采用一些更復(fù)雜的方法，比如b樹、trie 樹、哈希表等。這個階段還需要對預(yù)處理之后的文檔進(jìn)行詞法分析，這是因為很多語言的文本都不宜直接把正文中的字符串用于建立索引。例如，中文里的詞與詞之間不存在分隔符，因此必須先進(jìn)行分詞，而英文中的詞存在很多變形，比如“compute”就存在“computes”、“computing”、“computed”等多種變形，應(yīng)先進(jìn)行詞根還原。此外，有些詞雖然出現(xiàn)頻率很高，但對于查詢沒有任何幫助，比如“的”、“了”等，就無需放入索引，為此需要預(yù)備一個停用詞表（stop word list）對這類詞進(jìn)行過濾。3. 查詢處理用戶輸入的查詢條件可以有多種形式，包

8、括關(guān)鍵詞、布爾表達(dá)式、自然語言形式的描述語句甚至是文本，但如果把這些輸入僅當(dāng)作關(guān)鍵詞去檢索，顯然不能準(zhǔn)確把握用戶的真實信息需求。很多系統(tǒng)采用查詢擴(kuò)展來克服這一問題。各種語言中都會存在很多同義詞，比如查“計算機(jī)”的時候，包含“電腦”的結(jié)果也應(yīng)一并返回，這種情況通常會采用查詞典的方法解決。但完全基于詞典所能提供的信息有限，而且很多時候并不適宜簡單地以同義詞替換方法進(jìn)行擴(kuò)展，因此很多研究者還采用相關(guān)反饋、關(guān)聯(lián)矩陣等方法對查詢條件進(jìn)行深入挖掘。4. 檢索最簡單的檢索系統(tǒng)只需要按照查詢詞之間的邏輯關(guān)系返回相應(yīng)的文檔就可以了，但這種做法顯然不能表達(dá)結(jié)果與查詢之間的深層關(guān)系。為了把最符合用戶需求的結(jié)果顯示在

9、前面，還需要利用各種信息對結(jié)果進(jìn)行重排序。目前有兩大主流技術(shù)用于分析結(jié)果和查詢的相關(guān)性：鏈接分析和基于內(nèi)容的計算。許多研究者發(fā)現(xiàn)，www 上超鏈結(jié)構(gòu)是個非常豐富和重要的資源，如果能夠充分利用的話，可以極大地提高檢索結(jié)果的質(zhì)量?；谶@種鏈接分析的思想，sergey brin 和larry page 在1998 年提出了pagerank 算法，同年j.kleinberg 提出了hits 算法，其它一些學(xué)者也相繼提出了另外的鏈接分析算法，如salsa，phits，bayesian等算法。這些算法有的已經(jīng)在實際的系統(tǒng)中實現(xiàn)和使用，并且取得了良好的效果。而基于內(nèi)容的計算則沿用傳統(tǒng)的文本分類方法，多采用向

10、量空間模型、概率模型等方法來逐一計算用戶查詢和結(jié)果的相似度（相關(guān)性）。兩者各有優(yōu)缺點(diǎn)，而且恰好互補(bǔ)。鏈接分析充分利用了web 上豐富的鏈接結(jié)構(gòu)信息，但它很少考慮網(wǎng)頁本身的內(nèi)容，而直觀上看，基于內(nèi)容的計算則較為深入地揭示了查詢和結(jié)果之間的語義關(guān)系，但忽略了不同網(wǎng)頁之間的指向關(guān)系，因此現(xiàn)在很多系統(tǒng)嘗試把兩者結(jié)合起來，以達(dá)到更好的性能。3、信息檢索技術(shù)的模型信息檢索模型可形式化地表示成為一個四元組，d是一個文檔集合，q是一個查詢集合，f是一個對文檔和查詢建模的框架，r(qi,dj) 是一個排序函數(shù)，它給查詢qi和文檔 dj 之間的相關(guān)度賦予一個排序值。3.1、布爾模型所謂布爾檢索, 就是采用布爾代數(shù)

11、的方法, 用布爾表達(dá)式表示用戶提問, 通過對文本標(biāo)識與用戶給出的檢索式進(jìn)行邏輯比較來檢索文本。設(shè)文本集d 中某一文本i, 該文本可表示為:di = ( t1 , t2, , tm) ,其中, t1 , t 2, , t m 為標(biāo)引詞, 用以反映i 的內(nèi)容。另設(shè)用戶某一檢索式如下:qj = ( t1 t 2) ( t3 ( t4) ) .對于該檢索式, 系統(tǒng)響應(yīng)并輸出的一組文本應(yīng)為: 它們都含有標(biāo)引詞t1 和t2 , 或者含有標(biāo)引詞t 3, 但不含有標(biāo)引詞t 4。布爾檢索具有簡單、易理解、易實現(xiàn)等優(yōu)點(diǎn), 故得到廣泛的應(yīng)用。1967年后, 布爾檢索模型正式被大型文獻(xiàn)檢索系統(tǒng)采用, 并漸成為各種商業(yè)

12、性聯(lián)機(jī)檢索系統(tǒng)的標(biāo)準(zhǔn)檢索模式, 服務(wù)信息情報界30多年, 直到現(xiàn)在, 大多數(shù)商用檢索系統(tǒng)仍采用布爾檢索。盡管布爾檢索有著種種的優(yōu)點(diǎn), 但是它的缺點(diǎn)仍然是明顯的, 它存在的主要缺陷有以下幾點(diǎn)。( 1) 布爾邏輯式的構(gòu)造不易全面反映用戶的需求。用標(biāo)引詞的簡單組配不能完全反映用戶的實際需要, 用戶需要那一方面內(nèi)容的文本, 需要到多大程度, 這是檢索式無法表達(dá)清楚的, 如對上述檢索式, t1 和t2 , 究竟用戶希望能得到更多地反映t1 內(nèi)容的文本還是反映t2 內(nèi)容的文本, 傳統(tǒng)的布爾檢索無法解決此問題。( 2) 匹配標(biāo)準(zhǔn)存在某些不合理的地方。例如, 在響應(yīng)某個用“”連接的檢索時, 系統(tǒng)把只含有其中一

13、個或數(shù)個但非全部檢索詞的文本看作與那些根本不含有其中一個檢索詞的文本一樣差, 同樣加以排除; 另一方面, 用響應(yīng)某個用“”連接的檢索式時, 系統(tǒng)都不能把含有所有這些檢索詞的文本看作比那些只含有其中一個檢索詞的文本更好一些。( 3) 檢索結(jié)果不能按照用戶定義的重要性排序輸出。系統(tǒng)檢索輸出的文本中, 排在第一位的文本不一定是文本集中最適合用戶需要的文本, 用戶只能從頭到尾瀏覽才能知道輸出文本中那些更適合自己的需要。針對于標(biāo)準(zhǔn)的布爾模型中文獻(xiàn)表達(dá)形式過于簡單、檢索條件過于嚴(yán)格而出現(xiàn)的問題，人們對其采取了擴(kuò)充和修改，提出了擴(kuò)展的布爾模型。如salton 于1983年提出的一種所謂的擴(kuò)展布爾檢索模型,

14、它是將向量檢索模型與布爾檢索模型融為一體, 并克服了傳統(tǒng)希爾模型的一些缺陷, 下面我們用矢量的方法來討論布爾檢索。設(shè)文本集中每篇文本僅由兩個標(biāo)引詞t1 和t2 標(biāo)引, 并且t1、t2允許賦以權(quán)值, 其權(quán)值范圍為 0, 1 , 權(quán)值越接近1, 說明該詞越能反映文本的內(nèi)容, 反之, 越不能反映文本的內(nèi)容, 在salton 模型中, 上述情形用平面坐標(biāo)系上某點(diǎn)代表某一文本和用戶給出的檢索式, 如圖：圖中的橫、縱坐標(biāo)用t1、t2 表示, 其中a( 0, 1) 表示詞t1 權(quán)值為0, 詞t 2 權(quán)值為1 的文本, b( 1, 0) 表示詞t 1權(quán)值為1, 詞t 2 權(quán)值為0 的文本, c( 1, 1)

15、表示詞t 1、t 2 的權(quán)值均為1 的文本, 文本集d 中凡是可以用t 1、t 2 標(biāo)引的文本可以用四邊形oacb 中某一點(diǎn)表示, 同樣, 用戶給出檢索式后, 也可用四邊形oacb 中某一點(diǎn)表示。下面我們來看看salton 模型中是如何構(gòu)造相似度計算式的。對于由t1 和t2 構(gòu)成的檢索式q = t1 t2 , 在圖1中只有a 、b、c 3點(diǎn)所代表的各文本才是最理想的文本, 對于某一文本d 來說, 當(dāng)d 點(diǎn)離a、b、c 3點(diǎn)越接近時說明相似度越大，或者說，當(dāng)d點(diǎn)離o點(diǎn)越遠(yuǎn)時，相似度越大。因而d與o的距離 = = 可以作為我們衡量一文本與查詢q 的相關(guān)程度的一個尺度, 顯然0 2 , 為了使相似度

16、控制在0 與1 之間, 將相似度定義為:sim( d, q( t1 t2 ) ) = (1)對于由t1 和t 2 構(gòu)成的查詢q = t1 t 2, 只有c 點(diǎn)才是最理想的文本, 用d 與c 的距離 = 作為我們衡量一文本與查詢q 的相關(guān)程度的一個尺度, 于是, 把相似度定義為:sim( d, q( t1 t2 ) ) = 1 -(2) ( 1)、( 2) 式還可推廣到對檢索標(biāo)引詞進(jìn)行加權(quán)的情形, 設(shè)檢索標(biāo)引詞t1、t2 的權(quán)值分別為a, b,0 a, b 1, 則( 1) 式、( 2) 式可進(jìn)一步推廣為:sim( d, q( t1 , a) ( t2, b) ) = 1 - (4)salton

17、 模型還給出了把標(biāo)引詞推廣到n 個時的相似度計算公式。設(shè)d = ( d1 , d2, , dn ) ,其中d i 表示第i 個標(biāo)引詞t i 的權(quán)值, 0 di 1。由布爾運(yùn)算符“”及“”所確定的檢索式分別為:q( p ) = ( t1 , a1) ( t 2, a2) ( tn, an ) ,q( p ) = ( t1 , a1) ( t 2, a2) ( tn, an ) ,其中ai 表示第i 個檢索標(biāo)引詞ti 的權(quán)值, 0 ai 1, 這里, p 是一個可變的量, 1 q , 在salton 模型中, 以( 4) 式作為基本的出發(fā)點(diǎn), 在n 個標(biāo)引詞生成的n 維歐氏空間中應(yīng)用l p矢量模公

18、式進(jìn)行歐氏模的計算, 將文本和查詢的相似度定義為:sim( d, q( p) ) = 1 - 在文本信息檢索中, 布爾檢索不僅具有簡單、易理解等特點(diǎn), 而且易于在計算機(jī)中加以實現(xiàn), 是一種最為常用的檢索方法。擴(kuò)展的布爾模索模型salton 模型克服了傳統(tǒng)布爾模型的一些缺陷, 更符合了用戶的需要。3.2、向量空間模型向量空間模型是由salton及其學(xué)生們在六十年代末到七十年代初提出并發(fā)展起來的。這一模型將給定的文本(文章、查詢或文章中的一段等)轉(zhuǎn)換成一個維數(shù)很高，由一系列關(guān)鍵詞組成的向量。模型并沒有規(guī)定關(guān)鍵詞如何定義，但是一般來說，關(guān)鍵詞可以是字，詞或者短語。假設(shè)我們用“詞”作為term，那么在

19、詞典中的每一個詞，都定義向量空間中的一維。如果一篇文檔包含這個詞，那么表示這個文檔的向量在這個詞所定義的維度上應(yīng)該擁有一個非0值。這個模型最大特點(diǎn)是可以方便地計算出任意兩個向量的近似程度，即向量所對應(yīng)的文本間的相似性。用信息檢索的術(shù)語來說，如果兩個向量是相近的，則其對應(yīng)的文本是語義相關(guān)的。將所有文獻(xiàn)和查詢以向量形式表示，則針對特定的查詢向量，比較它與所有文獻(xiàn)向量的相似度，并依相似度將文獻(xiàn)降序排列，這便是現(xiàn)代信息檢索系統(tǒng)中常用的方法。salton及其學(xué)生們還根據(jù)向量空間模型實現(xiàn)了smart系統(tǒng)。該系統(tǒng)在過去的30多年中，對信息檢索的研究有非常重要的影響。信息檢索的許多理論和技術(shù)(如自動索引、加權(quán)

20、技術(shù)、相關(guān)反饋、文獻(xiàn)聚類等)都是在smart上首先實現(xiàn)或測試的。假設(shè)表示文檔向量，而表示查詢向量，文檔與查詢的相關(guān)性可以用余弦距離表示如下：如果我們用和表示和中的第i維的值，并且對每個文檔矢量進(jìn)行歸一化，即令，那么上式有可以表示為在此，究竟如何取值是一個重要的問題，其取值一般被稱為關(guān)鍵詞i在文檔d中的權(quán)重。目前，對關(guān)鍵詞權(quán)重的確定方法一般都需要獲取一些關(guān)于關(guān)鍵詞的統(tǒng)計量，而后根據(jù)這些統(tǒng)計量，應(yīng)用某種認(rèn)為規(guī)定的計算公式來得到權(quán)重。 最常用的統(tǒng)計量包括： tf，term frequency的縮寫，表示某個關(guān)鍵詞在某個文檔中出現(xiàn)的頻率。 qtf，query term frequency的縮寫。表示查

21、詢中某關(guān)鍵詞的出現(xiàn)頻率。 n，集合中的文檔總數(shù) df，document frequency的縮寫，表示文檔集合中，出現(xiàn)某個關(guān)鍵詞的文檔個數(shù)。 idf，inversed document frequency的縮寫。 dl，文檔長度 adl，平均文檔長度權(quán)重的計算：在向量空間模型下，構(gòu)造關(guān)鍵詞權(quán)重計算公式有三個基本原則：1. 如果一個關(guān)鍵詞在某個文檔中出現(xiàn)次數(shù)越多，那么這個詞應(yīng)該被認(rèn)為越重要。 2. 如果一個關(guān)鍵詞在越多的文檔中出現(xiàn)，那么這個詞區(qū)分文檔的作用就越低，于是其重要性也應(yīng)當(dāng)相應(yīng)降低。 3. 一篇文檔越長，那么其出現(xiàn)某個關(guān)鍵詞的次數(shù)可能越高，而每個關(guān)鍵詞對這個文檔的區(qū)分作用也越低，相應(yīng)的應(yīng)

22、該對這些關(guān)鍵詞予以一定的折扣。 早期的權(quán)重往往直接采用tf，但是顯然這種權(quán)重并沒有考慮上述第二條原則，因此在大規(guī)模系統(tǒng)中是不適用的。目前，常用的關(guān)鍵詞權(quán)重計算公式大多基于tf和df進(jìn)行構(gòu)建，同時，一些較為復(fù)雜的計算公式也考慮了文檔長度?，F(xiàn)簡要列舉如下：tf-idf得分。嚴(yán)格地說，tf/idf得分并不特指某個計算公式，而是一個計算公式集合。其中tf與idf都可以進(jìn)行各種變換，究竟何種變換較能符合實際需求，需要由實驗和應(yīng)用來驗證。常見的變換方法有：其中，最后一個公式，即:被大量系統(tǒng)證明是最有效的。此外，較為常用的關(guān)鍵詞權(quán)重算法還包括okapi權(quán)重和pivoted normalization 權(quán)重(

23、pnw)。這些公式綜合考慮了查詢和文檔中的詞頻，以及文檔的長度。okapi權(quán)重需要預(yù)設(shè)三個參數(shù)： k1，在1.0-2.0之間 b,通常為0.75 k3,在0-1000之間 而pnw則需要預(yù)設(shè)一個參數(shù)s，大部分情況下取0.20。 在經(jīng)典模型中，假設(shè)索引項是獨(dú)立的，或者說是正交的。這個假設(shè)極大地簡化了索引項權(quán)值的計算過程，盡管這一假設(shè)有時不符合自然語言的實際情況，但是在這個假設(shè)下，計算權(quán)值的過程簡單快捷，因而在目前很多實用的信息檢索模型中仍被廣泛采用。向量空間模型中索引項權(quán)重的算法提高了檢索的性能，改進(jìn)了檢索效果，同時采用了部分匹配的策略和一定的相似度計算方法，使得模型可以根據(jù)結(jié)果文檔與檢索項的相似度進(jìn)行排序，檢索出與用戶查詢要求接近的