Extra Exercises

More exercises, by topic

The exercise page of each week holds a handful of exercises, about what a two hour session allows. This page collects the rest, grouped by topic rather than by week, for revision and for exam preparation. Nothing here is new material: every topic points back to the week that covers it, and the exercises assume only what that week has already introduced.

Exercises marked optional go beyond what is required.

Supervised learning: data generating processes and likelihood

From week 2.

Exercise 1

Take one of the applications of machine learning from slides of week 1 (introduction). Discuss with a colleague

the data generating process for \(X\),
the data generating process for \(Y|X\),
where the noise comes from,
a distribution that could be used to model \(Y|X\).

Exercise 2

On the two classes page we chose a Bernoulli distribution and let the loss follow.

Write the log-likelihood of \(\theta_0, \theta_1\) for the training data \(((x_1 = 0, y_1 = \text{B}), (x_2 = 2, y_2 = \text{A}), (x_3 = 3, y_3 = \text{B}))\) under \(P(Y = \text{A}|x) = s(\theta_0 + \theta_1 x)\).
Show that \(1 - s(z) = s(-z)\), and use it to write your answer with a single \(s\) and no subtractions.
Unlike linear regression, this has no closed form. Show that the derivative with respect to \(\theta_1\) contains \(s\) evaluated at the data, and explain in one sentence why that prevents solving for \(\hat\theta_1\).
The zero-one loss counts mistakes and is the number we report. Explain why we do not minimize it directly, in terms of its derivative.

Linear regression and the choice of predictors

From week 2.

Exercise 3

Run a multiple linear regression on the weather data with two predictors, the pressure in Luzern and the sunshine duration in Luzern. Is the prediction on the test set better than with the pressure alone, as fitted on the linear regression page.

Exercise 4 optional

On the linear regression page we used all available predictors of the weather data. We do not know whether all of them are relevant.

Search systematically for the model with at most 2 predictors that has the lowest test RMSE. Write a function that takes the training data, the test data and a pair of predictors, fits a linear regression and returns the test RMSE.
How much higher is the test error than with all predictors.
How many models did you have to fit.
How many would you have to fit for the best model with at most 5 predictors.

Flexibility, bias and variance

From week 3.

Exercise 5 optional

Compare \(k\) nearest neighbours and polynomial regression on the generator of week 3, exercise 6.

For \(k = 1, \dots, 30\), compute the test error of \(k\) nearest neighbours.
Plot it against \(1/k\) together with the polynomial curve from that exercise, plotted against the degree, on the same axes.
Which method does better here, and can you say why from the shape of \(f\).

Hint: k nearest neighbours has the KNeighborsRegressor call and polynomial regression the pipeline for the other half.

Exercise 6

Week 3 has nine illustrations. Use four of them.

On polynomial regression, read off the degree with the smallest test loss at \(\sigma_{\text{gen}} = 0.01\) and at \(\sigma_{\text{gen}} = 0.30\). Which way does it move, and why?
On k nearest neighbours, do the same for \(K\) at \(\sigma_{\text{gen}} = 0.01\), \(0.10\) and \(0.20\). The direction is the opposite of the one in part 1. Explain why that is the same statement.
On bias and variance, put x_test in the middle of its range and step the degree from 1 upwards, watching the bottom plot. At which degree does the variance overtake the squared bias there? Now move x_test to either end and say what is different.
On regularization, find the smallest reducible error the polynomial ridge panel reaches at degree 4, then at degree 20. What does the comparison say about degree as a measure of flexibility?
In every one of these panels the test loss is flat near its minimum. Say what that flatness costs you when you have to choose a hyper-parameter from data.

Model assessment and tuning

From week 4.

Exercise 7

For a model that is linear in its parameters, leave-one-out has the closed form \(\mathrm{CV}_n = \frac1n\sum_i \bigl((y_i - \hat y_i)/(1 - h_{ii})\bigr)^2\).

