Introduction

The preceding articles introduced support vector machines and softmax for linear classification, along with the hinge and cross-entropy losses used to optimize them. We also saw score function $f$, parameterized by weight $W$ and bias $b$, and gradient descent as a way to optimize the score and loss. Because calculating an analytic gradient over every sample is computationally expensive, we introduced stochastic gradient descent and mini-batch gradient descent, which reduces update noise while remaining efficient.

This article explains how to optimize parameters efficiently in multilayer networks, beginning with a single perceptron. Along the way, it traces a central episode in the early history, decline, and revival of artificial intelligence.

Perceptron

The idea of an artificial neural network first appeared in the 1943 paper A Logical Calculus of the Ideas Immanent in Nervous Activity. McCulloch and Pitts described the human nervous system as a network of connected logical switches. Their work did not yet produce a practical learning algorithm. A more applied proposal arrived with Frank Rosenblatt's 1958 perceptron, which helped open the first era of AI enthusiasm.

Rosenblatt's perceptron was a feed-forward neural network for linear classification. It multiplied inputs by weights, applied an activation function, and returned $1$ or $-1$ according to whether the result crossed a threshold.

Modern deep learning differs in detail, but its fundamental structure remains a collection of these functions arranged into many nodes and layers. Like deep learning today, the perceptron attracted enormous academic and media attention, along with predictions that AI would soon replace much of the world.

Enthusiasm declined sharply after Marvin Minsky and Seymour Papert mathematically analyzed its limits in the 1969 book Perceptrons.

They pointed out that a single linear perceptron cannot implement even XOR. Failure on such a basic logical function implied that it could not solve many ordinary nonlinear problems. Minsky noted that a multilayer perceptron might represent XOR, but no effective method was then available to train all of its parameters.

Multilayer Perceptron

Interest in neural networks faded, but some researchers continued. The 1986 book Parallel Distributed Processing popularized multilayer perceptrons with hidden layers and the backpropagation algorithm. A single perceptron is restricted to linear classification; a multilayer perceptron (MLP) adds hidden layers that can compose multiple decision boundaries and represent functions such as XOR.

More layers also mean many more weights and biases, making their optimization difficult. Backpropagation solves this by sending an input forward through the network, comparing the prediction with ground truth, and propagating the resulting error backward to update every parameter.

Backpropagation

Let us make that concept concrete. For a single-layer linear classifier, score function $f$ contains weights and biases; by folding the bias into an augmented weight and input, we can write it using only $W$:

$$\begin{aligned} \hat{y} =& f(W;~X) = X \cdot W \newline \delta =& \rho(\hat{y},~y). \end{aligned}$$

Loss metric $\rho$ compares prediction $\hat{y}$ with ground truth $y$ and produces error $\delta$. The error tells us in which direction the output must move. Because the prediction depends on inputs $W$ and $X$, derivatives tell us how those inputs affect the error. For the parameter $W$, we need

$$\frac{\partial \delta}{\partial W}.$$

This derivative is only the local slope of the loss surface; it does not reveal a global minimum directly. Gradient descent still takes small steps along the negative gradient.

By the chain rule,

$$\frac{\partial \delta}{\partial W} = \frac{\partial \delta}{\partial \hat{y}} \frac{\partial \hat{y}}{\partial W}.$$

Now suppose there are many layers, with activation function $\sigma$:

$$\begin{aligned} \hat{y} = f(W_1,~W_2,~\cdots,~W_n;~X) =& \sigma( \cdots \sigma(\sigma(X \cdot W_1) \cdot W_2) \cdots W_n) \newline \delta =& \rho(\hat{y},~y). \end{aligned}$$

Let $y_k$ denote the activation after layer $k$, so $\hat{y}=y_n$. The last layer's weight gradient is a product of local derivatives:

$$\frac{\partial \delta}{\partial W_n} = \frac{\partial \delta}{\partial y_n} \frac{\partial y_n}{\partial W_n}.$$

For the preceding layer,

