HW 3 (due Monday, April 26th at 11:59pm)
1 (SVM) Let f(x) = β0 + xTβ. Show that the solution to
min
β0,β
{
N∑
i=1
max[0, 1− Yif(Xi)] + λ2 ‖β‖
2
}
,
with λ = 1/C, is the same as that of
min
β0,β
{
1
2‖β‖
2 + C
N∑
i=1
ξi
}
subject to ξi ≥ 0, yif(xi) ≥ 1− ξi, ∀i.
2. (SVM) Consider a second degree polynomial kernel K(x, x′) = (1 + 〈x, x′〉)2 where x, x′ ∈ R2. Find a
positive integer M and a function h : R2 → RM such that K(x, x′) = 〈h(x), h(x′)〉.
3. (K-means) Show that
K∑
k=1
∑
i∈Ck
d(Xi, X¯k) ≥
K∑
j=1
∑
i∈C′
j
d(Xi, X¯ ′j),
where d is the squared Euclidean distance, X¯k ∈ Rp is the centroid of the cluster determined by Ck,
C ′j = {i : d(Xi, X¯j) = mink=1,...,K d(Xi, X¯k)} and X¯ ′j is the centroid of the cluster determined by C ′j . Note
that this inequality guarantees the convergence of the K-means algorithm. (Hint: writing Ck = ∪Kj=1(Ck ∩C ′j)
could be a good starting point).
4. (Dissimilarity measure) Show by an example that the correlation-based distance
d(X,X ′) = 1− ρ(X,X ′) = 1−
∑p
j=1(Xj − X¯)(X ′j − X¯ ′)√∑p
j=1(Xj − X¯)2
∑p
j=1(X ′j − X¯ ′)2
,
where X,X ′ ∈ Rp, is not strictly speaking a metric. (Hint: show that it violates the triangle inequality).
5. (Spectral clustering) Show that for any v = (v1, . . . , vN )
vTLv = 12
N∑
i=1
N∑
j=1
wij(vi − vj)2,
where W = {wij} is an N ×N adjacency matrix and L is an N ×N unnormalized graph Laplacian matrix.
1



























































学霸联盟