One-sided Support Vector Regression for Multiclass Cost-sensitive Classification

Han-Hsing Tu, Hsuan-Tien LinICML 2010 · OpenReview

TL;DR This paper introduces a novel approach to multiclass cost-sensitive classification by reducing the problem to "one-sided regression." By modifying Support Vector Regression (SVR) to penalize predictions only when they violate specific cost thresholds, the authors create RED-OSSVR—an algorithm that provides theoretical guarantees for minimizing total error costs and empirically outperforms existing SVM-based methods.

The Challenge of Cost-Sensitive Classification

In standard machine learning classification, all errors are treated equally; the goal is simply to minimize the overall error rate. However, in the real world, different mistakes carry drastically different consequences. For example, in medical diagnosis, predicting a healthy patient as sick (a false positive) might cost a few hundred dollars in extra testing, but predicting a sick patient as healthy (a false negative) could cost a life.

This is known as cost-sensitive classification. While well-understood for binary problems, multiclass cost-sensitive classification is notoriously difficult. Existing approaches usually try to reduce the problem to standard binary classification by tweaking the "weights" (importance) of training examples. Unfortunately, these methods either require massive amounts of data to capture the cost information accurately or rely on complex thresholding steps that inevitably lose valuable cost data. The authors sought a mathematically sound, computationally efficient way to train a classifier that directly minimizes the cost of errors rather than just the number of errors.

A Paradigm Shift: Reduction to One-Sided Regression

The authors propose a paradigm shift: instead of encoding cost information into the weights of the training data, they encode it into the labels of a regression model. They reduce the classification problem to one-sided regression.

  1. The One-Sided Loss: The model trains a joint regressor to estimate the cost of predicting each class. If a class is the true, lowest-cost class, the regressor is penalized only if it outputs a value higher than the actual cost. For all other incorrect classes, it is penalized only if it outputs a value lower than the cost. It is "one-sided" because deviations on the "safe" side of the threshold incur zero penalty.
  2. RED-OSSVR Algorithm: The authors adapt standard Support Vector Regression (SVR) to use this specific one-sided loss function.
  3. Prediction: During inference, the model evaluates the regressor for all possible classes and picks the one that yields the lowest estimated cost.

By forcing a regressor to directly predict the cost of an action, the model preserves the exact economic or utility differences between classes, avoiding the information loss that plagues weight-based reduction methods. Interestingly, the authors prove that the widely popular One-Versus-All SVM (OVA-SVM) is actually just a special, "cost-blind" case of RED-OSSVR where all misclassification costs are naively set to be equal.

Visualizing the Decision Boundary

To demonstrate how the algorithm shifts decision boundaries away from high-cost errors, the authors evaluated their algorithm on an artificial 2D dataset generated from Gaussian distributions.

Decision boundaries comparing Bayes optimal, OVA-SVM, and RED-OSSVR

As shown above, RED-OSSVR successfully adjusts its decision boundaries to more closely approximate the Bayes optimal boundaries. The model explicitly learns to make more mistakes if those mistakes are cheap in order to avoid making fewer mistakes that are catastrophically expensive.

Empirical Results and Efficiency

Beyond artificial data, the authors tested RED-OSSVR on 10 UCI Benchmark Datasets (using randomized proportional setups to simulate varying misclassification costs) and the KDDCup 1999 network intrusion dataset, which features a realistic, built-in cost matrix.

Key findings include: * Lower Overall Costs: RED-OSSVR achieved significantly lower average test costs compared to standard OVA-SVM. For example, on the glass dataset, the average cost dropped from 283.86 (OVA-SVM) to 228.54 (RED-OSSVR). * Higher Error Rates (By Design): As expected, RED-OSSVR often had a higher raw error rate than OVA-SVM (e.g., 31.48% vs 29.91% on glass). This proves the model successfully trades raw accuracy to avoid high-cost penalties. * State-of-the-Art Performance: RED-OSSVR outperformed or matched other advanced cost-sensitive SVM reductions (like FT-SVM, SECOC-SVM, and WAP-SVM) across the vast majority of datasets.

Performance comparison of RED-OSSVR against other methods across datasets
  • Computational Efficiency: Because RED-OSSVR trains $K$ regressors (where $K$ is the number of classes), its training time scales linearly $\mathcal{O}(K)$. Competing methods like WAP-SVM scale quadratically $\mathcal{O}(K^2)$. On the letter dataset, RED-OSSVR trained about 13 times faster than WAP-SVM while achieving similar performance.

Conclusion and Future Directions

The paper provides a mathematically rigorous foundation proving that minimizing their specific one-sided regression loss directly upper-bounds the actual expected cost of the resulting classifier. While the authors acknowledge that the randomized cost generation used for the UCI datasets does not fully reflect real-world cost structures, the KDDCup results validate the method's practical utility.

Furthermore, while this paper focuses heavily on SVMs, the theoretical reduction to one-sided regression is algorithm-agnostic. A clear future direction is applying this one-sided loss framework to other modern regression architectures, such as deep neural networks or gradient-boosted trees.

Summary updated

Abstract

We propose a novel approach that reduces cost-sensitive classification to one-sided regression. The approach stores the cost information in the regression labels and encodes the minimum-cost prediction with the onesided loss. The simple approach is accompanied by a solid theoretical guarantee of error transformation, and can be used to cast any one-sided regression method as a cost-sensitive classification algorithm. To validate the proposed reduction approach, we design a new cost-sensitive classification algorithm by coupling the approach with a variant of the support vector machine (SVM) for one-sided regression. The proposed algorithm can be viewed as a theoretically justified extension of the popular one-versus-all SVM. Experimental results demonstrate that the algorithm is not only superior to traditional one-versus-all SVM for cost-sensitive classification, but also better than many existing SVM-based cost-sensitive classification algorithms.
BibTeX
@inproceedings{tu2010one,
  author = {Han-Hsing Tu and Hsuan-Tien Lin},
  title = {{One-sided Support Vector Regression for Multiclass Cost-sensitive Classification}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=HkVgBnbubS},
}
Figure