Show that \(\sum_i h_{ii} = p + 1\) for a design matrix with \(p\) predictors and an intercept. Hint, \(H\) is a projection, so consider its trace.
What is the average leverage. Explain why \(\mathrm{CV}_n\) blows up when the number of parameters approaches \(n\).
Why is there no similar shortcut for \(K\)-fold with \(K < n\).

Exercise 8

Ask a language model to write a function that evaluates a classifier with cross-validation on an imbalanced data set where only 3 percent of the cases are positive.

Record the answer.
Check three things. Does it stratify the folds. Does it report a metric that survives 97 percent class imbalance. Does any preprocessing sit outside the fold loop.
For each of the three, say whether the answer got it right, got it wrong, or did not mention it. The third case is common, and it is the one that costs points.
In one paragraph, say what you needed to know already in order to find the errors you found.

Exercise 9

Reproduce the measurement on the tuning page, then extend it.

Run it again with a larger search. Use polynomial degree 1 to 10 together with a ridge penalty \(\lambda \in \{10^{-4}, \dots, 10^{2}\}\), so 70 combinations.
Plot the gap between flat cross-validation and the truth as a function of the number of combinations searched, for \(m \in \{2, 5, 10, 25, 70\}\).
The gap grows roughly like the expected minimum of \(m\) noisy draws. What does that mean for a project in which you try 500 configurations.

Exercise 10 optional

The leave-one-out shortcut of the previous exercise assumed a model that is linear in its parameters. Test how far it goes.

Implement leave-one-out by brute force and with the hat matrix formula for polynomial regression. Check that they agree to machine precision.
Now apply the same formula to ridge regression, where the hat matrix is \(H_\lambda = X(X^\top X + \lambda I)^{-1}X^\top\). Does the identity still hold exactly. Check it numerically for three values of \(\lambda\).
Explain why it fails for \(k\) nearest neighbours, and what leverage would even mean there.

Gradient descent

From week 5.

Exercise 11

Assume the noise in a linear regression setting comes from a Laplace distribution, i.e. the conditional probability density of the response is given by \(p(Y = y | X = x, \beta) = \frac1{2s}\exp(-\frac{|y - x^T\beta|}{s})\). For simplicity we assume throughout this exercise that the intercept \(\beta_0 = 0\) and does not need to be fitted.

Calculate with paper and pencil the negative log-likelihood loss. Apply transformations to the negative log-likelihood function to obtain a good loss function for gradient descent. The solution you should find is \[ \tilde L = \frac1{n} \sum_{i=1}^n |y_i - x_i^T\beta|. \]
Compute \(\partial\tilde L/\partial\beta_j\). What is different about this gradient compared to the one for the squared error?
Assume the training data consists of \(x_1 = (1, 0, 0), y_1 = 4\) and \(x_2 = (1, 0, 2), y_2 = -1\) and you start with \(\beta_1^{(0)} = \beta_2^{(0)} = \beta_3^{(0)} = 0\). Compute with paper and pencil two steps of gradient descent on the negative log-likelihood loss with learning rate \(\eta = \frac1{10}\).

Generate a training set of 100 points with the following data generator. Notice that the noise follows a Laplace distribution instead of a normal distribution.

import numpy as np

def data_generator(n=100, beta=[1., 2., 3.]):
    x = np.random.randn(n, 3)
    y = np.dot(x, beta) + np.random.laplace(0, 0.3, n)
    return {'x': x, 'y': y}

Code a function to compute the loss on the training set for a given parameter vector. Hint: use matrix multiplication, e.g. torch.matmul(data["x"], beta). For conversion from numpy to torch there are multiple options, like torch.tensor(numpy_array) or torch.from_numpy(numpy_array). For conversion back one can use torch_tensor.detach().numpy().
Perform gradient descent on the training set. Plot the learning curve to see whether gradient descent has converged. If you see large fluctuations at the end of training, decrease the learning rate. If the learning curve is not flat at the end, increase the maximal number of steps. To see well the loss towards the end of gradient descent it is advisable to use log-scale for the y-axis.
Estimate the coefficients with the standard linear regression. Hint: do not forget that we fit without intercept.
Compare which method (6) or (7) found parameters closer to the one of our data generating process [1, 2, 3] and explain your finding.

