- Identity RNN with ReLU activation (solving vanishing gradient problem only)
- Gradient clipping
- Skip connections
- LSTM
- GRU

Solutions for vanishing/exploding gradient

A webpage explaining exploding gradients

https://machinelearningmastery.com/exploding-gradients-in-neural-networks/

A Gentle Introduction to Exploding Gradients in Neural Networks

If we initialize $W$s as a matrix of 0s, then $\frac{d\mathcal L}{dz}$ in each neuron from each layer would get the same value and no matter how long you train the network, gradient descent would get stuck at the same point. This is usually called the symmetry breaking problem.

What happens if we initialize the weights of a feed forward network to 0s?

Exploding/vanshing gradients is a common problem in reccurrent neural networks. Consider a network where an input is multiplied by a matrix $\bold{W}$ $t$ times. Let $\bold{W}^t$ have eigendecomposition $\bold{V}\text{diag}(\bold{\lambda})^t\bold{V}^{-1}$.

We can see that if $\lambda>1$, our result will approach $\infty$ as $t$ gets large. This is an exploding gradient. Also, if $\lambda <1$, the result will approach $0$ as $t$ gets large. This is a vanishing gradient.

When are exploding/vanishing gradients a problem?

In a neural network with many time steps or layers, a gradient at the early layer is the product of all the terms from the later layers, which leads to an inherently unstable situation. Especially when the value of gradient has become so small, it no longer updates properly or is vanished eventually. Exploding gradient can be considered as the opposite of vanishing process. The updated weights using gradient descent become so large that they cause the whole network to become unstable, which leads to numerical overflow. 

University of Michigan - Ann Arbor

Claude

University of Connecticut

In an RNN, backpropagation needs to take into account that the model is carrying forward information from each neural layer to the next, and fine tune the weights that govern this “short-term memory”.

This is called Backpropagation Through Time (BPTT). BPTT uses the chain rule to go back from the latest time step to the previous step, and then to the next-previous, each time using gradient descent to discover the best weights for each neuron and for the hidden state function.

Backpropagation Through Time (BPTT)

Gradient descent is a fundamental optimization algorithm that leverages gradients to minimize a model's loss function. Because the gradient of a function points in the direction of steepest ascent, moving the model's parameters in the opposite direction iteratively lowers the loss. Each step of such gradient-based optimization algorithms requires calculating the exact gradient of the loss with respect to the parameters.

Gradient Descent

For a feedforward neural network, the depth of the network is the number of hidden layers plus one (as the output layer is also parameterized). The width of the network is the dimensionality of its hidden layers.

The main architectural considerations for designing a neural network are choosing the depth of the network and the width of each layer.


Depth and Width for Neural Networks

Initial weights are applied to all the neurons.
It is necessary to set initial weights for the first forward pass. Two basic options are to set weights to zero or to randomize them. However, this can result in a vanishing or exploding gradient, which will make it difficult to train the model. To mitigate this problem, you can use a heuristic (a formula tied to the number of neuron layers) to determine the weights. A common heuristic used for the Tanh activation is called Xavier initialization.

On top of that if the architecture being used has already been trained by someone else (such as ImageNet) the node values can be initialized to those values. This is known as transfer learning and it can be very useful to substantially increase training speed and model accuracy.

Deep Learning Weight Initialization

Overflow and underflow are both errors resulting from a shortage of space.

- Overflow: Overflow indicates that we have done a calculation that resulted in a number larger than the largest number we can represent.

- Underflow: Underflow is a bit trickier to understand because it has to do with precision in floating points. Again, due to the discrete nature of storage in computers, we cannot store an arbitrarily small number either. The floating-point convention comes up with techniques to represent fractional numbers. When we use these in calculations that result in a smaller number than our least value, we again exceed our designated space.

Overflow and  Underflow in Computer Science

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

Dive into Deep Learning

Vanishing/exploding gradient

Let's start with a quick recap of the basic equations in RNN:
$$h^{(t)}=g_1(Wh^{(t-1)} \oplus Ux^{(t)}+b_h)$$
$$\hat y^{(t)}=g_2(Vh^{(t)}+b_y)$$
$$J^{(t)} = \mathcal{L} (\hat{y}^{(t)}, y^{(t)}) ~~~~~and~~~~~ J = \frac{1}{T} \sum_{t=1}^T J^{(t)} $$

We want to calculate the gradients of the loss function with parameters U,V, and W. We can sum up the gradients at each step since $\frac{\partial J}{ \partial W} = \frac{1}{T} \sum_{t=1}^T \frac{\partial J^{(t)}}{\partial W} $. Thus we only need to find $\frac{\partial J^{(t)}}{\partial W} $, $\frac{\partial J^{(t)}}{\partial V} $, and $\frac{\partial J^{(t)}}{\partial U} $.

Derivative of V only depends on the current step:
$$\frac{\partial J^{(t)}}{\partial V}  = \frac{\partial J^{(t)} }{\partial \hat{y}^{(t)}} \frac{\partial \hat{y}^{(t)}}{\partial V} $$

But it is not the case for derivative of U and W, take t=3 as an example:
$$\frac{\partial J^{(3)}}{\partial W}  = \sum_{k=1}^3 \frac{\partial J^{(3)} }{\partial \hat{y}^{(3)}} \frac{\partial \hat{y}^{(3)}}{\partial h^{(3)}} \frac{\partial h^{(3)}}{\partial h^{(k)}} \frac{\partial h^{(k)}}{\partial W}$$
$$ =\sum_{k=1}^3 \frac{\partial J^{(3)} }{\partial \hat{y}^{(3)}} \frac{\partial \hat{y}^{(3)}}{\partial h^{(3)}} (\prod_{j=k+1}^3 \frac{\partial h^{(j)}}{\partial h^{(j-1)}}) \frac{\partial h^{(k)}}{\partial W}$$
and
$$\frac{\partial J^{(3)}}{\partial U}  = \sum_{k=1}^3 \frac{\partial J^{(3)} }{\partial \hat{y}^{(3)}} \frac{\partial \hat{y}^{(3)}}{\partial h^{(3)}} \frac{\partial h^{(3)}}{\partial h^{(k)}} \frac{\partial h^{(k)}}{\partial U}$$
$$ =\sum_{k=1}^3 \frac{\partial J^{(3)} }{\partial \hat{y}^{(3)}} \frac{\partial \hat{y}^{(3)}}{\partial h^{(3)}} (\prod_{j=k+1}^3 \frac{\partial h^{(j)}}{\partial h^{(j-1)}}) \frac{\partial h^{(k)}}{\partial U}$$

RNN Backpropagation Formulas

A helpful website for understanding backpropagation in RNN:
http://www.wildml.com/2015/10/recurrent-neural-networks-tutorial-part-3-backpropagation-through-time-and-vanishing-gradients/

Helpful Website for BPTT

Teacher forcing is a method for quickly and efficiently training recurrent neural network models that use the ground truth from a prior time step as input.

Teacher forcing

Weight-tying is where you have a language model and use the same weight matrix for the input-to-embedding layer (the input embedding) and the hidden-to-softmax layer (the output embedding). The idea is that these two matrices contain essentially the same information, each having a row per word in the vocabulary.

In addition to providing improved perplexity results, this approach significantly reduces the number of parameters required for the model.

Weight typing

A helpful website for understanding gradient descent:
https://towardsdatascience.com/gradient-descent-explained-9b953fc0d2c

Gradient Descent Reference

Gradient descent is used to properly update parameters in order to maximize the efficiency of linear regressions. Below is a step-by-step example of how to implement gradient descent.

Linear Regression and Gradient Descent

You can check your derivative computation to make sure that your implementation of back propagation is correct. You want to consider BOTH the right hand side and the left hand side derivatives. By taking a two sided derivative, you can numerically verify whether or not the function g of theta is a correct implementation of the derivative of f.

Numerical Approximation of Gradients

This is the technique used to check that our implementation is correct. There are different formulas for gradient checking and one of those is two-sided form:
          $$\frac {J(\theta + \epsilon) - J(\theta - \epsilon)} {2\epsilon}$$
Common choice for $\epsilon$ is $10^{-7}$. You shouldn't use gradient checking for the whole training data as it can be slow.

Gradient Checking

Assuming that the error function is $J(w)$ with one parameter $w$, to minimize the error, we can update the weight $w$ as follows.
$$w = w - \alpha * \frac{dJ(w)}{dw}$$
, where $\alpha$ is a learning rate, and $\frac{dJ(w)}{dw}$ is the derivative of $J(w)$ with respect to $w$.

If the error function has two or more parameters, for example, a weight $w$ and a bias $b$, we can update them one by one.
$$w = w - \alpha * \frac{\partial J(w,b)}{\partial w}$$
$$b = b - \alpha * \frac{\partial J(w,b)}{\partial b}$$
, where $\partial$ is a stylish cursive $d$, denoting the partial derivatives.

(Batch) Gradient Descent (Deep Learning Optimization Algorithm)

https://towardsdatascience.com/gradient-descent-explained-9b953fc0d2c

Gradient Descent Explained

Gradient Descent is an algorithm which is designed to find the optimal points, but these optimal points are not necessarily global. And yes if it happens that it diverges from a local location it may converge to another optimal point but its probability is not too much.

