Page cover image

#8: Neural Networks

  • 5 min

#8: Neural Networks content

Created
Topics
XOR, Backpropagation Algorithm

Lecture Outline

  1. Motivation behind neural networks
  1. The XOR problem
  1. Multi-Layer Perceptron model
  1. Backpropagation algorithm
  1. Regularization and other stuff in NNs

Artificial Neuron

notion image

OR vs XOR

TODO

Activation Functions

Introduce non-linearity to the model
  • Sigmoid
  • ReLU
Choosing activation function: an art not a science
  • Stick to one activation function for all layers

Two-Layer Neural Network

Single-hidden-layer network
Potentially overfits the dataset
Can simulate any line (linear or non-linear)
notion image
  • M=M = number of hidden layers (depth of network ) ⇒ number of hyperplanes
    • Deep learning: many hidden layers
  • h=h = any activation function (sigmoid, ReLU, etc.)
For regression tasks: K=1K=1, σ=\sigma= identity function
For binary classification task: σ(a)=sigmoid(a)=11+e−a\sigma(a)=\text{sigmoid}(a)=\frac{1}{1+e^{-a}}

Model

yk(x,w)=σ(∑j=0Mwkj(2)⋅h(∑i=0Dwji(1)⋅xi))y_{k}(x, \mathbf{w})=\sigma\left(\sum_{j=0}^{M} w_{k j}^{(2)} \cdot h\left(\sum_{i=0}^{D} w_{j i}^{(1)} \cdot x_{i}\right)\right)

Weight Matrix

notion image
Shape of WW
  • ii rows ⇒ # neurons in the next layer
  • jj columns ⇒ # neurons in the current layer
Each row in WiW_i corresponds to the output of the next layer
  • σ(wi⋅ai(L−1)+bi)=ai(L)\sigma (w_i\cdot a_i^{(L-1)}+b_i)=a_i^{(L)}
  • σ(wTa(L−1)+b)=a(L)\sigma (w^T a^{(L-1)}+b)=a^{(L)}

General Neural Network

A directed acyclic graph from left to right
notion image
zk=h(∑jwkjzj)z_{k}=h\left(\sum_{j} w_{k j} z_{j}\right)
k = unit for which compute activation for
j = input for unit k

Universal Approximator

💡
A two layer neural network can approximate any function

Training Neural Networks

Regression Task

Likelihood function

p(t∣xn,w)=N(t∣y(xn,w),β−1)p(t∣X,w,β)=∏i=1Np(tn∣xn,w,β)\begin{aligned}p\left(t \mid x_{n}, \mathbf{w}\right) &=\mathcal{N}\left(t \mid y\left(x_{n}, \mathbf{w}\right), \beta^{-1}\right) \\p(\mathbf{t} \mid X, \mathbf{w}, \beta) &=\prod_{i=1}^{N} p\left(t_{n} \mid x_{n}, \mathbf{w}, \beta\right)\end{aligned}

Loss Function

