Unit 02 · Chapter 9

Support Vector Machines

Support Vector Machines01

Linear Classifiers (exercise)

Given the dataset below, where would a Perceptron draw a separating line?

Support Vector Machines · Margins02

Linear Classifiers

Given the dataset below, where would a Logistic Regression draw a separating line?

Support Vector Machines · Margins03

Margin Classifier

Support Vector Machines · Margins04

Support Vectors

Support Vectors are the points on or inside the margin that define the decision boundary

Support Vector Machines · Margins05

Support Vector Machines (SVMs)

Support Vector Machines are a kind of Binary Classifier that focus on the concept of a margin to make more robust and efficient classifiers

Support Vector Machines · Margins06

SVMs in Biology

Golub et al. (1999) measured the activity of about 7,000 genes in samples from 72 leukemia patients and asked: can we tell the two main types (AML and ALL) apart from the genes alone?

That's thousands of features and only dozens of samples, so infinitely many lines separate the training data perfectly and most of them are bad.

Picking the line with the largest margin is a sensible way to choose, and SVMs (Furey et al., 2000) became one of the standard tools for classifying tumors from gene activity.

Support Vector Machines · Margins07

Hard-Margin vs. Soft-Margin SVMs

hard margin hard margin soft margin soft margin

Hard-Margin SVMs allow no misclassifications, much like a Perceptron

Soft-Margin SVMs allow for some misclassifications to allow for a more robust decision boundary

Support Vector Machines · Margins08

Underfitting and Overfitting

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ underfitting about right overfitting
Support Vector Machines · Bias and Variance09

The bias-variance tradeoff (reading)

Underfitting and overfitting are symptoms of having a high bias or a high variance

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ underfitting about right overfitting
Support Vector Machines · Bias and Variance10

The bias-variance tradeoff (reading)

"the bias–variance tradeoff describes the relationship between a model's complexity, the accuracy of its predictions during training, and the accuracy of its predictions during testing." (Modified from Wikipedia)

Support Vector Machines · Bias and Variance11

The bias-variance tradeoff (reading)

model complexity error
Support Vector Machines · Bias and Variance12

The bias-variance tradeoff (reading)

High Bias (Low Variance)High Variance (Low Bias)
underfittingoverfitting
model too simplemodel too complex
poor on training and test datagreat on training, poor on test data
e.g. a line through a curve, small Ce.g. degree 8 on 13 games, huge C and γ
Support Vector Machines · Bias and Variance13

Hard-Margin Classifier Definition

Support Vector Machines · The Math14

Hard-Margin Classifier Definition

We want to minimize ||ω|| such that

all points are correctly classified and

all points are on or outside of the margin

Support Vector Machines · The Math15

Lagrangian Multipliers

A strategy for finding the local maxima and minima of a function subject to constraints

L(x, \alpha) = f(x) - \alpha\, g(x), \qquad \alpha \ge 0 L(x, \alpha) = f(x) - \alpha\, g(x), \qquad \alpha \ge 0

Essentially, allows us to wrap the "s.t." into a single cost/error/loss function

Support Vector Machines · The Math16

Regularization

Lagrangian Multipliers are also how regularization works

L2 L1 cost budget

They allow us to transform the "s.t." into a single cost/error/loss function

Support Vector Machines · The Math17

Hard-Margin SVM Optimization (math)

\min_{\omega,b}\ \frac{1}{2}\norm{\omega}^2 \quad \text{subject to} \quad y_i(x_i \omega\T + b) \ge 1\ \text{ for every } i \min_{\omega,b}\ \frac{1}{2}\norm{\omega}^2 \quad \text{subject to} \quad y_i(x_i \omega\T + b) \ge 1\ \text{ for every } i L = \frac{1}{2}\norm{\omega}^2 - \sum_i \alpha_i \bb{y_i(x_i \omega\T + b) - 1} \text{set the slopes in } \omega \text{ and } b \text{ to } 0 \omega = \sum_i \alpha_i y_i x_i, \qquad \sum_i \alpha_i y_i = 0 L = \frac{1}{2}\norm{\omega}^2 - \sum_i \alpha_i \bb{y_i(x_i \omega\T + b) - 1}; \text{set the slopes in } \omega \text{ and } b \text{ to } 0; \omega = \sum_i \alpha_i y_i x_i, \qquad \sum_i \alpha_i y_i = 0
Support Vector Machines · The Math18

