Understanding Support Vector Machine Regression

Mathematical Formulation of SVM Regression

Overview

Support vector machine (SVM) analysis is a popular machine learning tool for classification and regression, first identified by Vladimir Vapnik and his colleagues in 1992[5]. SVM regression is considered a nonparametric technique because it relies on kernel functions.

Statistics and Machine Learning Toolbox™ implements linear epsilon-insensitive SVM (ε-SVM) regression, which is also known as L1 loss. In ε-SVM regression, the set of training data includes predictor variables and observed response values. The goal is to find a function f(x) that deviates from y_n by a value no greater than ε for each training point x, and at the same time is as flat as possible.

Linear SVM Regression: Primal Formula

Suppose we have a set of training data where x_n is a multivariate set of N observations with observed response values y_n.

To find the linear function

$$f(x)=x\prime \beta +b,$$

and ensure that it is as flat as possible, find f(x) with the minimal norm value (β′β). This is formulated as a convex optimization problem to minimize

$$J\left(\beta \right)=\frac{1}{2}\beta \prime \beta$$

subject to all residuals having a value less than ε; or, in equation form:

$$\forall n:\left|y_n-\left(x_n\prime \beta +b\right)\right|\le \epsilon .$$

It is possible that no such function f(x) exists to satisfy these constraints for all points. To deal with otherwise infeasible constraints, introduce slack variables ξ_n and ξ^*_n for each point. This approach is similar to the “soft margin” concept in SVM classification, because the slack variables allow regression errors to exist up to the value of ξ_n and ξ^*_n, yet still satisfy the required conditions.

Including slack variables leads to the objective function, also known as the primal formula[5]:

$$J\left(\beta \right)=\frac{1}{2}\beta \prime \beta +C{\displaystyle \sum _{n=1}^N\left({\xi }_n+{\xi }_n^{*}\right)},$$

subject to:

$$\begin{array}{l}\forall n:y_n-\left(x_n\prime \beta +b\right)\le \epsilon +{\xi }_n\\ \forall n:\left(x_n\prime \beta +b\right)-y_n\le \epsilon +{\xi }_n^{*}\\ \forall n:{\xi }_n^{*}\ge 0\\ \forall n:{\xi }_n\ge 0.\end{array}$$

The constant C is the box constraint, a positive numeric value that controls the penalty imposed on observations that lie outside the epsilon margin (ε) and helps to prevent overfitting (regularization). This value determines the trade-off between the flatness of f(x) and the amount up to which deviations larger than ε are tolerated.

The linear ε-insensitive loss function ignores errors that are within ε distance of the observed value by treating them as equal to zero. The loss is measured based on the distance between observed value y and the ε boundary. This is formally described by

$$L_{\epsilon }=\{\begin{array}{ll}0\hfill & \text{if }\left|y-f\left(x\right)\right|\le \epsilon \hfill \\ \left|y-f\left(x\right)\right|-\epsilon \hfill & \text{otherwise}\hfill \end{array}$$

Linear SVM Regression: Dual Formula

The optimization problem previously described is computationally simpler to solve in its Lagrange dual formulation. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. The optimal values of the primal and dual problems need not be equal, and the difference is called the “duality gap.” But when the problem is convex and satisfies a constraint qualification condition, the value of the optimal solution to the primal problem is given by the solution of the dual problem.

To obtain the dual formula, construct a Lagrangian function from the primal function by introducing nonnegative multipliers α_n and α^*_n for each observation x_n. This leads to the dual formula, where we minimize

$$L\left(\alpha \right)=\frac{1}{2}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{j=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)\left({\alpha }_j-{\alpha }_j^{*}\right)x_i\prime x_j+\epsilon {\displaystyle \sum _{i=1}^N\left({\alpha }_i+{\alpha }_i^{*}\right)}}}+{\displaystyle \sum _{i=1}^N{y}_i\left({\alpha }_i^{*}-{\alpha }_i\right)}$$

subject to the constraints

