08 - SVM - lec. 11, 12, 13
ucla | CS M146 | 2023-05-03T13:57
Table of Contents
Supplemental
Perceptron Review
Constrained Optimization
$\min_x x^2\quad\text{s.t.}\quad x\ge b$
Lecture
Linear Separators
Perceptron Review
Choosing a separator
- the last separator is robust to nooise in the dataset
Margin of a Linear Separator
- given a binary classifier with (1,-1) labels and a linear separator decision boundary
- the margin of aapoint $\bm x^{(i)}$ w.r.t. the hyperplane (linear separator) is the perpendicular distance between the point and the hyperplane
$\gamma^{(i)}=\text{length}(AB)$
Computing Margin
proof
- assuming $\bm \theta$ defines the hyperplane that perfectly separates the data with no bias
- we assume the point wee are tryiing to calculate margin for $\bm x^{(i)}$ has a positive label $y^{(i)}=1$ thus the hypothesis >0
- $\bm \theta/|\bm\theta|_2$ is the unit normal vector to the plane
- thus the point $B$ lies on the hyperplane
$B=\bm x^{(i)}-\gamma^{(i)}\frac{\bm\theta}{|\bm \theta|_2}$
- this means because the point B lies on the hyperplane, its corresponding feature vector’s hypothesis = 0 so
$\gamma^{(i)}=\frac{\bm\theta^T\bm x^{(i)}}{|\bm\theta|_2}$
$\gamma^{(i)}=y^{(i)}\frac{\bm\theta^T\bm x^{(i)}}{|\bm\theta_{1:d}|_2}$
Maximizing Margin Classification
issueis. that max margin in NON-CONVEX → hard to optiimize
Support Vector Machines
- the maachines made from datapoints that lie on the boundary (support vectors) of the max-margin
Hard Margin SVMs
- we canuse the pereptron loss to constrain the minimization
Classic SVMs (max-margin classification)
Soft Margin SVMs
Slack Constraints
Defining Support Vectors
Hinge Loss (Unconstrained Optimization)
Discussion
Resources
📌
**SUMMARY
**
