Lecture 2 Statistical Machine Learning: Regression continued

Started with a recap: derivation of a closed form solution for the error function.

But in general, an error function E(w) may be non-quadratic in parameters w, so we have an error landscape instead and cannot find a closed form expression to solve it.

Optimization

In this case, we use gradient descent, with steps in the direction of the negative gradient: meaning, if you take a step in this direction, your error should slightly decrease. But gradient descent finds local minima, not necessarily a global minimum.

Optimization by gradient descent: $w_new := w - \eta \nabla E$.

This converges if $\eta$ is "sufficiently small" and E is bounded from below. Because E is bounded from below, it must converge asymptotically to 0.

See slide for proof.

But note that we still do not need gradient descent if w has a closed-form solution! REVIEW: why of w and not of error?

Model comparison: which M to choose?

Book: 1.1

But we can also choose different orders M for the polynomial. Which one is the best? Does varying M change the optimal solution found by gradient descent?

Too high M will lead to overfitting. Too low M to underfitting.

But how do we assess fit if we don't have access to the ground truth?

To asses the fit, we compute RMSE on training set and test set, and then see where they diverge. If error on the test set goes up whereas it drops on the train set, we are overfitting.

Before we just used the sum of squared errors (SSE), why now use the root mean squared error (RMSE). Why?

$$E_{RMS} = \sqrt{2E(w*)/N}$$

Bishop, p. 26: "division by N allows us to compare different sizes of data sets on an equal footing, and the square root ensures that $E_{RMS}$ is measured on the same scale (and in the same units) as the target variable t"

Overfitting

Book: 1.1

Slide 28: you also see that for M=9 there are huge weight values (both positive and negative). So another way to tackle overfitting is to discourage very high weights.

High weights indicate that too much finetuning is needed

Overfitting is not due to the presence of noise, but due to sparseness of data. It then becomes to easy to fit the noise instead of the data points.

Bishop, p. 28: "We see that, for a given model complexity, the over-fitting problem become less severe as the size of the data set increases. Another way to say this is that the larger the data set, the more complex (in other words more flexible) the model that we can afford to fit to the data. One rough heuristic that is sometimes advocated is that the number of data points should be no less than some multiple (say 5 or 10) of the number of adaptive parameters in the model. However, as we shall see in Chapter 3, the number of parameters is not necessarily the most appropriate measure of model complexity." (28)

If you have a lot of data, a higher order polynomial can still result in a nice fit. This has to be the case by definition, because higher-order polynomials include the exact terms of the lower order polynomial that would be a better fit.

So more complex models require more data to combat overfitting. If that data is not available, we have to apply measures to limit the complexity of the model, such as regularization (see below).

However, this problem does not occur in a Bayesian approach to maximum likelihood:

Also, there is something rather unsatisfying about having to limit the number of parameters in a model according to the size of the available training set. It would seem more reasonable to choose the complexity of the model according to the com plexity of the problem being solved. We shall see that the least squares approach to finding the model parameters represents a specific case of maximum likelihood (discussed in Section 1.2.5), and that the over-fitting problem can be understood as Section 3.4 a general property of maximum likelihood. By adopting a Bayesian approach, the over-fitting problem can be avoided. We shall see that there is no difficulty from a Bayesian perspective in employing models for which the number of parameters greatly exceeds the number of data points. Indeed, in a Bayesian model the effective number of parameters adapts automatically to the size of the data set. (Bishop, 28)

Regularization

Book: 1.1

If you don't have much data, your best option is to apply regularization to penalize complexity. This is done by penalizing larger coefficients.

This is called a shrinkage method of regularization. For quadratic regularizers (such as below), this is called ridge regression (Hoerl and Kennard, 1970). In neural networks, this is called weight decay.

Example:

$$E(w) = \frac{1}{2}\sum_{n=1}^{N}{y(x_n, \textbf{x}) - t_n}^2 + \frac{\lambda}{2}||\textbf{w}||^2$$

Note that w is bold, indicating it's a vector and not a variable.

Lambda governs the strength of the regularization relative to the error term. The division by two is again just to make the derivative cleaner.

  • w0 is often "omitted from the regularizer because its inclusion causes the results to depend on the choice of origin for the target variable (Hastie et al., 2001)" (29)

$||\textbf{w}||$ is the magnitude of vector w.

Example:

