Optimization: How to Model an Efficient Learning?

1. Compute its outputs from its inputs (FPROP)

2. Compute gradient vectors at its inputs from gradient vectors at its outputs (BPROP)

An interesting special case: multilayer networks

– Weight matrices:

– Sigmoids + bias:

Stochastic update

– Stochastic gradient:

– The parameters are updated after each presentation of an example

– Full gradient:

– The gradients are accumulated over the whole training set before a parameter

update is performed

A few practical tricks

– BackProp is a simple algorithm, but convergence can take ages if it is

not used properly

– The error surface of a multilayer network is non quadratic and non-

convex, and has often many dimensions.

– There is no miracle technique for finding the minimum. Heuristics

(tricks) must be used.

– Depending on the details of the implementation, the convergence time

can vary by orders of magnitude, especially on small problems.

– Here is a list of some common traps, and some ideas about how to

avoid them.

Stochastic vs Batch update

– Stochastic update is usually MUCH faster than batch update. Especially on

large, redundant data sets.

– Here is why:

– Imagine you are given a training set with 1000 examples.

– Imagine this training set is in fact composed of 10 copies of a set of 100 patterns.

– Batch: the computation for one update will be 10 times larger then necessary

– Stochastic: the redundancy in the training set will be taken advantage of. One

epoch on the large set will be like 10 epochs on the smaller set.

– Batch will be AT LEAST10 times slower than Stochastics

– In real life, repetitions rarely occur, but very often the training examples are

highly redundant (many patterns are similar to one another), which has the

same effect.

– In practice speed differences of orders of magnitude between Batch and

Stochastic are not uncommon.

– Small batches can be used without penalty, provided the patterns in a

minibatch are not too similar.

Stochastic vs Batch update (cont)

Stochastic

– Advantages:

– Much faster convergence on large redundant datasets

– Stochastic trajectory allows escaping from local minima

– Disadvantages:

– Keeps bouncing around unless the learning rate is reduced

– Theoretical conditions for convergence are not as clear as for batch

– Convergence proofs are probabilistic

– It is harder to parallelize than batch

Batch

– Advantages:

– Guaranteed convergence to a local minimum under simple conditions

– Easy convergence proofs

– Disadvantages:

– Painfully slow on large problems

– Despite the long list of disadvantages for Stochastic, that is what most people

use (and rightfully so, at least on large problems).

Mini Batch update

Shuffling the examples

– Rule: at any time, chose the training example with the maximum

information content

– For example

– The one with the largest error

– The one that is maximally different from its predecessors

– A simple trick: (applicable to stochastic gradient on classification

tasks). Shuffle the training set so that successive examples never (or

rarely) belong to the same class.

– A more refined trick: use an “emphasizing” scheme: show difficult

patterns more often than easy patterns. [Whether a pattern is easy or

hard can be determined with the error it produced during the previous

iterations]

– Problem with emphasizing techniques:

– They perturb the distribution of inputs

– The presence of outliers or of mislabeled examples can be catastrophic

Normalizing the inputs

– Each input variable should be sifted so that its mean (averaged over

the training set) is close to 0 (or is small compared to its standard

deviation).

– Here is why:

– Consider the extreme case where the input variables are always positive.

– The weights of neuron in the first hidden layer can only increase together or

decrease together (for a given input pattern the gradients all have the same sign).

– This means that if the weight vector has to change its direction, it will have to do it by

zigzagging (read: SLOW).

– Shifts of the input variables to a neuron introduce a preferred direction

for weight changes, which slows down the learning.

Initializing the weights

– Large initial weights saturate the units, leading to small gradients and slow

learning. Small weights correspond to a very flat area of the error surface

– Assuming the inputs are independent, the expected standard deviation of the

weighted sum is

where is the number of input to the unit, and is the standard deviation of

its incoming weights.

– To ensure that is close to 1, the weights to a unit can be drawn from a

distribution with standard deviation

Choosing learning rates

Equalize the learning speeds

– Each weight (or parameter) should have its own learning rate.

– Some weights may require a small learning rate to avoid divergence,

while others may require a large learning rate to converge at

reasonable speed.

– Because of possible correlations between input variables, the learning

rate of a unit should be inversely proportional to the square root of the

number of inputs to the unit.

– If shared weights are used (as in TDNNs and convolutional networks),

the learning rate of a weight should be inversely proportional to the

square root of the number of connection sharing that weight.

– Learning rates in the lower layers should generally be larger than that

in the higher layers.

– The rationale for many of these rules of thumb will become clearer

later. Several techniques are available to reduce "learning rate

fiddling".

More standard tricks

Momentum

– Increases speed in batch mode. Seems marginally useful but not

indispensable in stochastic mode.

Adaptive learning rates:

– a separate learning rate for each weight is increased if the gradient is

steady, decreased if the gradient changes sign often [Jacobs 88]. This

only works with BATCH.

– a global learning rate is adjusted using line searches. Again, this only

works for BATCH.

Adaptive methods optimization

RMSprop

– The key idea of Root Mean Square Propagation is that the gradient is

normalized by its root-mean-square.

ADAM:

– Adaptive Moment Estimation, which is RMSprop plus momentum.

Reference:

•

Nivdia Deep learning teaching Kit