ISMI 3a: Supervised Learning

Discriminative model: when we aim at finding a decision boundary.

Validation

Before machine learning, we'd for example have 10k labeled data points. We'd then reserve about 10% for validation and 10% for testing, which amounts to 1000 points for each.

In times of deep learning we often use way more data points, in the order of millions. This means that in practice the percentage reserved for validation and testing is also lower, for example 1% for each. 1% of a million is already 10k samples for validation and 10k for testing, which is decent for getting performance estimates.

In times of deep learning, we use/need way more labeled data than before deep learning. Instead of 10k labeled samples being sufficient, we need more like a million labeled samples.

k-fold Cross-validation

I do not get this section! Normally, during cross-validation the way I understand it, you hold out your test set like you normally do. Of the remaining data, for k-fold crossvalidation you divide it in k subsamples where one is the training set, the other is the test set. You repeat this k times.

What these slides say is:

  • Divide the whole dataset into k subsets
  • Use 1 as validation set
  • Use 1 as test set
  • Use k-2 remaining subsets as training set
  • Repeat k times for all possible combinations.

I guess this is actually the same, but what I mentioned above is just one training iteration with one held-out test set. This results in one trained model. Since you've tested on the test set here, another training round requires you to start with a fresh model.

The proposed schema here uses k-possible holdouts. So this procedure results in k different models!

Leave-k-out and leave-one-patient-out

k-fold cross validation is non-exhaustive, meaning you do not use all possible splits.

Leave-one-out is exhaustive (leave-k-out with k = |training data|).

Important: In medical imaging you do not want information from a patient to seep through between train/validation/test set. The main goal is that your results generalize to unseen patients. So you want a leave-one-patient-out cross-validation schema!

Which model to pick in the end?

For a final prediction, you can:

  • Pick a random trained model if performance of all models is similar
  • Combine the predictions of all models, e.g. after k-fold cross validation
    • But... does this not secretly use some information from the test set?
  • Only use cross-validation to pick the best hyper-parameters; once they are found, retrain your model on all the training data. It will be applied on other unseen data anyways.

Parametric models

$y=f(x,W)$ with parameters $W$.

The more parameters $W$, the higher the capacity of the model.

If the capacity is too poor, we'll end up with under-fitting. If the capacity if too large (relative to the available data points) we'll end up with over-fitting.

You want to find the optimal capacity that balances 1) fitting the data and 2) generalization to unseen test data.

For 1 you use a parameter optimization algorithm and for 2 you use a good validation schema.

Neural networks

All standard intro stuff.

Artificial neuron: $y = f( \sum_i w_i x_i + b)$ Or when you include bias as a parameter: $f(\mathbf{Wx})$.

Where $f$ is a non-linear function, e.g. sigmoid or tanh. These were popular pre-2012 and have some problems.

Without non-linearity hidden layers are useless, as the whole model will still be a linear transformation.

Dense layer parameters: for n neurons and m inputs, nxm + n inputs (+n for biases).

Output layer: sigmoid and softmax for (multi-class) classification.

Softmax:

$$P_i = \frac{ e^{z_i}}{\sum_k e^{z_k}}$$

Loss functions

Binary cross-entropy

$L(y_i, \hat{y_i}) = -y_i log(\hat{y_i})-(1-y_i)log(1-\hat{y_i})$

If y=1, the loss function requires $\hat{y}$ to also be large. If y=0, the loss function requires $\hat{y}$ to also be small.

Note that the cross-entropy loss includes a negative logarithm. When $\hat{y}=0$ we end up with $log(0)=Inf$.

So in practice, we can solve this by clipping the classifier output to something small like 0.001 or so.

Categorical cross-entropy loss (extension to multiple class)

$L_i=-\sum_j y_{i,j}log(\hat{y}_{i,j})$ using one-hot encoding

Optimization

A loss is computed over each training sample. The cost function is typically the average loss over the whole training set, as a function of the relevant parameters (weights in case of a neural network).

  • Compute the gradient vector of partial derivatives w.r.t. weights
  • Take a step in the direction of the negative gradient

$W_t = W_{t-1} - \eta \nabla_W J(W)$

Note that J(W) is the cost function (i.e. the average loss over samples). In general, gradients are computed per sample and then accumulated over $N$ samples. The update then is by $\frac{\nabla W}{N}$.

  • Batch gradient descent: compute gradients over all samples
  • Stochastic gradient descent: compute gradient over one random sample at a time
  • Mini-batch gradient descent: compute gradient over n random samples.

N.B. what people now call SGD is actually mini-batch gradient descent.

See stochastic_gradient_descent.md

Backpropagation

During backpropagation you may encounter out of memory errors. Where and why is all this memory used during backpropagation?

Backpropagation computes gradients of expressions through recursive application of the chain rule.

$$\frac{dz}{dx} = \frac{dz}{dy} \frac{dy}{dx}$$

This implies that you compute the partial derivatives for each intermediate computation node. You can pre-compute all gradients. During backpropagation, you can then immediately "fill in" the concrete values from the forward pass, starting from the loss at the end of the network and moving towards the inputs and weights.

This means that you always first need to do a forward pass and memorize the forward values. So this memory requirement cannot be done away with. If your network has a lot of parameters this may cause memory issues, because all parameter values need to be stored in memory.

The backpropagation algorithm is extensible and does not essentially change if your model increases the amount of parameters to the millions.

Backpropagation

Supervised Learning Procedure

1. Define Architecture

  • How many layers?
  • How many parameters?

2. Initialization

How to initialize parameters?

  • Do not set parameters to zero: then all parameters will get the same update, namely nothing since gradients are 0!
  • Random initialization scheme, e.g. with a normal distribution with mean 0 and unit standard deviation

More advanced schemas:

  • Glorot10/Xavier initialization
    • The output of a particular neuron increases with the number of inputs.
    • So you scale down the weight initialization using a normal with the square root of the number of inputs
  • He15
    • More suitable for different activation functions and deeper networks
    • Not explained yet in this lecture

See: neural_network_weight_initialization.md

3. Define train and validation set

  • Good habit to compute validation performance before training to estimate the performance of random parameters
    • Also sanity check: is the result what you expect with random initialization and classifications?

4. Training

Init:

  • Select subset of training samples, e.g. using mini-batches

Forward pass:

  • Compute predictions
  • Compute loss for each sample
  • Compute cost as average of losses

Backpropagation:

  • Compute all partial derivatives and propagate gradients backwards

In terms of learning rate, we usually pick the initial learning rate and then use a schema to decrease it over time.

  • Linear or exponential decrease
  • Decrease it every N epochs
  • Decrease when performance does not improve for N epochs

Evaluation

Check the learning curves! Where does the validation error start increasing?

It can happen that the validation loss can be lower than the training loss. Why?

  • This can be due to regularization during training (but which is not applied during validation)
  • You are in fact comparing two different models. The training loss is an average loss that is computed before the model is applied on the validation set.
  • The validation may by chance just be easier to classify

So a lower validation loss may be an indication you are doing something wrong, but it's not necessarily a problem.

You can also plot the loss per mini-batch. Then you'll see more noise, but in the end we care about the general trend.

Save the network parameters of the best model.

Sanity checks

  • Run your intialized but untrained network on t he validation set
    • If your validation set is balanced, you know the expected accuracy
  • Train and validate on a small training set
    • You should get loss $\approx$ 0 and accuracy $\approx$ 1
    • Otherwise you may have a bug in your network

Useful tricks (borderline must do's)

  • Shuffle your dataset
  • Also balance classes in your mini-batches
  • If you train on accuracy, make sure your validation set is balanced