The Multilayer Perceptron

A Multilayer Perceptron is a feedforward neural network composed of an input layer, one or more hidden layers, and an output layer, where every neuron in one layer connects to every neuron in the next — a structure called fully connected or dense. Each neuron computes a weighted sum of its inputs plus a bias, then passes that sum through a nonlinear activation function such as sigmoid, tanh, or ReLU. The word "multilayer" is the key departure from the single-layer Perceptron: by introducing at least one hidden layer between input and output, the network gains the ability to represent nonlinear functions. Formally, layer $\ell$ computes

where $\mathbf{a}^{(0)} = \mathbf{x}$ is the input, $W^{(\ell)}$ and $\mathbf{b}^{(\ell)}$ are the weight matrix and bias vector for layer $\ell$, and $\phi$ is an elementwise nonlinear activation. The final layer's output $\mathbf{a}^{(L)}$ is the network's prediction, often passed through a task-specific function such as softmax for classification. The nonlinearity $\phi$ is not optional decoration — it is the entire reason depth matters. If every $\phi$ were the identity function, the composition of layers would reduce algebraically to a single matrix multiplication, since a product of linear maps is itself linear. Concretely, if $\mathbf{a}^{(2)} = W^{(2)}(W^{(1)}\mathbf{x} + \mathbf{b}^{(1)}) + \mathbf{b}^{(2)}$, this equals $W'\mathbf{x} + \mathbf{b}'$ for $W' = W^{(2)}W^{(1)}$ and $\mathbf{b}' = W^{(2)}\mathbf{b}^{(1)} + \mathbf{b}^{(2)}$ — a network with no more power than a single perceptron layer, no matter how many layers you stack. The nonlinear activation between layers breaks this collapse and is what allows the network to represent curved, folded, non-convex decision boundaries.

Building and running an MLP means fixing an architecture (how many layers, how wide each is, which activation each uses) and then performing a forward pass: propagating an input vector through each layer in sequence, computing an affine transformation followed by a nonlinearity at every step.

Step 1 — Architecture specification. Choose the number of hidden layers $L-1$, the width $n_\ell$ (number of neurons) of each layer $\ell$, and an activation function $\phi_\ell$ per layer (commonly ReLU for hidden layers, and sigmoid/softmax for the output layer depending on the task).

Step 2 — Parameter initialization. For each layer $\ell = 1, \dots, L$, initialize a weight matrix $W^{(\ell)} \in \mathbb{R}^{n_\ell \times n_{\ell-1}}$ and bias vector $\mathbf{b}^{(\ell)} \in \mathbb{R}^{n_\ell}$, typically with small random values (e.g., scaled by fan-in) to break symmetry between neurons.

Step 3 — Forward propagation. Feed the input through each layer in order: compute the pre-activation $\mathbf{z}^{(\ell)}$, apply $\phi_\ell$ to get $\mathbf{a}^{(\ell)}$, and pass $\mathbf{a}^{(\ell)}$ as the input to the next layer. This full mechanism — the chain of affine-then-nonlinear steps and the bookkeeping needed to later compute gradients — is developed in detail as Forward Propagation.

Step 4 — Output interpretation. The final layer's activation is interpreted per the task: raw values for regression, a sigmoid for binary classification, a softmax for multiclass classification. ``` function MLP_FORWARD(x, layers):

# layers is a list of L layer records:

# layers[l].W -- weight matrix, shape (n_l, n_{l-1})

# layers[l].b -- bias vector, shape (n_l,)

# layers[l].phi -- activation function for layer l a = x # a^(0) = input, shape (n_0,) for l in 1 .. L: z = layers[l].W @ a + layers[l].b # affine transform a = layers[l].phi(z) # elementwise nonlinearity return a # a^(L) = network output function SIGMOID(z): return 1 / (1 + exp(-z)) # elementwise function TANH(z): return (exp(z) - exp(-z)) / (exp(z) + exp(-z)) function RELU(z): return max(0, z) # elementwise ``` Edge cases the pseudocode must respect: if a layer has zero hidden units the matrix product degenerates and the network cannot pass information (a genuine architecture bug, not a numerical corner case); if `phi` were linear (identity) at every layer, the loop above is mathematically equivalent to one matrix multiply, confirming the collapse argument above; batched inputs simply replace vectors with matrices ($X$ of shape (batch, features)) and the same per-layer formula applies row-wise.

Time complexity of a forward pass. For a layer mapping $n_{\ell-1}$ inputs to $n_\ell$ outputs, the matrix-vector product $W^{(\ell)}\mathbf{a}^{(\ell-1)}$ costs $O(n_\ell \cdot n_{\ell-1})$ scalar multiply-adds, and the activation costs $O(n_\ell)$ elementwise operations. Summed over $L$ layers, the total forward-pass cost is

