Support Vector Machines

Supervised learning > classification

• attempt to maximize margins => better generalization and avoids overfitting, bigger margin is better
• finding a maximal margin is a quadratic programming problem
• support vectors are between the points nearby separator used for determining the separating boundary
• using kernel trick points $x,y$ are generalized into $K(x,y)$ similarity function and can be transposed to higher dimensional spaces
• choice of kernel function inserts domain knowledge into SVMs

Linear separability

• Goal: find the line of least commitment in linearly separable set of data
• leave as much space as possible around this boundary => how to find this line?

│
⟍
│ ⟍  ▲   ▲
│○  ⟍   ▲   ▲    ▲
│  ○  ⟍    ▲  ▲
│ ○     ⟍     ▲   ▲
│  ○   ○  ⟍  ▲
│○    ○ ○   ⟍     ▲
│   ○     ○   ⟍     ▲
╰──────────── ⟍──────  

Equation of hyperplane: $y=w^{T}x+b$   where $y$ is the classification label, $x$ is input, $w$ and $b$ are parameters of the plane

• equation of the line is $w^{T}x+b=0$
• positive value means part of the class, negative value means not part of the class $y\in \{-1,+1\}$

Draw a separator as close as possible to negative labels, and another as close as possible to the positive labels:

• the equation of the bottom (leftmost) separator is $w^T{x}_1+b=-1$
• the equation of the top (rightmost) separator is $w^T{x}_2+b=1$
• the boundary separator (middle) should have maximal distance from bottom and top separator

$(w^T{x}_1+b)-(w^T{x}_2+b)$   =>   $w^T(x_1-x_2)=2$

${\displaystyle \frac{w^T}{\Vert w\Vert }(x_1-x_2)=\frac{2}{\Vert w\Vert }}$     where the left side is the "margin" to maximize

=> maximize ${\displaystyle \frac{2}{\Vert w\Vert }}$   while   $y_i(w^T{x}_i+b)\ge 1\mathrm{\forall }i$  

i.e. maximize distance while classifying everything correctly.

this problem can be expressed in easier-to-solve form if written as: minimize $\frac{1}{2}\Vert w{\Vert }^2$

It is easier because it is a quadratic programming problem, and it is known how to solve such problems (easily) *and* they always have a unique solution ~~ ❀

$$W(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\text{s.t.}{\alpha }_i\ge 0,\sum _i{\alpha }_i{y}_i=0$$

Once the $\alpha$ that maximize the above equation are known, $w$ can be recovered: $w=\sum _i{\alpha }_i{y}_i{x}_i$ and once $w$ is known, $b$ is can be recovered.

Most $\alpha$ tend to be 0s, only a few support vectors actually are needed to build the SVM

• points far away from the separator have $\alpha \approx 0$
• intuitively points far away do not matter in defining the boundary

Nonlinear separability

How to handle data that cannot be separated linearly:

│         ○  ○
│      ○      ▲  ○
│    ○  ▲   ▲      ○
│   ○  ▲   ▲    ▲  ○
│   ○   ▲  ▲        ○
│   ○ ▲    ▲   ▲   ○
│    ○  ▲     ▲    ○
│      ○   ▲     ○   
│          ○   ○
│
╰────────────────────  

Use function:   $\mathrm{\Phi }(q)=<q^2,q_2^2,\sqrt{2}{q}_1{q}_2>$   transforms 2d point $q$ into 3d space:

$$x^{T}y⇝\mathrm{\Phi }(x{)}^T\mathrm{\Phi }(y)$$

$$\mathrm{\Phi }(x{)}^T=<x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2{>}^T\mathrm{\Phi }(y)=<y_1^2,y_2^2,\sqrt{2}{y}_1{y}_2>$$

$$\mathrm{\Phi }(x{)}^T\mathrm{\Phi }(y)=x_1^2{y}_1^2+2x_1{x}_2{y}_1{y}_2+x_2^2{y}_2^2=(x_1{y}_1+x_2{y}_2{)}^2=(x^{T}y{)}^2$$

=> transform data into higher dimension so it becomes linearly separable.

Here using kernel $K=(x^{T}y{)}^2$     other kernel functions can be used in general.

Kernel function

General form kernel function:

$$K-(x^{T}y+c{)}^p$$

$$W(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i^T{x}_j)$$

Many other functions can be used:   ${\displaystyle (x^{T}y)(x^{T}y{)}^2{e}^{-(\Vert x-y{\Vert }^2/2{\sigma }^2)}\tanh (\alpha x^{T}y+\theta )}$

Kernel function takes some $x_i,x_j$ and returns a number

Points $x_i,x_j$ represent similarity in data => after passing through $K$ it still represents similarity

Kernel function is a mechanism by which we insert domain knowledge into SVM

Criteria for appropriate kernel functions:

• Mercer condition - kernel function must act as a (well-behaved) similarity or distance function.

Evaluation

• learning problem is a convex optimization problem => efficient algorithms exist for solving the minima
• handles (reduces) overfitting by maximizing the decision boundary
• robust to noise; can handle irrelevant and redundant attributes well
• user must provide right kernel function
• high computational complexity for building the model
• missing values are difficult to handle