Page 205 -

5.6 Performance of Neural Networks 193

Having seen how the number of possible dichotomies grows with the number of
patterns, we now turn to the issue of evaluating the discriminative capability of a
given network. We start by analysing the two-class classification case with two-
layer perceptrons (i.e., with a single hidden layer) with hard-limiters.
For two-layer perceptrons an interesting result, due to Mirchandani and Cao
(1989), is that in 91d the maximum number of regions that are linearly separable,
with h hidden neurons, R(h, 4, is given by:

d
i),
~(h,d)= ~(h, setting C(h, i) = 0 for h < i
i=O

Figure 5.31. Number of total dichotomies (dotted line) and linearly separable
regions (solid line), able to be implemented by a perceptron in a two-dimensional
space (logarithmic vertical scale).

This formula allows us to set a lower bound to the number of training patterns:
n 2R(h,d), since we need at least one pattern for each trainable region. In
particular, the formula yields:

- R(h, d) = 2h for h l d ;
- R(h, 4 = h+l for d=l.
In practice, one needs a number of patterns that is significantly greater than
R(h, d) in order for the network to be able to generalize. An upper bound on the
number of hidden neurons for any single hidden layer MLP is the number of
patterns itself (see Huang and Babri, 1998).