Bi-Parameter Space Partition for Cost-Sensitive SVM

Bin Gu, Victor S. Sheng, Shuo Li

Introduction

In critical domains such as medical diagnosis and fraud detection, the cost of a false negative often far outweighs that of a false positive. Cost-Sensitive Support Vector Machines (CS-SVMs) address this imbalance by employing two distinct regularization parameters, $C_+$ and $C_-$, to penalize errors on positive and negative classes differently.

Traditionally, optimizing these parameters requires a discrete grid search, which is both computationally expensive and prone to missing the global optimum between grid points. This paper introduces the Bi-Parameter Space Partition (BPSP) algorithm, a geometric framework that analytically maps the entire continuous parameter space into regions of constant model behavior, enabling the identification of mathematically global optimal settings significantly faster than traditional methods.

The BPSP Framework

The BPSP algorithm moves away from brute-force searching by treating model selection as a geometric partitioning problem. The process follows four primary steps:

1. Coordinate Transformation

To handle the theoretically infinite search space of $(C_+, C_-)$, the authors first reformulate the CS-SVM problem into a more manageable $(\lambda, \eta)$ coordinate system. This transformation maps the infinite quadrant into a finite unit square, making the entire parameter space searchable.

Mapping from the infinite (C+, C-) space to the finite (lambda, eta) unit square.

2. Critical-Region Partitioning

By applying Karush-Kuhn-Tucker (KKT) conditions, the authors prove that the parameter space can be divided into a finite number of convex polygon regions. Within each "critical region," the set of support vectors remains constant, and the model's solution changes linearly with the parameters.

3. Invariant-Region Partitioning

These critical regions are further subdivided into "invariant regions." In these smaller polygons, the empirical classification error on a validation set remains constant. This allows the algorithm to pinpoint exactly where performance shifts.

4. K-fold Superposition

For cross-validation, the algorithm overlays the partitions generated from all $K$ folds. The resulting intersection of regions creates a master map where every point in a specific sub-region yields the same cross-validation error. The global minimum is then found by simply checking the error associated with each region.

Key Insights: Geometry over Brute Force

The core innovation of BPSP is leveraging the piecewise linearity of SVM solutions. Instead of guessing points, the algorithm calculates the exact boundaries where the model's behavior changes. It uses a recursive approach: starting with a single solution, it "walks" through boundaries to discover adjacent regions until the entire space is mapped.

Evolution of the parameter space partition, showing critical regions (a, b), the partition in the original C-space (c), and the final complex map (d).

Experimental Results

The researchers evaluated BPSP on 11 datasets, including imbalanced ones like Ecoli and Vehicle0. The results demonstrated two major advantages:

  • Guaranteed Optimality: Unlike grid search, which is a "best of what we tried" approach, BPSP explores the continuous space, ensuring no "sweet spot" is missed. It consistently achieved the lowest cross-validation error across all test cases.
  • Dramatic Speedups: BPSP outperformed grid search by orders of magnitude. For the Diabetes dataset, grid search required 294 minutes, whereas BPSP completed the task in just 5.5 minutes. Similarly, for Vehicle0, the time was reduced from 262 minutes to 26 minutes.
  • Stability: BPSP identifies the center of an optimal region rather than a single point. This leads to more stable test errors, as the chosen parameters are robust to minor fluctuations.

Conclusion and Future Work

BPSP represents a significant shift in SVM hyperparameter tuning, replacing heuristic search with geometric certainty. While highly effective for two parameters, future research aims to extend this multi-parametric partitioning to more complex learning models and scenarios involving more than two hyperparameters. Currently, the implementation's reliance on vertex enumeration and inverse matrix updates presents a higher complexity ceiling for massive-scale datasets, which remains an area for optimization.

Summary updated

Abstract

Model selection is an important problem of costsensitive SVM (CS-SVM). Although using solution path to find global optimal parameters is a powerful method for model selection, it is a challenge to extend the framework to solve two regularization parameters of CS-SVM simultaneously. To overcome this challenge, we make three main steps in this paper. (i) A critical-regions-based biparameter space partition algorithm is proposed to present all piecewise linearities of CS-SVM. (ii) An invariant-regions-based bi-parameter space partition algorithm is further proposed to compute empirical errors for all parameter pairs. (iii) The global optimal solutions for K-fold cross validation are computed by superposing K invariant region based bi-parameter space partitions into one. The three steps constitute the model selection of CS-SVM which can find global optimal parameter pairs in K-fold cross validation. Experimental results on seven normal datsets and four imbalanced datasets, show that our proposed method has better generalization ability and than various kinds of grid search methods, however, with less running time.
BibTeX
@inproceedings{gu2015bi,
  author = {Bin Gu and Victor S. Sheng and Shuo Li},
  title = {{Bi-Parameter Space Partition for Cost-Sensitive SVM}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure