Questions

1.  (3 marks) Suppose that the following are a set of points in two classes: class 1 :       

class 2 :       

Plot them and find the optimal separating line.  What are the support vectors, and what is the margin1? Note: this question can be done “by hand”/using “pen and paper”.

2.  (1 mark) Using the data and your answer from the previous question, calculate the  (Euclidean) distance between the optimal separating line (i.e. the discriminant) and the point (5 .23  7.14)T .

3.  (2 marks) Lodhi et al. [1] describe the string subsequence kernel and illustrate its calculation with an example (p.422-423). If this example was expanded to include the word “rat”, how many dimensions would the feature space have?

4.  (4 marks) From the lecture material, we know that there is an equivalance between the kernel function and the basis functions in support vector machines:

k(x, x′) = ϕ(x).ϕ(x′)

for two data points x and x′ . One interesting example of a kernel function is the Arc-cosine kernel:

kac(x, x′) =               (sinθ + (π − θ)cosθ)

which is known to have an equivalence

n

kapprox(x, x′) = n X max(0, wi .x)max(0, wi .x′) ≈ kac ,

with the approximation becoming exact as n → ∞.  Here, wi  is a weight vector of dimensionality equal to the dimensionality of x, with each entry in wi  drawn independently from N(0, 1).

Examine this approximation by writing a program to compute and plot the value of kac  and kapprox as a function of θ .