AN ESTIMATE OF THE COMPLEXITY REQUISITE IN A UNIVERSAL DECISION NETWORK Scott H. Cameron Armour Research Foundation INTRODUCTION A decision network as it is discussed herein is an assemblage of real components having: 1) a number of "input" connections on which binary input signals appear simultaneously, and 2) a single "output" connection on which a binary output signal appears. The value of the output signal is a function only of the set of input signals and is independent of the values of the input signals in the past. The function of the decision network is to "decide" whether or not the set of input signal values currently appearing on the input connections is or is not possessed of some particular abstract feature and to indicate the nature of this decision by means of the output signal. Examples of such networks include the familiar conjunctive and disjunctive logical operators as well as character or symbol identification networks in which the input signals are derived from a number of points in a retinal field and the output "decision" is intended to indicate whether or not the input pattern possesses the abstract feature which the human might regard as A-ness or B-ness. A universal decision network is a decision network having a sufficient number of adjustable parameters and a structure such that sets of parameter values may be found so that the network can render a valid decision relative to all possible abstractions of the input set. Since the input signals are twovalued, this is equivalent to the statement that a universal network of input connections is capable of "realizing" or computing each of the 2 Boolian functions of arguments for some set of parameter values. Since that output "decision" is in general a function of all the input signal values and is also to be two-valued, it is clear that at least one non-linear operation will be required. A network in which the output is obtained by a linear combination of the input signals would not in general provide a twovalued output. In particular we will be concerned in this discussion with the threshold operator and we will in fact postulate that the threshold operator is the simplest structure capable of serving as a decision network. The threshold operator is illustrated in Fig. 1 where its operational characteristics are defined. A decision network may consist of a single threshold operator or it may consist of an assemblage of such operators. The complexity of a network of threshold operators is measured simply in terms of the total number of such operators employed in the network. THE THRESHOLD OPERATOR We now consider the general characteristics of the threshold operator and ask initially whether or not the threshold operator is universal in the sense defined previously. (The adjustable parameters are the coefficients ... a, and .) It is easy to show that this is not the case, and in fact, a threshold operator of two inputs is capable of computing only 14 of the 16 possible functions of two arguments. The Boolean function y = The Boolean function y2+2 and are not realizable by means of the threshold operator. We now attempt to compute a quantity R(n) which we will define as the number of different functions of n arguments for which there exists a mechanization by means of the threshold operator of n n inputs. While the development of an expression giving R(n) precisely for each n seems to be an exceedingly difficult problem, we may obtain an upper bound for R(n) by means of the follow ing argument. n Let I," represent the jth input configuration, i.e., associate the input set with an n bit binary number so that each input configuration (set of input values) is represented by an integer in the range of sero to 2-1. I," may also be regarded as a column matrix of the following form: n (1) In this case X = 1, x2 = 0, x3 ' 1, x4 = 1, and 1011 is the binary representa tion of the decimal number 11. Let An by a row matrix whose elements are the multiplicative coefficients of the threshold operator, e.g. A4 = ( 21 22 23 24) Note that the operation of the threshold operator may be restated as: (2) The equation IA - is the equation of a hyper-plane in a space of A n n+1 dimensions, the coordinate axis of which are 21, 22, + n behavior such that its response to X, is y = 1, while threshold parameters j represented by a point on the opposite side of the plane result in y = 0 for the input I. The set of planes IA = 0 for j - 1, 2, 3, ---2a partitions the space into a large number of regions within each of which the behavior of the |