文字資訊檢索

文字資訊檢索是針對文字的資訊檢索技術。在技術社群中，文字資訊檢索常常被等同於資訊檢索技術本身。

相對影片、音訊檢索而言，文字資訊檢索是發展較快也較成熟的，其他模態的資訊檢索技術，往往也要仰賴文字資訊檢索的支援。

雖然網路搜尋引擎目前已不僅僅局限於對文字進行檢索，文字資訊檢索仍然是大部分網路搜尋引擎的基礎。

歷史介紹[編輯]

自人類的文字產生起，如何快速地從大量的，記錄在各種各樣的儲存媒體中尋找或獲取資訊就成為一個引人注目的問題。這個問題關係到人類如何能夠主動地取得自己需要的知識。因此，文字資訊檢索技術甚至可以追述到古代的書籍編目。但是直到近一個世紀，隨著人類的知識以前所未有的速度急劇膨脹，資訊儲存方式越來越豐富，使得在海量的，多模態的資訊庫中進行快速、準確的檢索成為急迫的需求。1945年，Vannevar Bush的論文《就像我們可能會想的……》^[1]第一次提出了設計自動的，在大規模的儲存資料中進行尋找的機器的構想。這被認為是現在資訊檢索技術的開山之作。進入50年代後，研究者們開始為逐步的實現這些設想而努力。在50年代中期，在利用電腦對文字資料進行檢索的研究上，研究者取得了一些成果。其中最有代表性的是Luhn在IBM公司的工作^[2]，他提出了利用詞對文件構建索引並利用檢索與文件中詞的匹配程度進行檢索的方法，這種方法就是目前常用的倒排文件技術的雛形。

在60年代，資訊檢索技術的一些關鍵技術取得了突破。其間出現了一些優秀的系統以及評價指標。在評價指標方面，由Cranfield的研究組組織的Cranfield評測^[3]提出了許多目前仍然被廣泛採用的評價指標，而在系統方面，Gernard Salton開發的SMART系統^[4]構建了一個很好的研究平台，在此平台上，研究者可以定義自己的文件相關性測度，以改進檢索效能。這樣，作為一個研究課題，資訊檢索技術擁有了較為完善實驗平台與評價指標，其研究理所當然地步入了快車道。也正因為如此，在70年代到80年代，許多資訊檢索的理論與模型被提出，並且被證明對當時所能獲得的資料集是有效的。其中最為著名的是Gerard Salton提出的向量空間模型^[5] ^[6] ^[7]。至今該模型還是資訊檢索領域最為常用的模型之一。但是，檢索的對象——文字集合的缺乏使得這些技術在海量文字上的可靠性無法得到驗證。當時的研究大多針對數千篇的文件組成的集合。這時，美國國家標準技術研究所(NIST)組織的文字檢索會議(Text Retrieval Conference, TREC)的召開改變了這一情況。TREC是一個評測性質的會議，為參評者提供了大規模的文字語料，從而大大推動了資訊檢索技術的快速發展。會議的第一次召開是1992年，不久後，網際網路興起為資訊檢索技術提供了一個巨大的實驗場。從Yahoo到Google，大量實用的文字資訊檢索系統開始出現並得到廣泛應用。這些系統從事實上改變了人類取得資訊與知識的方式。

目前，在文字檢索領域，簡單的資訊檢索已經開始向更加複雜且人性化的垂直搜尋演化，引入了資訊抽取技術以提取文件中的結構化資訊。

模型[編輯]

早期的資訊檢索系統採用「布林查詢」的方法來進行全文檢索。這種方法無疑將構造一個合適的查詢的責任推到使用者身上。使用者必須詳細的規劃自己的查詢，其複雜程度不亞於程式語言。這種檢索方式並不提供任何的文件相關性測度，對於文件與查詢的評價就只有「匹配」，「不匹配」兩種而已。這兩點問題決定了布林查詢不能被廣泛應用。但是，由於布林檢索能夠給使用者提供更多的可控制性，今天我們仍然可以在搜尋引擎的「進階搜尋」中找到布林查詢的身影。

