Multi-Layer perceptron

Properties

1. Perceptron: Single neuron.
2. One-layer neural network: Putting perceptrons side by side.
3. Multi-layer neural network (MLP): Stacking one one-layer NN upon the other.
4. Universal approximation property: An MLP can represent any function.

Multi-Layer perceptron

Network function

\[ \begin{align} h({\bf{x}}) =& g \left ( w_1 h_1({\bf{x}}) + w_2 h_2({\bf{x}}) + c \right ) \\ =& g \left ( w_1 g(\theta_1 x_1 + \theta_2 x_2 + b_1) + w_2 g(\theta_3 x_1 + \theta_4 x_2 + b_2) + c \right ) \end{align} \]

Multi-Layer perceptron

Multi-Layer perceptron

Properties

1. Boolean approximation: An MLP of one hidden layer can represent any boolean function exactly.
2. Continuous approximation: An MLP of one hidden layer can approximate any bounded continuous function with arbitrary accuracy.
3. Arbitrary approximation: An MLP of two hidden layers can approximate any function with arbitrary accuracy.

A simple model:

\(y = w x \)

• We have a regression problem and want to learn a model.
• This means finding the optimal parameter \(w\).
• We use the squared error as loss function.

Error function

Derivative

• Because the error function is continuous, a small change in \(w\) can only result in a small change in \(e\).
• This could be expressed as:
  
  \[ f(w + \epsilon_w) = e + \epsilon_e \]
• Because the function is smooth, when \(\epsilon_e\) is small enough:
  
  \[ f(w + \epsilon_w) = e + a * \epsilon_w \]
• The previous linear approximation is valid, only in the \(\epsilon\)-neighborhood of \(w\), i.e, if we are close enough to \(w\).
• The slope of this linear approximation is called the derivative.

Derivative

Derivative

• A positive slope means the function increases as we increase \(w\).
• Similarly, a negative slope negative slope means the function increases when we decrease \(w\).
• If the derivative is zero, there is a local optimum.
• Therefore, a good strategy to find the optimum is to move \(x\) in the oppossite direction to the sign of its derivative at the current point.
• This is what gradient descent, a popular optimization algorithm, uses to implement its update rule as:
  
  \[ w = w - \mu f'(w) \] where \( \mu \) is a learning rate parameter.

Gradient descent

Gradient

Definition and interpretation

The gradient of a function \( J(\theta_1,\dots,\theta_d) \) is a vector-value function defined as:


\[ \nabla J(\theta_1,\dots,\theta_d) = < \frac{\partial J}{\partial \theta_1}(\theta_1,\dots,\theta_d), \dots,\frac{\partial J}{\partial \theta_d}(\theta_1,\dots,\theta_d)> \]

1. The gradient of a multi-variable function has a component for each direction.
2. The gradient points in the direction of greatest increase.

Gradient descent

Finding the optimum of the loss function

Gradient descent: A local minimization method based on updating the parameters of a function \( J(\theta_1,\dots,\theta_d) \) in the opposite direction to its gradient.

A parameter \( \mu \) is used to indicate the learning rate of the algorithm (the size of the step taken to reach to local optimum)

Derivative of a composite function

• Since our network function is a a composite function, we need to compute its derivative applying the chain rule.
• Chain rule:
  
  \[ h'(x)= \frac{d}{dx}[g(f(x))] = g'(f(x)) f'(x) \]

Backpropagation

Characteristics

• Backpropagation provides a computationally efficient method for evaluating the partial derivatives of all the weights of the neural network with respect to the output.
• Gradients are computed by first estimating the error in each layer of the network.
• Gradients are then used by the optimization algorithms (i.e., variants of gradient descent) to update the weights incrementally.
• Backpropagation reuses the errors of the outer (closer to the output) layers to compute the errors of the inner layers in a more efficient way.

Backpropagation

Steps

1. Feed-forward computation: The network is used for processing the inputs and the error between predictions and target values is computed.
2. Backpropagation of the error: The error is backpropagated through the network. For every weight, the partial derivatives are computed.
3. Weight updates: The partial derivatives are used to update the weights.

MLP Backpropagation

Optimization methods for deep neural networks

Finding the optimum of the loss function

Optimization is involved in several aspects of machine learning algorithms.

Of all the optimization problems involved in deep learning, the most difficult is neural network training.

Optimization is also relevant to the efficiency of the DNN learning algorithm.

We focus on the optimization problem of finding the parameters \( \Theta \) of a neural network that significantly reduce a (possibly regularized) loss function \( J(\Theta) \).

Gradient descent

Finding the optimum of the loss function

Gradient descent algorithms can be grouped in three classes according to the way the gradient is used for the updates:

1. Batch gradient descent.
2. Stochastic gradient descent (SGD).
3. Mini-batch gradient descent.

Gradient descent variants

Batch gradient descent

To perform one parameter update, computes the gradient of \(J\) using all the points the dataset as:


\[ \theta = \theta - \epsilon \nabla_{\theta} J(\theta) \]

1. Guaranteed to converge to the global minimum for convex functions and to local minimum for non-convex functions.
2. Not very efficient since for performing a single update the gradients of the whole dataset are evaluated.

Gradient descent variants

Stochastic gradient descent (SGD)

A parameter update is performed for each point \(x^i\) and label \(y^i\) as:


\[ \theta = \theta - \epsilon \nabla_{\theta} J(\theta;x^i,y^i) \]

1. Usually much faster than batch gradient descent.
2. Can be used to learn online.
3. Convergence to local minimum is not guaranteed.

Gradient descent variants

Mini-batch gradient descent

A parameter update is performed for each mini-batch of \(n\) points \( (x^i,\dots,x^{i+n})\) and labels \((y^i,\dots,y^{i+n})\) as:


\[ \theta = \theta - \epsilon \nabla_{\theta} J(\theta; (x^i,\dots,x^{i+n}),(y^i,\dots,y^{i+n})) \]

1. Combines characteristics of batch gradient descent and SGD.
2. Can make use of highly optimized matrix optimizations.
3. Nevertheless, it does not guarantee a good convergence.
4. Very sensitive to the learning rate \( \epsilon \).
5. It can be trapped in local optima, particularly saddle points.

(Mini-batch) stochastic gradient descent

Advanced gradient descent methods

Momentum

• A fraction \( \alpha \) of the update vector of the past time step is added to the current vector as:
  
  
  \[ v_t = \alpha v_{t-1} - \epsilon \nabla_{\theta} J(\theta) \\ \theta = \theta + v_t \]
• Helps accelerate SGD in the relevant directions and dampens oscillations.
• The larger \(\alpha \) is relative to \(\epsilon\), the more previous gradientes affect the current direction.

Momentum

Advanced gradient descent methods

Nesterov accelerated gradient (NAG)

• Computes an approximate prediction of the parameters in order to calculate the gradient w.r.t. the approximate future position of the parameters.
• The updates are defined as:
  
  
  \[ v_t = \alpha v_{t-1} - \epsilon \nabla_{\theta} J(\theta + \alpha v_{t-1}) \\ \theta = \theta + v_t \]

Nesterov accelerated gradient (NAG)

Adagrad