STAT 542: Homework 9

Instruction

Students are encouraged to work together on homework. However, sharing, copying, or providing any part of a 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 compass2g. No email or hardcopy will be accepted. For late submission policy and grading rubrics, please refer to the course website.

• What is expected for the submission to Gradescope

  • You are required to submit one rendered PDF file HWx_yourNetID.pdf. For example, HW01_rqzhu.pdf. Please note that this must be a .pdf file generated by a .Rmd file. .html format cannot be accepted.
  • Please follow the instructions on Gradescope to select corresponding PDF pages for each question.

• Please note that your homework file is a PDF report instead of a messy collection of R codes. This report should include:

  • Your Name and NetID. (Replace Ruoqing Zhu (rqzhu) by your name and NetID if you are using this template).
  • Make all of your R code chunks visible for grading.
  • Relevant outputs from your R code chunks that support your answers.
  • Provide clear answers or conclusions for each question. For example, you could start with Answer: I fit SVM with the following choice of tuning parameters ...
  • Many assignments require your own implementation of algorithms. Basic comments are strongly encouraged to explain the logic to our graders. However, line-by-line code comments are unnecessary.

• Requirements regarding the .Rmd file.

  • You do NOT need to submit Rmd files. However, your PDF file should be rendered directly from it.
  • Make sure that you set random seeds for simulation or randomized algorithms so that the results are reproducible. If a specific seed number is not provided in the homework, you can consider using your NetID.
  • 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.

About HW9

In this HW, we use two examples to demonstrate how the RKHS and Representer Theorem are used in practice. In both questions, we will use the radial basis kernel, defined as

\[K(\mathbf{x}, \mathbf{z}) = e^{- \frac{\lVert \mathbf{x} - \mathbf{z}\rVert^2}{2\sigma^2}}.\] You are not required to tune the parameter \(\sigma\). The information will be given.

Question 1 [45 Points] Kernel Ridge Regression

Let’s first generate a set of data using the following code (or some similar code in Python):

  set.seed(1)
  n = 500
  p = 2
  X = matrix(rnorm(n*p, 0, 1), n, p)
  y = 2*sin(X[, 1]*2) + 2*atan(X[, 2]*4) + rnorm(n, 0, 0.5)
  
  alldata = cbind(X, y)
  train = alldata[1:200, ]
  test = alldata[201:500, ]

[5 Points] As a comparison, we can first fit a ridge regression to this data. Use the train part to fit a ridge regression using the glmnet() package with 10-fold cross-validation. Use lambda.min as your tuning parameter to predict the testing data. What is the prediction error?

To fit a kernel ridge regression, we use the following formulation:

\[\underset{\boldsymbol \alpha}{\text{minimize}} \quad \frac{1}{n} \big\lVert \mathbf{y} -\mathbf{K} \boldsymbol \alpha \big\rVert^2 + \lambda \boldsymbol \alpha^\text{T} \mathbf{K} \alpha\]

It should be noted that you could add an \(\alpha_0\) term to this regression to rigorously add the intercept term. However, the theoretical mean of \(Y\) is zero. Hence, it is not a crucial issue, and not required here. Following our derivation in the class, perform the following to complete this kernel ridge regression:

• [10 Points] Compute the 200 \(\times\) 200 kernel matrix \(\mathbf{K}\). Use a Gaussian kernel and \(\sigma = 1\).
• [10 Points] Based on the kernel ridge regression derivation, get the solution \(\boldsymbol \alpha\). Use \(\lambda = 0.01\)
• [10 Points] The prediction of kernel ridge regression involves computing the kernel between a testing data and all the training data. To be specific, if we have a new testing data \(z\), then the prediction \(\widehat{f}(z)\) is \[\widehat{f}(z) = \sum_{i = 1}^n \alpha_i K(z, x_i)\] Since we have 300 testing data, this involves calculating a 300 \(\times\) 200 testing data kernel matrix, denoted as \(K_\text{test}\), and the vector of prediction is \(K_\text{test} \boldsymbol \alpha\).
• [10 Points] Predict the testing data using the kernel and \(\widehat{\boldsymbol \alpha}\). What is the prediction error? Is it better than the ridge regression?

Question 2 [55 Points] Non-linear SVM as Penalized Version

Recall that in HW8, we solved SVM using a penalized loss framework, with the logistic loss function: \[L(y, f(x)) = \log(1 + e^{- y f(x)}).\]

Again, we can specify the form of \(f(\cdot)\) as in a RKHS. And the penalized objective function becomes

\[\frac{1}{n} \sum_{i=1}^n L(y_i, K_i^\text{T} \boldsymbol \alpha) + \lambda \alpha^\text{T} \mathbf{K} \alpha\] where \(\mathbf{K}\) is the same \(n \times n\) kernel matrix as before and \(K_i\) is the \(i\)th column of \(\mathbf{K}\). The data are generated by the following code.

  set.seed(1)
  n = 500
  p = 2
  X = matrix(runif(n*p, -2, 2), n, p)
  y = sign( X[, 2] - sin(pi*X[, 1]))
  alldata = cbind(X, y)
  train = alldata[1:200, ]
  test = alldata[201:500, ]

  # visualize the data 
  plot(train[, 1], train[, 2], col = ifelse(y > 0, "red", "blue"), 
       pch = 19, )
  lines(seq(-3, 3, 0.01), sin(pi*seq(-3, 3, 0.01)) )

Similar to the HW8 linear SVM penalized version, we perform the following steps to complete this model fitting:

• [15 Points] Write a penalized loss objective function SVMfn(b, K, y, lambda) corresponding to the form we specified. Make sure to use the \(1/n\) scale in the loss function part.
• [20 Points] Drive the gradient of the loss function, typeset with LaTex. Then write a gradient function SVMgr(b, K, y, lambda) to implement it.
• [20 Points] Use the optim() function to solve this optimization problem by supplying the objective function and gradient function. Use \(\sigma = 0.2\) and \(\lambda = 0.01\). Initialize your coefficients as zeros. Report the following:
  • The optimal loss function
  • A confusion table of the training data
  • Mis-classification rate on training data.
• It could be difficult to obtain the decision line itself. However, its relatively easy to obtain the fitted label for the testing data. Hence, calculate the fitted label of the testing data and report the classification error. Plot the testing data using the fitted labels as colors. You should also add the true decision line (since you already know the true data generator). This would allow you to visualize (approximately) the decision line. You do not need to plot the original labels.

Note: 1) In a real problem, you can perform cross-validation to find the best tuning parameters. 2) You may also add a constant term \(\alpha_0\) to the problem to take care of intercept. These two are not required for the HW.