```{css, echo=FALSE} .solution { background-color: #CCDDFF; } ``` ## 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](https://studentcode.illinois.edu/article1/part4). Any violation will be punished as severely as possible. Final submissions must be uploaded to [Gradescope](https://www.gradescope.com/courses/1370811) using entry code __XE3YJ6__ (course ID 1370811). No email or hard copy will be accepted. For [**late submission policy and grading rubrics**](https://teazrq.github.io/stat546/syllabus.html), please refer to the course website. - __You are only required to complete five of the six questions. You may choose any five.__ - You are required to submit the rendered file `HWx_yourNetID.pdf`. For example, `HW01_rqzhu.pdf`. Please note that this must be a `.pdf` file. `.html` format __cannot__ be accepted since they may not be readable in Gradescope. All proofs must be typed in LaTeX format. Make all of your `R` code chunks visible for grading. - Include your Name and NetID in the report. - If you use this file or the example homework `.Rmd` file as a template, be sure to __remove this instruction__ section. - __On random seed and reproducibility__: You should use `R` version $\geq 4.0.0$. This will ensure your random seed generation is the same as everyone else. Please note that updating the `R` version may require you to reinstall all of your packages. In the markdown file, __set seed__ properly so that the results can be reproduced. - For some questions, there will be restrictions on what packages/functions you can use. Please read the requirements carefully. As long as the question does not specify such restrictions, you can use anything. - __Using AI tools__: You must provide a brief statement describing any use of AI tools in your homework. You remain responsible for the reasoning, code, interpretation, and correctness of your submission. ## Question 1: Kernel Functions [10 pts] Let $x,y \in \mathbb{R}^p$. a. 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$. b. 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] a) 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). b) 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. c) 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)$. a) Describe the resulting RKHS \(\mathcal{H}_{K}\). b) 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. ```{r fig.width=10, fig.height=5, fig.align='center', out.width='70%'} # 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) 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: * Use the Matérn kernel with smoothness parameter $\nu=3/2$, \[ K_\rho(x,x')= \left(1+\frac{\sqrt{3}\lVert x-x'\rVert}{\rho}\right) \exp\left(-\frac{\sqrt{3}\lVert x-x'\rVert}{\rho}\right), \qquad \rho>0. \] * Implement KRR yourself rather than using an existing KRR package. Construct the training kernel matrix $\mathbf K$ and the kernel matrix $\mathbf K_*$ between the prediction grid and the training pixels. * Under the loss scaling used in the lecture, compute $\widehat{\boldsymbol\alpha}$ using `solve()` rather than forming a matrix inverse: \[ \widehat{\boldsymbol\alpha} = (\mathbf K+n\lambda\mathbf I)^{-1}\mathbf y, \qquad \widehat{\mathbf y}_*=\mathbf K_*\widehat{\boldsymbol\alpha}. \] * Plot the smoothed $48 \times 48$ image and the original enlarged image side by side using the same gray-scale range. * You do not need to optimize $\rho$ or $\lambda$. Try at least two reasonable choices of $(\rho,\lambda)$ and briefly describe how they affect the result. ## 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). \] a. [5 pts] Show that, for any \(f \in \mathcal{H}\), \[ \langle f, \mu_P \rangle_{\mathcal{H}} = \mathbb{E}_P[f(X)]. \] b. [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`. c. [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. d. [5 pts] Try at least two reasonable values of \(\sigma\). Briefly describe how changing the bandwidth affects the empirical kernel mean embeddings.