E(w)=−log⁡∏n=1Np(tn∣y(xn,w,β)=β2∑n=1N[y(xn,w)−tn]2−N2log⁡β+N2log⁡(2π)≈12∑n=1N[y(xn,w)−tn]2\begin{aligned}E(\mathbf{w}) &=-\log \prod_{n=1}^{N} p\left(t_{n} \mid y\left(x_{n}, \mathbf{w}, \beta\right)\right.\\&=\frac{\beta}{2} \sum_{n=1}^{N}\left[y\left(x_{n}, \mathbf{w}\right)-t_{n}\right]^{2}-\frac{N}{2} \log \beta+\frac{N}{2} \log (2 \pi) \\& \approx \frac{1}{2} \sum_{n=1}^{N}\left[y\left(x_{n}, \mathbf{w}\right)-t_{n}\right]^{2}\end{aligned}

Classification Task

Cross Entropy Loss

E(w)=−∑n=1N∑j=1Ktknlog⁡yk(xn,w)E(\mathbf{w})=-\sum_{n=1}^{N} \sum_{j=1}^{K} t_{k n} \log y_{k}\left(x_{n}, \mathbf{w}\right)

Training Using Gradient Descent

wt+1←wt−η∇E(w)\mathbf{w}^{t+1}\leftarrow w^t-\eta \nabla E(\mathbf{w})
Gradient ∇E(w)\nabla E(\mathbf{w}) is hard to find due to model complexity

Training Using Backpropagation Algorithm

💡
Message passing algo with 2 steps:
notion image

➡️ Forward Pass

starting from the inputs successively compute the activations of each unit
  1. Apply input xnx_n to the network
  1. Compute the activations of all units (hidden & output)
  1. Evaluate δk\delta_kfor all output units
    δk=yk−tk\delta_k=y_k-t_k
    • tk=t_k= ground truth
    • yk=y_k= prediction of the model

Example: Single Neuron Per Layer

Structure
notion image
Formulas
C0=(a(L)−y)2=E0a(L)=σ(z(L))z(L)=w(L)a(L−1)+b(L)∂C0∂a(L)=2(a(L)−y)∂a(L)∂z(L)=σ′(z(L))∂z(L)∂w(L)=a(L−1)\begin{align*} C_0&=(a^{(L)}-y)^2=E_0\\ a^{(L)}&=\sigma(\mathcal{z}^{(L)})\\ \mathcal{z}^{(L)}&=w^{(L)}a^{(L-1)}+b^{(L)}\\ \frac{\partial C_0}{\partial a^{(L)}}&=2(a^{(L)}-y)\\ \frac{\partial a^{(L)}}{\partial z^{(L)}} &=\sigma'(\mathcal{z}^{(L)})\\ \frac{\partial z^{(L)}}{\partial w^{(L)}}&=a^{(L-1)} \end{align*}C0=(σ(w(L)a(L−1)+b(L))−y)2C_0=(\sigma(w^{(L)}a^{(L-1)}+b^{(L)})-y)^2
∂C0∂w(L)=∂z(L)∂w(L)∂a(L)∂z(L)∂C0∂a(L)=a(L−1)σ′(z(L))2(a(L)−y)\begin{align*} \frac{\partial C_{0}}{\partial w^{(L)}}=\frac{\partial z^{(L)}}{\partial w^{(L)}} \frac{\partial a^{(L)}}{\partial z^{(L)}} \frac{\partial C_0}{\partial a^{(L)}}=a^{(L-1)}\sigma'(\mathcal{z}^{(L)})2(a^{(L)}-y) \end{align*}
notion image
notion image
∂C0∂b(L)=∂z(L)∂b(L)∂a(L)∂z(L)∂C0∂a(L)=1σ′(z(L))2(a(L)−y)\begin{align*} \frac{\partial C_{0}}{\partial b^{(L)}}=\frac{\partial z^{(L)}}{\partial b^{(L)}} \frac{\partial a^{(L)}}{\partial z^{(L)}} \frac{\partial C_0}{\partial a^{(L)}}=1\sigma'(\mathcal{z}^{(L)})2(a^{(L)}-y) \end{align*}∂C0∂a(L−1)=∂z(L)∂a(L−1)∂a(L)∂z(L)∂C0∂a(L)=w(L)σ′(z(L))2(a(L)−y)\begin{align*} \frac{\partial C_{0}}{\partial a^{(L-1)}}=\frac{\partial z^{(L)}}{\partial a^{(L-1)}} \frac{\partial a^{(L)}}{\partial z^{(L)}} \frac{\partial C_0}{\partial a^{(L)}}=w^{(L)}\sigma'(\mathcal{z}^{(L)})2(a^{(L)}-y) \end{align*}
 

⬅️ Backward Pass

successively compute the gradients of the error function with respect to the activations and the weights
  • First compute the gradient of the output
  1. Backpropagate δ\delta to compute δ\delta for all hidden unitsδj=∂En∂aj=∂En∂zj⋅∂zj∂aj=[∑k∂En∂ak∂ak∂zj]⋅h′(aj)\delta_{j}=\frac{\partial E_{n}}{\partial a_{j}}=\frac{\partial E_{n}}{\partial z_{j}} \cdot \frac{\partial z_{j}}{\partial a_{j}}=\left[\sum_{k} \frac{\partial E_{n}}{\partial a_{k}} \frac{\partial a_{k}}{\partial z_{j}}\right] \cdot h^{\prime}\left(a_{j}\right)
    Given δak∂zj=wkj\frac{\delta a_{k}}{\partial z_{j}}=w_{k j} and δEnδak=δk\frac{\delta E_{n}}{\delta a_{k}}=\delta_{k}
    δj=h′(aj)∑kwkjδk\delta_{j}=h^{\prime}\left(a_{j}\right) \sum_{k} w_{k j} \delta_{k}
  1. Evaluate the derivatives w.r.t. weights wjiw_{ji}:∂En∂wji=∂En∂aj∂aj∂wji=δjzi\frac{\partial E_{n}}{\partial w_{j i}}=\frac{\partial E_{n}}{\partial a_{j}} \frac{\partial a_{j}}{\partial w_{j i}}=\delta_j \mathscr{z}_i

Regularization

Weight Decay

Early stopping

Stop training as soon as the validation error starts increasing
Training Loss
Validation Loss
notion image
⇒ Equivalent to some kind of weight decay

Dropout

During each training iteration, remove from the model (turn off) each unit with a probability of pp
jj turned off ⇒ δj=0\delta_j=0
  • Validate & test using the full model, scale each unit by the frequency at which it is on
notion image

Convolutional Neural Networks (CNNs)

Motivation

Neural Network Convention
notion image
Problem: Output should be invariant to translation, rotation, scaling, distortion, elastic deformation, other arbitrary artifacts
Naïve Solution: Fully Connected Networks w/ a large & diverse data to obtain invariance
  • Each unit of each layer sees the whole image
  • Ignores the key property of images: locality - near by pixels tend to have similar values
  • Neural Networks are brittle ⚠️: small variances → big effect on output
  • Information can be merged at later stages to get higher order features about the whole image