Smooth Ranking SVM via Cutting-Plane Method

Erhan Can Ozcan, Berk Görgülü, Mustafa Gökçe Baydogan, Ioannis Ch. PaschalidisarXiv 2024 · DOI · arXiv

Introduction

In many real-world classification tasks, such as credit card fraud detection or rare disease diagnosis, datasets are often highly imbalanced. In these scenarios, the "positive" class represents only a small fraction of the total data. Standard machine learning models that aim to maximize overall accuracy often fail because they can achieve high scores by simply predicting the majority class, rendering them practically useless for identifying rare events.

To address this, researchers frequently turn to the Area Under the Curve (AUC) metric, which evaluates a model's ability to rank positive instances higher than negative ones. However, direct optimization of AUC is challenging because the metric is non-continuous and non-differentiable. While Ranking Support Vector Machines (SVMs) have been developed to tackle this, they often struggle with non-linear data or overfitting. This paper introduces the Smooth Ranking-CG Prototype algorithm, a novel approach that maximizes AUC while ensuring model stability and interpretability.

Methodology: Smooth Ranking-CG Prototype

The proposed method builds a score function based on the Euclidean distance between data points and a set of "prototype" points. It incorporates several technical innovations to improve performance and stability:

  1. Cutting-Plane and Column Generation: Rather than utilizing all features simultaneously, the algorithm starts with an empty set and iteratively adds "prototypes"—effectively new features—that offer the greatest potential for model improvement. This process involves solving a dual optimization problem.
  2. Smoothing Penalty: A critical advancement over previous iterations is the introduction of a smoothing penalty. While earlier versions strictly bounded weights, this method allows weights to be free but penalizes significant changes in weights between iterations ($|w^{(t)} - w^{(t)}_{old}|$). This "smoothing" mechanism prevents erratic jumps in the model's logic as new prototypes are integrated.
  3. Sub-problem Optimization: To identify the optimal next prototype point, the authors solve a non-linear sub-problem using the Adam optimizer. To avoid local optima, the search is initialized using existing training samples.

Experimental Setup

The researchers evaluated the Smooth Ranking-CG Prototype against 73 binary classification datasets from the UCI and KEEL repositories. These datasets represent a diverse range of domains with varying characteristics:

  • Feature Count: Ranging from 3 to 60 features.
  • Imbalance Ratio: Spanning from nearly balanced (0.87) to extremely imbalanced (0.01).
  • Sample Size: Including small clinical datasets and larger sets with over 1,000 instances.

The performance was compared against several benchmarks, including $L_1$, $L_2$, and $L_\infty$ versions of Ranking SVM.

Key Results and Discussion

The experimental results highlight the effectiveness of the smoothing approach in both performance and model complexity.

Figure 3: XOR dataset visualization and Test AUC performance across iterations.

Performance and Stability

As shown in Figure 3, the "Smooth" version of the algorithm maintains a steady upward trajectory in AUC on challenging non-linear problems like the noisy XOR dataset. In contrast, "Unbounded" versions tend to fluctuate significantly and eventually overfit. Across the 73 datasets, the Smooth Ranking-CG Prototype achieved the highest test AUC in 25 cases, proving highly competitive with traditional Ranking SVM variants.

Model Sparsity and Interpretability

One of the most significant findings is the extreme sparsity of the resulting models. On average, the proposed method uses only about 2% of available features or prototypes.

Figure 5: Comparison of AUC performance and feature usage across different ranking methods.

As detailed in Figure 5, while standard Ranking SVMs often utilize between 73% and 100% of features, the Smooth Ranking-CG Prototype produces much leaner models. This high degree of sparsity significantly enhances model interpretability without sacrificing competitive performance.

Conclusion

The Smooth Ranking-CG Prototype offers a robust solution for maximizing AUC in imbalanced datasets. By penalizing the "velocity" of weight changes rather than imposing hard bounds, the algorithm achieves superior stability and produces highly interpretable, sparse models.

Future work may explore more sophisticated initialization strategies for the first prototype point and the implementation of an adaptive smoothing parameter to further refine the convergence process. While the non-convex nature of the sub-problem remains a challenge, the current initialization strategy effectively mitigates the risk of getting stuck in local optima.

Summary updated

Abstract

The most popular classification algorithms are designed to maximize classification accuracy during training. However, this strategy may fail in the presence of class imbalance since it is possible to train models with high accuracy by overfitting to the majority class. On the other hand, the Area Under the Curve (AUC) is a widely used metric to compare classification performance of different algorithms when there is a class imbalance, and various approaches focusing on the direct optimization of this metric during training have been proposed. Among them, SVM-based formulations are especially popular as this formulation allows incorporating different regularization strategies easily. In this work, we develop a prototype learning approach that relies on cutting-plane method, similar to Ranking SVM, to maximize AUC. Our algorithm learns simpler models by iteratively introducing cutting planes, thus overfitting is prevented in an unconventional way. Furthermore, it penalizes the changes in the weights at each iteration to avoid large jumps that might be observed in the test performance, thus facilitating a smooth learning process. Based on the experiments conducted on 73 binary classification datasets, our method yields the best test AUC in 25 datasets among its relevant competitors.
BibTeX
@misc{ozcan2024smooth,
  author = {Erhan Can Ozcan and Berk Görgülü and Mustafa Gökçe Baydogan and Ioannis Ch. Paschalidis},
  title = {{Smooth Ranking SVM via Cutting-Plane Method}},
  year = {2024},
  eprint = {2401.14388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.14388},
}
Figure