Multiclass Capped _p-Norm SVM for Robust Classifications

AAAI 2017

TL;DR

This paper introduces a novel "capped _p-norm SVM" that significantly improves classification accuracy in the presence of noisy or outlier data. By modifying the loss function to cap extreme errors, the method achieves more robust and stable performance compared to traditional SVMs, especially in real-world scenarios where data imperfections are common.

What Problem Does This Paper Address?

Traditional Support Vector Machine (SVM) models, while highly successful, are susceptible to errors in the training data. Specifically, the hinge loss and squared hinge loss functions, commonly used in SVMs, can be heavily influenced by outliers (e.g., mislabeled data points or data points that are significantly different from others in their class). These outliers can "misguide" the classifier's learning process, leading to suboptimal performance. While some methods have focused on feature selection or reducing support vectors for sparsity, few have directly addressed the robustness issue caused by data outliers. This paper aims to bridge this gap by developing a classification model that is inherently robust to both light and heavy outliers.

Methods

The core innovation is the introduction of a capped _p-norm based loss function for SVMs. Unlike standard hinge loss, which can grow infinitely with outliers, the capped _p-norm loss caps the maximum penalty for any data point, regardless of how far it deviates. This is achieved by taking the minimum of the standard loss raised to the power of _p and a predefined cap value, ε.

The authors then extend this concept to multiclass classification. Instead of relying on traditional one-vs-one or one-vs-rest strategies (which can suffer from label ambiguity), they propose a new multiclass SVM formulation that directly handles multiple classes.

To efficiently optimize this new, non-smooth, and potentially non-convex objective function, they develop a novel optimization algorithm. This algorithm is designed to solve a general class of problems involving concave functions and is proven to converge to a stationary point, which is typically a local minimum. The optimization process involves an iterative re-weighted method.

Datasets

The paper evaluates the proposed CappedSVM method on six benchmark datasets:

  • ALLAML
  • LUNG
  • Carcinomas
  • Prostate-GE
  • JAFFE
  • Wine

These datasets represent a mix of gene expression microarray data, image data, and daily life data, providing a diverse testbed for the algorithm. No new benchmarks were introduced; the focus was on evaluating performance on existing, well-characterized datasets.

Key Insights and Ideas

  • Outliers are a significant problem for standard classifiers: The paper clearly illustrates how traditional loss functions are sensitive to extreme data points, leading to reduced classification accuracy.
  • Capping the loss is key to robustness: The capped _p-norm loss function provides a principled way to mitigate the impact of outliers by limiting their influence on the model training.
  • A unified multiclass formulation is beneficial: Moving beyond one-vs-rest/one-vs-one strategies for multiclass problems can avoid ambiguity and lead to a more direct solution.
  • Novel optimization is crucial for non-smooth objectives: The development of a specialized, theoretically grounded optimization algorithm is essential for making the capped _p-norm SVM practical.
  • Parameter sensitivity is reduced: The proposed method appears to be less sensitive to parameter tuning compared to other methods, simplifying its application.

Key Results

The experimental results demonstrate that the proposed CappedSVM method consistently improves classification performance, particularly in scenarios where data noise or outliers are present. The paper shows that CappedSVM outperforms other methods like k-Nearest Neighbors (KNN), standard SVM, and Least Squares Support Vector Machine (LSSVM) across the tested datasets. For instance, on the JAFFE dataset, CappedSVM achieved 100.00% accuracy, outperforming SVM (99.59%) and LSSVM (100.00% - though the paper notes LSSVM was tuned to its best). The paper also includes plots showing classification accuracy under different parameter settings, highlighting the stability and robustness of CappedSVM compared to other methods.

Limitations and Future Work

  • Parameter ε selection: While the paper mentions a heuristic way to set ε (10% of data with largest noise), a more systematic approach for selecting this parameter could be beneficial.
  • Theoretical guarantees for global optimality: The optimization algorithm is proven to converge to a stationary point, which is usually a local minimum. Proving convergence to a global minimum for the general capped _p-norm problem would be a significant advancement.
  • Application to other capped norm problems: The authors suggest their optimization framework can be applied to other capped norm applications (e.g., capped _p-norm logistic regression), which could be a fruitful area for future research.

Summary updated

BibTeX
@inproceedings{2017multiclass,
  title = {{Multiclass Capped \_p-Norm SVM for Robust Classifications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
}
Figure