Author(s): Towards AI Editorial Team
Originally published on Towards AI the World’s Leading AI and Technology News and Media Company. If you are building an AI-related product or service, we invite you to consider becoming an AI sponsor. At Towards AI, we help scale AI and technology startups. Let us help you unleash your technology to the masses.
Image by Sara from Pixabay
Gradient Descent Algorithm with Code Examples in Python
Author(s): Pratik Shukla
“Educating the mind without educating the heart is no education at all.” ― Aristotle
The Gradient Descent Series of Blogs:
The Gradient Descent Algorithm
Mathematical Intuition behind the Gradient Descent Algorithm
The Gradient Descent Algorithm & its Variants (You are here!)
Table of contents:
Introduction
Batch Gradient Descent (BGD)
Stochastic Gradient Descent (SGD)
Mini-Batch Gradient Descent (MBGD)
Graph Comparison
End Notes
Resources
References
Introduction:
Drumroll, please: Welcome to the finale of the Gradient Descent series! In this blog, we will dive deeper into the gradient descent algorithm. We will discuss all the fun flavors of the gradient descent algorithm along with their code examples in Python. We will also examine the differences between the algorithms based on the number of calculations performed in each algorithm. We’re leaving no stone unturned today, so we request that you run the Google Colab files as you read the document; doing so will give you a more precise understanding of the topic to see it in action. Let’s get into it!
Batch Gradient Descent:
Working of the Batch Gradient Descent (BGD) Algorithm
The Batch Gradient Descent (BGD) algorithm considers all the training examples in each iteration. If the dataset contains a large number of training examples and a large number of features, implementing the Batch Gradient Descent (BGD) algorithm becomes computationally expensive — so mind your budget! Let’s take an example to understand it in a better way.
Batch Gradient Descent (BGD):
Number of training examples per iterations = 1 million = 1⁰⁶
Number of iterations = 1000 = 1⁰³
Number of parameters to be trained = 10000 = 1⁰⁴
Total computations = 1⁰⁶ * 1⁰³* 1⁰⁴ = 1⁰¹³
Now, let’s see how the Batch Gradient Descent (BGD) algorithm is implemented.
1. Step — 1:
First, we are downloading the data file from the GitHub repository.
https://medium.com/media/b56f0e725c9a8f0f5b7f310797d3bd05/href
2. Step — 2:
Next, we import some required libraries to read, manipulate, and visualize the data.
https://medium.com/media/c08ec5c5b8a8e9b1c805c2a2c58e6446/href
3. Step — 3:
Next, we are reading the data file, and then printing the first five rows of it.
https://medium.com/media/a92d01e6e044c53864c011b94478e20a/href
4. Step — 4:
Next, we are dividing the dataset into features and target variables.
https://medium.com/media/2cea84325aaf4268b9edbccf21eac21c/href
Dimensions: X = (200, 3) & Y = (200, )
5. Step — 5:
To perform matrix calculations in further steps, we need to reshape the target variable.
https://medium.com/media/efec831260d89b486c301638b94081f1/href
Dimensions: X = (200, 3) & Y = (200, 1)
6. Step — 6:
Next, we are normalizing the dataset.
https://medium.com/media/8d68a5edc6e7b8b4d62beddce6d327e6/href
Dimensions: X = (200, 3) & Y = (200, 1)
7. Step — 7:
Next, we are getting the initial values for the bias and weights matrices. We will use these values in the first iteration while performing forward propagation.
https://medium.com/media/7b468e4c5fb0aad6c653000e711a3511/href
Dimensions: bias = (1, 1) & weights = (1, 3)
8. Step — 8:
Next, we perform the forward propagation step. This step is based on the following formula.
https://medium.com/media/3c70575221d6d9dfd067cf887c719564/href
Dimensions: predicted_value = (1, 1)+(200, 3)*(3,1) = (1, 1)+(200, 1) = (200, 1)
9. Step — 9:
Next, we are going to calculate the cost associated with our prediction. This step is based on the following formula.
https://medium.com/media/9424f27bc90560f24b480d1938ae0531/href
Dimensions: cost = scalar value
10. Step — 10:
Next, we update the parameter values of weights and bias using the gradient descent algorithm. This step is based on the following formulas. Please note that the reason why we’re not summing over the values of the weights is that our weight matrix is not a 1*1 matrix.
https://medium.com/media/81cd5e9b370957821313af3f99a91129/href
Dimensions: db = sum(200, 1) = (1, 1)
Dimensions: dw = (1, 200) * (200, 3) = (1, 3)
Dimensions: bias = (1, 1) & weights = (1, 3)
11. Step — 11:
Next, we are going to use all the functions we just defined to run the gradient descent algorithm. We are also creating an empty list called cost_list to store the cost values of all the iterations. This list will be put to use to plot a graph in further steps.
https://medium.com/media/73426f47e5f4bf7a0dce14166a62f4e3/href
12. Step — 12:
Next, we are actually calling the function to get the final results. Please note that we are running the entire code for 200 iterations. Also, here we have specified the learning rate of 0.01.
https://medium.com/media/46a6cbf34a41a0d4a908e603c12d34d0/href
13. Step — 13:
Next, we are plotting the graph of iterations vs. cost.
https://medium.com/media/b75ea500a36c0d35aee6997601f6f2f4/href
14. Step — 14:
Next, we are printing the final weights values after all the iterations are done.
https://medium.com/media/f883fbb5f90e0ac8b72c29392d79f7e2/href
15. Step — 15:
Next, we print the final bias value after all the iterations are done.
https://medium.com/media/e486e2ea3c55f7c8953496e631097d6d/href
16. Step — 16:
Next, we plot two graphs with different learning rates to see the effect of learning rate in optimization. In the following graph we can see that the graph with a higher learning rate (0.01) converges faster than the graph with a slower learning rate (0.001). As we learned in Part 1 of the Gradient Descent series, this is because the graph with the lower learning rate takes smaller steps.
https://medium.com/media/5bbbdcea83737659e0a6ba99c40cc076/href
17. Step — 17:
Let’s put it all together.
https://medium.com/media/1492dcfa04b664a7fb59a44790066a5d/href
Number of Calculations:
Now, let’s count the number of calculations performed in the batch gradient descent algorithm.
Bias: (training examples) x (iterations) x (parameters) = 200 * 200 * 1 = 40000
Weights: (training examples) x (iterations) x (parameters) = 200 * 200 *3 = 120000
Stochastic Gradient Descent
Working of the Stochastic Gradient Descent (SGD) Algorithm
In the batch gradient descent algorithm, we consider all the training examples for all the iterations of the algorithm. But, if our dataset has a large number of training examples and/or features, then it gets computationally expensive to calculate the parameter values. We know our machine learning algorithm will yield more accuracy if we provide it with more training examples. But, as the size of the dataset increases, the computations associated with it also increase. Let’s take an example to understand this in a better way.
Batch Gradient Descent (BGD)
Number of training examples per iterations = 1 million = 1⁰⁶
Number of iterations = 1000 = 1⁰³
Number of parameters to be trained = 10000 = 1⁰⁴
Total computations = 1⁰⁶*1⁰³*1⁰⁴=1⁰¹³
Now, if we look at the above number, it does not give us excellent vibes! So we can say that using the Batch Gradient Descent algorithm does not seem efficient. So, to deal with this problem, we use the Stochastic Gradient Descent (SGD) algorithm. The word “Stochastic” means random. So, instead of performing calculation on all the training examples of a dataset, we take one random example and perform the calculations on that. Sounds interesting, doesn’t it? We just consider one training example per iteration in the Stochastic Gradient Descent (SGD) algorithm. Let’s see how effective Stochastic Gradient Descent is based on its calculations.
Stochastic Gradient Descent (SGD):
Number of training examples per iterations = 1
Number of iterations = 1000 = 1⁰³
Number of parameters to be trained = 10000 = 1⁰⁴
Total computations = 1 * 1⁰³*1⁰⁴=1⁰⁷
Comparison with Batch Gradient Descent:
Total computations in BGD = 1⁰¹³
Total computations in SGD = 1⁰⁷
Evaluation: SGD is ¹⁰⁶ times faster than BGD in this example.
Note: Please be aware that our cost function might not necessarily go down as we just take one random training example every iteration, so don’t worry. However, the cost function will gradually decrease as we perform more and more iterations.
Now, let’s see how the Stochastic Gradient Descent (SGD) algorithm is implemented.
1. Step — 1:
First, we are downloading the data file from the GitHub repository.
https://medium.com/media/2191eecb5ea5f99cffbd1713b8210dd1/href
2. Step — 2:
Next, we are importing some required libraries to read, manipulate, and visualize the data.
https://medium.com/media/2b042a4490911fe7ba0e2b426a524214/href
3. Step — 3:
Next, we are reading the data file, and then printing the first five rows of it.
https://medium.com/media/1195ef05b3a4addbcc8685bb6a401be0/href
4. Step — 4:
Next, we are dividing the dataset into features and target variables.
https://medium.com/media/8dbd790c5b0f7ed602a494f2d9000d47/href
Dimensions: X = (200, 3) & Y = (200, )
5. Step — 5:
To perform matrix calculations in further steps, we need to reshape the target variable.
https://medium.com/media/8aa47ce08f7a7a774b98f8f76e1021a5/href
Dimensions: X = (200, 3) & Y = (200, 1)
6. Step — 6:
Next, we are normalizing the dataset.
https://medium.com/media/3e7d62fb6e4b2f298ca95d5d2e5a4887/href
Dimensions: X = (200, 3) & Y = (200, 1)
7. Step — 7:
Next, we are getting the initial values for the bias and weights matrices. We will use these values in the first iteration while performing forward propagation.
https://medium.com/media/b6819151b482bfa28b111667ef482510/href
Dimensions: bias = (1, 1) & weights = (1, 3)
8. Step — 8:
Next, we perform the forward propagation step. This step is based on the following formula.
https://medium.com/media/7d62e9dfd6e8d901e2d29f2c11b4a797/href
Dimensions: predicted_value = (1, 1)+(200, 3)*(3,1) = (1, 1)+(200, 1) = (200, 1)
9. Step — 9:
Next, we’ll calculate the cost associated to our prediction. The formula used for this step is as follows. Because there will only be one value of the error, we won’t need to divide the cost function by the size of the dataset or add up all the cost values.
https://medium.com/media/599aab1238e1f85cb5cf094e77823aea/href
Dimensions: cost = scalar value
10. Step — 10:
Next, we update the parameter values of weights and bias using the gradient descent algorithm. This step is based on the following formulas. Please note that the reason why we are not summing over the values of the weights is that our weight matrix is not a 1*1 matrix. Also, in this case, since we have only one training example, we won’t need to perform the summation over all the examples. The updated formula is given as follows.
https://medium.com/media/1190be306edbbee2a09eb6699bf30a3d/href
Dimensions: db = (1, 1)
Dimensions: dw = (1, 200) * (200, 3) = (1, 3)
Dimensions: bias = (1, 1) & weights = (1, 3)
11. Step — 11:
https://medium.com/media/3d23fd33c575950eef3dbaac9baf6629/href
12. Step — 12:
Next, we are actually calling the function to get the final results. Please note that we are running the entire code for 200 iterations. Also, here we have specified the learning rate of 0.01.
https://medium.com/media/df2b00acb8e699d1fcb2683ad87b7779/href
13. Step — 13:
Next, we print the final weights values after all the iterations are done.
https://medium.com/media/629e08fd315c9839f8c7789f5396c82e/href
14. Step — 14:
Next, we print the final bias value after all the iterations are done.
https://medium.com/media/2156c2969e7e905dc121b89bb7e60ce0/href
15. Step — 15:
Next, we are plotting the graph of iterations vs. cost.
https://medium.com/media/0a97beff3e6f484214a6e4a8d1d7a026/href
16. Step — 16:
Next, we plot two graphs with different learning rates to see the effect of learning rate in optimization. In the following graph we can see that the graph with a higher learning rate (0.01) converges faster than the graph with a slower learning rate (0.001). Again, we know this because the graph with a lower learning rate takes smaller steps.
https://medium.com/media/a63f5531cca319bd0ebda662c56733d7/href
17. Step — 17:
Putting it all together.
https://medium.com/media/f625a0ed077e3c75722040f32410dd4d/href
Calculations:
Now, let’s count the number of calculations performed in implementing the batch gradient descent algorithm.
Bias: (training examples) x (iterations) x (parameters) = 1* 200 * 1 = 200
Weights: (training examples) x (iterations) x (parameters) = 1* 200 *3 = 600
Mini-Batch Gradient Descent Algorithm:
Working of the Mini-Batch Gradient Descent (MBGD) Algorithm
In the Batch Gradient Descent (BGD) algorithm, we consider all the training examples for all the iterations of the algorithm. However, in the Stochastic Gradient Descent (SGD) algorithm, we only consider one random training example. Now, in the Mini-Batch Gradient Descent (MBGD) algorithm, we consider a random subset of training examples in each iteration. Since this is not as random as SGD, we reach closer to the global minimum. However, MBGD is susceptible to getting stuck into local minima. Let’s take an example to understand this in a better way.
Batch Gradient Descent (BGD):
Number of training examples per iterations = 1 million = 1⁰⁶
Number of iterations = 1000 = 1⁰³
Number of parameters to be trained = 10000 = 1⁰⁴
Total computations = 1⁰⁶*1⁰³*1⁰⁴=1⁰¹³
Stochastic Gradient Descent (SGD):
Number of training examples per iterations = 1
Number of iterations = 1000 = 1⁰³
Number of parameters to be trained = 10000 = 1⁰⁴
Total computations = 1*1⁰³*1⁰⁴ = 1⁰⁷
Mini Batch Gradient Descent (MBGD):
Number of training examples per iterations = 100 = 1⁰²
→Here, we are considering 1⁰² training examples out of 1⁰⁶.
Number of iterations = 1000 = 1⁰³
Number of parameters to be trained = 10000 = 1⁰⁴
Total computations = 1⁰²*1⁰³*1⁰⁴=1⁰⁹
Comparison with Batch Gradient Descent (BGD):
Total computations in BGD = 1⁰¹³
Total computations in MBGD = 1⁰⁹
Evaluation: MBGD is 1⁰⁴ times faster than BGD in this example.
Comparison with Stochastic Gradient Descent (SGD):
Total computations in SGD = 1⁰⁷
Total computations in MBGD = 1⁰⁹
Evaluation: SGD is 1⁰² times faster than MBGD in this example.
Comparison of BGD, SGD, and MBGD:
Total computations in BGD= 1⁰¹³
Total computations in SGD= 1⁰⁷
Total computations in MBGD = 1⁰⁹
Evaluation: SGD > MBGD > BGD
Note: Please be aware that our cost function might not necessarily go down as we are taking a random sample of the training examples every iteration. However, the cost function will gradually decrease as we perform more and more iterations.
Now, let’s see how the Mini-Batch Gradient Descent (MBGD) algorithm is implemented in practice.
1. Step — 1:
First, we are downloading the data file from the GitHub repository.
https://medium.com/media/f1ef4c92a643e81232313e76404574c2/href
2. Step — 2:
Next, we are importing some required libraries to read, manipulate, and visualize the data.
https://medium.com/media/d5b5b02482ea1d70232ac54e197fe546/href
3. Step — 3:
Next, we are reading the data file, and then print the first five rows of it.
https://medium.com/media/4ea8018cb2e289fb0cebfd8bc47bb75f/href
4. Step — 4:
Next, we are dividing the dataset into features and target variables.
https://medium.com/media/7a6d513b39283f4fe65c6894ed3fddba/href
Dimensions: X = (200, 3) & Y = (200, )
5. Step — 5:
To perform matrix calculations in further steps, we need to reshape the target variable.
https://medium.com/media/18381ef18dd259c192a172dcbd3b1cba/href
Dimensions: X = (200, 3) & Y = (200, 1)
6. Step — 6:
Next, we are normalizing the dataset.
https://medium.com/media/9e1bef969b68ea3c6813cd62075d94c3/href
Dimensions: X = (200, 3) & Y = (200, 1)
7. Step — 7:
Next, we are getting the initial values for the bias and weights matrices. We will use these values in the first iteration while performing forward propagation.
https://medium.com/media/58260cde44b13f2802fc3a205d495cbc/href
Dimensions: bias = (1, 1) & weights = (1, 3)
8. Step — 8:
Next, we are performing the forward propagation step. This step is based on the following formula.
https://medium.com/media/5944bae804d3e0104cec9bf954227e2f/href
Dimensions: predicted_value = (1, 1)+(200, 3)*(3,1) = (1, 1)+(200, 1) = (200, 1)
9. Step — 9:
Next, we are going to calculate the cost associated with our prediction. This step is based on the following formula.
https://medium.com/media/7fe0c28282a6dafb16ecf3e853261495/href
Dimensions: cost = scalar value
10. Step — 10:
Next, we update the parameter values of weights and bias using the gradient descent algorithm. This step is based on the following formulas. Please note that the reason why we are not summing over the values of the weights is that our weight matrix is not a 1*1 matrix.
https://medium.com/media/94e7256c35ff7b97b741a95a558c5d47/href
Dimensions: db = sum(200, 1) = (1 , 1)
Dimensions: dw = (1, 200) * (200, 3) = (1, 3)
Dimensions: bias = (1, 1) & weights = (1, 3)
11. Step — 11:
Next, we are going to use all the functions we just defined to run the gradient descent algorithm. Also, we are creating an empty list called cost_list to store the cost values of all the iterations. We will use this list to plot a graph in further steps.
https://medium.com/media/82daf11d20531926009b39fbb6570353/href
12. Step — 12:
Next, we are actually calling the function to get the final results. Please note that we are running the entire code for 200 iterations. Also, here we have specified the learning rate of 0.01.
https://medium.com/media/511425604a8f9047e1c811d80105e29e/href
13. Step — 13:
Next, we print the final weights values after all the iterations are done.
https://medium.com/media/c7148a63d36a062aad9cdaa2e6fcb823/href
14. Step — 14:
Next, we print the final bias value after all the iterations are done.
https://medium.com/media/49a9145a39fb5ebbdc99a2580d97046c/href
15. Step — 15:
Next, we are plotting the graph of iterations vs. cost.
https://medium.com/media/c056c59c47b77f93177e4974ec644a64/href
16. Step — 16:
Next, we plot two graphs with different learning rates to see the effect of learning rate in optimization. In the following graph we can see that the graph with a higher learning rate (0.01) converges faster than the graph with a slower learning rate (0.001). The reason behind it is that the graph with lower learning rate takes smaller steps.
https://medium.com/media/160d8dc695f33b8aba3892bba48ef2c0/href
17. Step — 17:
Putting it all together.
https://medium.com/media/1537cf0b790fba3f1b7bd88a18c761cc/href
Calculations:
Now, let’s count the number of calculations performed in implementing the batch gradient descent algorithm.
Bias: (training examples) x (iterations) x (parameters) = 20 * 200 * 1 = 4000
Weights: (training examples) x (iterations) x (parameters) = 20 * 200 *3 = 12000
Graph comparisons:
Comparison of Batch, Stochastic, and Mini Batch Gradient Descent Algorithm
End Notes:
And just like that, we’re at the end of the Gradient Descent series! In this installment, we went deep into the code to look at how three of the major types of gradient descent algorithms perform next to each other, summed up by these handy notes:
1. Batch Gradient Descent
Accuracy → High
Time → More
2. Stochastic Gradient Descent
Accuracy → Low
Time → Less
3. Mini-Batch Gradient Descent
Accuracy → Moderate
Time → Moderate
We hope you enjoyed this series and learned something new, no matter your starting point or machine learning background. Knowing this essential algorithm and its variants will likely prove valuable as you continue on your AI journey and understand more about both the technical and grand aspects of this incredible technology. Keep an eye out for other blogs offering, even more, machine learning lessons, and stay curious!
Buy Pratik a Coffee!
Resources:
Batch Gradient Descent — Google Colab, GitHub
Stochastic Gradient Descent — Google Colab, GitHub
Mini Batch Gradient Descent — Google Colab, GitHub
Citation:
For attribution in academic contexts, please cite this work as:
Shukla, et al., “The Gradient Descent Algorithm & its Variants”, Towards AI, 2022
BibTex Citation:
@article{pratik_2022,
title={The Gradient Descent Algorithm & its Variants},
url={https://towardsai.net/neural-networks-with-python},
journal={Towards AI},
publisher={Towards AI Co.},
author={Pratik, Shukla},
editor={Lauren, Keegan},
year={2022},
month={Oct}
}
References:
Gradient descent — Wikipedia
The Gradient Descent Algorithm and its Variants was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.
Published via Towards AI