$$\frac{\partial \delta}{\partial W_{n-1}} = \frac{\partial \delta}{\partial y_n} \frac{\partial y_n}{\partial y_{n-1}} \frac{\partial y_{n-1}}{\partial W_{n-1}}.$$

The pattern continues: values already calculated in the forward pass supply local derivatives, and backward propagation multiplies them according to the chain rule.

Consider the simple computational graph below.

Green values are forward inputs and intermediate results; red values are gradients. Let $q=x+y$ and $f=qz=(x+y)z$. The gradient arriving at output $f$ is $1$. Because $\partial f/\partial q=z=-4$, the gradient at $q$ is $-4$. Addition has local derivative one for both inputs, so $\partial f/\partial x=-4$ and $\partial f/\partial y=-4$. Finally, $\partial f/\partial z=q=x+y=3$.

The example illustrates two principles:

• Values calculated during the forward pass are reused to calculate gradients for inputs during the backward pass.
• Starting from the final output gradient, each earlier gradient is obtained by multiplying local derivatives according to the chain rule.

Interpreting Backpropagation

Backpropagation is a local process. Every gate in a computational graph receives inputs and calculates two kinds of result: its forward output and local derivatives of that output with respect to its inputs. These calculations depend only on the gate's own operation, regardless of the surrounding graph.

After one forward pass, backpropagation can therefore compute the derivative of the final output with respect to every parameter. The chain rule multiplies the gradient arriving from downstream by each local input derivative. Multiplication along all backward paths is what allows otherwise independent perceptrons in a complicated network to learn together.

Return to the graph:

The addition gate receives $-2$ and $5$ and outputs $q=3$. Its local derivatives with respect to both inputs are $+1$. The complete graph outputs $-12$, and the backward gradient arriving at $q$ is $-4$.

If we wanted the final graph output to increase, a negative gradient at $q$ says that $q$ itself should decrease. The gate multiplies this arriving gradient by its local derivative for every input, giving $1\times(-4)=-4$ for both $x$ and $y$. Decreasing either input decreases $q$; because $z$ is negative, that increases final output $f=qz$.

In general, multiplying a gate's incoming gradient by its local input gradients tells us how far and in which direction each input should change to move toward the desired output. Backpropagation lets all gates communicate, with chain-rule derivatives as the message.

Example: A Two-Dimensional Neuron

$$f(w,~x) = \frac{1}{1+e^{-(w_0x_0 + w_1x_1 + w_2)}}.$$

This is one neuron with a two-dimensional input and sigmoid activation. Its computational graph uses the following elementary derivatives:

$$\begin{aligned} f(x) =& \frac{1}{x} &&\rightarrow \frac{df}{dx} = -\frac{1}{x^2} \newline f(x) =& x + c &&\rightarrow \frac{df}{dx} = 1 \newline f(x) =& e^x &&\rightarrow \frac{df}{dx} = e^x \newline f(x) =& ax &&\rightarrow \frac{df}{dx} = a. \end{aligned}$$

The figure records forward values in green and gradients in red. Start at the output with gradient $1.00$. The reciprocal gate has local derivative $-1/x^2$. At input $1.37$, the backward value is approximately

$$1\times\frac{-1}{1.37^2}=-0.53.$$

Adding one has derivative one, so $-0.53$ passes through unchanged. The exponential gate's local derivative equals its output, $0.37$, producing $-0.53\times0.37=-0.20$. Multiplication by $-1$ flips the sign to $0.20$.

The path now branches through additions. Addition passes the same $0.20$ to both inputs. At multiplication gates, each input's local derivative is the other input: if $f(x,y)=xy$, then $\partial f/\partial x=y$ and $\partial f/\partial y=x$. Thus the weight gradient for $w_0$ is $0.20x_0=-0.20$, while the input gradient for $x_0$ is $0.20w_0\simeq0.39$. Small numerical differences in the diagram come from rounding. The same calculation gives gradients $-0.39$ and $-0.59$ for $w_1$ and $x_1$.

Sigmoid Gradient

