1995年
Christos Faloutsos and Douglas Oard
University of Maryland
College Park, MD 20742
{christos,oard}@eng.umd.edu
中科院計算所軟體室 王 斌 譯
(2002年1月25日重新修改)
wangbin@ict.ac.cn
摘要
本文總結了資訊檢索(IR)的主要技術，主要內容分成兩部分：第一部分，對傳統IR方法(全文本掃描(full text scanning)、倒排檔(inversion)、簽名文件(signature file)及聚類(clustering))的回顧；第二部分，介紹一些試圖引入語義資訊的新的IR方法(如自然語言處理(NLP)、隱性語義標引(latent semantic indexing, LSI)、神經網路(neural network)等等)。
1 引言
本文分成兩部分。第一部分回顧了傳統文本檢索的方法。總結傳統方法出於兩個目的：一，傳統方法對瞭解新進展提供了豐富的背景知識；二，對這些傳統方法進行變形或者擴展構成新方法的中心內容。具體來說，本文考察了(1)全文掃描方法及其在近似搜索(approximate searching)方面的進展；(2)可能在任何IR系統中都使用的快速倒排檔方法；(3)簽名檔方法；(4)情報學中傳統使用的聚類方法。
總結上述背景知識後，本文第二部分中介紹了近年來一些將NLP技術和IR方法進行結合的嘗試，如隱性語義標引、神經網路等等。
文章最後是結論部分，作者給出了每種方法的要點及相關建議。
2 傳統文本檢索
2.1 全文掃描(Full Text Scanning)
確定某個字串在哪些文檔中出現，最直接的方法就是在所有的文檔中查找該字串(稱為子串測試，substring test)。“字串”是一系列字元組成的序列(不包含通配字元，Don’t Care Characters。比如我們常用*或者?來表示通配字元，譯者注)。如果一個查詢是由多個待查字串組成的複雜布林運算式，那麼就需要額外的步驟來判斷通過子串測試找到的匹配是否滿足該布林運算式(查詢求解，query resolution)。
本文不打算深入考查有關一般正則運算式的搜索方法，該主題可以參照Hopcroft及Ullman於1979年撰寫的《自動機理論》[31,pp.29-35]。給定一個正則運算式，可以構造一個有限狀態自動機，該自動機可以檢測該正則運算式在文檔中的出現。自動機的搜索時間與文檔大小成線性關係，但是自動機的狀態個數可能與正則運算式的大小成指數關係。
然而，如果搜索模式僅限於字串，那麼就可以應用比有限狀態自動機更高效的方法。下面我們就討論這些方法。
(1) 最顯而易見的子串測試方法是：將搜索字串與文檔相應字串進行比較，如果不匹配，則將文檔指標右移一個字元位置後(也可以說將搜索字串右移一個位置)重新將搜索字串與文檔當前的字串比較，直至找到該字串或碰到檔結束為止。該方法雖然簡單易行，但演算法實現時速度很慢。假設搜索的字串長度為m，文檔的長度為n，則最壞情況下需要O(m*n)次比較。
(2) Knuth、Morris及Pratt[37]提出一種只需要O(m+n)次比較的演算法(KMP)。KMP的主要思路就是，不論何時，只要能夠預測到字串的不匹配，則可能將搜索字串右移不止一個位置。該方法需要對搜索字串做一些預處理工作來檢測遞迴的字母序列。預處理的時間為O(m)。(該方法設計精巧，是資料結構課程中的典型內容，譯者注)
(3) 當前所知道的最快的子串測試方法由Boyer與Moore提出[5]。他們提出對字串進行從右到左的比較；如果不匹配，搜索字串可最多右移m個位置再進行匹配。最壞情況下，該方法需要n+m次比較，但通常情況下，比較的次數遠小於這個數目。例如，對於一個隨機的長度為5的搜索串(m=5)，該演算法的典型實現需要考查文檔的i/4個字元(i為開始匹配的字元在文檔中的位置)。同樣，該方法需要O(m)的預處理時間。
(4) 近來對基本演算法的變形可以參見Sunday文 [71]。
(5) 子串測試的另一種方法基於自動機理論。Aho及Corasick[1]於1975年提出一種基於有限狀態自動機的方法，該方法允許同時並行搜索多個字串。搜索的時間為O(n)，建立自動機的時間與待搜索字串的長度成線性關係。
(6) Wu和Manber[78]提出了一種能夠容忍鍵入錯誤的搜索方法。該方法以每次一個字元的方式掃描資料庫，並通過一種靈巧的位元編碼來記住當前已經匹配的字串。該方法速度很快(在Sun級別的工作站上幾秒鐘就可以查詢數兆文本)，也很靈活。其源碼可從Arizona-Tucson大學匿名下載。
總之，每種全文掃描方法的優點都在於不需要空間消耗 (無索引)，極小的插入和更新的費用(不需要更新索引)；缺點在於反應時間太長，該缺點在面對大資料量時表現得尤為突出。所以，全文掃描方法常常用專用硬體實現(Hollaar，1983)[30]，或者將該方法同能夠限制搜索範圍的其他訪問方法(如倒排檔)相結合使用。
2.2 簽名文件(Signature File)
簽名檔方法當前引起了廣泛的關注。在本方法中，每個文檔都通過Hash函數及重疊編碼(superimposed coding)產生一個稱為簽名(signature)的位串。文檔的簽名結果順序存入一個單獨的檔(簽名檔)中，簽名檔比原文件小得多，因此可以提供更快速的搜索。Files和Huskey[26]將該方法用於一書目資料庫。他們使用一停用詞表來忽略普通的詞，對非普通詞則使用一個自動過程將它們還原成詞幹。同時，他們使用一個數值函數而非對照表(look-up table)作為Hash函數，。Harrison[28]使用簽名檔方法以加快子串測試速度。他提出使用相鄰的連續字母(n-gram)作為Hash函數的輸入。Barton等人[3]於1974年提出使用等頻率文本片段(equi-frequent text segment)代替n-gram。因此，簽名中“1”的服從均勻(uniform) 分佈。Tsichritzia和Christodoulakis[73]試圖使用無重疊編碼的簽名檔。他們的方法通過將文檔中每個詞的簽名串聯起來就得到該文檔的簽名。這樣的話，就必須保留位置資訊。Rabitti和Zizka[48]聲稱該方法預期將比重疊編碼更加重CPU的負擔。
其他一些學者採用了類似的方法用於格式化的記錄。一些文章中提出了對文本檢索有潛在利用價值的想法。
Roberts [52] 1979年在一個電話目錄的應用中使用了一級簽名檔。他討論了許多有趣的應用細節，其中的兩個細節可以用於文本檢索：
- 簽名檔採用一種位片(bit-slice)的方式存儲。即所有簽名的頭一位連續存放，次一位再連續存放，…。儘管該結構使得更新很困難，但它能夠減少檢索的I/O費用。
- 他建議在構造簽名時，查詢中經常出現的標引項必須特殊對待。
然而，Roberts並沒有提供這個方面的任何數學分析，而文檔[23]中則對這一點進行了嘗試。文章表明，如果詞的訪問模式和出現頻率事先已知，並且分佈足夠偏斜的話(八二開)，那麼與同樣大小的普通簽名檔相比，該方法設計出的簽名檔，可以避免約50%的誤選(false drop)。
此外，人們還提出了具有更高搜索速度的二級簽名檔[55][54]；簽名樹[14]以及基於簽名的分割[39]也被提出，但是沒有應用於真實資料庫的時間結果的報導。
重疊編碼方法的設計和研究由來已久。首先將重疊編碼用於文本檢索的人是C. N. Mooers [46]。他發明了一種很精巧的基於邊緣凹口卡片和探針的機械設備。該設備可以快速處理對書目的聯合查詢。關鍵字抽取由人工實現，而Hash函數則使用對照表實現。
這種採用邊緣凹口卡片的方法引起了廣泛的興趣。Stiassny[68]使用字母對來產生每個詞的簽名。他還證明：對於一個給定的簽名長度，當文檔的簽名中“1”的數目等於“0”的數目時，誤選概率達到最小。Orosz和Tachacs [47]使用喬丹定律(Jordan’s theorem)，給出了文檔簽名中“1”的概率分佈的一個封閉形公式。Kautz和Singleton[35]討論了設計一個沒有誤選的簽名系統的問題，他們從編碼和資訊理論的角度對該問題進行了研究。儘管他們的方法在理論上很有意義，但在實現時有很多缺點：需要對照表；不易處理日益增長的辭彙表；簽名集合的設計需要巨大的開銷。
在對簽名檔方法的討論即將結束之際，需要指出的是，該方法的主要缺點就是當檔很大時反應時間較長。優點在於實現簡單，對插入的處理效率高，能夠處理詞的部分查詢，能夠支援不斷增長的檔以及對鍵入和拼寫錯誤的容錯性。另外，該方法易於並行化(見文[67]中在Connection Machine上的一個實現)。
2.3 倒排文件(Inverted File)
每個文檔都可以用一系列關鍵字來表示，從檢索目的來說，這些關鍵字描述了文檔的內容。只要找到文檔，便可以找到文檔中的關鍵字。反過來，如果按關鍵字建立到文檔的索引，便可以根據關鍵字快速地檢索到相關文檔。具體地，關鍵字被存儲在索引檔(index file)中(比如，按字母順序存儲)，對於每個關鍵字，都有一個指標鏈表，該表中的每個指標指向與該關鍵字相關的某個文檔，所有指針鏈表構成置入檔(posting file)。這種倒排檔的方法幾乎被當前所有的商用IR系統所採用[61]。
組織索引檔可以採用更複雜的方法，如：B樹，TRIE樹，Hash表或者這些方法的變形或混合(見[36] 第471-542頁)。STAIRS[32]使用了二級索引檔。以相同字母對開始的詞在二級索引中放在一起，一級索引中包含指向二級索引的指標，每個指標指向每個字母對。Lesk[40]使用一張負荷過度、鏈分開的Hash表(over-loaded hash table with separate chaining)來獲得對一書目資料庫的快速檢索。
倒排檔方法的缺點有：存儲開銷大(倒排檔的大小可能會達到原文件大小的300%[29])；動態環境下索引檔更新和重新組織的開銷大；如果表太大太多，則將它們合併的開銷巨大。
該方法的優點有：實現相對簡單，查詢速度快，很容易支援同義詞查詢(例如，同義詞可以在詞典中組織成穿插表(threaded list))。由於上述原因，倒排檔的方法在當前絕大部分的商用系統中被採用(DIALOG，BRS，MEDLARS，ORBIT，STAIRS，見[61]第二章)。
近年來倒排檔方面方面的進展和挑戰包括：
- 置入表分佈不均勻(滿足Zipf’s Law[1][82])。這意味著小部分詞出現頻率高，而大部分詞只出現一次或兩次。這樣的話，有些置入表很長，而大部分置入表的長度為1或2。為了解決問題，人們提出了混合方法策略[24]以及使置入表可調增長的演算法[25]。
- 在現實中，索引檔通常很大，可能有數兆甚至上G。而不管索引檔的大小如何，都要求必須能夠快速地處理插入。快速增量式插入的技術可以參見Tomasic等人[72]、Cutting和Pedersen[12]、Brown等人![Devil [6]](http://service.aspsmb.com/CS/emoticons/emotion-14.gif)
的工作。他們的做法基本上都是基於置入表分佈的不均，對於較長和較短的置入表，分別採取不同的處理辦法。為了解決倒排索引存儲開銷太大的問題，人們提出了一些壓縮方法：Zobel等人[83]將Elias的壓縮體制[22]用於置入表。最後要提到的是，“glimpse”套裝軟體[44] 中使用一個很粗的索引加上“agrep”包[78]來實現近似搜索。
2.4 向量模型和聚類(Vector Model and Clustering)
聚類的基本想法就是將相似的文檔聚合在一起形成類，該想法基於聚類假設(cluster hypothesis)：緊密關聯的文檔往往與相同的查詢要求有關。通過將相似文檔聚類可以加速搜索過程。
聚類在資訊檢索、情報學[61][75]以及模式識別[16]等領域中都引起了廣泛興趣。雖然在模式識別中文檔聚類並非重點，但模式識別中的許多方法和思想都可以用於文檔聚類。
注意到聚類的物件除了文檔外還可以是標引項，因此標引項也可以聚類形成共現標引項(co-occurring terms)類。共現標引項常常彼此相關，有時可能是同義詞。標引項的聚類對敘詞詞典[2](thesaurus)的自動構造和降維(dimensionality reduction)很有用。敘詞詞典的自動構造基於統計準則，因此它在概念上與文檔聚類方法是等價的。然而，Salton[58]聲稱自動標引項聚類演算法的效率值得懷疑，因此，他建議使用半自動方法。
文檔聚類包括兩個過程：聚類產生(cluster generation)及聚類搜索(cluster search)。首先我們討論聚類產生的方法並將它們分類。聚類搜索問題相對容易，將在後面部分討論。
2.4.1 聚類產生方法(Cluster generation methods)
聚類產生過程的操作物件是向量或者t維空間上的點。每個文檔都表示成一個向量，該向量被分配一些關鍵字，即將文檔表示成關鍵字(可能包含權值)組成的向量。這個過程稱為標引(indexing)，可以通過手工或者自動實現。Salton[59]對這兩種實現方式的對比表明，實驗環境下實現的簡單自動標引方法至少與手工方法性能一樣好。
自動標引過程通常使用以下詞典([57]，第117頁，第144-145頁)：
- 一個用於去掉普通詞(如“and”、“the”等等)的負性詞典(negative dictionary)，通常也叫停用詞詞表(stoplist)；
- 一個用於抽取單詞詞幹(stem)的首碼和尾碼表；
- 一個用於將每個詞幹分配到一個概念類的同義詞詞典。
這種方法下，每個文檔表示成一個t維向量，其中t是允許的標引項(概念)的個數。某個標引項在文檔中不存在用0標識或-1標識[9]，反之則用1(二值文檔向量)或者某個正值(標引項的權重)標識，該權重反映了該標引項在文檔中的重要程度。以下是幾種其他的權重函數：
- FREQik：第k個標引項出現在第i個文檔中的頻率。該值很容易獲得且比二值表示的權值更有效。(這個值就是通常所說的TF, Term Frequency，指Term在文檔中出現的頻率，一般來說，TF越大，表明該Term在文檔中的重要性越大，譯者注)
- 標引項專指度(Term specificity) [3] [66]：logN-log(DOCFREQk)+1，其中DOCFREQk表示包含標引項k的文檔數目，N是文檔的總數。該值也容易獲得，並且同樣比二值表示的權值更有效。(這個值實際上可以認為是IDF計算的一個變形，表明該Term在整個文檔集合中的分佈情況，DF 即DOCFREQk越高，該值越低，越不可以用於區分，譯者注)
- 逆文檔頻率(Inverse Document Frequency，IDF)：FREQik/DOCFREQk。與前面的權值相似但似乎更有效(見[61]第105頁)。(IDF通常是指N/DOCFREQk, TFIDF才是FREQik/DOCFREQk，譯者注)
- FREQik*TERMRELk：其中 TERMRELk=(rk/(R-rk))/(sk/(I-sk))，稱為標引項相關因數(term relevance factor)。R為文檔集合中所有相關的文檔數目，rk為相關文檔中含有標引項k的文檔數目，I 為所有不相關的文檔數目，sk為不相關的文檔中含有標引項k的文檔數目。在某種條件下，該權值為理論上最優的權值[79]，且試驗結果似乎證實了這一點([61]第207頁)。該方法的問題在於必須對查詢和所有文檔之間進行相關性評估並對每個標引項計算相應的參數，這需要人類專家花費大量時間才能實現。(TERMRELk可以認為是該Term在相關文檔出現的概率和在不相關文檔出現的概率的比值，是概率檢索模型中常用的一個參數，現在通常通過相關回饋方式來計算，譯者注)
上述過程將文檔表示成t維空間中的點。下一步就是要將這些點劃分到不同的類中。在理想情況下，劃分過程應該達到兩個目標：(1)在理論上穩定(theoretically sound)(2)高效(efficient)。理論上的穩定性準則是指([75]，第47頁)：
- 該方法在增長情況下保持穩定，也就是說，當插入新的文檔時，劃分不會顯著地改變；
- 文檔描述中的細微錯誤只導致劃分的細微改變；
- 該方法與文檔的初始順序無關。
高效性準則主要是指聚類的時間開銷。在分析聚類生成方法的性能時，常常忽略該方法的空間消耗。
迄今為止，人們提出了許多聚類生成方法。但不幸的是，沒有哪個單一的方法同時滿足穩定性準則和高效性準則。因此，在這裏將各種聚類生成方法分成兩類：
- 基於文檔間相似矩陣的穩定性方法；
- 更有效的直接來自文檔向量的迭代方法。
基於相似矩陣的方法(Methods based on the similarity matrix)
這類方法通常需要O(n2)或更多的時間費用(n為文檔的數目)，且常常要用到圖論技術。該方法中，必須選擇文檔之間的相似性函數來度量兩個文檔之間的相似程度。人們提出了很多不同的相似性函數(如可參見[61]第202-203頁)，但是文檔[75](第38頁)指出，如果對上述相似性函數進行適當的歸一化處理，則會發現它們提供幾乎相同的檢索性能。
給定一個文檔相似矩陣，此類聚類方法的一個最簡版本運行如下 (見[16]第238頁)：
(1) 先選定一個適當的閾值;
(2) 相似度大於該閾值的文檔之間用邊相連;
(3) 該圖的連通分量(最大簇)即為所要的類。
如果將類分層，即將類再聚類形成父類，父類再聚類形成父類的父類，…，則常常可以加快檢索的速度。一個將類分層的方法是將上述方法中的閾值不斷減小進行使用。一個更好的將類分層的方法可以參見文檔[74]，該文檔中使用單鏈(最近鄰)聚類準則進行聚類。將該方法用於200個文檔進行實驗，實驗結果表明，該演算法執行需要的時間複雜度為O(n2)。
上述方法(也許所有的聚類生成方法)的 一個共同缺點就是它們都至少需要一個經驗常數：用於相似性度量的閾值或者一個想要的分類個數。該常數會顯著影響最後的劃分結果，它會給給定的資料強加某種 結構，而不是去探測資料內在可能已經存在的結構。也就是說，劃分結果可能不是實際存在的某個結構，而是硬性劃分的一個結構。
Zahn[81]提出的方法試圖解決這一問題。他提出尋找給定點集合(文檔集合)的最小生成樹，然後刪除不相容邊(inconsistent edges)。當某條邊的長度l比它的的入邊的平均長度lavg大得多時稱該邊為不相容邊。結果圖的連通分支即作為聚類結果。同樣，該方法基於一個經驗值(用於不相容邊定義中的閾值)。但是，該方法的結果受該經驗值的影響並不十分敏感。在文章中，Zahn宣稱其方法在多種環境下應用於真實2維資料的有效性：重疊高斯型聚類(Overlapping Gaussian Clusters)，延伸型聚類(核粒子軌跡)，以及生物樣本建立的聚類等等。文章中沒有實驗結果的報導，但是該方法似乎很有前途。
迭代型方法(Iterative methods)
該方法包含了運行時間少於O(n2)時間(如O(nlogn)和O(n2/logn))的多種方法。這些方法直接基於物件(文檔)的描述，並且它們不需要預先計算的相似矩陣。該方法在提高效率的同時，付出的代價是犧牲了理論穩固性，最後的分類結果依賴於物件處理的順序，並且，文檔描述錯誤的結果是不可預測的。這些演算法基於啟發式方法，並且也需要一些經驗值參數，比如：
- 想要的分類數目；
- 每個類中含有的最小及最大文檔數目；
- 用於文檔和類之間相似度量的閾值，一個文檔與類的相似度小於該值時便將它排除在該類之外；
- 類間相互重疊的控制值；
- 一個任意選擇的用於優化的目標函數。
該類方法的過程可以概述如下：
- 確定一個初始的劃分；
- 反復迭代，重新將文檔分配到各個類中，直至不存在一個更好的重新分配為止。
很多迭代型方法都在文獻中找到。對迭代型方法的一個綜述可以參見文檔[75](第51-53頁)。最簡單、最快的方法似乎是單遍(single pass)方法[62]。每個文檔只須處理一次，要麼它被分配到某個類(如果允許重疊的話，可以分配到多個類)中，要麼它產生一個新的類。
在實際中常常可以將基於相似矩陣的穩定性方法和迭代型方法混合使用。Slaton和McGill[61]提出，可以先使用迭代型方法建立一個粗劃分，然後通過圖論方法將先前劃分繼續劃分。Van-Rijsbergen[75]提出另一種混合方法。該方法首先從文檔集中抽樣出一些文檔，然後利用一個時間為O(n2)的演算法為這些樣本文檔構造一個核心聚類，最後使用一個快速的分配策略將剩餘的文檔分配到已存的類中。
Salton[60]對一些迭代型聚類方法的運行時間進行了分析。分析表明，如果假定平均的類個數為logn或n/logn，則迭代型聚類方法的平均運行時間為O(nlogn)或者O(n2/logn)。然而，最壞情況下，運行時間將達到O(n2)。
2.4.2 聚類搜索(Cluster searching)
在已經聚類的文檔中搜索將比聚類生成簡單得多。輸入查詢將表示成一個t維向量，然後將該向量與每個類的質心進行比較。搜索過程處理最相似的那些類，即那些與輸入向量相似度大於某個閾值的類。該演算法中必須選擇一個用於度量類與查詢向量之間相似度的函數，這個函數常常選擇向量間的夾角余弦函數[57]。
Yu和Luk[80]對上述搜索策略作了修改：給定一個(2值)查詢向量及(2值)類向量，他們推導出一個公式，該公式用於計算每個類中滿足查詢的文檔數目的期望值。然後，演算法將只在可能含有足夠多滿足查詢的文檔的類中繼續搜索。在文檔[62]中，他們給出了該方法的實驗結果。實驗表明，該方法與夾角余弦函數方法的性能幾乎一樣(後者更簡單些)。
Croft[11]採用模式識別方法，推導出一個線性判別式函數，該函數本質上是一個查詢向量與類之間的相似度計算函數。他使用文檔頻率的對數值作為每個標引項在類中的權值，通過與夾角余弦函數方法的比較，他認為這種方法性能更優越。
查詢和文檔的向量表示可以採用一種稱為相關性回饋(relevance feedback) [53]的方法，該方法能夠提高搜索的效率。用戶可以在檢索到的文檔集合中確認真正相關的文檔，根據這些文檔，檢索系統可以重新生成查詢向量重新進行搜索。通常，重新生成查詢向量的方法是將相關文檔的向量與原查詢向量相加，並減去不相關的文檔向量，加減的過程中可能會加權。
實驗結果表明，通過2到3次迭代之後，上述方法可以得到很好的結果[56]。
3 使用語義資訊(Using Semantic Information)
在上面討論的IR方法中，我們只使用了文檔的很少一部分資訊用於確定相關性[42]。儘管這些方法存在固有的缺陷，但它們卻常常能夠達到可以接受的正確率，這主要是因為一個文檔的所有文本中包含了大量的冗餘資訊。下面，本文將考查近年以來一些試圖從文檔中獲得更多資訊、獲得更好性能的方法。
這些方法可以分成三類：(a) 使用分析技術，句法資訊及一般自然語言處理技術的方法；(b) 隱性語義標引方法；(c) 使用神經網路比如啟動擴散(spreading activation)模型。
3.1 自然語言處理(Natural Language Processing)
NLP技術試圖通過將某個查詢的語義資訊與文檔的語義資訊進行匹配來提高查詢的性能[33][49][76]。NLP技術已經被應用於大規模Text Retrieval Conference(TREC) 語料庫，並獲得了一定程度的成功[70][41][69]。儘管人們聲稱，要使IR達到其最佳潛能，必須對文本和查詢進行更深層次的語義分析。但是，自動語義分析技術能否帶來顯著的性能提高仍然有待證實。
然而，NLP技術和淺層的IR技術之間並不像它們起初表現那樣具有明顯的邊界。例如，通常使用的停用詞表就用於去掉語義含量較低的詞語。另一個將NLP技術與傳統的IR方法相結合的簡單例子就是使用短語作為標引項。Croft等人[10]提出使用一個粗分析器[7]來探測句子，然後利用句子來進行索引(與使用單個標引項相反)。使用短語作為標引項的好處就是，短語攜帶了更多的語義，但是，這樣做的代價就是，短語的特殊性將會降低依賴於一般性的評分(ranking)及匹配演算法。基於同樣的思路，Rau和Jabobs[50]利用詞典進行分析，將關鍵字分組來獲得更高的正確率和召回率。Mauldin[45]使用一個流覽式(skimming)分析器(即quick-and-dirty式分析器)將文檔轉換為格框架(case frames)。同簡單的關鍵字系統相比，該方法儘管有時會產生更壞的結果，但通常可以提高正確率和召回率。Salton等人[63]提出首先利用文檔向量進行初始過濾，然後再利用章節、段落以及句子向量進行比較。
在一個具有更完備的NLP功能的IR系統中，第一步很可能是自動句法分析。近年以來，自然語言的句法模型方面取得了相當多的進展，出現了多種可用的寬領域高效分析器[43]。語義分析不太好理解，但是一個稱為辭彙成分語義學(lexical compositional semantics)的語法制導語義(syntax-directed semantic)技術取得了進展。更深層的語義表達看來需要更廣闊的知識工程，因此束縛了依賴於NLP的系統的進一步發展。作為一種人工智慧技術的格框架(case frame)分析方法，在某些限定領域被成功使用[51]。
3.2 隱性語義標引(Latent Semantic Indexing)
隱性語義標引(LSI)是一種被證實比在Salton的SMART系統中使用的傳統向量空間技術性能更好的IR向量空間技術。下面將給出LSI的一個簡要但很嚴格的數學描述細節。
為了簡明扼要起見，本文省略了很多有關LSI進展的基本原理以及奇異值分解[4](Singular Value Decomposition，SVD)的存在性和唯一性論述，對該內容感興趣的讀者可以與Deerwester等人聯繫[13]。LSI在資訊過濾以及資訊檢索方面的應用在文[27][21][19]中都有介紹，該技術的未來展望參見文[17][18][2]。
首先我們通過一個最簡單的例子來闡述LSI技術的本質。首先從全部的文檔集中生成一個標引項-文檔矩陣，該矩陣的每個分量為整數值，代表某個特定的標引項出現在某個特定文檔中次數。然後將該矩陣進行奇異值分解，較小的奇異值被剔除。結果奇異向量以及奇異值矩陣用於將文檔向量和查詢向量映射到一個子空間中，在該空間中，來自標引項-文檔矩陣的語義關係被保留，同時標引項用法的變異被抑制。最後，可以通過標準化的內積計算來計算向量之間的夾角余弦相似度，再將文檔按與查詢的相似度降冪排列。
3.2.1 符號
我們採用了Deerwester等人[13]引入的符號。標引項-文檔矩陣X有t行(每行表示每個標引項在文檔中的出現情況)d列(每列表示集合中的每個文檔)。SVD X=T0S0D0T，結果T0是一個t×m的矩陣，它的標準正交列稱為左奇異向量；S0是一個m×m的正奇異值按降冪排序的對角矩陣；D0是一個d×m的矩陣，其標準正交列稱為右奇異向量。m為矩陣X的秩。圖1對X的SVD作了描述。
X
T0
S0
D0T
= = × ×
圖1：X的奇異值分解
通過T0、S0、D0，X可以精確地重構。LSI中的關鍵創新在於只保留S0中的k個最大的奇異值，而將其他的值置為0。k的值是設計時的一個參數。k的取值通常在100至200之間。原來的X矩陣可以用X’來近似，X’=TSDT，T是一個含有標準正交列的t×k矩陣，S是一個正定的k×k對角矩陣，D是一個含有標準正交列的d×k矩陣。圖2對X’的SVD作了描述。
X’
T
S
DT
= = × ×
圖2：X’的奇異值分解
3.2.2 文檔匹配(Document Matching)
LSI的有效性依賴於SVD可從文檔集的標引項頻率向量中抽取關鍵特徵。為了更好地理解這一點，首先有必要給出一個關於構成SVD的三個矩陣的操作性解釋。在源向量空間表示中，XTX是文檔向量的內積d×d對稱矩陣(即計算文檔之間的兩兩相似度，譯者注)，其中每個文檔利用標引項頻率向量表示。這種矩陣的一個用途是支援文檔集合的聚類分析。XTX矩陣的每一列都是X矩陣相應列的文檔向量與每個文檔向量的內積集合。於是，文檔i和文檔j的夾角余弦相似度可以如下計算：
因此，我們可以將矩陣XT看成一個從列向量Xq(描述某個單一文檔或查詢)到一個內積列向量(可以用於計算夾角余弦相似度)的線性函數(即XTXq中的d個分量代表d個文檔分別和Xq的相似度，譯者注)。利用SVD將XT擴展，XTXq=D0S0T0TXq。將該式看成由D0S01/2和S01/2T0T這兩個線性函數的合成對幫助我們理解很有用。首先考慮S01/2T0T。該操作將查詢向量投影到由左奇異向量生成的m維空間上。本質上，T0T矩陣將t維文檔向量空間中的文檔向量投影到一個m維的文檔特徵空間。因為每個奇異值都是正定的，S01/2是一個真正的對角矩陣。因此S01/2矩陣通過分別調節每個特徵而在文檔特徵空間上重新調節。綜合到一起來看，m×t矩陣S01/2T0T是從文檔向量空間到文檔特徵空間的一個投影，在投影過程中加入了這樣的想法，在估計文檔相似性時，一些特徵比另一些特徵更重要。
一旦文檔特徵向量可用，d×m矩陣D0S01/2可以用來計算我們想要的內積。具體地，可以計算文檔向量空間中的m維向量S01/2T0TXq和D0S01/2的每一行向量之間的內積。D0S01/2的每行可以解釋成被投影到文檔特徵空間且與Xq一樣重新調整的文檔向量。
LSI引入的唯一變化就是從S0中剔除小奇異值。這相當於這樣的一個判斷：與小奇異值相關聯的特徵實際上在計算相似度時並不相關，將它們包括進來將降低相關性判斷的精確度。保留下來的特徵是那些對文檔向量在m維空間中的位置大有影響的特徵。Deerwester等人認為，這種選擇抓住了標引項-文檔矩陣的內在語義結構(即概念)，同時剔除了源于標引項用法變異[13]的“噪音”。換句話說，剔除小的奇異值將文檔特徵空間變為文檔概念空間。
剔除小的奇異值將SVD變為X’=TSDT。然後可以計算文檔的內積向量X’TXq=DSTTXq。由於S1/2TT具有非平凡零化空間(nontrivial nullspace)，而DS1/2卻沒有，使用矩陣S1/2TT，LSI試圖通過將X’矩陣的秩從m降為k來抑制標引項用法變異的效果。這通過忽略T0中左奇異向量描述的向量成分來實現，這些成分與S0中的小奇異值相關。
上述分析激發了將S1/2TT看成從標引項空間到概念空間的線性函數、DS1/2中的每行看成與相應文檔相關聯的概念向量。概念向量之間的使用內積的夾角余弦相似度計算比原來基於源文本向量的相似度計算更可靠，這是LSI的主要使用原因所在。
我們可以將一個自然語言查詢看成一個文檔，然後計算該查詢和文檔集中每個文檔的歸一化內積向量。最相近的文檔推送給用戶。當然，查詢中可能含有現存文檔集上的LSI沒有保留的概念，因此，概念空間的調准有可能對一個特定查詢來說不是很適合。Dumais利用該技術對大規模TREC-2文檔集進行了實驗，取得了令人信服的結果。
3.2.3 標引項匹配(Term Matching)
在考查本節解釋的結果之前，通過一種有意義的方法來解釋這些函數的伴隨矩陣是很有幫助的。矩陣XXT由標引項頻率向量的內積組成。為方便起見，我們將這些向量稱為標引項向量以區別于上文提到的文檔向量。這樣稱呼可能會造成某種程度的混淆，因為標引項向量和文檔向量都含有標引項頻率資訊。它們的區別在於，文檔向量用於文檔間的比較，標引項向量用於標引項間的比較。
矩陣XXT的每列都是XT中相應列的標引項向量與每個標引項在文檔集中的標引項向量的內積向量。這些內積向量可以用來計算標引項之間的夾角余弦相似度，就象公式(1)中計算文檔之間的相似度一樣。應用SVD減少矩陣的秩實現LSI，XYq=T0S0D0TYq，其中Yq是X的第q行。剔除較小的奇異值以減小矩陣的秩得到：X’Yq=TSDTYq。這裏，S1/2DTYq是從標引項向量空間到標引項概念空間的投影，它用以在標引項用法變異時保留概念。矩陣TS1/2可以解釋成投影到標引項概念空間並且重新調整的標引項向量。
3.2.4 概念空間(Concept Space)
圖3概括了DS1/2和TS1/2的行、列的解釋。它說明文檔和標引項概念空間是等價的。在一個文檔只含有一個標引項的情況下，這一點很容易理解。在此情況下，TS1/2的行實實在在對應於這個標引項，該行包含了標引項的概念空間。由於S1/2TT是 一個線性操作，因此每個文檔向量只是單標引項文檔向量的簡單求和。因此，每個文檔概念向量是每個標引項向量的線性組合。進一步來說，在線性組合中，每個文 檔概念向量指定了應用於每個標引項向量的係數。換句話說，標引項概念空間和文檔概念空間是等價的，文檔置於文檔中標引項位置的質心?。
矩陣
行
列
TS1/2
標引項概念向量
標引項向量空間基準向量
DS1/2
文檔概念向量
文檔向量空間基準向量
圖3：SVD中行列的解釋
3.3 神經網路(Neural Networks)
該類方法的主要思想就是使用啟動擴散(spreading activation)方法。通常的技術就是，不管是通過手工還是自動方法，構造一個同義詞詞典，然後相應於同義詞詞典中的每個概念在隱藏層建立一個對應的節點。Johannes Scholtes 1993年于Amsterdam大學的博士論文是將spreading activation方法用於資訊檢索的最近的最全面的資料。他撰寫的一份更早的技術報告中包括重要研究的回顧和廣泛的參考文檔[65]。先前的有關本主題的工作還包括Doszkocs等人[15]、Kwok[38]、Belew[4]、Salton和Buckley[64]、Cohen和Kjeldsen![Music [8]](http://service.aspsmb.com/CS/emoticons/emotion-29.gif)
等人的論文。
實現細節可以參見[77]中的討論。Jennings和Higuchi報告了一個用於過濾USENET新聞文章的系統的結果[34]。他們的實驗結果達到了在大規模資訊過濾工作中的合理的性能。
4 結論和建議
我們討論了一些IR的傳統方法以及試圖獲取語義資訊的最近進展。對於傳統IR方法，我的建議如下：
- 全文本掃描方法推薦用於小型資料庫(可達數兆)；推薦使用“agrep”搜索包；
- 倒排檔方法是用於大型資料庫的主力軍；
- 聚類的兩個主要思想是：(a) 相關度回饋；(b) 提供帶有得分值的輸出(即文檔按相關度排序)
對於最近的進展還沒有什麼確定的結論。按短語標引可以在花費更多更精細的預處理(如全部或部分語法分析)的情況下提高少許正確率/召回率(可達20%[10]?)。LSI可以提高正確率/召回率，但是需要兩個前提：(a)一個用於建立標引項-文檔矩陣、實施SVD的可用訓練語料庫；(b) 大量的計算時間，因為一個m×n矩陣的SVD時間比m、n中較小值的多項式時間還多。
因此，總結論就是，儘管最近的一些方法(NLP、LSI以及神經網路等等)看起來很有前途，但怎樣從它們身上獲得最好效果還不清楚。大量的工作正在朝這個方向努力。
參考文檔
[1] A.V. Aho and M.J. Corasick. Fast pattern matching: an aid to bibliographic search. CACM, 18(6):333--340, June 1975.
[2] Brian T. Bartell, Garrison W. Cottrell, and Richard K. Belew. Latent semantic indexing is an optimal special case of multidimensional scaling. In Nicholas Belkin et al., editors, Proceedings of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 161--167. ACM, June 1992.
[3] I.J. Barton, S.E. Creasey, M.F. Lynch, and M.J. Snell. An information-theoretic approach to text searching in direct access systems. CACM, 17(6):345--350, June 1974.
[4] Richard K. Belew. Adaptive information retrieval: Using a connectionist representation to retrieve and learn about documents. In N. J. Belkin and C. J. van Rijsbergen, editors, Proceedings of the Twelfth Annual International ACMSIGIR Conference on Research and Development in Information Retrieval, pages 11--20. ACM, June 1989.
[5] R.S. Boyer and J.S. Moore. A fast string searching algorithm. CACM, 20(10):762--772, October 1977.
Eric W. Brown, James P. Callan, and W. Bruce Croft. Fast incremental indexing for full-text information retrieval. Proc. of VLDB Conf., pages 192--202, September 1994.
[7] K. Church. A stochastic parts program and noun phrase parser for unrestricted text. Proc. of the Second Conf. on Applied Natural Language Processing, pages 136--143, 1988.
Paul R. Cohen and Rick Kjeldsen. Information retrieval by constrained spreading activation in semantic networks. Information Processing and Management, 23(4):255--268, 1987.
[9] W.S. Cooper. On deriving design equations for information retrieval systems. JASIS, pages 385-- 395, November 1970.
[10] W. Bruce Croft, Howard R. Turtle, and David D. Lewis. The use of phrases and structured queries in information retrieval. Proc. of ACM SIGIR, pages 32--45, October 1991.
[11] W.B. Croft. A model of cluster searching based on classification. Information Systems, 5:189--195, 1980.
[12] Doug Cutting and Jan Pedersen. Optimizations for dynamic inverted index maintenance. Proc. SIGIR, pages 405--411, 1990.
[13] Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, and Richard Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41(6):391--407, 1990.
[14] U. Deppisch. S-tree: a dynamic balanced signature index for office retrieval. Proc. of ACM “Research and Development in Information Retrieval”, pages 77--87, September 1986.
[15] Tamas E. Doszkocs, James Reggia, and Xia Lin. Connectionist models and information retrieval. In Martha E. Williams, editor, Annual Review of Information Science and Technology (ARIST), volume 25, pages 209--260. Elsevier, 1990.
[16] R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
[17] Susan T. Dumais. Enhancing performance in latent semantic indexing (LSI) retrieval. Technical Memorandum TM-ARH-017527, Bellcore, September 1990.
[18] Susan T. Dumais. Improving the retrieval of information from external sources. Behavior Research Methods, Instruments and Computers, 23(2):229--236, 1991.
[19] Susan T. Dumais. LSI meets TREC: A status report. In D. K. Harman, editor, The First Text Retrieval Conference (TREC-1), 500-207, pages 137--152, Gaithersburg, MD, March 1993. NIST, NIST. Special Publication 500-207.
[20] Susan T. Dumais. Latent semantic indexing (LSI) and TREC-2. Technical Memorandum TM-ARH-023878, Bellcore, 445 South St., Morristown, NJ 07960, January 1994.
[21] Susan T. Dumais and Jacob Nielsen. Automating the assignment of submitted manuscripts to reviewers. In Nicholas Belkin et al., editors, Proceedings of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 233--244. ACM Press, June 1992.
[22] P. Elias. Universal codeword sets and representations of integers. IEEE Trans. on Information Theory, IT-21:194--203, 1975.
[23] C. Faloutsos and S. Christodoulakis. Design of a signature file method that accounts for non-uniform occurrence and query frequencies. In Proc. 11th International Conference on VLDB, pages 165--170, Stockholm, Sweden, August 1985.
[24] C. Faloutsos and H.V. Jagadish. Hybrid index organizations for text databases. EDBT '92, pages 310--327, March 1992. Also available as UMIACS-TR-91-33 and CS-TR-2621.
[25] Christos Faloutsos and H.V. Jagadish. On b-tree indices for skewed distributions. In 18th VLDB Conference, pages 363--374, Vancouver, British Columbia, August 1992. Also available as.
[26] J.R. Files and H.D. Huskey. An information retrieval system based on superimposed coding. Proc. AFIPS FJCC, 35:423--432, 1969.
[27] Peter W. Foltz. Using latent semantic indexing for information filtering. In Frederick H. Lochovsky and Robert B. Allen, editors, Conference on Office Information Systems, pages 40--47. ACM, April 1990.
[28] M.C. Harrison. Implementation of the substring test by hashing. CACM, 14(12):777--779, December 1971.
[29] R.L. Haskin. Special-purpose processors for text retrieval. Database Engineering, 4(1):16--29, September 1981.
[30] L.A. Hollaar, K.F. Smith, W.H. Chow, P.A. Emrath, and R.L. Haskin. Architecture and operation of a large, full-text information-retrieval system. In D.K. Hsiao, editor, Advanced Database Machine Architecture, pages 256--299. Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
[31] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading, Mass., 1979.
[32] IBM. IBM System/370 (OS/VS), Storage and Information Retrieval System / Vertical Storage (STAIRS/VS). IBM World Trade Corporation.
[33] Paul S. Jacobs and Lisa F. Rau. Natural language techniques for intelligent information retrieval. In Yves Chiaramella, editor, 11th International Conference on Research and Development in Information Retrieval, pages 85--99, Grenoble, France, June 1988. Presses Universitaires de Grenoble.
[34] Andrew Jennings and Hideyuki Higuchi. A user model neural network for a personal news service. User Modeling and Uaer-Adapted Interaction, 3(1):1--25, 1993.
[35] W.H. Kautz and R.C. Singleton. Nonrandom binary superimposed codes. IEEE Trans. Inform. Theory, IT-10:363--377, October 1964.
[36] D.E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass, 1973.
[37] D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput, 6(2):323--350, June 1977.
[38] K. L. Kwok. A neural network for probabilistic information retrieval. In N. J. Belkin and C. J. van Rijsbergen, editors, Proceedings of the Twelfth Annual International ACMSIGIR Conference on Research and Development in Information Retrieval, pages 21--30. ACM, June 1989.
[39] D.L. Lee and C.-W. Leng. Partitioned signature file: Designs and performance evaluation. ACM Trans. on Information Systems (TOIS), 7(2):158--180, April 1989.
[40] M.E. Lesk. Some Applications of Inverted Indexes on the UNIX System. Bell Laboratories, Murray Hill, New Jersey, 1978.
[41] David Lewis and Alan Smeaton. Workshop on: Use of natural language processing at TREC. In D. K. Harman, editor, The First Text Retrieval Conference (TREC-1), pages 365--366, Gaithersburg, MD, March 1993. NIST, U. S. Department of Commerce.
[42] David Dolan Lewis. Representation and Learning in Information Retrieval. PhD thesis, University of Massachusetts, February 1992.
[43] Dekang Lin and Randy Goebel. Context-free grammar parsing by message passing. In Proceedings of PACLING 93, 1993.
[44] Udi Manber and Sun Wu. Glimpse: a tool to search through entire file systems. Proc. of USENIX Techn. Conf., 1994. Also available as TR 93-94, Dept. of Comp. Sc., Univ. of Arizona, Tucson, or through anonymous ftp (ftp://cs.arizona.edu /glimpse/glimpse.ps.Z).
[45] Michael L. Mauldin. Performance in ferret: a conceptual information retrieval system. Proc. of ACM SIGIR, pages 347--355, October 1991.
[46] C. Mooers. Application of random codes to the gathering of statistical information. Bulletin 31, Zator Co, Cambridge, Mass, 1949. based on M.S. thesis, MIT, January 1948.
[47] G. Orosz and L. Tackacs. Some probability problems concerning the marking of codes into the superimposed field. J. of Documentation, 12(4):231--234, December 1956.
[48] F. Rabitti and J. Zizka. Evaluation of access methods to text documents in office systems. Proc. 3rd Joint ACM-BCS Symposium on Research and Development in Information Retrieval, 1984.
[49] Ashwin Ram. Interest-based information filtering and extraction in natural language understanding systems. In Proceedings of the Bellcore Workshop on High Performance Information Filtering, November 1991.
[50] Lisa F. Rau and Paul S. Jacobs. Creating segmented databases from free text for text retrieval. Proc. of ACM SIGIR, pages 337--346, October 1991.
[51] Ellen Riloff. Using cases to represent context for text classification. In Bharat Bhargava, Timothy Finin, and Yalena Yesha, editors, Proceedings of the Second International Conference on Information and Knowledge Management, pages 105--113. ACM, November 1993.
[52] C.S. Roberts. Partial-match retrieval via the method of superimposed codes. Proc. IEEE, 67(12):1624--1642, December 1979.
[53] J.J. Rocchio. Performance indices for document retrieval. In G. Salton, editor, The SMART Retrieval System - Experiments in Automatic Document Processing. Prentice-Hall Inc, Englewood Cliffs, New Jersey, 1971. Chapter 3.
[54] R. Sacks-Davis, A. Kent, and K. Ramamohanarao. Multikey access methods based on superimposed coding techniques. ACM Trans. on Database Systems (TODS), 12(4):655--696, December 1987.
[55] R. Sacks-Davis and K. Ramamohanarao. A two level superimposed coding scheme for partial match retrieval. Information Systems, 8(4):273--280, 1983.
[56] G. Salton. Relevance feedback and the optimization of retrieval effectiveness. In G. Salton, editor, The SMART Retrieval System - Experiments in Automatic Document Processing. Prentice-Hall Inc, Englewood Cliffs, New Jersey, 1971. Chapter 15.
[57] G. Salton. The SMART Retrieval System - Experiments in Automatic Document Processing. Prentice-Hall Inc, Englewood Cliffs, New Jersey, 1971.
[58] G. Salton. Experiments in automatic thesaurus construction for information retrieval. Information Processing 71, pages 115--123, 1972.
[59] G. Salton. Recent studies in automatic text analysis and document retrieval. JACM, 20(2):258--278, April 1973.
[60] G. Salton. Dynamic Information and Library Processing. Prentice-Hall Inc, Englewood Cliffs, N.J, 1975.
[61] G. Salton and M.J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.
[62] G. Salton and A. Wong. Generation and search of clustered files. ACM TODS, 3(4):321--346, December 1978.
[63] Gerard Salton, James Allan, and Chris Buckley. Automatic structuring and retrieval of large text files. Comm. of ACM (CACM), 37(2):97--108, February 1994.
[64] Gerard Salton and Chris Buckley. On the use of spreading activation methods in automatic information retrieval. In Yves Chiaramella, editor, 11th International Conference on Research and Development in Information Retrieval, pages 147--160. ACM SIGIR, June 1988.
[65] J. C. Scholtes. Neural nets and their relevance for information retrieval. ITLI Prepublication CL-91-02, University of Amsterdam, Institute for Language, Logic and Information, Department of Computational Linguistics, October 1991.
[66] K. Sparck-Jones. A statistical interpretation of term specificity and its application in retrieval. J. of Documentation, 28(1):11--20, March 1972.
[67] C. Stanfill and B. Kahle. Parallel free-text search on the connection machine system. CACM, 29(12):1229--1239, December 1986.
[68] S. Stiassny. Mathematical analysis of various superimposed coding methods. American Documentation, 11(2):155--169, February 1960.
[69] Tomek Strzalkowski and Jose Perez Carballo. Recent developments in natural language text retrieval. In D. K. Harman, editor, The Second Text Retrieval Conference (TREC-2), pages 123--136, Gaithersburg, MD, March 1994. NIST.
[70] Tomek Strzalowski. Natural language processing in large-scale text retrieval tasks. In D. K. Harman, editor, The First Text Retrieval Conference (TREC-1), pages 173--187, Gaithersburg, MD, March 1993. NIST, U.S. Department of Commerce.
[71] D.M. Sunday. A very fast substring search algorithm. Comm. of ACM (CACM), 33(8):132--142, August 1990.
[72] Anthony Tomasic, Hector Garcia-Molina, and Kurt Shoens. Incremental updates of inverted lists for text document retrieval. ACM SIGMOD, pages 289--300, May 1994.
[73] D. Tsichritzis and S. Christodoulakis. Message files. ACM Trans. on Office Information Systems, 1(1):88--98, January 1983.
[74] C.J. Van-Rijsbergen. An algorithm for information structuring and retrieval. Computer Journal, 14(4):407--412, 1971.
[75] C.J. Van-Rijsbergen. Information Retrieval. Butterworths, London, England, 1979. 2nd edition.
[76] Edgar B. Wendlandt and James R. Driscoll. Incorporating a semantic analysis into a document retrieval strategy. In A. Bookstein, Y. Chiaramella, G. Salton, and V. V. Raghavan, editors, Proceedings of the Fourteenth Annual International ACM/SIGIR Conference on Research and Development in Information Retrieval, pages 270--279. ACM, October 1991.
[77] Ross Wilkinson and Philip Hingston. Using the cosine measure in a neural network for document retrieval. In A. Bookstein, Y. Chiaramella, G. Salton, and V. V. Raghavan, editors, Proceedings of the Fourteenth Annual International ACM/SIGIR Conference on Research and Development in Information Retrieval, pages 202--210. ACM, October 1991.
[78] Sun Wu and Udi Manber. Agrep - a fast approximate pattern searching tool. In USENIX Conference, January 1992.
[79] C.T. Yu, K. Lam, and G. Salton. Term weighting in information retrieval using the term precision model. JACM, 29(1):152--170, January 1982.
[80] C.T. Yu and W.S. Luk. Analysis of effectiveness of retrieval in clustered files. JACM, 24(4):607--622, October 1977.
[81] C.T. Zahn. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans. on Computers, C-20(1):68--86, January 1971.
[82] G.K. Zipf. Human Behavior and Principle of Least Effort: an Introduction to Human Ecology. Addison Wesley, Cambridge, Massachusetts, 1949.
[83] Justin Zobel, Alistair Moffat, and Ron Sacks-Davis. An efficient indexing technique for full-text database systems. VLDB, pages 352--362, August 1992.
[1] Zipf通過收集大量的統計材料，發現自然語言辭彙的分佈服從一個簡單的定律。他稱這一定律為“省力法則”(Principle of least effort)。即將某一篇較長的文獻(約5000字以上)中每個詞出現的頻率按照遞減順序排列起來(高頻詞在前，低頻詞在後)，並用自然數給這些詞編上等級序號，頻次最高的是1級，其次是2級，3級，…，如果用f表示詞在文獻中出現的頻次，用r表示詞的等級序號，則有fr=c (c為常數)
[2] 在文獻自動加權標引中，如果把文獻頻率太低的詞作為標引詞將會使查全率降低。為避免這種情況，一般採用的方法是，將文獻頻率太低的詞構成敘詞類(thesaurus term class)，用一個詞代替該敘詞類，使文獻頻率升高。如，可以用“電腦”來代替“電腦”、“電腦”等同義詞組成的詞類。
[3] 標引詞的專指度是指標引詞表達文獻主題的準確程度。在標引文獻時選用專指度強的標引詞越多，則檢索出文獻的針對性也就越強，查準率就越高。該值應該是用於選擇標引詞，而不是在標引詞確定以後求得各標引詞的權值。
[4] 任何一個m×n的矩陣可以被分解成A=Q1ΣQ2T，其中Q1是一個m×m正交矩陣，Q2是一個n×n正交矩陣，而Σ是對角矩陣。對角上的非零值稱為矩陣A的奇異值。去掉零行，即是本文中的形式。
No comments:
Post a Comment