信息檢索概述

信息檢索是當(dāng)前應(yīng)用十分廣泛的一種技術(shù)，論文檢索、搜索引擎都屬于信息檢索的范疇。通常，人們把信息檢索問(wèn)題抽象為：在文檔集合D上，對(duì)于由關(guān)鍵詞w[1] ... w[k]組成的查詢(xún)串q，返回一個(gè)按查詢(xún)q和文檔d匹配度relevance(q, d)排序的相關(guān)文檔列表D'。

對(duì)于這一問(wèn)題，先后出現(xiàn)了布爾模型、向量模型等各種經(jīng)典的信息檢索模型，它們從不同的角度提出了自己的一套解決方案。布爾模型以集合的布爾運(yùn)算為基礎(chǔ)，查詢(xún)效率高，但模型過(guò)于簡(jiǎn)單，無(wú)法有效地對(duì)不同文檔進(jìn)行排序，查詢(xún)效果不佳。向量模型把文檔和查詢(xún)串都視為詞所構(gòu)成的多維向量，而文檔與查詢(xún)的相關(guān)性即對(duì)應(yīng)于向量間的夾角。不過(guò)，由于通常詞的數(shù)量巨大，向量維度非常高，而大量的維度都是0，計(jì)算向量夾角的效果并不好。另外，龐大的計(jì)算量也使得向量模型幾乎不具有在互聯(lián)網(wǎng)搜索引擎這樣海量數(shù)據(jù)集上實(shí)施的可行性。

tf-idf模型

目前，真正在搜索引擎等實(shí)際應(yīng)用中廣泛使用的是tf-idf模型。tf-idf模型的主要思想是：如果詞w在一篇文檔d中出現(xiàn)的頻率高，并且在其他文檔中很少出現(xiàn)，則認(rèn)為詞w具有很好的區(qū)分能力，適合用來(lái)把文章d和其他文章區(qū)分開(kāi)來(lái)。該模型主要包含了兩個(gè)因素：

1. 詞w在文檔d中的詞頻tf (Term Frequency)，即詞w在文檔d中出現(xiàn)次數(shù)count(w, d)和文檔d中總詞數(shù)size(d)的比值：

tf(w,d) = count(w, d) / size(d)

2. 詞w在整個(gè)文檔集合中的逆向文檔頻率idf (Inverse Document Frequency)，即文檔總數(shù)n與詞w所出現(xiàn)文件數(shù)docs(w, D)比值的對(duì)數(shù):

idf = log(n / docs(w, D))

tf-idf模型根據(jù)tf和idf為每一個(gè)文檔d和由關(guān)鍵詞w[1]...w[k]組成的查詢(xún)串q計(jì)算一個(gè)權(quán)值，用于表示查詢(xún)串q與文檔d的匹配度：

tf-idf(q, d)
= sum { i = 1..k | tf-idf(w[i], d) }
= sum { i = 1..k | tf(w[i], d) * idf(w[i]) }

信息檢索問(wèn)題的概率視角

直觀上看，tf描述的是文檔中詞出現(xiàn)的頻率；而idf是和詞出現(xiàn)文檔數(shù)相關(guān)的權(quán)重。我們比較容易定性地理解tf-idf的基本思想，但具體到tf-idf的一些細(xì)節(jié)卻并不是那么容易說(shuō)清楚為什么。比如：

1. 為什么tf是count(w, d) / size(d)？能不能是log(count(w, d) / size(d))等其他形式？

2. 為什么idf是一個(gè)log形式？

3. 為什么tf和idf之間是乘積關(guān)系，而不是加法或指數(shù)關(guān)系？

4. 為什么多個(gè)關(guān)鍵詞的tf-idf值是加法關(guān)系，而不是乘法或者指數(shù)關(guān)系？

5. 除了tf-idf值，Google還會(huì)計(jì)算網(wǎng)頁(yè)的PageRank值，二者相乘得到最后的權(quán)值，為什么是乘法，而不是加法或指數(shù)？

