Backpropagation algorithm

The Data: We are given $T$ test points $X^{(1)},\dots ,X^{(T)}\in {\mathbb{R}}^n$, together with measurements $f(X^{(t)})\in \mathbb{R}$, where $f$ is some unknown function.

The Objective: Our goal is to approximate $f$ at the given test points by a function $f_w$ computed by a feed-forward neural network.

The Cost Function: Approximation is achieved by minimizing the Sum of Squared Errors (SSE) across all $T$ test points. (Unlike LMS, which minimized instantaneous error, this is a batch approach).

Without loss of generality, we assume that:

• there are $n$ input neurons,
• and two hidden layers, each containing $n$ neurons.

Let $n_k^{(1)}$ denote the $k$-th neuron in the first hidden layer.

Let $w_{jk}^{(1)}$ be the weight connecting neuron $k$ in layer 1 with neuron $j$ in layer 2.

As activation function, we take for all neurons $\phi (t)=\frac{1}{1+e^{-t}}$

The derivative of $\phi (t)$ can be expressed in terms of $\phi$ itself. ${\phi }^{\prime }(t)=\phi (t)\cdot (1-\phi (t))$

The flow of error signals backward through a Feed-Forward Neural Network.

• $e(t)$: The raw instantaneous error (Target $-$ Output) at timestep $t$.

• $y_k^{(L)}$: The actual numerical output of neuron $k$ in layer $L$ during the forward pass.

• $y_k^{(L)}(1-y_k^{(L)})$: The derivative of the Sigmoid activation function

• ${\delta }_k^{(L)}$ (Local Gradient): The exact amount of “error responsibility” assigned to neuron $k$ in layer $L$.

The Sum of Squared Errors : $\mathcal{E}=\frac{1}{2}(Target-Output{)}^2$

The Blame is the derivative of the Total Error with respect to a specific neuron’s raw input ($v$): $\delta =\frac{\partial \mathcal{E}}{\partial v}$

The blame ($\delta$) for the final output neuron is :

**${\delta }_1^{(3)}$ = (The Raw Error) $\times$ (The Sigmoid Derivative)

$\delta =(Target-Output)\times [y(1-y)]$

• Single Connection (Layer 2): If a hidden neuron $j$ connects to only one output neuron, its local gradient is the subsequent $\delta$ multiplied by the connecting weight, passed through its own derivative: ${\delta }_j^{(2)}=\left({\delta }_1^{(3)}\cdot w_{1j}^{(2)}\right)\cdot \left[y_j^{(2)}(1-y_j^{(2)})\right]$ The error blame for Neuron $j$ in Layer 2 is = (The delta from Neuron 1 in the NEXT layer) * (The weight connecting them) * (The derivative of the sigmoid in Neuron $j$).

• Multiple Connections (The Summation at Layer 1): If a hidden neuron $k$ connects to multiple neurons in the next layer, we must sum the backward-flowing error signals from all connected neurons (denoted by the $\Sigma$ node in the diagram).

  ${\delta }_k^{(1)}=\left({\sum }_i{\delta }_i^{(2)}\cdot w_{ik}^{(1)}\right)\cdot \left[y_k^{(1)}(1-y_k^{(1)})\right]$

---

The problem variables are the weights $w=(w_0,w_1,\dots ,w_n)\in {\mathbb{R}}^{2n^2+n}$.

We disregard biases.

Because the network utilizes the Sigmoid activation function $\phi (t)=\frac{1}{1+e^{-t}}$, the final output of the network $N_w$ is strictly bounded: $N_w\in (0,1)$.

• If the true target measurements of the dataset fall outside the $(0,1)$ range, the network cannot mathematically reach them. Therefore, a necessary preprocessing step is to normalize the dataset so all target values fall within the reachable bounds of the activation function.

Let $y_k^{(i)}$ denote the output signal of neuron $n_k^{(i)}$. Then neuron $n_j^{(i+1)}$ receives as input

$v_j^{(i+1)}={\sum }_{k=1}^n{w}_{jk}^{(i)}{y}_k^{(i)}$,

and its output is given by

$y_j^{(i+1)}=\phi (v_j^{(i+1)})$.

The objective function is

$E(W)=\frac{1}{2}{\sum }_{t=1}^T(N_w(X(t))-f(X(t)){)}^2$ (sum of squared errors)

The ultimate optimal weight vector $w^{\ast }$ lives in the dimension ${\mathbb{R}}^{2n^2+n}$.

• Input layer ($n$) to Hidden 1 ($n$) = $n\times n=n^2$ weights.
• Hidden 1 ($n$) to Hidden 2 ($n$) = $n\times n=n^2$ weights.
• Hidden 2 ($n$) to Output ($1$) = $n\times 1=n$ weights.
• For a network with $n$ inputs, two hidden layers of $n$ neurons, and $1$ output, the total number of optimized parameters (ignoring biases) is $2n^2+n$

