XOR problem
Section of Neural units, part of Statistical learning
XOR problem
| Type | Section |
| Taught in | Neural units |
| Part | Statistical learning |
| Questions using it | 4 |
A single threshold unit separates two classes by a hyperplane, so the problems it can solve are the linearly separable ones. AND, OR, and NAND are linearly separable. OR is class 1 except where both inputs are off, and a hyperplane can put that single point on the other side. AND is the opposite corner. XOR is the diagonal: the positive class occupies (0,1) and (1,0), and the other class occupies (0,0) and (1,1).
The function is g:\{0,1\}\times\{0,1\}\to\{0,1\} with desired triples (x_1,x_2,y) equal to (0,0,0), (0,1,1), (1,0,1), (1,1,0). The proof compares four linear inequalities. Add the two inequalities that come from the positive corners and compare the sum with the two inequalities that come from the negative corners.
Theorem 1 (A single threshold unit cannot compute XOR) No choice of w_0,w_1,w_2 makes f(w_0+w_1 x_1+w_2 x_2) equal XOR on \{0,1\}^2.
The four patterns require
w_0<0,\qquad w_0+w_2\ge 0,\qquad w_0+w_1\ge 0,\qquad w_0+w_1+w_2<0.
Adding the middle two gives 2w_0+w_1+w_2\ge 0. The last requirement and w_0<0 give
2w_0+w_1+w_2=w_0+(w_0+w_1+w_2)<0,
a contradiction. The four requirements cannot hold together. This is the failure Minsky and Papert pointed out for the perceptron. These four points, with this labelling, are one configuration a linear classifier leaves unshattered. The VC dimension of half-spaces in the plane is 3. The support vector page records that count: it uses a general-position argument, and a single failed labelling is the witness that these four points are not a shattered set.
Used in
- Taught in Neural units
- Also used in Backpropagation · Support vector machines
- Questions that use it (4) — Logic gates · An XOR network of your own · Linear hidden units · Nonlinear separation of XOR
- All 7 questions on Neural units
See also
A single threshold unit cannot compute XOR · Polynomial kernel · Artificial neuron · Perceptron learning rule · One hidden layer approximates continuous functions · History of the neural unit · Neural unit · Linear separability