Description
1) Non-Linear-kernel SVM a) Choose a flag of a sovereign state and a pair of colors of this flag s.t. this pair cannot be distinguished by a linear separator. Prove that this condition holds. You are welcome to use the Tanzanian flag. If not, please include the flag as Flag.jpg . At any case, list the two colors in Colors.txt The two colors will be called -1 and +1 henceforth, in the order that you listed them. [5pt] b) Consider the flag as the rectangle {(0,0),(0,1),( 1½,1)(1½ ,0) Write a classifier g(x):R2 R such that its sign is able to classify a point x =(x(1), x(2)) in the plane as belonging to either of the colors. g(x) needs to be positive for all You are not asked to perform machine learning here, just to implement the ground truth solution as a MatLab function y = ClassifyMyFlag(x) with x a 2D input in the rectangle range [0, 1½]×[0,1] , and output in {-1,1}. It doesn’t matter what the function returns when the point is out of the flag range, or have a third color. [10 pt] c) Define a family of D≥3 linearly independent features { } whose linear combinations (1) ∑ (2) g(x)= f(x,*). Spell out in MatLab the family, the number of dimensions and the true *: phi_i_of_x=Features(x,i) D=DimOfFeatureSpace() ThetaStar=GenerateThetaStar() The latter two simple functions have no input arguments. Each just returns a constant value. As in the previous subsection, GenerateThetaStar returns, by design, the ground truth solution, not try to learn anything from data. Of course, if implemented correctly, then (1) and (2) above allow a way of computing ClassifyMyFlag(x) [10pt] d) Find a valid kernel for this feature family. [5pt]
e) Simulate 2N points, N that are uniformly drawn from each the two colors (SimPolyHedra is recommended if each of the colors is a collection of polygons). Do this by writing [ColorPlus1,ColorMinus1] = SimMyFlag(N) where ColorPlus1 is an N×2 matrix that details N points in color 1 where ColorMinus1 is an N×2 matrix that details N points in color -1 [10pt] f) Implement an SVM with the kernel from the previous section for fully separable data, where x0 are the points in color 1, x1 are the points in color -1. Theta = NLK_SVM(x0,x1) [40pt] g) Test your program in 2D in runs that each classifies a pair of simulated sets of points of a particular size. Find the support vectors for each run. Do this by writing a function [SupportVs, Theta, x0, x1] = Test_NLK_SVM(N) With arguments in Assignment 5. Repeat for N=10,20,30 , and submit respective 3×4 text files that detail the output of Test_LKS_SVM Output_[N]_x0 Output_[N]_x1 Output_[N]_Theta Output_[N]_SupportVs Include a plot of the rectangle [0, 1½]×[0,1], with the boundaries of each of the 3 learnt SVM classifiers drawn. [25 points]
