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 model 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
\[t = x_1 \oplus x_2.\]
| \(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 data set, 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,
\[ f(z) = \begin{cases} 1 & \text{if } z \geq 0 \\ 0 & \text{if } z < 0. \end{cases} \]
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, determine the meanings of the features computed by the hidden units, and then figure out how to compute the features.
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
The underlying idea is to think of the hidden units as computing new features that make the problem linearly separable. Our task then becomes determining what these features are and how to compute them. 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
\[ x_1 \oplus x_2 = (x_1 \wedge \neg x_2) \;\vee\; (\neg x_1 \wedge x_2) \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
\[ x_1 \oplus x_2 = (x_1 \vee x_2) \;\wedge\; \neg(x_1 \wedge x_2) \tag{Solution 2} \]
Both decompositions provide intermediate features that could be represented with hidden neurons. 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 as follows.
- Hidden unit \(h_1\) will compute \(x_1 \wedge \neg x_2\).
- Hidden unit \(h_2\) will compute \(\neg x_1 \wedge x_2\).
- Output unit \(y\) will compute \(h_1 \vee h_2\).
Each unit now computes a simple Boolean function whose positive and negative examples are linearly separable.
Solution 1 Boolean subproblems
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 \[ h_1 = x_1 \wedge \neg x_2 \]
We are going to design a 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 and one positive examples. 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 half way through the gap.
Decision boundary for \(h_1\)
Next, write an equation for the line. Since the line is at 45-degree and passes through the point \((0.5, 0)\), we can show that the line can be represented by the equation below. \[ x_2 = x_1 - 0.5 \] It has a slope of \(1\) and a y-intercept of \(-0.5\). Let’s move all the quantities to left side and get the following equation. \[ - x_1 + x_2 + 0.5 = 0. \]
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 \[ - 1 + 0 + 0.5 = - 0.5 < 0. \] 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 \[ h_1 = f(x_1 - x_2 - 0.5) \] which corresponds to the weights and the bias below. Following our MLP notation, \(h_1\) is unit 1 in layer 1.
\[ W^{(1)}_{1,1} = 1, \qquad W^{(1)}_{1,2} = -1, \qquad b^{(1)}_1 = -0.5. \]
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 it as an equation \(= 0\), 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\).
\[ x_2 = x_1 + 0.5 \]
Moving all the quantities to the left side gives
\[ -x_1 + x_2 - 0.5 = 0. \]
Plugging in the positive example \((x_1, x_2) = (0, 1)\) gives
\[ -0 + 1 - 0.5 = 0.5 \geq 0. \]
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 \[ W^{(1)}_{2,1} = -1, \qquad W^{(1)}_{2,2} = 1, \qquad b^{(1)}_2 = -0.5. \]
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\).
\[ h_2 = -h_1 + 0.5 \]
Moving all the quantities to the left side gives
\[ h_1 + h_2 - 0.5 = 0. \]
Plugging in the positive example \((h_1, h_2) = (1, 0)\) gives
\[ 1 + 0 - 0.5 = 0.5 \geq 0. \]
The expression is already non-negative at the positive example, so we keep the signs. Therefore, \[ y = f(h_1 + h_2 - 0.5), \] The weights and the bias are \[ W^{(2)}_{1,1} = 1, \qquad W^{(2)}_{1,2} = 1, \qquad b^{(2)} = -0.5. \]
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) \\ h_2 = \neg x_1 \wedge x_2 &= f\!\left(-x_1 + x_2 - 0.5 \,\right) \\ 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
\[ \mathbf{W}^{(1)} = \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix}, \qquad \mathbf{b}^{(1)} = \begin{bmatrix} -0.5 \\ -0.5 \end{bmatrix}, \]
and layer 2, which maps the hidden layer to the output, has
\[ \mathbf{W}^{(2)} = \begin{bmatrix} 1 & 1 \end{bmatrix}, \qquad b^{(2)} = -0.5. \]
The full forward pass is then a single composition of the two layers,
\[ y \;=\; f\!\left( \mathbf{W}^{(2)} \, f\!\left( \mathbf{W}^{(1)} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \mathbf{b}^{(1)} \right) + b^{(2)} \right). \]
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 \\ h_2 &= f(-1 + 0 - 0.5) = f(-1.5) = 0 \\ 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
\[ x_1 \oplus x_2 = (x_1 \vee x_2) \;\wedge\; \neg(x_1 \wedge x_2). \]
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 \(h_1 = x_1 \vee x_2\), the NAND function \(h_2 = \neg(x_1 \wedge x_2)\), and the AND function \(y = h_1 \wedge h_2\). 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) \\ h_2 = \neg(x_1 \wedge x_2) &= f\!\left(-x_1 - x_2 + 1.5 \,\right) \\ 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 network 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
\[ \mathbf{a}^{(m)} = \mathbf{z}^{(m)} = \mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}. \]
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)} \\ &= \mathbf{W}^{(2)} \bigl( \mathbf{W}^{(1)} \mathbf{a}^{(0)} + \mathbf{b}^{(1)} \bigr) + \mathbf{b}^{(2)} \\ &= \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
\[ \mathbf{a}^{(2)} = \mathbf{W}' \mathbf{a}^{(0)} + \mathbf{b}', \]
whose weight matrix and bias vector are
\[ \mathbf{W}' = \mathbf{W}^{(2)} \mathbf{W}^{(1)}, \qquad \mathbf{b}' = \mathbf{W}^{(2)} \mathbf{b}^{(1)} + \mathbf{b}^{(2)}. \]
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 \[ \sigma^{(m)}(\mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}) \] 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 \[ \text{ReLU}(z) = \max(0, z) \] 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 \(|h(x) - f(x)| < \epsilon\) 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 non-linear, bounded, continuous activation function \(\sigma\), such as sigmoid or \(\tanh\), whose output \(h(\mathbf{x})\) satisfies \(|h(\mathbf{x}) - f(\mathbf{x})| < \epsilon\) 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 also has important limitations. First, the theorem tells us that suitable weights exist, but not how to find them. In practice, we use Backpropagation to learn the weights from data. Second, the theorem does not tell us how many hidden units we need for a given accuracy. The network may need to be arbitrarily wide, as we will see in the next section. Finally, even if a network can fit the training data arbitrarily well, it may not generalize to unseen data.
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 which 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 those examples 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.
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\). Set \(b = -0.5\) in Step 2, although any \(b \in [-1, 0)\) works. The four units are listed below.
| Row | Pattern \(\mathbf{x}\) | \(\mathbf{w}\) | \(b\) |
|---|---|---|---|
| 1 | \(\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}^\top\) | \(\begin{bmatrix} -1 \\ -1 \\ -1 \end{bmatrix}\) | \(-0.5\) |
| 3 | \(\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}^\top\) | \(\begin{bmatrix} -1 \\ 1 \\ -1 \end{bmatrix}\) | \(-0.5\) |
| 6 | \(\begin{bmatrix} 1 & 0 & 1 \end{bmatrix}^\top\) | \(\begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}\) | \(-0.5\) |
| 8 | \(\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}^\top\) | \(\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\) | \(-0.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\) instead and produced an equivalently valid network. It suffices to design hidden units for one target value only because the target value is binary.
3.4 Exponential Width
Why might one hidden unit per positive example be a problem? With \(D\) binary input features, there are \(2^D\) possible input patterns, and up to \(2^D - 1\) of them could have target \(t = 1\). Our construction places one hidden unit per positive example, so the hidden layer can be as wide as \(2^D\), which is exponential in the number of features. Even for a modest \(D = 20\), that is over a million hidden units.
This is the main limitation the construction reveals about the universal approximation result. The theorem guarantees that a two-layer network wide enough to fit the data perfectly always exists, but it says nothing about how wide “wide enough” actually is. Width can be exponential, which is not practical.
In practice, the solution is to add more hidden layers. Deeper networks can often represent the same function with far fewer total units, because each layer can reuse and combine features built by the previous one rather than detecting every pattern from scratch. Choosing the right depth and width for a given problem is still done empirically, but the intuition that depth trades width for layers is a key reason multi-layer networks are used in practice.
3.5 What Universality Does Not Guarantee
The universal approximation theorem is a powerful existence result, but existence is not enough for practical machine learning. Three gaps stand between “a network that fits the data exists” and “we have a network that works.”
The theorem does not tell us how to find the weights. The pattern-detector construction above sets weights by hand, exploiting the structure of binary inputs and targets. For real data there is no such recipe. Instead, we search the weight space by minimizing a loss function, typically with gradient descent. That search is the subject of the next chapter. The backpropagation algorithm makes it feasible at scale. This reflects Fundamental Idea #1, which states that learning is optimization.
The guaranteed network may be impractically large. Even in the restricted binary setting, the construction can require \(2^D\) hidden units. The universal approximation theorem for continuous functions makes no width guarantee at all. A network that approximates \(f\) to accuracy \(\epsilon\) may exist, but the theorem does not say how many hidden units it needs. A guarantee that a solution exists somewhere in an exponentially large space is not the same as a guarantee that we can build or train it.
A network that fits the training data may not generalize. The ability to represent any function is precisely the ability to memorize any dataset, including its noise and label errors. A universal approximator with enough parameters can achieve perfect training accuracy and still generalize poorly on unseen data, and predicting unseen data accurately is the main goal of machine learning.
These three gaps motivate the next chapter, which develops backpropagation, the algorithm that computes the gradients needed to learn weights from data rather than hand-pick them.
4 Summary
Neural networks extend linear models by stacking affine transformations with nonlinear activation functions. Without 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 binary function on \(\{0,1\}^D\), and the XOR example shows that a compact hand-designed network can perfectly classify data that no linear classifier can. 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.