2.1 Some Preliminary Results on Neural Network Mapping Capabilities

In this section, some basic LTG network architectures are defined and bounds on the number of arbitrary functions which they can realize are derived. The realization of both Boolean and multivariate functions of the form : Rn  {0, 1} are considered.

2.1.1 Network Realization of Boolean Functions

A well known result from switching theory (e.g., see Kohavi, 1978) is that any switching function (Boolean function) of n-variables can be realized using a two layer network with at most 2n-1 AND gates in the first (hidden) layer and a single OR gate in the second (output) layer, assuming that the inputs and their complements are available as inputs. This network is known as the AND-OR network and is shown in Figure 2.1.1. The parity function is a Boolean function which requires the largest network, i.e., the network with 2n-1 AND gates. For the case n = 4, the K-map of the parity function is shown in Figure 2.1.2.

Figure 2.1.1. AND-OR network structure.

Figure 2.1.2. K-map for the 4-input parity function.

It was shown in Chapter One that a single LTG is a more powerful logic gate than a single AND (or OR) gate. Thus, one may replace the hidden layer AND gates in Figure 2.1.1 with LTG's and still retain the universal logic property of the AND-OR network [The universality of a properly interconnected network of simple threshold gates was first noted in a classic paper by McCulloch and Pitts (1943)]. The resulting net with the LTG's does not require the complements of the input variables as inputs, as for the AND-OR net. This LTG net will be referred to as a threshold-OR net. Given the same switching function, the threshold-OR net may require a smaller number of gates compared to an AND-OR net. The parity function, though, is an example where the required number of AND gates is equal to the number of threshold gates in both nets; i.e., 2n-1 gates. Note that a fewer number of hidden LTG's than AND gates are needed if the LTG net employs an LTG for the output unit. However, it can be shown (see Section 2.2.1) that hidden LTG's would still be necessary for realizing arbitrary Boolean functions in the limit of large n. Another interesting result is that a two hidden layer net with LTG's is necessary for realizing arbitrary Boolean functions (see Section 2.2.2 for details). Here, LTG's are sufficient.

The synthesis of threshold-OR and other LTG nets for the realization of arbitrary switching functions was extensively studied in the sixties and early seventies. A recommended brief introduction to this subject appears in the book by Kohavi (1978). In fact, several books and Ph.D. dissertations have been written on threshold logic networks and their synthesis (refer to the introduction of Chapter One for references). Here, we give only a simple illustrative example employing the K-map technique (the K-map was introduced in Section 1.1.1) to realize the Boolean function f(x) in Figure 2.1.3(a). Figure 2.1.3(b) shows one possible decomposition of f(x) into a minimal number of threshold patterns (single LTG realizable patterns) f1(x) and f2(x). The corresponding architecture for the threshold-OR net realization is depicted in Figure 2.1.3(c). This K-map-based synthesis technique may be extended to multiple output nets (see Problem 2.1.2), but is only practical for .

(a) (b) (c)

Figure 2.1.3. Threshold-OR realization of a 3-input switching function f(x): (a) K-map for f(x); (b) K-map decomposition of f(x) into two threshold functions; and (c) Threshold-OR realization of f(x).

The following theorem establishes an upper bound on the size of a feedforward net of LTG's for realizing arbitrary, partially specified switching functions.

Theorem 2.1.1: Consider a partially specified switching function f(x) defined on a set of m arbitrary points in {0, 1}n, with m 2n. Then, a two layer net of LTG's employing m LTG's in its hidden layer, feeding into a single output LTG, is sufficient to realize f(x).

Proof of Theorem 2.1.1:

This theorem can be viewed as a corollary of Theorem 1.4.1 of Chapter One (see Problem 2.1.2).

Theorem 2.1.1 can be easily extended to the case of multiple output switching functions of the form . Here, the worst case scenario is to duplicate the above network L times where L is the number of output functions! This leads to a sufficient LTG net realization having mL LTG's in its hidden layer and L LTG's in its output layer.

2.1.2 Bounds on the Number of Functions Realizable by a Feedforward Network of LTG's

Consider the following question: How many functions : Rn {0, 1} defined on m arbitrary points in Rn are realizable by a layered net of k LTG's? In the following, this question is answered for three different network architectures. First, a single hidden layer feedforward network, second, an arbitrarily interconnected net with no feedback, and finally a two hidden layer feedforward network. All three nets are assumed to be fully interconnected.

(2.1.1)

Figure 2.1.4. A two layer feedforward net with k hidden LTG's feeding into a single output LTG.

Proof:

Each of the k LTG's can realize at most (Winder, 1963; Also, recall Problem 1.3.3)

functions (dichotomies), and the final LTG can realize at most

functions. Therefore, the network can realize no more than

or

functions.

Another interesting type of network is the generally, fully interconnected net of k LTG's with no feedback shown in Figure 2.1.5. This type of network can realize at most G(nmk) functions with G given by

(2.1.2)

Figure 2.1.5. Generally fully interconnected net of k LTG's with no feedback.

Proof:

Since there is no feedback, the gates (LTG's) can be ordered as first gate, second gate, ..., kth gate, so that the jth gate only receives inputs from the n independent variables and the j - 1 gates labeled 1, 2, ..., j - 1 (see Figure 2.1.5). The jth gate can then realize at most

functions. The total network can realize at most

functions, which is less than

This last result can be simplified to

Similarly, it can be shown that the feedforward net shown in Figure 2.1.6 with two hidden layers of LTG's each, and with a single output LTG, is capable of realizing at most

(2.1.3)

functions.

Figure 2.1.6. A three layer LTG net having units in each of the two hidden layers and a single output LTG.

Similar bounds can be derived for points in general position by simply replacing the bound on the number of realizable functions by the tighter bound for input units (units receiving direct connections from all components of the input vector), since the statistical capacity of a single d-input LTG is 2(+ 1) points, for large d (refer to Section 1.3.3).

Goto [2.0] [2.2] [2.3] [2.4] [2.5]