sKAdam: An improved scalar extension of KAdam for function optimization

2.1Variants

The gradient descent algorithm has three main variants: Stochastic gradient descent (SGD), Batch gradient descent (Batch GD a.k.a. Vanilla GD) and Mini-batch gradient descent (Mini-batch GD); which differs in the amount of data used to compute the gradient.

Stochastic gradient descent performs a parameters update for each pattern x(i) and label y(i) in the training-set.

Usually this variant is more accurate while it is updating the parameters, but it takes longer to finish the optimization because of the number of updates that the algorithm performs.

Batch gradient descent computes the gradient for all the patterns in the training-set, then it performs a parameters update using the average direction from all the gradients.

Compared to SGD this variant is faster when it is updating the parameters. However, this speed improvement directly affects the accuracy of the parameter updates.

Mini-batch gradient descent divides the training-set in mini-batches and performs a parameters update with each mini-batch.

This variant has the best from both worlds; it combines part of the accuracy from SGD and the speed improvement from Batch GD. Theoretically, there is an optimal mini-batch size where the performance and the computational complexity are balanced.

2.2Gradient-based optimizers

There are different methods designed in order to accelerate and improve the gradient descent algorithm and its variants. Each state-of-the-art method present its own strengths and weaknesses, see [10] for further details with a deeper overview.

From here, let J be a stochastic objective function with model’s parameters θt∈ℝd and with gt∈ℝd the gradient w.r.t the parameters from the objective function at the time-step t.

Momentum[9] introduces the idea of using a fraction γ of the past update vector vt-1 as an impulse for the current update vector vt.

The momentum term drives the parameters into a relevant direction, accelerating the learning process and dampening oscillations on the parameters update. However, the same term could present a blind-rolling behaviour on the algorithm, because it keeps accumulating momentum from the previous update vectors.

AdaGrad[1] solved the blind-rolling behaviour by using adaptive learning rates for each parameter.

In Eq. (6), Gt is a diagonal matrix with the accumulated past square gradients up to the time step t.

One of the best features from AdaGrad is that it reduce the importance of tuning the learning rate manually. Nevertheless, this main advantage is also a problem at a certain point of the optimization because the learning rate start to shrink and eventually it will be infinitesimal, hence the algorithm will be no longer able to keep learning.

Adadelta[13] is an extension of AdaGrad, which solves the problem of the radically diminishing learning rates by restricting the accumulated past squared gradients to some fixed size window.

where, RMS stands for Root Mean Square. In Eq. (7), the numerator is used as an acceleration term by accumulating previous gradients similar to the momentum term, but with a fixed size window. The denominator is related to AdaGrad by saving the squared past gradient information, but with a fixed size window to ensure progress is made later in training.

RMSProp is an unpublished algorithm by Geoffrey Hinton that was reported in the Lecture 6 of his online course [11]. Moreover, this method was developed around the same time that Adadelta, and even with the same purpose of reducing the AdaGrad’s radically diminishing learning rates.

Similar to AdaGrad the RMSProp’s algorithm is storing the past squared gradients, but instead of keep accumulating them over the training, it is using an exponential moving average E⁢[g2]t with ρ as the coefficient for the weighting decrease. On the other hand, in the update rule the ϵ factor is used to ensure algorithmic stability.

Curiously, in the Adadelta’s method derivation in [13], it can be observed that before the second idea of its authors the update parameters rule is just like the update rule from RMSProp; but the authors of Adadelta considered an extra term to make a units correction over the parameters and not the gradient.

Adam[6] is one of the most popular and used optimizers in the training of neural networks. The method is described by its authors as a combinations from the advantages of AdaGrad and RMSProp.

Adam has the best from both worlds, the algorithm is using exponential moving averages over the past gradient (mt) and the past squared gradient (vt), with β1 and β2 as the coefficients for the weighting decrease respectively. Then a correction of these terms have place because they are biases towards zero, thus, the bias-corrected estimates of the first moment (the mean) m^t and second moment (the uncentered variance) v^t are computed. Finally, the Eq. (15) shows the update rule, which uses the ϵ factor to ensure algorithmic stability as in RMSProp.

3.1Scalar Kalman filter

In Eqs (16) to (17) the true state, dynamical model, and measurements are described with vectors and matrices. On the other hand, if the problem described lies in 1-D vector space, then it is represented in terms of scalars and constants. Thus, the equations for the Kalman filter can be rewritten as follows:

