What functions can a neuron compute?

From the statements in McCulloch and Pitts (1943) it follows naturally that their neurons are equivalent to a model commonly used nowadays, where:

• Each neuron $i$ is in either of two states at time $t$: $x_i[t]=1$ or ``firing'' and $x_i[t]=0$ or ``not firing'';
• all synapses (connections) are equivalent and characterized by a real number (their strength), which is positive for excitatory connections and negative for inhibitory connections;
• a neuron $i$ becomes active when the sum of those connections $w_{ij}$ coming from neurons $j$ connected to it which are active, plus a bias $b_i$, is larger than zero.

This is usually represented by

$$x_i[t] =\theta\left( b_i + \sum_{j\in C(i)} w_{ij} x_j[t-1]\right),$$ (3.1)

where $\theta(x)$ is the step function: 1 when $x>=0$ and 0 otherwise and $C(i)$ is the set of neurons that impinge on neuron $i$. This kind of neural processing element is usually called a threshold linear unit or TLU. The time indexes are dropped when processing time is not an issue (Hertz et al., 1991, 4).

If all inputs (assume there are $n$ of them) to a TLU are either 0 or 1, the neuron may be viewed as computing a logical function of $n$ arguments. The truth table of an arbitrary, total logical function of $n$ arguments has $2^n$ different rows, and the output for any of them may be 0 or 1. Accordingly, there are $2^{(2^n)}$ logical functions of $n$ arguments. However, there are logical functions a TLU cannot compute. For $n=1$ all 4 possible functions (identity, negation, constant true and constant false) are computable. However, for $n=2$ there are two noncomputable functions, corresponding to the exclusive or and its negation. The fraction of computable functions cannot be expressed as a closed-form function of $n$ but vanishes as $n$ grows (Horne and Hush, 1996)). The computable functions correspond to those in which the set of all input vectors corresponding to true outputs and the set of all input vectors corresponding to false outputs are separable by a $n$-dimensional hyperplane in that $n$-dimensional space. This follows intuitively from eq. (2.1): the equation of the hyperplane is the argument of function $\theta$ equated to zero.

The computational limitations of TLUs have a radical consequence: to compute a general logical function of $n$ arguments, one needs a cascade of TLUs. For example, to compute the exclusive-or function one needs at least two TLUs, as shown in figure 2.1.

Figure: Two TLUs may be used to compute the exclusive-or function ($u_1$ and $u_2$ are the inputs, $y$ is the output, and biases are represented as connections coming from a constant input of 1).

A common layout is the so-called multilayer perceptron (MLP) or layered feedforward neural net (Haykin (1998), ch. 4; Hertz et al. (1991), ch. 6). In this layout:

• Each neuron belongs to a subset called layer.
• If neuron $i$ belongs to layer $I$ then all neurons $j$ sending their output to neuron $i$ belong to layer $I-1$.
• Layer $0$ is the input vector.

The backpropagation (BP) learning algorithm (Haykin (1998), sec. 4.3; Hertz et al. (1991), ch. 6) is usually formulated for the MLP.