Neural Network Math, LSTM Background

tags: Internship

Goal:

• Understand math behind neural networks
• Study conceptual components of LSTM

Resources:
Towards Data Science Page
Adventures in Machine Learning
Machine Learning

Math of Optimizing Neural Networks

Example cost function for a pair:

• The 1/2 coefficient just helps with easy calculation when we derive later on.

Mean squared error:

Gradient descent:

• Same idea as
• J is loss function
• Partial derivatives for gradient

Calculating Derivative of Loss Function

Find change of loss J caused by weight max w through chain function:

Solving for dz/dw:

• Previously established that z the the vectorization of the nodes in a layer such that

Solving for dh/dz:

• Previously established that h is the output of the activation on the node, AKA the result of f(z), such that

Solving for dJ/dh:

• This also requires chain rule to solve

Final derivative of loss function:

• Given

Propagating through Hidden Layers

Connecting weights between different layers:

• Weights connecting to output layer:
  • Simple since can directly compare output with training data
• Harder to calculate loss changes in outputs of hidden layers
  • No direct reference to compare outputs with
  • Only connected to loss function via other nodes and mediating weights

For hidden layer calculations, use backpropagation:

• Propagate this term through the layers:

  • This term is the network's way of connecting to the loss function.
  • Nodes in hidden layers contribute to this term via their weight
  • If only one output layer node, generalized term:

• If multiple nodes in output layer, then we can generalize to:

Conclusion

Given all the work above, we can finally calculate change of loss function by change in weights:

Following similar steps, we can also calculate change of loss function by change in bias:

Given the above derivations, we can finally calculate gradient descent:

Vectorization of backpropagation:

• Does NOT use matrix multiplication
• Dot symbol is element-by-element multiplication, AKA Hadamard product

For reference, Hadamard product works as such:

Integrating Gradient Descent

(Reminder) Overall cost function:

(Reminder) Gradient descent calculation (element-by-element and vectorized):

Sum up all partial derivatives of individual cost function calculations (both W and b):

• Perform this operation at each iteration.

Once you've iterated through all samples, update weight parameters:

Final Backpropagation Algorithm

• Randomly initialize weights for each layer
  $W^{(l)}$
• While iterations < iteration limit:
  • Set
    $\mathrm{\Delta }W$ and
    $\mathrm{\Delta }b$ to zero
  • For samples [1,m):
    • Perform feed forward pass through all
      $n_l$ layers.
    • Store activation function outputs h(l)
    • Calculate
      ${\delta }^{(n_l)}$ for output layer
    • Use backpropagation to calculate
      ${\delta }^{(l)}$ values for layers 2 to
      $n_l-1$
    • Update
      $\mathrm{\Delta }{W}^{(l)}$ and
      $\mathrm{\Delta }{b}^{(l)}$ for each layer
  • Perform gradient descent using:

$$W^{(l)}=W^{(l)}–\alpha \left[\frac{1}{m}\mathrm{\Delta }{W}^{(l)}\right]$$

$$b^{(l)}=b^{(l)}–\alpha \left[\frac{1}{m}\mathrm{\Delta }{b}^{(l)}\right]$$

Repeat gradient descent until satisfied with minimization.

Implementation of NN in Python

GOAL: Identify value of hand-written digits.

I will skip this part of the tutorial for now.

LSTM Tutorial

Source: https://adventuresinmachinelearning.com/recurrent-neural-networks-lstm-tutorial-tensorflow/

Continued from last note.

Problem with Vanilla RNN

• Recurrent neural networks
  • Each time step shares same set of weights
  • Very flexible configurations to describe inputs vs. outputs
    • Many-to-many
    • Many-to-one
    • One-to-many

• Impracticality of vanilla RNNs
  • Vanishing gradient problem
    • Can't handle long-term memory
    • More time steps = more backpropagation gradients accumulate to either explode or vanish

Demonstration of Vanishing Gradient Problem

Representation of RNN:

${\mathbf{\text{h}}}_t=\sigma ({\mathbf{\text{Ux}}}_t+{\mathbf{\text{Vh}}}_{t-1})$

• U: weight matrix connecting inputs
• V: weight matrix connecting recurrent outputs

Three time steps into performing softmax of

${\mathbf{\text{h}}}_t$ outputs:

