SVM-Example-solutionsQuestion 1An SVM is trained with the following data:i 1 2 3xi(−1, −1) (1, 1) (0, 2)yi−1 1 1Let α1, α2, α3be the Lagrangian multipliers associated with this data. (αiis associated with (xi, yi).)AUsing the polynomial kernel of degree 2, what (dual) optimization problem needs to be solved in terms ofthe αiin order to determine their values?Reminder: the polynomial kernel of degree 2 is:K(xi, xj) = (x0ixj+ 1)2AnswerThe Gram matrix for the linear kernel: G =2 −2 −2−2 2 2−2 2 4The Gram matrix for the specified kernel: G =9 1 11 9 91 9 25Maximize: α1+ α2+ α3−129α21− 2α1α2− 2α1α3+ 9α22+ 18α2α3+ 25α23subject to: α1≥ 0, α2≥ 0, α3≥ 0, −α1+ α2+ α3= 0BThe solution to the optimization problem is:α1= 1/8, α2= 1/8, α3= 0a. What are the indexes of the support vectors? Circle them below.Answer: 1 2b. This SVM classifies the example x according to the sign of w0φ(x) + b, where the transformation φ isimplicitly defined by the kernel. Compute the value of the constant b. (This can be done withoutexplicit computation of φ or w.)Answer: Using the first support vector:b = −1 − (1 ∗ (−1) ∗ 9 + 1 ∗ 1 ∗ 1)/8 = −1 − (−9 + 8/8)/8 = 0c. What computation needs to be carried out to determine the classification of the point x = (−1, 0) by thisSVM?Answer: K(xj, x) = (4, 0).−18(4) +18(0) < 0Therefore the classification of x is −1.d. What computation needs to be carried out to determine the classification of the point x = (1, 0) by thisSVM?Answer: K(xj, x) = (0, 4).−18(0) +18(4) > 0Therefore the classification of x is
View Full Document
Unlocking...