08 - SVM - lec. 11, 12, 13

ucla | CS M146 | 2023-05-03T13:57

---

Table of Contents

• Supplemental
  • Perceptron Review
  • Constrained Optimization
• Lecture
  • Linear Separators
    • Perceptron Review
    • Choosing a separator
    • Margin of a Linear Separator
    • Computing Margin
    • proof
    • Maximizing Margin Classification
  • Support Vector Machines
    • Hard Margin SVMs
    • Classic SVMs (max-margin classification)
    • Soft Margin SVMs
    • Slack Constraints
    • Defining Support Vectors
    • Hinge Loss (Unconstrained Optimization)
• Discussion
• Resources

Supplemental

Perceptron Review

Constrained Optimization

$\underset{x}{min}{x}^2\text{s.t.}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 $\text{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 $\text{bm}\theta$ defines the hyperplane that perfectly separates the data with no bias
• we assume the point wee are tryiing to calculate margin for $\text{bm}{x}^{(i)}$ has a positive label $y^{(i)}=1$ thus the hypothesis >0
• $\text{bm}\theta /|\text{bm}\theta {|}_2$ is the unit normal vector to the plane
• thus the point $B$ lies on the hyperplane

$B=\text{bm}{x}^{(i)}-{\gamma }^{(i)}\frac{\text{bm}\theta }{|\text{bm}\theta {|}_2}$

• this means because the point B lies on the hyperplane, its corresponding feature vector’s hypothesis = 0 so

${\gamma }^{(i)}=\frac{\text{bm}{\theta }^T\text{bm}{x}^{(i)}}{|\text{bm}\theta {|}_2}$

${\gamma }^{(i)}=y^{(i)}\frac{\text{bm}{\theta }^T\text{bm}{x}^{(i)}}{|\text{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

• used. for non (linearly) seperable data

Slack Constraints

Defining Support Vectors

• in non seperable cases

Hinge Loss (Unconstrained Optimization)

Discussion

Resources

---

📌

**SUMMARY
**