Section A

1. (a) When is a set X = {x1 , . . . , xm } ⊂ Rd called shattered by a class H of prediction

rules? What is the VC-dimension of a class H of prediction rules for the binary
classification problem?
[4]
(b) (i) Suppose n documents contain in total m (distinct) terms. Explain how Binary
and Term Frequency term-to-document matrices are defined.
(ii) Explain how the (traditional) Inverse Document Frequency (IDF) is defined.
(iii) Deduce the IDF value of a term that is contained in every document.
[5]
(c) (i) State the definition of an eigenvalue and eigenvector of a matrix.
(ii) State the Principal Component Analysis (PCA) problem, and its equivalent
formulation using eigenvalues and eigenvectors of a matrix (without proving
the equivalence).
(iii) Given a matrix X ∈ Rd×m , suppose that a vector v 6= 0 is an eigenvector of
X > X ∈ Rm×m . Prove that if y = Xv 6= 0, then y is an eigenvector of XX >
corresponding to the same eigenvalue.
Explain how this fact can be used for a faster computation of the solution of
the PCA problem if m < d.
[7]
(d) (i) State what it means for a function L(θ) : Ω → R to be β-smooth.
(ii) For θ = (θ1 , θ2 ) ∈ R2 , let:
1
LI (θ) = (θ1 − θ2 )2 , and
2
1 1
LII (θ) = (θ1 − θ2 )2 + (θ1 − θ2 )3 .
2 3
For each of these functions, find a nontrivial convex domain Ω ⊂ R2 and β ∈ R,
β > 0, such that the function is β-smooth on Ω.
Hint: write certain expressions as inner products of vectors, and use the
Cauchy-Schwarz inequality that for any vectors x, y ∈ Rd , |hx, yi| ≤ kxk2 kyk2 .
[8]

Page 2 of 5 MA20278
 Section B

2. (a) State two assumptions statistical learning theory makes about a labelled dataset
D = (X, y), X = {x1 , . . . , xm }, y = {y1 , . . . , ym }, and prediction rules h(x).
State the definitions of expected and empirical risks under those assumptions.
[4]
(b) Explain the method of splitting a given labelled dataset D = (X, y), X =
{x1 , . . . , xN }, y = {y1 , . . . , yN }, into training and test datasets, and how this helps
to estimate an important quantity in statistical learning theory.
[2]
(c) Formulate the method of K-fold cross validation for a labelled dataset D = (X, y),
X = {x1 , . . . , xN }, y = {y1 , . . . , yN }. You may assume that K divides N .
[4]
(d) Consider a dataset D = (X, y), X = {x1 , . . . , xN }, y = {y1 , . . . , yN }, where
x1 , . . . , xN are arbitrary distinct values, and each of y1 , . . . , yN is chosen at random
to be 1 or −1 with probability 1/2. Consider the following prediction rule, which
returns the same label (1 or −1) for any x depending just on the parity of labels in
the training dataset:
(
1, number of yi = 1 in the training set is odd,
h(x) = h =
−1, otherwise.

Let us use the pointwise loss `(ŷ, y) = |ŷ − y| to define expected and empirical risks.
Prove that the N -fold cross validation error does not converge to the expected risk,
namely, that the difference between the cross validation error and the expected risk
is either 1 or −1 for any N ∈ N.
[8]

Page 3 of 5 MA20278
3. Let X = {x1 , . . . , xm } ⊂ X be an unlabelled dataset of vectors xi ∈ Rn , i = 1, . . . , m,
belonging to a metric space X = Rn with a distance function d : X × X → R+ .

(a) Define the centroid of a cluster C ⊂ X, and the K-means loss of clusters C1 , . . . , CK .
[2]
(b) Prove that if the distance function is Euclidean, d(x, µ) = kx−µk2 , then the centroid
of a cluster Ci can be computed as follows:
1 X
µi = x,
|Ci |
x∈Ci

where |Ci | is the number of elements in Ci .

[4]
(c) Write a pseudocode for the K-means algorithm.
[4]
(d) Consider X = {x1 , x2 , x3 , x4 }, with
     √  √
0 0 2 t 2 t
x1 = , x2 = , x3 = , and x4 = ,
0 2 0 2

where t > 1 is any real number. Let the distance d(x, µ) = kx − µk2 be Euclidean.
Suppose we want to split X into K = 2 clusters of 2 vectors in each cluster.
(i) Find all 6 possible clusterings and their corresponding K-means losses. What
is the optimal clustering?
(ii) Show that if the K-means algorithm is started from µ1 = x1 and µ2 = x2 ,
it converges to a suboptimal clustering with the K-means loss that is t times
larger than the optimal loss.
[8]

Page 4 of 5 MA20278
4. Consider the (homogeneous) logistic regression problem with the pointwise loss

`(hθ (x), y) = log(1 + exp(−yhθ, xi)),

where x, θ ∈ Rd , y ∈ {−1, 1}, and the empirical risk to be minimised

m
1 X
LD (θ) = `(hθ (xi ), yi ),
m
i=1

built upon a dataset D = (X, y), X = {x1 , . . . , xm }, y = {y1 , . . . , ym }, xi ∈ Rd ,

yi ∈ {−1, 1}.

(a) State what it means for a function L(θ) : Ω → R to be λ-strongly convex. State
an equivalent definition for continuously differentiable functions that uses only the
gradient of the function (without proving the equivalence).
[3]
(b) (i) Write a pseudocode for the Gradient Descent (GD) method tailored to
the empirical risk minimisation solving the logistic regression problem. In
particular, you need to express the next iterate θ k+1 explicitly in terms of the
previous iterate θ k , as well as i, xi , yi , m, and the learning rate tk .
(ii) State the appropriate theorem of convergence of GD applied to the logistic
regression problem, given that the empirical risk LD (θ) is β-smooth, but not
λ-strongly convex.
[5]
(c) (i) Prove that

1 1 1 1
− ≤2 and that − ≤ |t − s|
et + 1 es + 1 et + 1 es + 1

for any t, s ∈ R.
Hint: consider cases t ≤ s and s ≤ t separately and recall that et ≥ 1 + t for
any t ∈ R.
(ii) Prove that LD (θ) is β-smooth on Rd for some β ∈ R, β > 0.
Hint: use (i).
(iii) Prove the LD (θ) is not λ-strongly convex on Rd for any λ > 0.
Hint: prove by contradiction, taking θ and η = 2θ such that kθk2 is sufficiently
large.
[10]

SD Page 5 of 5 MA20278