1. Understanding Gradient Descent<\/h2>\n\n\n\nWhat is Gradient Descent?<\/h3>\n\n\n\n
Gradient Descent is an optimization algorithm used to minimize the cost function in machine learning models. The cost function, also known as the loss function, measures the difference between the predicted values and the actual values. Gradient Descent iteratively adjusts the model parameters to minimize this cost function.<\/p>\n\n\n\n
Types of Gradient Descent<\/h3>\n\n\n\n
There are three main types of Gradient Descent:<\/p>\n\n\n\n
- \n
- Batch Gradient Descent<\/strong>: Uses the entire dataset to compute the gradient at each step.<\/li>\n\n\n\n
- Stochastic Gradient Descent (SGD)<\/strong>: Uses one data point at a time to compute the gradient.<\/li>\n\n\n\n
- Mini-Batch Gradient Descent<\/strong>: Uses a small subset of the dataset to compute the gradient at each step.<\/li>\n<\/ol>\n\n\n\n
The Mathematics Behind Gradient Descent<\/h3>\n\n\n\n
The core idea of Gradient Descent is to use the gradient (the vector of partial derivatives) of the cost function to adjust the parameters in the opposite direction of the gradient. This is because the gradient points in the direction of the steepest increase in the cost function, so moving in the opposite direction decreases the cost.<\/p>\n\n\n\n
The update rule for the parameters (
) in Gradient Descent is:<\/p>\n\n\n\n
<\/p>\n\n\n\n
Where:<\/p>\n\n\n\n
- \n
is the learning rate, a small positive number that controls the step size.<\/li>\n\n\n\n
is the cost function.<\/li>\n\n\n\n
is the gradient of the cost function with respect to (\\theta).<\/li>\n<\/ul>\n\n\n\n
2. Implementing Gradient Descent in Python<\/h2>\n\n\n\n
Setting Up the Environment<\/h3>\n\n\n\n
First, let’s set up our Python environment. Ensure you have Python installed, along with essential libraries like NumPy and Matplotlib. You can install them using pip if you haven’t already:<\/p>\n\n\n
pip install numpy matplotlib<\/code><\/span>Code language:<\/span> Bash<\/span> (<\/span>bash<\/span>)<\/span><\/small><\/pre>\n\n\nDataset Preparation<\/h3>\n\n\n\n
For this tutorial, we’ll use a simple synthetic dataset for linear regression. Let’s create a dataset with a single feature and a target variable.<\/p>\n\n\n
import<\/span> numpy as<\/span> np\nimport<\/span> matplotlib.pyplot as<\/span> plt\n\n# Seed for reproducibility<\/span>\nnp.random.seed(42<\/span>)\n\n# Generate synthetic data<\/span>\nX = 2<\/span> * np.random.rand(100<\/span>, 1<\/span>)\ny = 4<\/span> + 3<\/span> * X + np.random.randn(100<\/span>, 1<\/span>)\n\n# Plot the data<\/span>\nplt.scatter(X, y)\nplt.xlabel('Feature'<\/span>)\nplt.ylabel('Target'<\/span>)\nplt.title('Synthetic Data'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nLinear Regression and Cost Function<\/h3>\n\n\n\n
Next, we define our linear regression model and the cost function. The model can be represented as:<\/p>\n\n\n\n
<\/p>\n\n\n\n
The cost function for linear regression is the Mean Squared Error (MSE):<\/p>\n\n\n\n
<\/p>\n\n\n\n
Where:<\/p>\n\n\n\n
- \n
is the number of training examples.<\/li>\n\n\n\n
is the predicted value for the
-th training example.<\/li>\n\n\n\n
is the actual value for the
Let’s implement these in Python:<\/p>\n\n\n
def<\/span> predict<\/span>(X, theta)<\/span>:<\/span>\n return<\/span> X.dot(theta)\n\ndef<\/span> compute_cost<\/span>(X, y, theta)<\/span>:<\/span>\n m = len(y)\n predictions = predict(X, theta)\n cost = (1<\/span> \/ (2<\/span> * m)) * np.sum((predictions - y) ** 2<\/span>)\n return<\/span> cost<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nImplementing Batch Gradient Descent<\/h3>\n\n\n\n
Now, we’ll implement Batch Gradient Descent. This involves updating the parameters using the entire dataset at each step.<\/p>\n\n\n
def<\/span> batch_gradient_descent<\/span>(X, y, theta, learning_rate, iterations)<\/span>:<\/span>\n m = len(y)\n cost_history = np.zeros(iterations)\n\n for<\/span> i in<\/span> range(iterations):\n gradients = (1<\/span> \/ m) * X.T.dot(predict(X, theta) - y)\n theta = theta - learning_rate * gradients\n cost_history[i] = compute_cost(X, y, theta)\n\n return<\/span> theta, cost_history\n\n# Prepare the data (add a column of ones for the bias term)<\/span>\nX_b = np.c_[np.ones((100<\/span>, 1<\/span>)), X]\ntheta = np.random.randn(2<\/span>, 1<\/span>)\nlearning_rate = 0.1<\/span>\niterations = 1000<\/span>\n\ntheta_final, cost_history = batch_gradient_descent(X_b, y, theta, learning_rate, iterations)\n\nprint(\"Final parameters:\"<\/span>, theta_final)\nplt.plot(range(iterations), cost_history)\nplt.xlabel('Iterations'<\/span>)\nplt.ylabel('Cost'<\/span>)\nplt.title('Cost Function History'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nImplementing Stochastic Gradient Descent<\/h3>\n\n\n\n
Stochastic Gradient Descent (SGD) updates the parameters using one data point at a time. This can lead to faster convergence on large datasets, though it can be more noisy.<\/p>\n\n\n
def<\/span> stochastic_gradient_descent<\/span>(X, y, theta, learning_rate, iterations)<\/span>:<\/span>\n m = len(y)\n cost_history = np.zeros(iterations)\n\n for<\/span> i in<\/span> range(iterations):\n for<\/span> j in<\/span> range(m):\n random_index = np.random.randint(m)\n xi = X[random_index:random_index+1<\/span>]\n yi = y[random_index:random_index+1<\/span>]\n gradients = 2<\/span> * xi.T.dot(predict(xi, theta) - yi)\n theta = theta - learning_rate * gradients\n cost_history[i] = compute_cost(X, y, theta)\n\n return<\/span> theta, cost_history\n\ntheta = np.random.randn(2<\/span>, 1<\/span>)\nlearning_rate = 0.01<\/span>\niterations = 50<\/span>\n\ntheta_final, cost_history = stochastic_gradient_descent(X_b, y, theta, learning_rate, iterations)\n\nprint(\"Final parameters:\"<\/span>, theta_final)\nplt.plot(range(iterations), cost_history)\nplt.xlabel('Iterations'<\/span>)\nplt.ylabel('Cost'<\/span>)\nplt.title('Cost Function History'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nImplementing Mini-Batch Gradient Descent<\/h3>\n\n\n\n
Mini-Batch Gradient Descent is a compromise between Batch Gradient Descent and SGD. It uses a small subset (batch) of the dataset at each step to compute the gradient.<\/p>\n\n\n
def<\/span> mini_batch_gradient_descent<\/span>(X, y, theta, learning_rate, iterations, batch_size)<\/span>:<\/span>\n m = len(y)\n cost_history = np.zeros(iterations)\n\n for<\/span> i in<\/span> range(iterations):\n shuffled_indices = np.random.permutation(m)\n X_shuffled = X[shuffled_indices]\n y_shuffled = y[shuffled_indices]\n\n for<\/span> j in<\/span> range(0<\/span>, m, batch_size):\n xi = X_shuffled[j:j+batch_size]\n yi = y_shuffled[j:j+batch_size]\n gradients = (1<\/span> \/ batch_size) * xi.T.dot(predict(xi, theta) - yi)\n theta = theta - learning_rate * gradients\n cost_history[i] = compute_cost(X, y, theta)\n\n return<\/span> theta, cost_history\n\ntheta = np.random.randn(2<\/span>, 1<\/span>)\nlearning_rate = 0.1<\/span>\niterations = 200<\/span>\nbatch_size = 20<\/span>\n\ntheta_final, cost_history = mini_batch_gradient_descent(X_b, y, theta, learning_rate, iterations, batch_size)\n\nprint(\"Final parameters:\"<\/span>, theta_final)\nplt.plot(range(iterations), cost_history)\nplt.xlabel('Iterations'<\/span>)\nplt.ylabel('Cost'<\/span>)\nplt.title('Cost Function History'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n3. Advanced Topics<\/h2>\n\n\n\n
Learning Rate Schedules<\/h3>\n\n\n\n
A static learning rate may not always be optimal. A learning rate schedule adjusts the learning rate over time to improve convergence.<\/p>\n\n\n
def<\/span> learning_rate_schedule<\/span>(t, t0=5<\/span>, t1=50<\/span>)<\/span>:<\/span>\n return<\/span> t0 \/ (t + t1)\n\ndef<\/span> sgd_with_schedule<\/span>(X, y, theta, iterations)<\/span>:<\/span>\n m = len(y)\n cost_history = np.zeros(iterations)\n\n for<\/span> epoch in<\/span> range(iterations):\n for<\/span> i in<\/span> range(m\n\n):\n random_index = np.random.randint(m)\n xi = X[random_index:random_index+1<\/span>]\n yi = y[random_index:random_index+1<\/span>]\n gradients = 2<\/span> * xi.T.dot(predict(xi, theta) - yi)\n learning_rate = learning_rate_schedule(epoch * m + i)\n theta = theta - learning_rate * gradients\n cost_history[epoch] = compute_cost(X, y, theta)\n\n return<\/span> theta, cost_history\n\ntheta = np.random.randn(2<\/span>, 1<\/span>)\niterations = 50<\/span>\n\ntheta_final, cost_history = sgd_with_schedule(X_b, y, theta, iterations)\n\nprint(\"Final parameters:\"<\/span>, theta_final)\nplt.plot(range(iterations), cost_history)\nplt.xlabel('Iterations'<\/span>)\nplt.ylabel('Cost'<\/span>)\nplt.title('Cost Function History with Learning Rate Schedule'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nGradient Descent with Momentum<\/h3>\n\n\n\n
Momentum helps accelerate Gradient Descent in the relevant direction and dampens oscillations.<\/p>\n\n\n
def<\/span> gradient_descent_with_momentum<\/span>(X, y, theta, learning_rate, iterations, beta=0.9<\/span>)<\/span>:<\/span>\n m = len(y)\n cost_history = np.zeros(iterations)\n v = np.zeros(theta.shape)\n\n for<\/span> i in<\/span> range(iterations):\n gradients = (1<\/span> \/ m) * X.T.dot(predict(X, theta) - y)\n v = beta * v + (1<\/span> - beta) * gradients\n theta = theta - learning_rate * v\n cost_history[i] = compute_cost(X, y, theta)\n\n return<\/span> theta, cost_history\n\ntheta = np.random.randn(2<\/span>, 1<\/span>)\nlearning_rate = 0.1<\/span>\niterations = 1000<\/span>\n\ntheta_final, cost_history = gradient_descent_with_momentum(X_b, y, theta, learning_rate, iterations)\n\nprint(\"Final parameters:\"<\/span>, theta_final)\nplt.plot(range(iterations), cost_history)\nplt.xlabel('Iterations'<\/span>)\nplt.ylabel('Cost'<\/span>)\nplt.title('Cost Function History with Momentum'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nAdaptive Gradient Descent Methods (AdaGrad, RMSProp, Adam)<\/h3>\n\n\n\n
Adaptive methods adjust the learning rate based on past gradients.<\/p>\n\n\n\n
AdaGrad<\/strong>:<\/p>\n\n\n
def<\/span> adagrad<\/span>(X, y, theta, learning_rate, iterations, epsilon=1e-8<\/span>)<\/span>:<\/span>\n m = len(y)\n cost_history = np.zeros(iterations)\n G = np.zeros(theta.shape)\n\n for<\/span> i in<\/span> range(iterations):\n gradients = (1<\/span> \/ m) * X.T.dot(predict(X, theta) - y)\n G += gradients ** 2<\/span>\n adjusted_gradients = gradients \/ (np.sqrt(G) + epsilon)\n theta = theta - learning_rate * adjusted_gradients\n cost_history[i] = compute_cost(X, y, theta)\n\n return<\/span> theta, cost_history\n\ntheta = np.random.randn(2<\/span>, 1<\/span>)\nlearning_rate = 0.1<\/span>\niterations = 1000<\/span>\n\ntheta_final, cost_history = adagrad(X_b, y, theta, learning_rate, iterations)\n\nprint(\"Final parameters:\"<\/span>, theta_final)\nplt.plot(range(iterations), cost_history)\nplt.xlabel('Iterations'<\/span>)\nplt.ylabel('Cost'<\/span>)\nplt.title('Cost Function History with AdaGrad'<\/span>)\nplt.show()<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nRMSProp<\/strong>:<\/p>\n\n\n
- Stochastic Gradient Descent (SGD)<\/strong>: Uses one data point at a time to compute the gradient.<\/li>\n\n\n\n