Active Bipartite Ranking

James Cheshire, Stéphan Clémençon, Vincent LaurentOpenalex Unknown 2023 · DOI · OpenAlex

TL;DR

This paper introduces the first rigorous framework for active bipartite ranking, a task where an algorithm sequentially chooses which data points to label to learn how to rank "positive" instances above "negative" ones. The authors propose active-rank, an elimination-based algorithm that provides strong theoretical guarantees (PAC-learning) and demonstrates that active sampling can significantly reduce the number of labels needed to achieve a near-optimal ROC curve compared to standard passive learning.

What Problem Does This Paper Address?

In many real-world scenarios—like credit scoring, medical diagnosis, or anomaly detection—we don't just want to know if a case is "positive" or "negative." We want to rank them. We want the person most likely to default on a loan or the patient most likely to have a disease at the very top of our list. This is "bipartite ranking," and it is typically evaluated using the Receiver Operating Characteristic (ROC) curve.

While active learning (where the model asks for specific labels) is well-understood for classification, it is much trickier for ranking. In classification, you mostly care about points near the decision boundary (e.g., a 50% probability). In ranking, the problem is "global": to place a point correctly in a list, you need to understand how it compares to all other points across the entire distribution. This paper fills a major gap in the literature by providing a formal strategy for selective sampling in this global context.

Methods

The authors focus on a setting where the feature space is one-dimensional and the "true" probability of being positive (the posterior $\eta(x)$) is piecewise constant on a grid of size $K$.

The core of their contribution is the active-rank algorithm. Here’s how it works:

  1. Active Set: It maintains a set of "active" grid points that still need more samples.
  2. Sequential Sampling: In each round, it samples points uniformly from the active set.
  3. Confidence Bounds: It calculates Upper and Lower Confidence Bounds (UCB and LCB) for the posterior probability of each grid point using Kullback-Leibler (KL) divergence.
  4. Elimination: A point is removed from the active set (it "stops" being sampled) once its confidence interval is small enough that its relative position on the ROC curve is determined within a precision of $\epsilon$.
  5. Final Ranking: Once all points are eliminated, the algorithm outputs a ranking based on the estimated means.

Crucially, the stopping criterion isn't just local; it depends on a global threshold that ensures the final learned ROC curve is within $\epsilon$ distance (in the sup-norm) of the optimal ROC curve.

Datasets

The paper evaluates the algorithm using synthetic datasets designed to test different "shapes" of the ranking problem:

  • Scenario 1: A simple case with 4 distinct levels and 16 grid cells.
  • Scenario 2: A smooth, increasing power-law curve ($x^4$) with 64 cells.
  • Scenario 3: A "jumpy" version of Scenario 2, created by sub-sampling the curve.
  • Scenario 4: A non-monotonic case where some cells have "dips" or "spikes" in probability, testing the algorithm's robustness against noisy ranking signals.

Key Insights and Ideas

  • Ranking is Harder than Classification: The authors show that the "complexity" of a ranking problem depends on the local flatness of the posterior function. If many points have very similar probabilities of being positive, you need many more samples to rank them correctly.
  • The "Gap" Matters: They define a problem-dependent complexity measure ($H_i$) that quantifies how difficult it is to distinguish a point from its neighbors on the ROC curve.
  • Near-Optimal Efficiency: The authors prove both an upper bound (how many samples active-rank needs) and a lower bound (the minimum samples any algorithm would need). These bounds match up to logarithmic factors, meaning their algorithm is nearly as efficient as theoretically possible.

Key Results

  • PAC Guarantee: The paper proves that active-rank is $(\epsilon, \delta)$-PAC, meaning with high probability ($1-\delta$), the resulting ROC curve will be within $\epsilon$ of the optimum.
  • Empirical Performance: In simulations, active-rank consistently outperformed:
  • Passive Rank: Uniformly sampling points.
  • Active Classification: Only sampling points near the 0.5 probability threshold.
  • Naive Rank: Sampling points with the highest uncertainty without considering the global ROC structure.
  • Efficiency: On complex distributions (like the $x^4$ curve), active-rank achieved much lower "regret" (distance from the optimal ROC) with significantly fewer samples than its competitors.

Limitations and Future Work

  • Dimensionality: The current work is restricted to 1D feature spaces. Extending this to high-dimensional data is a significant challenge because the "grid" approach suffers from the curse of dimensionality.
  • Smoothness Assumptions: The model assumes the posterior is piecewise constant. The authors suggest that future work should explore "smooth" posteriors (e.g., Hölder-continuous functions), which would require the algorithm to adaptively choose the grid size itself.
  • Computational Complexity: As the number of grid cells $K$ grows, the computation time increases. The authors note that for very large $K$, more optimized implementation strategies would be required.

Summary updated

Abstract

In this paper, we develop an active learning framework for the bipartite ranking problem.Motivated by numerous applications, ranging from supervised anomaly detection to credit-scoring through the design of medical diagnosis support systems, and usually formulated as the problem of optimizing (a scalar summary of) the ROC curve, bipartite ranking has been the subject of much attention in the passive context.Various dedicated algorithms have been recently proposed and studied by the machine-learning community.In contrast, active bipartite ranking rule is poorly documented in the literature.Due to its global nature, a strategy for labeling sequentially data points that are difficult to rank w.r.t. to the others is required.This learning task is much more complex than binary classification, for which many active algorithms have been designed.It is the goal of this article to provide a rigorous formulation of such a selective sampling approach.We propose a dedicated algorithm, referred to as active-rank, which aims to minimise the distance between the ROC curve of the ranking function built and the optimal one, w.r.t. the sup norm.We show that, for a fixed confidence level and probability , active-rank is PAC(, ).In addition, we provide a problem dependent upper bound on the expected sampling time of active-rank and also demonstrate a problem dependent lower bound on the expected sampling time of any PAC(, ) algorithm.Beyond the theoretical analysis carried out, numerical results are presented, providing strong empirical evidence of the performance of the algorithm proposed, which compares favorably with more naive approaches.
BibTeX
@inproceedings{cheshire2023active,
  author = {James Cheshire and Stéphan Clémençon and Vincent Laurent},
  title = {{Active Bipartite Ranking}},
  booktitle = {Openalex Unknown},
  year = {2023},
  doi = {10.52202/075280-2424},
}

Loading related content...

Figure