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   or   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   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   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   of having a high bias or a high variance

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ underfitting about right overfitting

"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 Variance10

The bias-variance tradeoff (reading)

model complexity error
High Bias (Low Variance)High Variance (Low Bias)
  
  
  
  
Support Vector Machines · Bias and Variance11

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 Math12

Lagrangian Multipliers

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

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

Support Vector Machines · The Math13

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 Math14

Hard-Margin SVM Optimization (math)

Support Vector Machines · The Math15

Linear Classifiers (exercise)

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

Support Vector Machines · The Math16

Soft-Margin SVMs (math)

Support Vector Machines · The Math17

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 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 · Kernels18

The Dual-Form Equation

Support Vector Machines · Kernels19

The Kernel Trick

What makes SVMs so powerful is their ability to implicitly   via the "Kernel Trick"

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

Common Kernels

There are three common kernels:

Support Vector Machines · Kernels21

Visualization

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

Matching: Support Vector Machines

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

Practice problems

Support Vector Machines · Review24