AdaRank: a boosting algorithm for information retrieval

"AdaRank: a boosting algorithm for information retrieval," Jun Xu, Hang Li, SIGIR 2007.

This paper proposes an boosting algorithm AdaRank of the issue learning to rank for document retrieval. According to the essence of AdaBoost, AdaRank repeatedly constructs "weak rankers" on the basis of re-weighted data, and the final prediction function is also the linear combination of those "weak rankers".

The evaluation of AdaRank is MAP (Mean Average Precision) and NDCG (Normalized Discounted Cumulative Gain).

Here below is the algorithm of AdaRank



Based on Adaboost, AdaRank is a novel attempt for ranking methods. Although the accuracy of the real experiment is not so good as my expectation, I think the efficiency may be much better than some previous work.

read more...

Support vector learning for ordinal regression

"Support vector learning for ordinal regression," R. Herbrich, ICANN, 1999.

This paper proposes a new learning task for ordinal regression which is complementary to both classification and metric regression because of discrete and ordered outcome space. The formulation for this task is to formalize as a problem of binary classification by minimizing pairwise 0-1 loss.

,
where U is the rank function to output the score.

Here below is an toy example from this paper, the figure(b) is the mapping result for figure(a), and after mapping, we can simply find the margin.

This paper considers the simply concept of SVM, and uses it for ranking. Although inefficiency and not-so-good accuracy, it's still a guide for us to think about ranking problems.


read more...