Regularization perspectives on support vector machines

Introduction

Regularization perspectives on SVM interpret SVM as a special case Tikhonov regularization, specifically Tikhonov regularization with the hinge loss for a loss function. This provides a theoretical framework with which to analyze SVM algorithms and compare them to other algorithms with the same goals: to generalize without overfitting. SVM was first proposed in 1995 by Corinna Cortes and Vladimir Vapnik, and framed geometrically as a method for finding hyperplanes that can separate multidimensional data into two categories. This traditional geometric interpretation of SVMs provides useful intuition about how SVMs work, but is difficult to relate to other machine learning techniques for avoiding overfitting like regularization, early stopping, sparsity and Bayesian inference. However, once it was discovered that SVM is also a special case of Tikhonov regularization, regularization perspectives on SVM provided the theory necessary to fit SVM within a broader class of algorithms. This has enabled detailed comparisons between SVM and other forms of Tikhonov regularization, and theoretical grounding for why it is beneficial to use SVM's loss function, the hinge loss.

Theoretical background

In the statistical learning theory framework, an algorithm is a strategy for choosing a function $f:\mathbf {X} \to \mathbf {Y}$ given a training set $S=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}$ of inputs and their labels (the labels are usually $\pm 1$). Regularization strategies avoid overfitting by choosing a function that fits the data, but is not too complex. Specifically:

$f={\text{arg}}\min _{f\in {\mathcal {H}}}\left\{{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},f(x_{i}))+\lambda ||f||_{\mathcal {H}}^{2}\right\}$,

where ${\mathcal {H}}$ is a hypothesis space of functions, $V:\mathbf {Y} \times \mathbf {Y} \to \mathbb {R}$ is the loss function, $||\cdot ||_{\mathcal {H}}$ is a norm on the hypothesis space of functions, and $\lambda \in \mathbb {R}$ is the regularization parameter .

When ${\mathcal {H}}$ is a reproducing kernel Hilbert space, there exists a kernel function $K:\mathbf {X} \times \mathbf {X} \to \mathbb {R}$ that can be written as an $n\times n$ symmetric positive definite matrix $\mathbf {K}$. By the representer theorem, $f(x_{i})=\sum _{f=1}^{n}c_{j}\mathbf {K} _{ij}$, and $||f||_{\mathcal {H}}^{2}=\langle f,f\rangle _{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})=c^{T}\mathbf {K} c$

Special properties of the hinge loss

The simplest and most intuitive loss function for categorization is the misclassification loss, or 0-1 loss, which is 0 if $f(x_{i})=y_{i}$ and 1 if $f(x_{i})\neq y_{i}$, i.e the heaviside step function on $-y_{i}f(x_{i})$. However, this loss function is not convex, which makes the regularization problem very difficult to minimize computationally. Therefore, we look for convex substitutes for the 0-1 loss. The hinge loss, $V(y_{i},f(x_{i}))=(1-yf(x))_{+}$ where $(s)_{+}=max(s,0)$, provides such a convex relaxation. In fact, the hinge loss is the tightest convex upper bound to the 0-1 misclassification loss function, and with infinite data returns the Bayes optimal solution:

$f_{b}(x)=\left\{{\begin{matrix}1&p(1|x)>p(-1|x)\\-1&p(1|x)<p(-1|x)\end{matrix}}\right.$

Derivation

To show that SVM is indeed a special case of Tikhonov regularization using the hinge loss, we will first state the Tikhonov regularization problem with the hinge loss, then demonstate that it is equivalent to traditional formulations of SVM. With the hinge loss, $V(y_{i},f(x_{i}))=(1-yf(x))_{+}$ where $(s)_{+}=max(s,0)$, the regularization problem becomes:

$f={\text{arg}}\min _{f\in {\mathcal {H}}}\left\{{\frac {1}{n}}\sum _{i=1}^{n}(1-yf(x))_{+}+\lambda ||f||_{\mathcal {H}}^{2}\right\}$,

However if we set $C={\frac {1}{2\lambda n}}$, we get:

$f={\text{arg}}\min _{f\in {\mathcal {H}}}\left\{C\sum _{i=1}^{n}(1-yf(x))_{+}+{\frac {1}{2}}||f||_{\mathcal {H}}^{2}\right\}$.

Notes and References

• Evgeniou, Theodoros (2000). "Regularization Networks and Support Vector Machines" (PDF). Advances in Computational Mathematics. 13 (1): 1–50. doi:10.1023/A:1018946025316. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

• Joachims, Thorsten. "SVMlight".

• Vapnik, Vladimir (1999). The Nature of Statistical Learning Theory. New York: Springer-Verlag. ISBN 0-387-98780-0.