Learning to Rank小結 - Searcher's Log

??? Searcher's Log home wiki about
??? Learning to Rank小結

??? /* -*- author: Tan Menglong; email: tanmenglong_at_gmail; twitter/weibo: @crackcell; 轉載請注明出處 -*- */
??? Table of Contents

??????? 1 前言
??????? 2 LTR流程
??????? 3 訓練數據的獲取
??????????? 3.1 人工標注
??????????? 3.2 搜索日志
??????????? 3.3 公共數據集
??????? 4 特征抽取
??????? 5 模型訓練
??????????? 5.1 訓練方法
??????????????? 5.1.1 Pointwise
??????????????? 5.1.2 Pairwise
??????????????? 5.1.3 Listwise
??????? 6 效果評估
??????????? 6.1 NDCG（Normalized Discounted Cumulative Gain）
??????????????? 6.1.1 定義
??????????????? 6.1.2 描述
??????????? 6.2 MAP（Mean Average Precision）
??????????????? 6.2.1 定義
??????????????? 6.2.2 描述
??????? 7 參考

??? 1 前言

??? 在傳統搜索引擎的ranking策略中，一般會包含若干子策略，子策略通過若干種方式組合成更大的策略一起發揮作用。策略的組合方式以及參數一般采取人工或者半人工的方式確定。隨著策略的逐步細化，傳統的方式變得越來越困難。于是Learning to Rank（LTR）就被引入了進來。LTR的核心是想是用機器學習來解決排序的問題。目前被廣泛運用在 信息檢索（IR） 、 自然語言處理（NLP） 和 數據挖掘（DM） 中。 LTR是監督的學習。建好模型之后，需要用訓練數據集的人工標注結果來訓練。
??? 2 LTR流程

??? ./NOTE_a_short_intro_2_ltr-training_process.png [[./NOTE_a_short_intro_2_ltr-training_process.png][./NOTE_a_short_intro_2_ltr-training_process.png]]
??? 3 訓練數據的獲取

??? 有2種獲取訓練數據的來源:1）人工標注；2）搜索日志。
??? 3.1 人工標注

??? 從搜索日志中隨機選取一部分Query，讓受過專業訓練的數據評估員對"Query-Url對"給出相關性判斷。常見的是5檔的評分:差、一般、好、優秀、完美。以此作為訓練數據。 人工標注是標注者的主觀判斷，會受標注者背景知識等因素的影響。
??? 3.2 搜索日志

??? 使用點擊日志的偏多。比如，結果ABC分別位于123位，B比A位置低，但卻得到了更多的點擊，那么B的相關性可能好于A。點擊數據隱式反映了同Query下搜索結果之間相關性的相對好壞。在搜索結果中，高位置的結果被點擊的概率會大于低位置的結果，這叫做"點擊偏見"（Click Bias）。但采取以上的方式，就繞過了這個問題。因為我們只記錄發生了"點擊倒置"的高低位結果，使用這樣的"偏好對"作為訓練數據。關于點擊數據的使用，后續再單獨開帖記錄，這里不展開。 在實際應用中，除了點擊數據，往往還會使用更多的數據。比如通過session日志，挖掘諸如頁面停留時間等維度。 在實際場景中，搜索日志往往含有很多噪音。且只有Top Query（被搜索次數較多的Query）才能產生足夠數量能說明問題的搜索日志。
??? 3.3 公共數據集

??? 現存一批公開的數據集可以使用

??????? LETOR, http://research.microsoft.com/en-us/um/beijing/projects/letor/
??????? Microsoft Learning to Rank Dataset, http://research.microsoft.com/en-us/projects/mslr/
??????? Yahoo Learning to Rank Challenge, http://webscope.sandbox.yahoo.com/

??? 4 特征抽取

??? 搜索引擎會使用一系列特征來決定結果的排序。一個特征稱之為一個“feature”。按照我的理解，feature可以分為3大類：