where, the matrix operations are replaced with scalar operations and the matrix inverse is replaced with the scalar multiplicative inverse (reciprocal value).

4.1Kalman filter parameters

Similar to the first version of KAdam, the variables ak=qk=hk=1 are set to be equal because the dynamic model is unknown and bk=uk=0 because the control-input is not required. For the rk parameter, instead of using Gaussian white noise rk∼𝒩⁢(0,σ) it was considered that the measurement noise term should be in the range (0,1] and needs to radically diminish over the training epochs, then, it was proposed to use an exponential decay:

where γ is the decay constant, which is suggest to set as a value from 10% to 15% of the total epochs for the training. However, this hyper-parameter can be adjusted according to how long the algorithm should have a higher measurement noise to explore new solutions.

With these considerations, the Eqs (23) to (27) of the scalar Kalman filter for this particular implementation can be rewritten as follows:

4.2sKAdam algorithm

The equations for sKAdam use a K⁢(∙) function, which summarizes the process of the scalar Kalman filters. Even that a 1-D Kalman filter is used for each gradient gt(i) from the loss function, instead of writing the filter for each gradient, all the filters can be vectorized and manipulated with element-wise operations. Hence, the K⁢(∙) function returns all the estimated gradients g^t at the time-step t.

Then the equations for the first Eq. (11) and second Eq. (12) moments estimated from Adam now use the estimated gradient:

and the equations for the bias-corrected first moment estimate Eq. (13), the bias-corrected second moment estimate Eq. (14), and the parameters update rule Eq. (15), they remain the same as in the Adam algorithm.

In Algorithm 1 is shown the pseudocode for sKAdam.

sKAdam our new proposed an optimized extension of KAdamη: Stepsize β1,β2∈[0,1): Exponentially decay rate for the moment estimates γ: Exponentially decay constant for the measurement noise f⁢(θ): Stochastic objective function with parameters θθ0: Initial parameter vector

m0←0Initialize first moment vector v0←0Initialize second moment vector x^0|0←0Initialize state estimates vector k0←0Initialize kalman gains vector p0|0←0Initialize covariances vector t←0Initialize time-step

θ0 not converge t←t+1gt←∇θ⁡ft⁢(θt-1)Get gradients from ft⁢(θt-1) w.r.t. θt-1x^t|t-1←x^t-1|t-1Compute a priori states estimate, Eq. (29) pt|t-1←pt-1|t-1+1Compute a priori covariances, Eq. (30) rt←et/γCompute measurement noise, Eq. (28) kt←(pt|t-1)/(pt-1|t-1+rt)Compute kalman gains, Eq. (31) x^t|t←x^t|t-1+kt⋅(zt-x^t|t-1)Compute a posteriori states estimate, Eq. (32) pt|t←(1-kt)⋅pt|t-1Compute a posteriori covariances, Eq. (33) gt^←xt|t^Set estimated gradients, Eq. (34) mt←β1⋅mt-1+(1-β1)⋅g^tCompute first moment estimate, Eq. (35) vt←β2⋅vt-1+(1-β2)⋅g^t2Compute second moment estimate, Eq. (36) m^t←mt/(1-β1t)Compute bias-corrected first moment estimate, Eq. (13) v^t←vt/(1-β2t)Compute bias-corrected second moment estimate, Eq. (14) θt←θt-1-η⋅m^t/(v^t+ϵ)Update parameters, Eq. (15)

5.1MNIST database classification experiment

The popular classification problem for the hand written numbers. Originally the dataset consists of images of 28 × 28 pixels, thus the problem lies in 784 dimensions. In order to reduce the dimensions of the problem and use a simpler architecture, the dataset was embed into a 2-D vector space (as it can be seen in Fig. 1) using an implementation11 of the t-SNE algorithm [12].

Figure 1.

MNIST 2-D visualization using the t-SNE implementation from scikit-learn.

Figure 2.

MNIST experiment in mini-batch settings – comparison of the loss optimization over the trainings.

For the architectures of the neural networks were set to (10, 10) neurons, hyperbolic tangent and sigmoid as the activation functions respectively. All the algorithms performs the optimization with 60,000 patterns from the transformed dataset over 1,000 epochs.

As a first comparison, the training was run in mini-batch settings to test the improvement in the execution time that sKAdam reaches. Also, the performance in the optimization was tested and the loss reduction of our method was compared against GD, Momentum, RMSProp, Adam, and KAdam.

