Stat 432 Homework 5

Instruction

Please remove this section when submitting your homework.

Students are encouraged to work together on homework and/or utilize advanced AI tools. However, there are two basic rules:

• sharing, copying, or providing any part of a homework solution or code to others is an infraction of the University’s rules on Academic Integrity. Any violation will be punished as severely as possible. This simply means: write your own solution.
• You must indicate clearly the level of involvement of AI tools (ChatGPT, Copilot, etc.) at the beginning of your homework. This includes whether you used it to generate code, debug code, or write explanations. If you did not use any AI tools, please state that explicitly. You are encouraged to briefly document your prompt(s) especially when AI is heavily involved. Please be aware that you are responsible any consequences of using AI tools, including incorrect or misleading information.

Final submissions must be uploaded to Gradescope. No email or hard copy will be accepted. Please refer to the course website for late submission policy and grading rubrics.

• 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 will not be accepted because they are often not readable on gradescope. Make all of your R code chunks visible for grading.
• Include your Name and NetID at the beginning of your homework.
• Make sure that you set seed properly so that the results can be replicated if needed. Make sure the version of your R is \(\geq 4.0.0\). This will ensure your random seed generation is the same as everyone else.
• 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.
• If you use this file or the example homework .Rmd file as a template, be sure to remove this instruction section.

Question 1: [20 pts] KNN Implementation and Simulation

The goal of Question 1 and 2 serves the purpose of comparing KNN with linear regression models in different settings. But first of all, let’s write a KNN function ourselves and compare that with some existing packages. Here is a data generate that we will consider:

\[ Y = 0.5 X_1 + \sin(X_2) - 0.3 X_3^2 + \epsilon_i, \quad i = 1, \ldots, n \]

Here for each observation, we will generate \(X_1, X_2, X_3\) from i.i.d. standard normal and \(\epsilon_i\) are i.i.d. \(\cal N(0, 0.1^2)\). We will consider \(n = 400\) observations as the training data and another 1000 observations as the testing data. Follow the steps below:

• Generate the training and testing data as required
• Write a function called myknn(trainx, trainy, testx, k) to perform KNN regression. You can refer to the lecture notes for the details of how KNN works. You are not allowed to use any existing KNN functions in R to complete this task, but you may use other functions to help the calculation. More specifically, the function should do the following:
  • For each testing observation, calculate the distance between this observation and all training observations.
  • Find the closest k neighbors and return the average of their y values as the prediction.
  • To keep your code efficient, you should only use one for loop in the function.
• Use your function to fit the training data and predict the testing data. Vary k in a grid seq(1, 10, 1).
• Provide a plot of k vs. prediction mean squared error (MSE) on the testing data. For your optimal k, provide a scatter plot of the predicted values vs. the true values on the testing data.
• Comment on the results. How does k affect the prediction error and how?

Question 2: [25 pts] Bias and Variance of KNN

Similar to our previous homework, we can use a simulation study to understand the bias and variance of KNN. To keep this simple, we will consider just one testing point at \((0.5, 0.7, 1)\). Keep in mind that based on our understanding of the bias-variance trade-off, we need to perform repeated simulations to get estimates of the outcome at this point, and then calculate the bias and variance across all simulations. Use the same model setting and training data size as in Question 1. You should try to figure out the procedure of this simulation based on the derivation we did in class. After completing the simulation, you should be able to plot the bias, variance and total error (bias\(^2\) + variance) vs. k = seq(1, 29, 2) in a single plot. Comment on the findings. Do you observe the trade off?

Question 3: [25 pts] Prediction Error Comparison

Let’s compare the performance of your KNN and Lasso. We will inherit the most of the setting as in Question 1 (training and testing sample size and model). However, make the following changes:

• Setting 1: Generate \(p = 30\) instead of \(p = 3\). The outcome is still generated using the first three covariates as in Question 1.
• Setting 2: Generate \(p = 30\) but from a multivariate normal distribution with mean zero, and covariance matrix \(\Sigma\), where the diagonal entries of \(\Sigma\) are all 1, and the off-diagonal entries are all 0.8. The outcome is still generated using the first three covariates as in Question 1.

Compare the performance of KNN and Lasso in these two settings. You should use the glmnet package to fit a Lasso model. Use cross-validation to get lambda.min. For your KNN, use k = 5. You should report the prediction MSE on the testing data for both methods in both settings. You only need to perform this once for each setting. No repeated simulations are needed. Comment on your findings,

• What changes do you observe in these two settings?
• What is the main difference between these two settings that may have caused such changes?

Question 4: [30 pts] MNIST with KNN Multi-class Classification

The MNIST dataset of handwritten digits is one of the most popular imaging data during the early times of machine learning development. Many machine learning algorithms have pushed the accuracy to over 99% on this dataset. We will use the first 2000 observations of this dataset. You can download this from our course website. The first column is the digits. This is a fairly balanced dataset.

  load("mnist_first2000.RData")
  dim(mnist)

## [1] 2000  785

Modify your KNN code for classification with multi-class labels. You already did this for regression in Question 1. Now you need to output the majority label among the k nearest neighbors. For ties, return a randomly selected label among the tied labels. Apply this function to predict the label of the 501 - 2000th observation using the first 500 observations as the training data. Use \(k = 10\) and report the prediction error as a contingency table. Which digits are more likely to be misclassified?