## 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):R

2 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]

Good luck!