6.14 Classier based kernel. Let S be a training sample of size m. Assume that S has been generated according to some probability distribution D(x; y), where

(x; y) 2 X  f????1; +1g.

(a) Dene the Bayes classier h : X ! f????1; +1g. Show that the kernel K

dened by K(x; x0) = h(x)h(x0) for any x; x0 2 X is positive denite symmetric. What is the dimension of the natural feature space associated to K?

(b) Give the expression of the solution obtained using SVMs with this kernel.

What is the number of support vectors? What is the value of the margin?

What is the generalization error of the solution obtained? Under what condition are the data linearly separable?

(c) Let h : X ! R be an arbitrary real-valued function. Under what condition on h is the kernel K dened by K(x; x0) = h(x)h(x0), x; x0 2 X, positive denite symmetric?