XOR problem
In plain wordsThe classic puzzle of teaching a single artificial neuron the 'one or the other but not both' rule. It cannot be done with one straight dividing line, which showed why networks need hidden layers.
The task of learning the exclusive-or function, which outputs 1 when exactly one of two binary inputs is 1; it is the standard example of a problem that is not linearly separablelinear separability, n.: When two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case., since no single line separates the points (0,1) and (1,0) from (0,0) and (1,1). Hence a single-layer perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong. or any linear classifier, including logistic regressionlogistic regression, n.: A simple, widely used method for yes-or-no predictions that outputs a probability — say, a 70% chance a customer cancels — by passing a weighted sum of inputs through an S-shaped curve. on the raw inputs, cannot represent it, whereas a network with one hidden layerhidden layer, n.: Any layer of a neural network between the input and the output. Its values are never shown to the user; they are the network's internal working-out. of two nonlinear units can, for example by computing OR and NAND and combining them with AND. The problem is the textbook illustration of why nonlinearity and hidden layers matter; its n-bit generalization, the parity function, remains a hard case for several learning methods.
Our first exercise is the XOR problem: watch the hidden units learn OR and NAND.
Origin
Marvin Minsky and Seymour Papert's book Perceptrons (1969) analyzed formally which predicates single-layer perceptrons can compute, showing that those whose feature detectors each see only a limited part of the input cannot compute parity or connectedness; XOR, the two-input case of parity, became the emblematic example. David Rumelhart, Geoffrey Hinton and Ronald Williams's 1986 backpropagation work used XOR to show hidden units learning the internal representation it requires.
Usage note
The story that the XOR result alone caused the first AI winterAI winter, n.: A slump in which disappointment over AI's unmet promises leads governments and companies to pull back money and attention. Historians count two big ones: one in the 1970s and one starting in the late 1980s. oversimplifies: Minsky and Papert knew multilayer networks could compute XOR, and the funding decline had several causes.
Related
- perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong.
- linear separabilitylinear separability, n.: When two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case.
- Perceptrons (book)Perceptrons (book), prop. n.: A 1969 book by Marvin Minsky and Seymour Papert proving that simple one-layer neural networks cannot learn certain patterns. It is widely blamed for a decade-long slump in neural-network research.
- multilayer perceptronmultilayer perceptron, n.: A neural network made of several layers of artificial neurons, each connected to every neuron in the next layer. It is the simplest kind of deep network and a component of almost every modern model.
- hidden layerhidden layer, n.: Any layer of a neural network between the input and the output. Its values are never shown to the user; they are the network's internal working-out.
- AI winterAI winter, n.: A slump in which disappointment over AI's unmet promises leads governments and companies to pull back money and attention. Historians count two big ones: one in the 1970s and one starting in the late 1980s.
Mentioned in
perceptronperceptron, n.: One of the first learning machines: a single artificial neuron that sorts inputs into two groups by drawing a straight dividing line, nudging its weights whenever it guesses wrong., Perceptrons (book)Perceptrons (book), prop. n.: A 1969 book by Marvin Minsky and Seymour Papert proving that simple one-layer neural networks cannot learn certain patterns. It is widely blamed for a decade-long slump in neural-network research.