1 Soft-Margin SVM Dual Derivation [12 pts] Consider the primal formulation of a soft-margin SVM with...

Transcribed Image Text:

1 Soft-Margin SVM Dual Derivation [12 pts] Consider the primal formulation of a soft-margin SVM with regularization and offset, where C ≥ 0 is a regularization hyperparameter. minimize ||²+C +0 &i 0,6, subject to From this, we can obtain the dual formulation. maximize ā subject to n n Xi i=1 n i=1 y(¹) (ē. (i) + b) ≥ 1 − §i, §i ≥ 0, Vi = 1, ..., n. n n ΣΣα;a;y(i)y()(i) . (1) i=1 j=1 | αry(i) = 0, 0<ai<C, Vi=1, ..., n. (a) (7 pt) Start with the primal form of a soft-margin SVM shown above and derive the dual formulation shown above. (i) (3 pt) To start, state the Lagrangian of the primal. Hint: Remember to include separate terms corresponding to each of the constraints in the Lagrangian. (ii) (4 pt) Next, swap the order of the optimization to go from the primal formulation to the dual. Then find the optimal value of ♬ as well as the constraints imposed by the optimal values of b and . You may assume that strong duality holds for this problem and that the duality gap is zero. For the remaining problems, assume we trained a soft-margin SVM classifier with C = 1 on a dataset consisting of n = 6 points and learned the parameters listed in the table below. x(i) [-1.5, -2.1 ]T [-1.9, 0]T [-3.7, -2.5 ]T [0.5, 0.75 ]T [2,3.3]T 2 1 2 3 4 5 6 [ 1.6, -2.5 ]T y (i) Xi 1 1 -1 -1 0 0.322 0 0.497 0 0.175 (b) (2 pt) Based on the above dataset, state which points are support vectors. (c) (3 pt) Use the same dataset and your results from part a ii to find the optimal value of 6 and 7 and use them to classify the following points: [−4, 1] and [2, 5]T. 1 Soft-Margin SVM Dual Derivation [12 pts] Consider the primal formulation of a soft-margin SVM with regularization and offset, where C ≥ 0 is a regularization hyperparameter. minimize ||²+C +0 &i 0,6, subject to From this, we can obtain the dual formulation. maximize ā subject to n n Xi i=1 n i=1 y(¹) (ē. (i) + b) ≥ 1 − §i, §i ≥ 0, Vi = 1, ..., n. n n ΣΣα;a;y(i)y()(i) . (1) i=1 j=1 | αry(i) = 0, 0<ai<C, Vi=1, ..., n. (a) (7 pt) Start with the primal form of a soft-margin SVM shown above and derive the dual formulation shown above. (i) (3 pt) To start, state the Lagrangian of the primal. Hint: Remember to include separate terms corresponding to each of the constraints in the Lagrangian. (ii) (4 pt) Next, swap the order of the optimization to go from the primal formulation to the dual. Then find the optimal value of ♬ as well as the constraints imposed by the optimal values of b and . You may assume that strong duality holds for this problem and that the duality gap is zero. For the remaining problems, assume we trained a soft-margin SVM classifier with C = 1 on a dataset consisting of n = 6 points and learned the parameters listed in the table below. x(i) [-1.5, -2.1 ]T [-1.9, 0]T [-3.7, -2.5 ]T [0.5, 0.75 ]T [2,3.3]T 2 1 2 3 4 5 6 [ 1.6, -2.5 ]T y (i) Xi 1 1 -1 -1 0 0.322 0 0.497 0 0.175 (b) (2 pt) Based on the above dataset, state which points are support vectors. (c) (3 pt) Use the same dataset and your results from part a ii to find the optimal value of 6 and 7 and use them to classify the following points: [−4, 1] and [2, 5]T.

Answer rating: 100% (QA)

Lets break it down step by step a i To start you need to write down the Lagrangian of the primal ... View the full answer