Description

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:
ii. Recognizing flower species from phtos is suitable application for multiclass classification. iii. Deciding credit card approval for a bank is binary classification.
(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:
1-vs-all: we need n − 1 binary classifiers.
1-vs-1: we need binary classifiers.
(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:
There is no such region existing.
First I have try this with Python as follows:

The output of predict is from 0 to 99 without repeated class. This is a way to explicitly prove the statement.
2. [8 points] Multiclass SVM
Consider the objective function of multiclass SVM as

s.t. wy(i)φ(x(i)) − wyˆφ(x(i)) ≥ 1 − ξ(i) ∀i = 1…n,yˆ = 0…K − 1,yˆ 6= 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 Kd-dimensional vector (w1,w2,w3,w4,w5,w6)> and with the specific choices of x, y and φ.

(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)).

.