Nonlinear features and XOR

From week 5, week 6 and week 7.

Exercise 12 optional

The XOR problem. Generate points in two dimensions with class 1 if \(x_1 x_2 > 0\) and class 0 otherwise.

Fit a logistic regression and report the accuracy. Plot the decision boundary.
Add the product \(x_1 x_2\) as a third predictor and fit again.
Explain what the third predictor changed, in terms of the geometry of the problem.

Exercise 13

The XOR problem (see the XOR problem) has a non-linear decision boundary in the original \(X_1, X_2\) coordinates, but a linear decision boundary in the \(H_1, H_2, H_3, H_4\) coordinates, with \(H_i = \max(0, w_i^TX)\) and the vector features \(w_1 = [1, 1]\), \(w_2 = [1, -1]\), \(w_3 = [-1, 1]\) and \(w_4 = [-1, -1]\). Here we prove that \(-H_1 + H_2 + H_3 - H_4 = 0\) defines indeed a linear decision boundary that solves the xor-problem.

Show that \(-H_1 + H_2 + H_3 - H_4 < 0\) for all points with \(X_1 > 0\) and \(X_2 > 0\).
Show that \(-H_1 + H_2 + H_3 - H_4 < 0\) for all points with \(X_1 < 0\) and \(X_2 < 0\).
Show that \(-H_1 + H_2 + H_3 - H_4 > 0\) for all other points.

Exercise 14

Repeat the XOR experiment from week 5, this time with a network rather than a hand-built feature.

Generate 400 points of XOR data with two inputs.
Fit a network with one hidden layer of 4 relu neurons.
Plot the weight vector of each hidden unit. How does the network split the plane.
Rerun with 5 different seeds. How often does it fail, and what does failure look like.

Exercise 15 optional

Take the quadrant data from the classification page.

Reproduce the two fits and the two accuracies.
Add \(x_1 x_2\) as a third feature and refit the logistic regression. What happens.
You now have three models: linear, linear on a hand-built feature, and a network. Rank them by test AUC, by number of parameters, and by how much you had to know about the data in advance.

More than two classes and the softmax

From week 5 and week 7.

Exercise 16

A network with no hidden layer, a softmax output and the cross-entropy loss is fitted by gradient descent.

Show that it is multinomial logistic regression.
The loss of that model is convex in the parameters, but the loss of the same model with one hidden layer is not. Where exactly does convexity get lost.
Two runs of the hidden-layer network from different random initializations give different parameters but almost the same test accuracy. Explain how both can be true.

Exercise 17

Multinomial logistic regression by hand, following more than two classes.

Generate 600 points in two dimensions from three well-separated Gaussian clusters, one per class.
Fit it with torch, writing the cross-entropy yourself from the softmax rather than calling cross_entropy. Compare the loss curve to the one you get from cross_entropy.
Now generate a point with \(\eta = (800, 799, 0)\) and evaluate both versions. One of them returns nan. Explain why, and what cross_entropy does differently.
Fit the same data with the last row of \(\theta\) frozen at zero. Show that the fitted probabilities are the same, and count the free parameters in each case.

Multilayer perceptrons

From week 6 and week 8.

Exercise 18

A network with one hidden layer of \(m\) relu neurons and a linear output has \(m(p+1) + m + 1\) parameters, and it is piecewise linear with at most \(m\) kinks, as shown in week 6, exercise 3.

A polynomial of degree \(d\) in one input has \(d+1\) parameters and is smooth. For which kinds of true function would you expect the piecewise linear family to do better, and for which the polynomial.
Both families can be made arbitrarily flexible. Which knob does each one have, and which of the two is easier to tune by cross-validation.
The universal approximation theorem says one hidden layer suffices, if it is wide enough. Explain in two sentences why that theorem does not settle the question of how many layers to use.