Consider the following "recliner chair" type of function(image below).

Obviously, this can be constructed so that there is a range in the middle where the gradient is the 0 vector, casuing the fail to find global optima. 


Why Gradient descent might fail?

DeepLearningAI. (2021, March 24). A Chat with Andrew on MLOps: From Model-centric to Data-centric AI. YouTube. https://www.youtube.com/watch?v=06-AZXmwHjo

A Chat with Andrew on MLOps: From Model-centric to Data-centric AI

Sagar, R. (2021, April 6). Big Data To Good Data: Andrew Ng Urges ML Community To Be More Data-Centric And Less Model-Centric. Analytics India Magazine. https://analyticsindiamag.com/big-data-to-good-data-andrew-ng-urges-ml-community-to-be-more-data-centric-and-less-model-centric/

Big Data to Good Data: Andrew Ng Urges ML Community To Be More Data-Centric and Less Model-Centric

Andrew Ng believes that for datasets with fewer than 10,000 data points, machine learning teams can make faster progress by focusing on improving data than improving code.

MLOps: Data-centric and Model-centric approaches

Points where the derivative of a function is 0 are known as critical points, or stationary points.

The derivative also has to be zero according to every possible directional derivative at that point in higher dimensional functions.

$$\triangledown f = 0$$

Critical Points

Optimization algorithms that use only the gradient, such as gradient descent,are called ﬁrst-order optimization algorithms.

First-order Optimization Algorithm

Optimization algorithms that also use the Hessian matrix, such as Newton’s method, are called second-order optimization algorithms

Second-order Optimization Algorithm

When the method of steepest descent is applied to a quadratic cost surface, it creates a zig-zag pattern that each line search direction is orthogonal to its previous line search direction.
Let $d_{t-1}$ be the previous search direction. At the minimum, we will find that:
$$\nabla _\theta f(\theta) \cdot d_{t-1} = 0$$
Then we know $d_t = \nabla _\theta f(\theta)$ is orthogonal to $d_{t-1}$

Method of Steepest Descent

Unlike first-order methods, second-order gradient methods use second-order derivatives. This improves optimization. 
- The most widely used second-order gradient method is the Newton method

Second-Order Gradient Methods

Gradient descent is an algorithm used to find the minimum value of a function. We will use the gradient descent algorithm to find the cost function. The idea of the algorithm is to randomly select a parameter combination at the beginning, calculate, and then find the next parameter combination that can reduce the cost function value the most, and continue to a minimum value.

https://machinelearningmastery.com/gradient-descent-for-machine-learning/

Gradient Descent Explanation

There are three variants of gradient descent, which differ in how much data we use to compute the gradient of the objective function: Batch Gradient Descent, Stochastic Gradient Descent and Mini-batch Gradient Descent. Depending on the amount of data, we make a trade-off between the accuracy of the parameter update and the time it takes to perform an update. 

Reference: https://ruder.io/optimizing-gradient-descent/

Gradient Descent Variants

Gradient descent methods use the slope of the surface. This will not necessarily point directly towards the extreme point. Local steepest direction may not be the same with the global optimum direction. 

Notes about gradient descent

Suppose you have built a neural network. You decide to initialize the weights and biases to be zero. Which of the following statements is true?

The training of BERT models follows a standard iterative optimization procedure used for deep neural networks. First, a large collection of training data is gathered. During each iteration, a random batch of these samples is selected, and the cumulative loss, $$\mathrm{Loss}_{\mathrm{BERT}}$$, is computed over the batch. Next, the model's parameters are updated to minimize this loss using an optimization algorithm like gradient descent or one of its variants. This cycle continues until a specific stopping condition is met, such as the convergence of the training loss.

BERT Training Process

To build a formal mathematical system for learning, machine learning algorithms rely on objective functions, which are formal mathematical measures that quantify how well or poorly a model is performing its task. These functions provide the fundamental evaluation metric that optimization algorithms seek to improve.

Objective Function

Distributed training is an approach used when a single processor or GPU lacks the computational capacity or memory to process large amounts of training data. By distributing the workload across multiple processors, optimization algorithms like stochastic gradient descent can aggregate computations. For example, training across $$1,024$$ GPUs with a small minibatch size of $$32$$ per GPU results in an aggregate minibatch of $$32,000$$ observations, dramatically accelerating training times for massive neural networks.

Distributed Training