據(jù)說(shuō)，最初甚至tf-idf的提出者自己也沒(méi)有對(duì)諸如“為什么idf是log形式”這個(gè)問(wèn)題給出有力的解釋?zhuān)m然后來(lái)有人從信息論的角度對(duì)idf的log形式給出了令人信服的解釋?zhuān)鞘Ｏ碌钠渌恍┮蓡?wèn)仍然存在。在我了解的范圍內(nèi)，對(duì)于tf-idf模型還沒(méi)有一個(gè)真正統(tǒng)一完整的理論解釋。在試圖為tf-idf找到更好的理論解釋的過(guò)程中，我意識(shí)到對(duì)tf-idf模型種種疑問(wèn)的根源在于tf-idf試圖表達(dá)的“查詢(xún)q和文檔的匹配度”本身就有一定的模糊性，什么叫做“匹配度”，這就有很大的自由發(fā)揮空間。如果說(shuō)向量模型的用向量夾角來(lái)表示匹配度概念還有一定的理論基礎(chǔ)，那么用tf-idf來(lái)表達(dá)匹配度就有點(diǎn)“與其說(shuō)是科學(xué)，不如說(shuō)是藝術(shù)”的味道。

更進(jìn)一步，其實(shí)，信息檢索問(wèn)題的抽象方式“在文檔集合D上，對(duì)于給定查詢(xún)串q，返回一個(gè)按查詢(xún)q和文檔d匹配度relevance(q, d)排序的相關(guān)文檔列表D'”本身是值得反思的。我們應(yīng)當(dāng)考慮拋棄“匹配度”這種模糊的目標(biāo)，從根源上尋求一種具有明確數(shù)學(xué)意義的目標(biāo)。如果我們從概率視角來(lái)看，把“查詢(xún)串q和文檔d的匹配度”問(wèn)題轉(zhuǎn)換為“當(dāng)查詢(xún)串是q時(shí)，用戶(hù)期望獲得文檔d的概率”問(wèn)題，信息檢索問(wèn)題就清晰多了。一方面這個(gè)概率描述是站在人的角度來(lái)看待信息檢索問(wèn)題的，更加貼近實(shí)際的用戶(hù)體驗(yàn)；另一方面，概率本身是有明確數(shù)學(xué)意義的，這樣我們就首先從目標(biāo)上對(duì)問(wèn)題進(jìn)行了嚴(yán)格化。

下面，我將通過(guò)一個(gè)模型，從概率的視角，一邊解釋tf-idf的概率意義，一邊指出其不合理之處。

盒子小球模型
為了分析“當(dāng)查詢(xún)串是q時(shí)，用戶(hù)期望獲得文檔d的概率”問(wèn)題，我首先建立了一種稱(chēng)為“盒子小球模型”的簡(jiǎn)化模型。盒子小球模型把詞想象成各種不同顏色的小球，文檔想象成裝有若干小球的盒子，把“當(dāng)查詢(xún)串是q時(shí)，用戶(hù)期望獲得文檔d的概率“轉(zhuǎn)換為下面的問(wèn)題：

有n個(gè)盒子d[1], d[2], ... d[n]，每個(gè)盒子中有若干不同顏色的小球，有人隨機(jī)地選擇了一個(gè)盒子，并從盒子中隨機(jī)地拿出了一個(gè)顏色為w[j]的小球，那么這個(gè)小球來(lái)自于盒子d[i]的概率是多少？

其實(shí)，這就是經(jīng)典的條件概率問(wèn)題P(d[i] | w[j])，采用貝葉斯推斷將其轉(zhuǎn)化為：

P(d[i] | w[j])
= P(d[i], w[j]) / P(w[j])
= P(d[i]) * P(w[j] | d[i]) / P(w[j])

我們注意到這個(gè)條件概率包括幾個(gè)部分，P(d[i])是盒子d[i]被選中的先驗(yàn)概率，p(w[j])是w[j]顏色小球被選中的先驗(yàn)概率，P(w[j] | d[i])是在盒子d[i]中選中顏色w[j]小球的條件概率。

文檔先驗(yàn)概率P(d)與PageRank

