The XOR Problem and the Need for Hidden Layers

A decision boundary is linearly separable if a straight line (in 2D), plane (in 3D), or hyperplane (in N-D) can completely split the classes.

Logical AND and OR gates are linearly separable. For example, in an OR gate, a single line can separate the point (0,0) from (0,1), (1,0), and (1,1). However, the XOR gate outputs 1 only when the inputs differ: (0,1) and (1,0) are positive, while (0,0) and (1,1) are negative. No single straight line can separate these two pairs in a 2D plane.

This simple logical function represents the fundamental bottleneck of early neural network research. Because the coordinates $(0,0)$ and $(1,1)$ are diagonally opposite, any linear decision boundary will always include at least one wrong class on either side.

In their 1969 book Perceptrons, Marvin Minsky and Seymour Papert mathematically proved that single-layer perceptrons could not solve the XOR problem. They went further to argue that multi-layer perceptrons would be too computationally complex to train, leading to a massive decline in funding for neural network research, a period known as the first AI winter.

This critique was only resolved in the 1980s with the rediscovery of the backpropagation algorithm. Backpropagation allowed networks to automatically learn features in hidden layers, making multi-layer neural networks highly practical.

Adding hidden layers between the input and output transforms the feature space, mapping non-linear relations into linear ones.

A hidden layer performs a non-linear coordinate transformation. By taking the inputs $x_1$ and $x_2$, applying weights and non-linear activation functions, the hidden layer projects the coordinates into a new space where the data points are linearly separable.

For example, if we create a hidden layer with two neurons representing AND and OR operations, the XOR output can be computed as a linear combination of these two hidden representations. The hidden layer acts as an automatic feature extractor, creating representations that are easier to classify.

The mathematical justification for hidden layers is formalised in the Universal Approximation Theorem. The theorem states that a feedforward network with a single hidden layer and a non-linear activation function can approximate any continuous function on compact subsets of $\mathbb{R}^n$ to arbitrary accuracy.

This theorem demonstrates that the limitation of the single-layer perceptron is completely overcome by adding hidden units. However, it does not guarantee that the weights can be easily learned, which is why optimizing network depth and architecture remains a major area of research.

Let's implement a Multi-Layer Perceptron (MLP) in PyTorch and verify that it can successfully classify XOR inputs.

Here is a simple MLP with one hidden layer containing 2 neurons, which is sufficient to solve the XOR gate problem:

In this code, we use the Sigmoid activation function to introduce non-linearity in the hidden layer. The output of the hidden layer provides a transformed representation that the final output neuron can easily separate with a single linear decision boundary.

We can check the decision boundary by inspecting the weights. The hidden layer splits the input space into two lines: one line checking if the sum of inputs is greater than 0.5, and another checking if it is greater than 1.5.

By combining these two lines, the output layer can isolate the diagonal points $(0,1)$ and $(1,0)$ from the others. This geometric decomposition shows how multi-layer architectures solve complex logical topologies.