Homework 2 AMATH 563 solution

Description

Problems

Theory

1. Suppsoe Γ : 𝒳 ×𝒳 → R is a PDS kernel. Prove that ∀𝑥, 𝑥′ ∈ 𝒳 it holds that |Γ(𝑥, 𝑥′
)|
2 ≤ Γ(𝑥, 𝑥)Γ(𝑥
′
, 𝑥′
).

2. Given a kernel 𝐾 on 𝒳 define its normalized version as
𝐾¯ (𝑥, 𝑥′
) =
⎧
⎪⎨
⎪⎩
0 if 𝐾(𝑥, 𝑥) = 0 or 𝐾(𝑥
′
, 𝑥′
) = 0
𝐾(𝑥, 𝑥′
)
√︀
𝐾(𝑥, 𝑥)
√︀
𝐾(𝑥
′
, 𝑥′)
Otherwise.
Show that if 𝐾 is PDS then so is 𝐾¯ .

3. Show that the following kernels on R
𝑑 are PDS:
• Polynomial kernel: 𝐾(𝑥, 𝑥′
) = (︁
𝑥
𝑇 𝑥
′ + 𝑐
)︁𝛼
for 𝑐 > 0 and 𝛼 ∈ N.
• Exponential kernel: 𝐾(𝑥, 𝑥′
) = exp(𝑥
𝑇 𝑥
′
).
• RBF kernel: 𝐾(𝑥, 𝑥′
) = exp(−𝛾
2‖𝑥 − 𝑥
′‖
2
2
).

4. Let Ω ⊆ R
𝑑 and let {𝜓𝑗}
𝑛
𝑗=1 be a sequence of continuous functions on Ω and {𝜆𝑗}
𝑛
𝑗=1 a sequence of
non-negative numbers. Show that 𝐾(𝑥, 𝑥′
) = ∑︀𝑛
𝑗=1 𝜆𝑗𝜓𝑗 (𝑥)𝜓𝑗 (𝑥
′
) is a PDS kernel on Ω.

5. Show that: (i) if 𝐾 and 𝐾′ are two reproducing kernels for an RKHS ℋ, then they have to be the
same. (ii) the RKHS of a PDS kernel 𝐾 is unique.

Computation

Download the MNIST training and test .csv files from Canvas and load them on your computer. I suggest
you use Python or MATLAB for this excercise.

• Use Principle Component Analysis (PCA) on the training set to reduce the dimension of your input.
How many modes do you need to preserve 95% of the variance in the training set?

• Extract the digits 1 and 9 from the training set. Use kernel regression to design and train a classifier
to distinguish these digits using three different kernels of your choosing (I suggest RBF, Polynomila,
and linear). It is a good idea to use PCA to reduce your input dimensions here. Also, you may use
cross validation to tune your kernel/regularization/nugget parameters if you need them. Present the
training and test error of your method.

• Repeat the above experiment for the digits (3, 8), (1, 7), and (5, 2).

• Write a report of a maximum of four pages, outlining your results and findings.