Task 1.

[5+10+10 points]

Let x1 , . . . ,xm   ∈ Rd  denote the training data points with labels y1 , . . . ,ym   ∈ {±1}. We aim to find a separating hyperplane {x ∈ Rd  : wT x = β} that has maximum margin (see Lecture Notes, Section 5.2.2).

(a) In the lectures we have formulated this task as the following convex quadratic optimization

problem.

w(m)  ||w||2           subject to      yi (wT xi − β) ≥ 1,    for all 1 ≤ i ≤ m.              (1)

Implement a matlab function supportvectormachineHARD(x,y) that takes the data points (arranged as a d × m matrix x holding in the ith column the vector xi ) and the labels (arranged in a row vector y that holds yi  in its ith entry) as input, solves (1) via quadprog, and returns w, β, and the corresponding maximum margin.  If there is no solution, then w = [] should be returned.

(b) If there exists no separating hyperplane then the data is said to be not linearly separable. A

common approach in this case is to relax the constraints to allow for ”errors”in the classifi- cation. With an additional input parameter C ≥ 0 that penalizes the misclassifications, the optimization problem amounts to

1

min

w,β,ξ 1 , . . . ,ξm   2

subject to

m

||w||2 + C      ξi

i=1

yi (wT xi − β) ≥ 1 − ξi ,   for all 1 ≤ i ≤ m,

(2)

ξi  ≥ 0,                            for all 1 ≤ i ≤ m.

Implement a matlab function supportvectormachineSOFT(x,y,C) that takes x and y as in (a) and the parameter C as input, solves (2) via quadprog, and returns w, β, and the corresponding maximum margin. If there is no solution, then w = [] should be returned.

(c) Instead of (2) one can solve the so-called dual problem

m                      m     m

(3)

αi  ≥ 0,               for all 1 ≤ i ≤ m,

which involves new variables α 1 , . . . ,αm . If α1(∗) , . . . ,αm(∗)  denotes the solution to (3), then w and β are obtained via w =     αi(∗)yi xi and β = wT xj −yj  (where j ∈ {1, . . . ,m} is an index

for which 0 < α < C), respectively.  This method returns the same separating hyperplane as the method from (b).

Implement a matlab function  supportvectormachineSOFTDual(x,y,C)  that takes x,  y, and C as in (b) as input, solves (3) via quadprog, and returns w, β, the corresponding maximum margin, and the α1(∗) , . . . ,αm(∗) . If there is no solution, then w =  [] should be re- turned.

Task 2.                                                                                                                   [4+3+3 points]

This task is about applying the support vector machines from Task 1 to data points in R2 .

(a) To produce plots that show the 2D data points and the separating hyperplane wT x = β it is

helpful to have a matlab function determinepoints(xlimits,ylimits,w,beta) available, which returns the two (or, respectively, zero) points of intersection between the line wT x = β and the box  [xlimits(1),xlimits(2)] × [ylimits(1),ylimits(2)] that represents the data range of your plot. Give a matlab implementation of such a function.

(b) Consider the m = 10 data points

x1  = (1, 5),   x2  = (2, 2),   x3  = (3, 5),   x4  = (3, 3),   x5  = (4, 4), x6  = (5, 8),   x7  = (5, 7),   x8  = (6, 8),   x9  = (7, 9),   x10  = (9, 6)

with labels y1   = y2   = y3   = y4   = y5   = +1, and y6   = y7   = y8   = y9   = y10   =  −1. Use supportvectormachineHARD  or supportvectormachineSOFT to determine the maximum margin separating hyperplane for this data set. State w and β explicitly and plot the hyper- plane wT x = β and the data points (use different colors for different labels).

(c) Consider the m = 10 data points x1 , . . . ,x10   and labels y1 , . . . ,y10  from   (b).  Exchange the  labels y3   and y7 ,  i.e.,  set y3    =  −1  and y7    =  +1.  On this  changed  data  set  use supportvectormachineSOFT with C  = 10. State the returned w and β and plot the hy- perplane wT x  = β  and the data points (use different colors for different labels).   Is the returned wT x = β a separating hyperplane for the given input data (and if not, how many points are misclassified)?

Task 3.                                                                                                                   [5+5+5 points]

This task is about image classification via support vector machines. More precisely, the aim is to use support vector machines from Task 1 to classify whether a given image shows a cat or a dog.

(a) Download train .zip and evaluate .zip and extract the image files. Classify each of the 20

images in train .zip manually (+1 for cat, -1 for dog) and write a matlab program that reads all the 22 images (from both ZIP files), resizes any of them to an N × N image (use the imresize command and an N of your choice), and subsequently converts them to grayscale (via rgb2gray). Plot the resulting 22 images (they should all fit onto a single A4 page).