Goal: find an unconstrained minimizer $w^{\ast }\in {\mathbb{R}}^{2n^2+n}$ of $E(W)$ such that $E(w^{\ast })\le E(w)$ for all $w$, to find the unconstrained minimizer $w^{\ast }$ that minimizes the total Sum of Squared Errors across all $T$ test points.

The objective function is a:

high-dimensional, smooth, non-convex empirical risk functional defined over a nonlinear parameterization of a feedforward neural network

Remark :

• New test points can be added without changing the structure of the model, since the objective is defined as a sum over samples.
• The structure of the network $N_w$ determines the structure of the objective function $E(w)$ and therefore has a fundamental impact on how well different target functions $f$ can be approximated. This is a central topic in approximation theory.
• In general, we cannot expect numerical optimization methods such as steepest (gradient) descent to converge to a global minimum of the objective. Gradient descent is a local method: it follows the negative gradient toward stationary points, but in non-convex landscapes there is no general guarantee of reaching the global minimum.
• For the application of steepest descent methods, the activation function $\phi$ must be differentiable, since gradient-based optimization requires the existence of $\nabla E(w)$, which is computed via the chain rule through $\phi$. If the math has a sharp corner (like a step function), the derivative is undefined, the chain rule breaks, and Backpropagation completely fails.

---

Backpropagation (high-level view)

Choose an initial parameter vector $w_0$.

In Step $k$

Assume $w_k$ is already computed. Then compute $w_{k+1}$ via:

$$w_{k+1}=w_k-\eta \nabla E(w_k),\eta >0$$

where:

• $\eta$ is the learning rate
• $\nabla E(w_k)$ is the gradient of the loss at $w_k$, the steepest descent direction of $E$ at $w_k$
• The update moves parameters in the direction of maximal local decrease of the objective

Backpropagation is the procedure used to compute $\nabla E(w_k)$ efficiently using the chain rule through the network, while the update above is the actual optimization step (gradient descent).

The main breakthrough of backpropagation algo is that the computation of ${\nabla }_{w}E(w)$ aligns extremely well with the layered structure of the neural network.

• This structural compatibility allows the gradient to be computed efficiently by reusing intermediate quantities computed during the forward pass.

To see this, one must carry out a sequence of explicit (and somewhat tedious) derivative computations, applying the chain rule systematically through the layers of the network.

Backpropagation is efficient because the chain rule factorization matches the computational graph of the network.

• The network is a compositional map $X\to layer1\to layer2\to ..\to output$
• gradients propagate naturally in reverse order of this composition So instead of recomputing derivatives repeatedly, backprop:
• stores intermediate activations
• reuses them during gradient computation

1. Layer 3 (The Output): Looks at the final error, calculates its own derivative, and gets a “blame score” ($\delta$). It hands that number to the wires pointing backward.
2. Layer 2 (Hidden): Layer 2 doesn’t even look at the final error. It just catches the $\delta$ number from Layer 3, multiplies it by its own derivative, and hands the new number backward.
3. Layer 1 (Input): Catches the number from Layer 2, multiplies it by its own derivative, and uses it to update its weights.

---

The earlier a weight appears in the network, the more indirect and complex its influence on the objective function (E(w)). This is because its effect propagates through multiple subsequent layers via repeated nonlinear transformations.

For this reason, backpropagation proceeds from the output layer backward toward the input layer.

We therefore start by computing partial derivatives with respect to the weights in the last layer, i.e.

$$\frac{\partial E}{\partial w_{jk}^{(L-1)}}$$

and then propagate these derivatives backward through the network using the chain rule.

The loss function is:

$$E(w)=\frac{1}{2}\sum _{t=1}^T(f(X(t))-y_1^{(3)}(t){)}^2$$

where the output neuron is given by:

$$y_1^{(3)}(t)=\phi \left(\sum _{k=1}^n{w}_{1k}^{(2)}.y_k^{(2)}(t)\right)$$

Substituting this into the objective gives:

$$E(w)=\frac{1}{2}\sum _{t=1}^T{\left(f(X(t))-\phi \left(\sum _{k=1}^n{w}_{1k}^{(2)}.y_k^{(2)}(t)\right)\right)}^2$$

$y_k^{(2)}$ (the outputs of the previous layer) have already been calculated during the forward pass, they are treated as constants that are independent of the current weight $w_{1k}^{(2)}$ being optimized.

The partial derivative of $\mathcal{E}$ with respect to a single, specific weight $w_{1j}^{(2)}$

$\frac{\partial \mathcal{E}}{\partial w_{1k}^{(2)}}={\sum }_{t=1}^T\left(\underset{\text{Part 1}}{\underbrace{\frac{\partial \mathcal{E}}{\partial y_1^{(3)}}}}\times \underset{\text{Part 2}}{\underbrace{\frac{\partial y_1^{(3)}}{\partial v_1^{(3)}}}}\times \underset{\text{Part 3}}{\underbrace{\frac{\partial v_1^{(3)}}{\partial w_{1k}^{(2)}}}}\right)$ $\mathcal{E}=\frac{1}{2}(f(x)-y_1^{(3)}{)}^2$

