Introduction to the maths of SVMs

The machine learning technique Support Vector Machines get their names from the mathematical concept of supports - that is, the smallest closed set of a topological space that do not map to zero. We'll see this below.

They deal purely with numeric data but nominal values can easily be mapped to numeric values by having a column for all categories and a value 1 for those data that fall into that category and 0 for all others.

They are known to have a "low generalization error, [be] computationally inexpensive, easy to interpret results" [1] but the maths behind them is pretty complicated.

What is the kernel trick?

I found this nice explanation here.

It provides a bridge from linearity to non-linearity to any algorithm that can expressed solely on terms of dot products between two vectors. It comes from the fact that, if we first map our input data into a higher-dimensional space, a linear algorithm operating in this space will behave non-linearly in the original input space. Now, the Kernel trick is really interesting because that mapping does not need to be ever computed. If our algorithm can be expressed only in terms of a inner product between two vectors, all we need is replace this inner product with the inner product from some other suitable space. That is where resides the “trick”... This is highly desirable, as sometimes our higher-dimensional feature space could even be infinite-dimensional and thus unfeasible to compute.

An example

A great example can be found here. Chitta Ranjan takes the classic example of points that are not linearly separable in 2-dimensions and decides that he will use 3-dimensions. The function he uses for this is:

Φ(x) → x₁, x₂, √2 x₁x₂

Leading to a similarity measure of:

<Φ(x_i), Φ(x_j) >

Although this raising the number of dimensions does indeed separate the data, his friend, Sam, notes that you this can equivalently be written as:

<x_i, x_j > ²

All Sam had done "is realize there is some higher dimensional space which can separate the data. Choose a corresponding Kernel and voila! He is now working in the high-dimension while doing computation in the original low dimensional space."

Which Kernel?

Although lists of kernels exist, "people just go with the infinite dimension by using the Gaussian (RBF) Kernel. RBF is the most commonly used Kernel. It has a tuning hyperparameter σσ that is tuned to choose between a smooth or curvy boundary. In short, as a rule of thumb, once you realize linear boundary is not going to work try a non-linear boundary with an RBF Kernel."

Prerequisites

In an attempt to understand things better, I turned to Learing with Kernels (Schölkopf). These are some notes I made:

ℌ, a feature space that has a dot product.
Χ, a set that contains the inputs.
Φ, a map from the inputs to the feature space. This may be trivial or a more exotic, non-linear mapping.
m is the number of inputs and n is the size of a feature vector.
k(x, x') is the kernel function that gives us a similarity measure.

A naive implementation

Given two clusters, we can calculate their centres:

c₊ = m₊^-1 Σ_{i|yi=+1} x_i

c_- = m_-^-1 Σ_{i|yi=-1} x_i

where we differentiate the two clusters with + and - symbols.

We define w as the vector between the two centres, that is c₊-c_-.

Half way between these two clusters (c₊+c_-/2) is point c. Which cluster x is closest to can be given by the sign of <x-c, w>. Or, to put it another way, the sign of:

<x-c, w> = <x-(c₊+ c_-/ 2), c₊-c_-> = <x, c₊>-<x, c_-> - b

where b = (||c₊||²- ||c_-||²) / 2

The sign of this equation essentially gives us our decision function, y. However, to use the kernel trick in this equation, we need to express everything in terms of x. Since w and b can be expressed in terms of c and c in terms of x, this gives:

y = sgn(m₊^-1 Σ_{i|yi=+1} <x, x_i> - m_-^-1 Σ_{i|yi=-1} <x, x_i > + b)
  = sgn(m₊^-1 Σ_{i|yi=+1} k(x, x_i) - m_-^-1 Σ_{i|yi=-1} k(x, x_i) + (m₊^-2 Σ_{i,j|yi=+1} k(x_i, x_j) - m_-^-2 Σ_{i,j|yi=-1} k(x_i, x_j))/2)

Aside: if we then choose the origin to be equidistant from the two two centres, then b becomes zero. And if the kernel function, k, is normalized such that we can view it as a probability density function (that is, for a given x' the probability ) then:

∫_Χ k(x, x') dx = 1 ∀ x ∈ Χ

This leads to the equation for y taking the form:

y = sgn(Σ α_i k(x, x_i) + b)

which looks like the Bayes Classifier apparently.

A better implementation

This is just a toy implementation where the hyperplane is just the mean between the two centroids. What we really want is a hyperplane that maximizes the distance between the clusters. That is, given a decision function f,

f(x) = sgn(<x, w>+ b)

we want to maximize the minimum distance between the two sets of points either side of the boundary. Let's say that the two points in each set that are the closest are x₁ and x₂. With the right scaling, we can say:

<x₁, w> + b = 1
<x₂, w> + b = -1

Taking these as simultaneous equations, we can eliminate b and get:

<x₁ - x₂, w> = 2

or equivalently:

<x₁ - x₂, w / |w|> = 2 / |w|

The left hand side of this equation is the distance between  x₁ and x₂ projected on the normal of the hyperplane. If we want to maximize this, we want to maximize (2/|w|), or to put it another way, minimize |w|.

To this end, let's introduce an objective function:

τ(w) = |w|² / 2

that we wish to maximize (why we square it and divide it by 2 will become apparent later. Suffice to say minimizing is the same as minimizing τ).

Now, one solution would be the trivial w = 0 so we need to add the inequality constraints:

y_i (<x_i, w>+ b) ≥ 1

Now we use Lagrange multipliers. That is, we note at the minimum of τ that dτ/dw is 0 (standard calculus). Let's propose the Lagrangian we want to maximize as:

L(w, b, α) = τ(w) - Σ_i=1^m α_i (y_i (<x_i, w>+ b) - 1)

Note that if the inequality constraint is not exact, the term in the summation is negative. Since we we want to maximize the Lagrangian, necessarily its corresponding α_i must be zero (note that we are subtracting the summation). So, α_i will only be non-zero for points that make the inequality constraint exact. This is the Karush-Kuhn-Tucker condition. It agrees with our intuition that we only care about nearest points. All other points are irrelevant.

Also, these non-zero α_is will obviously have their corresponding term equal to 0 as they're exactly 1, and we subtract 1 from such (in)equality constraints. This is enough information to make our Lagrangian.

Differentiating the Lagrangian by w yields:

w = Σ_i=1^m α_i y_i x_i

and by b yields:

Σ_i=1^m α_i y_i = 0

This latter equation compliments the former by being a constraint on the solution.

Substituting this equation for w into that for τ(w), we can now say that its minimum is at:

Σ_i,j=1^m α_i α_j y_i y_j <x_i, x_ij>

and the objective function we started with at the top of this section is now:

f(x) = sgn(Σ_i=1^m α_i y_i <x, x_i>+ b)

The hard part is calculating the alphas etc in that minimization. This is the dual optimization problem and it beyond the scope of this post.

Shattering

One last point is how effective the boundary is. "Since the labels are in {±1} there are at most 2^m different labelings for m patterns. A very rich function class might be able to realize all 2^m separations, in which case it is said to shatter the m points."

[1] Machine Learning in Action published by Manning.