Learning to Order Things

By William W. Cohen, Robert E. Schapire, Yoram Singer. 1997

There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference judgments, i.e., statements to the effect that one instance should be ranked ahead of another. We outline a two-stage approach in which one first learns by conventional means a binary preference function indicating whether it is advisable to rank one instance before another. Here we consider an on-line algorithm for learning preference functions that is based on Freund and Schapire's "Hedge" algorithm. In the second stage, new instances are ordered so as to maximize agreement with the learned preference function. We show that the problem of finding the ordering that agrees best with a learned preference function is NP-complete. Nevertheless, we describe simple greedy algorithms that are guaranteed to find a good approximation. Finally, we show how metasearch can be formulated as an ordering problem, and present experimental results on learning a combination of "search experts," each of which is a domain-specific query expansion strategy for a web search engine.

Subfields: Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Retrieval & Search

Citations in the corpus

Natural Language Processing (Almost) from Scratch (2011, methodology): “We propose here to use a pairwise ranking approach (Cohen et al., 1998).”
Recent advances in document summarization (2017, methodology): “Classic reordering approaches include inferring order from weighted sentence graph [36], or perform a chronological ordering algorithm [8] that sorts sentences based on timestamp and position.”
Accurately interpreting clickthrough data as implicit feedback (2005, methodology): “The strategies we explore are based on the idea that not only clicks should be used as feedback signals, but also the fact that some links were not clicked on [14, 7].”
Mining User Mobility Features for Next Place Prediction in Location-Based Services (2012, methodology): “This method of training a model by providing feedback in the form of user preference has been established in the past [4] and corresponds to an effective reduction of the ranking problem to a binary classiﬁcation task .”
The K-armed Dueling Bandits Problem (2012, methodology): “We will present algorithms which achieve identical regret bounds for both formulations (up to constant factors) by assuming a property called stochastic triangle inequality , which is described in the next section.”
Automatically Generating Wikipedia Articles: A Structure-Aware Approach (2009, methodology): “tk using a majority ordering algorithm (Cohen et al., 1998).”
Inferring Strategies for Sentence Ordering in Multidocument News Summarization (2002, background): “Cohen et al. (1999) show that this algorithm produces a tight approximation of the optimal solution.”
Learning to rank: from pairwise approach to listwise approach (2007, methodology): “If pairwise data is available (such as clicksthrough Joachims (2002)), then we can use them to create training data as well, for example, by employing the algorithm proposed in Cohen et al. (1998)).”
When are elections with few candidates hard to manipulate? (2007, background): “However, there exist voting mechanisms where determining the winner is computationally hard [Bartholdi et al. 1989b; Hemaspaandra et al. 1997; Cohen et al. 1999; Dwork et al. 2001; Rothe et al. 2003; Davenport and Kalagnanam 2004; Conitzer et al. 2006; Conitzer 2006]—but only for large numbers of ca”
StarNet: Targeted Computation for Object Detection in Point Clouds (2019, background): “more expensive or learned methods may further improve the system [35]. For example, one could learn a ranking function to order the relative importance of proposals for a self-driving planning system [9,5,7]. Finally, we are particularly interested in studying how this system may be amenable to obje”
Learning locomotion over rough terrain using terrain templates (2009, background): “This corresponds to the widely studied rank learning or preference learning problem in the machine learning literature [7].”
A Comprehensive Survey of Neighborhood-based Recommendation Methods (2011, background): “More information on this approach can be found in [13, 21, 37, 36].”
AUC: A Better Measure than Accuracy in Comparing Learning Algorithms (2003, background): “If we want to achieve a more accurate ranking from a classi er, one might naturally expect that we must need the true ranking in the training examples [2].”
Revisiting Word Embedding for Contrasting Meaning (2015, methodology): “In this paper, we use also another training criteria, motivated by the pairwise ranking approach (Cohen et al., 1998).”
Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments (2001, background): “, 1998; Billsus & Pazzani, 1998; Nakamura & Abe, 1998) and as a listranking problem (Cohen et al., 1999; Freund et al., 1998).”
More Accurate Question Answering on Freebase (2015, background): “Following [10], we have also sorted the candidates by their number of ”won” comparisons against all other candidates.”
QoS Ranking Prediction for Cloud Services (2013, methodology): “However, there are n ! possible rankings for n services, and the optimal ranking search problem is NP-Complete [6].”
EigenRank: a ranking-oriented approach to collaborative filtering (2008, methodology): “Various machine learning approaches including ensembles[5, 6], support vector machines[16] and neural networks[4] have been developed for learning such a binary classifier to model the preference function.”
Learning to match and cluster large high-dimensional data sets for data integration (2002, methodology): “Asnoted above, our formalization of adaptive clustering and matching is inspired by the model of ”learning to order” of Cohen, Schapire, and Singer [5].”