A Data Complexity Approach to Kernel Selection for Support Vector Machines

Roberto Valerio, Ricardo VilaltaAAAI 2014 · DOI

Abstract

Choosing the right kernel for a Support Vector Machine (SVM) is often a matter of trial and error. This paper proposes a "meta-learning" approach that uses data complexity measures—metrics that describe the geometric structure of a dataset—to automatically predict whether a Gaussian or Polynomial kernel will perform better, significantly streamlining the model selection process.

Introduction

Support Vector Machines are powerful because of the "kernel trick," which allows them to map data into high-dimensional spaces to find linear separations that weren't visible in the original space. However, the effectiveness of an SVM depends heavily on the choice of the kernel function (e.g., Gaussian/RBF vs. Polynomial).

Currently, researchers usually rely on computationally expensive grid searches or "rules of thumb" to pick a kernel. There is a lack of fundamental understanding regarding why one kernel outperforms another on a specific dataset. The authors aim to bridge this gap by characterizing datasets using "data complexity measures" to make an informed, a priori choice.

Methodology

The authors focus on the two most common kernels: the Gaussian (RBF) kernel, which acts as a "local" specialist focusing on neighborhoods, and the Polynomial kernel, a "global" kernel that weights all training examples equally. To decide between them, they utilize two specific data complexity measures:

  • T1 (Clusterability): Measures the ratio of clusters to the total number of points. A high $T1$ value suggests fragmented data where local neighborhoods are difficult to define.
  • NEG (Neighborhood Expected Gain): Estimates the performance gain of using a local classifier over a global one.

The researchers developed a simple decision tree meta-model to automate the selection process based on these metrics.

The decision tree meta-model used to predict the optimal kernel based on T1 and NEG complexity measures.

Experimental Setup and Results

The study evaluated the approach using 19 real-world datasets from the UCI repository, covering medical, physical, and social domains. The proposed decision tree model was remarkably effective, correctly predicting the best-performing kernel for 17 out of the 19 datasets—an 89% success rate.

Experimental results showing the T1 and NEG values, predicted kernels, and actual best kernels for the 19 test datasets.

The model only failed on two datasets: Bank Marketing and Echocardiogram. In these instances, the complexity measures did not perfectly align with the empirical performance, suggesting areas for future refinement.

Discussion and Key Insights

The core finding is that the geometry of a dataset dictates kernel performance. The Gaussian kernel excels when a dataset has high "clusterability" (low $T1$) and benefits from local decision-making (high $NEG$). By formalizing the Gaussian kernel as a local specialist and the Polynomial kernel as a global generalist, the authors provide a theoretical basis for kernel selection that moves beyond trial and error.

This approach allows practitioners to skip exhaustive cross-validation steps typically required to compare kernel families, moving straight to fine-tuning the parameters of the predicted "best" kernel.

Limitations and Future Work

While successful, the current model is limited to binary classification and numeric data. Future work could expand this to include a wider variety of kernels (e.g., Sigmoid or Laplacian) and multi-class problems. Additionally, complexity measures might eventually be used to estimate specific hyperparameters, such as the Gaussian width ($\sigma$) or Polynomial degree, further automating the SVM pipeline.

Summary updated

BibTeX
@inproceedings{valerio2014data,
  author = {Roberto Valerio and Ricardo Vilalta},
  title = {{A Data Complexity Approach to Kernel Selection for Support Vector Machines}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9105},
}
Figure