Expressiveness of Neural Networks
Learning Objectives
After reading this page, you should be able to:
- Design a two-layer neural network that computes XOR or a similar function.
- Explain why nonlinear activation functions are crucial for the expressive power of neural networks.
- Design a two-layer feedforward neural network to classify any data set with binary features and target exactly.
1 Introduction
On the Limitations of Linear Models page, we saw that no linear model can represent the XOR function. We begin this page by hand-designing a two-layer network that models XOR perfectly. This example shows that hidden layers make neural networks more expressive than linear models.
We then consider the expressiveness of neural networks more generally. It turns out that a multi-layer perceptron (MLP) with a single hidden layer is a universal approximator. However, additional depth in an MLP is still necessary for compactness.
2 Computing XOR with a Neural Network
Previously, on the Limitations of Linear Models page, we showed that the XOR problem is not linearly separable, so a one-layer neural network cannot classify it perfectly. It turns out that a two-layer neural network with just two hidden units can. In this section, we will derive two such networks and learn a general approach for hand-designing the weights of a neural network to model a logical function.
2.1 Worked Example: XOR with a Two-Layer Neural Network
Recall the XOR data from Limitations of Linear Models. Table 1 lists the XOR truth table over inputs \(x_1, x_2 \in \{0, 1\}\), and Figure 1 plots the same four points in the \((x_1, x_2)\)-plane. In logic, XOR is typically written with the symbol \(\oplus\). We use this symbol to write the target as
\[ \begin{aligned} & t = x_1 \oplus x_2. \end{aligned} \]
| \(x_1\) | \(x_2\) | \(t = x_1 \oplus x_2\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR points in input space
Next, we will design a two-layer neural network that classifies the XOR data points perfectly. Based on the dataset, our network has two binary inputs and one binary output. Completing the network design requires a few more decisions. First, we need to determine the number of hidden units. It turns out that two hidden units are sufficient to classify XOR. Second, we need to determine the activation function for the hidden and output layers. For simplicity, we will use the threshold activation function introduced earlier,
\[ \begin{aligned} & f(z) = \begin{cases} 1 & \text{if } z \geq 0 \\ 0 & \text{if } z < 0. \end{cases} \end{aligned} \]
Figure 2 shows the resulting network structure. What remains is to hand-pick the weights and biases for each hidden and output unit so that the network’s predictions match the targets for every input.
Structure of a two-layer neural network for XOR
How can we choose these weights and biases? The key idea is to think of the hidden units as computing useful features that would make the problem linearly separable. That is, we first determine the meanings of the features computed by the hidden units and then figure out how to compute them.
To determine the meanings of the features, we will start by decomposing XOR into simpler Boolean operations (Step 1). We hope that each of these simpler Boolean functions can be computed by a single hidden unit (Step 2). We can then select the weights and biases for each unit (Step 3), and assemble them to form the network (Step 4).
Step 1: Decompose XOR into Simpler Boolean Functions
To start, we will decompose XOR into two simpler Boolean functions. Then, we will design each hidden unit to compute one of these functions and combine the hidden unit outputs to produce the prediction.
In logic, there are two common ways to decompose XOR. First, XOR is true when exactly one input is true. This happens in two cases. Either \(x_1\) is true and \(x_2\) is false, or \(x_1\) is false and \(x_2\) is true. We can write this formally as
\[ \begin{aligned} & x_1 \oplus x_2 = (x_1 \wedge \neg x_2) \;\vee\; (\neg x_1 \wedge x_2) \end{aligned} \tag{Solution 1} \]
Second, XOR is true when at least one input is true, but not both. That is, we start with the case where \(x_1\) or \(x_2\) is true and exclude the case where both are true. We can write this formally as
\[ \begin{aligned} & x_1 \oplus x_2 = (x_1 \vee x_2) \;\wedge\; \neg(x_1 \wedge x_2) \end{aligned} \tag{Solution 2} \]
Both decompositions provide intermediate features that could be represented with hidden units. We will design a network based on Solution 1 in detail. Solution 2 is left as an exercise at the end of this example.
Step 2: Assign Sub-Problems to the Network’s Units
The decomposition provided by Solution 1 maps directly onto the two-hidden-unit architecture. Hidden unit \(h_1\) will compute the first term, hidden unit \(h_2\) will compute the second term, and output unit \(y\) will compute the OR of the two hidden units.
\[ \begin{aligned} h_1 & = x_1 \wedge \neg x_2 \\[0.5em] h_2 & = \neg x_1 \wedge x_2 \\[0.5em] y & = h_1 \vee h_2 \end{aligned} \]
Each unit now computes a simple Boolean function whose positive and negative examples are linearly separable.
Solution 1 Boolean sub-problems
Step 3: Select Weights for Each Unit
Now that we have broken down XOR into sub-problems, we can tackle each sub-problem in turn. In this section, we will choose the weights and the bias for hidden unit \(h_1\) such that it is equivalent to the following Boolean operation.
\[ \begin{aligned} & h_1 = x_1 \wedge \neg x_2 \end{aligned} \]
We are going to design the hidden unit using a geometric approach in three steps. First, we will choose a decision boundary that separates the data perfectly into the two classes. Second, we will derive an equation representing the line. Finally, we will determine the signs of the weights by determining which half-space corresponds to the positive examples. Let’s carry out these steps to determine the hidden unit \(h_1\).
First, we need to pick a desired decision boundary. Looking at the four data points, there is a wide gap between the three negative examples and the one positive example. Similar to our approach in Deriving a Decision Boundary on the Logistic Regression page, we have the freedom to choose a line that leads to a simpler mathematical derivation. A natural choice is the 45-degree line halfway through the gap.
Decision boundary for \(h_1\)
Next, write an equation for the line. Since the line is at 45 degrees and passes through the point \((0.5, 0)\), it can be represented by the equation below.
\[ \begin{aligned} & x_2 = x_1 - 0.5 \end{aligned} \]
It has a slope of \(1\) and an intercept of \(-0.5\). Let’s move all the quantities to the left side and get the following equation.
\[ \begin{aligned} & - x_1 + x_2 + 0.5 = 0. \end{aligned} \]
Finally, we will determine the signs of the weights and the bias. The line splits the input space into two half-spaces, and the threshold unit outputs \(1\) on the side where the expression is non-negative. We need the positive example to lie on that side. Plugging in the positive example \((x_1, x_2) = (1, 0)\) gives
\[ \begin{aligned} & - 1 + 0 + 0.5 = - 0.5 < 0. \end{aligned} \]
The expression is negative at the positive example, so a unit with these weights would output \(0\) for it. Multiplying every term by \(-1\) describes the same line but flips the sign of the expression on each side. Therefore, the hidden unit \(h_1\) is given by the following expression
\[ \begin{aligned} & h_1 = f(x_1 - x_2 - 0.5), \end{aligned} \]
which corresponds to the weights and the bias below. Following our MLP notation, \(h_1\) is unit 1 in layer 1.
\[ \begin{aligned} & W^{(1)}_{1,1} = 1, \qquad W^{(1)}_{1,2} = -1, \qquad b^{(1)}_1 = -0.5. \end{aligned} \]
This three-step procedure can be used to select the weights for any Boolean function whose outputs are linearly separable. That is, choose a convenient separating line, write its equation with zero on the right-hand side, and check the sign at a positive example. Apply this procedure to design \(h_2\) and \(y\) in the two questions below.
Question: Use the three-step procedure to design the second hidden unit \(h_2 = \neg x_1 \wedge x_2\). Give its weights \(W^{(1)}_{2,1}\) and \(W^{(1)}_{2,2}\) and its bias \(b^{(1)}_2\).
Answer:
The only positive example is \((0, 1)\), and the other three points are negative. A natural separating line is the one halfway through the gap, with slope \(1\) and intercept \(0.5\).
\[ \begin{aligned} & x_2 = x_1 + 0.5 \end{aligned} \]
Moving all the quantities to the left side gives
\[ \begin{aligned} & -x_1 + x_2 - 0.5 = 0. \end{aligned} \]
Plugging in the positive example \((x_1, x_2) = (0, 1)\) gives
\[ \begin{aligned} & -0 + 1 - 0.5 = 0.5 \geq 0. \end{aligned} \]
The expression is already non-negative at the positive example, so we keep the signs. Therefore,
\[ \begin{aligned} & h_2 = f(-x_1 + x_2 - 0.5). \end{aligned} \]
The weights and the bias are
\[ \begin{aligned} & W^{(1)}_{2,1} = -1, \qquad W^{(1)}_{2,2} = 1, \qquad b^{(1)}_2 = -0.5. \end{aligned} \]
Question: Use the three-step procedure to design the output unit \(y = h_1 \vee h_2\). Its inputs are \(h_1\) and \(h_2\). Give its weights \(W^{(2)}_{1,1}\) and \(W^{(2)}_{1,2}\) and its bias \(b^{(2)}\).
Answer:
In the \((h_1, h_2)\)-plane, the only negative example is \((0, 0)\), and the other three points are positive. A natural separating line is the one halfway through the gap, with slope \(-1\) and intercept \(0.5\).
\[ \begin{aligned} & h_2 = -h_1 + 0.5 \end{aligned} \]
Moving all the quantities to the left side gives
\[ \begin{aligned} & h_1 + h_2 - 0.5 = 0. \end{aligned} \]
Plugging in the positive example \((h_1, h_2) = (1, 0)\) gives
\[ \begin{aligned} & 1 + 0 - 0.5 = 0.5 \geq 0. \end{aligned} \]
The expression is already non-negative at the positive example, so we keep the signs. Therefore,
\[ \begin{aligned} & y = f(h_1 + h_2 - 0.5). \end{aligned} \]
The weights and the bias are
\[ \begin{aligned} & W^{(2)}_{1,1} = 1, \qquad W^{(2)}_{1,2} = 1, \qquad b^{(2)} = -0.5. \end{aligned} \]
Step 4: Assemble the Full Network
Applying Step 3 to the three sub-problems from Step 2 yields the following neurons.
\[ \begin{aligned} h_1 = x_1 \wedge \neg x_2 & = f\!\left(\, x_1 - x_2 - 0.5 \,\right) \\[0.5em] h_2 = \neg x_1 \wedge x_2 & = f\!\left(-x_1 + x_2 - 0.5 \,\right) \\[0.5em] y = h_1 \vee h_2 & = f\!\left(\, h_1 + h_2 - 0.5 \,\right) \end{aligned} \]
Figure 5 assembles the three neurons into the two-layer neural network, and Figure 6 shows the resulting decision regions in the input plane.
Solution 1 weighted XOR network
Solution 1 XOR decision regions
These parameters can also be packaged as a weight matrix and bias vector for each layer. Layer 1, which maps the input to the hidden layer, has
\[ \begin{aligned} & \mathbf{W}^{(1)} = \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix}, \qquad \mathbf{b}^{(1)} = \begin{bmatrix} -0.5 & -0.5 \end{bmatrix}^\top, \end{aligned} \]
and layer 2, which maps the hidden layer to the output, has
\[ \begin{aligned} & \mathbf{W}^{(2)} = \begin{bmatrix} 1 & 1 \end{bmatrix}, \qquad b^{(2)} = -0.5. \end{aligned} \]
The full forward pass is then a single composition of the two layers,
\[ \begin{aligned} & y \;=\; f\!\left( \mathbf{W}^{(2)} \, f\!\left( \mathbf{W}^{(1)} \begin{bmatrix} x_1 & x_2 \end{bmatrix}^\top + \mathbf{b}^{(1)} \right) + b^{(2)} \right). \end{aligned} \]
Question: Using the weights and biases above, perform the forward pass for each of the four possible inputs. Verify that the network’s predictions match the targets in Table 1.
Answer:
Plugging in each of the four possible inputs reproduces the XOR truth table. For \((x_1, x_2) = (1, 0)\), for example,
\[ \begin{aligned} h_1 & = f(1 - 0 - 0.5) = f(0.5) = 1 \\[0.5em] h_2 & = f(-1 + 0 - 0.5) = f(-1.5) = 0 \\[0.5em] y & = f(1 + 0 - 0.5) = f(0.5) = 1, \end{aligned} \]
which matches the target \(1 \oplus 0 = 1\).
The other three inputs work the same way. The table below lists all four forward passes.
| \(x_1\) | \(x_2\) | \(h_1\) | \(h_2\) | \(y\) | \(t\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
It is worth becoming comfortable moving between the three views we have used. These are the per-neuron formulas, the labelled network diagram, and the matrix–vector parameters. They contain exactly the same information, but the matrix–vector form is what we will use throughout the rest of the chapter and beyond, because it scales naturally to networks with many units per layer and many layers, where listing the formulas for each unit individually would be impractical.
Question: Solution 2 decomposes XOR as
\[ \begin{aligned} & x_1 \oplus x_2 = (x_1 \vee x_2) \;\wedge\; \neg(x_1 \wedge x_2). \end{aligned} \]
Using the same architecture as Figure 2 and the threshold activation function, design a network based on Solution 2. First, decide which Boolean function each hidden unit and the output unit should compute. Then, derive the weights and biases for \(h_1\), \(h_2\), and \(y\).
Answer:
Solution 2 assigns the OR function to \(h_1\), the NAND function to \(h_2\), and the AND function to \(y\). Applying the three-step procedure from Step 3 to each unit gives the following neurons.
\[ \begin{aligned} h_1 = x_1 \vee x_2 & = f\!\left(\, x_1 + x_2 - 0.5 \,\right) \\[0.5em] h_2 = \neg(x_1 \wedge x_2) & = f\!\left(-x_1 - x_2 + 1.5 \,\right) \\[0.5em] y = h_1 \wedge h_2 & = f\!\left(\, h_1 + h_2 - 1.5 \,\right). \end{aligned} \]
Other weights and biases also work, as long as each unit separates the same positive and negative examples. Figure 7 shows the Solution 2 network with all edge weights. Figure 8 shows its decision regions in the input plane.
Solution 2 weighted XOR network
Solution 2 XOR decision regions
The general lesson from this example applies well beyond XOR. A two-layer neural network can perfectly classify data that is not linearly separable by creating new features through the hidden units such that the transformed data points become linearly separable in these new features.
Our two XOR networks illustrate a property of neural networks called non-identifiability, which means that very different weights can produce the same predictions. The two networks share the same architecture and activation function, but use different weights and biases. Yet both classify all four points perfectly.
3 Expressiveness of Neural Networks
In the XOR example, adding a hidden layer with just two units let the network perfectly classify the XOR data points, which are not linearly separable. So neural networks are clearly more expressive than linear models. But how much more expressive are they? What functions can a neural network represent? The answer depends on several factors, including the number of layers in the network, the number of units in each layer, and the chosen activation functions. First, we show that without nonlinear activation functions, adding more layers does not make a network more expressive. Next, we describe which functions an MLP can represent in principle. Then, we build a network by hand that represents any function from binary inputs to binary targets. Finally, we discuss what these results do not tell us.
3.1 Why Nonlinear Activations Matter
Suppose every hidden layer used the identity activation function, so each layer only applied an affine transformation
\[ \begin{aligned} & \mathbf{a}^{(m)} = \mathbf{z}^{(m)} = \mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}. \end{aligned} \]
Could stacking many such layers represent patterns that one linear layer cannot?
The answer is no. Any sequence of affine layers can be rewritten as one affine map. For example, the result of composing two linear layers with input \(\mathbf{a}^{(0)}\) is
\[ \begin{aligned} \mathbf{a}^{(2)} & = \mathbf{W}^{(2)} \mathbf{a}^{(1)} + \mathbf{b}^{(2)} \\[0.5em] & = \mathbf{W}^{(2)} \bigl( \mathbf{W}^{(1)} \mathbf{a}^{(0)} + \mathbf{b}^{(1)} \bigr) + \mathbf{b}^{(2)} \\[0.5em] & = \underbrace{\mathbf{W}^{(2)} \mathbf{W}^{(1)}}_{\mathbf{W}'} \mathbf{a}^{(0)} + \underbrace{\mathbf{W}^{(2)} \mathbf{b}^{(1)} + \mathbf{b}^{(2)}}_{\mathbf{b}'}. \end{aligned} \]
The forward pass through these two layers produces the same output as one linear layer
\[ \begin{aligned} & \mathbf{a}^{(2)} = \mathbf{W}' \mathbf{a}^{(0)} + \mathbf{b}', \end{aligned} \]
whose weight matrix and bias vector are
\[ \begin{aligned} & \mathbf{W}' = \mathbf{W}^{(2)} \mathbf{W}^{(1)}, \qquad \mathbf{b}' = \mathbf{W}^{(2)} \mathbf{b}^{(1)} + \mathbf{b}^{(2)}. \end{aligned} \]
By repeated substitution, any number of linear layers collapses to one. Therefore, a deep network whose hidden activations are all linear has the same expressive power as logistic or linear regression.
Nonlinear activation functions prevent this collapse because a hidden layer’s output
\[ \begin{aligned} & f^{(m)}(\mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}) \end{aligned} \]
is generally not an affine function of \(\mathbf{a}^{(m-1)}\). Thus, the network can form decision boundaries that are not one hyperplane, as in the XOR example. Even the ReLU activation function
\[ \begin{aligned} & \text{ReLU}(z) = \max(0, z) \end{aligned} \]
is enough, since its change in slope at \(z = 0\) prevents the collapse.
3.2 Universal Function Approximators
How can we quantify the expressive power of a neural network formally? It turns out that MLPs with nonlinear hidden activations are universal function approximators. Intuitively, given enough hidden units, an MLP can approximate any continuous function as closely as we want. Decision trees are another universal approximator class, as discussed in Learning Decision Trees.
Definition: A model class \(\mathcal{A}\) is a universal function approximator if, for any continuous target function \(f\), meaning any continuous ground-truth mapping from input \(x\) to output \(t\), and for any desired level of approximation error \(\epsilon > 0\), there exists some hypothesis \(h \in \mathcal{A}\) such that
\[ \begin{aligned} & |h(x) - f(x)| < \epsilon \end{aligned} \]
for all \(x\) in the domain or in a relevant, sufficiently large subset of the domain.
Although the definition above is for a scalar function only, it illustrates the broad idea that applies to vector-valued functions as well. If we care about accuracy up to tolerance \(\epsilon\) on a region of inputs, we can choose a network in the class whose predictions are within \(\epsilon\) of the target everywhere on that region. The definition does not say how large the network must be, only that some network in the class exists.
For MLPs, the classical result is the universal approximation theorem, which instantiates the definition above for shallow networks and continuous targets.
Theorem (universal approximation): Let \(\mathcal{X} \subset \mathbb{R}^D\) be compact, meaning closed and bounded. For any continuous function \(f : \mathcal{X} \to \mathbb{R}\) and any \(\epsilon > 0\), there exists an MLP with a single hidden layer, a finite number of hidden units, and a nonlinear, bounded, continuous activation function \(\sigma\), such as sigmoid or \(\tanh\), whose output \(h(\mathbf{x})\) satisfies
\[ \begin{aligned} & |h(\mathbf{x}) - f(\mathbf{x})| < \epsilon \end{aligned} \]
for all \(\mathbf{x} \in \mathcal{X}\).
In other words, if we only care about inputs in a bounded region, an MLP with one hidden layer and enough hidden units can get as close as we want to any continuous function. The activation function must be nonlinear, but a simple one such as sigmoid or \(\tanh\) is enough. Later results show that ReLU and other common activation functions work as well.
The theorem only guarantees that suitable weights exist. We return to what it does not guarantee in Limitations of Universality, after working through a concrete construction.
3.3 Universality for Binary Inputs and Targets
Let’s make the universal approximation theorem more concrete by considering the case of binary inputs and targets. Consider a dataset with \(D\) binary features \(x_j \in \{0, 1\}\) and a binary target \(t \in \{0, 1\}\). We will hand-design an MLP with one hidden layer to classify the data perfectly. However, the hidden layer may contain an exponential number of hidden units, up to \(2^D\).
Consider the dataset in Table 2, which is not linearly separable. There are \(D = 3\) binary features and a binary target \(t \in \{0, 1\}\).
| \(i\) | \(x_1\) | \(x_2\) | \(x_3\) | \(t\) |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |
| 5 | 1 | 0 | 0 | 0 |
| 6 | 1 | 0 | 1 | 1 |
| 7 | 1 | 1 | 0 | 0 |
| 8 | 1 | 1 | 1 | 1 |
3.3.2 Output Layer Design
Now that we have a design recipe that ensures that a hidden unit outputs \(1\) if and only if the inputs match a given target pattern, we can use this recipe to design a two-layer network to fit Table 2.
First, since our recipe ensures that a hidden unit outputs \(1\) for a given input pattern, it is best suited to model an example with a target value of \(1\) rather than an example with a target value of \(0\). Therefore, we can design one hidden unit for each row with a target value of \(1\). For Table 2, we have four such rows, namely rows 1, 3, 6, and 8, and therefore need to design four hidden units, \(h_1\), \(h_3\), \(h_6\), and \(h_8\).
Question: Using the two-step design recipe above, design a hidden unit for each of the four rows in Table 2 with target \(t = 1\), which are rows \(1\), \(3\), \(6\), and \(8\). For each unit, write the input weights \(\mathbf{w}\) and bias \(b\) so that the unit fires if and only if the inputs match that row’s pattern. You may use Figure 9 and Figure 10 to check your answers.
Answer:
Apply Step 1 with \(w_i = +1\) where the pattern requires \(x_i = 1\) and \(w_i = -1\) where it requires \(x_i = 0\). With these weights, the maximum weighted sum equals the number of \(1\)s in the pattern, which we denote by \(k\). Every other input has a weighted sum of at most \(k - 1\). In Step 2, the bias must therefore satisfy the following inequalities.
\[ \begin{aligned} & k + b \ge 0 \quad \Rightarrow \quad b \ge -k, \\ & (k - 1) + b < 0 \quad \Rightarrow \quad b < 1 - k. \end{aligned} \]
Any \(b \in [-k, 1 - k)\) works, and we choose the midpoint \(b = 0.5 - k\). The four units are listed below.
| Hidden unit | Pattern \(\mathbf{x}\) | \(\mathbf{w}\) | \(b\) |
|---|---|---|---|
| \(h_1\) | \(\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}^\top\) | \(\begin{bmatrix} -1 & -1 & -1 \end{bmatrix}^\top\) | \(0.5\) |
| \(h_3\) | \(\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}^\top\) | \(\begin{bmatrix} -1 & 1 & -1 \end{bmatrix}^\top\) | \(-0.5\) |
| \(h_6\) | \(\begin{bmatrix} 1 & 0 & 1 \end{bmatrix}^\top\) | \(\begin{bmatrix} 1 & -1 & 1 \end{bmatrix}^\top\) | \(-1.5\) |
| \(h_8\) | \(\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}^\top\) | \(\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}^\top\) | \(-2.5\) |
Next, we need a way to combine these hidden unit outputs into a single output. We want the output to be \(1\) whenever the inputs match at least one of the four target patterns, and \(0\) otherwise. This corresponds to a logical OR operation, which is true if and only if at least one of the inputs is \(1\). Therefore, we can design the output unit to implement the OR function. Specifically, we can set the output weight for each hidden unit to be \(1\). The output bias should be \(-0.5\) so that the output fires when at least one of the hidden units is \(1\). See the complete solution in Figure 11 below.
Binary universal construction network
We designed hidden units for the rows with \(t = 1\) because our design recipe produces a hidden unit that outputs \(1\) for exactly one pattern. Alternatively, we could have designed hidden units for the rows with \(t = 0\). In that case, the output unit would compute NOR instead of OR, outputting \(1\) only when none of the hidden units fires. It suffices to design hidden units for one target value only because the target value is binary.
3.4 Limitations of Universality
The universal approximation theorem guarantees that a suitable network exists, but it has three limitations that matter in practice.
First, the theorem does not say how many hidden units are needed, and the number can be exponential. Our construction in the previous section illustrates this. We designed one hidden unit for every input pattern with target \(t = 1\). Since there are \(2^D\) input patterns, the hidden layer can grow exponentially with the number of features. For example, with \(D = 20\), the construction could require over a million hidden units.
Adding more hidden layers is the usual fix for excessive width. Instead of making one wide hidden layer, we can design a deeper network with multiple narrower hidden layers. Since each layer reuses and combines the features computed by the layer below, a deeper network can often represent the same function with far fewer units in total. The best depth and width for a given problem are still chosen empirically, but this efficiency is a key reason multi-layer networks are used in practice.
Second, a network that fits the training data may not generalize. If a network can represent any function, it can also memorize any dataset, including its noise and label errors. A sufficiently large network can achieve perfect training accuracy and still perform poorly on unseen data. Yet predicting unseen data accurately is the main goal of machine learning.
Third, the theorem does not tell us how to find the weights. We chose the weights and biases by hand in the previous section, but real data rarely has a structure simple enough for that approach to work. Instead, we learn the weights by minimizing a loss function, typically with gradient descent. The next chapter develops backpropagation, the algorithm that efficiently computes the gradients this optimization requires.
4 Summary
Neural networks extend linear models by stacking affine transformations with nonlinear activation functions. The XOR example shows that a compact hand-designed network can perfectly classify data that no linear classifier can. Without nonlinear activation functions, any depth collapses to a single linear map and gains nothing over logistic regression. With them, even a two-layer network is a universal approximator. The pattern-detector construction shows that a threshold network with one hidden layer can represent any function from binary inputs to a binary output. But existence is not enough. The guaranteed network may be exponentially wide, we still need an algorithm to find the weights from data, and a model powerful enough to fit any training set can just as easily memorize it without generalizing.
Two fundamental ideas run through this chapter. Fundamental Idea #4, which states that ML describes geometric processes, explains why nonlinearity matters. Each hidden unit carves the input space with a hyperplane, and the output layer composes those half-spaces into the non-convex decision regions that let a network perfectly classify data that is not linearly separable, such as XOR. Fundamental Idea #1, which states that learning is optimization, explains the gap the construction leaves open. Hand-picking weights works only in toy settings. In practice, we minimize a loss over the weight space, which requires gradients. The next chapter develops backpropagation, the algorithm that makes gradient computation tractable for large networks.