首先，我們來(lái)看盒子d[i]被選中的先驗(yàn)概率P(d[i])是什么。P(d[i])的意義是：當(dāng)用戶(hù)什么也沒(méi)有輸入的時(shí)候，它可能對(duì)文檔d[i]感興趣的概率。在沒(méi)有更多信息的情況下，我們可以認(rèn)為每個(gè)盒子被選中的先驗(yàn)概率P(d[i])是相等的，都等于1 / m，其中m表示總文檔數(shù)（總盒子數(shù)），這時(shí)P(d[i])作為公共系數(shù)可被忽略。不過(guò)，在實(shí)際應(yīng)用中，我們通?？梢愿鶕?jù)其他知識(shí)獲得各文檔的先驗(yàn)概率，比如，學(xué)術(shù)文獻(xiàn)和網(wǎng)頁(yè)通常可以基于引用度模型計(jì)算其先驗(yàn)概率，這些經(jīng)典論文和熱門(mén)網(wǎng)頁(yè)是多數(shù)人樂(lè)于見(jiàn)到的。說(shuō)到這里，你可能已經(jīng)發(fā)現(xiàn)，Google PageRank本質(zhì)上就是這個(gè)先驗(yàn)概率P(d[i])乘以某個(gè)系數(shù)！所以，PageRank實(shí)際上也被納入這個(gè)條件概率模型中來(lái)了，這就不難解釋為什么在Google的排序算法中PageRank權(quán)重和tf-idf權(quán)重是一種乘積關(guān)系而不是加或者指數(shù)關(guān)系。另一方面，在理解了文檔先驗(yàn)概率對(duì)整個(gè)搜索結(jié)果概率的影響后，當(dāng)搜索引擎中針對(duì)PageRank出現(xiàn)各種假鏈接SEO時(shí)，我們可以不拘泥于基于鏈接引用模型的PageRank，只要是以網(wǎng)頁(yè)先驗(yàn)概率為目標(biāo)，不論是采用基于鏈接引用的PageRank，還是基于搜索結(jié)果點(diǎn)擊數(shù)模型，或是其他模型，都是可以的。這就是“變通”，從原理上“通”了，就可以在方法上“變”。

詞的先驗(yàn)概率P(w)

下面我們來(lái)考察詞w[j]的先驗(yàn)概率P(w[j])。P(w[j])的意義是：在整個(gè)文檔集合中，w[j]被作為搜索關(guān)鍵詞的概率，比如：“iPhone 5”，“青花瓷”這類(lèi)詞被用作搜索關(guān)鍵詞的概率較高，而“的”，“什么”，“我們”這類(lèi)高頻詞不大可能成為搜索關(guān)鍵詞。那么，我們?nèi)绾蝸?lái)定量計(jì)算P(w[j])呢？一種思路就是把w[j]在文檔集中出現(xiàn)的頻率作為其先驗(yàn)概率。不過(guò)，顯然存在更好的方案：在大量的搜索查詢(xún)中進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)方法得出P(w[j])的方法很接近P(w[j])本質(zhì)的，不需要引入額外的假設(shè)。比如，一段時(shí)間內(nèi)某搜索引擎的搜索總次數(shù)為10^10次，“公積金”這個(gè)詞出現(xiàn)了100次，那么，我們可以認(rèn)為先驗(yàn)概率P("公積金")就是100 / 10^10 = 10^-8。

詞代表文檔主題的條件概率P(w | d)

最后，我們來(lái)看條件概率P(w[j] | d[i])。P(w[j] | d[i])的意義是在文檔d[i]中，人們用關(guān)鍵詞w[j]來(lái)搜索它的概率。那么，什么樣的詞是人們會(huì)用來(lái)搜索一篇文檔的呢？多數(shù)情況下，是那些代表一篇文檔主題的詞。比如，有一篇新聞是關(guān)于iPhone 5發(fā)布會(huì)的，那么“iPhone5”， “發(fā)布會(huì)”，“庫(kù)克”，“蘋(píng)果”這些詞基本上就構(gòu)成了文章的主題；那么，反過(guò)來(lái)說(shuō)，如果用戶(hù)想搜索這篇關(guān)于iPhone 5發(fā)布會(huì)的新聞，他就有很大的可能通過(guò)這幾個(gè)詞來(lái)進(jìn)行搜索。我們應(yīng)當(dāng)注意分辨P(w[j] | d[i])與P(w[j])的區(qū)別，后者可以通過(guò)大量的查詢(xún)統(tǒng)計(jì)得來(lái)，而前者不能與后者直接劃等號(hào)，因?yàn)榍罢叩囊饬x是w[j]代表d[i]主題的概率。如果非要引入統(tǒng)計(jì)方法，那么P(w[j] | d[i])對(duì)應(yīng)的統(tǒng)計(jì)是：當(dāng)搜索關(guān)鍵詞是w[j]且搜索結(jié)果包含d[i]時(shí)，用戶(hù)點(diǎn)擊（滿(mǎn)意）d[i]作為搜索結(jié)果的頻率。比如，用“iPhone5 發(fā)布會(huì)”的搜索，在結(jié)果中有都10000次出現(xiàn)了網(wǎng)頁(yè)x，其中，用戶(hù)8000次點(diǎn)擊了網(wǎng)頁(yè)x，那么，可以認(rèn)為有80%的概率網(wǎng)頁(yè)x的主題是關(guān)于“iPhone5 發(fā)布會(huì)”的。

詞的信息量和idf

