5. Classification

The magnitude of the weights are irrelevant b/c we only take the sign.

We can control false pos/neg by setting the boundary to something other than 0.

Max-Margin Solution

Too many perfect classifiers → chose weights with max distance between the boundary and the data points that are closest to it.

Boundary to datapoint dist: $\mathrm{dist}(w,x_i)=\left|\frac{w^T{x}_i}{\Vert w{\Vert }_2}\right|$ (projecting onto $w$, then normalizing by $w$)

Since only $w$‘s direction matters, we fix $\Vert w{\Vert }_2=1$ $⟹\mathrm{dist}(w,x_i)=|w^T{x}_i|$

If correctly classified: $y_i\cdot w^T{x}_i>0(y_i\in \{-1,1\})$ Since picking from perfect ones: $\mathrm{dist}(w,x_i)=y_i\cdot w^T{x}_i$

Max-margin classifier: $w_{\text{MM}}$ $=\underset{|w{|}_2=1}{\max }\mathrm{margin}(w)$ $=\underset{|w{|}_2=1}{\max }\underset{1\le i\le n}{\min }{y}_i\cdot w^T{x}_i$

Support Vector Machine (SVM)

Since minimax difficult to solve → minimize the norm of $w$ subject to all points being at least distance 1 from the boundary:

$$\underset{w\in {\mathbb{R}}^d}{\min }\Vert w{\Vert }_2\text{s.t.}{y}_i\cdot w^T{x}_i\ge 1\forall i$$

Support vectors: the vectors sitting exactly 1 unit away from the boundary. If you removed any other point, the solution wouldn’t change.

---

Implicit Bias of GD: GD w/ logistic loss yields max-margin solution (recently proven):

$$\underset{t\to \infty }{\lim }\frac{w^t}{\Vert w^t{\Vert }_2}=w_{\text{MM}}.$$

Soft margin