If all parameters of a hidden layer are initialized to a constant, such as $$\mathbf{W}^{(1)} = c$$, every hidden unit will receive the same inputs and parameters, producing identical activations during forward propagation. Consequently, during backpropagation, the gradients of the output with respect to the parameters $$\mathbf{W}^{(1)}$$ will all take the exact same value. Because gradient-based algorithms like minibatch stochastic gradient descent update the parameters using these uniform gradients, all elements of $$\mathbf{W}^{(1)}$$ will continue to have identical values after every iteration. The hidden layer will thus behave as if it has only a single unit, failing to realize the network's expressive power.

The Problem with Constant Initialization

A feedforward network with a single layer is suﬃcient to representany function, but the layer may be infeasibly large and may fail to learn and generalize correctly. In many circumstances, using deeper models can reduce the number of units required to represent the desired function and can reduce the amount of generalization error.

As is shown in the figure, empirical results show that deeper networks generalize better when used to transcribe multidigit numbers from photographs of addresses. Data from Goodfellow et al. (2014d). The test set accuracy consistently increases with increasing depth.


Effect of Depth for Neural Networks

The depth of a model can be measured in two main approaches:
- Analyzing the length of sequential pathway of an input to the output. The depth can vary by the definition of a unit operation. The figure below illustrates how a logistic regression can be viewed as a model with a depth of 3 or 1.
- Analyzing how the concepts are related to each other.

Measuring the depth of the model

For a single neuron example: you want to train a deep network without the weights exploding or vanishing.

Example of Weight Initialization 

Symmetry breaking refers to a requirement of initializing machine learning models like neural networks.

When a neural network model has weights, all initialized to the same value, it can be difficult or impossible for the weights to differ as the model is trained. This is known as the “symmetry” problem.

Initializing the model to small random values breaks the symmetry and allows different weights to learn independently of each other.

Symmetry Breaking in Deep Learning


To prevent the gradients of the network’s activations from vanishing or exploding, we will stick to the following rules of thumb:

- The mean of the activations should be zero.
- The variance of the activations should stay the same across every layer.

Under these two assumptions, the backpropagated gradient signal should not be multiplied by values too small or too large in any layer.

Ensuring zero-mean and maintaining the value of the variance of the input of every layer guarantees no exploding/vanishing signal

How to Initialization Weights to Prevent Vanishing/Exploding Gradients

The longest part of the development of a deep learning model is that of the training stage. However, if the problem that is being tackled has already been studied and worked on by someone else and the model has been released to the public including the trained weights then a technique to substantially increase the training process is to utilize transfer learning.

Transfer Learning in Deep Learning

In multi-task learning, the goal is to try to have one neural network classify/predict multiple outputs at the same time, with each of the tasks helping in the execution of the other tasks, i.e., learning from multiple tasks. This contrasts with transfer learning where the tasks are done sequentially, with the previous task helping in the execution of the next.

Multi-task Learning in Deep Learning

When analyzing the scale distribution of an output $$o_i$$ for a fully connected layer without nonlinearities, the output is computed as $$o_i = \sum_{j=1}^{n_	extrm{in}} w_{ij} x_j$$. Assuming the inputs $$x_j$$ and weights $$w_{ij}$$ are drawn independently with a mean of $$0$$ and variances of $$\gamma^2$$ and $$\sigma^2$$ respectively, the expected value $$E[o_i]$$ is $$0$$. We can compute the variance as $$	extrm{Var}[o_i] = E[o_i^2] - (E[o_i])^2 = \sum_{j=1}^{n_	extrm{in}} E[w^2_{ij} x^2_j] - 0 = \sum_{j=1}^{n_	extrm{in}} E[w^2_{ij}] E[x^2_j] = n_	extrm{in} \sigma^2 \gamma^2$$. Note that the distribution does not have to be Gaussian, but the mean and variance must exist. To keep this variance fixed during forward propagation and prevent it from changing across layers, the initialization must satisfy the condition $$n_	extrm{in} \sigma^2 = 1$$.

Variance of Layer Output in Forward Propagation

When building a neural network, if a specific parameter initialization method is not explicitly defined by the user, the deep learning framework will apply a default random initialization method. This default approach, such as drawing weight values from a standard normal distribution, is often sufficient and works well in practice for models with moderate problem sizes.

Default Random Initialization

Xavier initialization, named after its creators Glorot and Bengio (2010), is a standard technique designed to mitigate vanishing and exploding gradients by carefully setting the initial weights of a neural network layer. To balance the variance during both forward and backward propagation, it typically samples weights from a Gaussian distribution with a mean of $$0$$ and a variance of $$\sigma^2 = \frac{2}{n_	extrm{in} + n_	extrm{out}}$$, where $$n_	extrm{in}$$ and $$n_	extrm{out}$$ represent the number of inputs and outputs of the layer respectively. While the underlying assumption of linear activations is often violated in practice, this initialization method has proven highly effective.

Learn Before

Related

Learn After