今天來談一個核心問題:如何判定一個網頁與某個查詢之間的相關性。理解這幾個環節之後,具備基礎程式能力的人其實就能動手做一個簡易搜尋引擎,例如為自己就讀的學校或系所建一個小型檢索系統。
沿用之前的例子:查找關於「原子能的應用」的網頁。第一步是在索引中找出包含這幾個詞的頁面。任何一個搜尋引擎的候選集都有數十萬甚至上百萬個「多少有點關係」的頁面,那麼誰該排前面?顯然要依相關性排序。
「原子能的應用」可以拆成三個關鍵詞:原子能、的、應用。依直覺,包含這些詞較多的網頁應該更相關。但這方法有個明顯漏洞:長頁面天生佔便宜,因為它包含的關鍵詞總數本來就多。
因此需要依網頁長度做歸一化,也就是用關鍵字出現次數除以網頁總字數,這個商稱為「關鍵詞頻率」,或單文本詞彙頻率(Term Frequency,TF)。舉例來說,某個共一千詞的網頁中,「原子能」、「的」、「應用」分別出現2次、35次、5次,詞頻就是0.002、0.035、0.005,三者相加得0.042,這就是該頁與查詢相關性的一個簡易度量。
概括地說,若查詢包含關鍵詞 w1, w2, …, wN,它們在特定網頁中的詞頻分別是 TF1, TF2, …, TFN,則相關性就是:TF1 + TF2 + … + TFN。
你可能已經發現另一個漏洞:上例中「的」佔了總詞頻的八成以上,但它對判斷網頁主題幾乎毫無幫助。這類詞被稱為「應刪除詞」(Stopwords),衡量相關性時應排除。中文裡的應刪除詞還有「是」、「和」、「中」、「地」、「得」等數十個。排除之後,上述網頁的相關性降為0.007,其中「原子能」貢獻0.002,「應用」貢獻0.005。
還有一個問題:中文裡「應用」是通用詞,而「原子能」是專業詞,後者在相關性排序中應該更重要。因此我們需要給每個詞一個權重,且這個權重必須滿足兩個條件:
1. 一個詞預測主題的能力越強,權重越大;反之越小。看到「原子能」我們多少能猜出主題,看到一次「應用」則幾乎一無所獲,所以「原子能」的權重應該大於「應用」。
2. 應刪除詞的權重應該為零。
很明顯,一個關鍵詞若只在極少網頁中出現,我們就容易靠它鎖定目標,權重該大;若它在大量網頁中出現,看到它仍不清楚要找什麼,權重就該小。假定關鍵詞 w 出現在 Dw 個網頁中,Dw 越大,w 的權重越小。
資訊檢索中最常用的權重是「逆文本頻率指數」(Inverse Document Frequency,IDF),公式為 log(D/Dw),其中 D 是全部網頁數。舉例:假定中文網頁總數 D=10億,應刪除詞「的」出現在所有網頁中,即 Dw=10億,則 IDF = log(1) = 0。若專業詞「原子能」出現在兩百萬個網頁中,IDF = log(500) ≈ 6.2。若通用詞「應用」出現在五億個網頁中,IDF = log(2) ≈ 0.7。也就是說,在網頁中匹配到一次「原子能」,約相當於匹配九次「應用」。
引入IDF後,相關性計算從簡單求和變成加權求和:TF1×IDF1 + TF2×IDF2 + … + TFN×IDFN。上例中,該頁與「原子能的應用」的相關性為0.0161,其中「原子能」貢獻0.0126,「應用」僅貢獻0.0035。這個比例就與我們的直覺相當吻合了。
TF/IDF被公認為資訊檢索領域最重要的發明之一,在搜尋、文獻分類等相關領域有廣泛應用。它的歷史頗有意思:IDF的概念最早由劍橋大學的Karen Sparck Jones於1972年在〈關鍵詞特殊性的統計推論及其在文獻檢索中的應用〉一文中提出。遺憾的是,她既未從理論上解釋為何權重應取對數函數 log(D/Dw)(而非其他形式,例如平方根),也未在此後深入發展這個題目,以至於後來大量文獻在談TF/IDF時沒有引用她的論文,多數人甚至不知道她的貢獻。
同年Robinson寫了兩頁的解釋,寫得並不好。倒是康乃爾大學的Salton多次撰文與著書討論TF/IDF在資訊檢索中的用途,加上他在領域內的聲望(資訊檢索的世界大獎即以他命名),許多人引用他的書,甚至誤以為這個概念由他提出。世界終究沒有忘記Sparck Jones——2004年,在紀念《文獻學學報》創刊60週年之際,該學報重印了她的經典論文。Robinson也在同期寫了一篇文章,用香農的資訊論解釋IDF,這次解釋是對的,但文章寫得冗長(足足十八頁),把簡單問題搞複雜了。其實資訊論學者早已指出:IDF本質上就是特定條件下關鍵詞機率分布的交叉熵(Kullback-Leibler Divergence)。就這樣,資訊檢索的相關性度量,又回到了資訊論。
今日的搜尋引擎在TF/IDF之上做了不少細節優化,使相關性度量更精準。但對想動手做個搜尋引擎的入門者來說,先把TF/IDF用起來就足夠了。若再結合網頁排名(PageRank),排序品質還能再上一層。