Homework-7Question 1An SVM is trained with the following data:i 1 2 3 4xi(0, 0) (0, 1) (1, 0) (1, 1)yi−1 1 1 1Let α1, . . . , α4be the Lagrangian multipliers associated with this data. (αiis associated with (xi, yi).) Usinga linear kernel, what (dual) optimization problem needs to be solved in terms of the αiin order to determinetheir values?Question 2An SVM is trained with the following data:i 1 2 3 4xi(0, 0) (0, 1) (1, 0) (1, 1)yi−1 1 1 1Let α1, . . . , α4be the Lagrangian multipliers associated with this data. (αiis associated with (xi, yi).)AShow that with linear kernel the (dual) optimization problem that needs to be solved in terms of the αiis:Maximize: α1+ α2+ α3+ α4−12(α2+ α4)2+ (α3+ α4)2subject to: α1≥ 0, α2≥ 0, α3≥ 0, α4≥ 0, α1= α2+ α3+ α4BThe solution to the above optimization problem is: α1= 4, α2= 2, α3= 2, α4= 0.a. What are the indexes of the support vectors? Circle them below.Answer: 1 2 3 4b. What computation needs to be carried out to determine the classification of the point x5= (−1, 0) bythis SVM.c. What computation needs to be carried out to determine the classification of the point x5= (−1, 1) bythis SVM.d. What computation needs to be carried out to determine the classification of the point x5= (1, 1) by thisSVM.Question 3An SVM is trained with the following data:i 1 2 3 4xi(0, 0) (0, 1) (1, 0) (1, 1)yi−1 1 1 −1Let α1, . . . , α4be the Lagrangian multipliers associated with this data. (αiis associated with (xi, yi).) Usinga linear kernel, what (dual) optimization problem needs to be solved in terms of the αiin order to determinetheir values?Question 4An SVM is trained with the following data:i 1 2 3 4xi(0, 0) (0, 1) (1, 0) (1, 1)yi−1 1 1 −1Let α1, . . . , α4be the Lagrangian multipliers associated with this data. (αiis associated with (xi, yi).)AShow that with linear kernel the (dual) optimization problem that needs to be solved in terms of the αiis:Maximize: α1+ α2+ α3+ α4−12(α2− α4)2+ (α3− α4)2subject to: α1≥ 0, α2≥ 0, α3≥ 0, α4≥ 0, α1= α2+ α3− α4BObserve that α1= α2= α3= α4= k satisfies the constraints for any k ≥ 0, and that the function tobe maximized in terms of k is 4k. Based on these observations, what is the solution to the above (dual)optimization problem?Question 5An SVM is trained with the following data:i 1 2 3 4 5xi(0, 0) (1, 0) (2, 0) (3, 0) (0, 1)yi−1 1 1 1 −1Let α1, . . . , α5be the Lagrangian multipliers associated with this data. (αiis associated with (xi, yi).)AUsing the linear kernel, what (dual) optimization problem needs to be solved in terms of the αiin order todetermine their values?AnswerBThe solution to the optimization problem is:α1= 2, α2= 2, α3= 0, α4= 0, α5= 0.a. Show the computation that needs to be carried out to determine the classification of the point x = (1, 1)by this SVM.b. Show the computation that needs to be carried out to determine the classification of the point x = (0, −2)by this SVM.CTo obtain solution with soft margins using the l1norm (this is the one described in class), the term Cσiζiis added to the primal function. Using the value of C = 10, repeat parts a, b of B.a. Show the computation that needs to be carried out to determine the classification of the point x = (1, 1)by this soft margins SVM.b. Show the computation that needs to be carried out to determine the classification of the point x = (0, −2)by this soft margins
View Full Document