In Fig. 2 it can be observed the experiment in mini-batch settings. Here, on the left side, it can be seen that sKAdam presents the smoothest descent in comparison with the original KAdam’s algorithm. Furthermore, on the right side of the figure, it can be seen that sKAdam reaches an optimal value near to the epoch 120 and keeps closer to this optimal value until the end of the optimization. On the other hand, the other adaptive learning-rate methods reach similar results until the epoch 500 but with noisy behaviors, which can be undesirable in an on-line training setting where the adapted variables could have a physical interpretation and to present large variations in the values of the variables can represent a risk of damage to the system being controlled.

In a second comparison, the training was run in full-batch settings, where the authors already know that the execution time may not present a considerable difference with the original KAdam’s algorithm and the other optimizers.

Figure 3.

MNIST experiment in full-batch settings – comparison of the loss optimization over the trainings.

Figure 4.

MNIST experiment – last 100 epoch of the trainings.

This time, at the left side of Fig. 3 it can be seen that again sKAdam presents a smoother behavior compared with KAdam. However, on the right side, it can be observed that the adaptive learning-rate methods present similar results, and only RMSprop presents noisy behavior.

In Fig. 4 there is a close up to the dynamics of KAdam and sKAdam in the last 100 iterations of both mini-batch and full-batch trainings. Here, it is clear to see that even when KAdam and sKAdam are similar methods, they present completely different dynamics due to the noise measurement factor considered for each algorithm. As the authors previously mentioned, besides the problem of the execution time, there is another problem in KAdam related to the fixed noise measurement matrix. Which at the early stages of the optimization, this fixed matrix helps to reach new solutions with the estimated gradients as well as present a faster descent, but later in training it makes it harder to reach new solutions and also the converge of the algorithm present a noisy dynamic.

Nevertheless, as it can be observed the sKAdam method shows the importance of the exponential decay included to reduce the noise factor over the optimization.

Table 1 presents a summary of the results obtained over the optimization in both settings. Where it can be seen how even that KAdam and sKAdam are similar algorithms, they present a considerable difference in the execution time using mini-batch settings, which is a consequence of the matrix inverse computed in KAdam vs the simpler calculation of the scalar multiplicative inverse that sKAdam performs. In Table 1, the columns min. loss present the minimum value for the loss function found for each algorithm, the columns min σ2 show the minimum variance, and the columns time the time spent on the execution in seconds units, these values are obtained after executing three times each algorithm.

As it can be seen either in the comparisons and at the Table 1 of the experiment, the adaptive learning-rate methods as RMSProp, Adam, KAdam, and sKAdam present the best performance over the optimization. However, for the other methods, only the execution time is a remarkable feature in the comparison. Therefore in the following experiments, the gradient descent and momentum methods were removed from the comparison results.

In Fig. 5 it can be observed the confusion matrices from all the algorithms in the comparison. These matrices were calculated from the generalization performed with the trained neural networks in full-batch settings and using the test dataset, which contains 10,000 patterns.

Figure 5.

Confusion matrix for MNIST Generalization.

5.2Moon database classification experiment

In order to test the behavior of sKAdam with datasets that present a low noise factor, it was selected this experiment that deals with the classification problem of two interleaving half circles in two dimensions. The dataset contains 10,000 patterns, generated by a function22 from the scikit-learn python package [8].

The loss reduction comparison was run over 3,000 epochs and using a mini-batch size of 256. For the architecture of the neural networks, two layers were used with (10, 1) neurons, hyperbolic tangent and sigmoid as the activation functions respectively.

In Fig. 6, it can be seen again that using mini-batch settings sKAdam presents a smother behavior and is dampening the oscillations that KAdam presents during the training. Thus, sKAdam confirms again that as the authors state out when the exponential decay is used over the measurement noise factor the new method does not present the noisy behavior later in training.

Figure 6.

Moons optimization in mini-batch settings – comparison of the loss reduction over the trainings.

On the other hand, Fig. 7 shows that using full-batch settings there is not a remarkable difference in the performance from all the algorithms.

Figure 7.

Moons optimization in full-batch settings – comparison of the loss reduction over the trainings.

Nevertheless, in the summarize presented on Table 2 it is confirmed that KAdam and sKAdam present a considerable difference in the time taken to optimize even in full-batch settings due to the matrix inverse computed in KAdam vs the simpler calculation of the scalar multiplicative inverse that sKAdam performs. In Table 2, the columns min. loss present the minimum value for the loss function found for each algorithm, the columns min σ2 show the minimum variance, and the columns time the time spent on the execution in seconds units, these values are obtained after executing three times each algorithm.

