Lecture One

This is a jupyter notebook. It let's you mix code, figures, and text. You can find all the material (including this notebook) on: https://github.com/wildtreetech/advanced-comp-2017

All the examples and exercises will be in python. The GitHub repository contains instructions on how to get setup on your machine.

Let's dive in, what is all this machine-learning about? To start off we create a toy dataset. Each observation has only two features (variables). This makes it easy to visualise (most montiors are only 2D) and means we will not spend time waiting for the computer to crunch numbers. Most of the intuition we gather from these small datasets transfers directly to larger ones.

Randomly distributed blobs, either red or blue:

The features (or observations) are stored in a two dimensional array named, by convention X. The label (the thing we are trying to predict) is stored in a one dimensional array named, by convention, y. Let's inspect them in a bit more detail:

What if we received a new observation at [3., -2.5]. What would you predict its colour to be?

One good way to make predictions is to look around the neighbourhood of the new point and assign it a label based on its neighbours. This is exactly the strategy of the KNeighborsClassifier. Let's do that:

What about at [3., +2.5]?

If we keep doing evaluating the classifier at every point in the plane we will end up with a plot like the following. It shows the decision surface of the classifier.

Notation

One observation (or sample) $X^T = (X_0, X_1, ..., X_p)$ is a vector with $p$ components. These are the $p$ input variables. Together the $N$ samples in our dataset form a $N\times p$ matrix $\mathbf{X}$. To distinguish the $i$th feature in $x$ from the $i$th observation in $\mathbf{x}$ only vectors of length $N$ will be bold. Therefore $x_i$ is a scalar (the value of the $i$th variable for observation $x$), and $\mathbf{x}_i$ is a vector (the $i$th observation).

Regression relates input variables $X\in \mathbb{R}^p$ to continous outputs $y\in\mathbb{R}$

Classification relates input variables $X\in \mathbb{R}^p$ to categorical outputs $y\in\mathcal{G}$. $\mathcal{G}$ is a finite set, for example $\mathcal{G} = \{-1, 1\}$ or $\mathcal{G} = \{\mathrm{car}, \mathrm{house}, \mathrm{dog}\}$.

General problem statement

Data comes as a finite learning set ${\cal L} = (\mathbf{X}, y)$ where

• Input samples are given as an array $\mathbf{X}$ of shape (n_samples $\times$ n_features), with values in $\mathcal{X}$;
• (Classification) Output values are given as an array $y$, taking symbolic values in ${\mathcal Y}$.
• (Regression) Output values are given as an array $y$, taking real values in ${\mathcal Y}$.

The goal of supervised classification is to build an estimator $f: {\cal X} \mapsto {\cal Y}$.

We are not interested in just any function $f$.

We are looking for $$ f^* = \arg \min_f Err(f) = \mathbb{E}_{X,Y}[ L(Y, f(X)) ] $$ where $L$ is a loss function, for example,

• the zero-one loss $L(Y,\hat{Y}) = 1(Y \neq \hat{Y})$ for classification;
• the squared error $L(Y,\hat{Y}) = (Y-\hat{Y})^2$ for regression.

Linear regression

Another machine-learning model that is easy to understand and probably familiar to most here under a less exciting name is: linear regression.

You probably know it as "fitting a line to my data".

Despite it's simplicity and age it is a successful method that earns a lot of people a lot of money. A true workhorse. It also serves as a good jumping off point for more modern and complex methods. We can introduce all the essential nomenclature and cover technicalities using a simple model before focussing on more complex methods.

Note: we are leaving classification behind for the moment and switching to regression.

Linear regression in it's most simple form is truly simple. Given an observation $X^T = (X_0, X_1, ..., X_p)$ with $p$ inputs, we predict $Y$ using the model:

$$ \hat Y = \hat \beta_0 + \sum_{j=1}^p X_j \hat \beta_j $$

To use this model we need to find a way to use the data to estimate the coefficients $\beta_i$. We do this by fitting the model to our data $\mathcal{L}$, the learning set.