Exercise 19 optional

Fit a polynomial of degree 3 in 1000 input dimensions with a network.

Generate data where only 5 of the 1000 inputs matter.
Fit a network and report the test error.
Fit a lasso on the same data and compare. Which one finds the 5 relevant inputs.

Exercise 20

Compare the four ways of regularizing a network on the bicycle rental data of week 8.

No regularization.
Weight decay, three values.
Dropout, three rates.
Early stopping.

Report the test deviance for each and say which one gives the best result per unit of effort spent tuning.

Evaluating a classifier

From week 7.

Exercise 21

Open the threshold illustration on the evaluation page.

Move the threshold from 0 to 1 and describe the path the marked point takes on the ROC curve.
Find the threshold that maximizes the accuracy. Is it 0.5.
Change the seed several times at a fixed threshold. How much does the confusion matrix move, and what does that tell you about reporting a confusion matrix from 400 points without an interval.

Exercise 22

The code below is meant to compare a logistic regression with a network on a classification problem. It reports that the network is much better. Three things are wrong with it.

X = StandardScaler().fit_transform(features)
y = labels

lin = LogisticRegression().fit(X, y)
net = MLPClassifier(hidden_layer_sizes=(256, 256), max_iter=2000).fit(X, y)

print("linear: ", lin.score(X, y))
print("network:", net.score(X, y))

fpr, tpr, _ = roc_curve(y, net.predict(X))
print("network AUC:", auc(fpr, tpr))

Find all three problems.
For each one, say whether it makes the comparison favour the network, favour the linear model, or simply produce a meaningless number.
Fix the code.

Exercise 23

Write a data generator function that samples inputs \(x\) normally distributed with mean 2 and standard deviation 3. The response \(y\in\{\text{true, false}\}\) should be sampled from a Bernoulli distribution with rate of \(\text{true}\) equal to \(\sigma(0.5x - 2.7)\) where \(\sigma(x) = 1/(1 + e^{-x})\) is the sigmoid (or logistic) function.

Create a training set of size \(n = 20\).
Fit the data with logistic regression.
Look at the fitted parameters.
Predict the probability of class true on the training input. Hint: use the predict_proba function.
Determine the class with highest predicted probability and compare the result to the labels of the training set.
Create a test set of size \(n = 10^4\) where the input is always at \(x = 4\). Estimate the average test error at \(x = 4\) using this test set. Use the negative log-likelihood as error function.
Compute the test error at \(x = 4\) using the fitted parameters and compare your result to the previous result. Hint: the expected negative log-likelihood at \(x = 4\) is an average over the two possible values of \(y\), weighted by their probabilities under the generator.
Rerun your solution with different training sets of size \(n = 20\) and write down your observations.
Rerun your solution multiple times with training sets of size \(n = 10^4\). Compare the fitted parameters to the one of the generator and look at the test error. Write down your observations.
Repeat steps 1 and 2 with a network with one hidden layer of 32 neurons. Does the test error at \(x = 4\) get better or worse, and why.

Counts and Poisson regression

From week 7 and week 8.

Exercise 24

In this exercise we have a closer look at the bike sharing data (fetch_openml(data_id=42712, as_frame=True, parser="auto").frame, see data sets).

Follow the code examples on the counts page to run a Poisson regression on the responses count with predictors temp and humidity.
For comparison, run a linear regression on the same inputs and output.
Fit a Poisson network on the same inputs and output.
Create a scatter plot with the true counts on the x-axis and the predictions of the counts for the linear regression model, the Poisson model and the Poisson network on the y-axis. If the model perfectly captures the data, the plotted points should lie on the diagonal; add the diagonal to the figure to help seeing deviations from perfect predictions.
Comment on the differences you see in the plot between the Poisson model and the linear regression model.
Report the mean Poisson deviance of all three on a held-out test set, and say which one you would use and why.

