Page cover image

#7: SVM, Optimization

  • 5 min

#7: SVM, Optimization content

Created
Topics
Dual Form Solution, Kernel Trick, Hinge Loss

Logistic Regression Review

notion image

Multi-Class Classification

💡
Use kk Logistic Regression models to classify kk classes

Likelihood for a Single Sample (Softmax Function)

P(yi=k∣xi)=eak∑j=1Keajak=wkT⋅xi,w∈RP×KP\left(y^{i}=k \mid x^{i}\right)=\frac{e^{a_{k}}}{\sum_{j=1}^{K} e^{a_{j}}} \quad a_{k}=\mathbf{w}_{k}^{T} \cdot x^{i} , \mathbf{w} \in \mathfrak{R}^{P \times K}
The softmax function is a function that turns a vector of KK real values into a vector of KK real values that sum to 1.

Likelihood of the Data

P(Y∣X)=∏i=1NP(yi∣xi)=∏i=1N∏j=1KP(yi=j∣xi)yji\begin{gathered}P(Y \mid X)=\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}\right)=\prod_{i=1}^{N} \prod_{j=1}^{K} P\left(y^{i}=j \mid x^{i}\right)^{y_{j}^{i}} \end{gathered}

Loss Function (Cross-Entropy Loss)

Lw=−log⁡[∏i=1NP(yi∣xi)]=−∑i=1N∑j=1Kyji⋅log⁡eak∑j=1Keaj\mathscr{L}_{w}=-\log \left[\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}\right)\right]=-\sum_{i=1}^{N} \sum_{j=1}^{K} y_{j}^{i} \cdot \log \frac{e^{a_{k}}}{\sum_{j=1}^{K} e^{a_{j}}}
  • yjiy_j^i value of output to the j-th xix_i

The Perceptron Model

h(x)=sign⁡(∑i=1dwixi+b)x=(BIAS income  education )=(1⋮),w=(−242)h(x)=\operatorname{sign}\left(\sum_{i=1}^d w_ix_i+b\right)\\x=\left(\begin{array}{c} B I A S \\ \text { income } \\ \text { education } \end{array}\right)=\left(\begin{array}{c} 1 \\ \vdots \end{array}\right), \quad w=\left(\begin{array}{c} -2 \\ 4 \\ 2 \end{array}\right)
💡
Bias pushes the hyperplane toward the decision boundary
wT⋅x=∣w∣⋅∣x∣cos⁡θw^T \cdot x=|w|\cdot|x|\cos\theta
notion image

Support Vector Machine

💡
Seeks large margin separator to improve generalization
  • Largest margin: farthest from the 2 classes
🎯
Uses optimization to find efficient and optimal solutions
🛠
Uses kernel trick to make computations efficient specially in cases where the feature vectors is huge
  • Projects data to a high-dimensional space
notion image

Notations

