Gradient descent<\/strong> is an optimization algorithm that follows the negative gradient of an objective function in order to locate the minimum of the function.<\/p>\n A problem with gradient descent is that it can bounce around the search space on optimization problems that have large amounts of curvature or noisy gradients, and it can get stuck in flat spots in the search space that have no gradient.<\/p>\n Momentum<\/strong> is an extension to the gradient descent optimization algorithm that allows the search to build inertia in a direction in the search space and overcome the oscillations of noisy gradients and coast across flat spots of the search space.<\/p>\n In this tutorial, you will discover the gradient descent with momentum algorithm.<\/p>\n After completing this tutorial, you will know:<\/p>\n Let\u2019s get started.<\/p>\n Gradient Descent With Momentum from Scratch This tutorial is divided into three parts; they are:<\/p>\n Gradient descent<\/a> is an optimization algorithm.<\/p>\n It is technically referred to as a first-order optimization algorithm as it explicitly makes use of the first-order derivative of the target objective function.<\/p>\n First-order methods rely on gradient information to help direct the search for a minimum \u2026<\/p>\n<\/blockquote>\n \u2014 Page 69, Algorithms for Optimization<\/a>, 2019.<\/p>\n The first-order derivative<\/a>, or simply the \u201cderivative<\/em>,\u201d is the rate of change or slope of the target function at a specific point, e.g. for a specific input.<\/p>\n If the target function takes multiple input variables, it is referred to as a multivariate function and the input variables can be thought of as a vector. In turn, the derivative of a multivariate target function may also be taken as a vector and is referred to generally as the \u201cgradient<\/a>.\u201d<\/p>\n The derivative or the gradient points in the direction of the steepest ascent of the target function for a specific input.<\/p>\n Gradient descent refers to a minimization optimization algorithm that follows the negative of the gradient downhill of the target function to locate the minimum of the function.<\/p>\n The gradient descent algorithm requires a target function that is being optimized and the derivative function for the objective function. The target function f()<\/em> returns a score for a given set of inputs, and the derivative function f'()<\/em> gives the derivative of the target function for a given set of inputs.<\/p>\n The gradient descent algorithm requires a starting point (x<\/em>) in the problem, such as a randomly selected point in the input space.<\/p>\n The derivative is then calculated and a step is taken in the input space that is expected to result in a downhill movement in the target function, assuming we are minimizing the target function.<\/p>\n A downhill movement is made by first calculating how far to move in the input space, calculated as the step size (called alpha<\/em> or the learning rate<\/em>) multiplied by the gradient. This is then subtracted from the current point, ensuring we move against the gradient, or down the target function.<\/p>\n The steeper the objective function at a given point, the larger the magnitude of the gradient and, in turn, the larger the step taken in the search space. The size of the step taken is scaled using a step size hyperparameter.<\/p>\n If the step size is too small, the movement in the search space will be small and the search will take a long time. If the step size is too large, the search may bounce around the search space and skip over the optima.<\/p>\n Now that we are familiar with the gradient descent optimization algorithm, let\u2019s take a look at momentum.<\/p>\n Momentum is an extension to the gradient descent optimization algorithm, often referred to as gradient descent with momentum<\/strong>.<\/p>\n It is designed to accelerate the optimization process, e.g. decrease the number of function evaluations required to reach the optima, or to improve the capability of the optimization algorithm, e.g. result in a better final result.<\/p>\n A problem with the gradient descent algorithm is that the progression of the search can bounce around the search space based on the gradient. For example, the search may progress downhill towards the minima, but during this progression, it may move in another direction, even uphill, depending on the gradient of specific points (sets of parameters) encountered during the search.<\/p>\n This can slow down the progress of the search, especially for those optimization problems where the broader trend or shape of the search space is more useful than specific gradients along the way.<\/p>\n One approach to this problem is to add history to the parameter update equation based on the gradient encountered in the previous updates.<\/p>\n This change is based on the metaphor of momentum from physics where acceleration in a direction can be accumulated from past updates.<\/p>\n The name momentum derives from a physical analogy, in which the negative gradient is a force moving a particle through parameter space, according to Newton\u2019s laws of motion.<\/p>\n<\/blockquote>\n \u2014 Page 296, Deep Learning<\/a>, 2016.<\/p>\n Momentum involves adding an additional hyperparameter that controls the amount of history (momentum) to include in the update equation, i.e. the step to a new point in the search space. The value for the hyperparameter is defined in the range 0.0 to 1.0 and often has a value close to 1.0, such as 0.8, 0.9, or 0.99. A momentum of 0.0 is the same as gradient descent without momentum.<\/p>\n First, let\u2019s break the gradient descent update equation down into two parts: the calculation of the change to the position and the update of the old position to the new position.<\/p>\n The change in the parameters is calculated as the gradient for the point scaled by the step size.<\/p>\n The new position is calculated by simply subtracting the change from the current point<\/p>\n Momentum involves maintaining the change in the position and using it in the subsequent calculation of the change in position.<\/p>\n If we think of updates over time, then the update at the current iteration or time (t) will add the change used at the previous time (t-1) weighted by the momentum hyperparameter, as follows:<\/p>\n The update to the position is then performed as before.<\/p>\n The change in the position accumulates magnitude and direction of changes over the iterations of the search, proportional to the size of the momentum hyperparameter.<\/p>\n For example, a large momentum (e.g. 0.9) will mean that the update is strongly influenced by the previous update, whereas a modest momentum (0.2) will mean very little influence.<\/p>\n The momentum algorithm accumulates an exponentially decaying moving average of past gradients and continues to move in their direction.<\/p>\n<\/blockquote>\n \u2014 Page 296, Deep Learning<\/a>, 2016.<\/p>\n Momentum has the effect of dampening down the change in the gradient and, in turn, the step size with each new point in the search space.<\/p>\n Momentum can increase speed when the cost surface is highly nonspherical because it damps the size of the steps along directions of high curvature thus yielding a larger effective learning rate along the directions of low curvature.<\/p>\n<\/blockquote>\n \u2014 Page 21, Neural Networks: Tricks of the Trade<\/a>, 2012.<\/p>\n Momentum is most useful in optimization problems where the objective function has a large amount of curvature (e.g. changes a lot), meaning that the gradient may change a lot over relatively small regions of the search space.<\/p>\n The method of momentum is designed to accelerate learning, especially in the face of high curvature, small but consistent gradients, or noisy gradients.<\/p>\n<\/blockquote>\n \u2014 Page 296, Deep Learning<\/a>, 2016.<\/p>\n It is also helpful when the gradient is estimated, such as from a simulation, and may be noisy, e.g. when the gradient has a high variance.<\/p>\n Finally, momentum is helpful when the search space is flat or nearly flat, e.g. zero gradient. The momentum allows the search to progress in the same direction as before the flat spot and helpfully cross the flat region.<\/p>\n Now that we are familiar with what momentum is, let\u2019s look at a worked example.<\/p>\n In this section, we will first implement the gradient descent optimization algorithm, then update it to use momentum and compare results.<\/p>\n First, let\u2019s define an optimization function.<\/p>\n We will use a simple one-dimensional function that squares the input and defines the range of valid inputs from -1.0 to 1.0.<\/p>\n The objective()<\/em> function below implements this function.<\/p>\n We can then sample all inputs in the range and calculate the objective function value for each.<\/p>\n Finally, we can create a line plot of the inputs (x-axis) versus the objective function values (y-axis) to get an intuition for the shape of the objective function that we will be searching.<\/p>\n The example below ties this together and provides an example of plotting the one-dimensional test function.<\/p>\n Running the example creates a line plot of the inputs to the function (x-axis) and the calculated output of the function (y-axis).<\/p>\n We can see the familiar U-shape called a parabola.<\/p>\n Line Plot of Simple One Dimensional Function<\/p>\n<\/div>\n Next, we can apply the gradient descent algorithm to the problem.<\/p>\n First, we need a function that calculates the derivative for the objective function.<\/p>\n The derivative of x^2 is x * 2 and the derivative()<\/em> function implements this below.<\/p>\n We can define a function that implements the gradient descent optimization algorithm.<\/p>\n The procedure involves starting with a randomly selected point in the search space, then calculating the gradient, updating the position in the search space, evaluating the new position, and reporting the progress. This process is then repeated for a fixed number of iterations. The final point and its evaluation are then returned from the function.<\/p>\n The function gradient_descent()<\/em> below implements this and takes the name of the objective and gradient functions as well as the bounds on the inputs to the objective function, number of iterations, and step size, then returns the solution and its evaluation at the end of the search.<\/p>\n We can then define the bounds of the objective function, the step size, and the number of iterations for the algorithm.<\/p>\n We will use a step size of 0.1 and 30 iterations, both found after a little experimentation.<\/p>\n The seed for the pseudorandom number generator is fixed so that we always get the same sequence of random numbers, and in this case, it ensures that we get the same starting point for the search each time the code is run (e.g. something interesting far from the optima).<\/p>\n Tying this together, the complete example of applying grid search to our one-dimensional test function is listed below.<\/p>\n Running the example starts with a random point in the search space, then applies the gradient descent algorithm, reporting performance along the way.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see that the algorithm finds a good solution after about 27 iterations, with a function evaluation of about 0.0.<\/p>\n Note the optima for this function is at f(0.0) = 0.0.<\/p>\n We would expect that gradient descent with momentum will accelerate the optimization procedure and find a similarly evaluated solution in fewer iterations.<\/p>\n Next, we can visualize the progress of the search on a plot of the target function.<\/p>\n First, we can update the gradient_descent()<\/em> function to store all solutions and their score found during the optimization as lists and return them at the end of the search instead of the best solution found.<\/p>\n The function can be called and we can get the lists of the solutions and the scores found during the search.<\/p>\n We can create a line plot of the objective function, as before.<\/p>\n Finally, we can plot each solution found as a red dot and connect the dots with a line so we can see how the search moved downhill.<\/p>\n Tying this all together, the complete example of plotting the result of the gradient descent search on the one-dimensional test function is listed below.<\/p>\n Running the example performs the gradient descent search on the objective function as before, except in this case, each point found during the search is plotted.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see that the search started more than halfway up the right part of the function and stepped downhill to the bottom of the basin.<\/p>\n We can see that in the parts of the objective function with the larger curve, the derivative (gradient) is larger, and in turn, larger steps are taken. Similarly, the gradient is smaller as we get closer to the optima, and in turn, smaller steps are taken.<\/p>\n This highlights that the step size is used as a scale factor on the magnitude of the gradient (curvature) of the objective function.<\/p>\n Plot of the Progress of Gradient Descent on a One Dimensional Objective Function<\/p>\n<\/div>\n Next, we can update the gradient descent optimization algorithm to use momentum.<\/p>\n This can be achieved by updating the gradient_descent()<\/em> function to take a \u201cmomentum<\/em>\u201d argument that defines the amount of momentum used during the search.<\/p>\n The change made to the solution must be remembered from the previous iteration of the loop, with an initial value of 0.0.<\/p>\n We can then break the update procedure down into first calculating the gradient, then calculating the change to the solution, calculating the position of the new solution, then saving the change for the next iteration.<\/p>\n The updated version of the gradient_descent()<\/em> function with these changes is listed below.<\/p>\n We can then choose a momentum value and pass it to the gradient_descent()<\/em> function.<\/p>\n After a little trial and error, a momentum value of 0.3 was found to be effective on this problem, given the fixed step size of 0.1.<\/p>\n Tying this together, the complete example of gradient descent optimization with momentum is listed below.<\/p>\n Running the example starts with a random point in the search space, then applies the gradient descent algorithm with momentum, reporting performance along the way.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see that the algorithm finds a good solution after about 13 iterations, with a function evaluation of about 0.0.<\/p>\n As expected, this is faster (fewer iterations) than gradient descent without momentum, using the same starting point and step size that took 27 iterations.<\/p>\n Finally, we can visualize the progress of the gradient descent optimization algorithm with momentum.<\/p>\n The complete example is listed below.<\/p>\n Running the example performs the gradient descent search with momentum on the objective function as before, except in this case, each point found during the search is plotted.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, if we compare the plot to the plot created previously for the performance of gradient descent (without momentum), we can see that the search indeed reaches the optima in fewer steps, noted with fewer distinct red dots on the path to the bottom of the basin.<\/p>\n Plot of the Progress of Gradient Descent With Momentum on a One Dimensional Objective Function<\/p>\n<\/div>\n As an extension, try different values for momentum, such as 0.8, and review the resulting plot. This section provides more resources on the topic if you are looking to go deeper.<\/p>\n In this tutorial, you discovered the gradient descent with momentum algorithm.<\/p>\n Specifically, you learned:<\/p>\n Do you have any questions?<\/strong> The post Gradient Descent With Momentum from Scratch<\/a> appeared first on Machine Learning Mastery<\/a>.<\/p>\n<\/div>\n Go to Source<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n
![\"Gradient](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2021\/04\/Gradient-Descent-With-Momentum-from-Scratch.jpg\")
<\/p>\n
Photo by Chris Barnes<\/a>, some rights reserved.<\/p>\n<\/div>\nTutorial Overview<\/h2>\n
\n
\n
Gradient Descent<\/h2>\n
\n
\n
\n
\n
Momentum<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n
Gradient Descent with Momentum<\/h2>\n
One-Dimensional Test Problem<\/h3>\n
# objective function\r\ndef objective(x):\r\n\treturn x**2.0<\/pre>\n
...\r\n# define range for input\r\nr_min, r_max = -1.0, 1.0\r\n# sample input range uniformly at 0.1 increments\r\ninputs = arange(r_min, r_max+0.1, 0.1)\r\n# compute targets\r\nresults = objective(inputs)<\/pre>\n
...\r\n# create a line plot of input vs result\r\npyplot.plot(inputs, results)\r\n# show the plot\r\npyplot.show()<\/pre>\n
# plot of simple function\r\nfrom numpy import arange\r\nfrom matplotlib import pyplot\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x**2.0\r\n\r\n# define range for input\r\nr_min, r_max = -1.0, 1.0\r\n# sample input range uniformly at 0.1 increments\r\ninputs = arange(r_min, r_max+0.1, 0.1)\r\n# compute targets\r\nresults = objective(inputs)\r\n# create a line plot of input vs result\r\npyplot.plot(inputs, results)\r\n# show the plot\r\npyplot.show()<\/pre>\n
![\"Line](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/12\/Line-Plot-of-Simple-One-Dimensional-Function-2.png\")
<\/p>\nGradient Descent Optimization<\/h2>\n
# derivative of objective function\r\ndef derivative(x):\r\n\treturn x * 2.0<\/pre>\n
# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size):\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# take a step\r\n\t\tsolution = solution - step_size * gradient\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solution, solution_eval]<\/pre>\n...\r\n# seed the pseudo random number generator\r\nseed(4)\r\n# define range for input\r\nbounds = asarray([[-1.0, 1.0]])\r\n# define the total iterations\r\nn_iter = 30\r\n# define the maximum step size\r\nstep_size = 0.1\r\n# perform the gradient descent search\r\nbest, score = gradient_descent(objective, derivative, bounds, n_iter, step_size)<\/pre>\n
# example of gradient descent for a one-dimensional function\r\nfrom numpy import asarray\r\nfrom numpy.random import rand\r\nfrom numpy.random import seed\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x**2.0\r\n\r\n# derivative of objective function\r\ndef derivative(x):\r\n\treturn x * 2.0\r\n\r\n# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size):\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# take a step\r\n\t\tsolution = solution - step_size * gradient\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solution, solution_eval]\r\n\r\n# seed the pseudo random number generator\r\nseed(4)\r\n# define range for input\r\nbounds = asarray([[-1.0, 1.0]])\r\n# define the total iterations\r\nn_iter = 30\r\n# define the step size\r\nstep_size = 0.1\r\n# perform the gradient descent search\r\nbest, score = gradient_descent(objective, derivative, bounds, n_iter, step_size)\r\nprint('Done!')\r\nprint('f(%s) = %f' % (best, score))<\/pre>\n>0 f([0.74724774]) = 0.55838\r\n>1 f([0.59779819]) = 0.35736\r\n>2 f([0.47823856]) = 0.22871\r\n>3 f([0.38259084]) = 0.14638\r\n>4 f([0.30607268]) = 0.09368\r\n>5 f([0.24485814]) = 0.05996\r\n>6 f([0.19588651]) = 0.03837\r\n>7 f([0.15670921]) = 0.02456\r\n>8 f([0.12536737]) = 0.01572\r\n>9 f([0.10029389]) = 0.01006\r\n>10 f([0.08023512]) = 0.00644\r\n>11 f([0.06418809]) = 0.00412\r\n>12 f([0.05135047]) = 0.00264\r\n>13 f([0.04108038]) = 0.00169\r\n>14 f([0.0328643]) = 0.00108\r\n>15 f([0.02629144]) = 0.00069\r\n>16 f([0.02103315]) = 0.00044\r\n>17 f([0.01682652]) = 0.00028\r\n>18 f([0.01346122]) = 0.00018\r\n>19 f([0.01076897]) = 0.00012\r\n>20 f([0.00861518]) = 0.00007\r\n>21 f([0.00689214]) = 0.00005\r\n>22 f([0.00551372]) = 0.00003\r\n>23 f([0.00441097]) = 0.00002\r\n>24 f([0.00352878]) = 0.00001\r\n>25 f([0.00282302]) = 0.00001\r\n>26 f([0.00225842]) = 0.00001\r\n>27 f([0.00180673]) = 0.00000\r\n>28 f([0.00144539]) = 0.00000\r\n>29 f([0.00115631]) = 0.00000\r\nDone!\r\nf([0.00115631]) = 0.000001<\/pre>\n<\/p>\n
Visualization of Gradient Descent Optimization<\/h2>\n
# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size):\r\n\t# track all solutions\r\n\tsolutions, scores = list(), list()\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# take a step\r\n\t\tsolution = solution - step_size * gradient\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# store solution\r\n\t\tsolutions.append(solution)\r\n\t\tscores.append(solution_eval)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solutions, scores]<\/pre>\n...\r\n# perform the gradient descent search\r\nsolutions, scores = gradient_descent(objective, derivative, bounds, n_iter, step_size)<\/pre>\n
...\r\n# sample input range uniformly at 0.1 increments\r\ninputs = arange(bounds[0,0], bounds[0,1]+0.1, 0.1)\r\n# compute targets\r\nresults = objective(inputs)\r\n# create a line plot of input vs result\r\npyplot.plot(inputs, results)<\/pre>\n
...\r\n# plot the solutions found\r\npyplot.plot(solutions, scores, '.-', color='red')<\/pre>\n
# example of plotting a gradient descent search on a one-dimensional function\r\nfrom numpy import asarray\r\nfrom numpy import arange\r\nfrom numpy.random import rand\r\nfrom numpy.random import seed\r\nfrom matplotlib import pyplot\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x**2.0\r\n\r\n# derivative of objective function\r\ndef derivative(x):\r\n\treturn x * 2.0\r\n\r\n# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size):\r\n\t# track all solutions\r\n\tsolutions, scores = list(), list()\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# take a step\r\n\t\tsolution = solution - step_size * gradient\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# store solution\r\n\t\tsolutions.append(solution)\r\n\t\tscores.append(solution_eval)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solutions, scores]\r\n\r\n# seed the pseudo random number generator\r\nseed(4)\r\n# define range for input\r\nbounds = asarray([[-1.0, 1.0]])\r\n# define the total iterations\r\nn_iter = 30\r\n# define the step size\r\nstep_size = 0.1\r\n# perform the gradient descent search\r\nsolutions, scores = gradient_descent(objective, derivative, bounds, n_iter, step_size)\r\n# sample input range uniformly at 0.1 increments\r\ninputs = arange(bounds[0,0], bounds[0,1]+0.1, 0.1)\r\n# compute targets\r\nresults = objective(inputs)\r\n# create a line plot of input vs result\r\npyplot.plot(inputs, results)\r\n# plot the solutions found\r\npyplot.plot(solutions, scores, '.-', color='red')\r\n# show the plot\r\npyplot.show()<\/pre>\n![\"Plot](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/12\/Plot-of-the-Progress-of-Gradient-Descent-on-a-One-Dimensional-Objective-Function-1.png\")
<\/p>\nGradient Descent Optimization With Momentum<\/h2>\n
...\r\n# keep track of the change\r\nchange = 0.0<\/pre>\n
...\r\n# calculate gradient\r\ngradient = derivative(solution)\r\n# calculate update\r\nnew_change = step_size * gradient + momentum * change\r\n# take a step\r\nsolution = solution - new_change\r\n# save the change\r\nchange = new_change<\/pre>\n
# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size, momentum):\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# keep track of the change\r\n\tchange = 0.0\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# calculate update\r\n\t\tnew_change = step_size * gradient + momentum * change\r\n\t\t# take a step\r\n\t\tsolution = solution - new_change\r\n\t\t# save the change\r\n\t\tchange = new_change\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solution, solution_eval]<\/pre>\n...\r\n# define momentum\r\nmomentum = 0.3\r\n# perform the gradient descent search with momentum\r\nbest, score = gradient_descent(objective, derivative, bounds, n_iter, step_size, momentum)<\/pre>\n
# example of gradient descent with momentum for a one-dimensional function\r\nfrom numpy import asarray\r\nfrom numpy.random import rand\r\nfrom numpy.random import seed\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x**2.0\r\n\r\n# derivative of objective function\r\ndef derivative(x):\r\n\treturn x * 2.0\r\n\r\n# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size, momentum):\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# keep track of the change\r\n\tchange = 0.0\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# calculate update\r\n\t\tnew_change = step_size * gradient + momentum * change\r\n\t\t# take a step\r\n\t\tsolution = solution - new_change\r\n\t\t# save the change\r\n\t\tchange = new_change\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solution, solution_eval]\r\n\r\n# seed the pseudo random number generator\r\nseed(4)\r\n# define range for input\r\nbounds = asarray([[-1.0, 1.0]])\r\n# define the total iterations\r\nn_iter = 30\r\n# define the step size\r\nstep_size = 0.1\r\n# define momentum\r\nmomentum = 0.3\r\n# perform the gradient descent search with momentum\r\nbest, score = gradient_descent(objective, derivative, bounds, n_iter, step_size, momentum)\r\nprint('Done!')\r\nprint('f(%s) = %f' % (best, score))<\/pre>\n>0 f([0.74724774]) = 0.55838\r\n>1 f([0.54175461]) = 0.29350\r\n>2 f([0.37175575]) = 0.13820\r\n>3 f([0.24640494]) = 0.06072\r\n>4 f([0.15951871]) = 0.02545\r\n>5 f([0.1015491]) = 0.01031\r\n>6 f([0.0638484]) = 0.00408\r\n>7 f([0.03976851]) = 0.00158\r\n>8 f([0.02459084]) = 0.00060\r\n>9 f([0.01511937]) = 0.00023\r\n>10 f([0.00925406]) = 0.00009\r\n>11 f([0.00564365]) = 0.00003\r\n>12 f([0.0034318]) = 0.00001\r\n>13 f([0.00208188]) = 0.00000\r\n>14 f([0.00126053]) = 0.00000\r\n>15 f([0.00076202]) = 0.00000\r\n>16 f([0.00046006]) = 0.00000\r\n>17 f([0.00027746]) = 0.00000\r\n>18 f([0.00016719]) = 0.00000\r\n>19 f([0.00010067]) = 0.00000\r\n>20 f([6.05804744e-05]) = 0.00000\r\n>21 f([3.64373635e-05]) = 0.00000\r\n>22 f([2.19069576e-05]) = 0.00000\r\n>23 f([1.31664443e-05]) = 0.00000\r\n>24 f([7.91100141e-06]) = 0.00000\r\n>25 f([4.75216828e-06]) = 0.00000\r\n>26 f([2.85408468e-06]) = 0.00000\r\n>27 f([1.71384267e-06]) = 0.00000\r\n>28 f([1.02900153e-06]) = 0.00000\r\n>29 f([6.17748881e-07]) = 0.00000\r\nDone!\r\nf([6.17748881e-07]) = 0.000000<\/pre>\n<\/p>\n
Visualization of Gradient Descent Optimization With Momentum<\/h2>\n
# example of plotting gradient descent with momentum for a one-dimensional function\r\nfrom numpy import asarray\r\nfrom numpy import arange\r\nfrom numpy.random import rand\r\nfrom numpy.random import seed\r\nfrom matplotlib import pyplot\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x**2.0\r\n\r\n# derivative of objective function\r\ndef derivative(x):\r\n\treturn x * 2.0\r\n\r\n# gradient descent algorithm\r\ndef gradient_descent(objective, derivative, bounds, n_iter, step_size, momentum):\r\n\t# track all solutions\r\n\tsolutions, scores = list(), list()\r\n\t# generate an initial point\r\n\tsolution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# keep track of the change\r\n\tchange = 0.0\r\n\t# run the gradient descent\r\n\tfor i in range(n_iter):\r\n\t\t# calculate gradient\r\n\t\tgradient = derivative(solution)\r\n\t\t# calculate update\r\n\t\tnew_change = step_size * gradient + momentum * change\r\n\t\t# take a step\r\n\t\tsolution = solution - new_change\r\n\t\t# save the change\r\n\t\tchange = new_change\r\n\t\t# evaluate candidate point\r\n\t\tsolution_eval = objective(solution)\r\n\t\t# store solution\r\n\t\tsolutions.append(solution)\r\n\t\tscores.append(solution_eval)\r\n\t\t# report progress\r\n\t\tprint('>%d f(%s) = %.5f' % (i, solution, solution_eval))\r\n\treturn [solutions, scores]\r\n\r\n# seed the pseudo random number generator\r\nseed(4)\r\n# define range for input\r\nbounds = asarray([[-1.0, 1.0]])\r\n# define the total iterations\r\nn_iter = 30\r\n# define the step size\r\nstep_size = 0.1\r\n# define momentum\r\nmomentum = 0.3\r\n# perform the gradient descent search with momentum\r\nsolutions, scores = gradient_descent(objective, derivative, bounds, n_iter, step_size, momentum)\r\n# sample input range uniformly at 0.1 increments\r\ninputs = arange(bounds[0,0], bounds[0,1]+0.1, 0.1)\r\n# compute targets\r\nresults = objective(inputs)\r\n# create a line plot of input vs result\r\npyplot.plot(inputs, results)\r\n# plot the solutions found\r\npyplot.plot(solutions, scores, '.-', color='red')\r\n# show the plot\r\npyplot.show()<\/pre>\n![\"Plot](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/12\/Plot-of-the-Progress-of-Gradient-Descent-with-Momentum-on-a-One-Dimensional-Objective-Function.png\")
<\/p>\n
\nLet me know what you discover in the comments below.<\/p>\nFurther Reading<\/h2>\n
Books<\/h3>\n
\n
APIs<\/h3>\n
\n
Articles<\/h3>\n
\n
Summary<\/h2>\n
\n
\nAsk your questions in the comments below and I will do my best to answer.<\/p>\n