對於大規模的語料庫，任何檢索都可能返回數量眾多的結果，因此對檢索結果進行排序是必須的。因此，一個好的資訊檢索模型必須提供文件相關性測度。一個好的測度應該使與使用者查詢需求最相關的那些結果，排在最前面，同時允許儘可能多的，與使用者查詢有一定關係的結果被包括進來。目前，最為常用的資訊檢索模型有三種：

向量空間模型 (Vector Space Model, VSM)
概率模型 (Probabilistic Model)
推理網路模型 (Inference Network Model)

向量空間模型[編輯]

向量空間模型最早由Gerard提出^[5]。在此模型中，一個文件(Document)被描述成由一系列關鍵詞(Term)組成的向量。模型並沒有規定關鍵詞如何定義，但是一般來說，關鍵詞可以是字，詞或者短語。在語音文件檢索中，還可以是混淆類、音子、音子串等等單元。假設我們用「詞」作為Term，那麼在詞典中的每一個詞，都定義向量空間中的一維。如果一篇文件包含這個詞，那麼表示這個文件的向量在這個詞所定義的維度上應該擁有一個非0值（對絕大多數系統來說，是正值）。

當一個查詢被提交時，由於這個查詢也是由文字構成，所以也可以被向量空間所表示。模型將對查詢與文件，計算一個相似度需要注意的是，模型也沒有對相似度給出確切的定義。它可以使歐氏距離，也可以是兩個向量的夾角的餘弦。

假設 ${\overrightarrow {D}}$ 表示文件向量，而 ${\overrightarrow {Q}}$ 表示查詢向量，文件與查詢的相關性可以用餘弦距離表示如下：

Sim({\overrightarrow {D}},{\overrightarrow {Q}})={\frac {{\overrightarrow {D}}\cdot {\overrightarrow {Q}}}{({\overrightarrow {D}}\cdot {\overrightarrow {D}})({\overrightarrow {Q}}\cdot {\overrightarrow {Q}})}}

如果我們用 $w_{t_{i}Q}$ 和 $w_{t_{i}D}$ 表示 ${\overrightarrow {D}}$ 和 ${\overrightarrow {Q}}$ 中的第 $i$ 維的值，並且對每個文件向量進行歸一化，即令 ${\overrightarrow {D}}\cdot {\overrightarrow {D}}\equiv 1$ ，那麼上式有可以表示為

Sim({\overrightarrow {D}},{\overrightarrow {Q}})=\sum _{t_{i}\in Q\cap D}w_{t_{i}Q}\cdot w_{t_{i}D}

在此， $w_{t_{i}}$ 究竟如何取值是一個重要的問題，其取值一般被稱為關鍵詞 $i$ 在文件D中的權重。關鍵詞權重問題將在隨後進行專門的討論。

傳統向量空間模型的一個問題是各個維度間缺乏相關性，因而無法對文件中各個詞的相關性提供資訊。從宏觀上看，仍然沒有擺脫「關鍵詞匹配」的窠臼。一個自然的想法就是對文件特徵——文件向量進行降維，將維數巨大的文件向量投影到某個較小維度的空間中，使得關鍵詞之間即使不完全匹配，也能夠根據語意發生關係。這就誕生了潛語意索引(Latent Semantic Indexing)^[8]，它通過對向量空間進行奇異值分解，將高維文件向量投射到低維潛語意空間中。潛語意索引隨後被融入概率模型框架中，形成了基於概率模型的PLSI(Probabilistic Latent Semantic Indexing)^[9]，和LDA(Latent Dirichlet Allocation)^[10]。

概率模型[編輯]