Input: xx
Output (labels): y∈{−1,+1}y\in \{-1,+1\}
Parameters: ww
Bias (Intercept): bb
hθ(x)=g(wTx+b)s.t.θ=[w,b]g(z)={1z≥0−1z<0h_\theta(x)=g(w^Tx+b) \quad \text{s.t.}\quad \theta=[w,b]\\g(z)=\left\{\begin{array}{rl} 1 & z \geq 0 \\ -1 & z<0 \end{array}\right.

Functional Margin γ^\hat{\gamma}

💡
Large margin → correct prediction & high confidence
Functional margin of a single training sample (xi,yi)(x^i, y^i) w.r.t. (w,b)(w, b)
γ^i=yi(wTxi+b)\hat{\gamma}^{i}=y^{i}\left(w^{T} x^{i}+b\right)
  • If yi=1y^{i}=1 then for γ^i\hat{\gamma}^{i} to be large we need wTxi+b≫0w^{T} x^{i}+b \gg 0
  • If y=−1y^{=}-1 the for γ^i\hat{\gamma}^{i} to be large we need wTxi+b≪0w^{T} x^{i}+b \ll 0
Note that when the above is true, the prediction is also correct: yi(wTxi+b)>0y^{i}\left(w^{T} x^{i}+b\right)>0

Scaling

💡
Normalize the parameters to ensure ∣∣w∣∣=1| |w| | = 1 without affecting the solution
hθ(x)=g(wTx+b)=g(2wTx+2b) h_{\theta}(x)=g\left(w^{T} x+b\right)=g\left(2 w^{T} x+2 b\right)
  • hθ()h_{\theta}() is invariant under scaling
  • γ^i\hat{\gamma}^{i} is not invariant under scaling

Geometric Margin γ\gamma

Distance of (xi,yi)(x^i, y^i) from the hyperplane

Property 1

Unit vector w∗=w∣∣w∣∣⊥w^*=\frac{w}{||w||} \perp hyper-plane
  • For x1,x2x_1,x_2 lying on the hyper-plane
  • wt(x1−x2)=0w^t(x_1-x_2)=0

Property 2

For any points on the hyper-plane we have wtx0=−bw^tx_0 = − b

Property 3

Signed distance between any point to the hyper-plane is given by
notion image

Geometric Margin of a Particular Class

γi=1∣∣w∣∣(wTxi+b)\gamma^{i}=\frac{1}{|| w||}\left(w^{T} x^{i}+b\right)

Geometric Margin of Both Classes

γi=yi(wTxi+b)∥w∥=yi(wTxi∥w∥+b∥w∥)\gamma^{i}=\frac{y^{i}\left(w^{T} x^{i}+b\right)}{\|w\| }=y^{i}\left(\frac{w^{T} x^{i}}{\|w\|}+\frac{b}{\|w\|}\right)
  • A scaled version of Functional Margin
γi=γi^∣∣w∣∣\gamma^i=\frac{\hat{\gamma^i}}{||w||}
  • invariant to scaling of parameters

Geometric Margin for the Data Set

𝒟=(x1,y1),…,(xn,yn)𝒟 = {(x^1, y^1),…, (x^n, y^n)}
💡
Distance to the closest point of either of the classes
γ∗=min⁡i=1,...,nγi\gamma^*=\min_{i=1,...,n} \gamma^i

Maximum Margin Classifiers

💡
Maximize the distance to the closest point of either of the classes
  • Discards other points, only care about the closest
‼️
Assumption: D\mathscr{D} is linearly separable
ρ=max⁡w,b:yi(wTxi+b)≥0γ∗=max⁡w,b:yi(wTxi+b)≥0[min⁡i=1,…,n∣wTxi+b∣∣∣w∣∣]\begin{align*} \rho&=\max _{w, b: y^{i}\left(w^{T} x^{i}+b\right) \geq 0} \quad\gamma^* \\&=\max _{w, b: y^{i}\left(w^{T} x^{i}+b\right) \geq 0} \quad\left[\min _{i=1, \ldots, n} \frac{\left|w^{T} x^{i}+b\right|}{|| w||}\right] \end{align*}

Constrained Optimization Problem

max⁡γ,w,bγs.t.yi(wTxi+b)≥γ, ∀i∈[1,n] and ∣∣w∣∣=1\max_{\gamma,w,b} \quad \gamma \quad \text{s.t.}\quad y^i(w^Tx^i+b)\geq\gamma, \>\forall i\in[1,n] \> \text{and}\> ||w||=1
Constraints
  1. Geometric margin ≥ γ\gamma: Make sure all points are further than γ\gamma → then maximize γ\gamma
  1. ∣∣w∣∣=1| |w| | = 1 imposed to ensure Functional Margin = Geometric Margin
    • simplifies equation
    • L-2 norm
Simplify: Use Functional Margin Instead
  • Remove constraint ∣∣w∣∣=1||w||=1
  • Modify Objective to γ=γ^∣∣w∣∣\gamma=\frac{\hat{\gamma}}{||w||}
  • γ^=1\hat{\gamma}=1 (scaling constraint on w,bw,b)

1️⃣ Primer SVM Problem Statement p∗p^*

Goes directly for the ww
Simplified from the definition above
min⁡w,b12∣∣w∣∣2 s.t. yi(wTxi+b)≥1,∀i=1,…,n\begin{array}{ll}\min _{w, b} & \frac{1}{2}|| w||^{2} \\\text { s.t. } & y^{i}\left(w^{T} x^{i}+b\right) \geq 1, \quad \forall i=1, \ldots, n\end{array}
  • Convex quadratic optimization with linear constraints

Optimization Overview

Unconstrained Optimization

min⁡/max⁡ f(w)w∈Rd\min /\max \>f(w)\quad w\in\mathbb{R^d}

Constrained Optimization

Equality constraint gi(w)g_i(w) ↔️ 2x inequality constraint hi(w)h_i(w)

Inequality Constraint

min⁡w/max⁡w f(w)w∈Rds.t.gi(w)≤0\min_w /\max_w \>f(w)\quad w\in\mathbb{R^d}\\\textbf{s.t.}\quad g_i(w)\leq0

Equality Constraint

min⁡w/max⁡w f(w)w∈Rds.t.hi(w)=0\min_w /\max_w \>f(w)\quad w\in\mathbb{R^d}\\\textbf{s.t.}\quad h_i(w)=0

Lagrangian Multiplier

🎯
Reduces a problem with dd variables with ee constraints to an unconstrained problem of d+ed + e variables
  1. Introduce a Lagrangian Multiplier\text{Lagrangian Multiplier} to each constraint
  1. Compute the linear combination of multipliers & constraints
  1. Optimize the Lagrangian Multipliers\text{Lagrangian Multipliers} wrt ww ↔️ evaluating f(w)f(w) at ww
 
If ww satisfies all the constraints
Op(w)=max⁡α={α1,…,αk},β={β1,…,βe}:αi≥0[f(w)+∑i=1kαigi(w)+∑i=1eβihi(w)]=f(w)\begin{aligned} O_{p}(w) &=\max_{\alpha=\left\{\alpha{1}, \ldots, \alpha_{k}\right\}, \beta=\left\{\beta_{1}, \ldots, \beta_{e}\right\}: \alpha_{i} \geq 0}\left[f(w)+\sum_{i=1}^{k} \alpha_{i} g_{i}(w)+\sum_{i=1}^{e} \beta_{i} h_{i}(w)\right] \\ &=f(w) \end{aligned}
Solution to Op(w)O_{p}(w) is the same as f(w)f(w)
p∗=min⁡wOp(w)=min⁡wmax⁡α,β:αi≥0L(w,α,β)=min⁡wf(x)p^{*}=\min_{w} O{p}(w)=\min_{w} \max_{\alpha, \beta: \alpha{i} \geq 0} L(w, \alpha, \beta)=\min _{w} f(x)

Dual Problem Statement d∗d^*

💡
A reduction of the primer problem
  • d∗≤p∗d^*\leq p^* always true
  • d∗=p∗d^*=p^* sometimes true under certain conditions
max⁡α,β:αi≥0OD(α,β)=max⁡α,β:αi≥0[min⁡wL(w,α,β)]d∗=max⁡α,β:αi≥0[min⁡wL(w,α,β)]\max_{\alpha, \beta: \alpha{i} \geq 0} O_{D}(\alpha, \beta)=\max_{\alpha, \beta: \alpha{i} \geq 0}\left[\min _{w} L(w, \alpha, \beta)\right] \\ d^{*}=\max_{\alpha, \beta: \alpha{i} \geq 0}\left[\min _{w} L(w, \alpha, \beta)\right]

Conditions for d∗=p∗d^*=p^*

  1. f,gif,g_i are convex
  1. hih_i is affine/linear: hi(w)=aiTw+bih_i(w)=a_i^Tw+b_i
  1. gig_i strictly possible: ∃ws.t.gi(w)≤0\exists w\quad \text{s.t.} \quad g_i(w)\leq 0

Solutions

∃w∗,α∗,β∗\exists w^*,\alpha^*,\beta^* satisfying the KKT conditions
  • w∗w^* solves the primal problem
  • α∗,β∗\alpha^*,\beta^* solves the dual problem
  • d∗=p∗d^*=p^*

KKT (Karush-Kuhn-Tucker) Conditions

∂∂wiL(w∗,α∗,β∗)=0i=1,…,d∂∂βiL(w∗,α∗,β∗)=0i=1,…,eαi∗gi(w∗)=0i=1,…,kgi(w∗)≤0i=1,…,kαi∗≥0i=1,…,k\begin{array}{rl}\frac{\partial}{\partial w_{i}} L\left(w^{*}, \alpha^{*}, \beta^{*}\right)=0 & i=1, \ldots, d \\\frac{\partial}{\partial \beta_{i}} L\left(w^{*}, \alpha^{*}, \beta^{*}\right)=0 & i=1, \ldots, e \\\alpha_{i}^{*} g_{i}\left(w^{*}\right)=0 & i=1, \ldots, k \\g_{i}\left(w^{*}\right) \leq 0 & i=1, \ldots, k \\\alpha_{i}^{*} \geq 0 & i=1, \ldots, k\end{array}
Complementarity Condition ai>0a_i>0 ➡️ gi(w∗)=0g_i(w^*)=0 ➡️ constraint gi(w∗)≤0g_i(w^*)\leq0 is active

2️⃣ Dual SVM Problem Statement d∗d^*

The Lagrangian is Given By

L(α,w,b)=12∥w∥2−∑i=1Nαi(yi(wTxi+b)−1)L(\alpha, w, b)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N} \alpha_{i}\left(y^{i}\left(w^{T} x^{i}+b\right)-1\right)

KKT Conditions

∇wL(α,w,b)=w−∑i=1Nαiyixi=0⟹w=∑i=1Nαiyixi∇bL(α,w,b)=−∑i=1Nαiyi=0αi[yi(wTxi+b)−1]=0Complementarity Condition\begin{align*} \nabla_{w} L(\alpha, w, b)=w-\sum_{i=1}^{N} \alpha_{i} y^{i} x^{i}&=0 &&\quad \Longrightarrow \quad w=\sum_{i=1}^{N} \alpha_{i} y^{i} x^{i} \\\nabla_{b} L(\alpha, w, b)=-\sum_{i=1}^{N} \alpha_{i} y^{i}&=0 \\\alpha_{i}\left[y^{i}\left(w^{T} x^{i}+b\right)-1\right]&=0 &&\quad\text{Complementarity Condition} \end{align*}

Dual formulation

max⁡αL(α,w,b)=max⁡α∑i=1Nαi−∑i,j=1Nαiαjyiyj(xi⋅xj) s.t. αi≥0,∑i=1Nαiyi=0\begin{gathered}\max_{\alpha} L(\alpha, w, b)=\max_{\alpha} \sum_{i=1}^{N} \alpha_{i}-\sum_{i, j=1}^{N} \alpha_{i} \alpha_{j} y^{i} y^{j}\left(x^{i} \cdot x^{j}\right)\\\text { s.t. } \alpha_{i} \geq 0, \quad \sum_{i=1}^{N} \alpha_{i} y^{i}=0\end{gathered}

Solution

min⁡w,b12∥w∥2⟶w∗=∑i=1Nαiyixi s.t. yi(wTxi+b)≥1,∀i=1,…,n\begin{aligned}\min_{w, b} &\quad \frac{1}{2}\|w\|^{2} \longrightarrow w^{*}=\sum{i=1}^{N} \alpha_{i}^{} y^{i} x^{i} \\\text { s.t. }&\quad y^{i}\left(w^{T} x^{i}+b\right) \geq 1, \quad \forall i=1, \ldots, n\end{aligned}b∗=−max⁡i,yi=−1(w)Txi+min⁡i,yi=1(w)Txi2b^*=-\frac{\max _{i, y^{i}=-1}\left(w^{}\right)^{T} x^{i}+\min _{i, y^{i}=1}\left(w^{}\right)^{T} x^{i}}{2}

Understanding the Constraints

αi[yi(wTxi+b)−1]=0\alpha_{i}\left[y^{i}\left(w^{T} x^{i}+b\right)-1\right]=0 ➡️ Either ai=0a_i=0 or yi(wTxi+b)−1=0y^{i}\left(w^{T} x^{i}+b\right)-1=0
➡️ ∀ai≠0,yi(wTxi+b)=Geometric Margin=1\forall a_i\neq0,\quad y^{i}\left(w^{T} x^{i}+b\right)=\text{Geometric Margin}=1
💡
The hyperplane is defined by only the few closest data points
notion image

Predictions with SVMs

Naïve Approach

Compute (w∗)T⋅x0+b∗(w^*)^T\cdot x^0+b^*; assign class +1 if positive, class -1 if negative

Better Approach

(w∗)Tx0+b∗=(∑i=1Nαi∗yixi)T⋅x+b∗=∑i=1Nαi∗yi(xiT⋅x0)+b∗\begin{aligned}\left(w^{*}\right)^{T} x^{0}+b^{*}=&\left(\sum_{i=1}^{N} \alpha_{i}^{*} y^{i} x^{i}\right)^{T} \cdot x+b^{*} \\&=\sum_{i=1}^{N} \alpha_{i}^{*} y^{i}\left(x^{i^{T}} \cdot x^{0}\right)+b^{*}\end{aligned}

Summary

Solution

max⁡α∑i=1Nαi−12∑i,j=1Ny(i)y(j)αiαj⟨x(i),x(j)⟩ s.t. αi≥0,i=1,…,N∑i=1Nαiy(i)=0\begin{align*} \max _{\alpha} & \sum_{i=1}^{N} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{N} y^{(i)} y^{(j)} \alpha_{i} \alpha_{j}\langle x^{(i)}, x^{(j)}\rangle \\ \text { s.t. } & \alpha_{i} \geq 0, i=1, \ldots, N \\ & \sum_{i=1}^{N} \alpha_{i} y^{(i)}=0 \end{align*}

Prediction

∑i=1Nαi∗y(i)⟨(x(i))T,x⟩+b\sum_{i=1}^{N} \alpha_{i}^{*} y^{(i)}\langle(x^{(i)})^{T}, x\rangle+b

When Linear Separability Does Not Exist

All constraints are violated
⇒ Geometric margin loses its meaning

Solution 1: Find w,bw,b s.t. min # of constraints are violated

notion image
⇒ NP-Hard Problem

Solution 2: Minimize Slack Penalty

If functional margin is ≥ 1, the no penalty
If functional margin is < 1, then pay linear penalty
notion image

Hinge Loss

This is the tightest convex upper bound of the intractable 0/1 loss
notion image

Intuition

y^y≥1\hat{y}y\geq 1 ⇒ y^,y\hat{y}, y same sign ⇒ correct classification ⇒ Lhinge=0\mathcal{L}_\text{hinge}=0
y^y<1\hat{y}y< 1 ⇒ y^,y\hat{y}, y different sign ⇒ incorrect classification ⇒ Lhinge=1−y^y\mathcal{L}_\text{hinge}=1-\hat{y}y

Formulation

min⁡w,b,ξi12∥w∥2+C∑i=1Nξi s.t. yi(wTxi+b)≥1−ξi,i=1,…,Nξi≥0,i=1,…,N\begin{align*}\min _{w, b, \xi_{i}} \quad& \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i} \\\text { s.t. } \quad& y^{i}\left(w^{T} x^{i}+b\right) \geq 1-\xi_{i}, i=1, \ldots, N \\& \xi_{i} \geq 0, \quad i=1, \ldots, N\end{align*}
If C=∞C = ∞ then you have to separate the data ⇒ linearly separable solution only
If C=0C = 0 then completely ignore the data
min⁡w,b12∥w∥2+C∑i=1NLhinge(yi,wTxi+b)\min _{w, b} \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} L_{h i n g e}\left(y^{i}, w^{T} x^{i}+b\right)
Optimization over Hinge Loss with an regularization term CC
 

Loss Functions

Understanding loss functions : Hinge loss | by Kunal Chowdhury | Analytics Vidhya | Medium
notion image
 
notion image