We obtain estimates for the true but unknown parameters $\beta_i$. To separate the estimates from the true values we give them a ^: $\hat\beta_i$. To find estimates we use the loss function $L(Y, f(x))$ that penalises incorrect predictions. In the case of regression a popular choice is the squared error: $$ L = (Y,\hat{Y}) = (Y-\hat{Y})^2 $$ where $\hat Y = \hat \beta_0 + \sum_{j=1}^p X_j \hat \beta_j$. Writing it as above implies a sum over all $N$ observations, more explicitly: $$ L(\beta) = \sum_i^N \left( y_i - x_i^T\beta \right)^2 $$

How do you minimise $L$? In this case either some linear algebra or with a numerical minimiser. In general the method for minimising the loss function is part of the classifier or regressor you are using.

How does this look in practice, some simple data:

We now have our learning set $\mathcal{L}$, the pairs of X (input samples) and y (output values).

To see what the loss function looks like we can calculate its value on a grid of possible values of $\beta_0$ and $\beta_1$.

The linear model can be solved using ordinary least squares. This means you do not have to run a numerical minimiser, instead you do some linear algebra to solve directly for the coefficients. We will come back to different optimisers when we discuss neural networks.

In a real world application you can use the LinearRegression regressor from scikit-learn:

As you can see scikit-learn takes care of minimising the loss function of a classifier or regressor. The coefficients and y-axis intercept we obtain from the fit are close to the values we used to generate the data.

Summary

The basic linear model is not very exciting and a lot of you will already be familiar with it. This is good. It means you can now map the terms learning set, loss function, fitting a model, and estimator to concepts you already know. These terms will keep reappearing and half the work in machine-learning is identifying how to map your problem onto these concepts.

---

Goodness of fit

How do we measure how well our model is performing? How do we make a prediction for how well our model will perform on new, unseen data?

For a simple linear model like this we could count the number of degrees of freedom and the data points. This has the disadvantage that it uses the same data that we used to fit the model, so it is not unseen data. Furthermore it does not work in general for all machine-learning methods.

Instead we split our dataset into two. One is used to fit or train the model. The other is used only to measure the performance of the model. This estimate of the performance is then used to predict the performance on new, unseen data.

Mathematically speaking: we have a learning set $\mathcal{L}$ which we split into a training set $\mathcal{T}$ and a testing set $\mathcal{S}$.

(To make the point more clearly experiment with reducing the number of training samples down to two.)

Model complexity

The regression problem we created above is extremely simple. What if the problem is more complicated? We need a more complex model. Simple problems need simple models, complex problems need complex models.

Let's switch back to our blob dataset and kNN classifier from earlier.

Questions:

• what is the model?
• what is the learning set $\mathcal{L}$?
• what is the loss function $L$?

The kNN model has many parameters that need "fitting" during the training as it memorises the whole dataset. In the case of n_neighbors=1 it fits one parameter for each training point. As n_neighbors increases the number of parameters reduces.

As you increase n_neighbors you decrease the model complexity. When considering only the nearest neighbour your model has as many free parameters as there are training examples. This is a very complex model. At the opposite end of the spectrum a model with n_neighbors=n_samples has only one parameter, it will always predict the average of all training examples.

What about the n_neighbors parameter? Is that not a parameter? Yes and no. It is not a parameter in the same sense as the $\beta_i$s in a linear model. Instead it is a hyper-parameter, it influences the "kind of model" you are fitting to your data.

Bias-Variance trade-off

It can be shown that the best method for making a prediction $\hat y$ at $x$ is to predict the average of all training examples for which $X = x$. When "best" is defined by the average squared error. In practice there is at most one training point at each $x$. In practice this means we settle for: $$ \hat f(x) = \mathrm{Ave}\left(y_i \mid x_i \in N_k(x)\right) $$ where $N_k(x)$ is the neighbourhood containing $k$ points from $\mathcal{T}$ nearest to $x$. This is exactly what kNN does. So why not use it always and for everything?

The curse of dimensionality: as the number of dimensions increases you need an exponentially larger number of training samples to keep $k$ constant.

By making assumptions about the (local) shape of the function we are trying to model we can counteract this and get more stable predictions.

Lienar regression assumes that $f(x)$ is well approximated by a globally linear function.

In contrast kNN assumes that $f(x)$ is well approximated by a locally constant function.

The latter is more flexible, but you have to pay a price for this flexibility. If you do not need the flexibility you can obtain a more stable estimate by making more assumptions.