DSCI 552: Programming Assignment 6 [Support Vector Machines] solution

Description

Part 1: Implementation [7 points]

You are given two data files – linsep.txt and nonlinsep.txt – each of which contains 100 2D points with
classification labels +1 or -1. The first two columns in each file indicate the 2D coordinates of a point;
and the third column indicates its classification label. The points in linsep.txt are linearly separable. The
points in nonlinsep.txt are not linearly separable in the original space but are linearly separable in a zspace that uses a simple nonlinear transformation.

Part (a) [3.5 points]: Find the fattest margin line that separates the points in linsep.txt. Please solve the
problem using a Quadratic Programming solver. Report the equation of the line as well as the support
vectors.

Part (b) [3.5 points]: Using a kernel function of your choice along with the same Quadratic Programming
solver, find the equation of a curve that separates the points in nonlinsep.txt. Report the kernel function
you use as well as the support vectors.

You can write your programs in any programming language. However, you will have to implement the
algorithms yourself instead of using library functions (except for the Quadratic Programming solver). In
your report, please provide a description of the data structures you use, any code-level optimizations you
perform, any challenges you face, and of course, the requested outputs.

Part 2: Software Familiarization [Optional – No Credit]

Do your own research and find out about library functions relevant to Support Vector Machines. Learn
how to use them. Compare them against your implementations and suggest some ideas for how you can
improve your code. Describe all this in your report.

Part 3: Applications [Optional – No Credit]

Do your own research and describe some interesting applications of Support Vector Machines.

Submission Guidelines

In your report, please include the names of all group members and mention their individual contributions.

The maximum number of the members in a team is 2. The report should be in PDF format. Your
submission should include the code as well as the report and is due before 04/16, 11:59pm in an archive
in zip, tar.gz or tar.xz format. Only one submission is required for each group by one of the group
members. Please submit your homework on D2L (do NOT email the homework to the instructor or the
TA).