For a simple vector (w1, w2)^T, ||w|| is $\sqrt{w_1^2 + w_2^2}$ so the square of the magnitude is simply $w_1^2 + w_2^2$. In terms of vectors, we can write that as $\textbf{w}^T \textbf{w}$. You thus see that the size of the coefficient quadratically contributes to the error.

The book does not provide values for lambda directly, but instead provides them like $ln \lambda = -18$. So I guess the regularization constants will be very very small usually.

Regularization is also more heavy on small data sets, because then the regularization error term is relatively high in comparison with the regular error. On large datasets, this proportion will be smaller; but this is desired, because in this case we also allow more complex models.

The bottom line is the same: effective complexity depends on the amount of training data.

With proper regularization, you apply dampening to the curve. Too large regularization, and you will flatline the curve.

You can find the right amount of regularization again by plotting error values as a function of lambda, again on a train and test set.

Again, regularization is inherent to the Bayesian approach, so this would be a more principled way to tackle this issue.

Linear Basis Function Models / General Solution

Book: 3.1

Let's generalize to functions other than polynomials. A polynomial is just one example of a linear regression model.

The simplest form of linear regression models are also linear functions of the input variables. However, we can obtain a much more useful class of functions by taking linear combinations of a fixed set of nonlinear functions of the input variables, known as basis functions. Such models are linear functions of the parameters, which gives them simple analytical properties, and yet can be nonlinear with respect to the input variables. (156)

So a linear model can be nonlinear in the input whereas still being linear functions of the parameters.

A simple regression line is both linear in the parameters (weights) and the inputs, but this severely restricts the usefulness of this approach.

If we replace $x^j$ with some function $\phi_j(x)$, where $\phi_j(x)$ is non-linear to its input x, then we have linear combination (in the weights) of non-linear functions. This is still a linear model .

And these general functions are called a basis function or feature function. We now have:

$$y(x,\textbf{w}) = w_0 + \sum{j=1}{M-1} w_j \phi_{j}(\textbf{x})$$

Note that $w_0$ is a bias term that is not associated with a basis function. That's why for M parameters we have M-1 basis functions.

We can include the bias in a simpler formula if we define $\phi_00(x)=1$. We then have:

$$y(x,\textbf{w})=\sum{j=0}{M=1}w_j \phi_j(x) = \textbf{w}^T \phi(x)$$

Note that the dot product returns a scalar.

This way we can get a set of linear basis functions (see end of 3.1):

  • Polynomials
    • Then we have basis functions $\phi_j(x) = x^j$.
  • Gaussians
  • Sigmoids
  • Fourier
  • Wavelets etc.

Extension to multiple inputs; deriving the error function.

3.1.1. The book goes more into detail about maximum likelihood: the sum-of-squares error "could be motivated as the maximum likelihood solution under an assumed Gaussian noise model." (159)

The lectures slides skip the reasoning behind why the error function is appropriate and just starts with the new error term.

A shorter reasoning is: the extra complexity of multiple input variables can be hidden in the basis function such that we still have the same old shape for the error term:

$$E(w) = \frac{1/2}\sum_{n=1}^N{t_n - w^T \phi(x_n))^2}$$

How do we now find w? Still the same: differentiate with respect to w, set to zero, and solve to find w.

$\nabla$ w.r.t. w using chain rule:

$$\nabla_w E(w) = \sum_{n=1}{N}(t_n-w^T \phi(x_n))\phi(x_n)^T = 0$$.

I got confused about the transpose at the end. In the book we always assume that vectors are vector columns. So the vector $\phi(x_n)=(\phi(x_0), ... \phi(x_n))^T$. The outcome of the dot product is that again transposed, so we end up with a "horizontal" vector.

We can rewrite the gradient set to zero to the following (see book 142):

$$0=\sum_{n=1}{N}t_n \phi(x_n)^T - w^T(\sum_{n=1}{N}\phi(x_n)\phi(x_n)^T)$$

By 1) multiplying in phi, 2) splitting the sums, 3) taking the weight vector in front of the sum.

When we take $\Phi=\phi(x_n)$, the sums can be rewritten as:

$$0=\Phi^T \textbf{t} - \textbf{w}^T (\Phi^T \Phi)$$

$\Phi$ is called the design matrix with $\Phi_{nj}=\phi_j{x_n}$, that is, each column vector corresponds to a basic function, and each row correspond to one input variable x.

