Advanced Machine Learning

13: Support Vector Machines

Schedule (you are here )

Outline for the lecture

• Connecting the Dots: The Road to SVM
• Max-Margin Hyperplane & Geometric Margin
• Lagrange Duality & KKT Conditions
• Dual SVM Formulation & Support Vectors
• Kernel Trick & Mercer's Theorem
• Soft-Margin SVM & Hinge Loss View
• SVM in Practice (Scaling, CV, Calibration)
• Take Home Points

Connecting the Dots: The Road to Non-parametric Methods & SVM

Max Margin Classifiers

bayesian decision boundary

• If $\prob{P}{\omega_1|\vec{x}} \gt \prob{P}{\omega_2|\vec{x}}$, decide $\omega_1$
• If $\prob{P}{\omega_1|\vec{x}} \lt \prob{P}{\omega_2|\vec{x}}$, decide $\omega_2$
• $\prob{P}{error|\vec{x}} = \min[\prob{P}{\omega_1|\vec{x}}, \prob{P}{\omega_2|\vec{x}}]$

Decision boundary: 2 classes

In the general case, we need to non-parametrically estimate the densities

$\prob{P$_{KDE}$}{\vec{x}} = \frac{1}{Nh^d} \sum_{n=1}^N \prob{K}{\frac{\vec{x} - \vec{x}^n}{h}}$, where $\prob{K}{\vec{x}} = (2\pi)^{-d/2}e^{-\frac{1}{2}\vec{x}^T\vec{x}}$

Decision boundary is sensitive to outliers!

Restricted Bayes optimal classifier

Definition: Given a joint distribution $\prob{P$_{KDE}$}{\vec{x},C}$ and a set of classifiers $\cal H$, we say that $h^*$ is a restricted Bayes optimal classifier with respect to $\cal H$ and ${\rm P}_{KDE}$

if $h^* \in {\cal H}$ and $\forall h\in {\cal H}$, $\prob{error}{h^*:{\rm P}_{KDE}} \le \prob{error}{h: {\rm P}_{KDE}}$

Restricted Decision boundary

Max-margin hyperplane is Bayes optimal

Max-margin Classifier

A Hyperplane

• $r_{\color{red}{\vec{x}}} = \frac{|\vec{w}^T{\color{red} \vec{x}} + b|}{\|\vec{w}\|}$
• $r_{\color{red}{\vec{x}}} = \frac{{\color{red}{y}}(\vec{w}^T{\color{red} \vec{x}} + b)}{\|\vec{w}\|}$

Interactive: Decision Hyperplane & Margin Band

Decision "Surface"

Observation

The distance does not depend on $\|\vec{w}\|$

• $r_i = \frac{y_i(\vec{w}^T{\vec{x}_i} + b)}{\|\vec{w}\|}$
• Scaling by $k$
• $\frac{y_i(k\vec{w}^T{\vec{x}_i} + kb)}{\|k\vec{w}\|} = \frac{k y_i(\vec{w}^T{\vec{x}_i} + b)}{k \|\vec{w}\|} = \frac{y_i(\vec{w}^T{\vec{x}_i} + b)}{\|\vec{w}\|}$
• We are free to set $y_i(\vec{w}^T{\vec{x}_i} + b)$ to whatever we want!
• Let's set it to $y_*(\vec{w}^T{\vec{x}_*} + b) = 1$ for the nearest point

Linear SVM Classifier

• The gap is distance between parallel hyperplanes \begin{align} \vec{w}^T\vec{x} + b &= -1\\ \vec{w}^T\vec{x} + b &= 1\\ \end{align}
• The gap is distance between parallel hyperplanes \begin{align} \vec{w}^T\vec{x} + (b + 1) &= 0\\ \vec{w}^T\vec{x} + (b - 1) &= 0\\ \end{align}
• $D = |b_1 - b_2|/\|\vec{w}\|$
• $D = 2/\|\vec{w}\|$

To maximize the gap, need to minimize $\|\vec{w}\|$ or equivalently $\frac{1}{2}\|\vec{w}\|^2$ ($\frac{1}{2}\vec{w}^T\vec{w}$)

Linear SVM Classifier

