# Model Selection and Overfitting

# Model Selection

In neural networks, there exists several free parameters

- Learning rate
- Batch size
- Number of layers
- Number of neurons
- Etc

Every set of parameters of the network leads to a specific model

How do we determine the optimum parameters or model for a given regression/classification problem?

# Performance Estimates

How do we measure the performance of networks? Some metrics include

1. Mean-square/Root-mean-square errors for regression

   $$
   \begin{aligned}
       MSE &= \frac{1}{P} \sum_{p = 1}^{P} \sum_{k = 1}^{K} (d_{pk} - y_{pk})^2 \\

       RMSE &= \sqrt{\frac{1}{P} \sum_{p = 1}^{P} \sum_{k = 1}^{K} (d_{pk} - y_{pk})^2}
   \end{aligned}
   $$

2. Classification error of a classifier

   $$
       E = \sum_{p = 1}^{P} 1(d_p \neq y_p)
   $$

where $d_p$ is the target, and $y_p$ is the predicted output of pattern $p$. $1(.)$ is the indicator function

# True Error vs Apparent Error

**Apparent error** (training error): The error on the training data. What the learning algorithm tries to optimise

**True error**: The error that will be obtained in use (i.e. over the whole sample space). What we want to optimise, but unkonwn

However, the apparent error is not always a good estimate fo the true error. It is just an optimistic measure of it

**Test error** (out of sample error): An estimate of the true error obtained by testing the network on some independent data

Generally, a larger test set helps provide a greater confidence on the accuracy of the estimate

## Estimation of True Error

Intuition: Choose the model with the best fit to the data

Meaning: Choose the model that provides the lowest error rate on teh entire sample population. Of course, that error rate is the true error rate

- However, to choose a model, we must first know how to estiamte the error of a model
- The entire sample population is often unavailable and only example data is available

## Validation

In real applications, we only have a finite set of examples

Validation is the approach to use the entire example data avialable to build the model and estimate the error rate. The validation uses a part of the data to select the model, which is known as the validation test

Validation attempts to solve fundamental problems encountered

- The model tends to overfit the training data. It is not uncommon to have 100% correct classification on training data
- There is no way of knowing how well the model performs on unseen data
- The error rate estimate is usually overly optimistic (usually lower than the true error rate). We need an unbiased estimate

## Validation Methods

An effective approach is to split the entire data into subsets (Training/Validation/Test) datasets

Some validation methods

- The holdout (1/3 - 2/3 rule for test and train partitions)
- Re-sampling methods
  - Random subsampling
  - K-fold cross validation
  - Leave one out cross validation
- Three-way data splits (train-validation-test partitions)

### Holdout Method

Split the entire dataset into 2 sets

1. Training set: Used to train the classifier
2. Testing set: Used to estimate the error rate of trained classifier on unseen data samples

The holdout method has 2 basic drawbacks

- By setting some samples for testing, the training dataset becomes smaller
- Use of a single train-and-test experiment could lead to misleading estimates if an unfortunate split happens (training data may not cover the space of testing data)

### Random Sampling Methods

Limitations of holdout can be overcome with a family of resampling methods at the expense of more computations

- Random subsampling
- K-Fold cross validation
- Leave one out (LOO) cross-validation

### K-Data Splits Random Subsampling

Random subsampling performs $K$ data splits of the dataset for training and testing

Each split randomly selects a number of samples. For each data split, we retrain the classifier from scratch with the training data. Let the error estiamte obtained for the $i$-th split be $e_i$

The average test error is

$$
E = \frac{1}{K} \sum_{i = 1}^{K} e_i
$$

We choose the model with the lowest average test error

### K-Fold Cross-Validation

Create a $K$-fold partition of the dataset

- For each of the $K$ experiments, use $K - 1$ folds for training, and the remaining one-fold for testing

Similarly, the corss-validation error is the average of the error estimate for each of the experiments

$$
E = \frac{1}{K} \sum_{i = 1}^{K} e_i
$$

$K$-fold cross validation is similar to random subsampling. The advantage of $K$-fold cross validation is that all examples in the dataset are eventually used for both training and testing

### Leave-One-Out (LOO) Cross-Validation

LOO is the degenerate case of $K$-fold cross validation, where $K$ is chosen as the total number of examples

- For a dataset with $N$ examples, perform $N$ experiments (i.e. $N = K$)
- For each experiment, use $N - 1$ examples for training and the remaining one example for testing

The LOO CV error is given by the average CV error over all folds

$$
E = \frac{1}{K} \sum_{i = 1}^{K} e_i
$$

### Three-Way Data Splits Method

If model selection and true error estimates are to be computed simulatneously, the data needs to be divided into 3 disjoint sets

1. Training set: Examples used for learning to fit the parameters of several possible classifiers. For DNN, we would use teh training set to find the optimal weights with gradient descent
2. Validation set: Examples to determine the error $J_m$ of different models $m$, using the validation set. The optimal model $m^*$ is given by

   $$
       m^* = \argmin_m J_m
   $$

3. Training + Validation set: Combine examples used to retrain/redesign model $m^*$, and find the new optimal weights and biases
4. Test set: Examples used only to assess the performance of a trained model $m^*$. We use the test data to estimate the error rate after we have trained the final model with train + validation data

Why separate test and validaiton sets?

- Error rate estimate of the final model on the validation data will be biased (smaller than true error rate) since the validation set is also used to select in the process of final model selection
- After assessing the final model, an independent test set is required to estimate the performance of the final model

## Model Complexity

Complex models: Models with many adjustable weights and biases will

- More likely be able to solve the required task
- More likely memorise the training data without solving the task (overfitting)

Simple models: The simpler the model, the more likely it is to generalise over the entire sample space. However, this model may not learn the problem well

The fundamental trade-off

- Too simple: Cannot do the task because not enough parameters to learn (underfitting)
- Too complex: Cannot generalise from small and noisy datasets well (overfitting)

### Overfitting

The network learns to respond correctly to the training inputs by remembering them too much, but is unable to generalise to produce correct outputs to novel inputs

Overfitting happens when the amount of training data is inadequate in comparison to the number of network parameters to learn

Overfitting occurs when the weights and biases become too large, and are fine-tuned to remember the training patterns too much. Even if the model is correct, too much training can cause overfitting

#### Methods to Overcome Overfitting

1. Early stopping
2. Regularisation of weights
3. Dropouts

Early stopping

- Training of network is stopped when validation error starts increasing.
- Early stopping can be used in test/validation by stopping when the validation error is minimum

Regularisation of weights

- During overfitting, some weights attain very large values to reduce training error, jeopardising its ability to generalise.
- To avoid this, a penalty term (regularisation term) is added to teh cost function

For a network with weights $\bold{W} = \{ w_{ij} \}$ and bias $\bold{b}$, the penalised (or regularised) cost function $J_1(\bold{W}, \bold{b})$ is defined as

$$
J_1 = J = \beta_1 \sum_{i, j} |w_{ij}| + \beta_2 \sum_{i, j} (w_{ij})^2
$$

- $J(\bold{W}, \bold{b})$ is the standard cost function (i.e. MSE or cross-entropy)
- $\sum_{i, j} |w_{ij}|$ is the $L_1$ norm
- $\sum_{i, j} (w_{ij})^2$ is the $L_2$ norm
- $\beta_1$ and $\beta_2$ are the $L_1$ and $L_2$ regularisation (penalty) constants. These penalties discourage weights from attaining large values

$L_2$ regularisation of weights

- Regularisation is usually not applied on bias terms. $L_2$ regularisation is most popular on weights
  $$
      J_1 = J + \beta_2 \sum_{i, j} (w_{ij})^2
  $$
- The gradient of the regularised cost w.r.t. weights:

  $$
      \nabla_{\bold{W}} J_1 = \nabla_\bold{W} J + \beta_2 \frac{\partial \sum_{i, j} w_{ij}^2}{\partial \bold{W}}
  $$

- We can easily calculate $\frac{\partial \sum_{i, j} w_{ij}^2}{\partial \bold{W}}$

  $$
      \begin{aligned}
      \sum_{i, j} w_{ij}^2 &= w_{11}^2 + \cdots + w_{nK}^2 \\
      \frac{\partial \sum_{i, j} w_{ij}^2}{\partial \bold{W}} &= \begin{pmatrix}
          \frac{\partial \sum(w_{ij})^2}{\partial w_{11}} & \frac{\partial \sum(w_{ij})^2}{\partial w_{12}} & \cdots & \frac{\partial \sum(w_{ij})^2}{\partial w_{1K}} \\
          \frac{\partial \sum(w_{ij})^2}{\partial w_{21}} & \frac{\partial \sum(w_{ij})^2}{\partial w_{22}} & \cdots & \frac{\partial \sum(w_{ij})^2}{\partial w_{2K}} \\
          \vdots & \vdots & \ddots & \vdots \\
          \frac{\partial \sum(w_{ij})^2}{\partial w_{n1}} & \frac{\partial \sum(w_{ij})^2}{\partial w_{n2}} & \cdots & \frac{\partial \sum(w_{ij})^2}{\partial w_{nK}} \\
      \end{pmatrix} = 2\bold{W}
      \end{aligned}
  $$

- Now, we can substitute

  $$
      \nabla_{\bold{W}} J_1 = \nabla_\bold{W} J + 2 \beta_2 \bold{W}
  $$

- For gradient descent, we can use the following

  $$
  \begin{aligned}
      \bold{W} \leftarrow \bold{W} - \alpha \nabla_\bold{W} J_1 \\
      \bold{W} \leftarrow \bold{W} - \alpha (\nabla_\bold{W} J + \beta \bold{W})
  \end{aligned}
  $$

  - $\beta = 2 \beta_2$
  - $\beta$ is known as the weight decay parameter

### Dropout

Deep neural networks with large numbers of parameters are powerful learning machines. Overfitting can be avoided by training only a fraction of weights in each iteration. The key idea of dropout is to randomly drop neurons (along with their connections) from the network during training. This prevents neurons from co-adapting, and thereby reduces overfitting

The units (neurons) are present with probability $p$, and presented to the next layer with weights $\bold{W}$ to the next layer at training time.

However in testing, the weights are always present, and presented to the network with weights multiplied by probability $p$ (dropout rate). The output at the test time is same as the expected output during training time

