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]
