Lab 5 – Support Vector Machine

1    Support  Vector Machines for Non-linear classiica-

tion

1.  Generate and test as above but with a non-linear decision boundary.

(a)  To create a training set with instances classiied according to anon-linear decision boundary, you need to map each instance you generate to a feature vector.  For example, to create a training set with instance vectors of length 2 based on a quadratic decision boundary c0 + c1 x1 + c2 x2 + c3 x1 x2 + c4 x1(2) + c5 x2(2):

i.  Randomly choose a coefficient vector cT  =[c0     c1     c2     c3     c4     c5]

ii.  Generate 100 training instances, each instance i being a vector xi  = [x i2(x i1)].

iii.  For each instance vector xi , create a corresponding feature vector:

iv. Assign each instance vector xi  a label yi  where:

(b)  Train each of the algorithms you implemented above on the training samples and compare the results.  To train the algorithms on a non-linear training set, map the instance vectors to the feature vectors before providing the training set to the algorithms.

2    Kernels

1.  Hard SVM  (to  implement this algorithm we will using the quadratic programming solver from CVXOPT).

2. Implement Kernelized Soft-SVM

3.  Run experiments to compare Kernelized  Soft-SVM with a polynomial kernel,  Ker- nelized Soft-SVM with a Gaussian kernel, and Hard SVM with a polynomial feature mapping.

3    Submission

To submit the homework, upload the following to theSpring (either as individual iles or a zip ile, whichever is easiest for you):

1.  all of your code

2. A report (as a pdf) showing a comparison of how well the algorithms learned on both the linear and non-linear training sets.