xbe.at

Deep learning / Backpropagation and optimization

Gradient Descent The Optimization Algorithm Powering AI Models

7 min read, 15 sections

Contents
  1. Introduction to Gradient Descent
  2. The Gradient
  3. The Optimization Process
  4. Learning Rate
  5. Local vs Global Minima
  6. Stochastic Gradient Descent
  7. Momentum
  8. Adaptive Learning Rates
  9. Gradient Descent in Neural Networks
  10. Gradient Descent in Practice
  11. Challenges and Limitations
  12. Beyond Vanilla Gradient Descent
  13. Real-life Example: Image Classification
  14. Real-life Example: Natural Language Processing
  15. Additional Resources

Introduction to Gradient Descent

Gradient Descent is a fundamental optimization algorithm in machine learning and artificial intelligence. It's used to minimize a function by iteratively moving in the direction of steepest descent. In AI, it's the backbone of training neural networks and other models.

import matplotlib.pyplot as plt
import numpy as np

def f(x):
    return x**2 + 5*np.sin(x)

x = np.linspace(-10, 10, 100)
y = f(x)

plt.plot(x, y)
plt.title('Function to Optimize')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.show()

The Gradient

The gradient is a vector of partial derivatives that points in the direction of steepest ascent. To minimize a function, we move in the opposite direction of the gradient.

def gradient(x):
    return 2*x + 5*np.cos(x)

x = np.linspace(-10, 10, 100)
grad = gradient(x)

plt.plot(x, grad)
plt.title('Gradient of the Function')
plt.xlabel('x')
plt.ylabel('Gradient')
plt.axhline(y=0, color='r', linestyle='--')
plt.show()

The Optimization Process

Gradient Descent iteratively updates the parameters by subtracting the gradient multiplied by a learning rate. This process continues until convergence or a maximum number of iterations is reached.

def gradient_descent(start, learn_rate, n_iter):
    x = start
    for i in range(n_iter):
        grad = gradient(x)
        x = x - learn_rate * grad
    return x

result = gradient_descent(start=5, learn_rate=0.1, n_iter=100)
print(f"Optimized x: {result}")
print(f"Optimized f(x): {f(result)}")

Learning Rate

The learning rate is a crucial hyperparameter in Gradient Descent. It determines the step size at each iteration. If it's too small, convergence will be slow. If it's too large, the algorithm might overshoot the minimum.

learning_rates = [0.01, 0.1, 0.5]
colors = ['r', 'g', 'b']

for lr, c in zip(learning_rates, colors):
    x = 5
    path = [x]
    for _ in range(20):
        x = x - lr * gradient(x)
        path.append(x)
    plt.plot(path, f(np.array(path)), c=c, label=f'LR = {lr}')

plt.legend()
plt.title('Effect of Learning Rate')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.show()

Local vs Global Minima

Gradient Descent can get stuck in local minima, especially for non-convex functions. This is why initialization and other techniques like momentum are important.

def complex_function(x):
    return x**4 - 4*x**3 - 2*x**2 + 12*x

x = np.linspace(-2, 3, 100)
y = complex_function(x)

plt.plot(x, y)
plt.title('Function with Multiple Minima')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.show()

Stochastic Gradient Descent

In practice, especially for large datasets, we often use Stochastic Gradient Descent (SGD). SGD computes the gradient using only a small subset (mini-batch) of the data at each iteration.

def sgd(X, y, learning_rate, n_epochs):
    w = np.zeros(X.shape[1])
    for epoch in range(n_epochs):
        for i in range(X.shape[0]):
            gradient = 2 * X[i] * (np.dot(X[i], w) - y[i])
            w -= learning_rate * gradient
    return w

# Example usage
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([5, 11, 17])
w = sgd(X, y, learning_rate=0.01, n_epochs=1000)
print("Optimized weights:", w)

Momentum

Momentum is a technique to accelerate Gradient Descent by adding a fraction of the previous update to the current one. This helps overcome local minima and plateaus.

def momentum_gd(gradient, start, learn_rate, momentum, n_iter):
    x = start
    v = 0
    for _ in range(n_iter):
        grad = gradient(x)
        v = momentum * v - learn_rate * grad
        x += v
    return x

