SVM — The Main Idea

Introduction to Support Vector Machines

Starting from slides drawn by Ming-Hsuan Yang and Antoine Cornu´ejols

SVM Bibliography

B. Boser, I. Guyon, V. Vapnik, “A training algorithm for optimal margin classifier”, 1992

C. Cortes, V. Vapnik, “Support vector networks”. Journal of Machine Learning, 20, 1995.

V. Vapnik. “The nature of statistical learning theory”.

Springer Verlag, 1995.

C. Burges, “A tutorial on support vector machines for pat- tern recognition”. Data Mining and Knowledge Descovery, 2(2):955-974, 1998.

N. Cristianini, J. Shawe-Taylor, “Support Vector Machines and other kernel-based learning methods”. Cambridge University Press, 2000. Andrew Ng, “Support Vector Ma- chines”, Stanford University, CS229 Lecture Notes, Part V.

2.

SVM — The Main Idea

Given a set of data points which belong to either of two classes, find an optimal separating hyperplane

- maximizing the distance (from closest points) of either class to the separating hyperplane, and

- minimizing the risk of misclassifying the training samples and the unseen test samples.

Approach: Formulate a constraint-based optimisation prob- lem, then solve it using quadratic programming (QP).

Optimal Separation Hyperplane

optimal separating hyperplane

maximal margin

valid separating hyperplane

Plan

1. Linear SVMs

The primal form and the dual form of linear SVMs Linear SVMs with soft margin

2. Non-Linear SVMs

Kernel functions for SVMs

An example of non-linear SVM

1. Linear SVMs: Formalisation

Let S be a set of points x_i ∈ R^d with i = 1, . . . , m. Each point x_i belongs to either of two classes, with label y_i ∈ {−1, +1}. The set S is linear separable if there are w ∈ R^d and w₀ ∈ R

such that

y_i(w · x_i + w₀) ≥ 1 i = 1, . . . , m

The pair (w, w₀) defines the hyperplane of equation w·x+w₀ = 0, named the separating hyperplane.

The signed distance d_i of a point x_i to the separating hyper- plane (w, w₀) is given by d_i = ^w·x_||ⁱ_w^+w_|| ⁰.

It follows that y_id_i ≥ _||w¹_||, therefore _||w¹_|| is the lower bound on the distance between points x_i and the separating hyper- plane (w, w₀).

Optimal Separating Hyperplane

Given a linearly separable set S, the optimal separat- ing hyperplane is the separating hyperplane for which the distance to the closest (either positive or negative) points in S is maximum, therefore it maximizes _||w¹_||.

x_i

maximal margin

optimal separating hyperplane

1 II w II

x_i

II w II

D( )

geometric margin

vectors support

D(x) < −1 D(x) = 0

D(x) = −1

D(x) = 1 D(x) > 1

w

D(x) = w · x + w₀

Linear SVMs: The Primal Form

minimize ¹₂||w||²

subject to y_i(w · x_i + w₀) ≥ 1 for i = 1, . . . , m

This is a constrained quadratic problem (QP) with d + 1 pa- rameters (w ∈ R^d and w₀ ∈ R). It can be solved by quadratic optimisation methods if d is not very big (10³).

For large values of d (10⁵): due to the Kuhn-Tucker theorem, since the above objective function and the associated con- straints are convex, we can use the method of Lagrange multipliers (α_i ≥ 0, i = 1, . . . , m) to put the above problem under an equivalent “dual” form.

Note: In the dual form, the variables (α_i) will be subject to much simpler constraints than the variables (w, w₀) in the primal form.

Linear SVMs: Getting the Dual Form

The Lagrangean function associated to the primal form of the given QP is

L_P(w, w₀, α) = 1

2||w²|| −

m

X

i=1

α_i(y_i(w · x_i + w₀) − 1)

with α_i ≥ 0, i = 1, . . . , m. Finding the minimum of L_P implies

∂L_P

∂w₀ = −

m

X

i=1

y_iα_i = 0

