Multiclass Capped ℓp-Norm SVM for Robust Classifications

Feiping Nie, Xiaoqian Wang, Heng HuangAAAI 2017 · OpenReview

Abstract

The Support Vector Machine (SVM) model is one of the most successful machine learning methods and has been successfully applied to solve numerous real-world applications. Because SVM methods typically use hinge loss or squared hinge loss functions for classification, they usually outperform other approaches, such as least square loss-based methods. However, like most supervised learning algorithms, they learn classifiers based on labeled training data without a specific strategy to handle noise. In many real-world applications, data outliers in the training set can misguide classifier learning, leading to suboptimal performance. To address this problem, we propose a novel capped $\ell_p$-norm SVM classification model by utilizing a capped $\ell_p$-norm based hinge loss in the objective, which can deal with both light and heavy outliers. We utilize this new formulation to naturally build a multiclass capped $\ell_p$-norm SVM. More importantly, we derive a novel optimization algorithm to efficiently minimize the capped $\ell_p$-norm based objectives and rigorously prove the convergence of the proposed algorithm. We present experimental results showing that employing the new capped $\ell_p$-norm SVM method can consistently improve classification performance, especially in cases where the data noise level increases.

Introduction

Standard Support Vector Machines (SVMs) are widely recognized for their effectiveness in classification tasks, primarily due to their use of "unilateral" loss functions like the hinge loss. These functions penalize data points only when they fall on the incorrect side of the decision boundary. However, a significant drawback of traditional SVMs is their sensitivity to outliers. In standard formulations, the penalty for a misclassified point increases linearly or quadratically with its distance from the boundary. In real-world datasets containing incorrectly labeled samples or extreme anomalies, these outliers can exert a disproportionate influence on the optimization process, "stretching" the decision boundary and degrading overall classification performance.

To address this, the authors introduce a robust variation of the SVM designed to handle noisy data by capping the loss function, thereby preventing outliers from dominating the model's learning process.

Methodology: Capped $\ell_p$-Norm Hinge Loss

The primary innovation of this work is the Capped $\ell_p$-Norm Hinge Loss. This approach modifies the standard hinge loss by introducing a threshold, $\epsilon$. When the loss for a specific data point exceeds this threshold, it is capped at $\epsilon$. This mechanism effectively tells the model to stop trying to fit points that are too far from the boundary, identifying them as likely outliers.

Comparison of various loss functions: (a) Hinge, (b) $\ell_1$-norm, (c) Squared hinge, (d) $\ell_2$-norm, and (e) the proposed Capped hinge loss which plateaus for large errors.

Key components of the method include:

  1. The Cap: The thresholding mechanism ensures that no single outlier can exert excessive "pull" on the classifier.
  2. The $\ell_p$-Norm: By utilizing an $\ell_p$-norm ($0 < p \leq 2$), the model gains flexibility in handling different types of noise (light vs. heavy outliers).
  3. Direct Multiclass Formulation: Unlike traditional "one-vs-rest" strategies that can create ambiguous classification regions, this model uses a unified multiclass objective based on slack variables.
  4. Optimization: Since capping the loss results in a non-smooth and non-convex objective, the authors developed a novel Re-weighted iterative algorithm. They rigorously proved that this algorithm converges to a local optimum, typically within fewer than 20 iterations.

Experimental Results

The researchers evaluated the CappedSVM against several benchmarks, including $k$-Nearest Neighbors (KNN), standard SVM, and Least Square Regression (LSReg), across six diverse datasets: Gene Expression (ALLAML, LUNG, Carcinomas, Prostate-GE), JAFFE facial expressions, and chemical/physical data (Wine, Abalone).

Performance and Robustness

  • Accuracy: CappedSVM achieved superior accuracy on 5 out of 6 datasets. Notably, on the LUNG dataset, it reached 98.03% accuracy, outperforming the standard SVM's 96.47%.
  • Noise Tolerance: The performance advantage of CappedSVM became more pronounced as the noise level in the training data increased, demonstrating its robustness.
  • Stability: The model showed less sensitivity to hyperparameter tuning compared to standard SVMs. The "cap" prevents extreme values from destabilizing the model across different regularization settings.

Conclusion

The Multiclass Capped $\ell_p$-Norm SVM offers a robust solution for classification in the presence of outliers. By incorporating an automated outlier rejection mechanism through capped loss, the model maintains high accuracy even in noisy environments. While the non-convex nature of the objective requires iterative optimization to reach a local optimum, empirical results demonstrate that the method is both computationally viable and highly effective for real-world applications.

Summary updated

Abstract

Support vector machine (SVM) model is one of most successful machine learning methods and has been successfully applied to solve numerous real-world application. Because the SVM methods use the hinge loss or squared hinge loss functions for classifications, they usually outperform other classification approaches, e.g. the least square loss function based methods. However, like most supervised learning algorithms, they learn classifiers based on the labeled data in training set without specific strategy to deal with the noise data. In many real-world applications, we often have data outliers in train set, which could misguide the classifiers learning, such that the classification performance is suboptimal. To address this problem, we proposed a novel capped Lp-norm SVM classification model by utilizing the capped `p-norm based hinge loss in the objective which can deal with both light and heavy outliers. We utilize the new formulation to naturally build the multiclass capped Lp-norm SVM. More importantly, we derive a novel optimization algorithms to efficiently minimize the capped Lp-norm based objectives, and also rigorously prove the convergence of proposed algorithms. We present experimental results showing that employing the new capped Lp-norm SVM method can consistently improve the classification performance, especially in the cases when the data noise level increases.
BibTeX
@inproceedings{nie2017multiclass,
  author = {Feiping Nie and Xiaoqian Wang and Heng Huang},
  title = {{Multiclass Capped ℓp-Norm SVM for Robust Classifications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=By4FU6euZS},
}
Figure