result = momentum_gd(gradient, start=5, learn_rate=0.1, momentum=0.9, n_iter=100)
print(f"Optimized x: {result}")
print(f"Optimized f(x): {f(result)}")

Adaptive Learning Rates

Algorithms like AdaGrad, RMSProp, and Adam adapt the learning rate for each parameter. This can lead to faster convergence and better performance.

def adagrad(gradient, start, learn_rate, n_iter):
    x = start
    g_sum = 0
    for _ in range(n_iter):
        grad = gradient(x)
        g_sum += grad**2
        x -= (learn_rate / (np.sqrt(g_sum) + 1e-8)) * grad
    return x

result = adagrad(gradient, start=5, learn_rate=0.1, n_iter=100)
print(f"Optimized x: {result}")
print(f"Optimized f(x): {f(result)}")

Gradient Descent in Neural Networks

In neural networks, Gradient Descent is used to update the weights and biases. Backpropagation is used to efficiently compute the gradients.

import numpy as np

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

def nn_forward(X, W1, W2):
    Z1 = np.dot(X, W1)
    A1 = sigmoid(Z1)
    Z2 = np.dot(A1, W2)
    A2 = sigmoid(Z2)
    return A1, A2

def nn_backward(X, y, A1, A2, W2):
    m = X.shape[0]
    dZ2 = A2 - y
    dW2 = np.dot(A1.T, dZ2) / m
    dZ1 = np.dot(dZ2, W2.T) * A1 * (1 - A1)
    dW1 = np.dot(X.T, dZ1) / m
    return dW1, dW2

# Example usage
X = np.array([[0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1]])
y = np.array([[0], [1], [1], [0]])
W1 = np.random.randn(3, 4)
W2 = np.random.randn(4, 1)

for _ in range(10000):
    A1, A2 = nn_forward(X, W1, W2)
    dW1, dW2 = nn_backward(X, y, A1, A2, W2)
    W1 -= 0.1 * dW1
    W2 -= 0.1 * dW2

print("Final predictions:", nn_forward(X, W1, W2)[1])

Gradient Descent in Practice

In real-world applications, Gradient Descent is used in various machine learning tasks, such as training recommender systems, natural language processing models, and computer vision algorithms.

import numpy as np

# Simple linear regression using gradient descent
def linear_regression_gd(X, y, learning_rate, n_iterations):
    m, n = X.shape
    theta = np.zeros(n)
    
    for _ in range(n_iterations):
        h = np.dot(X, theta)
        gradient = np.dot(X.T, (h - y)) / m
        theta -= learning_rate * gradient
    
    return theta

# Generate sample data
np.random.seed(42)
X = np.column_stack((np.ones(100), np.random.rand(100, 1)))
y = 2 + 3 * X[:, 1] + np.random.randn(100) * 0.1

# Train the model
theta = linear_regression_gd(X, y, learning_rate=0.1, n_iterations=1000)

print("Estimated coefficients:", theta)

Challenges and Limitations

While Gradient Descent is powerful, it faces challenges like slow convergence for ill-conditioned problems, difficulty with saddle points, and sensitivity to scaling of input variables.

import numpy as np
import matplotlib.pyplot as plt

def rosenbrock(x, y):
    return (1 - x)**2 + 100 * (y - x**2)**2

x = np.linspace(-2, 2, 100)
y = np.linspace(-1, 3, 100)
X, Y = np.meshgrid(x, y)
Z = rosenbrock(X, Y)

plt.contour(X, Y, Z, levels=np.logspace(-1, 3, 20))
plt.colorbar()
plt.title('Rosenbrock Function - A Challenging Optimization Landscape')
plt.xlabel('x')
plt.ylabel('y')
plt.show()

Beyond Vanilla Gradient Descent

Advanced techniques like conjugate gradient, Quasi-Newton methods (e.g., BFGS), and Hessian-free optimization can sometimes outperform standard Gradient Descent.

from scipy.optimize import minimize

def rosenbrock(x):
    return (1 - x[0])**2 + 100 * (x[1] - x[0]**2)**2

# Using BFGS algorithm
result = minimize(rosenbrock, [0, 0], method='BFGS')

print("Optimized solution:", result.x)
print("Optimized value:", result.fun)

Real-life Example: Image Classification

Gradient Descent is crucial in training convolutional neural networks (CNNs) for image classification tasks, such as identifying objects in photographs or recognizing handwritten digits.

import numpy as np

def conv2d(image, kernel):
    h, w = image.shape
    k_h, k_w = kernel.shape
    output = np.zeros((h-k_h+1, w-k_w+1))
    for i in range(h-k_h+1):
        for j in range(w-k_w+1):
            output[i,j] = np.sum(image[i:i+k_h, j:j+k_w] * kernel)
    return output

# Simple edge detection kernel
kernel = np.array([[-1, -1, -1],
                   [-1,  8, -1],
                   [-1, -1, -1]])

# Example image (5x5 grayscale)
image = np.array([[0, 0, 0, 0, 0],
                  [0, 1, 1, 1, 0],
                  [0, 1, 1, 1, 0],
                  [0, 1, 1, 1, 0],
                  [0, 0, 0, 0, 0]])

result = conv2d(image, kernel)
print("Convolution result (edge detection):")
print(result)

Real-life Example: Natural Language Processing

In NLP tasks like sentiment analysis or language translation, Gradient Descent optimizes the parameters of recurrent neural networks (RNNs) or transformers to capture complex language patterns.

import numpy as np

def softmax(x):
    exp_x = np.exp(x - np.max(x))
    return exp_x / exp_x.sum(axis=0)

def simple_rnn_step(x, h, W_hh, W_xh, W_hy):
    h_next = np.tanh(np.dot(W_hh, h) + np.dot(W_xh, x))
    y = softmax(np.dot(W_hy, h_next))
    return h_next, y

# Example usage
vocab_size = 1000
hidden_size = 100
output_size = 5  # e.g., 5 sentiment classes

# Initialize weights randomly
W_hh = np.random.randn(hidden_size, hidden_size) * 0.01
W_xh = np.random.randn(hidden_size, vocab_size) * 0.01
W_hy = np.random.randn(output_size, hidden_size) * 0.01

# Example input (one-hot encoded word)
x = np.zeros(vocab_size)
x[42] = 1  # Assuming word index 42

h = np.zeros(hidden_size)
h_next, y = simple_rnn_step(x, h, W_hh, W_xh, W_hy)

print("Predicted sentiment probabilities:", y)

Additional Resources

For those interested in diving deeper into Gradient Descent and optimization techniques, here are some valuable resources:

  1. "Optimization Methods for Large-Scale Machine Learning" by Bottou et al. (2018) ArXiv: https://arxiv.org/abs/1606.04838
  2. "An Overview of Gradient Descent Optimization Algorithms" by Ruder (2016) ArXiv: https://arxiv.org/abs/1609.04747
  3. "Adam: A Method for Stochastic Optimization" by Kingma and Ba (2014) ArXiv: https://arxiv.org/abs/1412.6980

These papers provide comprehensive overviews and in-depth analyses of various Gradient Descent algorithms and their applications in machine learning.

More in Backpropagation and optimization

  1. Implementing Batch Gradient Descent in Python7 min

    Batch Gradient Descent is a fundamental optimization algorithm used in machine learning to minimize the cost function of a model. It updates the model...

  2. Gradient Descent Fundamentals for Machine Learning8 min

    Gradient Descent is an iterative optimization algorithm used to minimize a cost function by updating parameters in the opposite direction of the gradient. It...

  3. Introduction to Gradient Descent in Python7 min

    Gradient descent is a fundamental optimization algorithm in machine learning and deep learning. It's used to minimize a cost function by iteratively moving...

  4. Gradient Descent from Scratch in Python7 min

    Gradient descent is a fundamental optimization algorithm used in machine learning to minimize the cost function of a model. It iteratively adjusts the...

  5. Mastering Artificial Neural Networks Feedforward and Backpropagation Fundamentals6 min

    Artificial Neural Networks (ANNs) are computational models inspired by biological neural networks. They consist of interconnected nodes (neurons) organized...

  6. Gradient Descent for Neural Networks in Python4 min

    Gradient descent is an optimization algorithm used to find the minimum of a function by iteratively adjusting the parameters in the direction of the negative...