$\frac{\partial \mathcal{E}}{\partial y_1^{(3)}}=-1\cdot (\mathbf{f}(\mathbf{x})-{\mathbf{y}}_1^{(3)})$

$y_1^{(3)}=\phi (v_1^{(3)})$

$\frac{\partial y_1^{(3)}}{\partial v_1^{(3)}}={\mathbf{y}}_1^{(3)}\cdot (1-{\mathbf{y}}_1^{(3)})$

$v_1^{(3)}=w_{11}^{(2)}{y}_1^{(2)}+w_{12}^{(2)}{y}_2^{(2)}+\cdots +w_{1k}^{(2)}{y}_k^{(2)}+\cdots +w_{1n}^{(2)}{y}_n^{(2)}$

We are only taking the derivative with respect to one specific weight: $w_{1k}^{(2)}$, this means every other weight in that long addition problem is treated as a constant. $\frac{\partial v_1^{(3)}}{\partial w_{1k}^{(2)}}={\mathbf{y}}_{\mathbf{k}}^{(2)}$

$\frac{\partial \mathcal{E}}{\partial w_{1k}^{(2)}}={\sum }_{t=1}^T\underset{\text{Part 1}}{\underbrace{-1\cdot (f(x(t))-y_1^{(3)}(t))}}\cdot \underset{\text{Part 2}}{\underbrace{y_1^{(3)}(t)(1-y_1^{(3)}(t))}}\cdot \underset{\text{Part 3}}{\underbrace{y_k^{(2)}(t)}}$

Substituting this gradient into the standard Steepest Descent formula ($w_{new}=w_{old}-\eta \nabla \mathcal{E}$)

We mathematically group the raw error and the sigmoid derivative into a single term called the local gradient or $\delta$ (Delta):

${\delta }_1^{(3)}(t)=e_1^{(3)}(t)\cdot y_1^{(3)}(t)\cdot (1-y_1^{(3)}(t))$

$w_{1j}^{(2),new}=w_{1j}^{(2)}-\eta \cdot \frac{\partial \mathcal{E}}{\partial w_{1j}^{(2)}}$

$w_{1j}^{(2),new}=w_{1j}^{(2)}-\eta \cdot \left[{\sum }_{t=1}^T-1\cdot (f(x(t))-y_1^{(3)}(t))\cdot y_1^{(3)}(t)(1-y_1^{(3)}(t))\cdot y_j^{(2)}(t)\right]$

$w_{1j}^{(2),new}=w_{1j}^{(2)}+\eta {\sum }_{t=1}^T\left[\right(f(x(t))-y_1^{(3)}(t))\cdot y_1^{(3)}(t)(1-y_1^{(3)}(t))\cdot y_j^{(2)}(t)]$

$w_{1j}^{(2),new}=w_{1j}^{(2)}+\eta {\sum }_{t=1}^T({\delta }_1^{(3)}(t)\cdot y_j^{(2)}(t))$

Therefore updating a weight requires almost no new computation

• The error of the output (already calculated).
• The output of the Sigmoid itself (already calculated).
• The signal coming from the previous layer (already calculated).

Calculating the gradient for the Hidden Layer ($w^{(1)}$) : For a hidden layer, there is no “Target.” The data set doesn’t tell Neuron $j$ in Layer 2 what its output should have been.

For Layer 2: **${\delta }_j^{(2)}=({\delta }_1^{(3)}\cdot w_{1j}^{(2)})\cdot [y_j^{(2)}(1-y_j^{(2)})]$ $w_{jk}^{(1),new}=w_{jk}^{(1)}+\eta {\sum }_{t=1}^T({\delta }_j^{(2)}(t)\cdot y_k^{(1)}(t))$

For Layer 1 : ${\delta }_k^{(1)}=\left({\sum }_{\mathbf{j}=1}^{\mathbf{n}}{\delta }_j^{(2)}\cdot w_{jk}^{(1)}\right)\cdot [y_k^{(1)}(1-y_k^{(1)})]$ $w_{ki}^{(0),new}=w_{ki}^{(0)}+\eta {\sum }_{t=1}^T({\delta }_k^{(1)}(t)\cdot x_i(t))$

• Layer 3: Look at the target, calculate ${\delta }_1^{(3)}$. Update Layer 3’s weights.
• Layer 2: Catch the $\delta$ from Layer 3. Calculate ${\delta }_j^{(2)}$. Update Layer 2’s weights.
• Layer 1: Catch all the $\delta$‘s from Layer 2. Calculate ${\delta }_k^{(1)}$. Update Layer 1’s weights.