A survey and empirical comparison of object ranking methods
---
paper_title: Analyzing and Modeling Rank Data

paper_content:

Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix
---
paper_title: Analyzing and Modeling Rank Data

paper_content:

Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix
---
paper_title: Rank aggregation methods for the Web

paper_content:

We consider the problem of combining ranking results from various sources. In the context of the Web, the main applications include building meta-search engines, combining ranking functions, selecting documents based on multiple criteria, and improving search precision through word associations. We develop a set of techniques for the rank aggregation problem and compare their performance to that of well-known methods. A primary goal of our work is to design rank aggregation techniques that can e ectively combat \spam," a serious problem in Web searches. Experiments show that our methods are simple, e cient, and e ective.
---
paper_title: Regression Models for Ordinal Data

paper_content:

SUMMARY A general class of regression models for ordinal data is developed and discussed. These models utilize the ordinal nature of the data by describing various modes of stochastic ordering and this eliminates the need for assigning scores or otherwise assuming cardinality instead of ordinality. Two models in particular, the proportional odds and the proportional hazards models are likely to be most useful in practice because of the simplicity of their interpretation. These linear models are shown to be multivariate extensions of generalized linear models. Extensions to non-linear models are discussed and it is shown that even here the method of iteratively reweighted least squares converges to the maximum likelihood estimate, a property which greatly simplifies the necessary computation. Applications are discussed with the aid of examples.
---
paper_title: A Machine Learning Approach to Sentence Ordering for Multidocument Summarization and Its Evaluation

paper_content:

Ordering information is a difficult but a important task for natural language generation applications. A wrong order of information not only makes it difficult to understand, but also conveys an entirely different idea to the reader. This paper proposes an algorithm that learns orderings from a set of human ordered texts. Our model consists of a set of ordering experts. Each expert gives its precedence preference between two sentences. We combine these preferences and order sentences. We also propose two new metrics for the evaluation of sentence orderings. Our experimental results show that the proposed algorithm outperforms the existing methods in all evaluation metrics.
---
paper_title: Ranking with Large Margin Principle: Two Approaches

paper_content:

We discuss the problem of ranking k instances with the use of a "large margin" principle. We introduce two main approaches: the first is the "fixed margin" policy in which the margin of the closest neighboring classes is being maximized — which turns out to be a direct generalization of SVM to ranking learning. The second approach allows for k - 1 different margins where the sum of margins is maximized. This approach is shown to reduce to v-SVM when the number of classes k - 2. Both approaches are optimal in size of 2l where l is the total number of training examples. Experiments performed on visual classification and "collaborative filtering" show that both approaches outperform existing ordinal regression algorithms applied for ranking and multi-class SVM applied to general multi-class classification.
---
paper_title: Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

paper_content:

Valiant (1984) and others have studied the problem of learning various classes of Boolean functions from examples. Here we discuss incremental learning of these functions. We consider a setting in which the learner responds to each example according to a current hypothesis. Then the learner updates the hypothesis, if necessary, based on the correct classification of the example. One natural measure of the quality of learning in this setting is the number of mistakes the learner makes. For suitable classes of functions, learning algorithms are available that make a bounded number of mistakes, with the bound independent of the number of examples seen by the learner. We present one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions. The basic method can be expressed as a linear-threshold algorithm. A primary advantage of this algorithm is that the number of mistakes grows only logarithmically with the number of irrelevant attributes in the examples. At the same time, the algorithm is computationally efficient in both time and space.
---
paper_title: A Cutting Plane Algorithm for the Linear Ordering Problem

paper_content:

The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications including triangulation of input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences. In a former paper, we have investigated the facet structure of the 0/1-polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular, we could triangulate all input-output matrices, of size up to 60 × 60, available to us within acceptable time bounds.
---
paper_title: An Efficient Boosting Algorithm for Combining Preferences

paper_content:

We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several applications, such as that of combining the results of different search engines, or the "collaborative-filtering" problem of ranking movies for a user based on the movie rankings provided by other users. In this work, we begin by presenting a formal framework for this general problem. We then describe and analyze an efficient algorithm called RankBoost for combining preferences based on the boosting approach to machine learning. We give theoretical results describing the algorithm's behavior both on the training data, and on new test data not seen during training. We also describe an efficient implementation of the algorithm for a particular restricted but common case. We next discuss two experiments we carried out to assess the performance of RankBoost. In the first experiment, we used the algorithm to combine different web search strategies, each of which is a query expansion for a given domain. The second experiment is a collaborative-filtering task for making movie recommendations.
---
paper_title: Analyzing and Modeling Rank Data

paper_content:

Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix
---
paper_title: Optimizing search engines using clickthrough data

