Description
1) Linear-kernel separable SVM
a) Implement a linear-kernel separable SVM
[Slope,Intercept] = LKS_SVM(x0,x1)
by solving the dual quadratic program, where
x0,x1 are matrices of D columns listing the points in the two classes, for yi=1 respectively
Slope is the D dimensional direction of the max-gap classifier (w in class/slides)
Intercept is the scalar offset of this classifier (b in class/slides)
[25 points]
b) Test your program in 2D in runs separating simulated sets of points sized of fixed size on the
cyan vs. black portions of the Tanzanian flag (using SimPolyHedra) measuring the quality
(margin) of the solution and finding the support vectors for each. Do this by writing a function
[Margin, SupportVs, Slope, Intercept, x0, x1] = Test_LKS_SVM(N)
With input N that is the number of points to simulate in each class, and outputs that include the
simulated inputs for the SVM, its output, the scalar margin Margin which is the distance
between the per-class half planes (m in the notation of the class/slides), and k×2 matrix of the k
support vectors in 2D, SupportVs (usually k=3).
Submit also a plot of the margin as a function of N for N=5,10,15,…,50 , along with respective
10×6 text files that detail the output of Test_LKS_SVM
Output_[N]_x0
Output_[N]_x1
Output_[N]_Intercept
Output_[N]_Slope
Output_[N]_SupportVs
Output_[N]_Margin
[25 points]
2) Non-separable linear SVM:
a) Add ability to handle non-separable data by
[Slope,Intercept] = NSL_SVM(x0,x1,C)
by solving the dual quadratic program, where all arguments are as before, except C the factor
that controls the weight of the slack (misclassified points) vs. the gap.
[25 points]
b) Test your program in 2D in runs separating simulated sets of points sized of fixed size on the
cyan vs. black portions of the Tanzanian flag (using SimPolyHedra) measuring the quality
(margin, number of misclassifications) of the solution while tuning the slack weight. Do this by
writing a function
[Nmiss, Margin, SupportVs, Slope, Intercept, x0, x1] =
Test_NSL_SVM(N,Nfalse)
With input N that is the number of simulated points labeled to be in each class. These N ponts
include N-Nfalse that are a labeled according to the color of the region that they are in, and
Nfalse that are in the opposite-color region. Outputs are as before, with the addition of
Nmiss, the number of misclassified points.
Submit also a plot of the margin and the number misclassified as a function of C for 10 values of
C of your choice (try to zoom in on the best performance), and for three configurations:
N=10,20,50 , when every dataset includes 10% false points. Submit respective 3×10×7 text files
that detail the output of Test_NSL_SVM
Output_[C]_[N]_x0
Output_[C]_[N]_x1
Output_[C]_[N]_Intercept
Output_[C]_[N]_Slope
Output_[C]_[N]_SupportVs
Output_[C]_[N]_Margin
Output_[C]_[N]_Nmiss
[25 points]
Good luck!