• Instances must be correctly classified \begin{align} \vec{w}^T\vec{x}_i + b & \le -1 \mbox{ if } y_i = -1\\ \vec{w}^T\vec{x}_i + b & \ge +1 \mbox{ if } y_i = +1\\ \end{align}
• Equivalently $y_i(\vec{w}^T\vec{x}_i + b) \ge 1$

Want to minimize $\frac{1}{2}\|\vec{w}\|^2$ subject to $y_i(\vec{w}^T\vec{x}_i + b) \ge 1$ for $i=1,\dots, N$

Classify new instance $\vec{x}$ as $f(\vec{x}) = \mbox{sign}(\vec{w}^T\vec{x} + b)$

Linear SVM: primal formulation

Minimize $\frac{1}{2}\|\vec{w}\|^2$ subject to $y_i(\vec{w}^T\vec{x}_i + b) - 1 \ge 0$ for $i=1,\dots, N$

• Primal formulation of linear SVM
• It is a convex quadratic programming (QP) optimization problem with $d$ variables and $N$ constraints

\begin{align} \underset{\vec{w} \in \RR^m}{\argmin} \vec{w}^T {\mathbf Q} \vec{w} & + \vec{w}^T\vec{c} + \epsilon \\ {\mathbf A}\vec{w} & \le \vec{b} \\ {\mathbf A} \in \RR^{n\times m}, \vec{w} & \in \RR^m, \vec{b}\in \RR^n\\ {\mathbf C}\vec{w} & = \vec{d} \\ {\mathbf C} \in \RR^{s\times m}, \vec{d} &\in \RR^s\\ \end{align}

Lagrange Duality

c.f. Appendix E: Lagrange Multipliers "Pattern Recognition and ML" C. M. Bishop

Lagrange Duality: general form

Karush-Kuhn-Tucker (KKT) Necessary Optimality Conditions

1. Stationarity: $\nabla_x \Lambda = 0$   |   2. Primal Feasibility: $c_i(x^*) \ge 0, \; g_i(x^*) \le 0, \; h_i(x^*) = 0$
3. Dual Feasibility: $\alpha_i \ge 0, \; \lambda_i \ge 0$   |   4. Complementary Slackness: $\alpha_i c_i(x^*) = 0, \; \lambda_i g_i(x^*) = 0$

Karush-Kuhn-Tucker (KKT) conditions

For convex problems with regular constraints (Slater's condition), KKT conditions are both necessary and sufficient for global optimality!

Interactive Lagrange Multipliers

Lagrange Duality: example 1

$\min_x x^2$
s.t. $x \ge b$

$\min_x x^2$

$x^* = 0$ $\min_x x^2$
s.t. $x\ge -1$ $x^* = 0$ $\min_x x^2$
s.t. $x\ge 1$ $x^* = 1$

Lagrange Duality: example 1

$\min_x x^2$
s.t. $x \ge b$ or $x-b\ge 0$

Let's move the constraint to the objective Lagrangian

$L(x, \alpha) = x^2 - \alpha(x-b)$
s.t. $\alpha \ge 0$

Solve: $\min_x \max_{\alpha} L(x, \alpha)$
s.t. $\alpha \ge 0$

Interactive: Primal vs. Dual Saddle Explorer

Lagrange Duality: example 2

Find the largest area rectangle inside an ellipse

Lagrange Duality: example 2

Find the largest area rectangle inside an ellipse

• maximize the area $4xy$
• subject to
• $\frac{x^2}{a^2} + \frac{y^2}{b^2} \le 1$

Ellipse equation

$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$

• maximize
• $\Lambda(x,y,\alpha) = 4xy - \alpha (\frac{x^2}{a^2} + \frac{y^2}{b^2} - 1)$
• subject to
• $\alpha \ge 0$

Let's solve it

Lagrange Duality: example 2

Find the largest area rectangle inside an ellipse

Lagrange Duality: example 2

Main point

Using Lagrangian multipliers and KKT conditions can convert a constrained problem into an unconstrained saddle-point problem.

Dual formulation of SVM

Linear SVM: dual formulation

• Lagrangian saddle problem: $\min_{\vec{w}, b} \max_{\vec{\alpha} \ge 0} \Lambda(\vec{w}, b, \vec{\alpha}) = \frac{1}{2}\|\vec{w}\|^2 - \sum_{i=1}^N \alpha_i \left[ y_i(\vec{w}^T\vec{x}_i + b) - 1 \right]$
• Stationarity conditions ($\nabla_{\vec{w}, b} \Lambda = 0$):
  $$\frac{\partial\Lambda}{\partial \vec{w}} = 0 \implies \vec{w} = \sum_{i=1}^N \alpha_i y_i \vec{x}_i \qquad \text{and} \qquad \frac{\partial\Lambda}{\partial b} = 0 \implies \sum_{i=1}^N \alpha_i y_i = 0$$
• Substitute $\vec{w}$ and the constraint into $\Lambda$ to obtain the Dual Quadratic Program:
  $$\max_{\vec{\alpha}} \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i,j=1}^N \alpha_i \alpha_j y_i y_j (\vec{x}_i^T\vec{x}_j) \quad \text{s.t.} \quad \alpha_i \ge 0, \; \sum_{i=1}^N \alpha_i y_i = 0$$
