Backpropagation: The Algorithm Powering Modern Machine Learning

The Universal Algorithm in Machine Learning

Nearly all machine learning systems, from GPT and AlphaFold to various models of the brain, share a common foundation despite their diverse architectures and applications. This universal algorithm, known as backpropagation, forms the cornerstone of the entire field of machine learning. While often overlooked in its details, backpropagation is what enables artificial neural networks to learn. Interestingly, it's also what makes them fundamentally different from and incompatible with biological brains.

The Origins of Backpropagation

The history of backpropagation is somewhat ambiguous, with certain concepts traceable to Leibniz in the 17th century. However, the modern formulation still in use today is generally attributed to Seppo Linnainmaa, who published it in his 1970 master's thesis. Linnainmaa didn't explicitly reference neural networks, but his work laid the groundwork for future developments.

A significant milestone occurred in 1986 when David Rumelhart, Geoffrey Hinton, and Ronald Williams published their paper "Learning representations by back-propagating errors." They applied the backpropagation algorithm to multi-layer perceptrons, demonstrating for the first time that training with backpropagation allows networks to solve problems and develop meaningful representations at the hidden neuron level.

As the field progressed, researchers scaled up these models significantly and introduced various architectures. However, the fundamental principles of training remained largely unchanged.

Understanding Backpropagation: A Ground-Up Approach

To gain a comprehensive understanding of what it means to train a network, let's build the concept of backpropagation from the ground up.

The Curve Fitting Problem

Imagine you have collected a set of points (x,y) on a plane and want to describe their relationship. You need to fit a curve y(x) that best represents the data. Since there are infinitely many possible functions, we need to make some assumptions.

Let's assume we want to find a smooth approximation of the data using a polynomial of degree 5. This means the resulting curve will be a combination of a constant term, a polynomial of degree 1 (a straight line), a parabola, and so on up to a power of five, each weighted by specific coefficients.

The equation for the curve would look like this:

y(x) = k0 + k1x + k2x^2 + k3x^3 + k4x^4 + k5x^5

where each k is an arbitrary real number. Our job is to find the configuration of k0 through k5 that leads to the best-fitting curve.

Defining the Best Fit

To make the problem unambiguous, we need to agree on what "best curve" means. While visual inspection is possible, it's subjective and impractical for large datasets. We need an objective measurement - a numerical value that quantifies the quality of a fit.

A popular method is to measure the square distance between data points and the fitted curve. A high value suggests that the data points are significantly far from the curve, indicating a poor approximation. Conversely, low values indicate a better fit as the curve closely aligns with the data points.

This measurement is commonly referred to as a "loss," and the objective is to minimize it. The loss is effectively a function of parameters, so it's usually called a loss function.

The Loss Function

It's important not to confuse two different functions we're dealing with:

1. The function y(x), which has one input number and one output number and defines the curve itself.
2. The loss function, which has six inputs (k0 through k5) and outputs a single number - the value of the loss.

Our job is to find the configuration of k's that yields a minimum loss, or in other words, to minimize the loss function with respect to the coefficients.

The Curve Fitter 6000

Let's imagine a machine called the Curve Fitter 6000, designed to simplify manual calculations. It has six adjustable knobs for k0 through k5, which we can freely turn. We initialize the machine with our data points, and for each setting of the knobs, it evaluates the curve y(x), computes the distance from it to the data points, and prints out the value of the loss function.

We can start twisting the knobs to find the minimum loss. For example, we might start with some initial setting and slightly nudge knob number one to the right. If the resultant curve changes and the value of the loss function slightly decreases, we know we're on the right track.

However, this random perturbation method is not very efficient. Is there a way we can be more intelligent about the knob adjustments?

The Concept of Differentiability

In the most general case, when the machine is a complete black box, nothing better than random perturbation is guaranteed to exist. However, a great deal of computations, including what's carried out under the hood of our curve fitter, have a special property called differentiability.

Differentiability allows us to compute the optimal knob setting much more efficiently. Ideally, we'd like to upgrade the machine so that it would have a tiny screen next to each knob. For any configuration, these screens should tell us which direction we need to nudge each knob to decrease the loss function and by how much.

This might sound like cheating - predicting the future and estimating the effect of the knob adjustment on the loss function without actually performing that adjustment. However, this idea is based on a simple mathematical foundation.

Understanding Derivatives

Let's consider a simpler case first, where we freeze five out of six knobs. The machine now has only one variable parameter, k1, that we can tweak, and the loss function is a simpler function of one variable.

We can visualize this function as a graph in a two-dimensional plane. Our goal is to find the value of k1 that corresponds to the minimum of the loss function. However, we don't have access to the true underlying shape of the function. All we can do is set the knob at a chosen position and query the machine for the value of the loss.

