search驗證的方法

兩個月前寫的心得，當時沒餘力將心得整理得更完備，隨手寫了草稿，丟了也可惜，先放上Blog備忘吧。

警告：本篇的心得並不嚴僅，只是抽樣讀了幾篇近二年SIGIR論文，簡單歸納的結果，不見得正確。

我從SIGIR’06、’07裡用ranking當keyword找paper title，隨意挑幾篇有興趣的paper看，只看abstract和實驗裡keyword附近的說明，簡單地整理一下驗證的方法。

驗證 ranking order 的差異性都是用 Kendall’s coefficient of concordance，這個方法對 n 個 item 比較 C(n，2) 對的差異，若比較的兩個 item 在這兩個 ranking 的 order 一致就 +1，不一致 -1，其中一邊相等則為 0，總合除以 C(n，2) 即為結果，1.0 表示完全一致，-1.0 表示完全相反。

驗證 ranking 的正確性時，常用的測量基準是: NDCG，MAP (Mean Average Precision)，和 k-precision (取不同的 top k 結果看 precision)，個人覺得 NDCG 很怪，無法像 MAP 或 k-repcision 從數字值理解出大致狀況，只能從高低之分得知那個好，但大概接近半數論文採用這個做法，而且作者都說這是well-known，很有用的基準。它的概念不差，強調名次之間重要性的差異，就性質的判斷來說不錯，但無法判斷重要性的差異有多大。例如，我們可以用NDCG了解 A ranking 比 B ranking 好，但無法從數據得知好多少。而且這個整體差異也許是某局部計算帶來的，很難分析數字計算出的成因。

在使用這些基準前得先決定兩件事：

1. query words。
2. groud truth，也就是那些文件和query相關。

這兩者通常會一起討論，比方使用TREC的資料，裡面已有整理好的documents和queries，以及標示為相關與否；或是從 search engine log裡找 click 的情況 (大公司的玩法)，將資料多的網頁取出，先透過某種搜尋方式 (e.g. by Lucene) 取出 top k，再由人工驗證相關與否。不管怎麼說，人工驗證耗時可靠性又有限，但很難避開這問題。

以上的準備結束後，再來要說明自己的方法真的有效，於是要找個替死鬼來打，說自己的方法比它好，早期的論文可能會用 tf*idf，一個針對 query 取出網頁和排序的算式，而近兩年我看到的SIGIR paper，幾乎都用 BM25 (Best Match 25)，BM25是由 tf*idf 變化出的複雜算式，似乎是某年 workshop 的冠軍，所以大家都用它當替死鬼吧。於是把自己算出的網頁權重 (e.g PageRank) 和 BM25 的結果合起來，畫個圖表說在 NDCG，MAP，k-precision 下，合起來都比單純的 BM25 好，就算達到目的了。

合的方法也有很多種，像用 RankSVM，RankNet (learning to rank的做法)，這些做法似乎是把 BM25 算的值當一個 feature (或稱 attribute)，也就是 learn 出合起來的 weight；或是用 BM25 取出 top k，再用自己方法算出來的值重排。

大致上是這樣吧，但看的時候跳來跳去沒有細看，不敢保證正確性，我只是大概了解情況而已。