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.
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.
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