Non-parametric Online AUC Maximization

Balázs Szörényi, Snir Cohen, Shie MannorECML/PKDD 2017 · DOI

TL;DR

This paper tackles the challenge of maximizing the Area Under the ROC Curve (AUC) in online and one-pass settings, where data arrives sequentially. They propose a novel algorithm, KNNOAM, based on k-Nearest Neighbors, which overcomes limitations of existing methods by achieving asymptotic optimality and not requiring parameter tuning, while also demonstrating superior performance on benchmark datasets.

What Problem Does This Paper Address?

The Area Under the ROC Curve (AUC) is a crucial metric for evaluating binary classifiers, especially in imbalanced datasets, finding applications in fields like bioinformatics and anomaly detection. While maximizing AUC is desirable, it's a notoriously difficult problem, particularly in online and one-pass settings where data is processed sequentially without storing the entire dataset. Existing methods often resort to optimizing surrogate loss functions instead of the true AUC, which can lead to suboptimal solutions, especially when restricted to simple hypothesis classes like linear functions. Furthermore, these methods typically require parameter tuning, necessitating multiple passes over the data, which is incompatible with the online setting. This paper aims to address these shortcomings by proposing a method that directly optimizes AUC, is asymptotically optimal, and works efficiently in the online and one-pass settings without parameter tuning.

Methods

The core of this paper's contribution lies in its proposed algorithm, KNNOAM (KNN Online AUC Maximization). Instead of relying on surrogate losses, KNNOAM leverages the k-Nearest Neighbors (k-NN) estimate of the conditional probability function, $\eta(x) = P[Y=1|X=x]$. The theoretical foundation is built upon a theorem (Theorem 2) that establishes a bound on the regret of such estimates, showing that good estimates of $\eta(x)$ lead to good AUC maximization. KNNOAM uses a specific k-NN estimate called DGKL (Devroye, Györfi, Krzyzak, Lugosi) which is shown to converge under certain conditions on the stepsize $k_n$. The algorithm is designed to be efficient, with an important feature being its ability to be implemented efficiently using structures like Cover Trees, allowing for fast neighbor searches. A key advantage highlighted is that KNNOAM does not require parameter tuning, unlike its competitors, which simplifies its application and aligns with the online learning paradigm.

Datasets

The paper evaluates KNNOAM on sixteen benchmark datasets. These datasets are sourced from LIBSVM and the UCI Machine Learning Repository. The datasets are diverse in terms of instance and feature counts. Notably, half of the datasets (segment, satimage, vowel, letter, poker, usps, connect-4, acoustic and vehicle) were originally multi-class and were converted into imbalanced binary datasets by selecting one class as positive and the rest as negative, ensuring the ratio of negative to positive instances ($T^-/T^+$) is below 50. Features for all datasets were rescaled linearly to [-1, 1].

Key Insights and Ideas

  • Surrogate losses are problematic: The paper strongly argues that optimizing surrogate losses for AUC can lead to suboptimal solutions, especially when the hypothesis class is restricted (e.g., linear functions). This is demonstrated with a concrete example where a method optimizing a surrogate loss fails to find the true AUC optimum.
  • k-NN as a principled approach: By directly linking AUC maximization to the estimation of conditional probabilities ($\eta(x)$), the paper provides a theoretically grounded approach. The k-NN estimator is shown to be a viable candidate for this task.
  • No parameter tuning is a game-changer: The lack of parameter tuning in KNNOAM is presented as a significant practical advantage, making it more suitable for online settings and simplifying its deployment compared to methods requiring extensive hyperparameter optimization.
  • Empirical superiority: KNNOAM not only has theoretical advantages but also demonstrates superior or competitive performance across a majority of the benchmark datasets, often with significant improvements.

Key Results

In the online setting, KNNOAM outperforms the four compared state-of-the-art algorithms on 12 out of 16 datasets. In 10 of these datasets, the improvement is significant, with KNNOAM converging to much lower empirical AUC loss. The paper also highlights that KNNOAM exhibits a smoother convergence compared to its competitors, whose performance can be unstable. For the one-pass setting, the results are similar, with KNNOAM being better or at least competitive. Furthermore, KNNOAM is often the fastest algorithm among the compared ones in the one-pass setting.

Limitations and Future Work

The authors acknowledge that while KNNOAM is a significant step forward, it's not necessarily the ultimate solution. They suggest several avenues for future research:

  • Combining with metric learning: Exploring the integration of KNNOAM with metric learning techniques could extend its applicability to more diverse and complex domains.
  • Adversarial setting: Investigating the problem of maximizing AUC in an adversarial setting is identified as an important open question that current results do not fully address.
  • Dimensionality Reduction: While not a limitation of KNNOAM itself, the paper notes that like other methods, k-NN can suffer from dimensionality issues. They suggest using dimensionality reduction techniques like online PCA as a preprocessing step to maintain good AUC performance while mitigating runtime issues.

Summary updated

BibTeX
@inproceedings{szorenyi2017non,
  author = {Balázs Szörényi and Snir Cohen and Shie Mannor},
  title = {{Non-parametric Online AUC Maximization}},
  booktitle = {ECML/PKDD},
  year = {2017},
  doi = {10.1007/978-3-319-71246-8\_35},
}
Figure