??????? Doc本身的特征：Pagerank、內容豐富度、是否是spam等
??????? Query-Doc的特征：文本相關性、Query term在文檔中出現的次數等

??? 此階段就是要抽取出所有的特征，供后續訓練使用。
??? 5 模型訓練
??? 5.1 訓練方法

??? LTR的學習方法分為Pointwise、Pairwise和Listwise三類。Pointwise和Pairwise把排序問題轉換成 回歸 、 分類 或 有序分類 問題。Lisewise把Query下整個搜索結果作為一個訓練的實例。3種方法的區別主要體現在損失函數（Loss Function）上。
??? 5.1.1 Pointwise

??? 排序問題被轉化成單結果的 回歸 、 分類 或 有序分類 的問題。

??????? 函數框架
??????? L(F(x),y)=∑i=1nl(f(xi)?yi)
??????? 小結
??????? ./NOTE_a_short_intro_2_ltr-pointwise_flow.png

??? 5.1.2 Pairwise

??? 排序問題被轉化成結果對的 回歸 、 分類 或 有序分類 的問題。

??????? 函數框架
??????? L(F(x),y)=∑i=1n?1∑j=i+1nl(sign(yi?yj),f(xi)?f(xj))
??????? 小結
??????? ./NOTE_a_short_intro_2_ltr-pairwise_flow.png

??? 5.1.3 Listwise

??????? 函數框架
??????? L(F(x),y)=exp(?NDCG)
??????? 小結
??????? ./NOTE_a_short_intro_2_ltr-listwise_flow.png

??? 6 效果評估

??? 對于搜索結果，有多種量化搜索得分的計算方法，這里介紹NDCG和MAP。
??? 6.1 NDCG（Normalized Discounted Cumulative Gain）
??? 6.1.1 定義
??? NDCG(k)=G?1max,i(k)∑j:πi≦k2yi,j?1log2(1+πi(j))

??????? 計算前k條結果的相關性得分
??????? i：第i次搜索
??????? j：第j條結果
??????? yi,j：第j條結果的相關性標注得分，5檔制
??????? πi(j)：這條結果在排序中的位置

??? 6.1.2 描述

??????? 顧名思義，NDCG的公式由 N、D、C、G 4部分組成。將公式改寫成
??????? NDCG(k)=Gmax,i(k)∑j:πi≦kGi(j)Di(πi(j))
??????? 先看G部分。G是增益函數（Gain）,表示第j條結果在被給予評分yi,j之后所貢獻的分值增益。定義如下
??????? Gi(j)=2yi,j?1
??????? 再看D部分。D是位置折算函數（Discounted）。因為不同位置的增益應該是不同的，D函數給結果按照位置賦予一個權重。定于如下
??????? D(πi(j))=1log2(1+πi(j))
??????? C部分就是累加（Cumulative），將k條結果的得分加在一起。
??????? N是歸一化因子（Normalized），取值是該位置上G函數理論上取得的最大值的倒數。目的是縮放不同位置上的得分到統一區間。

??? 6.2 MAP（Mean Average Precision）
??? 6.2.1 定義
??? AP=∑nij=1P(j)yi,j∑nij=1yi,j
??? P(j)=∑k:πi(k)≦πi(j)yi,kπi(j)

??????? MAP中，相關性評分yi,j只有2檔：0和1

??? 6.2.2 描述

??????? P表示結果j的權重，從位置j開始，相關（標記為1）的結果所在的比例
??????? AP表示單query下，相關的結果的平均的加權得分
??????? AP中，只有標記為相關的結果才會參與加權的累加
??????? AP是單query下的得分，多query的平均AP，就成了MAP

??? 7 參考

??????? Hang Li. Learning to Rank for Information Retrieval and Natural Language Processing
??????? Hang Li. A Short Introduction to Learning to Rank

??? Author: Tan Menglong <tanmenglong AT gmail DOT com>

??? Date: 2011-12-17 17:11:51 CST

??? HTML generated by org-mode 6.33x in emacs 23

Learning to Rank小結