Published on Tue Aug 16 2016

Scalable Learning of Non-Decomposable Objectives

Elad ET. Eban, Mariano Schain, Alan Mackey, Ariel Gordon, Rif A. Saurous, Gal Elidan

Modern retrieval systems are often driven by an underlying machine learning model. The goal of such systems is to identify and possibly rank the few most relevant items for a given query.

0
0
0
Abstract

Modern retrieval systems are often driven by an underlying machine learning model. The goal of such systems is to identify and possibly rank the few most relevant items for a given query or context. Thus, such systems are typically evaluated using a ranking-based performance metric such as the area under the precision-recall curve, the score, precision at fixed recall, etc. Obviously, it is desirable to train such systems to optimize the metric of interest. In practice, due to the scalability limitations of existing approaches for optimizing such objectives, large-scale retrieval systems are instead trained to maximize classification accuracy, in the hope that performance as measured via the true objective will also be favorable. In this work we present a unified framework that, using straightforward building block bounds, allows for highly scalable optimization of a wide range of ranking-based objectives. We demonstrate the advantage of our approach on several real-life retrieval problems that are significantly larger than those considered in the literature, while achieving substantial improvement in performance over the accuracy-objective baseline.

Fri May 28 2010
Machine Learning
Ranked bandits in metric spaces: learning optimally diverse rankings over large document collections
Most learning to rank research has assumed that the utility of different documents is independent. We present a formulation that optimizes the fraction of satisfied users. We show that our algorithms learn orders of magnitude more quickly than previous approaches.
0
0
0
Wed Feb 28 2018
Machine Learning
Constrained Classification and Ranking via Quantiles
In most machine learning applications, classification accuracy is not the primary metric of interest. Binary classifiers which face class imbalance are often evaluated by the score. The maximization of many of these metrics can be expressed as a constrained optimization problem.
0
0
0
Tue Feb 11 2014
Machine Learning
Ranking via Robust Binary Classification and Parallel Parameter Estimation in Large-Scale Data
RoBiRank is a ranking algorithm that is motivated by observing a close connection between evaluation metrics for learning to rank and loss functions for robust classification. The algorithm shows a very competitive performance on standard benchmark datasets against other representative algorithms.
0
0
0
Sun Mar 06 2016
Machine Learning
Generalization error bounds for learning to rank: Does the length of document lists matter?
Existing generalization error bounds necessarily degrade as the size of the document list associated with a query increases. For several loss functions, including the cross-entropy loss used in the well known ListNet method, there is no degradation in generalization ability as document lists become longer.
0
0
0
Sat May 03 2014
Machine Learning
Perceptron-like Algorithms and Generalization Bounds for Learning to Rank
Learning to rank is a supervised learning problem where the output space is the space of rankings. We make theoretical contributions to the learning to rank problem both in the online and batch settings. We propose a perceptron-like algorithm for learning a ranking function in an online setting.
0
0
0
Wed Jul 23 2014
Machine Learning
Learning Rank Functionals: An Empirical Study
Ranking is a key aspect of many applications, such as information retrieval, question answering, ad placement and recommender systems. Learning to rank has the goal of estimating a ranking model automatically from training data. In experiments, we evaluate these design aspects on two tasks.
0
0
0