從本週開始我們進入人工智能核心技術模塊，本週我會集中講解經典的搜索核心算法，今天先來介紹 TF-IDF 算法。
在信息檢索（Information Retrieval）、文本挖掘（Text Mining）以及自然語言處理（Natural Language Processing）領域，TF-IDF 算法都可以說是鼎鼎有名。雖然在這些領域中，目前也出現了不少以深度學習為基礎的新的文本表達和算分（Weighting）方法，但是 TF-IDF 作為一個最基礎的方法，依然在很多應用中發揮著不可替代的作用。
瞭解和掌握 TF-IDF 算法對初學者大有裨益，能夠幫助初學者更快地理解其它更加深入、複雜的文本挖掘算法和模型。今天我就來談談 TF-IDF 的歷史、算法本身的細節以及基於 TF-IDF 的幾個變種算法。
TF-IDF 的歷史
把查詢關鍵字（Query）和文檔（Document）都轉換成“向量”，並且嘗試用線性代數等數學工具來解決信息檢索問題，這樣的努力至少可以追溯到 20 世紀 70 年代。
1971 年，美國康奈爾大學教授傑拉德·索爾頓（Gerard Salton）發表了《SMART 檢索系統：自動文檔處理實驗》（The SMART Retrieval System—Experiments in Automatic Document Processing）一文，文中首次提到了把查詢關鍵字和文檔都轉換成“向量”，並且給這些向量中的元素賦予不同的值。這篇論文中描述的 SMART 檢索系統，特別是其中對 TF-IDF 及其變種的描述成了後續很多工業級系統的重要參考。
1972 年，英國的計算機科學家卡倫·瓊斯（Karen Spärck Jones）在《從統計的觀點看詞的特殊性及其在文檔檢索中的應用》（A Statistical Interpretation of Term Specificity and Its Application in Retrieval） 一文中第一次詳細地闡述了 IDF 的應用。其後卡倫又在《檢索目錄中的詞賦值權重》（Index Term Weighting）一文中對 TF 和 IDF 的結合進行了論述。可以說，卡倫是第一位從理論上對 TF-IDF 進行完整論證的計算機科學家，因此後世也有很多人把 TF-IDF 的發明歸結於卡倫。
傑拉德本人被認為是“信息檢索之父”。他 1927 年出生於德國的紐倫堡，並與 1950 年和 1952 年先後從紐約的布魯克林學院獲得數學學士和碩士學位，1958 年從哈佛大學獲得應用數學博士學位，之後來到康奈爾大學參與組建計算機系。為了致敬傑拉德本人對現代信息檢索技術的卓越貢獻，現在，美國計算機協會 ACM（Association of Computing Machinery）每三年頒發一次“傑拉德·索爾頓獎”（Gerard Salton Award），用於表彰對信息檢索技術有突出貢獻的研究人員。卡倫·瓊斯在 1988 年獲得了第二屆“傑拉德·索爾頓獎”的殊榮。
TF-IDF 算法詳解
要理解 TF-IDF 算法，第一個步驟是理解 TF-IDF 的應用背景。TF-IDF 來源於一個最經典、也是最古老的信息檢索模型，即“向量空間模型”（Vector Space Model）。
簡單來說，向量空間模型就是希望把查詢關鍵字和文檔都表達成向量，然後利用向量之間的運算來進一步表達向量間的關係。比如，一個比較常用的運算就是計算查詢關鍵字所對應的向量和文檔所對應的向量之間的“相關度”。
因為有了向量的表達，相關度往往可以用向量在某種意義上的“相似度”來進行近似，比如餘弦相似性（Cosine Similarity）或者是點積（Dot Product）。這樣，相關度就可以用一個值來進行表達。不管是餘弦相似度還是點積都能夠從線性代數或者幾何的角度來解釋計算的合理性。
在最基本的向量空間模型的表達中，查詢關鍵字或是文檔的向量都有 V 維度。這裡的 V 是整個詞彙表（Vocabulary）的總長度。比如，我們如果有 1 萬個常用的英文單詞，那麼這個 V 的取值就是 1 萬，而查詢關鍵字和每個文檔的向量都是一個 1 萬維的向量。 對於這個向量中的每一個維度，都表示英文中的一個單詞，沒有重複。
你可以看到，在這樣的情況下，如果當前的詞出現在這個向量所對應的文檔或者關鍵字裡，就用 1 來表達；如果這個詞沒出現，就用 0 來表達。這就是給每個維度賦值（Weighting）的最簡單的方法。
TF-IDF 就是在向量空間模型的假設下的一種更加複雜的賦值方式。TF-IDF 最基礎的模式，顧名思義，就是 TF 和 IDF 的乘積。
TF 其實是“單詞頻率”（Term Frequency）的簡稱。意思就是說，我們計算一個查詢關鍵字中某一個單詞在目標文檔中出現的次數。舉例說來，如果我們要查詢“Car Insurance”，那麼對於每一個文檔，我們都計算“Car”這個單詞在其中出現了多少次，“Insurance”這個單詞在其中出現了多少次。這個就是 TF 的計算方法。
TF 背後的隱含的假設是，查詢關鍵字中的單詞應該相對於其他單詞更加重要，而文檔的重要程度，也就是相關度，與單詞在文檔中出現的次數成正比。比如，“Car”這個單詞在文檔 A 裡出現了 5 次，而在文檔 B 裡出現了 20 次，那麼 TF 計算就認為文檔 B 可能更相關。
然而，信息檢索工作者很快就發現，僅有 TF 不能比較完整地描述文檔的相關度。因為語言的因素，有一些單詞可能會比較自然地在很多文檔中反覆出現，比如英語中的“The”、“An”、“But”等等。這些詞大多起到了鏈接語句的作用，是保持語言連貫不可或缺的部分。然而，如果我們要搜索“How to Build A Car”這個關鍵詞，其中的“How”、“To”以及“A”都極可能在絕大多數的文檔中出現，這個時候 TF 就無法幫助我們區分文檔的相關度了。
IDF，也就是“逆文檔頻率”（Inverse Document Frequency），就在這樣的情況下應運而生。這裡面的思路其實很簡單，那就是我們需要去“懲罰”（Penalize）那些出現在太多文檔中的單詞。
也就是說，真正攜帶“相關”信息的單詞僅僅出現在相對比較少，有時候可能是極少數的文檔裡。這個信息，很容易用“文檔頻率”來計算，也就是，有多少文檔涵蓋了這個單詞。很明顯，如果有太多文檔都涵蓋了某個單詞，這個單詞也就越不重要，或者說是這個單詞就越沒有信息量。因此，我們需要對 TF 的值進行修正，而 IDF 的想法是用 DF 的倒數來進行修正。倒數的應用正好表達了這樣的思想，DF 值越大越不重要。
在瞭解了 TF 和 IDF 的基本計算方法後，我們就可以用這兩個概念的乘積來表達某個查詢單詞在一個目標文檔中的重要性了。值得一提的是，雖然我們在介紹 TF-IDF 這個概念的時候，並沒有提及怎麼把查詢關鍵字和文檔分別表達成向量，其實 TF-IDF 算法隱含了這個步驟。
具體來說，對於查詢關鍵字，向量的長度是 V，也就是我們剛才說過的詞彙表的大小。然後其中關鍵字的單詞出現過的維度是 1，其他維度是 0。對於目標文檔而言，關鍵詞出現過的維度是 TF-IDF 的數值，而其他維度是 0。在這樣的表達下，如果我們對兩個文檔進行“點積”操作，則得到的相關度打分（Scoring）就是 TF-IDF 作為相關度的打分結果。
TF-IDF 算法變種
很明顯，經典的 TF-IDF 算法有很多因素沒有考慮。在過去的很長一段時間裡，研究人員和工程師開發出了很多種 TF-IDF 的變種。這裡我介紹幾個經典的變種。
首先，很多人注意到 TF 的值在原始的定義中沒有任何上限。雖然我們一般認為一個文檔包含查詢關鍵詞多次相對來說表達了某種相關度，但這樣的關係很難說是線性的。拿我們剛才舉過的關於“Car Insurance”的例子來說，文檔 A 可能包含“Car”這個詞 100 次，而文檔 B 可能包含 200 次，是不是說文檔 B 的相關度就是文檔 A 的 2 倍呢？其實，很多人意識到，超過了某個閾值之後，這個 TF 也就沒那麼有區分度了。
用 Log，也就是對數函數，對 TF 進行變換，就是一個不讓 TF 線性增長的技巧。具體來說，人們常常用 1+Log(TF) 這個值來代替原來的 TF 取值。在這樣新的計算下，假設“Car”出現一次，新的值是 1，出現 100 次，新的值是 5.6，而出現 200 次，新的值是 6.3。很明顯，這樣的計算保持了一個平衡，既有區分度，但也不至於完全線性增長。
另外一個關於 TF 的觀察則是，經典的計算並沒有考慮“長文檔”和“短文檔”的區別。一個文檔 A 有 3,000 個單詞，一個文檔 B 有 250 個單詞，很明顯，即便“Car”在這兩個文檔中都同樣出現過 20 次，也不能說這兩個文檔都同等相關。對 TF 進行“標準化”（Normalization），特別是根據文檔的最大 TF 值進行的標準化，成了另外一個比較常用的技巧。
第三個常用的技巧，也是利用了對數函數進行變換的，是對 IDF 進行處理。相對於直接使用 IDF 來作為“懲罰因素”，我們可以使用 N+1 然後除以 DF 作為一個新的 DF 的倒數，並且再在這個基礎上通過一個對數變化。這裡的 N 是所有文檔的總數。這樣做的好處就是，第一，使用了文檔總數來做標準化，很類似上面提到的標準化的思路；第二，利用對數來達到非線性增長的目的。
還有一個重要的 TF-IDF 變種，則是對查詢關鍵字向量，以及文檔向量進行標準化，使得這些向量能夠不受向量裡有效元素多少的影響，也就是不同的文檔可能有不同的長度。在線性代數里，可以把向量都標準化為一個單位向量的長度。這個時候再進行點積運算，就相當於在原來的向量上進行餘弦相似度的運算。所以，另外一個角度利用這個規則就是直接在多數時候進行餘弦相似度運算，以代替點積運算。
小結
今天我為你講了文檔檢索領域或者搜索領域裡最基本的一個技術：TF-IDF。我們可以看到，TF-IDF 由兩個核心概念組成，分別是詞在文檔中的頻率和文檔頻率。TF-IDF 背後隱含的是基於向量空間模型的假設。
一起來回顧下要點：第一，簡要介紹了 TF-IDF 的歷史。第二，詳細介紹了 TF-IDF 算法的主要組成部分。第三，簡要介紹了 TF-IDF 的一些變種 。
最後，給你留一個思考題，如果要把 TF-IDF 應用到中文環境中，是否需要一些預處理的步驟？
閱讀更多 小鳥編程 的文章
