Ranking Algorithms

A ranking algorithm orders a set of candidate items for a request so that the items most likely to satisfy it appear first. In a recommender, ranking is usually one stage of a pipeline and not the whole system.

Where ranking sits in a pipeline

Google’s Machine Learning Crash Course on candidate generation describes candidate generation as producing a set of relevant candidates for a query. The next stage, described in Google’s Machine Learning Crash Course on recommendation system stages, scores and ranks the candidates to choose the set of items to display, on the order of ten. Because fewer items are scored, the system can use a more precise model with additional queries. A final re-ranking stage takes additional constraints into account, for example removing items the user explicitly disliked or boosting fresher content, and can help ensure diversity, freshness, and fairness.

Families of ranking methods

• Heuristic scores such as popularity or recency. They are simple baselines. The Recommender Systems article compares several simple scoring models.
• Learned scores. A model predicts a score for each item, and the list is sorted by the score.
• Pairwise learning to rank. RankNet, described by Burges (2010), models the probability that item \(i\) should rank above item \(j\) as a sigmoid of the score difference, \(P_{ij} = 1/(1+e^{-\sigma(s_i – s_j)})\), and trains with a cross-entropy cost against the known preference.
• Lambda methods. LambdaRank scales the pairwise gradients by the change in NDCG that swapping the pair would cause, and LambdaMART applies those gradients to gradient-boosted decision trees.

For a pair with scores \(s_i = 2\) and \(s_j = 1\) and \(\sigma = 1\), the model gives \(P_{ij} = 0.731\). If item \(i\) should indeed rank higher, the cross-entropy cost is \(-\ln 0.731 = 0.313\). Equal scores give 0.5, and the cost falls as the score gap in the right direction grows.

Why the metric is hard to optimize directly

Ranking metrics such as NDCG depend on the sorted order of the scores, so they are non-smooth and not differentiable. According to Burges, standard classification and regression losses are not well suited to them. The lambda gradients were designed to carry the metric’s information into training without optimizing the metric explicitly.

Choosing and checking a ranker

Evaluate the final ordering with a metric that matches how the list is used, such as NDCG or hit rate, and state how relevance was labeled (Relevance in Recommender Systems). Offline scores do not settle what users do with live rankings, which is what interleaving tests and A/B tests examine.

References:

• Burges, From RankNet to LambdaRank to LambdaMART: An Overview (Microsoft Research technical report MSR-TR-2010-82)
• Google for Developers, Machine Learning Crash Course: Candidate generation overview (Creative Commons Attribution 4.0)
• Google for Developers, Machine Learning Crash Course: Recommendation system stages (Creative Commons Attribution 4.0)