Discrimination - Neural Networks: Methodology and Applications - page 335

Fig. 6.4. Two Boolean functions; left : function OR, realizable with a perceptron;
right : the complement of the XOR (the non-XOR), not realizable by a perceptron

perceptron without threshold in an extended input space of dimension N +1.
In that space, we define the linear potential as follows:

v L = N w i x i = w · x ,

i =0

where the subscript stands for linear (to distinguish it from the generalized
potentials introduced in the following sections). The perceptron's output is
given by

σ L =sign( v L ) .
The perceptron separates the inputs x into two subsets, depending on the out-
put value σ . From the definitions of the (linear) potential and the output of
the perceptron, the weight vector w is normal to a hyperplane in R N +1 (a hy-
perplane is the generalization to dimension N of a plane in three-dimensional
space). That hyperplane contains the origin and separates the examples with
σ = 1 from those with σ = − 1. The former obey w · x > 0, the latter w · x < 0.

Thus, the perceptron performs linear separations in input space.
If we restrict the inputs to take only binary values, a perceptron performs
a Boolean function of its inputs, that is, an application from

{ 0 , 1 } N +1 onto

{ ). Clearly, it is unable to perform

some functions, like the exclusive-or (XOR) or its complement, as shown on
Fig. 6.4b.
Given the inputs x k of the training set, which are M points in a space
of N dimensions, there are 2 M possible Boolean functions of those points.
That number increases exponentially with M . Although it is not known how
many Boolean functions are linearly separable, it has been shown that their
number increases with M like a power law (

0 , 1 } (or from {− 1 , +1 } N +1 onto {− 1 , +1 }

M n , with n> 1), much slower
than exponentially. For large M , the linearly separable functions are a very
small fraction of all the possible Boolean functions. Thus, the perceptron can
perform a very small number of Boolean functions of its inputs.

≈