Pay attention: you transpose this again in order to take the dot product with t, so that for each basic function $\phi_i(x_1)$ is multiplied with t1, x2 with t2 and so on.

We now solve for w, move things around, and move one term to the right (that's where the inverse comes from):

Then we get: $w=(\Phi^T \Phi)^{-1} \Phi^T t$

This makes use of $(AB)^{-1} = B^{-1}A^{-1}$ for square and invertible matrices.

This is of the same form as we found for the polynomial solution in exercise 1! There we had $w = A^{-1}T$.

This is the same as computing the whole sum when finding derived f(x)=0.

So now we have a closed expression for optimizing our error function for arbitrary dimensional data with a yet unspecified basis function!

Example: fitting a flat surface to 3-D data.

You can write a second order polynomial (quadric) surface in 3-dimensions as so:

$w_0 + w_1x_1 + w_2x_2 + w_3x_1^2 + w_4x_1x_2 + w_5x_2^2$

Why? I'm not sure I've encountered this before and I'm having a brain fart.

Slide 42 uses shitty notation: $x_n(1)=(x_1, x_n)$

$x_1(1)$: first element of first data point x1 (did I get this correctly?)

Tom Claassen promised a plot that he can't do right now due to technical issues.

Regularized least squares

Book: 3.1.4

Regularization allows complex models to be trained on data sets of limited size without severe over-fitting, essentially by limiting the effective model complexity. However, the problem of determining the optimal model complexity is then shifted from one of finding the appropriate number of basis functions to one of determining a suitable value of the regularization coefficient $\lambda$ (Bishop, 164)

To avoid overfitting, we can add a regularization term to the error function, e.g. weight decay.

wTw -> regularization depends on the size of weights. The larger the weights, the higher the penalty.

We derive the new form (see slide) in the next exercise. For a polynomial we had the closed form solution $w = A^{-1}T$. The Moore-Penrose solution is a generalization of this solution. Now we can derive (Exercise 2.2.7) that the "A" term is slightly adjusted after regularization:

$w = (\lambda I + \Phi^T \Phi)^{-1}\Phi^Tt$

Different forms of regularization have different behaviors.

We have a general standard form (!= weight decay from above):

$$\frac{1}{2}\sum_{n=1}{N}(t_n - w^T\phi(x_n))^2 + \frac{\lambda}{2}\sum_{j=1}{M}|w_j|^q$$

Now we get different regularizers for different values of q.

Ideal: Ignore irrelevant components/basis functions to arrive at a smaller solution.

For q=1, we get a LASSO with regularizer:

With q=2, weight vectors with the same length contribute the same amount.

I do not understand how to read the plots. Also see book 146.

We have y(x,w); with w having n elements. Then the LASSO favors many numbers of w to be exactly 0, so they drop out of your model. This reduced complexity of your model and leads to a sparser solution.

Lasso: bottom slide 45: w*[0,w_2]; forces w_1 contribution to be zero.

All regularizers shrink the weights. But only the LASSO have the extra benefits that it forces parts of the weights to 0, resulting in sparser solutions.

Comments from chat:

"The line is a contour where the penalty term has the same value" "In two dimensions, e.g. the contour where lambda * (|w_1|^q + |w_2|^q) is constant." "Update; you can leave lambda out"

Q: Why does the LASSO result in a sparse solution ($w_j \neq 0$ for only a few j's)?

See slide 1.45 and book p. 164: Minimizing the regularized error function is equivalent to minimizing the unregularized sum-of-squares error under constraint $\sum_{j=1}{M}|w_j| \leq \eta$.

They can be related through lagrange multipliers:

Lagrange multipliers

Book: Appendix E.

Lagrange multipliers, also sometimes called undetermined multipliers, are used to find the stationary points of a function of several variables subject to one or more constraints.

Remember: a "fixed point" is a point for which F(x)=x (cf. gradient descent exercise).

Base case: you could express a constraint between two variables by expressing the one in terms of the other. But this is not always possible and gives one of the variables a special treatment (this is supposedly not elegant, but I don't see the practical issues here).

A more general solution is to use Lagranian multipliers.

Minimize f(x) under constraint g(x)=0.

Adds additional constraint to function you want to optimize.

This is handy when we start working with probabilities, because then we can incorporate the constraint that probabilities have to sum up to zero.