The graph above decomposes sigmoid into elementary operations, but its analytic derivative is simpler:

$$\begin{aligned} \sigma (x) =& \frac{1}{1+e^{-x}} \newline \frac{d \sigma(x)}{dx} =& \frac{e^{-x}}{(1+e^{-x})^2}. \end{aligned}$$

Rearranging,

$$\frac{d \sigma(x)}{dx} = \left( \frac{1+e^{-x}-1}{1+e^{-x}} \right) \left( \frac{1}{1+e^{-x}} \right) = (1-\sigma(x))\sigma(x).$$

In the example, the preactivation $w_0x_0+w_1x_1+w_2$ gives $\sigma(x)=0.73$, so the derivative is immediately

$$\sigma(x)(1-\sigma(x))=0.73(1-0.73)=0.1971.$$

Conclusion

We traced how multilayer networks overcame the linear limits of a single perceptron, and how backpropagation made those networks trainable. Local gradients connect every component of a network through the chain rule. This was the mechanism that allowed neural networks to move beyond the problems a perceptron could not solve and begin the path toward modern deep learning.

Appendix

Question: Draw a computational graph for the following equation and calculate its gradients in Python.

$$f(x,~y) = \frac{x+\sigma (y)}{\sigma (x) + (x+y)^2}.$$

Answer

x = 3 # example values
y = -4

# forward pass
sigy = 1.0 / (1 + math.exp(-y)) # sigmoid in numerator   #(1)
num = x + sigy # numerator                               #(2)
sigx = 1.0 / (1 + math.exp(-x)) # sigmoid in denominator #(3)
xpy = x + y                                              #(4)
xpysqr = xpy**2                                          #(5)
den = sigx + xpysqr # denominator                        #(6)
invden = 1.0 / den                                       #(7)
f = num * invden # done!                                 #(8)

# backprop f = num * invden
dnum = invden # gradient on numerator                    #(8)
dinvden = num                                            #(8)
# backprop invden = 1.0 / den
dden = (-1.0 / (den**2)) * dinvden                       #(7)
# backprop den = sigx + xpysqr
dsigx = (1) * dden                                       #(6)
dxpysqr = (1) * dden                                     #(6)
# backprop xpysqr = xpy**2
dxpy = (2 * xpy) * dxpysqr                               #(5)
# backprop xpy = x + y
dx = (1) * dxpy                                          #(4)
dy = (1) * dxpy                                          #(4)
# backprop sigx = 1.0 / (1 + math.exp(-x))
dx += ((1 - sigx) * sigx) * dsigx                        #(3)
# backprop num = x + sigy
dx += (1) * dnum                                         #(2)
dsigy = (1) * dnum                                       #(2)
# backprop sigy = 1.0 / (1 + math.exp(-y))
dy += ((1 - sigy) * sigy) * dsigy                        #(1)

Answer Walkthrough

Matching the code's values and gradients to the diagram gives the following result.

Red values were computed in the forward pass; green values are backward gradients. The final gate multiplies num and invden. Since the output gradient is one, each input receives the other input as its gradient:

dnum = invden
dinvden = num

The reciprocal gate multiplies by local derivative $-1/x^2$ at input den:

dden = (-1.0 / (den**2)) * dinvden

Because den adds sigx and xpysqr, its gradient passes unchanged to both:

dsigx = (1) * dden
dxpysqr = (1) * dden

The square gate uses derivative $2x$:

dxpy = (2 * xpy) * dxpysqr

The addition xpy = x + y passes that gradient to both variables:

dx = (1) * dxpy
dy = (1) * dxpy

The sigmoid derivative derived above adds another contribution to dx:

dx += ((1 - sigx) * sigx) * dsigx

The numerator addition likewise passes dnum to x and sigy. Notice that dx already contains a contribution from the denominator path, so gradients from the two paths are accumulated:

dx += (1) * dnum
dsigy = (1) * dnum

Finally, the second sigmoid contributes to dy:

dy += ((1 - sigy) * sigy) * dsigy