Support Vector Machine (SVM)

Support Vector Machine (SVM) Classifiers

---

Definition

• Support Vector Machine (SVM): A system for efficiently training linear learning machines in kernel-induced feature spaces, leveraging generalisation theory and optimisation theory.

---

Scalar Product

• Measures similarity between vectors.
• Defined as:

$$\mathbf{x}\cdot \mathbf{z}=\sum _i{x}_i{z}_i$$

---

Decision Function (Binary Classification)

• Decision function $f(x)\in \mathbf{R}$:

$$f(x_i)\ge 0\Rightarrow y_i=1;f(x_i)<0\Rightarrow y_i=-1$$

---

Linear Discrimination

Linear Separators

• Binary classification separates classes using a linear hyperplane:

$$f(\mathbf{x})=sign({\mathbf{w}}^T\mathbf{x}+b)$$

Optimal Linear Separator

• Maximum Margin Criterion: SVM selects hyperplane with maximum margin between classes.
• Margin ($\rho$): Distance between closest data points (support vectors) of two classes.

Classification Margin

• Distance from data point to hyperplane:

$$r=\frac{{\mathbf{w}}^T\mathbf{x}+b}{||\mathbf{w}||}$$

• Margin width:

$$\rho =\frac{2}{||\mathbf{w}||}$$

---

Statistical Learning Theory

• Maximizing margin reduces complexity and prevents overfitting.
• Generalisation error bounded by function complexity and misclassification error.
• Solution depends only on support vectors.

---

Linear SVM Mathematically

Constraints:

For training set $\{({\mathbf{x}}_i,y_i)\}$:

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$$

Optimization Problem (Primal Formulation):

Minimize:

$$\frac{1}{2}{\mathbf{w}}^T\mathbf{w}$$

subject to constraints above.

Dual Formulation:

Maximize:

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

subject to:

• ${\sum }_i{\alpha }_i{y}_i=0;{\alpha }_i\ge 0$

Solution:

• Weight vector and bias:

$$\mathbf{w}=\sum _i{\alpha }_i{y}_i{\mathbf{x}}_i;b=y_k-{\mathbf{w}}^T{\mathbf{x}}_k,({\alpha }_k\ne 0)$$

• Decision function:

$$f(\mathbf{x})=\sum _i{\alpha }_i{y}_i({\mathbf{x}}_i^T\mathbf{x})+b$$

---

Soft Margin Classification

Motivation:

• Handles non-linearly separable data by allowing misclassifications.

Slack Variables (${\xi }_i$):

• Allow margin violations for difficult/noisy examples.

Optimization Problem with Slack Variables:

Minimize:

$$\frac{1}{2}{\mathbf{w}}^T\mathbf{w}+C\sum _i{\xi }_i$$

subject to:

• $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i;{\xi }_i\ge 0;C>0(\text{controls overfitting})$

Dual Formulation (Soft Margin):

Maximize:

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

subject to:

• $0\le {\alpha }_i\le C;{\sum }_i{\alpha }_i{y}_i=0$

---

Nonlinear Discrimination

Feature Spaces

• Data not linearly separable in original space can become separable in higher-dimensional feature spaces.
• Explicit construction of feature spaces unnecessary due to kernels.

Kernel Trick

• Kernel functions implicitly map data into higher-dimensional spaces.
• Kernel function defined as inner product in feature space:
  • $K({\mathbf{x}}_i,{\mathbf{x}}_j)=<\phi ({\mathbf{x}}_i),\phi ({\mathbf{x}}_j)>$

Common Kernels Examples:

Kernel Type	Formula
Linear	$K(\mathbf{x},\mathbf{z})=⟨x,z⟩={\mathbf{x}}^T\mathbf{z}$
Polynomial	$K(\mathbf{x},\mathbf{z})=(1+⟨x,z⟩{)}^p$
Gaussian (RBF)	$K(\mathbf{x},\mathbf{z})=e^{-\frac{\Vert \mathbf{x}-\mathbf{z}{\Vert }^2}{2{\sigma }^2}}$
Two-layer Perceptron	$K(\mathbf{x},\mathbf{z})=\tanh ({\beta }_0{x}^{T}z+{\beta }_1)$

---

Non-linear SVM Mathematically

Dual Problem with Kernels:

Maximize:

• $Q(\alpha )={\sum }_i{\alpha }_i-\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)$

Subject to constraints same as linear case.

Decision Function (Kernelized):

• $f(\mathbf{x})={\sum }_i{\alpha }_i{y}_{i}K({\mathbf{x}}_i,\mathbf{x})+b$

---

Theoretical Justification for Maximum Margins

• Vapnik’s theorem bounds VC dimension ($h$):
  • $h\le min[\frac{D^2}{{\rho }^2},m_0]+1;$
    • $D=\text{diameter enclosing data}$,
    • $m_0=\text{dimensionality}$,
    • $\rho =\text{margin width}$
• Maximizing margin minimizes classifier complexity irrespective of dimensionality.

---

SVM Applications & Extensions

Applications:

• Text classification, genomic data analysis, regression, principal component analysis, etc.

Extensions of SVMs include:

• Regression, Variable Selection, Boosting, Density Estimation, Unsupervised Learning, Novelty/Outlier Detection, Feature Detection, Clustering

---

Important Concepts Recap:

Concept	Description
Support Vectors	Critical data points defining the hyperplane
Margin	Distance between support vectors of different classes
Kernel Trick	Implicitly maps data into higher-dimensional space
Soft Margin	Allows misclassifications for noisy/non-separable data
Quadratic Optimization	Method for solving SVM optimization problems