∂L_P

∂w = w −

m

X

i=1

y_iα_ix_i = 0 ⇒ w =

m

X

i=1

y_iα_ix_i

where ∂L_P

∂w = (∂L_P

∂w₁ , . . . , ∂L_P

∂w_d )

By substituting these constraints into L_P we get its dual form

L_D(α) =

m

X

i=1

α_i − 1 2

m

X

i=1 m

X

j=1

α_iα_jy_iy_j x_i · x_j

Linear SVMs: The Dual Form

maximize ^Pm_i=1 α_i − ¹₂ ^Pmi=1

Pm

j=1 α_iα_jy_iy_j x_i · x_j subject to ^Pm_i=1 y_iα_i = 0

α_i ≥ 0, i = 1, . . . , m

The link between the primal and the dual form:

The optimal solution (w, w₀) of the primal QP problem is given by

w =

m X i=1

α_iy_ix_i

α_i(y_i(w · x_i + w₀) − 1) = 0 for any i = 1, . . . , m

where α_i are the optimal solutions of the above (dual form) optimisation problem.

Support Vectors

The only α_i (solutions of the dual form of our QP problem) that can be nonzero are those for which the constraints y_i(w · x_i + w₀) ≥ 1 for i = 1, . . . , m in the primal form of the QP are satisfied with the equality sign.

Because most α_i are null, the vector w is a linear combination of a relative small percentage of the points x_i.

These points are called support vectors because they are the closest points to the optimal separating hyperplane (OSH) and the only points of S needed to determine the OSH.

The problem of classifying a new data point x is now simply solved by looking at sign(w · x + w₀).

Linear SVMs with Soft Margin

If the set S is not linearly separable — or one simply ignores whether or not S is linearly separable —, the previous analysis can be generalised by introducing m non-negative (“slack”) variables ξ_i, for i = 1, . . . , m such that

y_i(w · x_i + w₀) ≥ 1 − ξ_i, for i = 1, . . . , m

Purpose: to allow for a small number of missclassified points, for better generalisation or computational efficiency.

Generalised OSH

The generalised OSH is then viewed as the solution to the problem:

minimize ¹₂||w||² + C ^Pm_i=1 ξ_i

subject to y_i(w · x_i + w₀) ≥ 1 − ξ_i for i = 1, . . . , m ξ_i ≥ 0 for i = 1, . . . , m

The associated dual form:

maximize ^Pm_i=1 α_i − ¹₂ ^Pmi=1

P_m

j=1 α_iα_jy_iy_j x_i · x_j subject to ^Pm_i=1 y_iα_i = 0

0 ≤ α_i ≤ C, i = 1, . . . , m As before:

w = ^Pm_i=1 α_iy_ix_i

α_i(y_i(w · x_i + w₀) − 1 + ξ_i) = 0 (C − α_i) ξ_i = 0

The role of C:

it acts as a regularizing parameter:

• large C ⇒ minimize the number of misclassified points

• small C ⇒ maximize the minimum distance _||w¹_||

2. Nonlinear Support Vector Machines

• Note that the only way the data points appear in (the dual form of) the training problem is in the form of dot products x_i · x_j.

• In a higher dimensional space, it is very likely that a linear separator can be constructed.

• We map the data points from the input space R^d into some space of higher dimension Rⁿ (n > d) using a function Φ : R^d → Rⁿ

• Then the training algorithm would depend only on dot products of the form Φ(x_i) · Φ(x_j).

• Constructing (via Φ) a separating hyperplane with maximum margin in the higher-dimensional space yields a nonlinear decision boundary in the input space.

General Schema for Nonlinear SVMs

Input

space Output

space

Internal redescription

space

x Φ h y

Introducing Kernel Functions

• But the dot product is computationally expensive...

• If there were a “kernel function” K such that K(x_i, x_j) = Φ(x_i)·Φ(x_j), we would only use K in the training algorithm.

• All the previous derivations in the model of linear SVM hold (substituting the dot product with the kernel func- tion), since we are still doing a linear separation, but in a different space.

