COSC 202: Gradient Descent

• Lecture 18 focuses on Gradient Descent within COSC 202 Data Science and AI
• The lecture discusses how to train a Neural Network, and the different gradient descent algorithms including:
  • Gradient Descent
  • Stochastic Gradient Descent
  • Mini-batch Gradient Descent

How to Train a Neural Network?

• Machine learning aims to find the best model for a given situation
• The best model minimizes the error
• The best model represents the solution to an optimization problem
• Gradient Descent is an optimization algorithm to find the best weights and biases for accurate predictions in neural networks
• The network calculates the gradient, which is the partial derivative from Calculus, of the error
• Gradient is calculated as the the difference between the network's predictions and the actual values, with respect to the weights and biases
• The gradient indicates the direction in which the function increases most quickly

Understanding Gradient Descent

• Gradient descent is like descending a hill to reach the lowest point (the valley).
• You can only feel the slope beneath your feet, unable to see the entire landscape
• It involves taking small steps in the direction of the steepest descent to reach the valley
• Gradient descent adjusts weights and biases by computing the gradients (slopes) of the cost function relative to each weight and bias
• The algorithm reduce the cost each step
• Updates to weights and biases happen in the direction opposite of the gradients
• A common cost function is mean squared error, appropriate for regression problems
• When the gradient is zero you have reached the global cost minimum

Gradient Descent Details

• When f(z) is a multivariable function, it possesses multiple partial derivatives; each shows how f(z) changes with small changes in a single input variable
• Assume a perceptron with two inputs and a ReLU activation function
• Loss function is based on Mean Squared Error
• The goal is to minimize loss by tweaking the weights and bias using gradient descent
• ReLU activation function is used
• The loss function is MSE = 1/n * Σ (yi - max(0, w1x1 + w2x2 + b))^2
• To find the slope, find the partial derivative with respect to the weights and with respect to the bias, since these are the values you are tweaking
• ReLU step function is non-differentiable
• The new weight becomes w_next_step = w - α∇MSE α is the learning rate, a hyperparameter representing the step size
• When the derivative is positive for one of the weights, a step is taken to the left
• After reducing the weight, there is now a lower loss
• The derivative is taken again with another step toward the local minimum, and repeated
• When the derivative is negative, a step is taken to the right

The Learning Rate and Initialization State

• The size of the steps (learning rate) and the initial state are hyperparameters when training a neural network
• A small learning rate will require many iterations to converge
• A too high learning rate might jump across the local minimum, possibly going higher than before which might make the algorithm diverge, with larger and larger values, and failing to find a good solution
• If the initialization state starts on the left, then it converges to a local minimum, not the global minimum
• If it starts on the right, it will take a very long time to cross the plateau
• Stopping too early prevents reaching the global minimum

Batch Gradient Descent

• Batch gradient descent is performed over the whole training set in an iterative manner
• Epochs are hyperparameter that refers to the number of complete passes through the entire training dataset, where the model parameters are updated iteratively across multiple epochs
• This is slow, especially for big datasets since every update requires processing the entire dataset

Stochastic Gradient Descent

• Stochastic Gradient Descent picks a random instance in the training set at every step and computes the gradients based only on that single instance, making it faster due to little data manipulation per iteration
• Makes it possible to train on huge training sets
• It's stochastic (random) nature makes the algorithm less regular than Batch Gradient Descent:
  • Instead of decreasing gently to the minimum, the cost function decreases on average by bouncing up and down
  • Over time, the function ends up close to the minimum but bounces around instead of settling.
• Stochastic Gradient Descent has a better chance of finding the global minimum than Batch Gradient Descent

Mini-Batch Gradient Descent

• Mini-batch GD computes the gradients on small random sets of instances called mini-batches
• batch_size is a hyperparameter
• Algorithm progresses through parameter space less erratically than Stochastic GD, especially with relatively large mini-batches
• Mini-batch GD walks around a bit closer to the minimum than Stochastic GD but it can struggle to escape from local minima

Summary of Algorithms

• Batch Gradient Descent:
  • Updates based on the entire dataset
  • High computational cost
  • Cost function reduces slowly
• Stochastic Gradient Descent
  • Updates based on a single observation
  • Fast update, but it can take longer to converge
  • High variation in the cost function
• Mini-batch Gradient Descent
  • Updates based on a subset of data (batch size)
  • Lower cost than batch gradient descent and faster than SGD
  • Smoother cost function compared to SGD