上面談到了對(duì)P(w[j] | d[i])的計(jì)算的統(tǒng)計(jì)方法，但該方法有一定的局限，比如，要能進(jìn)行統(tǒng)計(jì)首先需要文檔出現(xiàn)在足夠多的搜索結(jié)果中，需要時(shí)間和量的積累。除了統(tǒng)計(jì)方法外，我們可以考慮其他方法計(jì)算詞w[j]代表文檔d[i]主題的概率。可能有人立刻會(huì)想到要對(duì)文章進(jìn)行語(yǔ)義分析提取關(guān)鍵詞，給這些關(guān)鍵詞高權(quán)重，給其他詞低權(quán)重。這種想法有一定的合理性，但實(shí)現(xiàn)上涉及語(yǔ)義分析，沒(méi)有成熟高效的方法。實(shí)際上，信息論為我們提供了另一條高效方案。上面談到“的”，“什么”，“我們”這類(lèi)高頻詞不會(huì)成為文檔主題和搜索關(guān)鍵詞的原因是它們不能提供足夠的信息，而“iPhone 5”，“發(fā)布會(huì)”這樣的詞匯則信息量豐富。所謂信息是指對(duì)不確定性（熵）的減小程度，信息的單位是比特(bit)，信息量越大對(duì)于不確定性的減小程度越大。比如，外面可能在下雨也可能沒(méi)有下雨，可能性空間大小為2，如果我們看一眼窗外，可能性空間就變成了1，那么“看見(jiàn)窗外在下雨”所提供的信息量就和熵的減小程度成正比，具體來(lái)講等于log(2/1)=1。如果要用二進(jìn)制編碼是否下雨，需要1個(gè)bit，0代表沒(méi)有下雨，1代表下雨。

但在很多場(chǎng)景下，各個(gè)可能性的概率并不相同，比如：歐洲杯16只球隊(duì)都可能奪冠，賽前它們奪冠的先驗(yàn)概率并不相同，那么結(jié)果的不確定性程度實(shí)際上是小于log(16)=4。如果你沒(méi)有看比賽，有人告訴你西班牙奪冠了，你可能會(huì)覺(jué)得很正常，但如果有人告訴你瑞士奪冠了，你通常會(huì)非常驚訝。這一現(xiàn)象的理論解釋是，如果賽前西班牙奪冠概率是1/4，而瑞士奪冠概率是1/32，那么，“西班牙奪冠”的信息量為log(4)=2，即把不確定性減小為原來(lái)的1/4，而“瑞士奪冠”的信息量為log(32)=5，不確定性減小為原來(lái)的1/32，一下子接受比前者大了兩倍以上的信息量，當(dāng)然你會(huì)吃驚。

回到信息檢索，比如，“2012美國(guó)大選”這個(gè)查詢(xún)串包含了“2012”，“美國(guó)”和“大選”3個(gè)關(guān)鍵詞，我們應(yīng)該如何定量計(jì)算它們的信息量呢？根據(jù)信息的定義，詞的信息量等于它對(duì)不確定性的縮小程度。如果文檔總數(shù)為2^{30，其中2}14篇文檔出現(xiàn)了“美國(guó)”，那么“美國(guó)”這個(gè)詞就把文檔的不確定性從2^30縮小為214，它所包含的信息量為log(2^30/214)=16；而只有2^{10篇文檔出現(xiàn)了“大選”，那么大選的信息量就是log(2}30/2^10)=20，比“美國(guó)”多了4個(gè)bit。而“的”，“什么”，“我們”這些高頻詞對(duì)減小文檔不確定性幾乎沒(méi)有幫助，因而信息量為0。相信你已經(jīng)發(fā)現(xiàn)，上面idf(w)公式中的log(n / docs(w, D))實(shí)際上就是詞w的信息量了。

如果我們考慮詞的信息量對(duì)條件概率P(w[j] | d[i])的影響，假設(shè)“詞w在文檔中被選中的概率與其在文檔中的出現(xiàn)頻率和其信息量的乘積成正比”，那么上面的條件概率模型就變成：

