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.
Key components of the method include:
- The Cap: The thresholding mechanism ensures that no single outlier can exert excessive "pull" on the classifier.
- 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).
- 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.
- 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