• Important remark: By the use of the kernel function, it is possible to compute the separating hyperplane without explicitly carrying out the map into the higher space.

Some Classes of Kernel Functions for SVMs

• Polynomial: K(x, x^′) = (x · x^′ + c)^q

• RBF (radial basis function): K(x, x^′) = e^{−||x−x′||}

2 2σ2

• Sigmoide: K(x, x^′) = tanh(αx · x^′ − b)

An Illustration

(a) (b)

Decision surface

(a) by a polynomial classifier, and (b) by a RBF.

Support vectors are indicated in dark fill.

Important Remark

The kernel functions require calculations in x(∈ R^d), therefore they are not difficult to compute.

It remains to determine which kernel function K can be as- sociated with a given (redescription space) function Φ.

In practice, one proceeds vice versa:

we test kernel functions about which we know that they correspond to the dot product in a certain space (which will work as redescription space, never made explicit).

Therefore, the user operates by “trial and error”...

Advantage: the only parameters when training an SVM are the kernel function K, and the “tradeoff” parameter C.

Mercer’s Theorem (1909):

A Characterisation of Kernel Functions for SVMs

Theorem: Let K : R^d × R^d → R be a symmetrical function.

K represents a dot product,

i.e. there is a function Φ : R^d → Rⁿ such that K(x, x^′) = Φ(x) · Φ(x^′)

if and only if

Z

K(x, x^′)f(x)f(x^′)dx dx^′ ≥ 0

for any function f such that ^R f²(x)dx is finite.

Remark: The theorem doesn’t say how to construct Φ.

Some simple rules for building (Mercer) kernels

If K₁ and K₂ are kernels over X × X, with X ⊆ Rⁿ, then

• K(x, y) = K₁(x, y) + K₂(x, y)

• K(x, y) = aK₁(x, y), with a ∈ R⁺

• K(x, y) = K₁(x, y)K₂(x, y) are also kernels.

Illustrating the General Architecture of SVMs

for the problem of hand-written character recognition

K

K K

α

α

α

α

K

Σ

Comparison: K(x_i, x)

Support vectors: x₁, x₂, x₃, . . .

Input: x

An Exercise: xor

x₁

x2

1

−1

−1

1

Note: use K(x, x^′) = (x · x^′ + 1)².

It can be easily shown that Φ(x) = (x²₁, x²₂, √

2x₁x₂, √

2x₁, √

2x₂, 1) ∈ R⁶ for x = (x₁, x₂) ∈ R².

i x_i y_i Φ(i) 1 (1,1) −1 (1,1,√

2,√ 2,√

2,1) 2 (1,−1) 1 (1,1,−√

2,√

2,−√ 2,1) 3 (−1,1) 1 (1,1,−√

2,−√ 2,√

2,1) 4 (−1,−1) −1 (1,1,√

2,−√

2,−√ 2,1)

L_D(α) = ^P4_i=1 α_i − ¹₂ ^P4i=1

P₄

j=1 α_iα_jy_iy_j Φ(x_i) · Φ(x_j)

= α₁ + α₂ + α₃ + α₄−

−¹₂( 9α₁² − 2α₁α₂ − 2α₁α₃ + 2α₁α₄+ 9α₂² + 2α₂α₃ − 2α₂α₄+

9α₃² − 2α₃α₄+ 9α₄²)

subject to:

−α₁ + α₂ + α₃ − α₄ = 0

∂L_D(α)

∂α¹ = 0 ⇔ 9α₁ − α₂ − α₃ + α₄ = 1

∂L_D(α)

∂α2 = 0 ⇔ α₁ − 9α₂ − α₃ + α₄ = −1

∂L_D(α)

∂α3 = 0 ⇔ α₁ − α₂ − 9α₃ + α₄ = −1

∂L_D(α)

∂α⁴ = 0 ⇔ α₁ − α₂ − α₃ + 9α₄ = 1

¯

