Support Vector Machine (SVM)

Definition. An SVM is a supervised (mainly binary) classification algorithm that learns the hyperplane

$$w \cdot x + b = 0$$

which separates the two classes with the maximum margin.

1. Maximum-margin idea

• Many hyperplanes may separate two classes; SVM chooses the one farthest from the nearest point of each class — the margin, of width $2/\|w\|$ for the canonical hyperplanes $w \cdot x + b = \pm 1$.
• Hard-margin optimisation: $\min_{w,b} \; \tfrac{1}{2}\|w\|^2$ subject to $y_i (w \cdot x_i + b) \ge 1$ for every training point. Minimising $\|w\|^2$ is the same as maximising the margin.
• Soft margin — when the classes overlap, slack variables $\xi_i \ge 0$ are permitted with a penalty $C \sum_i \xi_i$; the parameter $C$ trades margin width against training error.
• This is structural risk minimisation: a wider margin gives a better bound on generalisation error, so the model is not merely fitting the training set.

2. Support vectors

• The training points that lie on the margin (or violate it) are called support vectors.
• Only the support vectors determine the hyperplane — deleting any other training point changes nothing, so the model is sparse and robust.
• All other points can be discarded after training; prediction depends only on the support vectors, which keeps the stored model small.

3. Kernel trick

• If the data is not linearly separable, it is mapped by $\phi$ into a higher-dimensional space in which a linear separator exists.
• The kernel function $K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)$ evaluates that inner product directly, without ever constructing $\phi$ explicitly.
• Common kernels: linear $x \cdot y$, polynomial $(x \cdot y + c)^d$, RBF / Gaussian $\exp(-\gamma \, \|x - y\|^2)$, and sigmoid.
• Kernels let SVM model complex non-linear decision boundaries at modest computational cost.

4. Comparison with other classifiers

Aspect	SVM	Decision tree	Naive Bayes	KNN
Core idea	Max-margin hyperplane	Recursive attribute splits	Bayes' rule + independence	Vote of k nearest points
Non-linearity	Kernel trick	Inherent (axis-parallel splits)	Limited	Inherent
High-dimensional data	Very good	Overfits easily	Good	Suffers from distance concentration
Training cost	High (quadratic programming)	Low	Very low	None (lazy learner)
Prediction cost	Low (only support vectors)	Low	Low	High (scans training set)
Robustness to noise	Soft margin absorbs it	Sensitive	Moderate	Very sensitive
Interpretability	Low (black box)	High (readable rules)	Medium	Low

5. Merits and limitations

• Advantages — performs well in high dimensions, memory-efficient (stores only support vectors), solves a convex problem with a unique global optimum, and has strong theoretical generalisation guarantees.
• Limitations — training is slow on very large datasets, results are sensitive to the choice of kernel and $C$, the formulation is inherently binary (multiclass handled by one-vs-one or one-vs-rest), and it does not naturally output calibrated probabilities.

Conclusion

SVM recasts classification as a convex quadratic optimisation problem with a unique global solution, maximises the separating margin, and extends to non-linear boundaries through the kernel trick — the reasons it became one of the most reliable classifiers for medium-sized, high-dimensional datasets.