$$\begin{array}{l}{\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)=0}\\ \forall n:0\le {\alpha }_n\le C\\ \forall n:0\le {\alpha }_n^{*}\le C.\end{array}$$

The β parameter can be completely described as a linear combination of the training observations using the equation

$$\beta ={\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)x_n.}$$

The function used to predict new values depends only on the support vectors:

$$f\left(x\right)={\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)\left(x_n\prime x\right)+b.}$$

(1)

The Karush-Kuhn-Tucker (KKT) complementarity conditions are optimization constraints required to obtain optimal solutions. For linear SVM regression, these conditions are

$$\begin{array}{l}\forall n:{\alpha }_n\left(\epsilon +{\xi }_n-y_n+x_n\prime \beta +b\right)=0\\ \forall n:{\alpha }_n^{*}\left(\epsilon +{\xi }_n^{*}+y_n-x_n\prime \beta -b\right)=0\\ \forall n:{\xi }_n\left(C-{\alpha }_n\right)=0\\ \forall n:{\xi }_n^{*}\left(C-{\alpha }_n^{*}\right)=0.\end{array}$$

These conditions indicate that all observations strictly inside the epsilon tube have Lagrange multipliers α_n = 0 and α_n^* = 0. If either α_n or α_n^* is not zero, then the corresponding observation is called a support vector.

The property Alpha of a trained SVM model stores the difference between two Lagrange multipliers of support vectors, α_n – α_n^*. The properties SupportVectors and Bias store x_n and b, respectively.

Nonlinear SVM Regression: Primal Formula

Some regression problems cannot adequately be described using a linear model. In such a case, the Lagrange dual formulation allows the previously-described technique to be extended to nonlinear functions.

Obtain a nonlinear SVM regression model by replacing the dot product x₁′x₂ with a nonlinear kernel function G(x₁,x₂) = <φ(x₁),φ(x₂)>, where φ(x) is a transformation that maps x to a high-dimensional space. Statistics and Machine Learning Toolbox provides the following built-in positive semidefinite kernel functions.

Kernel Name	Kernel Function
Linear (dot product)	$$G(x_j,x_k)=x_j\prime x_k$$
Gaussian	$$G\left(x_j,x_k\right)=\exp \left(-{\Vert x_j-x_k\Vert }^2\right)$$
Polynomial	$$G(x_j,x_k)={(1+x_j\prime x_k)}^q$$, where q is in the set {2,3,...}.

The Gram matrix is an n-by-n matrix that contains elements g_i,_j = G(x_i,x_j). Each element g_i,_j is equal to the inner product of the predictors as transformed by φ. However, we do not need to know φ, because we can use the kernel function to generate Gram matrix directly. Using this method, nonlinear SVM finds the optimal function f(x) in the transformed predictor space.

Nonlinear SVM Regression: Dual Formula

The dual formula for nonlinear SVM regression replaces the inner product of the predictors (x_i′x_j) with the corresponding element of the Gram matrix (g_i,_j).

Nonlinear SVM regression finds the coefficients that minimize

$$L\left(\alpha \right)=\frac{1}{2}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{j=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)\left({\alpha }_j-{\alpha }_j^{*}\right)G\left(x_i,x_j\right)+\epsilon {\displaystyle \sum _{i=1}^N\left({\alpha }_i+{\alpha }_i^{*}\right)-{\displaystyle \sum _{i=1}^N{y}_i\left({\alpha }_i-{\alpha }_i^{*}\right)}}}}$$

subject to

$$\begin{array}{l}{\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)}=0\\ \forall n:0\le {\alpha }_n\le C\\ \forall n:0\le {\alpha }_n^{*}\le C.\end{array}$$

The function used to predict new values is equal to

$$f\left(x\right)={\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)G\left(x_n,x\right)+b}.$$

(2)

The KKT complementarity conditions are

$$\begin{array}{l}\forall n:{\alpha }_n\left(\epsilon +{\xi }_n-y_n+f\left(x_n\right)\right)=0\\ \forall n:{\alpha }_n^{*}\left(\epsilon +{\xi }_n^{*}+y_n-f\left(x_n\right)\right)=0\\ \forall n:{\xi }_n\left(C-{\alpha }_n\right)=0\\ \forall n:{\xi }_n^{*}\left(C-{\alpha }_n^{*}\right)=0.\end{array}$$