概率模型的基本思想是估計文件與查詢相關聯概率，並對所有文件根據關聯概率進行排序。這一模型最早由Maron和Kuhn在1960年提出。^[11]在給定查詢 $Q$ 的情況下，用 $P(R|D)$ 表示文件與查詢相關的概率，而用 $P({\overline {R}}|D)$ 表示文件與查詢不相關的概率。那麼，就可以用

\log {\frac {P(R|D)}{P({\overline {R}}|D)}}

對文件進行排序。利用貝葉斯公式，可以很容易的將上面的公式變為產生式的形式：

\log {\frac {P(R|D)}{P({\overline {R}}|D)}}=\log {\frac {P(D|R)P(R)}{P(D|{\overline {R}})P({\overline {R}}}}

由於 $P(R)$ 和 $P({\overline {R}})$ 同文件無關，上面的公式可以最終表示為：

Sim(D,Q)=\log {\frac {P(D|R)}{P(D|{\overline {R}})}}

概率模型的主要任務就集中在估計 $P(D|R)$ 和 $P(D|{\overline {R}})$ 上。

推理網路模型[編輯]

推理網路模型是一種較上述兩中模型更為一般化的模型，上述模型都可以歸結為推理網路模型的一種實現。在此模型下，僅僅規定文件以某種「力度」產生某個來自查詢的關鍵詞，至於力度如何定義，則完全沒有規定，即可以是概率，也可以是關鍵詞權重。

倒排文件索引技術[編輯]

在資訊檢索系統的具體實現中，需要快速地找到文件中所包含的關鍵詞。相比文件來說，關鍵詞的個數是較少的，因此，以關鍵詞為核心對文件進行索引是更加可行的方法。這就是資訊檢索領域常用的「倒排文件索引」技術。倒排文件索引可以被看成一個鏈結串列陣列，每個鏈結串列的表頭包含關鍵詞，其後續單元則包括所有包括這個關鍵詞的文件標號，以及一些其他資訊。這些資訊可以是文件中該詞的頻率，也可以是文件中該詞的位置等資訊。

倒排文件索引的優勢不僅在於關鍵詞個數少帶來的檢索效率提高，還在於其特別易於同資訊檢索技術結合。在實際應用中，查詢中所包含的關鍵詞往往是很少的，完全不包含查詢中的所有關鍵詞的文件，一般來說是不會被列入結果集的。因此，以關鍵詞為主鍵進行索引，只需要用查詢中包括的關鍵詞，進行幾次簡單的查詢就能夠找出所有可能的文件。

倒排文件索引的具體資料結構可以進行進一步的最佳化。在關鍵詞查詢上，往往採用B-Tree或雜湊表進行快速查詢。而文件列表的資料結構則可以採用簡單的無序列表進行儲存，但是此種無序列表存在一個問題，就是當多個關鍵詞對應的文件集需要進行比較的時候，比較效率將比較低。因此，在實際應用中往往採用二元搜尋樹組織文件列表。

關鍵詞權重[編輯]

關鍵詞對於區分文件的作用是不同的。例如一些虛詞對於區分文件的內容與查詢是否相關並沒有多大的意義。

對於概率模型而言，可以有完備的理論來估計每篇文件生成某個詞的概率，因而其主要工作集中於如何確定較好的概率估計方法。而對於向量空間模型來說，確定關鍵詞權重在很大程度上依賴於研究者的經驗及對文件特性的分析。

目前，對關鍵詞權重的確定方法一般都需要取得一些關於關鍵詞的統計量，而後根據這些統計量，應用某種認為規定的計算公式來得到權重。最常用的統計量包括：

tf，Term Frequency的縮寫，表示某個關鍵詞在某個文件中出現的頻率。
qtf，Query Term Frequency的縮寫。表示查詢中某關鍵詞的出現頻率。
N，集合中的文件總數
df，Document Frequency的縮寫，表示文件集合中，出現某個關鍵詞的文件個數。
idf，Inversed Document Frequency的縮寫。 $\mathrm {idf_{i}} =\log {\frac {|D|}{|\{d:d\ni t_{i}\}|}}$
dl，文件長度
adl，平均文件長度

在向量空間模型下，構造關鍵詞權重計算公式有三個基本原則：

如果一個關鍵詞在某個文件中出現次數越多，那麼這個詞應該被認為越重要。
如果一個關鍵詞在越多的文件中出現，那麼這個詞區分文件的作用就越低，於是其重要性也應當相應降低。
一篇文件越長，那麼其出現某個關鍵詞的次數可能越高，而每個關鍵詞對這個文件的區分作用也越低，相應的應該對這些關鍵詞予以一定的折扣。

早期的權重往往直接採用tf，但是顯然這種權重並沒有考慮上述第二條原則，因此在大規模系統中是不適用的。目前，常用的關鍵詞權重計算公式大多基於tf和df進行構建，同時，一些較為複雜的計算公式也考慮了文件長度。現簡要列舉如下：

TF-IDF得分。嚴格地說，TF/IDF得分並不特指某個計算公式，而是一個計算公式集合。其中TF與IDF都可以進行各種變換，究竟何種變換較能符合實際需求，需要由實驗和應用來驗證。常見的變換方法有：

w_{t_{i}D}=tf\cdot idf

w_{t_{i}D}=\ln tf\cdot \ln idf

w_{t_{i}D}=tf\cdot \ln idf

其中，最後一個公式，即: $w_{t_{i}D}=tf\cdot \ln idf$ 被大量系統證明是最有效的。

此外，較為常用的關鍵詞權重演算法還包括Okapi權重^[12]和Pivoted Normalization 權重(PNW)^[13]。這些公式綜合考慮了查詢和文件中的詞頻，以及文件的長度。Okapi權重需要預設三個參數：

$k_{1}$ ，在1.0-2.0之間
$b$ ,通常為0.75
$k_{3}$ ,在0-1000之間

w_{t_{i}D,Q}=\sum _{t\in Q\cap D}\ln {\frac {N-df+0.5}{df+0.5}}\cdot {\frac {(k_{1}+1)tf}{(k_{1}(1-b)+b{\frac {dl}{avdl}})+tf}}\cdot {\frac {(k_{3}+1)qtf}{k_{3}+qtf}}

而PNW則需要預設一個參數 $s$ ，大部分情況下取0.20。

\sum _{t\in Q\cap D}{\frac {1+\ln(1+\ln(tf))}{(1-s)+s{\frac {dl}{avdl}}}}\cdot qtf\cdot \ln {\frac {N+1}{df}}

評價指標[編輯]

任何研究都需要有一個客觀的評價體系，資訊檢索系統也不例外。但是對於一項需要在實際生產生活中應用的系統，其評價導向又必須包含一定的主觀性。資訊檢索系統效能的兩個基本客觀指標是召回率(Recall Rate)和準確率(Precision Rate)，這與絕大多數的圖型識別技術相同。用 ${\mathcal {D}}$ 表示檢索系統所針對的檢索集合， $Q$ 表示一個查詢，而 ${\mathcal {R}}(Q)$ 表示查詢所返回的相關文件集， ${\mathcal {R}}^{\ast }(Q)$ 表示文件集中與查詢相關的所有文件。並定義算符 $|\cdot |$ 為集合中元素的個數，有召回率、準確率的定義如下：

recall={\frac {|{\mathcal {R}}(Q)\cap {\mathcal {R}}^{\ast }(Q)|}{|{\mathcal {R}}^{\ast }(Q)|}}

precision={\frac {|{\mathcal {R}}(Q)\cap {\mathcal {R}}^{\ast }(Q)|}{|{\mathcal {R}}(Q)|}}

由於資訊檢索系統返回的是一個排序的文件集合，因此召回率與準確率是互補的。設定不同的相關性得分門限就能夠得到相應的準確率與召回率。如果我們在以準確率為Y軸，召回率為X軸的圖上畫出不同門限下的準確率與召回率，一般它會程下面的形狀：

那麼，對於系統的評價指標就存在一個問題，如果一個系統偏重與給使用者最準確的結果，那麼高的準確率是必要的，反之，如果系統希望包括儘可能多的相關結果，又會偏好召回率。系統如果簡單的用召回率或準確率對系統效能作評價，無法評估系統的理想效能的。

圖型識別中常用F值作為效能的評價指標，其定義為

F={\frac {2\times recall\times precision}{recall+precision}}

F值可以平衡地反映召回率與準確率，但是在資訊檢索中仍然不是非常實用，因為它仍然是一個單點的指標，沒有反映全域特性。為了得到一個能夠反映全域效能的指標，可以看考察下圖，其中兩條曲線分布對應了兩個檢索系統的準確率-召回率曲線。

可以看出，雖然兩個系統的效能曲線有所交疊但是以圓點標示的系統的效能在絕大多數情況下要遠好於用方塊標示的系統。從中我們可以發現一點，如果一個系統的效能較好，其曲線應當儘可能的向上突出。更加具體的，曲線與坐標軸之間的面積應當越大。最理想的系統，其包含的面積應當是1，而所有系統的包含的面積都應當大於0。這就是用以評價資訊檢索系統的最常用效能指標，平均準確率(mean Average Precision, mAP)。其規範的定義是，設 $P(R)$ 為系統在召回率為R時的準確率，

mAP=\int _{0}^{1}P(R)dR

當然，一般在做評價時取得的準確率與召回率都是離散值，因此一般在計算時都採用求和而非積分。

mAP是一個較好的客觀評價指標，但是它也有一個缺陷，那就是缺乏直觀性。因此在系統評測時常常還是要附帶上準確率-召回率曲線。在實際應用中，還有一些單值評價指標，能夠反映系統的主觀效能。其中最常用的是N-Best準確率。一般系統的返回結果都採用分頁顯示，使用者一般不會翻看太多頁，因此前幾個結果在檢索中是最為重要的。N-Best準確率可以很好的反映這個效能。^[14]

參閱[編輯]

倒排索引

參考文獻[編輯]

^ V. Bush, 「As We May Think」, Atlantic Monthly, vol. 176, pp. 101–108, 1945
^ H.P. Luhn, 「A statistical approach to mechanized encoding and searching of literary information」,IBM Journal of Research and Development, vol. 1(4), pp. 309–317, 1957.
^ C.W. Cleverdon, 「The Cranfield tests on index language devices」, in Aslib Proceedings, vol. 19, pp. 173–192, 1967.
^ G. Salton, 「The SMART Retrieval System–Experiments in Automatic Document Retrieval」, Tech. Rep., Prentice Hall Inc., Englewood Cliffs, NJ, 1971.
^ ^5.0 ^5.1 G. Salton, A. Wong, and C.S. Yang, 「A vector space model for information retrieval」, Communications of the ACM, vol. 18(11), pp. 613–620, 1975.
^ G. Salton and C. Buckley, 「Term-weighting approaches in automatic text retrieval」, Information Processing and Management, vol. 24(5), pp. 513–523, 1988.
^ G. Salton and M. J. McGill, Introduction to Modern Information Retrieval, McGraw Hill Book Co., 1983.
^ S. Deerwester, S.T. Dumais, G.W. Furnas, T.K. Landauer, and R. Harshman, 「Indexing by latent semantic analysis」, Journal of the American Society for Information Science, vol. 41(6), pp. 391–407, 1999.
^ T. Hofmann, 「Probabilistic latent semantic indexing」, in Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pp. 50–57, 1999.
^ D. M. Blei, A. Y. Ng, and M. I. Jordan, 「Latent dirichlet allocation」, J. Mach. Learn. Res., vol. 3, pp. 993–1022, 2003.
^ M.E. Maron and J.L. Kuhns, 「On relevance, probabilistic indexing and information retrieval」,Journal of the ACM, vol. 7, pp. 216–244, 1960.
^ S. E. Robertson, S. Walker, and M. Beaulieu, 「Okapi at TREC7, automatic ad hoc, filtering, VLC and filtering tracks」, in Seventh Text REtrieval Conference (TREC-7), pp. 253–264, 1999.
^ A. Singhal, J. Choi, D. Hindle, D. Lewis, and F. Pereira, 「AT&T at TREC 7」, in Proceedings of the Seventh Text REtrieval Conference (TREC-7), vol. 500, pp. 239–252, 1999.
^ 高勤漢語語音文件檢索技術研究及系統實現北京大學碩士研究生學位論文存档副本 (PDF). [2008-12-30]. （原始內容 (PDF)存檔於2011-05-11）.

外部連結[編輯]

Google 檢索系統（頁面存檔備份，存於網際網路檔案館）
Lucene，Apache 基金會的開源文字資訊檢索系統（頁面存檔備份，存於網際網路檔案館）
ACM資訊檢索興趣小組（頁面存檔備份，存於網際網路檔案館）
資訊檢索評測 TREC （頁面存檔備份，存於網際網路檔案館）
中文資訊檢索論壇（頁面存檔備份，存於網際網路檔案館）

[1] V. Bush, 「As We May Think」, Atlantic Monthly, vol. 176, pp. 101–108, 1945

[2] H.P. Luhn, 「A statistical approach to mechanized encoding and searching of literary information」,IBM Journal of Research and Development, vol. 1(4), pp. 309–317, 1957.

[3] C.W. Cleverdon, 「The Cranfield tests on index language devices」, in Aslib Proceedings, vol. 19, pp. 173–192, 1967.

[4] G. Salton, 「The SMART Retrieval System–Experiments in Automatic Document Retrieval」, Tech. Rep., Prentice Hall Inc., Englewood Cliffs, NJ, 1971.

[g1-5] 5.0 ^5.1 G. Salton, A. Wong, and C.S. Yang, 「A vector space model for information retrieval」, Communications of the ACM, vol. 18(11), pp. 613–620, 1975.

[6] G. Salton and C. Buckley, 「Term-weighting approaches in automatic text retrieval」, Information Processing and Management, vol. 24(5), pp. 513–523, 1988.

[7] G. Salton and M. J. McGill, Introduction to Modern Information Retrieval, McGraw Hill Book Co., 1983.

[8] S. Deerwester, S.T. Dumais, G.W. Furnas, T.K. Landauer, and R. Harshman, 「Indexing by latent semantic analysis」, Journal of the American Society for Information Science, vol. 41(6), pp. 391–407, 1999.

[9] T. Hofmann, 「Probabilistic latent semantic indexing」, in Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pp. 50–57, 1999.

[10] D. M. Blei, A. Y. Ng, and M. I. Jordan, 「Latent dirichlet allocation」, J. Mach. Learn. Res., vol. 3, pp. 993–1022, 2003.

[11] M.E. Maron and J.L. Kuhns, 「On relevance, probabilistic indexing and information retrieval」,Journal of the ACM, vol. 7, pp. 216–244, 1960.

[12] S. E. Robertson, S. Walker, and M. Beaulieu, 「Okapi at TREC7, automatic ad hoc, filtering, VLC and filtering tracks」, in Seventh Text REtrieval Conference (TREC-7), pp. 253–264, 1999.

[13] A. Singhal, J. Choi, D. Hindle, D. Lewis, and F. Pereira, 「AT&T at TREC 7」, in Proceedings of the Seventh Text REtrieval Conference (TREC-7), vol. 500, pp. 239–252, 1999.

[14] 高勤漢語語音文件檢索技術研究及系統實現北京大學碩士研究生學位論文存档副本 (PDF). [2008-12-30]. （原始內容 (PDF)存檔於2011-05-11）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]