On Optimal Computations Using Perceptrons

Abstract

This paper discusses optimal solutions for implementing arbitrary Boolean functions
using perceptrons. It starts by presenting neural structures and their biological inspirations, while
mentioning the simplifications leading to artificial neural networks. The state-of-the-art when
using neural networks as universal approximators, as well as size optimal perceptron solutions
are shortly overviewed. Afterwards we detail a result of Horne and Hush (1994), showing that a
neural network of perceptrons restricted to fan-in 2 can implement arbitrary Boolean functions,
but requires O(2^n/n) perceptrons in O(n) layers. This result is generalised to arbitrary fan-ins, and
used to prove that all the relative minimums of size are obtained for sub-linear ('small') fan-in
values. On one side, this result shows a limitation of using perceptrons to implement arbitrary
Boolean functions. On the other side, the result is in good agreement with hardware (i.e. VLSI
implementations), where the area and the delay are directly related to fan-ins (and to the precision
of the synaptic weights). The main conclusion is that discrete VLSI-efficient solutions are
connectivity (fan-in) limited even when using perceptrons