Combination of One-Class Support Vector Machines for Classification with Reject Option

Blaise Hanczar, Michèle SebagECML/PKDD 2014 · DOI

TL;DR

This paper introduces CONSUM, a novel approach for binary classification that explicitly handles both ambiguous and outlier examples by combining two one-class Support Vector Machines (SVMs). This method offers a more robust and reliable classification by allowing the model to abstain from making a decision when confidence is low, leading to improved performance, especially in real-world scenarios with noisy data.

What Problem Does This Paper Address?

Predictive classifiers are crucial in many fields, but their accuracy is often insufficient for high-stakes decisions like medical diagnoses. Errors in these domains can have severe consequences. To mitigate this, "abstaining classifiers" (also known as reject classifiers) have been developed. These classifiers can choose not to assign a class to an example if confidence is low, thereby improving overall reliability. However, existing methods primarily focus on "ambiguity rejection" (when an example is close to multiple class boundaries) and often neglect "outlier rejection" (when an example is far from all known classes). This paper addresses the gap by proposing a method that simultaneously handles both ambiguity and outlier rejection, offering a more comprehensive solution for robust classification.

Methods

The core of the proposed method, CONSUM, lies in combining two interdependent one-class SVMs, one for each class. A one-class SVM aims to define the smallest region that encompasses most of the training examples. By coupling two such models, CONSUM can construct more robust rejection regions. The method is formulated as a quadratic programming problem. To efficiently solve this for large datasets, the authors adapt the Sequential Minimal Optimization (SMO) algorithm, originally developed for standard SVMs. This adapted SMO algorithm iteratively optimizes pairs of Lagrange multipliers, making it scalable. The decision functions of CONSUM are derived from the outputs of the two one-class SVMs, and a final decision is made based on whether an example falls within the positive class region, the negative class region, or is rejected as either ambiguous or an outlier.

Datasets

The paper uses both artificial and real-world datasets for evaluation.

  • Artificial Datasets: Used to visualize classifier behavior and analyze parameter sensitivity. These datasets were generated from Gaussian distributions, with an additional third class (uniform distribution) introduced to simulate outliers.
  • Real-world Datasets: Six datasets from the UCI repository were used: wdbc, spam, madelon, pop, transfusion, and bank.

Key Insights and Ideas

  • Unified Ambiguity and Outlier Rejection: The most significant insight is the successful integration of both ambiguity and outlier rejection within a single framework. This is crucial for real-world data where outliers are common and often overlooked by existing methods.
  • One-Class SVM Synergy: Combining two one-class SVMs, rather than simply adding a rejection rule to a standard classifier, leads to a more principled and effective way of defining rejection regions.
  • SMO Adaptation for Scalability: The adaptation of the SMO algorithm is key to making this approach practical for large datasets, a common challenge in machine learning.
  • Parameter Control: The parameters in CONSUM offer fine-grained control over the trade-off between error rate and rejection rate, allowing users to tune the classifier's behavior based on specific application needs.
  • Rejection Option's Importance: The experiments highlight that while standard SVMs might perform best without rejection, the introduction of a rejection option significantly improves performance, especially for methods like CONSUM that are designed to leverage it.

Key Results

  • Superior Performance: On artificial datasets, CONSUM demonstrated better fitting of ambiguity and outlier rejection regions compared to SVM and a two-one-class SVM (2OSVM) approach.
  • Trade-off Control: CONSUM effectively controls the trade-off between error rate and rejection rate, outperforming other methods in error-rejection curve analysis.
  • Real-world Data: On real-world datasets, CONSUM achieved the best performance in scenarios involving both ambiguity and outlier rejection, often surpassing SVM and 2OSVM. Notably, SVM performed better in the "no rejection" scenario, underscoring the benefit of rejection-specific methods when rejection is employed.
  • Classification Cost: CONSUM generally achieved lower classification costs than SVM and 2OSVM when rejection was considered.

Limitations and Future Work

  • Parameter Sensitivity: The performance of CONSUM is sensitive to the choice of hyper-parameters (e.g., V+, V-, C, Cr, Ce). While the paper investigates this, optimal parameter selection remains an important aspect.
  • Cost Matrix Assumption: The initial formulation assumes equal costs for false positives/negatives and equal costs for ambiguity/outlier rejection. The paper acknowledges that for cost-sensitive or unbalanced problems, these costs might differ, requiring modifications to the constraints.
  • Multi-class Extension: The current work focuses on binary classification. Extending CONSUM to multi-class problems is identified as a significant future direction, though it presents challenges due to the quadratic increase in hyper-parameters. The authors suggest drawing inspiration from existing multi-class SVM methods.

Summary updated

BibTeX
@inproceedings{hanczar2014combination,
  author = {Blaise Hanczar and Michèle Sebag},
  title = {{Combination of One-Class Support Vector Machines for Classification with Reject Option}},
  booktitle = {ECML/PKDD},
  year = {2014},
  doi = {10.1007/978-3-662-44848-9\_35},
}
Figure