Linear Classifiers (exercise)

Given the dataset below, where would a Perceptron draw a separating line?

Support Vector Machines · The Math19

Soft-Margin SVMs (math)

\min_{\omega,b,\varepsilon}\ \frac{1}{2}\norm{\omega}^2 + C\sum_i \varepsilon_i \text{subject to} y_i(x_i \omega\T + b) \ge 1 - \varepsilon_i, \qquad \varepsilon_i \ge 0 \min_{\omega,b,\varepsilon}\ \frac{1}{2}\norm{\omega}^2 + C\sum_i \varepsilon_i; \text{subject to}; y_i(x_i \omega\T + b) \ge 1 - \varepsilon_i, \qquad \varepsilon_i \ge 0 \min_{\omega,b}\ \frac{1}{2}\norm{\omega}^2 + C\sum_i \max(0,\ 1 - y_i\yhat_i) \min_{\omega,b}\ \frac{1}{2}\norm{\omega}^2 + C\sum_i \max(0,\ 1 - y_i\yhat_i)
Support Vector Machines · The Math20

Non-Linearly Separable Data (reading)

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ -400 -300 -200 -100 0 +100 +200 +300 +400 yard difference (Notre Dame minus opponent) decided by more than 8 decided by 8 or fewer
Support Vector Machines · Kernels21

Non-Linearly Separable Data (reading)

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ -400 -300 -200 -100 0 +100 +200 +300 +400 yard difference, x −1 0 1 2 3 4 5 6 7 x² -102 yards +126 yards decided by 8 or fewer decided by more SVM boundary

Changing your space is a very powerful idea!

Support Vector Machines · Kernels22

The Dual-Form Equation

\max_{\alpha}\ \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j\, y_i y_j\, x_i x_j\T \text{subject to} 0 \le \alpha_i \le C, \qquad \sum_i \alpha_i y_i = 0 \max_{\alpha}\ \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j\, y_i y_j\, x_i x_j\T; \text{subject to}; 0 \le \alpha_i \le C, \qquad \sum_i \alpha_i y_i = 0
Support Vector Machines · Kernels23

The Kernel Trick

What makes SVMs so powerful is their ability to implicitly increase the dimensionality of our data via the "Kernel Trick"

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ x₁, x₂ z = x₁² + x₂² kernel
Support Vector Machines · Kernels24

Common Kernels

There are three common kernels:

K(x, x\p) = x\, x\p{}\T K(x, x\p) = (\gamma\, x\, x\p{}\T + r)^p K(x, x\p) = \exp(-\gamma \norm{x - x\p}^2) K(x, x\p) = x\, x\p{}\T; K(x, x\p) = (\gamma\, x\, x\p{}\T + r)^p; K(x, x\p) = \exp(-\gamma \norm{x - x\p}^2)
Support Vector Machines · Kernels25

Visualization

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/
Support Vector Machines · Kernels26

Matching: Support Vector Machines

  B   MarginA. Allows some misclassifications for a more robust decision boundary
  H   Support vectorsB. The gap between the decision boundary and the closest points of each class
  C   Hard-margin SVMC. Allows no misclassifications, much like a Perceptron
  A   Soft-margin SVMD. Fast and simple, but only finds a straight-line (hyperplane) boundary
  I   Lagrangian multipliersE. Builds very complex boundaries from distances; needs tuning of γ and C
  F   Kernel trickF. Computes dot products in a higher-dimensional space without transforming the data
  D   Linear kernelG. Finds curved boundaries of a chosen degree; can overfit at high degrees
  G   Polynomial kernelH. The points on or inside the margin that define the decision boundary
  E   RBF kernelI. Wrap the "s.t." constraints into a single cost/error/loss function
Support Vector Machines · Review27

Practice problems

Support Vector Machines · Review28

Practice problems

Support Vector Machines · Review29

Practice problems

Support Vector Machines · Review30