A Mathematical Structure of Processes for Generating Rankings Through the Use of Nonnegative Irreducible Matrices
3
Citation
5
Reference
20
Related Paper
Citation Trend
Abstract:
In our previous study, focusing on a ranking determination, we developed two ranking models. The foundation of these ranking models is derived from either one of the two ranking methods, denoted by Ranking (I) and Ranking (II), that were proposed in our previous papers. The purpose of this paper is to analyze the mathematical structure in the process of generating Ranking (I) and Ranking (II) in detail and to study the properties of the two ranking methods.Keywords:
Ranking SVM
Cite
The ranking problem consists of comparing a collection of observations and deciding which one is "better." An observation can consist of multiple attributes, multiple data types, and different orders of preference. Due to diverse practical applications, the ranking problem has been receiving attention in the domain of machine learning and statistics, some of those applications being webpage ranking, gene ranking, pesticide risk assessment, credit-risk screening, etc. In this article, we will present and discuss a novel and fast clustering-based algorithmic ranking technique and provide necessary theoretical working. The proposed technique utilizes the interrelationships among the observations to perform ranking and is based on the crossing minimization paradigm from the domain of VLSI chip design. Using laboratory ranking results as a reference, we compare the algorithmic ranking of the proposed technique and two traditional ranking techniques: the Hasse Diagram Technique (HDT) and the Hierarchical Clustering (HC) technique. The results demonstrate that our technique generates better rankings compared to the traditional ranking techniques and closely matches the laboratory results that took days of work.
Ranking SVM
Learning to Rank
Hasse diagram
Cite
Citations (3)
Probability Ranking Principle (PRP)[31], which assumes that each document has a unique and independent probability to satisfy a particular information need, is one of the fundamental principles for ranking. Traditionally, heuristic ranking features and well-known learning-to-rank approaches have been designed by following the PRP principle. Recently, neural IR models, which adopt deep learning to enhance the ranking performances, also obey the PRP principle. Though it has been widely used for nearly five decades, in-depth analysis shows that PRP is not an optimal principle for ranking, due to its independent assumption that each document should be independent of the rest candidates. Counter examples include pseudo relevance feedback[24], interactive information retrieval[46], search result diversification[10] etc. To solve the problem, researchers recently proposed to model the dependencies among the documents during the designing of ranking models. A number of ranking models have been proposed and state-of-the-art ranking performances have been achieved. This tutorial aims to give a comprehensive survey on these recently developed ranking models that go beyond the PRP principle. The tutorial tries to categorize these models based on their intrinsic assumptions: assuming that the documents are independent, sequentially dependent, or globally dependent. In this way, we expect the researchers focusing on ranking in search and recommendation can have a novel angle of view on the designing of ranking models, and therefore can stimulate new ideas on developing novel ranking models.
Ranking SVM
Learning to Rank
Relevance
Rank (graph theory)
Cite
Citations (1)
Preference learning
Cite
Citations (1)
Probability model
Cite
Citations (3)
This article investigates the theoretical relation between loss criteria and the optimal ranking functions driven by the criteria in bipartite ranking. In particular, the relation between area under the ROC curve (AUC) maximization and minimization of ranking risk under a convex loss is examined. We characterize general conditions for ranking-calibrated loss functions in a pairwise approach, and show that the best ranking functions under convex ranking-calibrated loss criteria produce the same ordering as the likelihood ratio of the positive category to the negative category over the instance space. The result illuminates the parallel between ranking and classification in general, and suggests the notion of consistency in ranking when convex ranking risk is minimized as in the RankBoost algorithm for instance. For a certain class of loss functions including the exponential loss and the binomial deviance, we specify the optimal ranking function explicitly in relation to the underlying probability distribution. In addition, we present an in-depth analysis of hinge loss optimization for ranking and point out that the RankSVM may produce potentially many ties or granularity in ranking scores due to the singularity of the hinge loss, which could result in ranking inconsistency. The theoretical findings are illustrated with numerical examples. Supplementary materials for this article are available online.
Hinge loss
Ranking SVM
Learning to Rank
Cite
Citations (22)
Rank (graph theory)
Data set
Association (psychology)
Cite
Citations (4)
Global ranking, a new information retrieval (IR) technology, uses a ranking model for cases in which there exist relationships between the objects to be ranked. In the ranking task, the ranking model is defined as a function of the properties of the objects as well as the relations between the objects. Existing global ranking approaches address the problem by learning to rank. In this paper, we propose a global ranking framework that solves the problem via data fusion. The idea is to take each retrieved document as a pseudo-IR system. Each document generates a pseudo-ranked list by a global function. The data fusion algorithm is then adapted to generate the final ranked list. Taking a biomedical information extraction task, namely, interactor normalization task (INT), as an example, we explain how the problem can be formulated as a global ranking problem, and demonstrate how the proposed fusion-based framework outperforms baseline methods. By using the proposed framework, we improve the performance of the top 1 INT system by 3.2% using the official evaluation metric of the BioCreAtIvE challenge. In addition, by employing the standard ranking quality measure, NDCG, we demonstrate that the proposed framework can be cascaded with different local ranking models and improve their ranking results.
Ranking SVM
Learning to Rank
Normalization
Rank (graph theory)
Cite
Citations (1)
Cite
Citations (3)
The ranking aggregation problem is that to establishing a new aggregate ranking given a set of rankings of a finite set of items. This problem is met in various applications, such as the combination of user preferences, the combination of lists of documents retrieved by search engines and the combination of ranked gene lists.
In the literature, the ranking aggregation problem has been solved as an optimization of some distance between the rankings overlooking the existence of a true ranking. In this thesis we address the ranking aggregation problem assuming the existence of a true ranking on the set of items: the goal is to estimate an unknown, true ranking given a set of input rankings provided by experts with different approximation quality.
We propose a novel solution called Belief Ranking Estimator (BRE) that takes into account two aspects still unexplored in ranking combination: the approximation quality of the experts and for the first time the uncertainty related to each item position in the ranking. BRE estimates in an unsupervised way the true ranking given a set of rankings that are diverse quality estimations of the unknown true ranking.
The uncertainty on the items's position in each ranking is modeled within the Belief Function Theory framework, that allows for the combination of subjective knowledge in a non Bayesian way.
This innovative application of belief functions to rankings, allows us to encode different sources of a priori knowledge about the correctness of the ranking positions and also to weigh the reliability of the experts involved in the combination.
We assessed the performance of our solution on synthetic and real data against state-of-the-art methods. The tests comprise the aggregation of total and partial rankings in different empirical settings aimed at representing the different quality of the input rankings with respect to the true ranking. The results show that BRE provides an effective solution when the input rankings are heterogeneous in terms of approximation quality with respect to the unknown true ranking.
Ranking SVM
Cite
Citations (11)
Multipartite ranking is a statistical learning problem that consists in ordering observations that belong to a high dimensional feature space in the same order as the labels, so that the observations with the highest label appear at the top of the list. This work aims to understand the probabilistic nature of the multipartite ranking problem in order to obtain theoretical guarantees for ranking algorithms. In this context, the output of a ranking algorithm takes the form of a scoring function, a function that maps the space of the observation to the real line which order is induced using the values on the real line. The contributions of this manuscript are the following : First, we focus on the characterization of optimal solutions to multipartite ranking. The second research theme is the design of algorithms to produce scoring functions. We offer two methods, the first using an aggregation procedure, the second an approximation scheme. Finally, we return to the binary ranking problem to establish adaptive minimax rate of convergence.
Ranking SVM
Multipartite
Learning to Rank
Cite
Citations (0)