P(d[i] | w[j])
= P(d[i], w[j]) / P(w[j])
= P(d[i]) * P(w[j] | d[i]) / P(w[j])
= P(d[i]) * (tf(w[j], d[i]) * idf(w[j] / sum { k = 1..size(d[i]), tf(w[k], d[i]) * idf(w[k]) }) / p(w[j])
= P(d[i]) * (tf-idf(w[j], d[i]) / sum { k = 1..size(d[i]), tf-idf(w[k], d[i]) }) / p(w[j])
= P(d[i]) * (tf-idf(w[j], d[i]) / tf-idf(d[i])) / p(w[j])

我們看到tf-idf已經(jīng)被納入框架內(nèi)了，但是還多出文檔先驗(yàn)概率P(d[i])，關(guān)鍵詞先驗(yàn)概率P(w[j])和文檔各詞的總tf-idf(d[i])。普通搜索引擎是基于PageRank和tf-idf的，那么，根據(jù)這個(gè)概率模型，我們可以看出，它沒(méi)有考慮文檔總tf-idf(d[i])和關(guān)鍵詞先驗(yàn)概率p(w[j])。如果考慮這兩個(gè)因素，相信搜索效果會(huì)更好。

多關(guān)鍵詞
上面的條件概率模型主要是針對(duì)單個(gè)關(guān)鍵詞的情況，下面我們進(jìn)一步將其擴(kuò)展到多關(guān)鍵詞情況。我們知道，在tf-idf中，多個(gè)關(guān)鍵詞的所產(chǎn)生的tf-idf值是一種疊加關(guān)系，那么這是否符合條件概率模型呢？答案是否定的。在兩個(gè)關(guān)鍵字情況下，條件概率問(wèn)題轉(zhuǎn)化為“如果有人從一個(gè)盒子中同時(shí)摸出顏色w[x]的小球和顏色w[y]的小球，這兩個(gè)小球來(lái)自于盒子d[i]的概率是多少？”。假設(shè)從盒子中摸出各個(gè)小球事件是相互獨(dú)立的情況下，即

P(w[x], w[y]) = P(w[x]) * P(w[y])
P(w[x], w[y] | d[i]) = P(w[x] | d[i]) * P(w[y] | d[i])

我們可以推導(dǎo)出條件概率：

P(d[i] | w[x], w[y])
= P(d[i], w[x], w[y]) / P(w[x], w[y])
= P(d[i]) * P(w[x], w[y] | d[i]) / P(w[x], w[y])
= P(d[i]) * P(w[x] | d[i]) * P(w[y] | d[i]) / (P(w[x] * P(w[y]))
= P(d[i]) * (tf-idf(w[x], d[i]) / tf-idf(d[i])) * ((tf-idf(w[y], d[i]) / tf-idf(d[i]))) / (p(w[x]) * P(w[y]))

可見(jiàn)，概率模型所得出的各個(gè)關(guān)鍵詞的tf-idf值之間是乘積關(guān)系，這是與tf-idf模型的加法關(guān)系是不同的。這一點(diǎn)可能與二者是否要求“文檔必須包含所有查詢(xún)關(guān)鍵詞”的基本假設(shè)有關(guān)系。在文檔不包含所有關(guān)鍵字的這種情況下，tf-idf模型可能得出一個(gè)非0的匹配度，但條件概率模型得出的概率肯定為0。不過(guò)，如果考慮一般查詢(xún)關(guān)鍵詞數(shù)量不多（3個(gè)以?xún)?nèi)），而大量文檔都同時(shí)包含這些關(guān)鍵詞，概率模型的乘積關(guān)系是比tf-idf模型的加法關(guān)系更有理論基礎(chǔ)。從根本上講，這是因?yàn)閠f-idf的“匹配度”是一個(gè)模棱兩可的概念，而條件概率有堅(jiān)實(shí)的理論基礎(chǔ)。

總結(jié)
TF-IDF模型是搜索引擎中廣泛使用的信息檢索模型，但對(duì)于TF-IDF模型一直存在各種疑問(wèn)。本文為信息檢索問(wèn)題一種基于條件概率的盒子小球模型，其核心思想是把“查詢(xún)串q和文檔d的匹配度問(wèn)題”轉(zhuǎn)化為“查詢(xún)串q來(lái)自于文檔d的條件概率問(wèn)題”。它從概率的視角為信息檢索問(wèn)題定義了比TF-IDF模型所表達(dá)的匹配度更為清晰的目標(biāo)。從概率模型中，我們看到查詢(xún)串q來(lái)自于文檔d的條件概率主要包含以下幾個(gè)因素：1) 文檔的先驗(yàn)概率P(d[i])，這與PageRank對(duì)應(yīng)；2) 詞w被作為搜索關(guān)鍵詞的先驗(yàn)概率P(w)，這可以通過(guò)統(tǒng)計(jì)方法獲得；3) 關(guān)鍵詞w代表文檔d主題，或以詞w搜索文檔d的概率，P(w | d)，除了統(tǒng)計(jì)方法，這可以通過(guò)tf-idf來(lái)計(jì)算。