paper_content:

This paper presents an approach to automatically optimizing the retrieval quality of search engines using clickthrough data. Intuitively, a good information retrieval system should present relevant documents high in the ranking, with less relevant documents following below. While previous approaches to learning retrieval functions from examples exist, they typically require training data generated from relevance judgments by experts. This makes them difficult and expensive to apply. The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking. Such clickthrough data is available in abundance and can be recorded at very low cost. Taking a Support Vector Machine (SVM) approach, this paper presents a method for learning retrieval functions. From a theoretical perspective, this method is shown to be well-founded in a risk minimization framework. Furthermore, it is shown to be feasible even for large sets of queries and features. The theoretical results are verified in a controlled experiment. It shows that the method can effectively adapt the retrieval function of a meta-search engine to a particular group of users, outperforming Google in terms of retrieval quality after only a couple of hundred training examples.
---
paper_title: Support Vector Learning for Ordinal Regression

paper_content:

We investigate the problem of predicting variables of ordinal scale. This task is referred to as ordinal regression and is complementary to the standard machine learning tasks of classification and metric regression. In contrast to statistical models we present a distribution independent formulation of the problem together with uniform bounds of the risk functional. The approach presented is based on a mapping from objects to scalar utility values. Similar to support vector methods we derive a new learning algorithm for the task of ordinal regression based on large margin rank boundaries. We give experimental results for an information retrieval task: learning the order of documents with respect to an initial query. Experimental results indicate that the presented algorithm outperforms more naive approaches to ordinal regression such as support vector classification and support vector regression in the case of more than two ranks.
---
paper_title: Order SVM: a kernel method for order learning based on generalized order statistics

paper_content:

In this paper, we address the problem of learning the order of a group of items. This study assumes that items have unobserved “scores” and are ranked by the score. The goal is to derive an approximate scoring function given ordered lists of items without their scores. We extend the notion of order statistics to any order and prove that the distribution functions of the extended statistics are scoring functions. We then propose a learning algorithm, Order SVM, that can approximate the distribution functions. Order SVM is experimentally compared with other learning algorithms using artificial data and important sentence selection data. The results show that Order SVM performs well on both datasets whereas the other methods show good performance on only one of the datasets. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 36(1): 35–43, 2005; Published online in Wiley InterScience (). DOI 10.1002sscj.10630
---
paper_title: A First Course in Order Statistics

paper_content:

Basic Distribution Theory Discrete Order Statistics Order Statistics from Some Specific Distributions Moment Relations, Bounds, and Approximations Characterizations Using Order Statistics Order Statistics in Statistical Inference Asymptotic Theory Record Values Bibliography Indexes.
---
paper_title: Supervised ordering - an empirical survey

paper_content:

Ordered lists of objects are widely used as representational forms. Such ordered objects include Web search results or bestseller lists. In spite of their importance, methods of processing orders have received little attention. However, research concerning orders has become common; in particular, researchers have developed various methods for the task of supervised ordering to acquire functions for object sorting from example orders. Here, we give a unified view of these methods and our new one, and empirically survey their merits and demerits.
---
paper_title: Efficient Clustering for Orders

paper_content:

Lists of ordered objects are widely used as representational forms. Such ordered objects include Web search results or best-seller lists. Clustering is a useful data analysis technique for grouping mutually similar objects. To cluster orders, hierarchical clustering methods have been used together with dissimilarities defined between pairs of orders. However, hierarchical clustering methods cannot be applied to large-scale data due to their computational cost in terms of the number of orders. To avoid this problem, we developed an k-o'means algorithm. This algorithm successfully extracted grouping structures in orders, and was computationally efficient with respect to the number of orders. However, it was not efficient in cases where there are too many possible objects yet. We therefore propose a new method (k-o'means-EBC), grounded on a theory of order statistics. We further propose several techniques to analyze acquired clusters of orders
---
paper_title: Nantonac collaborative filtering: recommendation based on order responses

paper_content:

A recommender system suggests the items expected to be preferred by the users. Recommender systems use collaborative filtering to recommend items by summarizing the preferences of people who have tendencies similar to the user preference. Traditionally, the degree of preference is represented by a scale, for example, one that ranges from one to five. This type of measuring technique is called the semantic differential (SD) method. Web adopted the ranking method, however, rather than the SD method, since the SD method is intrinsically not suited for representing individual preferences. In the ranking method, the preferences are represented by orders, which are sorted item sequences according to the users' preferences. We here propose some methods to recommed items based on these order responses, and carry out the comparison experiments of these methods.
---
paper_title: Supervised ordering - an empirical survey

paper_content:

