Machine Learning

Assignment 2

Deadline: May 11, 2022 at 23:55h.

Upload your report (report.pdf), your implementation (lsq regression.py) and your figure file (figures.pdf) to the TeachCenter. Please do not zip your files. Please use the provided framework-file for your implementation.

1. Least Squares and Double Descent Phenomenon (17P)

The goal in this assignment is to learn about linear least squares regression and the double descent phenomenon, shown in Figure 1. In the classical learning setting, the U-shaped risk curve can be observed indicating a bad test error while the training error is very low, i.e. the model does not generalize well to new data. However, a highly over-parameterized model with a large capacity allows the test error to go down again in a second descent (“double descent”), which can sometimes be observed in over-parametrized deep learning settings.

 

 

 

 

Figure 1: The double descent risk curve, which shows in addition to the classical U-shaped risk curve the decreasing test error for high-capacity risk function classes. Figure taken from [1].

 

 

We want to reproduce this phenomenon in the context of linear least squares regression with random features. Assume we have input data x = {x₁, ..., x_N }, with x_n ∈ Rd d-dimensional samples uniformely distributed on the unit sphere such that ?x_n?₂ = 1. Furthermore, consider associated targets y = {y₁, ..., y_N } with y_n ∈ R according to

n

4

d

n

y   =   1 + (1^T x  )² −1 + N (0, σ²),                                                                            (1)

 

∈

where 1_d      Rd  is a d-dimensional vector of ones.

Our goal is to model the underlying relation between training input data x and targets y and apply this to new, unseen test data by minimizing the regularized least squares error function

 

 

N

w^∗ = arg min  1 Σ

2

 

w^T φ(x_n) − y_n       +

λ

 

2

?w? .                                        (2)

w∈RM 2

 

2        2

n=1

The (possibly) non-linear transform φ(·) lifts the input data x_n  to a higher-dimensional space with

M features.  Here, we are going to use random features v = {v₁, ..., v_M } on the unit sphere with

 

 

1

 

v_m ∈ Rd and a nonlinear activation function such that

   1

φ(x_n) = √M

 

 

 

m

max(v^T x_n, 0)

 

{m=1,...,M }

 

 

(3)

 

2

Evaluation metrics for predictions yˆ  can be obtained using the mean squared error

 

 

Σ 1L

N

(y, yˆ) =             (y_i

N

i=1

 

 

— yˆ_i)  .                                                              (4)

 

Tasks

1. 1. Rewrite eq. (2) in pure matrix/vector notation, such that there are no sums left in the final expression. Use Φ = φ(x) for the feature transform which can be computed prior to the optimization. Additionally, state the matrix/vector dimensions of all occurring variables.
   2. Analytically derive the optimal parameters w^∗ from eq. (2).
   3. Give an analytic expression to compute predictions yˆ  given w^∗.

 

∈                          ∈

This can also be interpreted as a small feedforward neural network with one hidden layer for an input x    Rd  and output yˆ     R.  Draw a simple schematic of this neural network and include exemplary labels of its neurons and connections.

1. 4. Create a training dataset comprised of input data x = {x₁, ..., x_N } and corresponding targets

y = {y₁, ..., y_N } with N = 200, d = 5 and σ = 2 according to eq. (1).

In the same manner, create a test dataset with N_t = 50 for both test input data and test targets.

1. 5. Generate M = 50 d-dimensional random feature vectors v = {v₁, ..., v_M } on the unit sphere.
   6. Implement the computation of w^∗ from the training data using a QR decomposition. Further, compute the mean squared error denoted in eq. (4) for both the training and test data based on the optimal parameters w^∗.
   7.  

number of feature vectors M =

10k + 1 | k ∈ {0, 1, 2, ..., 60}

and save the training and test

Use λ = 1 × 10⁻⁸ to reproduce the double descent behavio}ur. Run this experiment for a

 

loss in each run. For each M , do the experiment r = 5 times to obtain averaged scores.

1. 8. Plot both the averaged (over the r = 5 runs) train and test errors depending on the number of feature vectors M in the same plot. Include the standard deviation of each setting in addition to the averaged loss. Give an interpretation of your results.
   9.  

{ ×            ×       }

Repeat the same experiment for λ =    1    10⁻⁵, 1    10⁻³    and explain the influence of λ. Include the resulting curves containing train and test error for each λ in two additional subplots.

 

Implementation details

 

•

To efficiently solve a system Ax = b, QR decomposition of the matrix A into an orthogonal matrix Q and an upper triangular matrix R can be used instead of direct matrix inversion (see numpy.linalg.qr). This can be computed as follows:

A = QR

z = Q^T b

Rx = z → x = R⁻¹z    (solve this with numpy.linalg.solve)

−

±

If you want to plot the standard deviation σ in addition to an averaged curve use matplotlib.pyplot.fill between, where y1 and y2 denote µ σ and µ + σ, respectively. You can set an alpha value for blending.

Implement the double descent phenomenon in task12 of lsq regression.py. Do not use any other libraries than numpy and matplotlib.

 

 

2