Functional Bipartite Ranking: a Wavelet-Based Filtering Approach

Stéphan Clémençon, Marine Depecker

TL;DR

This paper introduces a novel framework for ranking functional data (such as time-series or sensor curves) by combining wavelet-based dimensionality reduction with the TreeRank algorithm. The core innovation is a "local adaptive filtering" strategy that selects the most relevant features at each stage of a recursive ranking tree, significantly outperforming traditional global filtering methods.

What Problem Does This Paper Address?

In many real-world applications—like anomaly detection in signals, medical diagnosis from EEG, or credit scoring—data comes in the form of functional data (curves or functions) rather than simple vectors. While Functional Classification (predicting a binary label for a curve) is well-studied, Functional Bipartite Ranking is much less explored.

Ranking is a more complex task than classification: instead of just deciding if a curve is "positive" or "negative," the goal is to order all observations so that positive instances appear at the top of the list with the highest probability. This is equivalent to optimizing the Area Under the ROC Curve (AUC). The challenge is that functional data is inherently infinite-dimensional. Standard approaches "filter" the data once (e.g., using PCA or wavelets) to reduce dimensions before ranking, but this global preprocessing often discards fine-grained local information essential for accurate ranking.

Methods

The authors propose an extension of the TreeRank algorithm specifically designed for functional data. Their approach involves two main components:

  1. Wavelet-Based Filtering: Instead of using the Karhunen-Loève (KL) basis (which is data-dependent and hard to estimate), they use wavelets. Wavelets are excellent at capturing both the "gross structure" and "fine details" of stochastic processes with varying degrees of smoothness.
  2. Local Adaptive Filtering (The "Aha!" Moment): This is the paper's primary contribution. Rather than filtering the entire dataset once at the beginning, the algorithm performs filtering locally at every node of the ranking tree.
  3. As the tree grows and splits the data into smaller subsets (cells), the algorithm re-evaluates which wavelet coefficients are most important within that specific subset.
  4. At each split, it selects the $N$ coefficients with the highest local variance and uses them to train a cost-sensitive classifier (like CART) to further refine the ranking.

The paper also provides theoretical "distortion rates," proving that even if wavelets aren't the "perfect" basis for a process, the loss in AUC remains bounded and decreases as more coefficients are included.

Datasets

The authors evaluate their method on two types of data:

  • Synthetic "Toy" Examples: Curves generated using Beylkin wavelets. They created two scenarios: Case a (well-separated classes, optimal AUC = 0.94) and Case b (highly overlapping classes, optimal AUC = 0.71).
  • BCI (Brain Computer Interface) Benchmark: A real-world dataset consisting of brain signals from 203 sensors over 121 time points. The task is to rank observations to distinguish between audio and visual stimuli.

Key Insights and Ideas

  • The Power of Locality: Global filtering assumes that the same features are useful for distinguishing "very positive" instances from "somewhat positive" ones. Local filtering recognizes that different resolution levels of the signal may be relevant at different parts of the ranking distribution.
  • Nonlinear vs. Linear Selection: The authors show that "nonlinear" selection—choosing the $N$ coefficients with the highest variance regardless of their position—is far superior to "linear" selection (just taking the first $N$ coefficients).
  • Robustness to Basis Choice: Even if the wavelet basis used for filtering doesn't perfectly match the basis used to generate the signal, the local adaptive nature of the algorithm compensates for the mismatch, maintaining high ranking performance.

Key Results

  • Performance Gain: In synthetic experiments, the "Functional TreeRank" (local filtering) consistently outperformed "Filtered TreeRank" (global filtering). In some cases, local filtering provided a 10% increase in AUC.
  • Efficiency: The method remains accurate even when using a very small percentage of available coefficients (e.g., keeping only 0.5% to 5% of the signal's length).
  • Real-World Success: On the BCI dataset, the method achieved high AUC scores (up to 0.96 in some configurations), proving its utility in high-dimensional, noisy biological signal processing.

Limitations and Future Work

  • Sample Size Sensitivity: The real-world BCI experiments showed relatively high standard deviations in AUC. This suggests that while the method is powerful, local feature selection requires a sufficient number of observations in each node to remain stable.
  • Computational Complexity: Performing a wavelet transform and feature selection at every node of a tree is more computationally demanding than a single global preprocessing step.
  • Future Directions: The authors suggest exploring other local regularization techniques beyond simple variance-based coefficient selection and testing the framework on "Big Data" functional datasets where high variability across resolution levels is common.

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},
}

Loading related content...

Figure