tf-idf：Term frequency–inverse document frequency，詞頻與反文檔頻率。是搜尋引擎中常見的基本算法。這裡我們用資訊論的角度來解析這個算法。
資訊檢索中,比較常見的就是通過幾個詞條搜尋相應頁面；或者寫一篇blog，提取幾個關鍵詞作為别人搜尋的索引。
也就是兩個基本情況：提出一個詞條，得到一個文檔；一個文檔，對于文檔中的詞進行重要度排序。
這裡都涉及到一個概念：詞條權值度量。
詞條權值與資訊檢索
詞條權值度量在資訊檢索中有比較大的用途。通常我們需要一種方法來定量地度量某個詞條的權值。
常見于如下運用：
1. 根據詞條檢索文檔：也就是衡量一個詞條在一個文檔中的權值
2. 摘要詞條抽取：根據文檔中的不同詞的權值，提取出權值最大的一個詞條
3. 特征子集抽取：提取子特征。
通常用來衡量詞條權值的方法有：chi方，互資訊，Dice系數，似然率，Jaccard相似性度量等，交叉熵，資訊增益等等。
傳統的度量方法是基于共同發生頻率的。這裡的共同發生頻率指的是兩個方面：一個是某個詞條在不同的文檔中的頻率，另一個是不同的詞條在同一個文檔中的頻率。而tf-idf以及其變種都是基于這種方式的。
方法分類：
一種分類方法是根據不同的資料模型來分類：
a)基于頻率的數學模型：基于這樣一個假設：出現頻率高的詞條就更重要。
b)基于特殊性的數學模型：這種方法量化了随機詞條到某個詞條的偏差。這種方法包括基于互資訊的方法，基于信噪比的方法，以及idf.
c)基于特定鑒别函數的方法：這種方法基于特定的鑒别函數，衡量特定條件下的鑒别能力。常見的有資訊增益法，相關權重法。
d)基于表達的方法：結合了詞頻與反文檔資訊量，也就是tf-idf以及其變種方法。
小結：基于頻率的方法過于突出高頻詞彙，而基于資訊的方法又過于突出低頻詞彙，我們需要在這兩種方法上需找一個平衡。那麼基于鑒别函數的方法與基于表達的方法以不同方式完成了這種平衡。
通過下面一個例子來比較c與d的差別:如果某個詞在其他所有的文檔中都出現了，而在一篇文檔中沒有出現，那麼這個詞對于鑒别這篇文檔與其他文檔就很有用處，而對于其他文檔之間的鑒别沒有意義。然而，如果是基于表達的方法，那麼這個詞也是沒有用處的。
如下表格是這四種方法的對比與運用。
互資訊與KL距離
上面介紹了詞條權值度量的一些方法和分類。下面就其中的一種度量方法讨論：資訊熵。
假設兩個随機變量X，Y，他們不是獨立的。通過觀察X，我們能夠得到關于Y的一些資訊。同樣的，通過觀察Y，我們能夠得到關于X的一些資訊。
比如下雨和打傘兩個事件，我們通過路人打傘，可以推斷可能下雨。通過下雨，也可以推斷路人會打傘。
用資訊論的理論來解釋就是，已知X，Y的不确定降低了。定量地衡量就是P（Y|X）與P（Y）之間的KL距離。
除此之外，我們還可以有另一種了解：
還是下雨打傘兩個事件，我們可以構造P（X,Y），然後計算兩個事件的聯合機率P（xi,yj）,再計算P（xi,yj）的資訊熵，來衡量這兩個時間同時發生的資訊量。
也就是Xi，Yj的互資訊I（Xi，Yj）
最後，我們可以根據條件機率公式：P（X,Y）=P（Y|X）P(X)=P(X|Y)P(Y),把上面兩種度量KL，互資訊結合起來：
根據上面的公式推理，我們可以得到如下結論：
已知X，得到關于Y的資訊越少，P（Y|X）與P(Y)之間的KL距離越小，X,Y之間的互資訊也就越小。
（關于KL與互資訊，具體可見blog：
http://blog.csdn.net/ice110956/article/details/17120461）
最後，我們得到了以互資訊，或者KL距離來衡量權值的資訊論方法。
機率架構
有了上面的資訊論知識，我們再來看文字檢索的問題。
通過上面的叙述，我們可以通過互資訊來定量的進行資訊檢索。
如第一部分的論述，資訊檢索中的兩個基本情況是：提出一個詞條，得到一個文檔；一個文檔，對于文檔中的詞進行重要度排序。
這兩個問題，歸結起來都是關于詞條的權值計算，用資訊論的度量方法就是度量詞條與文檔的互資訊。
直覺上，我們有兩種可行的機率架構假設：
1. 每個文本都是由Ni個獨立随機變量，也就是詞組合而成的，這裡把文檔中的每個詞作為一個随機變量。同時，每個提出的詞條也是一個随機變量。
2. 文本是一個随機變量D，每個文本都是D的一個樣本，這裡把每個文本看成一個整體。同時，每一個提出的詞條還是一個随機變量。
根據方法1，我們有貝葉斯方法。
根據方法2，就有我們如下的tf-idf。
我們現在根據第二種機率架構：
假設有一個文本集合D，D包含了許多文本{d1,d2….dn},一個關鍵字集合W，W包含所有可能的查詢{w1,w2…wm}.這樣，D，W都被描述成一個随機變量，di,wi則為其中的樣本。
上圖中，把資訊檢索抽象為一個機率模型.
進一步的,如上一部分所述，我們可以有這樣兩種了解：
1. 與之前的天氣穿着類似，這裡我們已知詞條P（W）,以及P（D|W）.我們用P（D|W）來近似P（D）。
2. 另一種了解就是，我們計算得到聯合機率P（wi,dj），也就是提出詞條wi，得到文檔dj這個事件發生的機率。再通過這個機率模型來推導出相應的資訊量。
就像我們前一部分關于下雨打傘的兩個了解,最後都可以統一到一起.
我們先引出如下一個概念：
PWI：probability-weighted amount of information (PWI).資訊機率權值。
(1)
其為兩個事件同時發生的聯合資訊，也就是廣義上的互資訊，I（wi，dj）.
我們用PWI來作為互資訊與KL距離的一個統一的表達方法，其本質也就是互資訊。
我們根據PWI的定義，能夠繼續推導如下公式：
(2)
(3)
公式(1)可以用于衡量某個詞條與不同文檔之間的權重。
公式(2)可以用于衡量某個詞條對于所有文檔的權重，排序後可以得到關鍵詞條。
公式(3)可以用于衡量某個文檔對于所有詞條的權重。
後面的部分将會具體說明。
基于頻率的機率模型：
上面，我們根據整體架構，得到了基于PWI（互資訊）的方法架構。這時，隻要我們提出合理的D和W的具體機率分布，加到上述的公式中，我們就能計算基于互資訊的詞條權重了。
從直覺了解得出機率模型：
這裡的直覺的了解也就是頻率。通常來說，我們會覺得出現頻率高的更重要。于是這裡我們基于頻率，得到他們的機率模型如下：
我們首先列出以下要用的一些變量：
D：文檔随機變量D。
P（D）：D的分布。
W：詞條随機變量W。
P（W）：W的分布。
P（D|W）：已知W,D的條件分布。
P（wi,dj）：提出詞條wi,得到dj的機率。
F：所有文檔相加的總次數。
Fij:詞條i在文檔j中出現的頻率。
Fwi:詞條wi在所有文檔中的總頻率。
Fdj:單個文檔dj中的詞數。
基于頻率的機率模型：
我們假設詞條wi提出的頻率等于其出現的頻率：
P（Wi）=Fwi/F
每個文檔的出現機率與其包含詞數成正比：
P（dj）=Fdj/F
提出wi以後，每個文檔被取出的機率，也等于其包含wi頻率比例：
P（dj|wi）=Fij/Fwi
Wi和dj同時發生的機率等于dj包含詞條wi的頻率：
P（wi，dj）=P(wi)*P(dj|wi)=Fwi/F*Fij/Fwi=Fij/F
H表示資訊熵,I表示互資訊,KL表示KL距離．
于是，再帶入之前的資訊論模型，得到：
熵:
KL距離:
PWI(互資訊):
(1)
(2)
最後，根據互資訊之間的關系，我們有這樣一幅圖：
中間為I（wi，di）,橫向求和得到I（W,dj）;縱向求和得到I（wi,D）.雙向求和得到I（W,D）。
觀察公式（1）（2），我們能夠得到如下直覺結論：
(1) I（wi，dj）表征一個詞條與一個文檔之間的PWI，觀察公式得到，他與FijilogFiji成正比，與logFwiFdj成反比。也就是文檔中詞條頻率越大，權值越高；文檔字數越少，權值越高；詞條總的詞數越少（也就是在其他文檔中總的出現詞數），權值越高。
借用tf-idf的思維，Fiji/F為其tf（詞條頻率項），
為其idf(反文檔頻率項)
(2) I（wi，D）表征一個詞條對于整個文檔的權值，可以用于整體文檔的關鍵字提取。不過上式計算比較麻煩。在下面的近似模型中能夠得到近似簡化。
Tf-idf的近似機率模型
Tf-idf是基于經驗的模型，甚至他的提出者都不能清楚地說明其理論依據。上面關于資訊角度的模型分析，也是後來的人們分析得出的。其中關于基于頻率的機率模型，也與一開始的tf-idf不同。
我們稱上面的模型為準确模型，tf-idf的模型為近似模型。
之是以稱tf-idf為近似模型，因為其根據實際運用，在機率模組化的時候，做了如下的近似：
當每個文檔中詞數要求不嚴格，或者每個文檔都有相似的個數時，我們可以通過1式來近似。
當每個文檔的詞數相近時，或者對于文檔個數不要求時，我們也可以通過2式來近似。
上面的近似，也就是通過布爾值來代替頻率，不過假設的部分僅限于idf ，即反文檔頻率部分（log部分）。
這樣，就得到了基于如上假設的tf-idf模型。
Tf-idf最後得到的公式如下：
觀察上面的公式，其分為兩個部分，頻率部分tf，以及後面的log，反文檔部分。
第一部分與發生頻率成正比，第二部分與相關文檔數成反比。
準确的機率模型與tf-idf機率模型，根據不同的運用場景有着不同的用途，也有不同的效果。
詞條序列模型：
上面的算法都是基于單一詞條的模型，而我們一般的搜尋都是基于一個詞條序列的搜尋。
關于詞條序列的搜尋，我們一般有兩種假設模型：
1. k個詞條為獨立同分布，這個分布由所有文檔決定，也就是我們之前的假設。
2. 每個文檔決定了其包含詞條一個分布，并且我們假設所有k個詞條選至文檔集中的某個文檔。
這兩種假設如何解釋呢？
前者我們假設k個詞條都是獨立同分布的，由所有文檔共同生成。也就是已知P（dj|wi）和P（W）。這種方法就直接把之前的單個詞條PWI相加即可。
後者我們假設k個詞條全部取自一個文檔，即P（wi/dj），P(D)已知，再來求PWI。這也就是貝葉斯的方法。
其公式分别為：
根據第一個模型建立的，也就是向量空間的方法。
根據第二個模型建立的，也就是貝葉斯方法。
通過機率模型，我們也把這兩種方法所涉及的理論聯系到了一起。
參考文獻：An information-theoretic perspective of tf–idf measures
http://comminfo.rutgers.edu/~muresan/IR/Docs/Articles/ipmAizawa2003.pdf