Optimizing Linear Regression with Gradient Descent

1. The Intuition Behind Gradient Descent

Imagine you are standing on a foggy hill and want to get to the lowest point in the valley. Because of the fog, you can't see the bottom. What's a sensible strategy? You could look at the ground beneath your feet, find the direction of the steepest downward slope, and take a step in that direction. If you repeat this process, you will eventually reach the bottom.

This is exactly the intuition behind gradient descent. In our case:

• The "hill" is our cost function, $J({\theta }_0,{\theta }_1)$. The height at any point is the cost.
• Our "position" is determined by the current values of our parameters, ${\theta }_0$ and ${\theta }_1$.
• The "lowest point" is the minimum cost, which corresponds to the best-fit line.
• Finding the "steepest downward slope" involves a bit of calculus.

The following video from StatQuest provides an excellent step-by-step walkthrough of this idea. It starts by optimizing just one parameter (the intercept) to make the concept clear, before moving on to both.

2. The Mathematics of Gradient Descent

As you saw in the video, the "direction of steepest descent" is found by calculating the derivative of the cost function. When we have more than one parameter, like ${\theta }_0$ and ${\theta }_1$, we use partial derivatives. The collection of all partial derivatives is called the gradient.

The core of the gradient descent algorithm is the update rule, which is applied repeatedly to each parameter:

Let's break this down:

• ${\theta }_j$: The parameter we are updating (either ${\theta }_0$ or ${\theta }_1$).
• :=: This means "is updated to". We are assigning a new value to ${\theta }_j$.
• $\alpha$ (alpha): The learning rate. This is a small positive number (e.g., 0.01) that controls how big of a step we take.
• $\frac{\partial }{\partial {\theta }_j}J({\theta }_0,{\theta }_1)$: The partial derivative of the cost function with respect to the parameter ${\theta }_j$. This term gives us the slope of the cost function.

The entire term $\alpha \frac{\partial }{\partial {\theta }_j}J({\theta }_0,{\theta }_1)$ is the step size you saw in the video. By subtracting this step, we are moving "downhill" against the gradient.

The Update Rules for Linear Regression

For our linear regression cost function, the partial derivatives are:

• For the intercept ${\theta }_0$: $$\frac{\partial }{\partial {\theta }_0}J({\theta }_0,{\theta }_1)=\frac{1}{m}\sum _{i=1}^m({\hat{y}}^{(i)}-y^{(i)})$$
• For the slope ${\theta }_1$: $$\frac{\partial }{\partial {\theta }_1}J({\theta }_0,{\theta }_1)=\frac{1}{m}\sum _{i=1}^m({\hat{y}}^{(i)}-y^{(i)})x^{(i)}$$

(You don't need to derive these from scratch for the GATE exam, but you should understand their role. They represent the slope of the cost function with respect to each parameter.)

So, in each step of gradient descent, we simultaneously update our parameters using these specific rules:

To see how this works with both parameters, let's continue with the StatQuest video.

3. The Algorithm in Practice: A Python Implementation

Now that you have the theory and intuition, let's see how this translates into code. Since you prefer a balanced approach, we'll dive into a from-scratch implementation. This will solidify your understanding far better than just using a pre-built library function.

The following article, which you started in the last lesson, provides a clean Python implementation of linear regression using gradient descent.

Let's quickly summarize the complete algorithm, as seen in the article's code:

1. Initialize parameters: Start with some initial values for ${\theta }_0$ and ${\theta }_1$ (e.g., self.k_ = 0.0, self.b_ = 0.0).
2. Set hyperparameters: Choose a learning_rate ($\alpha$) and the number of n_iters (iterations).
3. Iterate: Loop for the specified number of iterations. In each iteration:
   a. Calculate predictions ($\hat{y}$): Use the current ${\theta }_0$ and ${\theta }_1$ to predict $\hat{y}$ for all data points.
   b. Calculate the gradients: Use the derivative formulas to compute the gradients for ${\theta }_0$ and ${\theta }_1$.
   c. Update parameters: Apply the update rules to get the new values for ${\theta }_0$ and ${\theta }_1$.
4. Finish: After the loop finishes, the final values of ${\theta }_0$ and ${\theta }_1$ define your best-fit line.

The image below beautifully connects the process of descending the cost function to finding the best-fit line for the data.

Conclusion

Congratulations! You have now learned the complete process of training a simple linear regression model. You not only understand the model's equation but also the optimization algorithm that brings it to life.

Key Takeaways:

• Gradient Descent is an iterative optimization algorithm used to find the minimum of a cost function.
• It works by repeatedly taking steps in the direction opposite to the gradient (the direction of steepest ascent).
• The learning rate ($\alpha$) is a crucial hyperparameter that controls the size of each step. If it's too large, the algorithm might fail to converge; if it's too small, training will be very slow.
• The update rule for each parameter ${\theta }_j$ is: ${\theta }_j:={\theta }_j-\alpha \frac{\partial }{\partial {\theta }_j}J$.
• In Python, this process is implemented as a loop that calculates predictions, computes gradients, and updates the parameters at each step.

Preview of the Next Lesson:
Linear regression is a powerful parametric model, where our goal is to learn a fixed set of parameters (${\theta }_0$ and ${\theta }_1$). In the next lesson, we will explore a completely different approach to prediction by implementing the k-Nearest Neighbors (k-NN) algorithm. This is a non-parametric model, which will give you a broader perspective on the different ways machine learning algorithms can learn from data.