Mathematics

Are the following functions K : IRd IRd ! IR valid kernels? Explain your observation. When K is a valid kernel
provide a feature map representation for it.
(a) K(x; t) = f(x)f(t), where f : IRd ! IR.
(b) K(x; t) = x>Dt, where D is a diagonal matrix with non-negative elements.
(c) K(x; t) = x>t ?? (x>t)2.
(d) K(x; t) =
Qd
i=1 xiti (Note: we used the notation xi for the i{th component of the vector x 2 IRd).
(e) K(x; t) = cos(angle(x; t)).
(f) K(x; t) = min(x; t); x; t  0.
2. [30 pts] (SVM’s)
Assume that the set S = f(xi; yi)gm
i=1  IR2  f??1; 1g of binary examples is strictly linearly separable by a line
going through the origin, that is, there exists w 2 IR2 such that the linear function f(x) = w>x, x 2 IR2 has the
property that yif(xi) > 0 for every i = 1; : : : ;m. In this case, a linear separable SVM computes the parameters
w by solving the optimisation problem:
P1 : minw2IR2

1
2
w>w : yiw>xi  1; i = 1; : : : ;m

:
(a) Show that the vector w solving problem P1 has the form w =
Pm
i=1 ciyixi where c1; : : : ; cm are some
nonnegative coecients.
(b) Show that the coecients c1; : : : ; cm in the above formula solve the optimisation problem
P2 : max
8<
:??
1
2
Xm
i;j=1
cicjyiyjx>
i xj +
Xm
i=1
ci : cj  0; j = 1; : : : ;m
9=
;:
(c) Argue that, if (^c1; : : : ; ^cm) solves problem P2 and ^w solves problem P1, then ^w> ^w =
Pm
i=1 ^ci.
3. [10 pts] (kernels)
Let x; t 2 (??1; 1) and dene the kernel
K(x; t) =
1
1 ?? xt
:
(a) Show that K is a valid kernel.
(b) Given any distinct inputs x1; : : : ; xm 2 (??1; 1) show that the kernel matrix K = (K(xi; xj) : i; j = 1; : : : ;m)
is invertible.
1