Learning to Rank简介
機器學習有三大問題，分類、回歸和排序。分類和回歸之前了解了很多的算法，但排序還沒有深入的了解過。
Learning to Rank有很多種典型的應用。包括：
- document retrieval
- expert search
- definition search
- collaborative filtering
- question answering
- keyphrase extraction
- document summarization
- machine translation
這一長串下來，想必重要性不言而喻。話不多說，開始正題。
基本定義
了解一個算法，要從它的目標和數據開始。Ranking的基本流程如下：
給定一個query，得到一批文檔。優化的目標自然就是相關性越高的文檔排在前面越好。那么如何量化這個指標呢？有三種函數可以量化這個指標：
- DCG（Discount Cumulative Gain）
- NDCG（Normalized Discount Cumulaive Gain）
- MAP (Mean Average Precision)
先從DCG開始說，對于查詢到的每一個樣本來說，標注好的數據中它都會有一個評分，該評分也相當于類別，這個評分越高，表明這個樣本越相關。DCG的基本思想就是排名越高的結果越相關那么DCG值就會越大。
DCG的公式表示，對于每次查詢得到的結果排列，對于前k個結果中的每一個樣本，計算一個總評分，該評分由兩項相乘得到，G(j)與相關性有關，相關性越大，G(j)越大，而且是以指數級增長；D(pi(j))則和位置有關，位置越靠前，就越重要，以對數的倒數形式衰減。
NDCG是歸一化后的DCG，它表示的是，對DCG進行歸一化，使得相關性排序正好從高到低時，值為1。所以在此不贅述了
下面說說MAP，如下：
需要注意的是，MAP中，結果只有相關和不相關兩種，即1和0。?
P(j)表示，到位置j時，前j個結果中有多少相關的結果的比率。而AP的定義則表示，所有相關結果位置上的準確率的平均。而MAP則是，所有樣本上AP值的平均。
在具體的算法中，上述的指標是無法直接優化的，只能采用各種各樣的妥協，比如：
這三種都是1-NDCG的upper bound函數（這里我還沒明白）。但這三種則代表了不同類型的妥協，第一種是pointwise的，因為在單個樣本上計算損失。第二種是pairwise的，在成對的樣本上計算損失。第三種是listwise的，因為直接在list上計算損失。
Pointwise方法
Pointwise方法包括：
- Subset Ranking
- McRank
- Prank
- OC SVM
以OC SVM為例，她是傳統SVM的變形，通過增多偏移量的方式，實現多個分類面，從而達到分類的目的。
以最簡單的線性分類器來看，傳統的SVM計算分類面的方式是w·x+b，而OC SVM則是有多個b，從而構造了多個平行的分類面，如下所示：
反映在目標函數上就是：
Pairwise方法
pairwise方法包括：
- Ranking SVM
- RankBoost
- RankNet
- GBRank
- IR SVM
- Lambda Rank
- LambdaMART
Ranking SVM
通過把問題簡化，變成判斷兩個樣本先后的二分類問題：
反映在目標函數上就是：
IR SVM
Ranking SVM的簡化方法導致該算法具有兩個缺點：
- 沒有區分不同相關性文檔的重要程度
- 沒有區分不同query間pair對的重要程度
為了解決這兩個問題，對Hinge Loss做出了改進，對不同類型的pair進行加權。
反映在目標函數上就是：
加權的兩個函數一個用來衡量不同相關性的樣例，一個用來衡量不同query的樣例。而加權的方法是采用先驗方法來做。對于不同相關性的文檔，要根據其相關性值來確定函數，對于不同query，根據該query產生的pair對的數目的倒數來加權。
Listwise方法
Listwise方法包括：
- ListNet
- ListMLE
- AdaRank
- SVM MAP
- SoftRank
以SVM MAP為例，對于一個query，查詢到的樣本會形成一個排列，該排列的得分可以用如下函數衡量：
而真正要優化的額函數，如下：
其中，E可以是NDCG或MAP。
對上面的函數進行轉化，取它的upper bound。如下：
這里是upper_bound的原因是因為后面那個被乘項要么是負，要么是零。由此，本來該求最小值，也變成了求最大值。
然后還是不能繼續優化，所以還得再做兩個變換。
- 將0-1（不等號）函數轉化：
- 因為?
從而，問題就轉化成了如下：
這樣就變為了可以優化的問題。
未來的研究方向
- training data creation
- semi-supervised learning and active learning
- feature learning
- scalable and efficient training
- domain adaption and multi-task learning
- ranking by ensembel learning
- global ranking
- ranking of nodes in a graph
參考文獻
[1]. Hang L I. A short introduction to learning to rank[J]. IEICE TRANSACTIONS on Information and Systems, 2011, 94(10): 1854-1862.
from:?http://blog.csdn.net/stdcoutzyx/article/details/50879219
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的Learning to Rank简介的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CUDA(六). 从并行排序方法理解并行
- 下一篇： 理解dropout