But what if we want to know more about the function, not just its value at each point? For example, whether at a given point the function is going up or down? This information would guide our adjustments because if we know the function is going down as we increase the input, turning the knob to the right is a safe bet.

To put this notion of "going up or down" on stronger mathematical ground, we introduce the concept of derivatives. The derivative of a function at a point is the slope of the line tangent to the graph at that point. It corresponds to the instantaneous rate of change or steepness of the function around that point.

The derivative of a function is itself a function that takes an arbitrary value of x and outputs the local steepness of y(x) at that point. This derivative function carries information about the steepness of the original function at every point.

Using Derivatives for Optimization

With this derivative information, we can efficiently find the optimal value of k1. We start at some random position, ask the machine for the value of the loss and the derivative of the loss function at that position, then take a tiny step in the direction opposite of the derivative. We repeat this procedure until we reach a point where the derivative is zero, which corresponds to the minimum where the tangent line is flat.

This process is easily carried out in higher dimensions. For example, if we're free to tweak two different knobs, k1 and k2, the loss becomes a function of two variables, which can be visualized as a surface. The function will have two partial derivatives, one for each variable.

Geometrically, you can imagine slicing the surface with planes parallel to the axes intersecting at the point of interest (k1, k2). The slope of the tangent line at each cross-section will give you the corresponding partial derivative of the loss at that point.

These partial derivatives are usually combined into a vector called the gradient vector. This vector points in the direction of steepest ascent, so if we want to minimize the function, we need to take steps in the direction opposite to this gradient.

This iterative procedure of nudging the parameters in the direction opposite of the gradient vector is called gradient descent. It's analogous to a ball rolling down a hill, with the partial derivatives telling you which direction is downhill.

The Backpropagation Algorithm

The main purpose of the backpropagation algorithm is to find the derivatives of arbitrarily complex functions. Here's how it works:

1. We start with a handful of simple functions whose derivatives are known from calculus. These are the building blocks.

2. We combine these building blocks using rules like the sum rule (the derivative of a sum of functions is the sum of their derivatives) and the product rule.

3. To complete the picture, we use the chain rule, which tells us how to compute the derivative of a combination of two functions when one of them is an input to another.

Using these rules, we can find the derivative of any arbitrarily complex function, as long as it can be decomposed into these building blocks.

The Forward and Backward Pass

In the context of our curve fitter, we use this process as follows:

1. We create a knob for each number the loss function can possibly depend on (parameters and data points).

2. We break down the loss calculation into a sequence of simple, easily differentiable operations. This forms a computational graph.

3. We perform a forward pass, computing the loss for a given configuration of parameters and data knobs.

4. We then perform a backward pass, unrolling the sequence of calculations in reverse order to find derivatives. We apply the chain rule sequentially to each node in the computational graph.

5. Once we have the gradients for each parameter, we can perform one iteration of gradient descent, slightly tweaking the knobs in the directions opposite to the gradient.

6. We repeat this process of forward pass, backward pass, and parameter adjustment until we reach the minimum loss.

This loop of forward pass, backward pass, nudge, repeat is the essence of training in every modern machine learning system.

Backpropagation in Modern Machine Learning

The same algorithm is used today in even the most complicated models. As long as the problem you're trying to solve with a given model architecture can be decomposed into individual operations that are differentiable, you can sequentially apply the chain rule many times to arrive at the optimal setting of the parameters.

For instance, a feedforward neural network is essentially a bunch of multiplications and summations with a few nonlinear activation functions sprinkled between the layers. Each of these atomic computations is differentiable, so you can construct the compute graph and run the backward pass on it to find how each parameter (like connection weights between neurons) influences the loss function.

Because neural networks, given enough neurons, can in theory approximate any function imaginable, we can create a large enough sequence of these building block mathematical machines to solve problems such as classifying images and even generating new text.

Conclusion

Backpropagation is an elegant and efficient solution for optimization problems in machine learning. By calculating derivatives, it tells us exactly which adjustments are necessary to minimize the loss function.

However, this raises interesting questions about biological learning. Does the brain also minimize some sort of loss function? Does it calculate derivatives, or could it be doing something totally different? These questions lead us into the fascinating world of synaptic plasticity and biological neural networks, which operate on principles quite different from their artificial counterparts.

Understanding backpropagation not only gives us insight into how modern AI systems learn, but also highlights the fundamental differences between artificial and biological intelligence. As we continue to advance in both fields, these insights will be crucial in developing more sophisticated AI systems and in understanding the complexities of the human brain.

Article created from: https://youtu.be/SmZmBKc7Lrs?feature=shared