Applying dropout results in a "thinned" network, that consists only of neurons that survived, which minimises redundancy in the network


 Model Selection and Overfitting

# Recurrent Neural Networks (RNN)

Designed to process sequential information

- Next data point is dependent on current data point
- E.g. NLP, genomic sequences etc.

RNN attempts to capture dependencies among data points in the sequence

![](https://media.geeksforgeeks.org/wp-content/uploads/20230518134831/What-is-Recurrent-Neural-Network.webp)

- $h$: Hidden state, a memory that captures information about what has been processed so far

# Types of RNNs

![](https://www.researchgate.net/publication/344570387/figure/fig3/AS:960025010917394@1605899207869/Elman-left-side-picture-and-Jordan-network-right-side-picture-models-25.png)

- Elman (Vanilla RNN): Current hidden state depends on **previous hidden state**
- Jordan: Current hidden state depends on **previous output**

# RNN with Hidden Recurrence

![](RNN-Elman.png)

Assume the RNN takes in inputs $\bold{x} \in \mathbb{R}^n$, has a hidden dimension $\bold{h} \in \mathbb{R}^d$, and has output $\bold{y} \in \mathbb{R}^m$

The parameters of an RNN:

- $\bold{U} \in \mathbb{R}^{n \times d}$: Weight vector that transforms raw inputs to hidden layer
- $\bold{W} \in \mathbb{R}^{d \times d}$: Recurrent weight vector connecting previous hidden layer output to hidden input
- $\bold{b} \in \mathbb{R}^{d}$: Bias connected from previous hidden layer to hidden layer
- $\bold{V} \in \mathbb{R}^{d \times m}$: Weight vector of output layer
- $\bold{c} \in \mathbb{R}^{m}$: Bias connected to output layer
- $\phi$: The $\tanh$ hidden-layer activation function
- $\sigma$: The linear/softmax output-layer activation function

## Single Inputs

Let $\bold{x}(t), \bold{y}(t), \bold{h}(t)$ be the input, output and hidden output of the network at time $t$. Note that $\bold{h}(0) = \hat{0}$

Activations of the Elman-type RNN with 1 hidden layer is given by:

$$
\begin{aligned}
    \bold{h}(t) &= \phi(\bold{U}^T \bold{x}(t) + \bold{W}^T \bold{h}(t - 1) + \bold{b}) \\
    \bold{y}(t) &= \sigma(\bold{V}^T \bold{h}(t) + \bold{c})
\end{aligned}
$$

Note that $\sigma$ is a softmax function for classification, and a linear function for regression

## Batch Inputs

Given $P$ patterns $\{ \bold{x}_p \}_{p=1}^{P}$ where $\bold{x}_p = (\bold{x}_p(t))_{t=1}^{T}$,

$$
\bold{X}(t) = \begin{pmatrix}
    \bold{x}_1(t)^T \\ \vdots \\ \bold{x}_P(t)^T
\end{pmatrix}
$$

Let $\bold{X}(t), \bold{Y}(t), \bold{H}(t)$ be the batch input, output and hidden output of the network at time $t$. Note that $\bold{H}(0) = \hat{0}$

Activation of the Elman type RNN is given by

$$
\begin{aligned}
    \bold{H}(t) &= \phi(\bold{X}(t) \bold{U} + \bold{H}(t - 1) \bold{W} + \bold{B}) \\
    \bold{Y}(t) &= \sigma(\bold{H}(t) \bold{V} + \bold{C})
\end{aligned}
$$

# RNN with Top-Down Recurrence (Jordan)

![](RNN-Jordan.png)

The hidden layer takes the previous output $\bold{y}(t-1)$ (instead of the previous hidden-layer output). Note that the dimensions of $\bold{W} \in \mathbb{R}^{m \times d}$ instead

## Single Input

Let $\bold{x}(t), \bold{y}(t), \bold{h}(t)$ be the input, output and hidden output of the network at time $t$. Note that $\bold{h}(0) = \hat{0}$

$$
\begin{aligned}
    \bold{h}(t) &= \phi(\bold{U}^T \bold{x}(t) + \bold{W}^T \bold{y}(t - 1) + \bold{b}) \\
    \bold{y}(t) &= \sigma(\bold{V}^T \bold{h}(t) + \bold{c})
\end{aligned}
$$

## Batch Input

Let $\bold{X}(t), \bold{Y}(t), \bold{H}(t)$ be the batch input, output and hidden output of the network at time $t$. Note that $\bold{H}(0) = \hat{0}$

$$
\begin{aligned}
    \bold{H}(t) &= \phi(\bold{X}(t) \bold{U} + \bold{Y}(t - 1) \bold{W} + \bold{B}) \\
    \bold{Y}(t) &= \sigma(\bold{H}(t) \bold{V} + \bold{C})
\end{aligned}
$$

# Backpropagation Through Time (BPTT)

Consider the vanilla-RNN with hidden recurrence. Forward propagation equations:

$$
\begin{aligned}
    \bold{h}(t) &= \phi(\bold{U}^T \bold{x}(t) + \bold{W}^T \bold{h}(t - 1) + \bold{b}) = f(\bold{x}(t), \bold{h}(t-1), \bold{W}) \\
    \bold{u}(t) &= \sigma(\bold{V}^T \bold{h}(t) + \bold{c}) \\
    \bold{y}(t) &= \begin{cases}
        \text{softmax}(\bold{u}(t)) & \text{ Classification} \\
        \bold{u}(t) & \text{ Linear}
    \end{cases} \\
    &= g(\bold{h}(t), \bold{V})
\end{aligned}
$$

We have learnable parameters

- $\bold{U}$: Weights from input to hidden
- $\bold{W}$: Weights from previous hidden to hidden
- $\bold{V}$: Weights from hidden to output
- $\bold{b}$: Bias from previous hidden to hidden
- $\bold{c}$: Bias from hidden to output

For backpropagation, the gradients propagate backwards, starting from the end of the sequence, in 2 directions

1. Top down (from output down to input)
2. Reverse sequence direction (from $t = T$ to $t = 0$)

Consider some loss function $J(t) = l(\bold{y}(t), \hat{\bold{y}}(t))$ for inputs at a specific timestep $t$ (Cross-entropy for classification, MSE for linear regression)

- $\bold{y}(t)$ is our target at timestep $t$
- $\hat{\bold{y}}(t)$ is our prediction at timestep $t$

We take the average of the gradients of the loss function through time

$$
\begin{aligned}
    \frac{\partial J}{\partial \bold{W}} &= \frac{1}{T} \sum_{t=1}^{T} \frac{\partial J(t)}{\partial \bold{W}} \\
    &= \frac{1}{T} \sum_{t=1}^{T} \frac{\partial J(t)}{\partial \bold{u}(t)} \frac{\partial \bold{u}(t)}{\partial \bold{h}(t)} \frac{\partial \bold{h}(t)}{\partial \bold{W}}
\end{aligned}
$$

$\frac{\partial J(t)}{\partial \bold{u}(t)}$ and $\frac{\partial \bold{u}(t)}{\partial \bold{h}(t)}$ are easy to compute, but $\frac{\partial \bold{h}(t)}{\partial \bold{W}}$ has to be computed recurrently, since $\bold{h}(t)$ is a recurrent term. $\bold{h}(t)$ depends on both $\bold{h}(t - 1)$ and $\bold{W}$. Thus, evaluating the total derivate of $\bold{h}(t)$ using the chain rule:

$$
\frac{\partial \bold{h}(t)}{\partial \bold{W}} = \frac{\partial f(\bold{x}(t), \bold{h}(t-1), \bold{W})}{\partial \bold{W}} + \frac{\partial f(\bold{x}(t), \bold{h}(t-1), \bold{W})}{\partial \bold{h}(t-1)} \frac{\partial \bold{h}(t - 1)}{\partial \bold{W}}
$$

To find the above gradient, assume we have 3 sequences $\{a_t\}, \{b_t\}, \{c_t\}$ satisfying $a_0 = 0$ and $a_t = b_t + c_t a_{t-1}$ for $t = 1, 2, ...$. Then for $t \geq 1$, we can prove that

$$
    a_t = b_t + \sum_{i=1}^{t - 1} \left( \prod_{j=i+1}^{t} c_j \right) b_i
$$

By substituting $a_t, b_t, c_t$ according to

$$
\begin{aligned}
    a_t &= \frac{\partial \bold{h}(t)}{\partial \bold{W}} \\
    b_t &= \frac{\partial f(\bold{x}(t), \bold{h}(t-1), \bold{W})}{\partial \bold{W}} \\
    c_t &= \frac{\partial f(\bold{x}(t), \bold{h}(t-1), \bold{W})}{\partial \bold{h}(t-1)}
\end{aligned}
$$

the gradient computation satisfies $a_t = b_t + c_t a_{t-1}$. Hence, we have a closed-form solution

$$
\frac{\partial \bold{h}(t)}{\partial \bold{W}} = \frac{\partial f(\bold{x}(t), \bold{h}(t-1), \bold{W})}{\partial \bold{W}} + \sum_{i=1}^{t-1} \left( \prod_{j = i + 1}^{t} \frac{\partial f(\bold{x}(j), \bold{h}(j - 1), \bold{W})}{\partial \bold{h}(j - 1)} \right) \frac{\partial f(\bold{x}(i), \bold{h}(i - 1), \bold{W})}{\partial \bold{W}}
$$

Runtime is $O(T)$, where $T$ is the length of the input sequence, and cannot be reduced by parallelisation due to its sequential nature.

Also note,

![](rnn-backprop.png)

$$
\begin{aligned}
\nabla_{\bold{h}(t)} J &= \left( \frac{\partial \bold{h}(t + 1)}{\partial \bold{h}(t)} \right)^T \nabla_{\bold{h}(t + 1)} J + \left( \frac{\partial \bold{u}(t)}{\partial \bold{h}(t)} \right)^T \nabla_{\bold{u}(t)} J \\
&= \bold{W} \text{diag}(1 - \bold{h}^2(t + 1)) \nabla_{\bold{h}(t + 1)} J + \bold{V} \nabla_{\bold{u}(t)} J
\end{aligned}
$$

1. The first term is the gradient that is backpropagated due to the future hidden state. $\frac{d}{dx} \tanh(x) = 1 - \tanh^2(x)$. $\bold{W}$ is the weights in the current hidden layer, and $\nabla_{\bold{h}(t + 1)} J$ is the gradient from the future hidden layer
2. The second term is the gradient that is backpropagated due to the output

# Long Short-Term Memory (LSTM)

RNNs have difficulties in learning long range dependencies due to exploding/vanishing gradients

- During gradient back-propagation learning of RNN, gradients are multiplied by a large/small number many times, which could cause the gradient to explode/vanish
- Exploding gradients cause learning to diverge
  - Can be solved by **gradient clipping**
- Vanishing gradients cause learning to stop

## Gradient Clipping

Commonly, we use 2 methods:

1. Clip gradient $g$ if it exceeds a threshold
   $$
       \text{If } \lVert g \rVert > v \implies \lVert g \rVert \leftarrow v
   $$
2. Normalise the gradient when it exceeds a threshold
   $$
       \text{If } \lVert g \rVert > v \implies \lVert g \rVert \leftarrow \frac{g}{\lVert g \rVert} v
   $$

For vanishing gradients, the solution is a Gated RNN

- Long short-term memory (LSTM)
- Gated Recurrent Units (GRU)

## LSTM Units

![](lstm.png)

The key of LSTM is "state"

- A persistent module called the cell state $\bold{c}(t)$
- State is a representation of past history

The LSTM is made up of 3 gates

1. Forget gate
2. Input gate
3. Output gate

### Forget Gate

Given the current input, determine how much of the previous state the cell should remember

$$
\bold{f}(t) = \sigma \left( \bold{U}_f^T \bold{x}(t) + \bold{W}_f^T \bold{h}(t - 1) + \bold{b}_f \right)
$$

- For e.g., we want to predict the next word based on all the previous words. Cell state may include gender of present subject, so that proper nouns can be used. When we see a new subject, we want to forget the old subject

### Input gate

Allow incoming signal to alter the state of the memory cell, or block the incoming signal. Decides what new information to store in the cell stage. Input gate consists of 2 parts:

1. Sigmoid input gate, decides which values to update
2. $\tanh$ layer, creates a vector of new candidate values $\tilde{\bold{c}}(t)$ that could be added to the state

$$
\begin{aligned}
    \bold{i}(t) &= \sigma \left( \bold{U}_i^T \bold{x}(t) + \bold{W}_i^T \bold{h}(t - 1) + \bold{b}_i \right) \\
    \tilde{\bold{c}}(t) &= \phi \left( \bold{U}_c^T \bold{x}(t) + \bold{W}_c^T \bold{h}(t - 1) + \bold{b}_c \right)
\end{aligned}
$$

- E.g., for language modelling, we would like to add the gender of the new subject to the cell state to replace the old one we are forgetting

Now our overall cell state:

$$
\bold{c}(t) = \tilde{\bold{c}}(t) \odot \bold{i}(t) + \bold{c}(t - 1) \odot \bold{f}(t)
$$

- $\tilde{\bold{c}}(t)$: Our new candidate vector to add to the cell state
- $\bold{i}(t)$: Which values to update in the cell state
- $\bold{f}(t)$: How much of our old cell state to forget
- Note that $\odot$ represents element-wise multiplication

### Output Gate

Output gate allows the state of the memory cell to have an effect on other neurons, or prevent it

$$
\begin{aligned}
    \bold{o}(t) &= \sigma \left( \bold{U}_o^T \bold{x}(t) + \bold{W}_o^T \bold{h}(t - 1) + \bold{b}_o \right) \\
    \bold{h}(t) &= \phi(\bold{c}(t)) \odot \bold{o}(t)
\end{aligned}
$$

### Overall LSTM

$$
\begin{aligned}
    \bold{i}(t) &= \sigma \left( \bold{U}_i^T \bold{x}(t) + \bold{W}_i^T \bold{h}(t - 1) + \bold{b}_i \right) \\
    \bold{f}(t) &= \sigma \left( \bold{U}_f^T \bold{x}(t) + \bold{W}_f^T \bold{h}(t - 1) + \bold{b}_f \right) \\
    \bold{o}(t) &= \sigma \left( \bold{U}_o^T \bold{x}(t) + \bold{W}_o^T \bold{h}(t - 1) + \bold{b}_o \right) \\ \\

    \tilde{\bold{c}}(t) &= \phi \left( \bold{U}_c^T \bold{x}(t) + \bold{W}_c^T \bold{h}(t - 1) + \bold{b}_c \right) \\
    \bold{c}(t) &= \tilde{\bold{c}}(t) \odot \bold{i}(t) + \bold{c}(t - 1) \odot \bold{f}(t) \\
    \bold{h}(t) &= \phi(\bold{c}(t)) \odot \bold{o}(t)
\end{aligned}
$$

- Most important component: State unit $c_i(t)$ (for time step $t$, cell $i$), which has a linear self-loop
- Self-loop weight controlled by the forget gate unit, which sets this weight to a value between 0 and 1 via a sigmoid
- This self-loop can produce paths where the gradient can flow for long durations, and make the weight on this self-loop conditioned on the context, rather than fixed

### Training LSTM Networks

![](train-lstm.png)

- We have 3 matrices for each of the gates, for a total of 12 matrices


 Recurrent Neural Networks (RNN)

# Attention

- Make predictions by selectively attending to a given set of data
- Amount of attention is quantified by learned weights

$$
\text{Attention} = \bold{WV}
$$

# Transformers

![](https://sebastianraschka.com/images/blog/2023/self-attention-from-scratch/transformer.png)

- Uses attention to model long range dependencies in data, a seq2seq model
- Model of choice in NLP
- Built on self-attention mechanisms, without using sequence-aligned recurrent architecture
  - Self-attention is a type of attention mechanism where the model makes predictions for one part of a data sample, using other parts of the observation about the same sample

Transformer architecture:
![](https://miro.medium.com/v2/resize:fit:1400/1*V2435M1u0tiSOz4nRBfl4g.png)

- Encoding: Stack of encoders
- Decoding: Stack of decoders, same number of encoders and decoders

Each encoder is broken down into 2 sublayers:

1. Self-attention layer
2. Feed forward neural network

Each decoder has 3 sublayers

1. Self-attention layer
2. Encoder-decoder attention
3. Feed-forward neural network

![](https://jalammar.github.io/images/t/Transformer_decoder.png)

## Self-Attention

![](https://production-media.paperswithcode.com/methods/35184258-10f5-4cd0-8de3-bd9bc8f88dc3.png)

Self-attention is known as scaled dot-product attention, and it is defined as:

$$
\text{Attention}(\bold{Q}, \bold{K}, \bold{V}) = \text{Softmax}\left( \frac{\bold{Q}\bold{K}^T}{\sqrt{d_k}} \right) \bold{V}
$$

- Output of self-attention is a weighted sum of the values, where the weights assigned to each value is determined by the dot product between the query and the keys

1. For each of the encoder's input vectors, create 3 vectors: Query $q_i$, key $k_i$, and value $v_i$

   $$
   \begin{aligned}
       \bold{X} &= \begin{pmatrix}
           x_1 \\ \vdots \\ x_t
       \end{pmatrix} \\
       \bold{Q} &= \bold{X} \bold{W}^Q \\
       \bold{K} &= \bold{X} \bold{W}^K \\
       \bold{V} &= \bold{X} \bold{W}^V \\
   \end{aligned}
   $$

2. Calculate the score

   $$
       \bold{Q} \bold{K}^T
   $$

   - Determines how much focus to place on other parts of the input sentence, given a specific word

3. Divide by square root of dimension of the keys $d_k$ (the last dimension of $\bold{W}^K$). This allows more stable gradients

   $$
       \frac{\bold{Q}\bold{K}^T}{\sqrt{d_k}}
   $$

4. Softmax to normalize

   $$
       \text{Softmax}\left( \frac{\bold{Q}\bold{K}^T}{\sqrt{d_k}} \right)
   $$

5. Multiply each vector by softmax score

   $$
       \text{Softmax}\left( \frac{\bold{Q}\bold{K}^T}{\sqrt{d_k}} \right) \bold{V}
   $$

6. Sum up weighted value vectors to get the output for the self-attention layer at this position

Example:

- Assume we have 2 sequences $(1, 2, 3), (4, 5, 6)$
- We have

$$
\bold{W}^Q = \begin{pmatrix}
    0.01 & 0.03 \\ 0.02 & 0.02 \\ 0.03 & 0.01
\end{pmatrix} \
\bold{W}^K = \begin{pmatrix}
    0.05 & 0.05 \\ 0.06 & 0.05 \\ 0.07 & 0.05
\end{pmatrix} \
\bold{W}^V = \begin{pmatrix}
    0.02 & 0.02 \\ 0.01 & 0.02 \\ 0.01 & 0.01
\end{pmatrix}
$$

Compute the output of the scaled-dot product attention

Note, $\bold{X} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}$

1. Find $\bold{Q}, \bold{K}, \bold{V}$:

   $$
   \begin{aligned}
       \bold{Q} &= \bold{X} \bold{W}^Q = \begin{pmatrix}
           0.14 & 0.10 \\ 0.32 & 0.28
       \end{pmatrix} \\
       \bold{K} &= \bold{X} \bold{W}^K = \begin{pmatrix}
           0.38 & 0.30 \\ 0.92 & 0.75
       \end{pmatrix} \\
       \bold{V} &= \bold{X} \bold{W}^V = \begin{pmatrix}
           0.07 & 0.09 \\ 0.19 & 0.24
       \end{pmatrix}
   \end{aligned}
   $$

2. Find $\text{Attention}(\bold{Q}, \bold{K}, \bold{V})$

   $$
   \begin{aligned}
       \text{Softmax}\left( \frac{\bold{Q}\bold{K}^T}{\sqrt{d_k}} \right) \bold{V} &= \text{Softmax} \left( \frac{\begin{pmatrix}
           0.14 & 0.10 \\ 0.32 & 0.28
       \end{pmatrix} \begin{pmatrix}
           0.38 & 0.30 \\ 0.92 & 0.75
       \end{pmatrix}^T }{\sqrt{2}}\right) \begin{pmatrix}
           0.07 & 0.09 \\ 0.19 & 0.24
       \end{pmatrix} \\
       &= \text{Softmax} \left( \begin{pmatrix}
           0.0588 & 0.1441 \\ 0.1454 & 0.3566
       \end{pmatrix}\right) \begin{pmatrix}
           0.07 & 0.09 \\ 0.19 & 0.24
       \end{pmatrix} \\
       &= \begin{pmatrix}
           0.4784 & 0.5213 \\ 0.4474 & 0.5526
       \end{pmatrix} \begin{pmatrix}
           0.07 & 0.09 \\ 0.19 & 0.24
       \end{pmatrix} \\
       &= \begin{pmatrix}
           0.1326 & 0.1682 \\ 0.1363 & 0.1729
       \end{pmatrix}
   \end{aligned}
   $$

   - Row-wise softmax
   - Note that $\sqrt{d_k} = 2$ ($\bold{W}^K \in \mathbb{R}^{2 \times 2}$)
   - Consider the top left element before softmaxing

     $$
         \frac{e^{z_i}}{\sum_j e^{z_j}} = \frac{e^{0.0588}}{e^{0.0588} + e^{0.1441}} = 0.4787
     $$

## Multi-Head Self-Attention

![](https://production-media.paperswithcode.com/methods/Screen_Shot_2020-07-08_at_12.17.05_AM_st5S0XV.png)

- Run scaled dot product attention multiple times in parallel
- Due to different linear mappings, each head is presented with different versions of keys, queries and values
- Independent attention outputs are simply concatenated and linearly transformed into the expected dimensions
- Allows the model to jointly attend to information from different representation subspaces at different positions
  - E.g. **Deep learning** is a part of **machine learning methods** based on artificial neural networks with **representation learning**
  - Given "representation learning", first head atttends to "Deep learning", second head attends to "machine learning methods"

## Positional Encoding

- Self-attention layers work on a set of vectors, and does not know the order of the vectors it is processing
- To add positional information, we add a positional encoding to each vector
  - Embedding + Positional encoding = Embedding with time signal
- Positional encoding has the same dimension as input embedding

Example of positional encoding:

$$
\begin{aligned}
    PE_{(pos, 2i)} &= \sin (pos / 10000^{2i/d_{model}}) \\
    PE_{(pos, 2i + 1)} &= \cos (pos / 10000^{2i/d_{model}})
\end{aligned}
$$

- Use $\sin$ for even indices, $\cos$ for odd indices

E.g. given the following sinusoidal positional encoding, calculate the $PE(pos=1)$ fo the first 5 dimensions: [0, 1, 2, 3, 4], assume $d_{model} = 512$

Given $pos = 1$, $d_{model} = 512$:

- At dimension 0, $2i = 0 \implies i = 0 \implies PE_{(pos, 2i)} = PE_{(1, 0)} = \sin(1/10000^{0/512})$
- At dimension 1, $2i + 1 = 0 \implies i = 0 \implies PE_{(pos, 2i + 1)} = PE_{(1, 1)} = \cos(1/10000^{0/512})$
- At dimension 2, $2i = 2 \implies i = 1 \implies PE_{(pos, 2i)} = PE_{(1, 2)} = \sin(1/10000^{2/512})$
- At dimension 3, $2i + 1 = 3 \implies i = 1 \implies PE_{(pos, 2i + 1)} = PE_{(1, 3)} = \cos(1/10000^{2/512})$
- At dimension 4, $2i = 4 \implies i = 2 \implies PE_{(pos, 2i)} = PE_{(1, 4)} = \sin(1/10000^{4/512})$

## Transformer Encoder

![](https://jalammar.github.io/images/t/transformer_resideual_layer_norm_2.png)

- Each encoder layer has a multi-head self-attention layer, and a simple position-wise fully connected FFN

$$
\text{FFN}(x) = \max(0, xW_1 + b_1) W_2 + b_2
$$

- Linear transformations are same across different positions, they use different parameters from layer to layer
- Each sub-layer adopts a residual connection and a layer normalisation

![](https://production-media.paperswithcode.com/methods/Screen_Shot_2020-05-19_at_4.24.42_PM.png)
Layer Normalisation

- Pixels along shaded are normalized by the same mean/variance, computed by aggregating the values of these pixels
- Batch normalisation is found to be unstable in transformers
- Layer normalisation works well with RNN, and is now being used in transformers

Outputs of (final) encoder go to the sub-layers of the decoders as well

![](https://jalammar.github.io/images/t/transformer_resideual_layer_norm_3.png)

## Transformer Decoder

- Encoder starts by processing input sequence
- Output of last (top) decoder is then transformed into a set of attention vectors $\bold{K}$ and $\bold{V}$
- These are to be used by each decoder in its encoder-decoder attention layer, which helps the decoder focus on appropriate places in the input sequence
- Output of each step is fed to the bottom decoder in the next time step
- Embed and add positional encoding to those decoder inputs. Process those inputs
- Repeat process until a special token (`END`) is reached, indicating the transformer decoder has completed its output
  - In the decoder, the self-attention layer is only allowed to attend to earlier positions in the output sequence
  - This is done by masking future positions (set to -inf) before the softmax step in the self-attention calculation

# Vision Transformer

![](https://miro.medium.com/v2/resize:fit:640/format:webp/0*97Y6wjHcHg5Th-lZ)

- Does not have decoder
- Reshape image $\bold{x} \in \mathbb{R}^{H \times W \times C}$ into a sequence of flattened 2D patches $\bold{x} \in \mathbb{R}^{N \times (P^2 \cdot C)}$
  - $(H, W)$ is the resolution of the original image
  - $C$ is the number of channels
  - $(P, P)$ is the resolution of each image patch
  - $N = HW/P^2$ is the number of resulting patches

For inference using ViT:

1. Prepend a learnable embedding $\bold{z}_0^0 = \bold{x}_{\text{class}}$ to the sequence of embedded patches

   $$
       \bold{z}_0 = [\bold{x}_{\text{class}}; \bold{x}_p^1 \bold{E}; \bold{x}_p^2 \bold{E}; \cdots ; \bold{x}_p^N \bold{E}] + \bold{E}_{\text{pos}}
   $$

   - Patch embedding: Linearly embed each of the patches to $D$ dimension with a trainable linear projection $\bold{E} \in \mathbb{R}^{(P^2 \cdot C) \times D}$
   - Add learnable position embeddings $\bold{E}_{\text{pos}} \in \mathbb{R}^{(N + 1) \times D}$ to retain positional information

2. Feed the resulting sequence of vectors $\bold{z}_0$ to a standard transformer encoder

   $$
   \begin{aligned}
       \bold{z}_0 &= [\bold{x}_{\text{class}}; \bold{x}_p^1 \bold{E}; \bold{x}_p^2 \bold{E}; \cdots ; \bold{x}_p^N \bold{E}] + \bold{E}_{\text{pos}} \\
       \bold{z}'_l &= \text{MSA}(\text{LN}(\bold{z}_{l - 1})) + \bold{z}_{l - 1} \\
       \bold{z}_l &= \text{MLP}(\text{LN}(\bold{z}'_l)) + \bold{z}'_l \\ \\

       \bold{y} &= \text{LN}(\bold{z}^0_L)
   \end{aligned}
   $$

   - $\bold{E} \in \mathbb{R}^{(P^2 \cdot C) \times D}$ is an embedding matrix (project image patch onto embedding)
   - $\bold{E}_{\text{pos}} \in \mathbb{R}^{(N + 1) \times D}$ is a positional embedding
   - $l = 1, ..., L$ is the layer's index (index of encoder inside full transformer encoder)
   - $\text{MSA}$ is multi-self-attention, and $\text{LN}$ is layer normalisation

## Inductive Bias

The inductive bias of a learning algorithm is the set of assumptions that the learner uses to predict outputs of given inputs that it has not yet encountered

- ViT has much less image-specific inductive bias than CNNs
- Inductive bias in CNN
  - Locality
  - 2-D neighborhood structure
  - Translation equivariance
- ViT
  - Only MLP layers are local and translationally equivariant. Self-attention layer is global
  - 2D neighborhood is used sparingly
    - Only at the beginning, where we cut image into patches
    - Learnable position embeddings (spatial relations) have to be learnt from scratch

## Performance of ViT

- ViT performs worse than CNN equivalent when trained on ImageNet (1M images) as it overfits
- ViT performs comparably to CNN on ImageNet-21K (14M images), and outperforms CNN on JFT (300M images)
- ViT overfits ImageNet task due to its lack of inbuilt knowledge about images


 Attention

# AutoEncoders

![](https://lilianweng.github.io/posts/2018-08-12-vae/autoencoder-architecture.png)

Autoencoders are an unsupervised method for learning feature vectors from raw data without any labels

- Features should extract useful information that we can use for downstream tasks

How to learn this feature transform from raw data?

- Use features to reconstruct the input data with a decoder

An autoencoder is a neural network trained to attempt to copy its input to its output

- Hidden layer describes a code that represents the output
- Consists of 2 parts: Encoder and Decoder

Given an input $\bold{x}$, the hidden-layer performs the encoding function $\bold{h} = \phi(\bold{x})$, and the decoder $\varphi$ produces the reconstruction $\bold{y} = \phi(\bold{h})$

$$
\begin{aligned}
    \bold{h} &= \phi(\bold{x}) \\
    \bold{y} &= \varphi(\bold{h})
\end{aligned}
$$

If the autoencoder succeeds, it should be able to copy its input to the output

$$
\bold{y} = \varphi(\phi(\bold{x})) = \bold{x}
$$

We can optionally constrain the weights in the encoder and the decoder

- Encoder weight matrix: $\bold{W}$
- Decoder weight matrix: $\bold{W}^T$

![](autoencoder.png)

Then the hidden and output layer activations can be written as:

$$
\begin{aligned}
    \bold{h} &= f(\bold{W}^T\bold{x} + \bold{b}) \\
    \bold{y} &= f(\bold{W}\bold{h} + \bold{c})
\end{aligned}
$$

# Training Autoencoders

The cost function for reconstruction can be measured in various ways depending on the appropriate distributional assumption on the inputs

Given a training set $\{\bold{x}_p\}_{p=1}^{P}$, we can use the MSE if the data is assumed to be continuous and Gaussian distributed

$$
J_{\text{MSE}} = \frac{1}{P} \sum_{p=1}^{P} \lVert \bold{y}_p - \bold{x}_p \rVert^2
$$

- $\bold{y}_p$: Output for input $\bold{x}_p$

If inputs are interpreted as bit-vectors, or vectors of bit-probabilities, we use the cross-entropy of reconstruction

$$
J_{\text{cross-entropy}} = -\sum_{p=1}^{P} \bold{x}_p \log \bold{y}_p + (1 - \bold{x}_p) \log (1 - \bold{y}_p)
$$

After choosing a cost function $J$, we can learn using gradient descent

$$
\begin{aligned}
    \bold{W} &\leftarrow \bold{W} - \alpha \nabla_\bold{W} J \\
    \bold{b} &\leftarrow \bold{b} - \alpha \nabla_\bold{b} J \\
    \bold{c} &\leftarrow \bold{c} - \alpha \nabla_\bold{c} J \\
\end{aligned}
$$

# Denoising Autoencoders (DAE)

![](https://pyimagesearch.com/wp-content/uploads/2020/02/keras_denoising_autoencoder_header.png)

DAEs receive corrupted data points as input, and is trained to predict the original uncorrupted data points as its output

- Force hidden layer to discover more robust features, and prevent it from simply learning the identity function

To train the DAE:

1. Input data is corrupted to mimic noise in the image: $\bold{x} \to \tilde{\bold{x}}$
2. Network is trained to produce uncorrupted data: $\bold{y} \to \bold{x}$

## Corrupting Inputs

Each input $x_i$ of the input data is added with additive or multiplicative noise

- Additive noise

  $$
      \tilde{x_i} = x_i + \epsilon
  $$

  where $\epsilon \sim \mathcal{N}(0, \sigma^2)$, and $\sigma$ is the standard deviation that determines the signal-to-noise ratio. Usually used for continuous data

- Multiplicative noise

  $$
      \tilde{x}_i = \epsilon x_i
  $$

  where $\epsilon \sim \text{Binomial}(p)$, and $p$ is the probability of ones, and $1-p$ is the probabilities of zeroes (noise). Usually used for binary data

# Undercomplete and Overcomplete Autoencoders

We have inputs $\bold{x} \in \mathbb{R}^n$, and hidden dimension $M$

- If $M < n$, it is an **undercomplete** autoencoder
- If $M > n$, it is an **overcomplete** autoencoder

## Undercomplete Autoencoders

In undercomplete autoencoders, hidden-layer has a lower dimension than the input layer

- Obtain a lower dimensional representation of the input signals
- Network reconstructs input signals from reduced-dimensional hidden representation
- Forces autoencoder to capture the most salient features

## Overcomplete Autoencoders

In overcomplete autoencoders, hidden-layer has a higher dimension than the input

- In order to learn useful information from overcomplete autoencoders, it is necessary to use constraints over its characteristics
- Even when hidden dimensions are large, one can still explore interesting structures of inputs by introducing other constraints such as "sparsity" of input data

# Regularising Autoencoders

Autoencoders fail to learn anything useful if the encoder and decoder are given too much capacity. Some constraints are requried to make them useful

- Deep autoencoders are only possible when some constraints are imposed on the cost function

Regularised autoencoders incorporate a penalty to the cost function to learn interesting features from the input

- With constraints, we can use larger model capacities (e.g. deeper autoencoders)

Regularised autoencoders add an appropriate penalty function $\Omega$ to the cost function

$$
J_1 = J + \beta \Omega(h)
$$

- $\beta$ is the penalty/regularisation parameter. Penalty is usually imposed on the hidden activations
- A regularised loss function encourages the model to have other properties besides the ability to copy its input to its output

# Sparse Autoencoders (SAE)

SAE is an autoencoder whose training criterion involves the sparsity penalty $\Omega_s$ at the hidden layer

$$
J_1 = J + \beta \Omega_s (h)
$$

- Sparsity penalty term makes the features learnt by the hidden-layer to be sparse
- With sparsity constraint, one would constrain the neurons at the hidden layer to be inactive for most of the time
- A neuron is "active" when its output is close to 1, and "inactive" when it is close to 0

## Sparsity Constraint

For a set $\{x_p\}_{p=1}^{P}$ of input patterns, the average activation $\rho_j$ of neuron $j$ at the hidden-layer is given by

$$
\rho_j = \frac{1}{P} \sum_{p=1}^{P} h_{pj} = \frac{1}{P} \sum_{p=1}^{P} f(\bold{x}_p^T \bold{w}_j + b_j)
$$

- $h_{pj}$ is the activation of the hidden neuron $j$ for the $p$-th pattern, and $\bold{w}_j$ and $b_j$ are the weights and biases for the hidden neuron $j$
- We would like to enforce the constraint: $\rho_j = \rho$ such that the sparsity parameter $\rho$ is set to a small value close to zero (e.g. 0.05)
- Most of the time, hidden neuron activations are maintained at $\rho$ on average. By choosing a smaller value for $\rho$, the neurons are activated selectively to patterns and thereby learn sparse features

To achieve sparse activations in the hidden layer, we use the Kullback-Leibler (KL) divergence as the sparsity constraint

$$
D(\bold{h}) = \sum_{j=1}^{M} \rho \log \frac{\rho}{\rho_j} + (1 - \rho) \log \frac{1 - \rho}{1 - \rho_j}
$$

- $M$ is the number of hidden neurons
- $\rho$ is the sparsity parameter

KL divergence measures the deviation of the distribution $\{\rho_j\}$ of the activations at the hidden layer, from the uniform distribution of $\rho$

- KL divergence is minimum when $\forall j, \rho_j = \rho$ (Average activations are uniform, and equal to the very low value $\rho$)

## Training SAE

The cost function for the SAE is given by

$$
J_1 = J + \beta D(\bold{h})
$$

where $D(\bold{h})$ is the KL divergence of the hidden-layer activations

$$
D(\bold{h}) = \sum_{j=1}^{M} \rho \log \frac{\rho}{\rho_j} + (1 - \rho) \log \frac{1 - \rho}{1 - \rho_j}
$$

For gradient descent, we compute $\nabla_\bold{W} J_1$

$$
\nabla_\bold{W} J_1 = \nabla_\bold{W} J + \beta \nabla_\bold{W} D(\bold{h})
$$

By chain rule,

$$
\frac{\partial D(\bold{h})}{\partial \bold{w}_j} = \frac{\partial D(\bold{h})}{\partial \rho_j} \frac{\partial \rho_j}{\partial \bold{w}_j}
$$

We can calculate $\frac{\partial D(\bold{h})}{\partial \rho_j}$ and $\frac{\partial \rho_j}{\partial \bold{w}_j}$ separately

$$
\begin{aligned}
    D(\bold{h}) &= \sum_{j=1}^{M} \rho \log \frac{\rho}{\rho_j} + (1 - \rho) \log \frac{1 - \rho}{1 - \rho_j} \\
    \frac{\partial D(\bold{h})}{\partial \rho_j} &= -\frac{\rho}{\rho_j} + \frac{1 - \rho}{1 - \rho_j} \\ \\

    \rho_j &= \frac{1}{P} \sum_{p=1}^{P} f(u_{pj}) \\
    &= \frac{1}{P} \sum_{p=1}^{P} f(\bold{x}_p^T \bold{w}_j + b_j) \\
    \frac{\partial \rho_j}{\partial \bold{w}_j} &= \frac{1}{P} \sum_p f'(u_{pj}) \bold{x}_p
\end{aligned}
$$

Therefore

$$
\begin{aligned}
    \frac{\partial D(\bold{h})}{\partial \bold{w}_j} &= \left( -\frac{\rho}{\rho_j} + \frac{1 - \rho}{1 - \rho_j} \right) \left( \frac{1}{P} \sum_p f'(u_{pj}) \bold{x}_p \right) \\
    &= \frac{1}{P} \left( -\frac{\rho}{\rho_j} + \frac{1 - \rho}{1 - \rho_j} \right) \sum_p f'(u_{pj}) \bold{x}_p
\end{aligned}
$$

Then, we can find

$$
\nabla_\bold{W} D(\bold{h}) = \begin{pmatrix}
    \nabla_{\bold{w}_1} D(\bold{h}) & \cdots & \nabla_{\bold{w}_M} D(\bold{h})
\end{pmatrix}
$$

The gradient of the constrained cost function can be computed fully now

$$
\nabla_\bold{W} J_1 = \nabla_\bold{W} J + \beta \nabla_\bold{W} D(\bold{h})
$$

Similarly, $\nabla_{\bold{b}} J_1$ and $\nabla_{\bold{c}} J_1$ can be derived.

Learning can be done as:

$$
\begin{aligned}
    \bold{W} &\leftarrow \bold{W} - \alpha \nabla_\bold{W} J_1 \\
    \bold{b} &\leftarrow \bold{b} - \alpha \nabla_\bold{b} J_1 \\
    \bold{c} &\leftarrow \bold{c} - \alpha \nabla_\bold{c} J_1 \\
\end{aligned}
$$

# Deep-stacked Autoencoders

Deep autoencoders can be built by stacking autoencoders one after the other, and training of deep autoencoders is done in a step-by-step fashion, one layer at a time

- After training the first level of the denoising autoencoder, the resulting hidden representation is used to train a second level of the denoising autoencoder
- The second level hidden representation can be used to train the third level of the encoder
- Process is repeated, and a deep stacked autoencoder can be realised

![](train-deep-stacked-autoencoders.png)

# Semi-Supervised Classification

![](train-semi-supervised-classification.png)
Many images, but few ground truth labels

1. Start unsupervised, train autoencoder on many images
2. Supervised fine-tuning, train classification network on labelled images

# Context Encoders

![](https://miro.medium.com/v2/resize:fit:1400/1*cOEuYbhhx5MmGWlENKJwFw.png)

1. Remove a patch $p$ from an image $x$.
2. Feed the image with the missing patch $x - p$ into the encoder
3. The decoder should output a reconstruction of the missing patch $\hat{p}$
4. Compute reconstruction loss with reconstructed patch $\hat{p}$ and original removed patch $p$


 AutoEncoders

# Generative Adversarial Networks

Unlike discriminative models, which only model $p(y | \bold{x})$, generative models can model $p(y | \bold{x})$ and generate new data/images

# Basics of GANs

![](https://sthalles.github.io/assets/dcgan/GANs.png)

GANs samples a noise $\bold{z} \sim \mathcal{N}(0, 1)$ or $\bold{z} \sim \mathcal{U}(-1, 1)$ and utilises a network generator $G$ to create an image $\bold{x} = G(\bold{z})$

In GANs, we add a discriminator to distinguish whether an image $\bold{x}$ is real or generated

$$
D(\bold{x}) = \begin{cases}
    1 & \bold{x} \text{ is real} \\
    0 & \bold{x} \text{ is generated}
\end{cases}
$$

Generative model $G$:

- Captures data distribution
- Generates an image $G(\bold{z})$ such that $D(G(\bold{z})) = 1$ (Discriminator thinks that generated image is real)
- $\bold{z}$ is some random gaussian/uniform noise, which can be thought as the latent representation of the data

Discriminative model $D$

- Distinguishes between real and fake samples
- $D(\bold{x}) = 1$ when $\bold{x}$ is a real image, 0 otherwise

$D$ and $G$ play the following two-player minimax game with the value function $V(G, D)$:

$$
\min_G \max_D V(D, G) = \mathbb{E}_{\bold{x} \sim p_{\text{data}}(\bold{x})} [\log D(\bold{x})] + \mathbb{E}_{\bold{z} \sim p_\bold{z}(\bold{z})} [\log (1 - D(G(\bold{z})))]
$$

# Training

We use mini-batch stochastic gradient descent training of GANs. The number of steps to apply the discriminator, $k$, is a hyperparameter. We use $k = 1$ here, the least expensive option

For a number of training iterations:

1. For $k$ steps:

   - Sample minibatch of $m$ noise samples $\{ \bold{z}^{(1)}, ..., \bold{z}^{(m)} \}$ from noise prior $p_g(\bold{z})$
     - We are sampling from some uniform/gaussian noise vector
   - Sample minibatch of $m$ examples $\{ \bold{x}^{(1)}, ..., \bold{x}^{(m)} \}$ from data generating distribution $p_\text{data}(\bold{x})$
     - We get real images from the training dataset
   - Update the discriminator by **ascending** its stochastic gradient (Note we want to **maximise** the cost function here)

     $$
         \nabla_{\theta_d} \frac{1}{m} \sum_{i=1}^{m} \left[ \log D\left( \bold{x}^{(i)} \right) + \log\left(1 - D\left(G\left(\bold{z}^{(i)}\right)\right)\right) \right]
     $$

     - We find the gradient w.r.t the parameters of the discriminator $\theta_d$
     - We want our discriminator to predict $1$ for any $\bold{x}^{(i)}$ (Real images should be predicted as real (1) by the discriminator)
     - We want our discriminator to predict $0$ for any $G(z^{(i)})$ (Generated images should be predicted as generated (0) by the discriminator)
     - The higher the cost function, the better our discriminator is performing (If our discriminator is perfect, the cost function evaluates to $0$)

2. Now we freeze the discriminator, and train the generator

   - Sample minibatch of $m$ noise samples $\{ \bold{z}^{(1)}, ..., \bold{z}^{(m)} \}$ from noise prior $p_g(\bold{z})$
   - Update the generator by **descending** its stochastic gradient (Note we want to **minimise** the cost function)

   $$
       \nabla_{\theta_g} \frac{1}{m} \sum_{i=1}^{m} \log\left(1 - D\left(G\left(\bold{z}^{(i)}\right)\right)\right)
   $$

   - We find the gradient w.r.t the parameters of the generator $\theta_g$
   - We want our generator to be able to fool the discriminator ($D\left(G\left(\bold{z}^{(i)}\right)\right) = 1$)
   - The lower the cost function, the better our generator is performing (If generator is perfect, the cost function evaluates to $-\infty$)

# Deep Convolutional GAN (DCGAN)

![](https://production-media.paperswithcode.com/methods/Screen_Shot_2020-07-01_at_11.27.51_PM_IoGbo1i.png)

- Note that most deconvs are batch normalised
  - Normalise responses to have 0 mean and unit variance over the entire mini-batch
  - Faster and more stable
- Fractionally strided convolutions are used

![](https://d3i71xaburhd42.cloudfront.net/f19284f6ab802c8a1fcde076fcb3fba195a71723/25-Figure4.6-1.png)
Fractionally-strided convolutions

- Zeros are inserted between input units, which make the kernel move around at a slower pace than with unit strides
- Dashed-white cells are zero rows/columns padded between the input cells (blue), and the resultant convolution is in green

## Other Tricks Proposed by DCGAN

- Adam optimizer (adaptive moment estimation)
  - Similar to SGD, but with less parameter tuning
- Momentum = 0.5 (usually 0.9, but training oscillated and was unstable)
- Low learning rate: 0.0002

## Sanity Check by Walking on the Manifold

We can interpolate between a series of random points in $\bold{z}$

$$
\bold{z}_{\text{new}} = m \bold{z}_1 + (1 - m) \bold{z}_2
$$

We pass $\bold{z}_\text{new}$ into the generator, and should see a smooth transition between $\bold{z}_1$ and $\bold{z}_2$

![](https://www.researchgate.net/publication/348875360/figure/fig2/AS:1000512908439564@1615552274687/Interpolation-of-the-pose-latent-space.ppm)

## Sanity Check by Vector Space Arithmetic

If we have $\bold{z}_1$ generating a man with glasses, $\bold{z}_2$ generating a man, and $\bold{z}_3$ generating a woman, then $\bold{z} = \bold{z}_1 - \bold{z}_2 + \bold{z}_3$ should generate a woman with glasses

# Advantages/Disadvantages of GANs

We choose GANs because

- Sampling/generation is straightforward
- Training does not involve maximum likelihood estimation (finding the best model paramters that fit the training data the most), which is believed to cause poorer quality of images (e.g. blurry images)
- Robust to overfitting, since generator never sees training data

However,

- Probability distribution is implicit
  - Not straightforward to compute $p(\bold{x})$
  - Vanilla GANs are only good for sampling/generation
- Training is hard
  - Non-convergence
  - Mode-collapse

## Non-convergence

Deep learning models usually involve a single player

- Player tries to maximise its reward (minimise loss)
- SGD with backpropagation to find optimal parameters
- SGD has convergence guarantees (under certain conditions)
- However, with non-convexity, we might converge to a local optima

$$
    \min_G L(G)
$$

GANs instead involve 2 or more players

- Discriminator is trying to maximise reward
- Generator trying to minimise discriminator's reward

  $$
      \min_G \max_D V(D, G)
  $$

- SGD not designed to find Nash equilibrium of a game
- Problem: Might not converge to Nash equilibrium at all

## Mode-Collapse

![](https://miro.medium.com/v2/resize:fit:1400/1*DXP3m9l82FHpuBJounBSXg.png)

Generator fails to output diverse samples

- Generator finds one good image that fools the discriminator, and only generates that one particular image

During mode collapse,

- Generator produces good samples, but very few
- Hence, discriminator is unable to tag them as fake

To address this problem,

- Let discriminator look at the entire batch instead of single examples
- If there is a lack of diversity, it will mark the examples as fake
- This way, generator is forced to produce diverse samples

Procedure

1. Extract features that capture diversity in the mini-batch
   - E.g. L2 norm of the difference between all pairs from the batch
2. Feed these features to the discriminator along with the image
3. Feature values will differ between diverse and non-diverse batches
   - Hence, discriminator will rely on these features for classification
4. This in turn
   - Forces generator to match those feature values with real data
   - Will generate diverse batches

## Supervision with Labels

Label inforrmation of the real data might help

- Instead of discriminator just predicting real/fake, discriminator should predict the classes present in the data, or whether the sample is fake (dog/car/cat + fake)
- Empirically generates much better samples

# Conditional GANs

Condition the inputs to the generator and discriminator with labels

- Take an image from the training data $\bold{x}^{(i)}$ and its corresponding label $y^{(i)}$
- Generate an image using some random noise $\bold{z}^{(i)}$ and a corresponding label $y^{(i)}$
- Pass image/label pairs into the discriminator, and let discriminator predict whether image is real/fake based on both the input image $\bold{x}^{(i)}$ and its corresponding label $y^{(i)}$
- Conditions the model on additional information for better multi-modal learning

![](https://salu133445.github.io/dan/figs/cgan.png)


 Generative Adversarial Networks

# Logarithms

Suppose you want to solve $10^x = 100$. We can see that $10*10 = 10^2 = 100$, hence $x=2$. However, what if we wanted a general function that solves for $x$:

$$
a^x = b
$$

This is where we define the **logarithm** function, where $x = \log_a b$. The logarithm answers the question: How many times do I have to multiply $a$ by itself to get $b$?

From this definition, we can derive a few properties of the logarithm function

## $\log_a a = 1$

We can multiply $a$ by itself exactly 1 time to get a ($a^1 = a$). Hence $\log_a a = 1$

---

## $\log_a x + \log_a y = \log_a xy$

We can let $p = a^x, q = a^y$. $pq = a^x a^y = a^{x+y}$.

$$
\begin{aligned}
    p &= a^x \implies \log_a p = x \log_a a = x \\
    q &= a^y \implies \log_a q = y \\
    pq &= a^{x+y} \implies \log_a pq = x + y = \log_a p + \log_a q
\end{aligned}
$$

Similarly, $\log_a x - \log_a y = \log_a \frac{x}{y}$

---

## $\log_a x^y = y \log_a x$

Since $\log_a x + \log_a x = 2\log_a x = \log_a x^2$, we can generalise that $y \log_a x = \log_a x  + \cdots + \log_a x = \log_a (x\cdots x) = \log_a x^y$

---

## $\log_a b = \frac{\log_c b}{\log_c a}$

$$
\begin{aligned}
x &= \log_a b \\
a^x &= b \\
\log_c a^x &= \log_c b & \text{(Take $\log_c$ both sides)} \\
x \log_c a &= \log_c b & (\log_a x^y = y \log_a x) \\
x &= \frac{\log_c b}{\log_c a} \\
\log_a b &= \frac{\log_c b}{\log_c a}
\end{aligned}
$$


 Logarithms

# Longest Common Subsequence

The longest common subsequence (LCS) is defined as the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences.

If S1 and S2 are the two given sequences then, Z is the common subsequence of S1 and S2 if Z is a subsequence of both S1 and S2. Furthermore, Z must be a strictly increasing sequence of the indices of both S1 and S2.

For example, the longest common subsequence between `ABCDE` and `AXBXCXBXA` is 3 (`ABC`)

Let's look at a few properties first before tackling the code.

1. The longest common subsequence between any string with an empty string is 0. "AAA" and "" have a longest common subsequence of 0
2. The longest common subsequence between any strings with the same last 2 characters is 1 + the longest common subsequence if both the strings did not have that character.

Between `ABC` and `BDC`, we know that `C` will be part of the subsequence, hence we can just compare `AB` and `BD`, and figure out the longest common subsequence between those 2 shortened strings. Afterwards, we can add 1 to that result.

3. Now between `ABCD` and `BDEF`, to find the longest common subsequence, we

- Remove 1 character from the first string, and compare the LCS for both strings (`lcs("ABC", "BDEF")`)
- Remove 1 character from the second string, and compare the LCS for both strings (`lcs("ABCD", "BDE")`)
- Take the maximum as the answer

With these information, we can write a recurrent function first

```python
def lcs(s1, s2):
    # If one of the strings is empty, the longest common subsequence is 0
    if len(s1) == 0 or len(s2) == 0:
        return 0

    # If the last characters are the same, we can add 1 to the score
    if s1[-1] == s2[-1]:
        return 1 + lcs(s1[:-1], s2[:-1])

    # Remove 1 character from the first string and compare, remove 1 character from the second string and compare
    return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
```

However, this algorithm has a very long runtime. We can reduce this by using dynamic programming instead. We will create a DP table, and build up our answers from there.

# Dynamic Programming

Dynamic Programming is an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later.

Let us consider finding the LCS of "ABC" and "BCZA"

So, to represent our series of subproblems, we can use the following table

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  |     |     |     |
| B   |     |     |     |
| C   |     |     |     |
| Z   |     |     |     |
| A   |     |     |     |

Each cell in the table represents the LCS of the string up to that character. For example, `table[0][0]` is the LCS for 2 empty strings. `table[1][3]` is the LCS between "B" and "ABC". Our final result is in `table[4][3]`

To begin, we can realise that any comparison with an empty string is 0. Hence,

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   |     |     |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

Next. We look at `table[1][1]`. We are finding the longest common subsequence between "A" and "B", which is the maximum of

1. The LCS between "A" and ""
2. The LCS between "" and "B"

The answer to 1. is in `table[0][1]` and 2. in `table[1][0]`. Hence, `table[1][1] = 0`

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   |     |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

Now we consider `table[1][2]`. We are looking for the LCS between "AB" and "B". Since the last characters are the same, we can conclude that `lcs("B", "AB") = 1 + lcs("", "A")`. From the table, we can conclude that `lcs("B", "AB") = 1`.

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   | 1   |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

In general, if at `table[m][n]`, the last characters of both strings are equal, then `table[m][n] = 1 + table[m-1][n-1]`.

Now we consider `table[1][3]`. We are trying to find the LCS of "ABC" and "B". The last character is not the same. Hence, we look at the 2 cases we mentioned.

1. `lcs("AB", "B")`, removing the last character of the first string. From the table, `lcs("AB", "B") = 1`
2. `lcs("ABC", "")`, removing the last character of the second string. From the table, `lcs("ABC", "") = 0`

With these 2 pieces of information, we can conclude that `lcs("ABC", "B") = max(1, 0) = 1`.

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   | 1   | 1   |
| C   | 0   |     |     |
| Z   | 0   |     |     |
| A   | 0   |     |     |

We can continue filling up the entire table, and it will look like this

|     | ""  | A   | B   | C   |
| --- | --- | --- | --- | --- |
| ""  | 0   | 0   | 0   | 0   |
| B   | 0   | 0   | 1   | 1   |
| C   | 0   | 0   | 1   | 2   |
| Z   | 0   | 0   | 1   | 2   |
| A   | 0   | 1   | 1   | 2   |

So, our final result is `lcs("ABC", "BCZA") = 2`

The code looks like this

```python
def lcs(s1, s2):
    # DP Table
    results = [[0]*(len(s1)+1) for i in range(len(s2)+1)]

    for columnIndex in range(1, len(results[0])):
        for rowIndex in range(1, len(results)):
            currentCharS1 = s1[columnIndex-1]
            currentCharS2 = s2[rowIndex-1]

            if currentCharS1 == currentCharS2:
                results[rowIndex][columnIndex] = 1 + results[rowIndex-1][columnIndex-1] # same as removing the last character of both strings
            else:
                results[rowIndex][columnIndex] = max(results[rowIndex-1][columnIndex], results[rowIndex][columnIndex-1])

    print(results)
    return results[-1][-1]
``
```


 Longest Common Subsequence

# N-Queens

Problem: Given an NxN sized chessboard, generate all possible configurations where N queens are placed on the board, and all of them do not attack each other

The N-queens problem will take very long to run, if we were to check all possible permutations of the chessboard. The total number of possible permutations are given by

$$
T(N) = {N^2 \choose N}
$$

For a standard chessboard $N = 8$, there are a total of 4,426,165,368 combinations, but only 92 solutions.

Instead of generating all possible permutations, we can constrain which permutations we generate. By constraining to have only 1 queen per row, we reduce the total possible permuations to

$$
T(N) = N^N
$$

For $N = 8$, we reduced the number of permutations to 16,777,216 (0.379% of the original). We can also further restrict that at most 1 queen can exist per diagonal, reducing it to $N!$ ($T(8) = 40320$).

We can use backtracking to solve the problem. The pseudocode is as follows:

1. Start from (0, 0)
2. For a specific row
   1. For all columns in the row
      1. Place the queen in that column
      2. If the board is still valid
         1. Recurse with the next row, starting again from the first column
      3. If all the queens are placed, and the board is valid
         1. Print the board
      4. Remove the queen from the space

```python
def n_queens(board, row, col):
    if row > len(board)-1 or col > len(board)-1:
        return

    for i in range(len(board)):
        # Try to add queen on the column
        board[row][i] = 1

        # If adding the queen is valid, recurse
        if isValidBoard(board):
            n_queens(board, row+1, col)

        # If all queens placed, and is valid
        if sum([sum(row) for row in board]) == n and isValidBoard(board):
            print('===')
            printBoard(board)

        # Remove the queen
        board[row][i] = 0

def printBoard(board):
    for i in range(len(board)):
        print(board[i])

def isValidBoard(board):
    # at most 1 queen per row
    for i in range(len(board)):
        if sum(board[i]) > 1:
            # print("Row is not valid")
            # printBoard(board)
            return 0

    # at most 1 queen per col
    for i in range(len(board)):
        if sum([row[i] for row in board]) > 1:
            # print("Column is not valid")
            # printBoard(board)
            return 0

    # Generating diagonals https://stackoverflow.com/questions/23069388/listing-elements-in-a-nested-lists-diagonally/23069625#23069625
    # at most 1 queen per diagonal
    h = len(board)
    w = len(board)
    for diagonal in [[board[h-1-q][p-q]
        for q in range(min(p, h-1), max(0, p-w+1)-1, -1)]
       for p in range(h+w-1)]:
          if sum(diagonal) > 1:
              return 0

    #  at most 1 queen per antidiagonal
    for antiDiagonal in [[board[p - q][q]
        for q in range(max(p-h+1,0), min(p+1, w))]
        for p in range(h + w - 1)]:
        if sum(antiDiagonal) > 1:
          return 0

    return 1

n = 12
board = [[0 for i in range(n)] for i in range(n)]
n_queens(board, 0, 0)
```

# Algorithm Analysis

Let $T(N)$ be the runtime for the n-queens algorithm of size $N$. From the code, we can express the runtime complexity recursively

$$
T(N) \approx N*(T(N-1) + O(N^2))
$$

At size $N$, we loop $N$ times, and we then call `n_queens` on the row afterwards, reducing the remaining number of rows to $N-1$. The last term $O(N^2)$ comes from the fact that `isValidBoard` runs in $O(N^2)$ time, checking all $N$ rows and $N$ columns.

Solving the recursive expression,

$$
T(N) = O(N!)
$$


 N-Queens

# Population vs Sample, and how to calculate statistics when combining datasets

It is important to distinguish **population** vs **sample**. A **population** is defined as **all members of a specified group**, while a **sample** is **part of a population**

> The **sample mean** is the average and is the sum of all observed outcomes from the sample divided by the total number of samples. The sample mean is denoted by $\bar{X}$

$$
\bar{X} = \frac{1}{n}\sum_{i=1}^{n} x_i
$$

The **population mean**, $\mu$ is the average of the entire population

> The **variance** is a statistical measurement of the spread between numbers in the dataset. The population variance, $\sigma^2$ and the sample variance $\hat{\sigma}^2$ are given by

$$
\sigma^2 = \frac{1}{N} \sum_{i=1}^{N}(x_i - \bar{X})^2 = \frac{1}{N} \left( \sum_{i=1}^{N}x_i^2 - \frac{\left(\sum_{i=1}^{N} x_i\right)^2}{N} \right)
$$

$$
\hat{\sigma}^2 = \frac{1}{N-1} \sum_{i=1}^{N}(x_i - \bar{X})^2 = \frac{1}{N-1} \left( \sum_{i=1}^{N}x_i^2 - \frac{\left(\sum_{i=1}^{N} x_i\right)^2}{N} \right)
$$

> The standard deviation is the square root of the variance

$$
\sigma = \sqrt{\frac{1}{N} \sum_{i=1}^{N}(x_i - \bar{X})^2}
$$

$$
\hat{\sigma} = \sqrt{\frac{1}{N-1} \sum_{i=1}^{N}(x_i - \bar{X})^2}
$$

# Effects of Transformations on the Mean and Variance

If a random variable $X$ has a mean $\mu$ and standard deviation $\sigma$, and we let $Y = AX + B$, then

$$
\begin{aligned}
\mu_Y &= A\mu + B \\
\sigma_Y &= A^2 \sigma^2
\end{aligned}
$$

# Deriving the Mean and Variance of the Sample Mean

Let $X_1, X_2, ..., X_n$ be $n$ independently drawn (with replacement) observations from a distribution with mean $\mu$ and variance $\sigma^2$. If they were not drawn with replacement, each observation would not be independent anymore.

$$
E(X_i) = \mu, Var(X_i) = \sigma^2
$$

Let $\bar{X}$ be the mean of the $n$ independent observations

$$
\bar{X} = \frac{1}{n}\sum_{i=1}^{n} X_i
$$

From here, the expected value of $\bar{X}$ is:

$$
\begin{aligned}
E(\bar{X}) &= E\left(\frac{1}{n}\sum_{i=1}^{n} X_i\right) \\
&= \left(\frac{1}{n}\right) E\left(\sum_{i=1}^{n} X_i\right) \\
&= \left(\frac{1}{n}\right) \sum_{i=1}^{n} E\left(X_i\right) \\
&=  \left(\frac{1}{n}\right) \sum_{i=1}^{n} \mu \\
&= \left(\frac{1}{n}\right) n \mu \\
&= \mu
\end{aligned}
$$

From this, we can conclude that the **expected mean of the sample is the population mean**

Similarly, the variance of $\bar{X}$,

$$
\begin{aligned}
Var(\bar{X}) &= Var\left(\frac{1}{n}\sum_{i=1}^{n} X_i \right) \\
&= \frac{1}{n^2} Var\left(\sum_{i=1}^{n} X_i \right) \\
&= \frac{1}{n^2} \sum_{i=1}^{n} Var\left(X_i \right) \\
&= \frac{1}{n^2} \sum_{i=1}^{n} \sigma^2 \\
&= \frac{1}{n^2} n\sigma^2 \\
&= \frac{\sigma^2}{n}
\end{aligned}
$$

In conclusion, the sampling distribution of $\bar{X}$ has

- Mean $\mu$
- Standard deviation $\frac{\sigma}{\sqrt{n}}$

# Why is the sample variance divided by $N-1$?

We will now prove that

$$
E(S^2) = E\left[\frac{1}{n-1}\sum_{i=1}^{n}(X_i - \bar{X})^2\right] = \sigma^2
$$

This will show why we divide the sample variance by $n-1$ and not $n$

Let $X_1, X_2, ..., X_n$ be $n$ independently drawn (with replacement) observations from a distribution with mean $\mu$ and variance $\sigma^2$. This means that $E(X) = \mu, Var(X) = \sigma^2$.

We know that

$$
\begin{aligned}
Var(X) &= E(X^2) - [E(X)]^2 \\
\sigma^2 &= E(X^2) - \mu^2 \\
E(X^2) &= \sigma^2 + \mu^2
\end{aligned}
$$

Similarly,

$$
E(\bar{X}^2) = \frac{\sigma^2}{n} + \mu
$$

As explained in the previous section, the sampling distribution of $\bar{X}$ has mean $\mu$ and variance $\frac{\sigma^2}{n}$

We will now compute $E\left[\sum_{i=1}^{n}(X_i - \bar{X})^2\right]$

$$
\begin{aligned}
E\left[\sum_{i=1}^{n}(X_i - \bar{X})^2\right] &= E\left[\sum_{i=1}^{n}(X_i^2 - 2X_i\bar{X} + \bar{X}^2)\right] & \text{Expand} \\
&= E\left[\sum_{i=1}^{n}X_i^2 - \sum_{i=1}^{n} 2X_i\bar{X} + \sum_{i=1}^{n} \bar{X}^2\right] & \text{Split summations} \\
&= E\left[\sum_{i=1}^{n}X_i^2 - 2\bar{X} \sum_{i=1}^{n} X_i + n \bar{X}^2\right] & \sum_{i=1}^{n} \bar{X}^2 = n \bar{X}^2 \\
&= E\left[\sum_{i=1}^{n}X_i^2 - 2\bar{X} n\bar{X} + n \bar{X}^2\right] & \frac{\sum_{i=1}^{n} X_i}{n} = \bar{X} \\
&= E\left[\sum_{i=1}^{n}X_i^2 - n\bar{X}^2\right] \\
&= \sum_{i=1}^{n}E\left[X_i^2\right] - nE\left[\bar{X}^2\right] \\
&= \sum_{i=1}^{n} (\sigma^2 + \mu^2) - n(\frac{\sigma^2}{n} + \mu) & E\left[X_i^2\right] = \sigma^2 + \mu^2, E(\bar{X}^2) = \frac{\sigma^2}{n} + \mu  \\
&= n(\sigma^2 + \mu^2) - n(\frac{\sigma^2}{n} + \mu) \\
&= (n-1) \sigma^2
\end{aligned}
$$

Now,

$$
\begin{aligned}
E(S^2) &= E\left[\frac{1}{n-1} \sum_{i=1}^{n}(X_i - \bar{X})^2\right] \\
&= \frac{1}{n-1}  E\left[\sum_{i=1}^{n}(X_i - \bar{X})^2\right] \\
&= \frac{1}{n-1} (n-1)\sigma^2 \\
&= \sigma^2
\end{aligned}
$$

Also, another way to look at this:

If we take a sample of size $n$ from $X$, then

$$
\sigma_X^2 = \frac{1}{n} \sum_{i=1}^{n} (X_i - \bar{X})^2
$$

According to the above, the random variable $X$ deviates from the sample mean $\bar{X}$ with variance $\sigma_X^2$. The sample mean $\bar{X}$ deviates from $\mu$ with a variance $\frac{\sigma^2}{n}$, explained above.

Therefore, $X$ should deviate from $\mu$ with variance $\sigma^2 = \sigma_X^2 + \frac{\sigma^2}{n}$. Hence $\sigma^2 = \frac{n}{n-1} \sigma_X^2$, and by replacing $\sigma_X^2$ with $\sigma^2$,

$$
\sigma^2 = \frac{1}{n-1} \sum_{i=1}^{n} (X_i - \bar{X})^2
$$

# Combining multiple datasets

Consider 2 independent, non-overlapping datasets:

1. $X = \{X_1, X_2, ..., X_m\}$ with mean $\mu_1$ and standard deviation $\sigma_1$
2. $Y = \{Y_1, Y_2, ..., Y_n\}$ with mean $\mu_2$ and standard deviation $\sigma_2$

If we combine the 2 datasets together,

$$
\begin{aligned}
\mu_3 &= \frac{\mu_1 m + \mu_2 n}{m + n} \\
\sigma_3 &= \sqrt{\frac{m \sigma_1^2 + n \sigma_2^2 + m(\mu_1 - \mu_3)^2 + n(\mu_2 - \mu_3)^2}{m + n}}
\end{aligned}
$$

Or, for sample instead of population standard deviation,

$$
\sigma_3 = \sqrt{\frac{(m-1) \sigma_1^2 + (n-1) \sigma_2^2 + m(\mu_1 - \mu_3)^2 + n(\mu_2 - \mu_3)^2}{m + n - 1}}
$$

### Derivation

The mean of the combination of the 2 datasets

$$
\begin{aligned}
\mu_3 &= \frac{\sum_{z_i \in X \cup Y} z_i}{|X| + |Y|} & \text{Definition of mean} \\
&= \frac{(X_1 + \cdots + X_m) + (Y_1 + \cdots + Y_n)}{m + n} \\
&= \frac{m \mu_1 + n \mu_2}{m + n} & \mu_1 = \frac{\sum_{i=1}^{m} X_i}{m}, \therefore \sum_{i=1}^{m} X_i = m \mu_1
\end{aligned}
$$

The variance of the combination of the 2 datasets

$$
\begin{aligned}
\sigma_3^2 &= \frac{\sum_{z_i \in X \cup Y} (z_i - \bar{z})^2}{|X| + |Y|} \\
&= \frac{\sum_{z_i \in X \cup Y} z_i^2 - 2\bar{z}\sum_{z_i \in X \cup Y} z_i + \sum_{z_i \in X \cup Y} \bar{z}^2}{m + n} \\
\end{aligned}
$$

$$
\begin{aligned}
\sigma_1^2 &= \frac{\sum X_i^2}{m} - \mu_1^2 \\
\therefore \sum X_i^2 &= m(\sigma_1^2 + \mu_1^2) \\
\\
\sum_{z_i \in X \cup Y} z_i^2 &= \sum_{X_i \in X} X_i^2 + \sum_{Y_i \in X} Y_i^2 \\
&= m(\sigma_1^2 + \mu_1^2) + n(\sigma_2^2 + \mu_2^2) \\
\\
2\bar{z}\sum_{z_i \in X \cup Y} z_i  &= 2\mu_3\left(\sum_{X_i \in X} X_i + \sum_{Y_i \in Y} Y_i\right) \\
&= 2\mu_3(m \mu_1 + n \mu_2) \\
\\
\sum_{z_i \in X \cup Y} \bar{z}^2 &= (m + n)\mu_3^2 \\
\\
\therefore \sigma_3^2 &= \frac{m(\sigma_1^2 + \mu_1^2) + n(\sigma_2^2 + \mu_2^2) - 2\mu_3(m \mu_1 + n \mu_2) + (m + n)\mu_3^2}{m + n} \\
&= \frac{m\sigma_1^2 + n\sigma_2^2 + (m\mu_1^2 - 2\mu_3 m \mu_1  + m \mu_3^2) + (n\mu_2^2  - 2\mu_3 n \mu_2 + n \mu_3^2)}{m + n} \\
&= \frac{m \sigma_1^2 + n \sigma_2^2 + m(\mu_1 - \mu_3)^2 + n(\mu_2 - \mu_3)^2}{m+n}
\end{aligned}
$$

### Sources

- [Deriving the Mean and Variance of the Sample Mean](https://www.youtube.com/watch?v=7mYDHbrLEQo)
- [Proof that the Sample Variance is an Unbiased Estimator of the Population Variance](https://www.youtube.com/watch?v=D1hgiAla3KI)
- https://stats.stackexchange.com/questions/55999/is-it-possible-to-find-the-combined-standard-deviation
- https://stats.stackexchange.com/questions/3931/intuitive-explanation-for-dividing-by-n-1-when-calculating-standard-deviation


TOH HONG XIANG

ABOUT ME

EXPERIENCE

Marketplace Intelligence Engineer - Shopee Private Limited

Software Developer - Industrial Electronics Private Limited

PROJECTS

NextJS Directus E-Commerce Website

Gallereddit

Haze Monitoring Website

STUFF I WRITE

Recent Blog Posts

Recent Notes

CONTACT ME