$${\mathbf{\text{h}}}_t=\sigma ({\mathbf{\text{Ux}}}_t+\mathbf{\text{V}}(\sigma ({\mathbf{\text{Ux}}}_{t-1}+\mathbf{\text{V}}(\sigma ({\mathbf{\text{Ux}}}_{t-2})))$$

Gradient of error with respect to weight matrix U:

$$\frac{\partial E_3}{\partial U}=\frac{\partial E_3}{\partial ou{t}_3}\frac{\partial ou{t}_3}{\partial h_3}\frac{\partial h_3}{\partial h_2}\frac{\partial h_2}{\partial h_1}\frac{\partial h_1}{\partial U}$$

Each gradient requires calculation of gradient of sigmoid function:

• Sigmoid function may output close to either 0 or 1, so gradient becomes very small
• Eventually leads to vanishing gradient

If gradient becomes very small, then it does very little in adjusting the weight to the new values.

Components of LSTM Network

• LSTM cell is designed to prevent vanishing gradient problem
  • Reduces multiplication of gradients less than zero
  • Creates internal memory state that is just added to processed input
  • Forget gate: controls time dependence and effects of past inputs
    • Determines what to remember/forge

Structure of LSTM Cell

• Data flows left to right
• $x_t$: current input
• $h_t-1$: previous cell output
• Concatenate
  $x_t$ and
  $h_t-1$ together and enter it to top "data rail"

Input Gate

Scale input to range (-1,1) using tanh activation function:

$$g=tanh(b^g+x_t{U}^g+h_{t-1}{V}^g)$$

• $U^g$: weight for input
• $V^g$: previous cell output
• $b^g$: input bias
• $g$ denotes input weights and bias values (as opposed to input gate, forget gate, output gate, etc.)

Multiply tanh-squashed input by output of the input gate:

• Element-wise multiplication
• Input gate: hidden layer of sigmoid activated nodes
  • Input: weighted
    $x_t$
    $h_t-1$
  • Output: between 0 and 1
  • "Switches" input on or off via multiplication

Input gate:

$i=\sigma (b^i+x_t{U}^i+h_{t-1}{V}^i)$

Output of input stage of LSTM cell:

$g\circ i$

• $\circ$ denotes element-wise multiplication

Input gate output i acts as weights for squashed input g.

Internal State and Forget Gate

• Introduces new variable
  $s_t$: inner state of LSTM cell
  • Delay
    $s_t$ by one time-step
  • Add to
    $g\circ i$ input
  • Provides internal recurrence loop to learn relationship between inputs separated by time
• Forget gate: sigmoid activated set of notes
  • Element-wise multiplied by
    $s_t-1$ to determine remember/forget
  • Acts as weights for internal state
  • $f=\sigma (b^f+x_t{U}^f+h_{t-1}{V}^f)$
• Element-wise product of previous state and forget gate:
  $s_{t-1}\circ f$
  • Then added to input
    • NOT multiplied or mixed with it
    • Vanilla RNN would typicall mix it via weights and a sigmoid activation function
    • ADDING reduces risk of vanishing gradients
• Output of this stage:
  $s_t=s_{t-1}\circ f+g\circ i$

Output Gate

• Two parts:
  • tanh squashing function
  • Output sigmoid gating function
• Output sigmoid gating function: multiplied by squashed state
  $s_t$ to determine which values are output
  • $o=\sigma (b^o+x_t{U}^o+h_{t-1}{V}^o)$
• Final output of cell:
  $h_t=tanh(s_t)\circ o$

Reducing Vanishing Gradient Problem

In an LSTM cell, the recurrency of the internal uses addition:

$$s_t=s_{t-1}\circ f+g\circ i$$

Taking the partial derivative:

$$\frac{\partial s_t}{\partial s_{t-1}}=f$$

• Becomes just multiplication of
  $f$
• If output of
  $f=1$, then no gradient decay
• In the begnning, the bias of sigmoid in
  $f$ is typically made bigger so
  $f$ starts as 1
• Allows all past input states to be remembered in the beginning
• Later forget gate will reduce memory

Data Dimensions inside LSTM Cell

• Each input is a vector
  • Example: "cat" is a 650-length vector
• Each input row has a certain number of vectors
  • Example: one input row has 35 input vectors, so input of each row is 35x650
• Batches of data processed at once via multi-dimensional tensors
  • Example: batch size of 20, so training input data is 20x35x650
• "Time-major" format: arranged (35 x 20 x 650)