1. We perform Parzen Window density estimation, using trapezoidal window functions given (in unnormalized form) in the figure below: (15 pts)

φ(u)

1

u

-h       -h/2       0           h/2   h

Choose h = 1. Assume that we have the following data

Dω 1   = {0, 2, 5}

Dω2   = {4, 7}

(a)  Sketch or plot the Parzen window estimates of the pdfs p(x|ω1 ) and p(x|ω2 ).

Please label pertinent values on both axes.

(b) Estimate the prior probabilities based on frequency of occurrence of the prototypes

in each class.

(c) Use the estimates you have developed in above to find the decision boundaries and regions for a Bayes minimum-error classifier based on Parzen windows. Only the part of feature space where at least one density is nonzero need to be classified.

2. We perform k-nearest neighbor density estimation, using k = 2 . Assume that you are given the following training set for a 2-class problem with one feature: (20 pts)

Dω 1   = {2, 5}

Dω2   = {4, 7}

(a)  Sketch or plot the k-nearest neighbors estimates of the pdfs p(x|ω1 ). Please label

pertinent values on both axes.  Also give the density estimates algebraically, for each region in feature space.

(b) Estimate the prior probabilities based on frequency of occurrence of the prototypes

in each class.

(c) Use the estimates you have developed in above to find the decision boundaries and regions for a Bayes minimum-error classifier based on k-nearest neighbors.

(d) Derive a classifier based on using KNN as a discriminative technique that esti- mates p(ωi |x) directly using nearest neighbors, and compare it to the classifier you obtained in 2c. If there are ties, break them in favor of ω2 .

3.  Consider the following training data set:

x1  = [1, 0]T , z1  = −1

x2  = [0, 1]T , z2  = −1

x3  = [0, −1], z3  = −1

x4  = [−1, 0]T , z4  = 1

x5  = [0, 2]T , z5  = 1

x6  = [0, −2]T , z6  = 1

x7  = [−2, 0]T , z7  = 1

Use following nonlinear transformation of the input vector x = [x1 , x2]T  to the trans- formed vector u = [ϕ1 (x), ϕ2 (x)]T : ϕ 1 (x) = x2(2) − 2x1 + 3 and ϕ2 (x) = x1(2) − 2x2 − 3.

What is the equation of the optimal separating “hyperplane” in the u space? (15 pts)

4.  Consider the following training data set : (25 pts)

x1  = [0, 0]T , z1  = −1

x2  = [1, 0]T , z2  = 1

x3  = [0, −1], z3  = 1

x4  = [−1, 0]T , z4  = 1

Note that in the following, you need to use equations that describe w and give rise to the dual optimization problem.

(a) Write down the dual optimization problem for training a Support Vector Machine

with this data set using the polynomial kernel function

κ(xi , xj ) = (xi(T)xj  + 1)2

(b)  Solve the optimization problem and find the optimal  λi ’s using results about

quadratic forms and check the results with Wolfram Alpha or any software pack- age.

(c)  Show that the equation of the decision boundary in a kernel SVM wT u + w0  = 0 can be represented as g(x) =      λi zi κ(xi , x) + w0 .

(d) We learned that for vectors that do not violate the margin1  (i.e. zj (wT uj + w0 ) − 1  > 0), the Lagrange multiplier is zero, i.e.   λj   = 0.   On the other hand, for

vectors on the margin (zj (wT uj + w0 ) − 1 = 0), λj   0. Show that, consequently,

one can find a vector xj   for which λj      0 and calculate w0   as w0   =  1/zj  −  λi zi κ(xi , xj ).

(e)  Sketch the decision boundary for this data set based on parts (4c) and (4d).

5. In the following figure, there are different SVMs with different decision boundaries. The training data is labeled as zi  ∈ {−1, 1}, represented as circles and squares respectively. Support vectors are drawn in solid circles. Determine which of the scenarios described below matches one of the 6 plots  (note that one of the plots does not match any scenario). Each scenario should be matched to a unique plot. Explain your reason for matching each figure to each scenario. (10 pts)

(a) A soft-margin linear SVM with C = 0.02

(b) A soft-margin linear SVM with C = 20

(c) A hard-margin kernel SVM with κ(xi , xj ) = xi(T)xj  + (xi(T)xj )2

(d) A hard-margin kernel SVM with κ(xi , xj ) = exp(−5|xi − xj |2 ) (e) A hard-margin kernel SVM with κ(xi , xj ) = exp( −  |xi − xj |2 )

6. Programming Part:  Multi-class and Multi-Label Classification Using Sup- port Vector Machines

(a) Download the Anuran Calls (MFCCs) Data Set from:  https://archive .ics .

uci.edu/ml/datasets/Anuran+Calls+%28MFCCs). Choose 70% of the data ran- domly as the training set.

(b) Each instance has three labels: Families, Genus, and Species. Each of the labels

has multiple classes.   We wish to solve a multi-class and multi-label problem. One of the most important approaches to multi-class classification is to train a classifier for each label. We first try this approach: