Assignment of functional responsibility in perceptrons
Rik Achiel Verstraete · University of California at Los Angeles eBooks · 1986
Perceptrons are defined to be multilayered networks of fixed topology that consist of adjustable combinational nodes. These nodes are not necessarily threshold gates, and the functional flexibility is present in all the layers (not just a single node or a single layer). The resulting network implements a modifiable Boolean function. The fundamental problem addressed is thus assignment of functional responsibility in a multilayered network. The original perceptron research is reviewed and its extensiveness is demonstrated. Other existing implementations, both analog and digital, are also presented, and an implementation developed by us is discussed at length. Perceptrons are useful in applications that require a fast and modifiable implementation of Boolean functions. An important emerging application domain is presented: combinational rule-based systems. It is shown that some propositional-logic rule bases can be transformed into a pair of Boolean functions, which could be implemented with perceptrons. Next, one aspect of the responsibility assignment in multilayered systems, namely the decomposition of a Boolean function on a given perceptron, is treated in detail. The theory of decomposition of Boolean functions is applied to this problem. The solution to the decomposition problem can be obtained in a straightforward fashion if the network has no fan-out connections. In a more general case, the decomposition problem is solved with a bottom-up search algorithm. At each node a few assignments are selected by a local selection criterion and tried in sequence. A reduction step between two nodes coordinates assignments to different nodes. Finally, the requirement that the given network function be specified completely in advance is relaxed. Two approaches towards distributed learning by example in binary tree networks, taken from the literature, are reviewed, followed by our contribution. The theory of decomposition of Boolean functions is again the basic tool in this study.