BEYOND MAJORITY: AGGREGATION TECHNIQUES FOR LABEL RANKING ENSEMBLES BASED ON VOTING RULES

Ensemble models collect the results of multiple simple models and combine them into a single aggregated output. By building an ensemble, the mistake of one model can be compensated by the other models, and consequently, ensembles generally exhibit better performance than that of a single model. While ensemble methods were extensively studied in the cases of classification tasks, multi-label tasks, regression tasks, learning to rank tasks and even unsupervised learning tasks such as anomaly detection, they were hardly studied in the context of label ranking tasks.

Label ranking is a prediction problem which deals with learning a mapping between an instance and an order (i.e., a ranking) of labels from a finite set, representing their relevance to the instance. As a motivating example, consider a college applicant that needs to decide what program she should apply to. A counselor can present a ranked list of suggestions, according to the applicant`s profile, preferences, abilities and perhaps even the performance of past students.

In this paper, we investigate novel methods for combining the results of simple label ranking models. While majority voting makes perfectly sense when combining categorical results (as commonly done in classification tasks) and averaging makes perfectly sense when combining numerical results (as commonly done in regression tasks), they make far less sense in the case of rankings. To the best of our knowledge, thus far, only two combination methods have been used in label ranking ensembles for combining the results of simple label ranking models. In contrast, the field of social choice suggests abundant methods that are suitable for aggregating rankings, known as voting rules.

We suggest using voting rules as the aggregation technique in label ranking ensembles. We demonstrate that in general, certain voting rules perform significantly better than others, and that majority voting is in fact one of the worst performing methods. Moreover, we find that under different settings, different voting rules perform the best. Therefore, we present a simple learning framework that learns the best voting rule to be used in a given setting. Evaluation of the proposed framework on 16 semi-synthetic and five real-world datasets shows that it obtains prediction performance that is higher than that obtained by the best performing voting rule.

Insights gained in the process of improving the competence of label ranking ensembles, may be valuable to a variety of fields that are concerned with rankings including: combining voters` preferences in computational social choice, ensembles in machine learning, rank aggregation in information retrieval, group recommendations in recommender system, phylogenetic profiling, and even error correction codes.