Abstract Label ranking aims to learn a mapping from instances to rankings over a finite number of predefined labels. Random forest is a powerful and one of the most successful general-purpose machine learning algorithms of modern times. In this paper, we present a powerful random forest label ranking method which uses random decision trees to retrieve nearest neighbors. We have developed a novel two-step rank aggregation strategy to effectively aggregate neighboring rankings discovered by the random forest into a final predicted ranking. Compared with existing methods, the new random forest method has many advantages including its intrinsically scalable tree data structure, highly parallel-able computational architecture and much superior performance. We present extensive experimental results to demonstrate that our new method achieves the highly competitive performance compared with state-of-the-art methods for datasets with complete ranking and datasets with only partial ranking information.
Both reduction approaches and probabilistic approaches have shown good performances in the experimental studies, while they also come with some disadvantages. For reduction approaches, theoretical assumptions on the sought ranking-valued'' mapping, which may serve as a proper learning bias, may not be easily translated into corresponding assumptions for the classification problems. Moreover, it is often not clear that minimizing the loss function on the binary problems leads to maximizing the performance of the label ranking model in terms of the desired loss function on rankings @cite_11 . For probabilistic approaches, their success also do not come for free but at a large cost associated with both memory and time. For example, the instances-based approaches involve costly nearest neighbour search and the aggregation of neighboring rankings is also slow as it requires using complex optimization procedures, such as the approximate expectation maximization in IB-M and the minorization maximization in IB-PL @cite_28 . Both IB-M and IB-PL are lazy learners, with almost no cost at training phase but a higher cost at predicting phase. It can be costly or even impossible in the resources-constrained applications.
@cite_28 @cite_11
2149166361 2114028889
Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions from supervised data. We assume that each instance in the training data is associated with a list of preferences over the label-set, however we do not assume that this list is either complete or consistent. This enables us to accommodate a variety of ranking problems. In contrast to the general form of the supervision, our goal is to learn a ranking function that induces a total order over the entire set of labels. Special cases of our setting are multilabel categorization and hierarchical classification. We present a general boosting-based learning algorithm for the label ranking problem and prove a lower bound on the progress of each boosting iteration. The applicability of our approach is demonstrated with a set of experiments on a large-scale text corpus. We present a theoretical analysis of supervised ranking, providing necessary and sufficient conditions for the asymptotic consistency of algorithms based on minimizing a surrogate loss function. We show that many commonly used surrogate losses are inconsistent; surprisingly, we show inconsistency even in low-noise settings. We present a new value-regularized linear loss, establish its consistency under reasonable assumptions on noise, and show that it outperforms conventional ranking losses in a collaborative filtering experiment.