• Recovering the classifier: $f(\vec{x}) = \text{sign}\left(\sum_{i=1}^N \alpha_i y_i (\vec{x}_i^T\vec{x}) + b\right)$   |   $b = y_k - \vec{w}^T\vec{x}_k$ for any SV ($\alpha_k > 0$).

Why "Support Vectors"? (Sparsity via KKT)

KKT Complementary Slackness:   $\alpha_i \left[ y_i(\vec{w}^T\vec{x}_i + b) - 1 \right] = 0 \quad \forall i$

Linear SVM: problems and solutions

The data may not be linearly separable

• $\phi(\vec{x})$: map the data into higher dimensions and hope for the best
• Soft-margin: allow some error

Support Vector Machines

Max Margin Classifiers

• Given two classes $A$ and $B$
  Data is a set of labeled examples $\{(\vec{x}_i,y_i)\}_{i=1}^N$
• Bayesian Decision Boundary: Distributions are known \begin{align}\nonumber g(\vec{x}) = P(A|\vec{x}) - P(B|\vec{x}) =0 \end{align}
• Maximum Margin Hyperplane: Only data is given

Mapping to Higher Dimensions

• A two class problem:
  not separable by a line
• Map each point into a higher dimensional space: \begin{align} \nonumber \vec{\eta}_i = \Phi(\vec{x}_i) \end{align}
• Choose $\Phi$ so the data becomes linearly separable \begin{align} \nonumber \Phi(\vec{x}) = (x_1^2,\sqrt{2}x_1x_2,x_2^2) \end{align}

Kernel Trick

Appropriate mappings are hard to construct. What to do?

• Dimensions can be many even $\infty$! Have to compute very expensive inner product?
• Avoid it by defining Hilbert spaces with kernels (and Mercer's theorem) \begin{align}\nonumber \langle\Phi(\vec{x}),\Phi(\vec{y})\rangle &=& \vec{k}(\vec{x},\vec{y})\\ \nonumber (x_1^2,\sqrt{2}x_1x_2,x_2^2) (y_1^2,\sqrt{2}y_1y_2,y_2^2)^T &=& (\vec{x}\cdot\vec{y})^2 \\\nonumber x_1^2y_1^2 + 2x_1x_2y_1y_2 + x_2^2y_2^2 &=& (x_1y_1 + x_2y_2)^2 \end{align}
• Take a linear algorithm, replace inner products with kernels and get a nonlinear algorithm as a result!

Kernel Trick for SVM

Maximize $\sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i,j=1}^N \alpha_i\alpha_j y_i y_j (\vec{x}_i^T\vec{x}_j)$
subject to $\alpha_i \ge 0$ and $\sum_{i=1}^N \alpha_i y_i = 0$
Final classifier: $f(\vec{x}) = \mbox{sign}\left(\sum_{i=1}^N \alpha_i y_i (\vec{x}_i^T\vec{x}) + b\right)$

Replace inner product $\vec{x}_i^T\vec{x}_j$ with kernel $K(\vec{x}_i,\vec{x}_j)$:
Maximize $\sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i,j=1}^N \alpha_i\alpha_j y_i y_j K(\vec{x}_i,\vec{x}_j)$
subject to $\alpha_i \ge 0$ and $\sum_{i=1}^N \alpha_i y_i = 0$
Final classifier: $f(\vec{x}) = \mbox{sign}\left(\sum_{i=1}^N \alpha_i y_i K(\vec{x}_i, \vec{x}) + b\right)$

