#7: SVM, Optimization content
Dual Form Solution, Kernel Trick, Hinge Loss
Logistic Regression Review
Multi-Class Classification
💡
Use
k Logistic Regression models to classify
k classes
Likelihood for a Single Sample (Softmax Function)
P(yi=k∣xi)=∑j=1Keajeakak=wkT⋅xi,w∈RP×KThe
softmax function is a function that
turns a vector of K real values into
a vector of K real values that sum to 1.
Likelihood of the Data
P(Y∣X)=i=1∏NP(yi∣xi)=i=1∏Nj=1∏KP(yi=j∣xi)yjiLoss Function (Cross-Entropy Loss)
Lw=−log[i=1∏NP(yi∣xi)]=−i=1∑Nj=1∑Kyji⋅log∑j=1Keajeak- yji value of output to the j-th xi
The Perceptron Model
h(x)=sign(i=1∑dwixi+b)x=BIAS income education =(1⋮),w=−242💡
Bias pushes the hyperplane toward the decision boundary
wT⋅x=∣w∣⋅∣x∣cosθ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
Notations
Output (labels):
y∈{−1,+1} hθ(x)=g(wTx+b)s.t.θ=[w,b]g(z)={1−1z≥0z<0Functional Margin γ^
💡
Large margin → correct prediction & high confidence
Functional margin of a single training sample
(xi,yi) w.r.t.
(w,b) γ^i=yi(wTxi+b)- If yi=1 then for γ^i to be large we need wTxi+b≫0
- If y=−1 the for γ^i to be large we need wTxi+b≪0
Note that when the above is true, the prediction is also correct:
yi(wTxi+b)>0Scaling
💡
Normalize the parameters to ensure
∣∣w∣∣=1 without affecting the solution
hθ(x)=g(wTx+b)=g(2wTx+2b)- hθ() is invariant under scaling
- γ^i is not invariant under scaling
Geometric Margin γ
Distance of
(xi,yi) from the hyperplane
Property 1
Unit vector
w∗=∣∣w∣∣w⊥ hyper-plane
- For x1,x2 lying on the hyper-plane
- wt(x1−x2)=0
Property 2
For any points on the hyper-plane we have
wtx0=−bProperty 3
Signed distance between any point to the hyper-plane is given by
Geometric Margin of a Particular Class
γi=∣∣w∣∣1(wTxi+b)Geometric Margin of Both Classes
γi=∥w∥yi(wTxi+b)=yi(∥w∥wTxi+∥w∥b)- A scaled version of Functional Margin
γi=∣∣w∣∣γi^- invariant to scaling of parameters
Geometric Margin for the Data Set
D=(x1,y1),…,(xn,yn) 💡
Distance to the closest point of either of the classes
γ∗=i=1,...,nminγiMaximum Margin Classifiers
💡
Maximize the distance to the
closest point of either of the classes
- Discards other points, only care about the closest
‼️
Assumption:
D is linearly separable
ρ=w,b:yi(wTxi+b)≥0maxγ∗=w,b:yi(wTxi+b)≥0max[i=1,…,nmin∣∣w∣∣wTxi+b]Constrained Optimization Problem
γ,w,bmaxγs.t.yi(wTxi+b)≥γ,∀i∈[1,n]and∣∣w∣∣=1Constraints
- Geometric margin ≥ γ: Make sure all points are further than γ → then maximize γ
- ∣∣w∣∣=1 imposed to ensure Functional Margin = Geometric Margin
Simplify: Use Functional Margin Instead
- Remove constraint ∣∣w∣∣=1
- Modify Objective to γ=∣∣w∣∣γ^
- γ^=1 (scaling constraint on w,b)
1️⃣ Primer SVM Problem Statement p∗
Goes directly for the
wSimplified from the definition above
minw,b s.t. 21∣∣w∣∣2yi(wTxi+b)≥1,∀i=1,…,n- Convex quadratic optimization with linear constraints
Optimization Overview
Unconstrained Optimization
min/maxf(w)w∈RdConstrained Optimization
Equality constraint
gi(w) ↔️ 2x inequality constraint
hi(w)Inequality Constraint
wmin/wmaxf(w)w∈Rds.t.gi(w)≤0Equality Constraint
wmin/wmaxf(w)w∈Rds.t.hi(w)=0Lagrangian Multiplier
🎯
Reduces a problem with
d variables with
e constraints
to an
unconstrained problem of
d+e variables
- Introduce a Lagrangian Multiplier to each constraint
- Compute the linear combination of multipliers & constraints
- Optimize the Lagrangian Multipliers wrt w ↔️ evaluating f(w) at w
If
w satisfies all the constraints
Op(w)=α={α1,…,αk},β={β1,…,βe}:αi≥0max[f(w)+i=1∑kαigi(w)+i=1∑eβihi(w)]=f(w)Solution to
Op(w) is the same as
f(w) p∗=wminOp(w)=wminα,β:αi≥0maxL(w,α,β)=wminf(x)Dual Problem Statement d∗
💡
A reduction of the primer problem
- d∗≤p∗ always true
- d∗=p∗ sometimes true under certain conditions
α,β:αi≥0maxOD(α,β)=α,β:αi≥0max[wminL(w,α,β)]d∗=α,β:αi≥0max[wminL(w,α,β)]Conditions for d∗=p∗
- f,gi are convex
- hi is affine/linear: hi(w)=aiTw+bi
- gi strictly possible: ∃ws.t.gi(w)≤0
Solutions
∃w∗,α∗,β∗ satisfying the KKT conditions
- w∗ solves the primal problem
- α∗,β∗ solves the dual problem
KKT (Karush-Kuhn-Tucker) Conditions
∂wi∂L(w∗,α∗,β∗)=0∂βi∂L(w∗,α∗,β∗)=0αi∗gi(w∗)=0gi(w∗)≤0αi∗≥0i=1,…,di=1,…,ei=1,…,ki=1,…,ki=1,…,kComplementarity Condition
ai>0 ➡️
gi(w∗)=0 ➡️ constraint
gi(w∗)≤0 is
active2️⃣ Dual SVM Problem Statement d∗
The Lagrangian is Given By
L(α,w,b)=21∥w∥2−i=1∑Nαi(yi(wTxi+b)−1)KKT Conditions
∇wL(α,w,b)=w−i=1∑Nαiyixi∇bL(α,w,b)=−i=1∑Nαiyiαi[yi(wTxi+b)−1]=0=0=0⟹w=i=1∑NαiyixiComplementarity ConditionDual formulation
αmaxL(α,w,b)=αmaxi=1∑Nαi−i,j=1∑Nαiαjyiyj(xi⋅xj) s.t. αi≥0,i=1∑Nαiyi=0Solution
w,bmin s.t. 21∥w∥2⟶w∗=∑i=1Nαiyixiyi(wTxi+b)≥1,∀i=1,…,nb∗=−2maxi,yi=−1(w)Txi+mini,yi=1(w)TxiUnderstanding the Constraints
αi[yi(wTxi+b)−1]=0
➡️ Either
ai=0 or
yi(wTxi+b)−1=0 ➡️
∀ai=0,yi(wTxi+b)=Geometric Margin=1💡
The hyperplane is defined by only the few closest data points
Predictions with SVMs
Naïve Approach
Compute
(w∗)T⋅x0+b∗; assign class +1 if positive, class -1 if negative
Better Approach
(w∗)Tx0+b∗=(i=1∑Nαi∗yixi)T⋅x+b∗=i=1∑Nαi∗yi(xiT⋅x0)+b∗Summary
Solution
αmax s.t. i=1∑Nαi−21i,j=1∑Ny(i)y(j)αiαj⟨x(i),x(j)⟩αi≥0,i=1,…,Ni=1∑Nαiy(i)=0Prediction
i=1∑Nαi∗y(i)⟨(x(i))T,x⟩+bWhen Linear Separability Does Not Exist
All constraints are violated
⇒ Geometric margin loses its meaning
Solution 1: Find w,b s.t. min # of constraints are violated
⇒ 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
Hinge Loss
This is the tightest convex upper bound of the intractable 0/1 loss
Intuition
y^y≥1 ⇒
y^,y same sign ⇒ correct classification ⇒
Lhinge=0 y^y<1 ⇒
y^,y different sign ⇒ incorrect classification ⇒
Lhinge=1−y^y Formulation
w,b,ξimin s.t. 21∥w∥2+Ci=1∑Nξiyi(wTxi+b)≥1−ξi,i=1,…,Nξi≥0,i=1,…,NIf
C=∞ then you have to separate the data ⇒ linearly separable solution only
If
C=0 then completely ignore the data
w,bmin21∥w∥2+Ci=1∑NLhinge(yi,wTxi+b)Optimization over Hinge Loss with an regularization term
C
Loss Functions
Understanding loss functions : Hinge loss | by Kunal Chowdhury | Analytics Vidhya | Medium