An Implementation of Adaptive Logic Networks Copyright W.W. Armstrong, Andrew Dwelly, Rolf Manderscheid, Monroe Thomas November 11, 1990 initial implementation on Unix (TM AT&T) bug-fixes and initial port to DOS Rolf Manderscheid April 15, 1991 ported to Microsoft Windows Monroe M. Thomas May 31, 1991 revised for Version 2.0 Monroe M. Thomas July 17, 1991 1 Introduction The C library atree.c contains an implementation of an unconventional kind of learning algorithm for adaptive logic networks[Arms], which can be used in place of the backpropagation algorithm for multilayer feedforward artificial neural networks [Hech], [Rume]. The ability of a logic network to learn or adapt to produce an arbitrary boolean function specified by some empirical "training" data is certainly important for the success of the method, but there is another property of logic networks which is also essential. It is the ability to generalize their responses to new inputs, presented after training is completed. The successful generalization properties of these logic networks are based on the observation, backed up by a theory [Boch], that trees of two-input logic gates of types AND, OR, LEFT, and RIGHT are very insensitive to changes of their inputs. Some experiments on handwritten numeral recognition and satellite image classification have been successfully carried out. [Arms3, Arms4]. Recent experiments have shown this algorithm to learn quickly on some problems requiring learning of integer or continuous-valued functions where backpropagation has reportedly led to long training times; and it functions very well on boolean data [Arms5]. At the present time, only limited comparisons have been made with the conventional approach to neurocomputing, so the claims necessarily have to be muted. This situation should rapidly be overcome as users of this software (or improved variants of it yet to come) begin experimentation. However one property of these networks in comparison to others is an absolute, and will become apparent to computer scientists just by examining the basic architecture of the networks. Namely, when special hardware is available, this technique, because it is based on combinational logic circuits of limited depth (e. g. 10 to 20 propagation delays), can potentially offer far greater execution speeds than other techniques which depend on floating point multiplications, additions, and computation of sigmoidal functions. A description of the class of learning algorithms and their hardware realizations can be found in [Arms, Arms2], but we will briefly introduce the concepts here. An atree (Adaptive TREE) is a binary tree with nodes of two types: (1) adaptive elements, and (2) leaves. Each element can operate as an AND, OR, LEFT, or RIGHT gate, depending on its state. The state is determined by two counters which change only during training. The leaf nodes of the tree serve only to collect the inputs to the subtree of elements. Each one takes its input bit from a boolean input vector or from the vector consisting of the complemented bits of the boolean input vector. The tree produces a single bit as its output. Despite the apparent limitation to boolean data, simple table-lookups permit representing non-boolean input values (integers or reals for example) as bit vectors, and these representations are concatenated and complemented to form the inputs at the leaves of the tree. For computing non-boolean outputs, several trees are used in parallel to produce a vector of bits representing the output value. This software contains everything needed for a programmer with knowledge of C and Windows 3.x to create, train,From daemon Sun Apr 19 22:01:26 1992 Received: by helix.nih.gov (5.64/helix-1.0) id AA20226; Sun, 19 Apr 92 22:01:23 -0400 Date: Sun, 19 Apr 92 22:01:23 -0400 From: MAILER-DAEMON (Mail Delivery Subsystem) Subject: Returned mail: User unknown Message-Id: <9204200201.AA20226@helix.nih.gov> To: PostMaster@helix.nih.gov To: glav Status: RO ----- Transcript of session follows ----- 550 ?... User unknown ----- Unsent message follows ----- Received: by helix.nih.gov (5.64/helix-1.0) id AA20221; Sun, 19 Apr 92 22:01:23 -0400 Date: Sun, 19 Apr 92 22:01:23 -0400 From: glav (Giovanni Lavorgna) Message-Id: <9204200201.AA20221@helix.nih.gov> Subject: test Cc: ? this is a test only! cc. cc. .. From MAILER-DAEMON@alw.nih.gov Sun Apr 19 22:03:58 1992 Received: from alw.nih.gov by helix.nih.gov (5.64/helix-1.0) id AA20343; Sun, 19 Apr 92 22:03:56 -0400 Received: from helix.nih.gov by alw.nih.gov (5.61/alw-2.1) id AA00285; Sun, 19 Apr 92 22:03:52 -0400 Date: Sun, 19 Apr 92 22:03:52 -0400 From: MAILER-DAEMON@alw.nih.gov (Mail Delivery Subsystem) Subject: Returned mail: User unknown Message-Id: <9204200203.AA00285@alw.nih.gov> To: PostMaster@helix.nih.gov To: Status: RO ----- Transcript of session follows ----- >>> RCPT To: <<< 550 ... Addressee unknown 550 ... User unknown ----- Unsent message follows ----- Received: from helix.nih.gov by alw.nih.gov (5.61/alw-2.1) id AA00283; Sun, 19 Apr 92 22:03:52 -0400 Received: by helix.nih.gov (5.64/helix-1.0) id AA20338; Sun, 19 Apr 92 22:03:52 -0400 Date: Sun, 19 Apr 92 22:03:52 -0400 From: glav@helix.nih.gov (Giovanni Lavorgna) Message-Id: <9204200203.AA20338@helix.nih.gov> Subject: test Cc: glav.nih.gov%DXI.DNET@dxi.nih.gov this is a new test! From glav Sun Apr 19 22:13:10 1992 Received: by helix.nih.gov (5.64/helix-1.0) id AA20588; Sun, 19 Apr 92 22:13:09 -0400 Date: Sun, 19 Apr 92 22:13:09 -0400 From: glav (Giovanni Lavorgna) Message-Id: <9204200213.AA20588@helix.nih.gov> To: txt@atree, glav@helix.nih.gov Status: RO