The TreeRank Tournament algorithm for multipartite ranking

Stéphan Clémençon, Sylvain RobbianoJournal of Nonparametric Statistics 2014 · DOI

TL;DR

This paper introduces the TreeRank Tournament (TRT) algorithm, a novel method for multipartite ranking (ranking with more than two categories). Unlike previous approaches that struggled with K>2 categories, TRT effectively optimizes the ROC manifold, a key metric for ranking performance, by recursively building a decision tree that "tournaments" candidate splitting rules.

What Problem Does This Paper Address?

Ranking problems, where we want to order items based on some criteria, are common in many fields like medicine and finance. While algorithms for bipartite ranking (two categories) are well-established, extending these to multipartite ranking (more than two categories) has been a significant challenge. The core difficulty lies in optimizing the "ROC manifold" (a generalization of the ROC curve for multiple categories) and its summary metrics like volume. Existing methods often reduce multipartite ranking to multiple bipartite problems, which can be inefficient or lose crucial information. This paper aims to provide a direct, efficient, and theoretically grounded algorithm for multipartite ranking that optimizes the ROC manifold.

Methods

The proposed TreeRank Tournament (TRT) algorithm builds upon the TreeRank algorithm, originally designed for bipartite ranking. TRT recursively partitions the feature space by constructing a ranking tree. At each node of the tree, instead of a single best split, TRT considers multiple candidate splits derived from bipartite subproblems. These candidates then "compete" in a "tournament" to determine the best split for that node, aiming to maximize the empirical Volume Under the ROC Surface (VUS). This tournament approach allows TRT to handle the complexity of multipartite ranking where a direct interpretation as a cost-sensitive error is not always possible. The algorithm is described as a recursive process involving:

  • LeafRank Runs: Running a base binary classification algorithm (like CART or SVM) on subproblems to generate candidate splits.
  • Tournament: Comparing these candidate splits based on their VUS contribution to select the best one.
  • Recursive Partitioning: Continuing this process until a desired tree depth is reached.

The paper also discusses theoretical aspects, including rate bounds for generalization ability and an adaptive piecewise linear approximation scheme for the optimal ROC surface.

Datasets

The paper evaluates the TRT algorithm on both synthetic and real-world datasets:

  • Synthetic Datasets:
    • Mixtures of Gaussian distributions in 2D.
  • Mixtures of uniform distributions on the unit square.
  • Real Datasets:
    • Cardiotocography (CTG) Data Set: Used for fetal heart rate analysis, with 2126 instances and 20 features.
  • LETOR benchmark datasets (MQ2007 and MQ2008): Used for information retrieval tasks, with 46 features.
  • Ordinal datasets (ERA, ESL, LEV, SWD): Datasets with ordered labels, often used in machine learning research.

The paper notes that some algorithms struggled to run on the LETOR datasets due to computational limitations.

Key Insights and Ideas

  • The "Tournament" as a Solution: The core innovation is the "tournament" mechanism for selecting splits in the multipartite case. This elegantly sidesteps the difficulty of directly interpreting multipartite VUS optimization as a simple cost-sensitive binary classification problem, which was a major hurdle for K>2.
  • Extending Bipartite Success: TRT successfully adapts the proven recursive partitioning strategy of TreeRank to the more complex multipartite setting, preserving its desirable properties.
  • ROC Manifold as the Target: The paper firmly grounds multipartite ranking in the optimization of the ROC manifold, treating it as the primary objective rather than relying on proxy metrics.
  • Piecewise Constant Scoring Function: The algorithm produces a piecewise constant scoring function whose ROC manifold can be viewed as an adaptive approximation of the optimal ROC manifold.
  • Theoretical Guarantees: The authors provide theoretical rate bounds for the generalization ability of TRT, offering statistical validation for its performance.

Key Results

  • Performance on Synthetic Data: For Gaussian mixtures, TRT performed comparably to kernel-based methods. For uniform mixtures, TRT outperformed competitors and achieved performance close to the optimal.
  • Performance on Real Data: TRT significantly outperformed competitors on the Cardiotocography dataset. On LETOR datasets, it performed slightly better than its competitors.
  • Computational Efficiency: While not explicitly detailed in terms of speedup, the paper suggests that TRT can be more efficient than some competitors, especially on datasets where other algorithms might crash.
  • Theoretical Bounds: The paper establishes theoretical bounds on the generalization error of TRT, demonstrating its statistical validity.

Limitations and Future Work

  • Computational Complexity: While TRT is presented as efficient, the paper acknowledges that extending the algorithm to the general K-partite case by considering all pairwise comparisons could increase computational demands.
  • Pruning Stage: The paper mentions that a pruning stage, similar to that in bipartite TreeRank, can be applied to optimize the ranking tree. However, the details and empirical impact of this stage are not extensively explored in this paper.
  • Committee-Based Methods: The authors suggest that bootstrap aggregating (bagging) techniques could be used to design committee-based multipartite ranking rules, potentially improving performance over single ranking trees. This is identified as a direction for future work.
  • Model Selection and Aggregation: Model selection analysis and aggregation strategies are explicitly stated as being beyond the scope of the current paper and will be addressed in future work.

Summary updated

Abstract

Whereas various efficient learning algorithms have been recently proposed to perform bipartite ranking tasks, cast as receiver operating characteristic (ROC) curve optimisation, no method fully tailored to K-partite ranking when K≥3 has been documented in the statistical learning literature yet. The goal is to optimise the ROC manifold, or summary criteria such as its volume, the gold standard for assessing performance in K-partite ranking. It is the main purpose of this paper to describe at length an efficient approach to recursive maximisation of the ROC surface, extending the TreeRank methodology originally tailored for the bipartite situation (i.e. when K=2). The main barrier arises from the fact that, in contrast to the bipartite case, the volume under the ROC surface criterion of any scoring rule taking K≥3 values cannot be interpreted as a cost-sensitive misclassification error and no method is readily available to perform the recursive optimisation stage. The learning algorithm we propose, called TreeRank Tournament (referred to as ‘TRT’ in the tables), breaks it and builds recursively an ordered partition of the feature space. It defines a piecewise scoring function whose ROC manifold can be remarkably interpreted as a statistical version of an adaptive piecewise linear approximant of the optimal ROC manifold. Rate bounds in sup norm describing the generalisation ability of the scoring rule thus built are established and numerical results illustrating the performance of the TRT approach, compared to that of natural competitors such as aggregation methods, are also displayed.
BibTeX
@article{clemencon2014treerank,
  author = {Stéphan Clémençon and Sylvain Robbiano},
  title = {{The TreeRank Tournament algorithm for multipartite ranking}},
  journal = {Journal of Nonparametric Statistics},
  year = {2014},
  doi = {10.1080/10485252.2014.967770},
}
Figure