CS6910 · Week 1 · Representation power of a network of perceptrons

Any boolean function with 2ⁿ hidden perceptrons

Theorem Week 1, p. 85
Any boolean function of n inputs can be represented exactly by a network of perceptrons containing 1 hidden layer with 2ⁿ perceptrons and one output layer containing 1 perceptron.

Interactive diagram

Inputs n: Function:

Drag to rotate · scroll or pinch to zoom · right-drag to pan.

weight +1 weight −1 perceptron fires output weight +1 (f = 1) output weight −1 (f = 0)

Click a row to feed that input to the network. Click an f cell to flip the function's output, which builds your own boolean function.

How the construction works

  1. Encoding: True = +1, False = −1 p. 72.
  2. One hidden perceptron per input combination. There are 2ⁿ rows in the truth table, so there are 2ⁿ hidden perceptrons.
  3. Input → hidden weights copy the pattern: +1 (blue) where the pattern has True and −1 (red) where it has False. The bias is −n (−2 for n = 2 on p. 72, −3 for n = 3 on p. 83), so a hidden perceptron fires only if Σ wᵢxᵢ ≥ n.
  4. Only one fires for each input. Σ wᵢxᵢ reaches n only when every input agrees with the pattern. Each mismatch lowers the sum by 2. So “each perceptron in the middle layer fires only for a specific input, and no two perceptrons fire for the same input” p. 74.
  5. Hidden → output weights are the truth table. Since exactly one hidden perceptron is on, the output sees only that perceptron's weight. Set it to +1 if f = 1 for that row and −1 if f = 0. With output threshold 1, y = f(x). “Each of the weights in the second layer is responsible for one of the inputs and can be adjusted to produce the desired output for that input” p. 83.

The catch: exponential growth

Inputs nHidden perceptrons 2ⁿTotal perceptrons 2ⁿ + 1

The 2ⁿ count is sufficient, not necessary p. 85. For example, AND needs just one perceptron. In the PYQ (“10 inputs, sufficient k = ?”) the answer is 2¹⁰ = 1024.