Adaptive partitioning schemes for bipartite ranking - How to grow and prune a ranking tree

Stéphan Clémençon, Marine Depecker, Nicolas VayatisMachine Learning 2011 · DOI · OpenReview

Introduction

In machine learning, the distinction between classification and ranking is fundamental yet often overlooked in model design. While classification focuses on local label assignment (e.g., "is this transaction fraudulent?"), bipartite ranking addresses a global ordering problem: "which transactions are most likely to be fraudulent?" Standard decision tree algorithms like CART are optimized for local misclassification error, which does not necessarily translate to maximizing the Area Under the Curve (AUC)—the standard metric for ranking performance.

This paper presents TreeRank, a robust framework for bipartite ranking using recursive partitioning. The authors address two critical challenges in tree-based ranking: establishing optimal splitting rules that account for the global nature of AUC, and developing pruning strategies to prevent overfitting in a ranking context.

The TreeRank Framework

TreeRank operates by recursively partitioning the feature space into cells. Unlike traditional classification trees, TreeRank produces both a partition and a specific permutation of the resulting cells. This ordering defines a ranking function that approximates the optimal ROC curve.

A key theoretical insight of the paper is the suboptimality of standard Bayes classifiers for ranking. Unless the positive class probability is exactly 0.5, a classifier thresholded at 0.5 is suboptimal for AUC. Ranking requires an understanding of the entire distribution of class probabilities across the feature space, necessitating a more holistic approach to tree construction.

Methodology: Growing and Pruning

LeafRank Splitting

The authors introduce the LeafRank splitting rule, which reframes the node-splitting process as a cost-sensitive classification task. In this setup, the "cost" is data-dependent, determined by the rate of positive instances within the specific node being split. This innovation allows any standard classification algorithm to be repurposed as a splitting rule for a ranking tree, ensuring that each cut contributes to the global maximization of the AUC.

Pruning Strategies

Because ranking is a global task, errors in early splits "stack" rather than being isolated to specific branches. This makes pruning even more vital than in classification. The authors propose two primary methods:

  1. Cross-Validation Pruning: An adaptation of CART's cost-complexity pruning that utilizes a linear complexity penalty to identify the subtree with the highest cross-validated AUC.
  2. Structural AUC Maximization: A theoretical approach using penalty terms derived from U-process theory. This allows for effective model selection without the need for a separate validation set, providing a more direct path to the "right-sized" tree.

Experimental Results

The TreeRank methodology was evaluated against Logistic Regression and RankBoost using both synthetic and real-world datasets.

Synthetic Benchmarks

The algorithm was tested on mixtures of uniform distributions and conditional Gaussian distributions. In these simulations, TreeRank demonstrated a remarkable ability to retrieve the underlying bi-level sets of the regression function, effectively learning the complex geometry of the data and approximating the optimal ROC curve with first-order splines.

Real-World Performance

On the UCI Breast Cancer dataset, TreeRank achieved a test AUC of 0.923, significantly outperforming Logistic Regression, which scored 0.856. Similar results were observed in credit scoring tasks. The pruning methods proved essential; while unpruned trees showed high training AUC, they suffered from significant overfitting. The proposed pruning strategies successfully identified subtrees that maintained high generalization performance on unseen data.

Discussion and Future Directions

While TreeRank offers a powerful and interpretable "white-box" model for ranking, it shares the common limitation of recursive partitioning: instability. Small changes in training data can lead to significantly different tree structures. Furthermore, the hierarchical nature of the algorithm can lead to a "pileup of error" across levels.

The authors suggest that the logical evolution of this work lies in aggregation strategies. Much as Random Forests improved upon the stability of CART, the development of "Ranking Forests" or bagging techniques for TreeRank could mitigate variance and further enhance predictive power while maintaining the framework's focus on AUC maximization.

Summary updated

Abstract

Recursive partitioning methods are among the most popular techniques in machine learning. The purpose of this paper is to investigate how to adapt this methodology to the bipartite ranking problem. Following in the footsteps of the TreeRank approach developed in Clémençon and Vayatis (Proceedings of the 2008 Conference on Algorithmic Learning Theory, 2008 and IEEE Trans. Inf. Theory 55(9):4316–4336, 2009), we present tree-structured algorithms designed for learning to rank instances based on classification data. The main contributions of the present work are the following: the practical implementation of the TreeRank algorithm, well-founded solutions to the crucial issues related to the splitting rule and the choice of the “right” size for the ranking tree. From the angle embraced in this paper, splitting is viewed as a cost-sensitive classification task with data-dependent cost. Hence, up to straightforward modifications, any classification algorithm may serve as a splitting rule. Also, we propose to implement a cost-complexity pruning method after the growing stage in order to produce a “right-sized” ranking sub-tree with large AUC. In particular, performance bounds are established for pruning schemes inspired by recent work on nonparametric model selection. Eventually, we propose indicators for variable importance and variable dependence, plus various simulation studies illustrating the potential of our method.
BibTeX
@article{clemencon2011adaptive,
  author = {Stéphan Clémençon and Marine Depecker and Nicolas Vayatis},
  title = {{Adaptive partitioning schemes for bipartite ranking - How to grow and prune a ranking tree}},
  journal = {Machine Learning},
  year = {2011},
  doi = {10.1007/s10994-010-5190-y},
}
Figure