Clinton Boys bio photo

Clinton Boys

I am an Australian data scientist and mathematician, living in Tel Aviv.

Email Twitter LinkedIn Instagram Github Stackoverflow

At work recently I gave a 90-minute colloquium talk on regression. We have a monthly series of talks where researchers and data scientists discuss fundamental topics at length, and although we’d had many interesting talks no one yet had given a thorough and solid introduction to regression theory. Seeing as I don’t mind a challenge, I decided to give it a go.

It turned out to be quite a difficult thing to do, since the range of experience and knowledge in the room was quite vast, from statistics PhDs to computer science undergraduates, and the material is typically not presented all at once. I’m not sure how successful I was in my attempt, but I’m posting parts of the content of the talk here to hopefully provide a good background to people who are interested.

Introduction

Regression is the art and science of estimating the relationships between variables. We will revise the basic ideas behind regression, discuss some important theoretical results and then look into some more advanced topics and methods.

Linear regression

We have a set of features and are trying to use them to predict the value of a continuous dependent variable .

Examples

  • is the height of a person and are their age, mother’s height and father’s height.
  • is the expected arrival time of a delivery and are its distance from the dropoff, the average driving speed in the city and the amount of rain.

The simplest possible non-trivial model is linear: let us assume that changes as some linear combination

of the . How can we find the coefficients ?

The answer is by using a collection of training data, i.e. a set of vectors

for which we know the true output values , find the coefficients which minimise the overall sum of squared differences from the true values:

Easier: reframe in vector notation , :

This is a function of which we can minimise using vector calculus to find the coefficients which give the best model.

\frametitle{Least squares - example} \begin{figure}[h!] \includegraphics[width=0.5\linewidth]{regression1.png} \end{figure}

Differentiating with respect to :

and setting to zero: , gives the solution

We can now use our model to compute modelled values of for any input vector :

In order to better understand statistical properties of this estimate, let’s compute its mean and variance.

Let’s assume for the moment that this model captures the true underlying behaviour; that is, for some normally-distributed errors . Then

So is an unbiased estimator for the parameters .

An estimator for the variance of is

Note The in the denominator is known as Bessel’s correction. It makes an unbiased estimator of .

It’s not too hard to show that

which can be estimated as . We can use these expressions to form confidence intervals for our parameters.

For example, to test the hypothesis that a particular coefficient is statistically significantly different from zero, we form the -score

where is the th diagonal entry of the matrix . Under (), which is very close to for large .

The Gauss-Markov Theorem

TL;DR: Under these assumptions, we can’t do any better than the least squares estimator.

More formally: if we assume , where

  • have zero mean
  • have constant, finite variance
  • are uncorrelated ( for all )

then the least-squares estimator is the best unbiased linear estimator of the parameters : best in this scenario means lowest variance).

Proof.

Let be another unbiased linear estimator for , say .

Then

and so we must have and .

Let’s write for some , using the formula for a generic left inverse of . Then

so . The rest is algebra:

since is positive definite.

Next steps

Ways to generalise:

  • Introduce non-linearity by considering new variables which are powers () or interactions (), or even functions (, etc) of existing features, splines etc
  • Relax the assumptions we made about linearity or the errors , which leads to generalised linear models
  • Reduce the number of features by restricting to the “most important” features
    • Feature subset selection
    • Regularisation, Shrinkage methods

Generalised linear models

Our linear regression setup was

