文字資訊檢索

文本信息檢索是針對文本的信息檢索技術。在技術社區中，文本信息檢索常常被等同於信息檢索技術本身。

相對視頻、音頻檢索而言，文本信息檢索是發展較快也較成熟的，其他模態的信息檢索技術，往往也要仰賴文本信息檢索的支持。

雖然網絡搜索引擎目前已不僅僅局限於對文本進行檢索，文本信息檢索仍然是大部分網絡搜索引擎的基礎。

歷史介紹

自人類的文字產生起，如何快速地從大量的，記錄在各種各樣的存儲媒體中尋找或獲取信息就成為一個引人注目的問題。這個問題關係到人類如何能夠主動地獲取自己需要的知識。因此，文本信息檢索技術甚至可以追述到古代的書籍編目。但是直到近一個世紀，隨着人類的知識以前所未有的速度急劇膨脹，信息存儲方式越來越豐富，使得在海量的，多模態的信息庫中進行快速、準確的檢索成為急迫的需求。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]