Posted: November 23rd, 2015

Supervised Learning

Supervised Learning

GI01/M055/GI20, Supervised Learning.

Aim: To get familiarity with kernels, SVM’s and regularisation. Presentation, clarity, and synthesis of exposition will
be taken into account in the assessment of these exercises.
1. [60 pts] (kernel properties)
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 ? 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 = {(xi
, yi)}
m
i=1 ? IR2 × {-1, 1} of binary examples is strictly linearly separable by a line
going through the origin, that is, there exists w ? IR2
such that the linear function f(x) = w>x, x ? 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 : minw?IR2

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 coefficients.
(b) Show that the coefficients c1, . . . , cm in the above formula solve the optimisation problem
P2 : max
?
?
?
–
1
2
Xm
i,j=1
cicjyiyjx
>
i xj +
Xm
i=1
ci
: cj = 0, j = 1, . . . , m
?
?
?
.
(c) Argue that, if (ˆc1, . . . , cˆm) solves problem P2 and wˆ solves problem P1, then wˆ
>wˆ =
Pm
i=1 cˆi
.
3. [10 pts] (kernels)
Let x, t ? (-1, 1) and define the kernel
K(x, t) = 1
1 – xt
.
(a) Show that K is a valid kernel.
(b) Given any distinct inputs x1, . . . , xm ? (-1, 1) show that the kernel matrix K = (K(xi
, xj ) : i, j = 1, . . . , m)
is invertible.
1

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT 🙂