Separation hyperplane with maximum geometric margin,i.e.maximum margin separation hyperplane,can be represented as constrained optimization problem: arg max y w,b st(而+) ≥Y,i=1,2,,N Changing from geometric margin to functional margin: arg max w,b w s.t.y(w…x+b)≥Y,i=1,2,..,N functional margin value doesn't affect optimization solution.If w,b are changed proportionally to Aw,Ab,then functional margin becomes A7.Changes of functional margin has no effect on(1)inequality constraints of optimization problem,nor on(2)optimization of objective function.It produces an equivalent optimization problem.We can set=1. 30/263
▶ Separation hyperplane with maximum geometric margin, i.e. maximum margin separation hyperplane, can be represented as constrained optimization problem: arg max w, b γ s.t. yi w kwk · xi + b kwk ≥ γ, i = 1, 2, . . . , N ▶ Changing from geometric margin to functional margin: arg max w, b γˆ kwk s.t. yi(w · xi + b) ≥ γ, ˆ i = 1, 2, . . . , N ▶ functional margin value doesn’t affect optimization solution. If w, b are changed proportionally to λw, λb, then functional margin becomes λγˆ. Changes of functional margin has no effect on (1) inequality constraints of optimization problem, nor on (2) optimization of objective function. It produces an equivalent optimization problem. We can set γˆ = 1. 30 / 263
We can add =minw￥+b)=1 as constraint,and get 1 arg max w;b w s.t.y(w·x+b)≥1，i=1,2,..,N min,(w·x+b)=1 i=1,,N These constraints are equivalent to the following: 1 arg max w,b lbwel s.t.(w·+b)≥1，i=1,2,.,N 31/263
▶ We can add γˆ = min i=1,..., N yi(w · xi + b) = 1 as constraint, and get arg max w, b 1 kwk s.t. yi(w · xi + b) ≥ 1, i = 1, 2, . . . , N min i=1,..., N yi(w · xi + b) = 1 ▶ These constraints are equivalent to the following: arg max w, b 1 kwk s.t. yi(w · xi + b) ≥ 1, i = 1, 2, . . . , N 31 / 263
Outline (Level 2-3) Modeling of SVM Optimization o Geometric Margin Maximization Modeling o Distance Maximization Modelling 32/263
Outline (Level 2-3) Modeling of SVM Optimization Geometric Margin Maximization Modeling Distance Maximization Modelling 32 / 263
2.4.2.Distance Maximization Modelling Maximum margin separating hyperplane can be formulated as a constrained optimization problem. 1 The objective is to maximize the margin under the constraints that all data points must lie on the correct side of the hyperplane: arg max(w,b)such that vi y(w'x;+b)0 w,b separating hyperplane maximize margin 2 Plugging in the definition ofy: 1 arg max min w'x+bl s such that i(w'x+b)≥0 w,b separating hyperplane (w,b) maximize margin 33/263
2.4.2. Distance Maximization Modelling ▶ Maximum margin separating hyperplane can be formulated as a constrained optimization problem. 1 The objective is to maximize the margin under the constraints that all data points must lie on the correct side of the hyperplane: arg max w,b γ¯(w, b) | {z } maximize margin such that ∀i yi(w T xi + b) ≥ 0 | {z } separating hyperplane 2 Plugging in the definition of γ: arg max w,b 1 kwk2 min x∈D |w T x + b| | {z } γ¯(w,b) | {z } maximize margin such that ∀i yi(w T xi + b) ≥ 0 | {z } separating hyperplane 33 / 263
3 As the hyperplane is scale invariant,we can fix the scale of w,b anyway we want.Let's be clever about it,and choose it such that: minwx+b=1 XED 4 This re-scaling can be added as an equality constraint.Then the objective becomes: 1 arg max ,6 arg min-arg minww w,b wb Using the fact f()=zis a monotonically increasing function for>0 and w2 >0;i.e.the w that maximizesw2 also maximizes ww. 34/263
3 As the hyperplane is scale invariant, we can fix the scale of w, b anyway we want. Let’s be clever about it, and choose it such that: min x∈D |w T x + b| = 1 4 This re-scaling can be added as an equality constraint. Then the objective becomes: arg max w,b 1 kwk2 · 1 = arg min w,b kwk2 = arg min w,b w Tw • Using the fact f(z) = z 2 is a monotonically increasing function for z ≥ 0 and kwk2 ≥ 0; i.e. the w that maximizes kwk2 also maximizes w Tw. 34 / 263