5 The new optimization problem becomes: arg min ww w.b st.y(wx+b)≥0，i min w'xi+bl 1 XiED 6 These constraints are still hard to deal with,however they are equivalent to a much simpler formulation. arg min ww w.b s.t.y(wx+b)≥1，i 35/263
5 The new optimization problem becomes: arg min w,b w Tw s.t. yi(w T xi + b) ≥ 0, ∀i min xi∈D |w T xi + b| = 1 6 These constraints are still hard to deal with, however they are equivalent to a much simpler formulation. arg min w,b w Tw s.t. yi(w T xi + b) ≥ 1, ∀i 35 / 263
Final Max Margin Classifier Formulation arg minww w.b s.t.(w'x+b)≥1，i This is a quadratic optimization problem. 1 The objective is quadratic and the constraints are all linear. 2 can be solved efficiently with any QCQP (Quadratically Constrained Quadratic Program)solver. 3 has a unique solution whenever a separating hyper plane exists. 4 has a nice interpretation:Find the simplest hyperplane(where simpler means smaller ww)such that all inputs lie at least 1 unit away from the hyperplane on the correct side 36/263
▶ Final Max Margin Classifier Formulation arg min w,b w Tw s.t. yi(w T xi + b) ≥ 1, ∀i ▶ This is a quadratic optimization problem. 1 The objective is quadratic and the constraints are all linear. 2 can be solved efficiently with any QCQP (Quadratically Constrained Quadratic Program) solver. 3 has a unique solution whenever a separating hyper plane exists. 4 has a nice interpretation: Find the simplest hyperplane (where simpler means smaller w Tw) such that all inputs lie at least 1 unit away from the hyperplane on the correct side. 36 / 263
Outline (Level 1-2) SVM Linear SVM in LSC o Convex optimization o Linear separability and classifier o Linear SVM in LSC Maximum Margin Types of SVM SV and margin boundary Three Types of Margin Lagrange Duality Modeling of SVM Optimization o Dual method of linear SVM in Primal optimization problem for LSC 37/263
Outline (Level 1-2) 2 Linear SVM in LSC Linear separability and classifier Types of SVM Three Types of Margin Modeling of SVM Optimization Primal optimization problem for SVM Convex optimization Linear SVM in LSC - Maximum Margin SV and margin boundary Lagrange Duality Dual method of linear SVM in LSC 37 / 263
2.5.Primal optimization problem for linear SVM in linearly separable case Optimization problems for linear SVM in linearly separable case: a呢min s.t.yw·x+b)-1≥0，i=1,2,.,N Note: arg max ,6 It is a convex quadratic programming problem,belonging to convex optimization. 38/263
2.5. Primal optimization problem for linear SVM in linearly separable case ▶ Optimization problems for linear SVM in linearly separable case: arg min w, b 1 2 kwk 2 s.t. yi(w · xi + b) − 1 ≥ 0, i = 1, 2, . . . , N Note: arg max w, b 1 kwk ⇔ arg min w, b 1 2 kwk 2 ▶ It is a convex quadratic programming problem, belonging to convex optimization. 38 / 263
Outline (Level 1-2) SVM Linear SVM in LSC Convex optimization Linear separability and classifier o Linear SVM in LSC Maximum Margin Types of SVM SV and margin boundary Three Types of Margin Lagrange Duality Modeling of SVM Optimization o Dual method of linear SVM in o Primal optimization problem for LSC 39/263
Outline (Level 1-2) 2 Linear SVM in LSC Linear separability and classifier Types of SVM Three Types of Margin Modeling of SVM Optimization Primal optimization problem for SVM Convex optimization Linear SVM in LSC - Maximum Margin SV and margin boundary Lagrange Duality Dual method of linear SVM in LSC 39 / 263