Exercise 25 optional

Replace the Poisson likelihood of the Poisson network by a negative binomial one, which has an extra parameter for the dispersion.

Write down the loss.
Fit it as a second output of the same network.
Compare to the Poisson model. Is the data overdispersed.

Convolutional networks

From week 9.

Exercise 26

We want to classify RGB images of 100 by 100 pixels into 20 classes. Compute the number of parameters for each architecture.

Flatten, then one dense layer of 200 neurons, then the output layer.
Two convolutional layers with 32 filters of size 3 by 3, each followed by 2 by 2 max pooling, then flatten, then the output layer.
The same as 2 but with 64 filters in the second layer.

Exercise 27

Transfer learning.

Take a network pretrained on ImageNet, for example resnet18 from torchvision.
Replace the output layer by one with the number of classes you need.
Freeze all other parameters and train only the new layer, on a few hundred images.
Compare to training the same architecture from scratch on the same data.

Trees and support vector machines

From week 10.

Exercise 28

For each data set below, say which of the four methods of week 10 — a single tree, a random forest, gradient boosting and a support vector machine — you would try first and why.

500 rows, 10 predictors, mostly categorical, and the client wants to know which predictor matters.
200 rows, 20000 predictors, two classes.
Two million rows, 30 numeric predictors.
60000 images of 28 by 28 pixels.

Exercise 29

Tune gradient boosting properly, on the weather data of week 2.

Cross-validate over the number of trees, the learning rate and the maximum depth. Boosting adds trees one at a time, so you need not refit for every number of trees — see staged_predict.
Plot the cross-validated error against the number of trees, one line per learning rate. What is the relationship between the two.
How much better is the tuned model than the default one.
How much of that improvement survives when you score on a held-out test set.

Exercise 30 optional

Compare kernels for a support vector machine on the MNIST digits, using only the classes 3 and 8 and the first 2000 rows.

Fit with a linear kernel and with an RBF kernel, tuning \(C\) and \(\gamma\).
Report the test accuracy of both.
How many support vectors does each one use, and what does that tell you.

Clustering

From week 11.

Exercise 31

The iris data of week 11, exercise 4, this time with hierarchical clustering.

Build the dendrogram with complete linkage and Euclidean distance.
Cut it to get three clusters and compare to the species.
Repeat with single, average and Ward linkage. Do the results change qualitatively.
Repeat without standardizing. How much does it matter here.

Exercise 32 optional

Cluster the MNIST digits with k-means and ten clusters.

Show five images from each cluster.
Compute the confusion matrix against the true labels.
Which digits end up in the same cluster, and can you say why from the images.

Exercise 33 optional

Generate data with no cluster structure at all, for example 500 points uniform on a square.

Run k-means for \(k = 2\) to \(8\) and plot the silhouette score.
Run it on data with three genuine clusters and plot the same curve.
Compare the two curves. How would you tell, from the curve alone, that the first data set has no clusters.

Dimensionality reduction

From week 12.

Exercise 34

On principal component regression.

Explain why PCR can help when the predictors are strongly correlated.
Explain why PCR can fail badly even when it explains 99 percent of the variance in \(X\).
What is the relationship between PCR and ridge regression, in one sentence.

Exercise 35

Compression and denoising on the digits data.

Reconstruct the images from 2, 5, 10 and 30 components and plot them.
Plot the reconstruction error against the number of components.
Add normal noise with standard deviation 4 and repeat. At which number of components is the reconstruction closest to the clean image.
Explain why that number is smaller than the number needed without noise.

Exercise 36 optional

Compare PCA and t-SNE on MNIST.

Take 5000 images. Plot the first two principal components, coloured by digit.
Run t-SNE on the same 5000 images and plot the result.
Run t-SNE three times with different seeds. How much does the picture change.
Run PCA to 50 components first and then t-SNE on those. Compare the result and the running time.