Functional Bipartite Ranking: a Wavelet-Based Filtering Approach

Stéphan Clémençon, Marine Depecker

Abstract

This article addresses the bipartite ranking issue from the perspective of functional data analysis (FDA). Given a training set of independent realizations of a second-order random function with a locally smooth autocorrelation structure and binary labels, the objective is to learn a scoring function with an optimal ROC curve. By leveraging wavelet-based approximations, we select compact finite-dimensional representations of input curves adaptively. This approach builds accurate ranking rules using recent advances in multivariate ranking with binary feedback. Numerical experiments illustrate the performance of these functional bipartite ranking methods.

Introduction: The Challenge of Functional Ranking

In domains like medical diagnosis (EEG signals), anomaly detection, and credit scoring, data often arrives as functional data—continuous curves or time-series rather than static vectors. While functional classification is well-established, Functional Bipartite Ranking remains a frontier.

Ranking is distinct from classification: the goal is not just to assign a label, but to order observations such that positive instances consistently appear above negative ones. This is mathematically equivalent to maximizing the Area Under the ROC Curve (AUC). The primary hurdle is the infinite-dimensional nature of functional data. Traditional "global filtering" methods (like PCA or standard wavelet transforms) reduce dimensions once for the entire dataset, often losing the local, high-frequency details critical for precise ranking.

Methodology: Local Adaptive Filtering

The proposed framework extends the TreeRank algorithm to the functional domain by introducing a "local adaptive filtering" strategy.

Wavelet-Based Representation

Instead of data-dependent bases like Karhunen-Loève, the authors utilize wavelets. Wavelets are uniquely suited for functional data because they capture both broad trends and localized "fine details" across different scales.

Recursive Ranking and LeafRank

The core innovation is performing feature selection locally at every node of the ranking tree. As the TreeRank algorithm recursively partitions the data into smaller subsets (cells), the importance of specific wavelet coefficients is re-evaluated for each subset.

Recursive partitioning in TreeRank and local node splitting with LeafRank.

At each split, the algorithm identifies the $N$ coefficients with the highest local variance. These features then drive a cost-sensitive classifier (LeafRank), such as CART or SVM, to further refine the ranking within that specific cell. This ensures that the ranking rule adapts to the specific characteristics of the data at different parts of the distribution.

Experimental Results

The method was evaluated on synthetic "toy" datasets and a real-world Brain Computer Interface (BCI) benchmark.

Synthetic Scenarios

Two cases were tested:

  • Case A: Well-separated classes (Optimal AUC ≈ 0.94).
  • Case B: Highly overlapping classes (Optimal AUC ≈ 0.71).

BCI Benchmark

Using brain signal data from 203 sensors, the task was to rank observations to distinguish between audio and visual stimuli. The local adaptive method achieved high AUC scores (up to 0.96), demonstrating its effectiveness in high-dimensional, noisy biological contexts.

ROC curves illustrating the performance of ranking models across different scenarios.

The results consistently showed that "Functional TreeRank" (local filtering) outperformed "Filtered TreeRank" (global filtering), sometimes by as much as 10% in AUC. Furthermore, the method proved efficient, maintaining high accuracy while using as little as 0.5% of the signal's original coefficients.

Key Insights and Discussion

  • The Power of Locality: Global filtering assumes a uniform feature importance. Local filtering recognizes that different signal resolutions become relevant as the ranking becomes more granular.
  • Nonlinear Selection: Choosing coefficients based on local variance (nonlinear selection) is significantly more effective than simply taking the first $N$ coefficients (linear selection).
  • Robustness: The local adaptive nature compensates for potential mismatches between the chosen wavelet basis and the underlying stochastic process.

Conclusion and Future Work

This wavelet-based filtering approach provides a robust framework for ranking functional data. While computationally more intensive than global methods, the gains in AUC are substantial. Future research will focus on scaling this approach to "Big Data" functional sets and exploring more sophisticated local regularization techniques beyond variance-based selection.

Summary updated

Abstract

It is the main goal of this article to address the bipartite ranking issue from the perspective of functional data analysis (FDA). Given a training set of independent realizations of a (possibly sampled) second-order random function with a (locally) smooth autocorrelation structure and to which a binary label is randomly assigned, the objective is to learn a scoring function s with optimal ROC curve. Based on linear/nonlinear wavelet-based approximations, it is shown how to select compact finite dimensional representations of the input curves adaptively, in order to build accurate ranking rules, using recent advances in the ranking problem for multivariate data with binary feedback. Beyond theoretical considerations, the performance of the learning methods for functional bipartite ranking proposed in this paper are illustrated by numerical experiments.
BibTeX
@inproceedings{clemencon2013functional,
  author = {Stéphan Clémençon and Marine Depecker},
  title = {{Functional Bipartite Ranking: a Wavelet-Based Filtering Approach}},
  booktitle = {SPIRE},
  year = {2013},
}
Figure