January 31, 2020 — 31 min
Deep learning is taking off for three main reasons:
- Instinctive features engineering: while most of machine learning algorithms require human expertise for the feature engineering and extraction, deep learning handles automatically the choice of variables and their weights
- Huge Datasets: the continuous collection of data has led to large databases which allow deeper neural networks
- Hardware evolution: the new GPUs, for Graphical Process Units, allow faster algebraic calculation which is the core base of DL
In this blog, we will focus mainly on the Multi-Layer Perceptron -MLP- where we will detail the mathematical background behind the success of deep learning and explore the optimization algorithms used to improve its performances.
The summary is as follows:
- Learning algorithm
- Parameter Initialization
- Forward - Backpropagation
- Activation functions
- Optimization algorithm
It is a bloc of mathematical operations linking between entities
Let’s consider the problem where we estimate the price of a house based on its size, it can be schematized as follows:
When including more description about the house by adding more variables, the graph becomes as follow:
Each neuron is divided into two main blocks:
- Computation of
zusing the inputs :
- Computation of
a, which is equal to y at the output layer, using z
weights, is the
biasand is said to be the
In general, neural networks better known as MLP, for ‘Multi Layers Perceptron’, is a type of direct formal neural network organized into several layers in which information flows from the input layer to the output layer only.
Each layer consists of a defined number of neurons, we distinguish :
The input layer
The hidden layers
The output layer
The following graph represents a neural network with 5 neurons at the input, 3 in the first hidden layer, 3 in the second hidden layer and 2 out.
Some variables in the hidden layers can be interpreted based on the input features: in the case of the house pricing and under the assumption that the first neuron of the first hidden layer pays more attention to the variables et , it can be interpreted as the quantification of the family size of the house for instance.
In most DL problems, we tend to predict an output y using a set of variables X, in this case, we suppose that for each row of the database we have the corresponding prediction , thus the labeled data.
Applications: Real Estate, Speech Recognition, Image Classification …
The used data can be:
- Structured: explicit databases with features well defined
- Unstructured: Audio, Image, Text, …
Deep learning in real life is the approximation of a given function . This approximation is possible and accurate thanks to the following theorem:
A multi-layer perceptron with a single hidden layer containing a finite number of neurons can approximate any continuous function on compact subsets of .
The class of deep neural networks is a universal approximator the activation function is not polynomial.
In finite dimension, a set is said to be compact if it is closed and bounded. Visit this link for more details.
The main take-out of this algorithm is that deep learning allows solving any problem which can be mathematically expressed
In any machine learning project in general, we divide our data into 3 sets:
- Train set: used to train the algorithm and construct batches
- Dev set: used to finetune the algorithm and evaluate bias and variance
- Test set: used to generalize the error/precision of the final algorithm
The following table sums up the repartition of the three sets according the size of the data set :
Standard deep learning algorithms require a large dataset where the number of samples is around lines.
Now that the data is ready we will see in the next section the training algorithm.
Usually, before splitting the data, we also normalize the inputs, a step detailed later in this article.
Learning in neural networks is the step of calculating the weights of the parameters
associated with the various regressions throughout the network. In other words, we aim to find the best parameters that give the best prediction/approximation , starting from the input , of the real value .
For this, we define an objective function called the
loss function and denoted
J which quantifies the distance between the real and the predicted values on the overall training set.
We minimize J following two major steps:
Forward Propagation: we propagate the data through the network either in entirely or in batches, and we calculate the loss function on this batch which is nothing but the sum of the errors committed at the predicted output for the different rows.
Backpropagation: consists of calculating the gradients of the cost function with respect to the different parameters, then apply a descent algorithm to update them.
We iter the same process a number of times called
After defining the architecture, the learning algorithm is written as follows:
- Initialization of the model parameters, a step equivalent to injecting noise into the model.
Fori=1,2…N: (N is the number of epochs)
- , Compute the predicted value of through the neural network:
- Evaluate the function : where m is the size of the training set, θ the model parameters and the cost function
- Apply a descent method to update the parameters :
The cost function evaluates the distances between the real and predicted value on a single point.
The first step after defining the architecture of the neural network is parameter initialization. It is equivalent to injecting initial noise into the model’s weights.
- Zero initialization: one can think of initializing the parameters with 0’s everywhere i.e . Using the forward propagation equations, we note that all the hidden units will be symmetric which penalizes the learning phase.
- Random initialization: it’s an alternative commonly used and consists of injecting random noise in the parameters. If the noise is too large, some activation functions might get saturated which might later affect the computation of the gradient.
Two of the most famous initialization methods are:
Xavier’s: it consists of filling the parameters with values randomly sampled from a centered variable following the normal distribution .
Glorot’s: same approach with a different variance: .
where is the number of nodes in the layer.
Before diving into the algebra behind deep learning, we will first set the annotation which will be used in explicitting the equations of both the forward and the backpropagation.
The neural network is a sequence of
regressions followed by an
activation function. They both define what we call the forward propagation. and are the learned parameters at each layer .
The backpropagation is also a sequence of algebraic operations carried out from the output towards the input.
Let us consider a neural network having
L layers as follows:
We consider the node of the hidden layer denoted .
It’s computed using the all the neurons of the previous layer as follows:
In general, considering the node of the layer we have the following equations:
with being the number of neurons in the layer and is the transpose of the matrix .
Finally, we denote:
Let us consider the prediction of the output of a single row data frame, denoted , through the neural network We set , at each layer , we compute:
Until , where is the number of layers
When dealing with a -row data set, repeating these operations separately for each line is very costly.
We have, at each layer :
We can use linear algebra to parallelize it as follows:
Considering the number of neuron in the layer:
The parameter uses broadcasting to repeat itself through the columns. This can be summarized in the following graph:
The backpropagation is the second step of the learning, which consists of injecting the error committed in the prediction (forward) phase into the network and update its parameters to perform better on the next iteration. Hence, the optimization of the function , usually through a descent method.
Most of the descent methods require the computation of the gradient of the loss function denoted .
In a neural network, the operation is carried out using a computational graph which decomposes the function into several intermediate variables.
Let us consider the following function:
The main objective is to calculate in where:
Let We carry out the computation using two passes:
Forward propagation: computes the value of from inputs to ouput:
- Backpropagation: recursively apply chain rule to compute gradients from output to inputs:
Mathematicaly, we compute the gradients of the cost function, , w.r.t the architecture’s parameters and . For a given parameter , we set and we have at the layer:
where is the element wise multiplication.
We recursively apply these equations for
When carrying out the backpropagation, an additional checking is added to make sure that the algebric computations are correct. Algorithm:
- We first reshape and stack all the parameters and into one vector denoted
- We carry out the same manoeuvre for their derivatives and and we denote the resulting vector.
- , We compute: an approximation of (where is very small )
- We check the following quantity:
It should be close to the value of , an error is suspected when the value of the quantity is near .
We can sum up the Forward and Backward propagation in the following block:
- Parameters, denoted , are the elements which we learn through the iterations and on which we apply backpropagation and update: and
Hyperparameters are all the other variables we define in our algorithm which can be tunned in order to improve the neural network:
- Learning rate
- Number of iterations
- Choice of activation functions
- Number of layers
- Number of units in each layer
Activation functions are a kind of transfer functions that select the data propagated in the neural network. The underlying interpretation is to allow a neuron in the network to propagate learning data (if it is in a learning phase) only if it is sufficiently excited.
Here is a list of the most common functions:
Remark: if the activation functions are all linear, the neural network is precisely equivalent to a simple linear regression
Let us consider a neural network denoted by . The real objective to optimize is defined as the expected loss over all the corpora:
Where is an element from a continuous space of observables to which correspond a target and being the marginal probability of observing the couple .
Since we can not have all the corpora and hence we ignore the distribution , we restrict the estimation of the risk on a certain dataset well representative of the overall corpora and consider all the cases equiprobable.
In this case: and where m is the size of the representative corpora. Hence, we iteratively optimize the loss function defined as follows:
Plus we can assert that:
Before optimizing the loss function, we need to normalize the inputs in order to speed up the learning. In this case, becomes tighter and more symmetric which helps gradient descent to find the minimum faster and thus in fewer iterations.
Standard data is the commonly used approach which consists of subtracting the mean of the variables and dividing by their standard deviation. Considering , the following image illustrates the effect of normalizing the input on the contour lines of -standard data on the right-:
Let X be a variable in our database, we set:
In general, we tend to construct a
differentiable function where any local minima is a global one. Mathematically speaking finding the global minimum of a convex function is equivalent to solving the equation , we denote its solution.
Most of the used algorithms are of kind with an initial guess, where is the step size and the descent direction.
We can assert that:
Since we seek to have then we need as negative as possible, meaning .
- is given
for stopping criterion:
Choice of :
- a fixed step size
- follows a certain decay law (see Learning rate decay section)
This technique consists of dividing the trainning set to batches , the training algorithm is as follows:
- Carry out forward propagation on
- Compute the cost function normalized on the size of the batch
- Carry out the backpropagation using
- Update the weight and
Choice of the mini-batch size:
- Small number of rows lines
- Typical size: power of 2 which is good for memory
- Mini-batch should fit in CPU/GPU memory
Remark: in the case where there is only one data line in the batch, the algorithm is called stochastic gradient descent
A variant of gradient descent which includes the notion of momentum, the algorithm is as follows:
- Initialize ,
On iteration k:
- Compute and on the current mini-batch
Update the parameters:
() are hyperparameters. Since is calculated on a mini-batch, the resulting gradient is very noisy, this exponentially weighted averages included by the momentum give a better estimation of derivatives.
Root Mean Square prop is very similar to gradient descent with momentum, the only difference is that it includes the second-order momentum instead of the first-order one, plus a slight change on the parameters’ update:
- Initialize ,
On iteration k:
- Compute and on the current mini-batch
Update the parameters:
() are hyperparameters and assures numerical stability ()
Adam is an adaptive learning rate optimization algorithm designed specifically for training deep neural networks. Adam can be seen as a combination of RMSprop and gradient descent with momentum. It uses square gradients to set the learning rate at scale as RMSprop and takes advantage of momentum by using the moving average of the gradient instead of the gradient itself as the gradient descends with momentum. The main idea is to avoid oscillations during optimization by accelerating the descent in the right direction, say dW, using the moment: if the descent is slow so and are small, a choice of the larger step solves the problem, moreover by dividing by , the optimization is accelerated further. The algorithm of the Adam optimizer is the following:
- Initialize: , , , ;
On iteration k:
- Computation of and through backpropagation
The main objective of the learning rate decay is to slowly reduce the learning rate over time/iterations. It finds justification in the fact that we afford to take big steps at the beginning of the learning but when approaching the global minimum, we slow down and thus decrease the learning rate. There exist many learning rate decay laws, here are some of the most common:
- We decrease the learning rate by epoch i.e 1 pass through the data (all the mini-batches):
- We can exponentially decrease the learning rate:
- We can also consider the following decay law:
(, , ) are hyperparameters
When training a neural network, it might suffer from:
- High bias: or underfitting, where the network fails to find the path in the data, in this case, is very high the same as . Mathematically speaking, when performing cross-validation; the mean of on all the considered folds is high.
- High variance or overfitting, the model fits perfectly on the training data but fails to generalize on unseen data, in this case, is very low and is relatively high. Mathematically speaking, when performing cross-validation; the variance of on all the considered folds is high.
Let’s consider the dartboard game, where hitting the red target is the best-case scenario. Having a low biais (first line) means that on average we are close to the goal. In case, of a low variance the hits are all concentrated around the target (the variance of the hits’ distribution is low). When the variance is high, under the assumption of a low bias, the hits are spread out but still around the red circle. Vice-versa, we can define the high bias with a low/high variance.
Mathematically speaking, let be a true regression function: where . We fit a hypothesis with MSE and consider be a new data point, , the expected error can be defined by and we can assert that:
A trade-off must be found between variance and bias to find the optimum complexity of the model either by using the criteria or using cross-validation. Here is a simple schema to follow to solve bias/variance issues:
Regularization is an optimization technique which prevents overfitting. It consists of adding a term in the objective function to minimize as follows:
- L1 regularization: becomes:
- L2 regularization: becomes:
is the hyperparameter of the regularization
- Backpropagation and regularization The update of the parameters during backpropagation depends on the the gradient , to which is added a new regularization term. In L2 regularization, it becomes as follows:
Considering , minimizing the cost function leads to weak values of parameters because of the term which simplifies the network and makes more consistent, hence less exposed to overfitting.
Roughly speaking, the main idea is to sample a uniform random variable,
for each layer for each node, and have chance of keeping the node and of removing it which diminishes the network.
The main intuition of dropout is based on the idea that the network shouldn’t rely on a specific feature but should instead spread out the weights!
Mathematically speaking, when dropout is off and considering the node of the layer, we have the following equations:
When dropout is on, the equations become as follows:
Where is a hyperparameter.
This technique is quite simple and consists of stopping the iteration around the area when and start seperating:
The computation of gradients suffers from two major problems: gradient vanishing and gradient exploding. To illustrate both of the situations, let’s consider a neural network where all the activation functions are linear, and , thus:
We note that will explode exponentially as a function of the depth L. If we use instead of then will vanish exponentially as well.
The same issue occurs with gradients.