Neural Networks

6.2 The XOR problem

1. What did Minsky and Papert (1969) prove about single neural units?
   That a single unit (perceptron) cannot compute some very simple functions of its input, notably XOR.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, p. 154
2. What is a perceptron?
   A simple neural unit with a binary output and a step-function activation: \(y = 1\) if \(w \cdot x + b > 0\), else 0.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, p. 154
3. Give perceptron weights that compute AND and OR on binary inputs.
   AND: \(w_1 = w_2 = 1\), \(b = -1\). OR: \(w_1 = w_2 = 1\), \(b = 0\). (Many other settings work.)
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, p. 155
4. Why can’t a perceptron compute XOR?
   A perceptron is a linear classifier: its decision boundary \(w_1x_1 + w_2x_2 + b = 0\) is a line. No line separates XOR’s positive cases (01, 10) from its negative cases (00, 11); XOR is not linearly separable.

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, p. 155
5. What is a decision boundary in higher dimensions?
   A hyperplane separating the input space into the two output classes.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, p. 155
6. How can a neural network compute XOR?
   With a layered network: e.g. two hidden ReLU units and one output unit (Goodfellow et al., 2016). The hidden layer maps inputs [0, 1] and [1, 0] to the same point, after which positive and negative cases are linearly separable.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, pp. 155–156
7. What lesson does the XOR network teach about hidden layers?
   The hidden layer forms a new representation of the input in which the problem becomes easy. With backpropagation, networks learn such useful representations automatically.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 6, §6.2, p. 156