Support Vector Regression Machines

Harris Drucker, Christopher J. C. Burges, Linda Kaufman, Alexander J. Smola, Vladimir VapnikNeurIPS 1996 · OpenReview

This seminal paper, authored by a "who's who" of machine learning pioneers (including Vladimir Vapnik, the father of Support Vector Machines), introduces Support Vector Regression (SVR). It marks a pivotal moment in computational intelligence by extending the robust classification principles of SVMs to the world of continuous value prediction.

TL;DR

The authors introduce Support Vector Regression (SVR), a technique that leverages an "$\epsilon$-insensitive" loss function to ignore small errors and focus on the most critical data points. Unlike traditional methods, SVR’s complexity depends on the number of training samples rather than the dimensionality of the input space, making it exceptionally powerful for high-dimensional problems.

The Problem: The Curse of Dimensionality

In the mid-90s, regression was dominated by techniques like neural networks and decision trees. However, these methods often struggled with the "curse of dimensionality." If you wanted to model complex, non-linear relationships, you typically had to map your data into a high-dimensional "feature space."

The problem with this approach is that as the dimensionality of the space grows, the number of parameters you need to estimate explodes, often far exceeding the number of available training samples. This leads to overfitting—where the model memorizes noise instead of learning the underlying trend. The authors sought a regression method that remained computationally efficient and generalized well, even when the underlying feature space was massive.

Methods: Bringing Support Vectors to Regression

The core innovation is the application of the Support Vector concept to regression through three main pillars:

  1. $\epsilon$-Insensitive Loss Function: Instead of penalizing every tiny deviation from the target (like Mean Squared Error does), SVR defines a "tube" of radius $\epsilon$ around the predicted function.
The epsilon-insensitive tube

If a data point falls inside this tube, the loss is zero. This makes the model robust to noise and focuses the optimization only on points that fall outside the tube (penalized by $\xi$ and $\xi^*$).

  1. The Dual Formulation: By transforming the optimization problem into its "dual" form, the authors show that the solution depends only on the dot products between training vectors. This allows for the use of kernels (specifically polynomial kernels in this paper) to handle non-linearity without ever explicitly calculating coordinates in a high-dimensional space.
  2. Sparsity: The resulting model is defined only by a subset of the training data—the Support Vectors—which are the points lying on or outside the $\epsilon$-tube.

To prove its efficacy, the authors compared SVR against Bagging (an ensemble of regression trees) and Ridge Regression performed in a manually constructed feature space.

Datasets and Key Insights

The study evaluates the algorithms on two types of data:

  • Friedman Functions (#1, #2, #3): Three synthetic benchmarks designed to test non-linear regression capabilities. Since these are artificial, the "ground truth" is known, allowing for precise measurement of modeling error.
  • Boston Housing Dataset: A classic real-world dataset containing 506 cases, where the goal is to predict median house prices based on 12 continuous predictor variables.

The most profound insight from these tests is Dimensionality Independence. SVR optimization does not depend on the dimensionality of the input space. This allows SVR to handle complex polynomial mappings that would break traditional linear techniques. Furthermore, the $\epsilon$-insensitive loss creates a "safety zone." By ignoring small errors, the model achieves better generalization on unseen data because it isn't trying to fit every minor fluctuation in the training set.

Key Results

  • Boston Housing Success: SVR significantly outperformed Bagging on the Boston Housing data, achieving a prediction error of 7.2 compared to Bagging's 12.4.
  • The Limits of Feature Space: On the Boston Housing task, the authors couldn't even construct a traditional feature space representation. A 5th-order polynomial mapping would have required estimating 6,885 coefficients for only 401 training samples. SVR handled this effortlessly because its complexity was tied to the number of samples, not the 6,885 dimensions.
  • Synthetic Benchmarks: On the Friedman functions, SVR consistently beat Bagging across modeling error (ME) and prediction error (PE) metrics.
SVR vs Bagging on Friedman benchmarks

While Ridge Regression performed slightly better on these specific low-dimensional tasks if the feature space was relatively small compared to the number of samples, SVR remained highly competitive and proved to be the clear winner when the feature space became too large to handle traditionally.

Limitations and Future Work

The authors noted that the performance of SVR depends heavily on choosing the right hyperparameters, such as $U$ (regularization), $\epsilon$ (tube width), and $p$ (polynomial degree). They used a validation set to find these, which can be computationally expensive.

Additionally, they admitted that the synthetic problems they chose were perhaps "too simple" to show SVR's full potential. The paper concludes by stating that SVR’s true value lies in "real-life examples" where the dimensionality of the feature space is significantly larger than the number of training examples—a prophecy that has since been validated across fields like bioinformatics and chemometrics.

Summary updated

Abstract

A new regression technique based on Vapnik's concept of support vectors is introduced. We compare support vector regression (SVR) with a committee regression technique (bagging) based on regression trees and ridge regression done in feature space. On the basis of these experiments, it is expected that SVR will have advantages in high dimensionality space because SVR optimization does not depend on the dimensionality of the input space.
BibTeX
@inproceedings{drucker1996support,
  author = {Harris Drucker and Christopher J. C. Burges and Linda Kaufman and Alexander J. Smola and Vladimir Vapnik},
  title = {{Support Vector Regression Machines}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
  url = {https://openreview.net/forum?id=HJ-hzO-OWB},
}
Figure