α₁ = ¯α₂ = ¯α₃ = ¯α₄ = ¹₈

¯

w = ¹₈(−Φ(x₁) + Φ(x₂) + Φ(x₃) − Φ(x₄)) = ¹₈(0, 0,−4√

2, 0, 0, 0)

¯

w · Φ(x_i) + ¯w₀ = y_i ⇒ w¯₀ = 0

The optimal separation hyperplane: w¯ · Φ(x) + ¯w₀ = 0 ⇔ −x₁x₂ = 0 Test: sign (−x₁x₂)

The xor Exercise: Result

2 x1

margin: 2

maximum

1 2

D(x , x ) = −1

1 2

D(x , x ) = 0

x₂

x₁

1 2

D(x , x ) = 0

21D(x , x ) = 0

1 2

D(x , x ) = +1

1 2

D(x , x ) = 0

1 2

D(x , x ) = +1

1 2

D(x , x ) = −1

1 2

D(x , x ) = −1

1 2

D(x , x ) = +1

2 x x_{1 2}

D(x , x ) = −x x

1 2

1 2 D(x , x ) =− 2 x x₁ 2 1 2

0 1 2

−1

−2

−2

−1 0 1 2

0 1 2

−1

−2

−2

−1 0 1 2

Feature space Input space

Concluding Remarks: SVM — Pros and Cons

Pros:

• Find the optimal separation hyperplane.

• Can deal with very high dimentional data.

• Some kernels have infinite Vapnik-Chervonenkis dimension (see Computational learning theory, ch. 7 in Tom Mitchell’s book), which means that they can learn very elaborate concepts.

• Usually work very well.

Cons:

• Require both positive and negative examples.

• Need to select a good kernel function.

• Require lots of memory and CPU time.

• There are some numerical stability problems in solving the con- strained QP.

Multi-class Classification with SVM

SVMs can only do binary classification.

For M classes, one can use the one-against-the-rest approach:

construct a hyperplane between class k and the M −1 other classes. ⇒ M SVMs.

To predict the output of a new instance, just predict with each of these M SVMs, and then find out which one puts the prediction furthest into the positive region of the instance space.

SVM Implementations

• SVMlight

• LIBSVM

• mySVM

• Matlab

• Huller

• ...

The SMO (Sequential Minimal Optimization) algorithm John Pratt, 1998

Optimization problem:

maxα W(α) =

m

X

i=1

α_i − 1 2

m

X

i=1 m

X

j=1

y_iy_jα_iα_jx_i ·x_j s. t. 0 ≤ α_i ≤ C, i = 1, . . . , m

m

X

i=1

α_iy_i = 0.

Andrew Ng, Stanford, 2012 fall, ML course, Lecture notes 3.

Algorithm:

Repeat till convergence {

1. Select some pair α_i and α_j to update next (using a heuristic that tries to pick the two that will allow us to make the biggest progress towards the global maximum).

2. Reoptimize W(α) with respect to α_i and α_j, while holding all the other α_k’s (k 6= i, j) fixed.

}

Update equations:

•

αnew, unclipped

j = α_j − ^yj(Ei_η^−Ej) αnew, clipped

j =











H if αnew, unclipped

j > H

αnew, unclipped

j if L ≤ αnew, unclipped

j ≤ H

L if αnew, unclipped

j < L

◦ where

E_k = w · x_k +w₀ −y_k w = Pm

i=1y_iα_ix_i, η = − k x_i −x_j k²

L = max(0, α_j −α_i) ¸si H = min(C, C +α_j −α_j) if y_i 6= y_j L = max(0, αj +α_i −C) ¸si H = min(C, αj +α_j) if y_i = y_j

•

αnew

1 = αold

1 +y₁y₂(αold

2 −αnew

2 )

Assume that α_i, α₂ are the free dual variables, and let the i and j indices be used to index other variables.

Credit: John Pratt, Fast training of SVMs using Sequential Minimal Optimization, 2000 The two Lagrange multipliers must fulfill all the constraints of the full prob- lem.The inequality constraints cause the Lagrange multipliers to lie in the box. The liniar equality constraint causes them to lie on a diagonal line.