Solving the SVM Regression Optimization Problem

Solver Algorithms

The minimization problem can be expressed in standard quadratic programming form and solved using common quadratic programming techniques. However, it can be computationally expensive to use quadratic programming algorithms, especially since the Gram matrix may be too large to be stored in memory. Using a decomposition method instead can speed up the computation and avoid running out of memory.

Decomposition methods (also called chunking and working set methods) separate all observations into two disjoint sets: the working set and the remaining set. A decomposition method modifies only the elements in the working set in each iteration. Therefore, only some columns of the Gram matrix are needed in each iteration, which reduces the amount of storage needed for each iteration.

Sequential minimal optimization (SMO) is the most popular approach for solving SVM problems[4]. SMO performs a series of two-point optimizations. In each iteration, a working set of two points are chosen based on a selection rule that uses second-order information. Then the Lagrange multipliers for this working set are solved analytically using the approach described in [2] and [1].

In SVM regression, the gradient vector $$\nabla L$$ for the active set is updated after each iteration. The decomposed equation for the gradient vector is

$${\left(\nabla L\right)}_n=\{\begin{array}{c}{\displaystyle \sum _{i=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)G\left(x_i,x_n\right)+\epsilon -y_n,n\le N}\\ -{\displaystyle \sum _{i=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)G\left(x_i,x_n\right)+\epsilon +y_n,n>N}\end{array}.$$

Iterative single data algorithm (ISDA) updates one Lagrange multiplier with each iteration[3]. ISDA is often conducted without the bias term b by adding a small positive constant a to the kernel function. Dropping b drops the sum constraint

$${\displaystyle \sum _{n=1}^N\left({\alpha }_i-{\alpha }^{*}\right)=0}$$

in the dual equation. This allows us to update one Lagrange multiplier in each iteration, which makes it easier than SMO to remove outliers. ISDA selects the worst KKT violator among all the α_n and α_n^* values as the working set to be updated.

Convergence Criteria

Each of these solver algorithms iteratively computes until the specified convergence criterion is met. There are several options for convergence criteria:

• Feasibility gap — The feasibility gap is expressed as

  $$\Delta =\frac{J\left(\beta \right)+L\left(\alpha \right)}{J\left(\beta \right)+1},$$

  where J(β) is the primal objective and L(α) is the dual objective. After each iteration, the software evaluates the feasibility gap. If the feasibility gap is less than the value specified by GapTolerance, then the algorithm met the convergence criterion and the software returns a solution.

• Gradient difference — After each iteration, the software evaluates the gradient vector, $$\nabla L$$. If the difference in gradient vector values for the current iteration and the previous iteration is less than the value specified by DeltaGradientTolerance, then the algorithm met the convergence criterion and the software returns a solution.

• Largest KKT violation — After each iteration, the software evaluates the KKT violation for all the α_n and α_n^* values. If the largest violation is less than the value specified by KKTTolerance, then the algorithm met the convergence criterion and the software returns a solution.

References

[1] Fan, R.E. , P.H. Chen, and C.J. Lin. "A Study on SMO-Type Decomposition Methods for Support Vector Machines." IEEE Transactions on Neural Networks, Vol. 17:893–908, 2006.

[2] Fan, R.E. , P.H. Chen, and C.J. Lin. "Working Set Selection Using Second Order Information for Training Support Vector Machines." The Journal of Machine Learning Research, Vol. 6:1871–1918, 2005.

[3] Huang, T.M., V. Kecman, and I. Kopriva. Kernel Based Algorithms for Mining Huge Data Sets: Supervised, Semi-Supervised, and Unsupervised Learning. Springer, New York, 2006.

[4] Platt, J. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98–14, 1999.

[5] Vapnik, V. The Nature of Statistical Learning Theory. Springer, New York, 1995.