Gradient descent
Before the adaptive learning rate methods were introduced, the gradient descent algorithms including Batch Gradient Descent (BGD), Stochastic Gradient Descent (SGD) and mini-Batch Gradient Descent (mini-BGD, the mixture of BGD ans SGD) were state-of-the-art. In essence, these methods try to update the weights \theta of the network, with the help of a learning rate \eta, the objective function J(\theta) and the gradient of it, \nabla J(\theta). What all gradient descent algorithms and its improvements have in common, is the goal of minimizing J(\theta) in order to find the optimal weights \theta.
The simplest of the three is the BGD.
\theta = \theta - \eta \cdot \nabla_{\theta} J(\theta)
It tries to reach the minimum of J\theta), by subtracting from \theta the gradient of J(\theta) (refere to Figure 3 for a visualization). The algorithm always computes over the whole set of data, for each update. This makes the BGD the slowest and causes it to be unable to update online. Additionally, it performs redundant operates for big sets of data, computing similar examples at each update and it converges to the closeset minimum depending on the given data data, resulting in potential suboptimal results.
An often used algorithm is the SGD.
\theta = \theta - \eta \cdot \nabla_{\theta}J(\theta; x^{(i)}; y^{(i)})
Contrary to BGD, SGD updates for each training example (x^{(i)}; y^{(i)}), thus updating according to a single example step. Furthermore, this fluctuation enables the SGD to jump to minima farther away, potentially reaching a better minimum. But thanks to this fluctuation, SGD is also able to overshoot. This can be counteracted by slowly decreasing the learning rate. In the exemplary code shown in Figure 2, a shuffle function is additionally used in the SGD and mini-BGD algorithm, compared to the BGD. This is done, as it is often preferable to avoid meaningful order of the data and thereby avoid bias of optimization algorithm, although sometimes better results can be achieved with data in order. In this case the shuffle operation is to be removed.
Lastly, there is the mini-BGD.
\theta = \theta - \eta \cdot \nabla_{\theta} J(\theta;x^{(i:i+n)};y^{(i:i+n)})
The mini-BGD updates for every mini-batch of n training examples. This leads to a more stable convergence, by reducing the variance of the parameters. When people talk abput a SGD algorithm, they often refer to this version.
batch gradient descent (BGD) | stochastic gradient descent (SGD) | mini-batch gradient descent (mini-BGD) |
---|
for i in range (nb_epoches): params_grad = evaluate_gradient(loss_function, data, params params = params - learning_rate * params_grad | for i in range(np_epochs): np.random.shuffle(data) for example in data: params_grad = evaluate_gradient(loss_function, example, params params = params - learning_rate * params_grad | for i in range(np_epochs): np.random.shuffle(data) for batch in get_batches(data, batch_size=50): params_grad = evaluate_gradient(loss_function, batch, params params = params - learning_rate * params_grad |
Figure 2: (1) Pseudo code of the three gradient descent algorithms
2 Kommentare
Unbekannter Benutzer (ga29mit) sagt:
26.Januar 2017All the comments are SUGGESTIONS and are obviously highly subjective!
Form comments:
Corrections:
Adaptive learning rate methodes are optimazation of gradient descent methodes, with the goal of minimizing the objective function of a network, by using the gradient of the function and the parameters of the network.
Adaptive learning rate methods are an optimization of gradient descent methods with the goal of minimizing the objective function of a network by using the gradient of the function and the parameters of the network.
Before the adaptive Learning Rate Methodes came the gradient descent algortihms, Batch Gradient Descent(BGD), Stochastic Gradient Descent (SGD) and the mixture of them both, mini-Batch Gradient Descent (mini-BGD).
Before the adaptive Learning Rate Methods were introduced, the gradient descent algorithms Batch Gradient Descent(BGD), Stochastic Gradient Descent (SGD) and the mixture of them both, mini-Batch Gradient Descent (mini-BGD) were state-of-the-art
The simpelst of the three is the BGD.
The simplest of the three is the BGD.
data, for eeach update.
data, for each update.
Additionally it performes redundant operates for big sets of data, computing similar examples every update and it converges to the closeset minima the data is placed near, resulting in potential suboptimal local minima.
Additionally, it performs redundant operations for big sets of data, computing similar examples every update and it converges to the closest minimum in a neighborhood of the given, resulting in potentially suboptimal local minima.
Furthermore with this fluctuation, SGD is able to jump to minima farther away, potentialy reaching a better minimum
Furthermore, this fluctuation enables SGD to jump to minima further away, potentially reaching a better minimum.
This is done, as it is often preferable to avoid meaningful order of the data, to avoid bias of optimazation algorithm, although sometimes better results can be achieved with data in order. In this case the shuffle operaten is to be removed. Lastly there is the mini-BGD.
This is done, as it is often preferable to avoid meaningful order of the data and thereby avoid bias of the optimization algorithm, although sometimes better results can be achieved with data in order. In this case the shuffle operation has to be removed. Lastly, there is the mini-BGD.
Often, if it is talked about an SGD algorithm, this one is meaned instead.
When people talk about an SGD algorithm, they often actually refer to this version.
As the next step to gradient descent algorithms there are the adaptive gradient descent optimization algorithm or adaptive learning rate methodes. Below, a few popular algorithms of this kind are described.
As the next step to gradient descent algorithms there are the adaptive gradient descent optimization algorithms or adaptive learning rate methods. Below a few popular algorithm of this kind are described.
Momentum can be seen as a evolution of the SGD.
Momentum can be seen as an evolution of the SGD.
Momentum circumevents that with adding the update vectore of the time step before an multipliing it with a γ
Momentum circumvents that with adding the update vector of the time step before an multiplying it with a γ
Nesterov accelerated gradient can be seen as a further enhancment to Momentum.
Nesterov accelerated gradient can be seen as a further enhancement to Momentum.
This algortihm adds a guess of the next stepp, in the form of the term −γvt−1
This algorithm adds a guess of the next step, in the form of the term −γvt−1
Using the same γ γ = 0.9 a comparisen in the first two steps of Momentum and Nesterov accelerated gradient can be viewed in Figure 2. The additional term results in a consideration of the error of the previos step, accelarating the progress compared to Momentum.
Using the same γ γ = 0.9, a comparison of the first two steps of Momentum and Nesterov accelerated gradient can be found in Figure 2. The additional term results in a consideration of the error of the previous step, accelerating the progress compared to Momentum.
Figure 2:[1] Comparison of Momentum (blue) and Nesterov accelerated gradient (green). The green arrow corresponds to the vector addition of the brown arrow, represented in the term γvt−1, and the red arrow, represented by the term η∇θJ(θ−γvt−1)
i θi seperatly during time each time step t.
Unbekannter Benutzer (ga73fuj) sagt:
30.Januar 2017General suggestions:
Corrections: