1. [6 points] Multiclass Classification Basics
(a) Which of the following is the most suitable application for multiclass classification?
Which is the most suitable application for binary classification?
i. Predicting tomorrow’s stock price;
ii. Recognizing flower species from photos; iii. Deciding credit card approval for a bank; iv. Assigning captions to pictures.
Your answer:
(b) Suppose in an n-dimensional Euclidean space where n ≥ 3, we have n samples x(i) = ei for i = 1...n (which means x(1) = (1, 0, ..., 0)n , x(2) = (0, 1, ..., 0)n , ..., x(n) = (0, 0, ..., 1)n ), with x(i) having class i. What are the numbers of binary SVM classifiers we need to train, to get 1-vs-all and 1-vs-1 multiclass classifiers?
Your answer:
(c) Suppose we have trained a 1-vs-1 multiclass classifier from binary SVM classifiers on the samples of the previous question. What are the regions in the Euclidean space that will receive the same number of majority votes from more than one classes? You can ignore samples on the decision boundary of any binary SVM.
Your answer:
2. [8 points] Multiclass SVM
Consider the objective function of multiclass SVM as
min
n
C kwk2 + X ξ(i)
w,ξ(i) ≥0 2
i=1
s.t. wy(i) φ(x(i) ) − wyˆφ(x(i)) ≥ 1 − ξ(i) ∀i = 1...n, yˆ = 0...K − 1, yˆ = yi
Let n = K = 3, d = 2, x(1) = (0, −1), x(2) = (1, 0), x(3) = (0, 1), y(1) = 0, y(2) = 1, y(3) =
2, and φ(x) = x.
(a) Rewrite the objective function with w being a K d-dimensional vector (w1 , w2, w3, w4, w5 , w6 )
and with the specific choices of x, y and φ.
Your answer:
(b) Rewrite the objective function you get in (a) such that there are no slack variables ξ(i) .
Your answer:
(c) Let wt = (1, 1, 1, 2, 1, −1) . Compute the derivative of the objective function you get in (b) w.r.t. w2, at wt , where w2 is the weight of second dimension on Class 0 (in case you used non-conventional definition of w in (a)).
Your answer:
(d) Prove that
Max{1 + W T/y 0(x)} = lim in E exp ( 1+ w T/y 0(x)}
2
Your answer:
