A Simple Geometric Interpretation of SVM using Stochastic Adversaries

Roi Livni, Koby Crammer, Amir GlobersonAISTATS 2012 · OpenReview

Abstract

We present a minimax framework for classification that considers stochastic adversarial perturbations to the training data. We show that for binary classification it is equivalent to SVM, but with a fresh geometric perspective. By framing regularization as robustness against a stochastic adversary, we derive a novel multiclass regularization scheme ($L_{2,\infty}$ norm) that proves more resilient to noise than standard methods.

Introduction

In the classic linearly separable case, Support Vector Machines (SVMs) offer a compelling geometric interpretation: they maximize the margin between classes. However, when data is not perfectly separable and regularized hinge loss is employed, this clear geometric intuition is often lost. Previous attempts to restore this intuition via Robust Optimization—where a deterministic adversary moves training points within a ball to maximize loss—often result in overly pessimistic models or complex formulations. This paper explores an alternative: what if the adversary is stochastic? Instead of a single worst-case point, the adversary must choose a probability distribution of perturbations.

Methodology: Stochastic Adversaries

The proposed minimax framework involves a learner choosing a classifier $w$ and a stochastic adversary choosing a distribution $p(\bar{x}|x)$ for each training point. The game is governed by three rules:

  1. Centeredness: The average perturbed point must be the original point ($E[\bar{x}] = x$).
  2. Budgeted Spread: The expected distance (or squared distance) of the perturbation is limited by a parameter $\sigma$.
  3. Objective: The learner minimizes the maximum expected hinge loss.

Through convex duality, this infinite-dimensional problem is transformed into a tractable, finite-dimensional optimization. For the binary case, robustness to a stochastic adversary with an $L_2$ budget is mathematically identical to standard $L_2$-regularized SVM. For multiclass settings, this framework yields the $L_{2,\infty}$ norm regularization, which penalizes the maximum Euclidean norm among class weight vectors rather than the sum of squares (Frobenius norm).

Experimental Evaluation

The authors evaluated the Robust SVM (RSVM) across three domains: toy datasets with varying noise, standard UCI benchmarks, and large-scale text datasets.

Performance on Benchmark Datasets

On standard UCI datasets, RSVM variants demonstrated performance comparable to or exceeding standard SVMs. The results across various datasets like usps, glass, and segment highlight the stability of the stochastic adversarial approach.

Comparison of RSVM variants and standard SVM on UCI benchmark datasets.

Large-Scale Text Classification

The advantages of RSVM were particularly evident in high-dimensional text classification tasks. In datasets such as 20News and NY Times subsets, the $L_{2,\infty}$ regularization frequently outperformed the standard Frobenius-regularized SVM. For instance, on the 20News dataset, RSVM reduced the error rate from 14.76% to 12.74%.

Performance comparison on large-scale text datasets, showing error rates for SVM and RSVM.

Key Insights

  • Regularization as a Noise Budget: The hyperparameter $\sigma$ represents a physical "expected distance" for noise, allowing for a heuristic setting based on the average distance to a point's nearest neighbor.
  • Multiclass Robustness: The $L_{2,\infty}$ norm suggests that in multiclass settings, we should worry most about the "strongest" class classifier rather than the average of all of them.
  • Noise Resilience: In toy experiments, as the number of noisy dimensions increased, RSVM significantly outperformed standard multiclass SVMs.

Conclusion and Future Work

This work provides a new lens through which to view SVM regularization. By replacing deterministic worst-case scenarios with stochastic ones, we recover geometric intuition and derive superior multiclass regularization. Future research will address the computational costs of squared $L_2$ constraints, which currently require expensive Semidefinite Programming, and extend these concepts to structured prediction tasks.

Summary updated

Abstract

We present a minimax framework for classification that considers stochastic adversarial perturbations to the training data. We show that for binary classification it is equivalent to SVM, but with ...
BibTeX
@inproceedings{livni2012simple,
  author = {Roi Livni and Koby Crammer and Amir Globerson},
  title = {{A Simple Geometric Interpretation of SVM using Stochastic Adversaries}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=DrgwJHy-HZw},
}
Figure