Problem Set 4(Cross-Validation and Bias-Variance decomposition) Solution

Goals. The goal of this exercise is to




Implement 4-fold cross-validation.




Understand bias-variance decomposition.




Setup, data and sample code. Obtain the folder labs/ex04 of the course github repository




github.com/epfml/ML course







This exercise is partly based on the materials from last week (labs/ex03). If you don't have it already, please nish the ex03 rst. You might directly reuse/copy some of the functions you implemented yourself during previous exercises, e.g., ridge regression(), least squares() and split data().










Cross-Validation



The simple 50%-50% split of test and training data from last week's exercise corresponds to the rst phase of 2-fold cross-validation. It may not give an unbiased test error. A better way to do this is to use full K-fold cross-validation.




Exercise 1:




Implementing 4-fold cross-validation.




Please COPY your code from last week, and ll in the corresponding templates, i.e., ridge regression()




to ridge regression.py, build poly() to build polynomial.py, and least squares() to least squares.py.




In this exercise, please ll in the notebook function cross validation demo(), and perform 4-fold cross-validation for polynomial degree 7. Plot the train and test RMSE as a function of . The resulting gure should look like Figure 1.




Note that we can use \numpy.random.seed(seed)" to generate two independent training and test data splits.




How will you use 4-fold cross-validation to select the best model among various degrees, say from 2 to 10? Write code to do it.




BONUS: Using cross-validation, one can also compute the variance of the RMSE, over the folds. This tells us how con dent we could be of our model selection. You can use box-plots to do this.
















Visualizing Bias-Variance Decomposition



In the lecture, we learned about the expected test and train error. In the following exercise, we will reproduce the gure illustrating \error vs. model complexity" of the \bias-variance" lecture notes). Read the lecture notes to understand which quantities are essential for this gure.




Exercise 2:




Visualizing the bias-variance trade-o .




Figure 1: E ect of on training and test errors, calculated using 4-fold cross-validation







Complete the notebook function bias variance demo() and experiment with di erent seeds, number of training and testing examples with least square, to get a plot that looks similar to Figure 2, i.e. on average the train error should go down and test error should go up for higher degrees. NOTE that you should COPY the function split data() implemented in ex03 to the template le split data.py.




Look at the variance of test errors. Does it increase with the degree of polynomial?




What would you expect to happen if you replace least-squares with Ridge regression? Go through the lecture notes to understand that.




BONUS: Another good visualization is to use the box-plot to get an appropriate visualization. You can clearly see the distribution of test error.




BONUS: Produce the same plot with Ridge regression. You will have to automatically nd the best for each degree. You do this using K-fold cross-validation (CV) only on the training set. So you need to insert the CV code inside. You also have to make sure that you chose an appropriate range of , so that you achieve the minimum test error.












Figure 2: Bias-Variance Decomposition