1.  (10 points)  The cost of fitting a model with p basis functions and N data points (say, using QR factorization) is 2Np2  flops. In this exercise, we explore the complexity of carrying out 10-fold cross validation on the same data set. We assume that N is much larger than p, i.e., N ≫ p, and divide the data set into  10 folds, each with N/10 data points.   The na¨ıve method is to fit  10 different models, each using 9 of the folds, using the QR factorization, which requires 10 · 2(0.9)Np2  = 18Np2 flops.  (To evaluate each of these models on the remaining fold requires 2(N/10)p flops, which can be ignored compared to the cost of fitting the models.) So the na¨ıve method of carrying out 10-fold cross validation requires, not surprisingly, around 10 × the number of flops as fitting a single model.

The method below outlines another way to carry out 10-fold cross-validation.  Give the total flop count for each step, keeping only the dominant terms, and compare the total cost of the method to that of the na¨ıve method. Let A1 , . . . ,A10 denote the (N/10) ×p blocks of the data matrix associated with the folds, and let b1 , . . . ,b10  denote the right-hand sides in the least squares fitting problem.

Step 1: Form the Gram matrices Gi  = Ai(T)Ai  and the vectors ci  = Ai(T)bi .

Step 2: Form G = G1 + ··· + G10  and c = c1 + ··· + c10 .

Step 3: For k = 1, . . . , 10, compute θk  = (G − Gk ) − 1 (c − ck ).

2.  Suppose that x is an N-vector representing time series data. The (one step ahead) prediction problem is to guess xt+1, based on x1 , ..., xt .  We will base our prediction t+1  of xt+1  on the previous M values, xt , xt − 1 , ..., xt −M+1 .  (The number M is called the memory or lag of our predictor.) When the prediction is a linear function,

t+1  = β 1 xt + β2 xt − 1 + ··· + βM xt −M+1 ,

it is called an auto-regressive predictor.  (It is possible to add an offset to t+1, but we will leave it out for simplicity.) Of course we can only use our auto-regressive predictor for M ≤ t ≤ N − 1.

Some very simple and natural predictors have this form.  One example is the predictor t+1  = xt , which guesses that the next value is the same as the current one. Another one is t+1  = xt + (xt − xt − 1 ), which guesses what xt+1  is by extrapolating a line that passes through xt  and xt − 1 .

We judge a predictor (i.e., the choice of coefficients βi ) by the mean-square prediction error

N − 1

J =  工 (t+1 − xt+1)2 .

A sophisticated choice of the coefficients βi   is the one that minimizes  J.   We will call this the least-squares auto-regressive predictor.

(a)  (10 points)  Find and report J for the two simple predictors described above, i.e., t+1  = xt and t+1  = xt + (xt − xt − 1 ), for both the train and test data. Round your results to 4 decimal places.

(b)  (10 points)  Find the matrix A and the vector b for which J = ∥Aβ −b∥2 /(N −M). This allows you to find the coefficients that minimize J, i.e., the auto-regressive predictor that minimizes the mean-square prediction error on the given time series. Be sure to give the dimensions of A and b.

(c)  (10 points)  For M = 2, . . . , 12, find the coefficients that minimize the mean-square prediction error on the time series x train given in time series data .ipynb. The same file has a second time series x test that you can use to test or validate your predictor.  Give the values of the mean-square error on the train and test series for each value of M . What is a good choice of M? Round your results to 4 decimal places.

Hint.  You can use the toeplitz function described on page 65 of the Python companion.  It will make your life a lot easier.

3.  Consider a fitting problem with n = 1, so x(1) , . . . ,x(N)  and y (1) , . . . ,y (N)  are scalars. We consider two types of closely related models.  The first is a piecewise-linear model with knot points at  −1 and 1, as described on pages 256-257 of the textbook, and illustrated in Figure 13.8.  The second is a stratified model (see page 272 of the textbook), with three independent affine models, one for x < −1, one for −1 ≤ x ≤ 1, and one for x > 1. (In other words, we stratify on x taking low, middle, or high values.)

(a)  (5 points)  Are these two models the same? Is one more general than the other? (b)  (5 points)  How many parameters does each model have?

(c)  (5 points) What can you say about the training set RMS error, and the testing set RMS error that would be achieved using least squares with these two models?

4.  The file lsq classifier data .ipynb contains feature n-vectors x1 , . . . ,xN , and the associated bi- nary labels, y1 , . . . ,yN , each of which is either +1 or −1. The feature vectors are stored as an n × N matrix X with columns x1 , . . . ,xN , and the labels are stored as an N-vector y . We will evaluate the error rate on the (training) data X , y and (to check if the model generalizes) a test set Xtest , ytest , also given in lsq classifier data .ipynb.

(a)  (10 points)  Least squares classifier.  Find β,v that

minimize

N

工(xi(T)β + v − yi )2

i=1

on the training set.  Our predictions are then fˆ(x) = sign(xT β + v).  Report the classification error on the training and test sets, i.e., the fraction of examples where fˆ(xi )  yi . There is no need to report the β,v values.

(b)  (10 points)  Regularized least squares classifier.  Now we add regularization to improve the gen- eralization ability of the classifier. Find β,v that

N

minimize    工(xi(T)β + v − yi )2 + λ∥β∥2 ,

i=1

where λ > 0 is the regularization parameter, for a range of values of λ .  Solve the problem for the following values of λ:  10 − 1 , 100 , 101 , 102 , 103 .  Based on your results, suggest a reasonable choice of λ and report the corresponding classification error on the training and test sets. Again, there is no need to report the β,v values.  Hint:  plot the training and test set errors against log10 (λ).