In Fig. 8 it can be observed the confusion matrices from all the algorithms in the comparison. These matrices were calculated from the generalization performed with the trained neural networks in full-batch settings and using the test dataset, which contains 2,000 patterns.

Figure 8.

Confusion matrix for Moon Generalization.

5.3Iris database classification experiment

One of the best-known dataset for pattern recognition. The problem (obtained from [4]) has four features (sepal length/width and petal length/width) to classify different iris plant species. In the classification, there are three different kinds of iris plants, but only one class is linearly separable from the others and also the latter are not linearly separable from each other. The dataset consists of 150 patterns (112 used for training) with 50 instances per class.

The loss reduction comparison was run over 1,000 epochs and using a mini-batch size of 32. For the architecture of the neural networks, two layers were used with (10, 3) neurons, hyperbolic tangent and sigmoid as the activation functions respectively.

As it can be observed in Fig. 9, this time in the mini-batch settings is where all the algorithms present close result in the loss function.

Figure 9.

Iris optimization in mini-batch settings – comparison of the loss reduction over the trainings.

On the other hand, Fig. 10 shows that in full-batch settings sKAdam presents a smoother behavior compared with RMSProp and KAdam. Moreover, it was able to make a significant change in the decent direction, thus, the algorithm presents a faster descent and a better accuracy in the loss reduction.

Figure 10.

Iris optimization in full-batch settings – comparison of the loss reduction over the trainings.

In Table 3, this time KAdam presents closer achievements in comparison with sKAdam. Nevertheless, in the mini-batch settings, the execution of KAdam takes nine times longer to finish the optimization due to the matrix inverse computed in KAdam vs the simpler calculation of the scalar multiplicative inverse that sKAdam performs. In Table 3, the columns min. loss present the minimum value for the loss function found for each algorithm, the columns min σ2 show the minimum variance, and the columns time the time spent on the execution in seconds units, these values are obtained after executing three times each algorithm.

Therefore, the execution time in KAdam increases as the the mini-batch size decrease. Thus, if its algorithm is used in a problem with a large numbers of patters and the optimization use mini-batch settings or online-settings, the problem of the execution time becomes serious.

Figure 11.

Confusion matrix for Iris Generalization.

In Fig. 11 it can be observed the confusion matrices from all the algorithms in the comparison. These matrices were calculated from the generalization performed with the trained neural networks in full-batch settings and using the test dataset, which contains 38 patterns.

5.4Red wine quality regression/classification experiment

The regression/classification problem [3] for the quality of different wines. As an evaluation for the quality, there are 11 features related to physicochemical tests for each wine sample. The authors of the database shared two datasets related to the quality of different red and white wines. For this experiment, it was used the red wine dataset, which contains 1,599 samples (1,119 used for training).

The loss reduction comparison was run over 1,000 epochs and using a mini-batch size of 256. In the architectures of the neural networks, two layers were used with (20, 1) neurons, hyperbolic tangent and linear as the activation functions respectively. This experiment uses more hidden units with the objective of test the impact in the execution time.

Figure 12.

Red wine optimization in mini-batch settings – comparison of the loss reduction over the trainings.

As Fig. 12 shows, in the mini-batch settings sKAdam presents a smoother and fastest descent compared with the other methods. Moreover, when all the algorithms present problems to reach low values over the loss function, our method was able to find a new and better solution even latter in training.

On the other hand, it can be seen in Fig. 13 that in full-batch settings sKAdam was close to the other methods, but near to the epoch 300 the algorithm find a new solution and it takes the advantage up to the end of the optimization.

Figure 13.

Red wine optimization in full-batch settings – comparison of the loss reduction over the trainings.

It can be seen in Table 4 that the architecture used in this experiment increase dramatically the execution time for the KAdam’s algorithm in both mini-batch and full-batch settings due to the matrix inverse computed in KAdam vs the simpler calculation of the scalar multiplicative inverse that sKAdam performs.

Furthermore, it can be observed that sKAdam does not present this problem and also handles to find new solutions over the loss function almost in the same execution time that the other optimizers.

In Table 4, the columns min. loss present the minimum value for the loss function found for each algorithm, the columns min σ2 show the minimum variance, the columns time the time spent on the execution in seconds units, these values are obtained after executing three times each algorithm. In addition, for this regression/classification experiment the columns r2 score were added, which are the coefficient of determination as the metric for the fit with the test dataset, which contains 400 samples.