Let’s assume that

  • instead of , is modelled by some known transformation , called the link function
  • instead of being normally distributed, the error terms $\epsilon$ have some arbitrary distribution (from a wide family of distributions known as the exponential family.

This is the setup for a generalised linear model (not to be confused with general linear models).

Logistic regression

Instead of a simple linear model, suppose we want to model the probability that has one of two discrete values.

Examples

  • indicates whether a patient is sick or well, and are continuous measurements from diagnostic equipment or lifestyle factors

Instead of a linearity assumption, we use the logit link function

and assume .

Note that this ensures is indeed a probability (between 0 and 1). Of course the results could still happen to be wrong, but they’re not guaranteed to be wrong as they would be if we tried to fit an unbounded linear model to predict probabilities.

There is no analytically closed solution to fit logistic regression. We must

  • write down the likelihood function $L(X;\beta)=\prod_{i=1}^N p(x_i;\beta)^{y_i}\Bigl(1-p(x_i;\beta)\Bigr)^{1-y_i}$$ and take its logarithm (log-likelihood)
  • differentiate with respect to $\beta$
  • maximise numerically using Newton–Raphson

####Other examples:

  • Poisson regression: Assume that the errors are distributed according to a Poisson distribution instead of normal.
  • Exponential response data

Shrinkage methods

We saw above a statistical test for whether certain coefficients in a linear regression model are significantly different from zero. What if we could “bake” this process into the model?

When considering removing features from the model, we must manage the tradeoff between

  • accuracy: how much of the variance in $Y$ is explained by the model?
  • interpretability: how well do we actually understand what is going on in the model?
  • overfitting: does the model perform well on withheld test sets or just on the training set?

Most intuitive and easiest solution:

  • loop over all combinations of features for between and ( combinations of 1 feature, combinations of 2 features, etc) (there is an efficient algorithm for this so long as )
  • plot the “best subset curve”: find the subset for each
  • the best-subset curve is necessarily decreasing, so cannot be used to select the subset size
  • the question of how to choose k involves the tradeoff between bias and variance, along with the more subjective desire for parsimony
  • e.g.: choose the simplest model (fewest features) within one standard error of the minimum

Ridge regression}

Ridge regression is a method for shrinking coefficients by imposing a penalty on their combined size.

Instead of the usual linear regression least-squares solution we instead solve

The LASSO

Another option is the LASSO (Least Absolute Shrinkage and Selection Operator), which solves the optimisation problem

In turns out that ridge regression and the LASSO behave similarly, but the LASSO is often preferable as it has a nice geometric property which allows some coefficients to be actually set to exactly zero.

Why do we need to do this?

Principal component analysis}

PCA is another way to deal with intercorrelated features. The idea is to replace the initial feature list with linear combinations of features which explain the highest possible amounts of variance.

We start with the singular value decomposition of the training matrix , where are orthogonal matrices and is diagonal. This is a process we can perform on any matrix (doesn’t have to be square) which generalises the eigendecomposition of positive semidefinite normal matrices.

We reorder the columns of and so that the diagonal entries of are in increasing order .

The columns of () span the column space of . These are orthogonal matrices, so , .

For a given , it’s easy to show that the least squares estimator can be written as

and similarly that the ridge regression estimator can be written as

This shows that ridge regression

  • computes the coordinates of with respect to the orthonormal basis (just like OLS regression)
  • shrinks these coordinates by factors

The largest (namely ) has the least amount of shrinkage, and the smallest (namely ) has the most.

It can be shown that the eigendecomposition of the sample variance/covariance matrix is and its eigenvectors , the columns of , are called the principal components of .

The first principal component has the property that has the largest sample variance among all linear combinations of the columns of : its sample variance is

Support vector machines for regression}

A support vector machine is a model for performing classification. To simplify notation, we describe the problem in one-dimension.

Suppose we have some boolean response variable and a single feature . We want to fit a function with the property that

  • all examples from the training dataset are classified correctly: one class is entirely on one side of the line and the other class entirely on the other
  • is the minimal slope with this property

Generalisations:

  • if the data are not separable, we can introduce slack variables which allow for misclassification
  • use the “kernel trick” to embed data in higher dimensional / transformed spaces where it may be separable

To use SVMs for regression, we replace the constraint that “all examples from the training dataset are classified correctly” with the constraint that “all responses are within some fixed of their true response from the training dataset.”