Matrix form: Maximize $\vec{\alpha}^T\mathbf{1} - \frac{1}{2} \vec{\alpha}^T \mathbf{Y}\mathbf{G}\mathbf{Y} \vec{\alpha}$
subject to $\vec{\alpha} \ge 0$ and $\vec{\alpha}^T \vec{y} = 0$,   where $\mathbf{Y} = \operatorname{diag}(\vec{y})$, $G_{ij} = K(\vec{x}_i, \vec{x}_j)$

Mercer's Theorem

Common Kernels & Hyperparameters

Kernels do not guarantee linear separability

Soft Margin SVM

Introduce slack variables $\xi_i \ge 0$ allowing margin violations

$$y_i(\vec{w}^T\vec{x}_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0$$

$\xi_i = 0$: correctly outside or on margin.
$0 < \xi_i \le 1$: inside margin, correctly classified.
$\xi_i > 1$: misclassified!

Dual Soft-Margin QP: Maximize $\vec{\alpha}^T\mathbf{1} - \frac{1}{2} \vec{\alpha}^T\mathbf{Y}\mathbf{G}\mathbf{Y}\vec{\alpha}$
subject to $0 \le \alpha_i \le C$ and $\vec{\alpha}^T \vec{y} = 0$

Soft Margin SVM Primal & Box Constraint

Primal Problem: $\min_{\vec{w}, b, \vec{\xi}} \frac{1}{2}\|\vec{w}\|^2 + C\sum_{i=1}^N \xi_i \quad \text{s.t.} \quad y_i(\vec{w}^T\vec{x}_i + b) \ge 1 - \xi_i, \; \xi_i \ge 0$
Multiplier $\beta_i \ge 0$ for $\xi_i \ge 0 \implies \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \beta_i = 0 \implies \alpha_i + \beta_i = C \implies \mathbf{\alpha_i \le C}$!

Interactive: 2D Kernel SVM Playground

The Loss Function Perspective: Hinge Loss

SVM in Practice: Engineering Workflow

from sklearn.svm import SVC
clf = SVC(C=1.0, kernel='rbf', gamma='scale',
          probability=True)
clf.fit(X_train, y_train)

Take Home Points

• Restricted Bayes Optimal: SVM finds the unique global optimum of a strictly convex quadratic program maximizing geometric margin $\gamma = 2/\|\vec{w}\|$.
• Support Vectors & Sparsity: By KKT complementary slackness, only critical boundary points have $\alpha_i > 0$. Uninformative points outside the margin have $\alpha_i = 0$ and can be discarded.
• The Kernel Trick: Replacing inner products $\vec{x}^T\vec{z}$ with positive semi-definite kernels $K(\vec{x},\vec{z})$ constructs non-linear decision surfaces in high/infinite dimensions with zero dimensional penalty.
• Soft Margin & Hinge Loss: Slack variables $\xi_i$ balance margin maximization against classification errors, corresponding to an $\ell_2$-regularized empirical Hinge loss objective.
• SVM in Practice: Always standardize features, tune $(C, \gamma)$ jointly on a logarithmic grid, use OvR/OvO for multiclass, and apply Platt calibration when probabilities are required.

Reading References

• Textbook Chapters:
  • C. Bishop, Pattern Recognition and Machine Learning (2006) — Chapter 7 (Sparse Kernel Machines, pp. 325–360).
  • S. Shalev-Shwartz & S. Ben-David, Understanding Machine Learning (2014) — Chapter 15 (Support Vector Machines, pp. 201–220).
  • K. Murphy, Machine Learning: A Probabilistic Perspective (2012) — Chapter 14 (Kernel Methods & SVMs).
• Foundational Papers:
  • C. J. C. Burges (1998). A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery.
  • S. Tong & D. Koller (2000). Support Vector Machine Active Learning with Applications to Text Classification. JMLR.
  • B. Schölkopf, R. Herbrich, & A. J. Smola (2001). A Generalized Representer Theorem. COLT / JMLR.