Thefore, one step of SMO must find an optimum of the objective function on a diagonal line segment. In this figure, γ = αold

1 + sαold

2 , is a constant that depends on the previous values of α₁ and α₂, and s = y₁y₂.

Proof

[following N. Cristianini and J. Shawe-Taylor, An introduction to SVM, 2000, pag. 138-140]

The objective function:

W(α₁, α₂, . . . , α_m) = Pm

i=1α_i − ¹₂ Pm i=1

Pm

j=1y_iy_jα_iα_jx_i ·x_j v_i not.

=

Pm

j=3 y_jα_jx_j

·x_i = f(x_i)−P2

j=1 y_jα_jx_j ·x_i for i = 1,2

⇒ W(α₁, α₂) = α₁ +α₂ − ¹₂α²₁x²₁ − ¹₂α²₂x²₂ −y₁y₂α₁α₂x₁ ·x₂ −y₁α₁v₁ −y₁α₂v₂ +const From

Pm

i=1y_iα_i = 0 ⇒ αold

1 +αold

2 = αnew

1 +αnew

2 = γ (another constant)

⇒ αnew

1 = αold

1 +y₁y₂(αold

2 −αnew

2 )

s not.

= y₁y₂

⇒ W(α₂) = γ −sα₂ +α₂ − ¹₂(γ −sα₂)²x²₁ − ¹₂α²₂x²₂

−y₁y₂x₁ ·x₂(γ −sα₂)α₂ −y₁v₁(γ −sα₂) −y₂v₂α₂ +const

∂W(α2)

∂α₂ = −s+ 1 + ¹₂ x²₁2s(γ −sα₂) − ¹₂ x²₂2α₂

−y₁y₂(x₁ ·x₂)γ + 2y₁y₂(x₁ ·x₂)sα₂ +y₁v₁s−y₂v₂

= −s+ 1 +x²₁(sγ −α₂) −x²₂α₂ −sγx²₁−sγ (x₁ ·x₂) + y₁v₁s −y₂v₂

Finding the stationary point:

∂W(α₂)

∂α₂ = 0 ⇒ αnew, unclipped

2 (x²₁ +x²₂ −2x₁ ·x₂) = 1−s +γsx²₁ −γs(x₁· x₂) +y₂v₁ −y₂v₂

1−s +γsx²₁ −γs(x1 ·x₂) +y₂v₁ −y₂v₂ = y₂(y2− y₁+γy₁(x²₁ −x₁ ·x₂) +v₁ −v₂) v₁ −v₂ = f(x1) −y₁αold

1 x²₁ −y₂αold

2 x₁ ·x₂

−f(x2) +y₁αold

1 x₁ ·x₂ +y₂αold

2 x²₂

= f(x1) −y₁(γ −sαold

2 )x²₁ −y₂αold

2 x₁ ·x₂

−f(x₂) +y₁(γ −sαold

2 )x₁ ·x₂ +y₂αold

2 x²₂ 1−s +γsx²₁ −γs(x₁ ·x₂) +y₂v₁ −y₂v₂ = y₂(y₂− y₁+f(x₁) + y₁sαold

2 x²₁ −y₂αold

2 x₁ ·x₂

−f(x₂)−y₁sαold

2 x₁ ·x₂ +y₂αold

2 x²₂)

= y₂(f(x₁)−y₁ −f(x₂) + y₂) +αold

2 (x²₁ +x²₂ −2x₁ ·x₂)

= y₂(E₁ −E₂) +αold

2 (x²₁ +x²₂ −2x₁ ·x₂)

⇒ αnew, unclipped

2 (x²₁ +x²₂ −2x1 ·x₂) = y₂(E1 −E₂) +αold

2 (x²₁ +x²₂ −2x1 ·x₂)

⇒ αnew, unclipped

2 = αold

2 − ^y2(E1_η^−E2)