Ordered lists of objects are widely used as representational forms. Such ordered objects include Web search results or bestseller lists. In spite of their importance, methods of processing orders have received little attention. However, research concerning orders has become common; in particular, researchers have developed various methods for the task of supervised ordering to acquire functions for object sorting from example orders. Here, we give a unified view of these methods and our new one, and empirically survey their merits and demerits.
---
paper_title: Analyzing and Modeling Rank Data

paper_content:

Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix
---
paper_title: Probability models on rankings

paper_content:

Abstract This paper investigates many of the probability models on permutations that have been proposed in the statistical and psychological literature. The various models are categorized into the following general classes: (1) Thurstone order statistics models, (2) ranking models induced by paired comparisons, (3) ranking models based on distances between permutations, and (4) multistage ranking models. Several thematic properties of ranking models are introduced that provide the basis for a systematic study of each of the classes of models. These properties are label-invariance, reversibility, strong unimodality, complete consensus, and L-decomposability. Next, several important subclasses of the four general classes are explored, including a determination of the pairwise intersections of the different classes of models. The paper concludes with an illustration of many of the models on a set of ranked “word association” data.
---
paper_title: Analyzing and Modeling Rank Data

paper_content:

Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix
---
paper_title: The Analysis of Permutations

paper_content:

SUMMARY A probability distribution is defined over the r! permutations of r objects in such a way as to incorporate up to r! -1 parameters. Problems of estimation and testing are considered. The results are applied to data on voting at elections and beanstores.
---
paper_title: Probability models on rankings

paper_content:

Abstract This paper investigates many of the probability models on permutations that have been proposed in the statistical and psychological literature. The various models are categorized into the following general classes: (1) Thurstone order statistics models, (2) ranking models induced by paired comparisons, (3) ranking models based on distances between permutations, and (4) multistage ranking models. Several thematic properties of ranking models are introduced that provide the basis for a systematic study of each of the classes of models. These properties are label-invariance, reversibility, strong unimodality, complete consensus, and L-decomposability. Next, several important subclasses of the four general classes are explored, including a determination of the pairwise intersections of the different classes of models. The paper concludes with an illustration of many of the models on a set of ranked “word association” data.
---
paper_title: Remarks on the method of paired comparisons: I. The least squares solution assuming equal standard deviations and equal correlations

paper_content:

Thurstone’s Case V of the method of paired comparisons assumes equal standard deviations of sensations corresponding to stimuli and zero correlations between pairs of stimuli sensations. It is shown that the assumption of zero correlations can be relaxed to an assumption of equal correlations between pairs with no change in method. Further the usual approach to the method of paired comparisons Case V is shown to lead to a least squares estimate of the stimulus positions on the sensation scale.
---
paper_title: Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons

paper_content:

A photographic material comprising a support having thereon at least one photographic layer with the layer adjacent the support containing non-volatile or low volatile liquid droplets having smaller diameters than the thickness of the layer adjacent the support and a process for producing the photographic material.
---

Title: A Survey and Empirical Comparison of Object Ranking Methods
Section 1: Introduction
Description 1: Introduce the purpose of the survey and provide a general overview of object ranking methods and their applications.

Section 2: An Object Ranking Task
Description 2: Provide a formal definition of the object ranking task and discuss its characteristics and differences from related tasks like regression and classification.

Section 3: Object Ranking Methods
Description 3: Present the different object ranking methods that will be surveyed, including their fundamental principles and methodologies.

Section 4: Cohen's method (Cohen)
Description 4: Discuss Cohen's method for object ranking, including its theoretical basis, algorithm, and practical applications.

Section 5: RankBoost (RB)
Description 5: Describe the RankBoost method, its algorithms, and the special features it incorporates.

Section 6: SVM-based methods: Order SVM (OSVM) and Herbrich's method (SVOR)
Description 6: Discuss the SVM-based methods, focusing on Order SVM and Support Vector Ordinal Regression, including how they adapt SVM techniques for ranking purposes.

Section 7: Expected Rank Regression (ERR)
Description 7: Explain the Expected Rank Regression method, its theoretical background, how it is implemented, and its expected benefits.

Section 8: Experiments on Artificial Data
Description 8: Outline the experimental setup, conditions, and results obtained from the application of various ranking methods on artificial data.

Section 9: Experiments Using Real Data
Description 9: Present the findings from applying the object ranking methods to real-world data sets, detailing the methods' performance and comparative results.

Section 10: Discussion and Conclusions
Description 10: Summarize the survey findings, compare the strengths and weaknesses of the various methods, and discuss the practical implications and future directions for research.

Section 11: A Probabilistic Generative Models for Orders
Description 11: Provide an overview of probabilistic generative models for orders used in the study, explaining their relevance and application in the context of object ranking.