Instruction

Students may discuss homework exercises with one another. However, sharing, copying, or providing any part of a completed homework solution or code is an infraction of the University’s rules on Academic Integrity. Any violation will be punished as severely as possible. Final submissions must be uploaded to Gradescope using entry code XE3YJ6 (course ID 1370811). No email or hard copy will be accepted. For late submission policy and grading rubrics, please refer to the course website.

Question 1: Kernel Functions [10 pts]

Let \(x,y \in \mathbb{R}^p\).

  1. Consider the kernel

\[ k_1(x,y) = (x^T y)^2 \]

Expand \(k_1(x,y)\) and show that it can be written as

\[ k_1(x,y) = \langle \Phi_1(x), \Phi_1(y) \rangle \]

for some feature mapping \(\Phi_1\) containing second-order terms of \(x\).

  1. Now consider the kernel

\[ k_2(x,y) = (x^T y + 1)^2 \]

Using your result from part (a), find a feature mapping \(\Phi_2\) such that

\[ k_2(x,y) = \langle \Phi_2(x), \Phi_2(y) \rangle \]

Explain how this feature mapping contains second-order terms, first-order terms, and an intercept term.

Question 2: Positive-Definiteness of Kernels [40 pts]

  1. Let \(\mathcal{X}\) be a set and \(\mathcal{F}\) be a Hilbert space. \(\Phi\) is a map from \(\mathcal{X}\) to \(\mathcal{F}\). If we define a kernel function \(k(\cdot, \cdot)\) as \[ k(x, x') = \langle \Phi(x), \Phi(x') \rangle_{\mathcal{F}}, \quad \forall x, x' \in \mathcal{X}, \] show that \(k\) is a positive definite kernel (Hint: use definition).

  2. Suppose \(k_1\) and \(k_2\) are two positive definite kernels on \(\mathcal{X}\). Show that the kernel \(k = k_1 + k_2\) is also a positive definite kernel.

  3. Let \(\mathcal{X}=\mathbb{R}\) and \(\sigma>0\). Consider the kernel \[ k(x, x') = \mathbf{1}\left\{ |x-x'| < \sigma \right\}. \] Is this a positive definite kernel on \(\mathbb{R}\)? If yes, prove it. If no, give a counterexample.

Question 3: Uniqueness of Kernel Functions [10 pts]

Show that if a reproducing kernel \(k(\cdot, \cdot)\) exists for a Hilbert space \(\mathcal{H} \subseteq \mathbb{R}^{\mathcal{X}}\), then it is unique. Hint: you may consider assuming that there are two different kernel functions \(k_1\) and \(k_2\) for \(\mathcal{H}\), and then show that the Hilbert norm of their difference \(\|k_1(\cdot, x) - k_2(\cdot, x)\|_{\mathcal{H}}\) is zero for any \(x \in \mathcal{X}\). To do that, expand this equation and use properties of a Hilbert space and the reproducing property.

Question 4: Kernel Norm [10 pts]

Let \(\Omega\) be a set, and let \(\phi: \Omega \to \mathbb{R}\) be a fixed, non-zero function. Define a kernel function as \(K(x, y) =\phi(x)\phi(y)\).

  1. Describe the resulting RKHS \(\mathcal{H}_{K}\).

  2. For a function \(f\) in this space, find its norm \(\lVert f \rVert_K\).

Question 5: Image Pixel Smoothing with KRR [25 pts]

Load an image from the ElemStatLearn package. This package has been archived, so you will need to find a way to install it. The first image in the zip.train dataset is a handwritten digit 6 with resolution \(16 \times 16\). “Blow it up” to \(48 \times 48\) by replicating each pixel into a \(3 \times 3\) block. The original and enlarged images look the same, but they have different dimensions.

  # Handwritten Digit Recognition Data
  library(ElemStatLearn)
  data(zip.train)

  # plot two images
  par(mfrow=c(1,2), mar=c(0,0,1,0))

  # look at the first sample
  img16 <- zip2image(zip.train, 1)
## [1] "digit  6  taken"
  image(img16, col=gray(256:0/256), zlim=c(-1,1),
        xlab="", ylab="", axes=FALSE)

  # change the resolution of this image to 48 x 48
  img48 <- img16[rep(1:16, each=3), rep(1:16, each=3)]

  # plot the enlarged image
  image(img48, col=gray(256:0/256), zlim=c(-1,1),
        xlab="", ylab="", axes=FALSE)

Although the enlarged image is larger, it is still pixelated. Treat the two image coordinates as covariates and use two-dimensional kernel ridge regression to obtain smoothed gray-scale values. Use the original \(16 \times 16\) pixels as the \(n=256\) training observations, and predict the image on a \(48 \times 48\) grid. Scale both image coordinates to \([0,1]\).

For this question, you should:

Question 6: Kernel Mean Embedding [25 pts]

Load the mixture.example dataset from the ElemStatLearn package. Let \(X_1, \ldots, X_n\) denote observations from one of the two classes. The population kernel mean embedding is

\[ \mu_P(\cdot)=\mathbb{E}_P[k(\cdot,X)]. \]

For the bounded Gaussian kernel used below, this expectation is well-defined. The empirical kernel mean embedding is

\[ \widehat{\mu}_P(x) = \frac{1}{n}\sum_{i=1}^n k(x, X_i). \]

Use the Gaussian kernel

\[ k(x,x') = \exp\left( -\frac{\|x-x'\|^2}{2\sigma^2} \right). \]

  1. [5 pts] Show that, for any \(f \in \mathcal{H}\),

\[ \langle f, \mu_P \rangle_{\mathcal{H}} = \mathbb{E}_P[f(X)]. \]

  1. [10 pts] Using the observations in mixture.example$x and the labels in mixture.example$y, separately compute the empirical kernel mean embeddings for observations with \(y=0\) and \(y=1\). Write the kernel function and the empirical kernel mean embedding calculation yourself instead of using an existing kernel package.

Evaluate each empirical kernel mean embedding over the two-dimensional grid given by mixture.example$px1 and mixture.example$px2.

  1. [5 pts] For each bandwidth considered in part (d), visualize the two empirical kernel mean embeddings using contour(), image(), or another suitable plotting function. Use comparable plotting scales for the two classes.

  2. [5 pts] Try at least two reasonable values of \(\sigma\). Briefly describe how changing the bandwidth affects the empirical kernel mean embeddings.