Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) is a popular optimization algorithm used in machine learning. It is used to train models by finding the best values for their parameters.

To understand SGD, let's first talk about Gradient Descent. Gradient Descent is a method for finding the minimum of a function. In the context of machine learning, this function represents the "error" or "loss" of a model, which measures how well the model is performing on a given task.

In traditional Gradient Descent, you calculate the gradient of the loss function with respect to each parameter of the model. The gradient tells you the direction in which the parameters should be updated to reduce the loss. You update the parameters by taking small steps in the opposite direction of the gradient until you reach a minimum.

Now, let's introduce the "stochastic" part of SGD. In Stochastic Gradient Descent, instead of calculating the gradient using the entire dataset, you calculate it on a single random example (or a small subset of examples) at each iteration. This randomness is what makes SGD "stochastic."

Why would we want to do that? Well, when working with large datasets, computing the gradient on the entire dataset can be computationally expensive. By using only a small subset or a single example, SGD significantly reduces the computational burden.

Moreover, SGD has a nice property: it introduces some randomness in the learning process. The random selection of examples can help the model avoid getting stuck in local minima (suboptimal solutions). It allows the model to explore different areas of the parameter space, potentially finding a better overall minimum.

However, there is a trade-off with this randomness. Since SGD uses only a subset of examples, the gradient it computes may not be as accurate as the one from traditional Gradient Descent. This introduces some noise in the optimization process. However, in practice, this noise is often tolerable and can even help the model generalize better to new, unseen data.

To summarize, Stochastic Gradient Descent is an optimization algorithm that updates the parameters of a model by computing the gradient of the loss function on a single random example or a small subset of examples. It is faster and more scalable for large datasets, introduces randomness to avoid local minima, but sacrifices some accuracy for faster computations.

Python Example

import numpy as np

# Generate some random training data
X = 2 * np.random.rand(100, 1)  # Input features
y = 4 + 3 * X + np.random.randn(100, 1)  # Target labels with noise

# Add bias term to input features
X_b = np.c_[np.ones((100, 1)), X]

# Set random seed for reproducibility
np.random.seed(42)

# Initialize random weights
theta = np.random.randn(2, 1)

# Set hyperparameters
learning_rate = 0.1
n_epochs = 100
m = len(X)

# Stochastic Gradient Descent
for epoch in range(n_epochs):
  for i in range(m):
    random_index = np.random.randint(m)  # Randomly select an example
    
    xi = X_b[random_index:random_index+1]
    yi = y[random_index:random_index+1]
    
    gradients = 2 * xi.T.dot(xi.dot(theta) - yi)  # Compute gradient
    theta = theta - learning_rate * gradients  # Update weights

# Print the learned parameters
print("Intercept:", theta[0][0])
print("Slope:", theta[1][0])

Results:

Intercept: 4.223113526238277
Slope: 2.734026492950525

In this example, we generate some random training data with a linear relationship between the input features (X) and the target labels (y). We add a bias term to the input features and initialize random weights.

The Stochastic Gradient Descent loop iterates over a fixed number of epochs. For each epoch, it randomly selects a single example from the dataset. It computes the gradient of the loss function with respect to the weights using this example and updates the weights accordingly.

At the end of the loop, the learned parameters (intercept and slope) are printed. These parameters represent the best-fit line that the Stochastic Gradient Descent algorithm has found to approximate the data.