Gradient Descent Optimization in Linear Regression
Introduction
Hello and welcome to another session on "Regression and Gradient Descent." In today's syllabus, we will construct and fit the gradient descent algorithm into a linear regression problem. Though linear regression does have a direct solution, gradient descent is essential for computational efficiency, especially when handling larger datasets or complex models.
The Concept of Gradient Descent
Gradient descent is an iterative optimization algorithm for minimizing a function, usually a loss function, quantifying the disparity between predicted and actual results. The goal of gradient descent is to find the parameters that minimize the value of the loss function. Importantly, gradient descent navigates its way to the minimum of the function by moving iteratively toward the direction of the steepest descent. However, to leverage gradient descent, the target function must be differentiable.
Taking Steps with Gradient Descent
Gradient descent derives its name from its working mechanism: taking descents along the gradient. It operates in several iterative steps as follows:
Choose random values for initial parameters.
Calculate the cost (the difference between actual and predicted value).
Compute the gradient (the steepest slope of the function around that point).
Update the parameters using the gradient.
Repeat steps 2 to 4 until we reach an acceptable error rate or exhaust the maximum iterations.
A vital component of gradient descent is the learning rate, which determines the size of the descent towards the optimum solution. It is important to note that if the learning rate is too high, we may overshoot the minimum, and if it's too low, the convergence to the minimum may take too long.
Implementing Gradient Descent in Python: The Cost Function
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
Let's implement it from scratch with a basic understanding of the gradient descent algorithm. We will need two functions: one for calculating the cost and another for calculating and applying the gradient to update our parameters. Moreover, we'll add an early stop mechanism that will halt computations after a predefined number of iterations.
The cost function is as follows:
J(X,y,θ)=m1i=1∑m(X⋅θ−yi)2
where J is the cost, X is the data, y is the actual values, θ is the parameters, and m is the length of y. It is the calculation of the mean square error.
Python
import numpy as npdef cost(X, y, theta): m = len(y) predictions = X.dot(theta) cost = (1/m) * np.sum(np.square(predictions-y)) # Compute mean square error return cost
Implementing Gradient Descent in Python: The Gradient Descent
Applying Gradient Descent to Linear Regression
Lesson Summary and Practice
Congratulations! You have mastered implementing the gradient descent algorithm and its application to linear regression. We covered theoretical explanations, derived the math behind the cost function and the gradient descent update rule, and brought these concepts to life by coding in Python.
It is now time to practice and solidify what you have learned. In the upcoming exercises, challenge yourself with different problems and experiment with varying parameters like the learning rate. Enjoy your journey into the world of gradients!
Next, for the gradient descent function, we follow the gradient descent update rule:
θ:=θ−αm1XT⋅(X⋅θ−y)
Here, α is the learning rate, which determines the size of our steps in the descent. XT is the transpose of the data. Note, that it should have been multiplied by 2, as we take the derivative of a the mean squared error, but we can ignore this 2 and just consider it as a part of the learning rate coefficient.
Python
def gradient_descent(X, y, theta, alpha, iterations): m = len(y) cost_history = np.zeros(iterations) theta_history = np.zeros((iterations,2)) for i in range(iterations): # Iterate until convergence prediction = np.dot(X,theta) # Matrix multiplication between X and theta theta = theta - (1/m)*alpha*(X.T.dot((prediction - y))) # Gradient update rule theta_history[i,:] = theta.T cost_history[i] = cost(X,y,theta) return theta, cost_history, theta_history
Let's apply our gradient descent function to a simple linear regression problem. The form of linear regression is:
y=ax+b
where a and b are the parameters, θ, we need to learn. The following data have been generated based on this form with some noise.
Note that after adding the bias column, X_b has shape (100, 2) — one column of ones for the intercept and one column for the feature. Accordingly, theta must have shape (2, 1) (i.e., number of features + 1, 1) so that the matrix multiplication X_b.dot(theta) is valid. Here, theta[0] corresponds to the intercept b and theta[1] corresponds to the slope a.
Python
X = 2 * np.random.rand(100,1)y = 4 +3 * X+np.random.randn(100,1)lr = 0.01 # Learning Raten_iter = 1000 # Max number of iterationstheta = np.random.randn(2,1) # Randomly initialized parameters, shape (2, 1)X_b = np.c_[np.ones((len(X),1)),X] # add bias parameter to X, shape (100, 2)theta, cost_history, theta_history = gradient_descent(X_b,y,theta,lr,n_iter) # Gradient Descent