which is exactly the total number of weight parameters in the network. For a batch of $m$ examples processed as a matrix, the cost multiplies by $m$: $O\!\left(m \sum_\ell n_\ell n_{\ell-1}\right)$, since each layer becomes a matrix-matrix product. This is tight — every weight must be touched at least once, so the bound is not just an upper estimate but essentially the exact operation count (up to small constant factors for the additions).

Space complexity. Storing the parameters requires $O\!\left(\sum_\ell n_\ell n_{\ell-1}\right)$ space, matching the time bound. During training (though not strictly required for a bare forward pass at inference time), every activation $\mathbf{a}^{(\ell)}$ must typically be cached for the backward pass, adding $O\!\left(\sum_\ell n_\ell\right)$ per example — asymptotically smaller than the parameter count in wide networks, but a real memory cost that scales with batch size and depth in practice (this is precisely what makes training deep networks memory-hungry, motivating techniques like gradient checkpointing developed elsewhere).

Correctness — why nonlinear depth adds expressive power. The central claim to justify is: a network with at least one hidden layer and a nonlinear activation can represent decision boundaries that no linear model can. The cleanest proof is the XOR construction. Consider inputs $x_1, x_2 \in \{0,1\}$ with target $y = x_1 \oplus x_2$. No single linear separator can achieve zero error, because the positive class points $(0,1),(1,0)$ and negative class points $(0,0),(1,1)$ cannot be separated by any single line — a short case analysis over all four points shows any line separating one diagonal misclassifies the other. But a two-neuron hidden layer with ReLU can compute:

Checking all four inputs: $(0,0) \to h_1=0, h_2=0 \to y=0$; $(1,0)\to h_1=1,h_2=0\to y=1$; $(0,1)\to h_1=1,h_2=0\to y=1$; $(1,1)\to h_1=2,h_2=1\to y=2-2=0$. This matches XOR exactly, and it works precisely because ReLU's nonlinear "kink" at zero lets $h_2$ activate only when $x_1+x_2>1$, creating a folded, piecewise-linear decision surface that a single linear layer cannot produce. This one construction is a full existence proof that hidden layers with nonlinearities strictly enlarge the hypothesis class beyond linear separators — the broader statement, that sufficiently wide one-hidden-layer networks can approximate any continuous function on a compact domain, is the subject of the Universal Approximation Theorem.

Tradeoffs. Depth and width buy expressive power but are not free: more parameters mean more data needed to avoid overfitting, more compute per forward and backward pass, and a harder, more nonconvex optimization landscape. Very deep plain MLPs (before architectural aids like residual connections and normalization existed) were historically hard to train due to vanishing or exploding gradients — an issue tied directly to the choice of activation function and initialization scheme.

Take a tiny concrete network: 2 inputs, one hidden layer of 2 ReLU units, one linear output unit — solving the XOR problem set up above, but now traced numerically for input $\mathbf{x} = (1, 0)$.

Parameters (matching the construction above):

The network outputs $\hat{y}=1$ for input $(1,0)$, matching $1 \oplus 0 = 1$. Running the same trace for $(1,1)$: $z_1 = 2$, $z_2 = 1$, so $a^{(1)} = (2,1)$, and $\hat{y} = 1\cdot2 - 2\cdot1 = 0$, matching $1\oplus1=0$. Every one of the four input pairs checks out (as shown algebraically above), confirming the forward pass mechanically reproduces the intended nonlinear function — something provably impossible for any single-layer linear model on this dataset.

The MLP's story is really two stories: the invention of a workable multilayer architecture, and the invention of a training algorithm (Forward Propagation paired with backpropagation) efficient enough to fit its weights. Early perceptron research promised much, but a rigorous 1969 analysis showed single-layer perceptrons could not represent XOR, and multilayer training remained computationally unclear for years, contributing to reduced funding for neural network research through the 1970s. The resurgence came once efficient gradient computation through many layers became practical in the mid-1980s, and it accelerated again decades later with GPU compute and large datasets.

MLPs are the computational core hiding inside nearly every modern deep learning system. The feedforward sublayer of every transformer block — the component that follows self-attention in models used for language and vision — is literally a small MLP applied independently to each token. Convolutional networks for image classification typically end with one or more fully connected MLP layers that map extracted features to class scores. Recommendation systems at large technology companies use MLPs (often called "deep and wide" networks) to combine sparse categorical embeddings into click-through-rate predictions. Tabular data problems in finance, healthcare, and operations research frequently use MLPs as strong, simple baselines before reaching for more specialized architectures. Any time an engineer needs a flexible, differentiable function approximator that maps fixed-size inputs to fixed-size outputs, the MLP is often the very first tool reached for, precisely because its forward computation is simple, its expressive power is provably nontrivial, and it composes cleanly with virtually any other architectural building block.

Ask the tutor: Can you show how backpropagation computes the gradients for the XOR network traced in this article?