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, evaluate, and print out adaptive logic networks. It has been written for clarity rather than speed in the hope that it will aid the user in understanding the algorithms involved. The intention was to try make this version faster than variants of the backpropagation algorithm for learning, and to offer much faster evaluation of learned functions than the standard approach given the same general-purpose computing hardware. Users of the software are requested to provide some feedback on this point to the authors. This software also includes a language "lf" that allows a non-programmer to conduct experiments using atrees, as well as a number of demonstrations. A version of this software which is both faster and contains a more effective learning algorithm is planned for the near future. Y ³ ÚÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄ¿ ³ Random Walk ³ ³ Decoder ³ ÀÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÙ ÚÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄ¿ ³ Output Vector ³ ÀÂÄÄÄÄÄÄÄÄÄÄÄÄÄÂÙ ³ ³ Trees - one per (O) (O) output bit ³ ³ ÚÄÄÄÄÄÁÄÄÄÄ¿ ÚÄÁÄ¿ (O)ÄÙ ÀÄ(O) ³ ³ ÚÄÁÄ¿ ÚÄÁÄ¿ (O)Ù À(O) (O)Ù À(O) ÚÄÁÄ¿ ÚÄÁÄ¿ ÚÄÁÄ¿ ÚÄÁÄ¿ ³ ³ ³ ³ ³ ³ ³ ³ b1 ~b1 b2 ~b1 ~b1 ~b2 b2 ~b2 Random Connections ÚÄÄÄÄÄÄÂÄÄÄÄÄÄ¿ ³ ~b1 ³ ~b2 ³ Complements ÀÄÄÂÄÄÄÁÄÄÂÄÄÄÙ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³ ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÚÄÄÁÄÄÄÂÄÄÁÄÄÄ¿ ³ b1 ³ b2 ³ Input Vector ÀÄÄÂÄÄÄÁÄÄÂÄÄÄÙ ÚÄÄÄÄÁÄÄÄÄÄÄÁÄÄÄ¿ ³ Random Walk ³ ³ Encoder ³ ÀÄÄÄÂÄÄÄÄÄÄÄÂÄÄÄÙ ³ ³ X1 X2 Figure 1: Using several trees to compute Y = f(X1, X2) 2 Writing Applications With atree Writing applications that perform a simple classification (yes or no) is relatively easy (within the constraints of Windows programming). The programmer creates a training set, then creates a tree using atree_create(). The tree is trained using atree_train() and then it can be used to evaluate new inputs using atree_eval(). Examples of this can be seen in the files mosquito.c, and mult.c, both of which hide most of Windows' dressings for clarity. Writing applications where the tree has to learn real number valued functions is a little more complex, as the programmer has to come to grips with the encoding problem. Because a single tree produces only one bit, the programmer must train several trees on the input data, each one responsible for one bit of the output data. This is made slightly simpler by the choice of parameters for atree_train() which takes an array of bit vectors as the training set, and an array of bit vectors for the result set. The programmer provides an integer which states which bit column of the result set the current tree is being trained on. Typical code might look as follows:- .... { int i; int j; LPBIT_VEC train; /* LPBIT_VEC is a long (far) pointer to a bit_vec */ LPBIT_VEC result; LPATREE *forest; /* LPATREE is a long (far) pointer to an atree */ /* Create the training set using your own domain function */ train = domain(); /* Create the result set */ result = codomain(); /* * Make enough room for the set of trees - one tree per bit in the * codomain */ forest = (LPATREE *) Malloc((unsigned)sizeof(LPATREE) * NO_OF_TREES); /* Now create and train each tree in turn */ for (i = 0; i < NO_OF_TREES; i++) { forest[i] = atree_create(variables,width); atree_train(forest[i], train, result, i, TRAIN_SET_SIZE, MIN_CORRECT, MAX_EPOCHS, VERBOSITY); } /* * Where TRAIN_SET_SIZE is the number of elements in train, * MIN_CORRECT is the minimum number of elements the tree should * get correct before stopping, MAX_EPOCHS is the absolute maximum * length of training and VERBOSITY controls the amount of * diagnostic information produced. */ ...... The standard encoding of integers into binary numbers does not work well with this algorithm since it tends to produce functions which are sensitive to the values of the least significant bit. So instead we use the routine atree_rand_walk() to produce an array of bit vectors where each vector is picked at random and is a specified Hamming distance away from the previous element. Picking the width of the encoding vector, and the size of the step in Hamming space is currently a matter of experimentation, although some theory is currently under development to guide this choice. Real numbers are encoded by dividing the real number line into a number of quantization levels, and placing each real number to be encoded into a particular quantization. Obviously, the more quantization levels there are, the more accurate the encoding will be. Essentially this procedure turns real numbers into integers for the purposes of training. The quantizations are then turned into bit vectors using the random walk technique again. Once the trees are trained, we can evaluate them with new inputs. Despite their training, the trees may not be totally accurate, and we need some way of dealing with error. The normal approach taken is to produce a result from the set of trees, then search through the random walk for the closest bit vector. This is taken as the true result. Typical code might be as follows:- .... /* Continued from previous example */ int closest_elem; int smallest_diff; int s; LPBIT_VEC test; LPBIT_VEC tree_result; /* Now create the (single in this example) test vector */ test = test_element(); /* Now create some room for the tree results */ tree_result = bv_create(No_OF_TREES); /* Evaluate the trees */ for (i = 0; i < NO_OF_TREES; i++) { /* * Set bit i of tree_result, the result of evaluating * the ith tree. */ bv_set(i, tree_result, atree_eval(forest[i], test)); } /* * tree_result probably has a few bits wrong, so we will look * for the closest element in the result array */ closest_elem = 0; smallest_diff = MAX_INT; for (i = 0; i < TRAIN_SET_SIZE; i++) { if ((s = bv_diff(tree_result, result[i])) < smallest_diff) { smallest_diff = s; closest_elem = i; } } /* * At this point, result[closest_elem] is the correct bit vector, * and smallest_diff is the amount of error produced by the tree. */ do_something_with(result[closest_elem]); /* Etc. */ } .... 3 The Windows atree Library The atree library consists of a single include file atree.h, which must be included in all software making calls on the library, and a library of routines atree.c. The routines permit the creation, training, evaluation and testing of adaptive logic networks in a Windows environment, and there are a number of utility routines designed to make this task easier. Important note: the module definition file for your application must include in its EXPORT section the name of the atree Status window procedure: VerbosityWndProc, along with any other window procedures your application may have - see mosquito.def for an example. 3.1 Naming Conventions Throughout this software, the following conventions have been used :- Publicly available functions are called atree_something(). If the routine is primarily concerned with bit vectors rather than atrees, it will be named bv_something() instead. The exceptions to this occur for functions that are directly responsible for maintaining performance of the atree software in the Windows environment. Variables are always in lower case. The variables i, j, and k are reserved as iterators in "for" loops. The variable verbosity is reserved for controlling the amount of diagnostic information produced. 3.2 Public Macros The following macros are defined in atree.h and are available to any application using the atree library. The macro MEMCHECK allows us to check the validity of a pointer. For example, if the pointer p in MEMCHECK(p) is NULL, then a message box pops up with appropriate notification, and the application is terminated. The macro RANDOM allows us to conveniently produce a random number between 0 and some user- specified x in the program. For example, in order to produce a random true or false value (0 or 1) we write RANDOM(2). The macro Malloc serves as a front end for the atree memory allocation routine WinMem_Malloc(). To allocate a chunk of 16 bytes to a pointer p, use p = Malloc(16). The macro Free serves as a front end for the atree memory routine WinMem_Free(). To free the memory pointed by a pointer p that was allocated with WinMem_Malloc() (or the macro Malloc), use Free(p). 3.3 void atree_init(hInstance) HANDLE hInstance; This routine should be called by the user before making calls to any other atree library routine. The parameter hInstance should be the instance handle given to your application by Windows in your WinMain() procedure. Currently, atree_init() calls the srand() routine to initialize the random number generator and initializes the atree Status window. 3.4 void atree_quit() This routine sets the internal atree_quit_flag variable to TRUE to notify all atree procedures that it is time to drop whatever it is they are doing and quit. This procedure should be called before your application exits so that any running atree procedures are not left in memory. 3.5 LPBIT_VEC atree_rand_walk(num,width,p) int num; int width; int p; The standard encoding of integers into binary is not suitable for adaptive logic networks, since the least significant bits vary quickly during incrementations of the integer compared to the more significant bits. The effect of binary number encoding is easy to see when we consider the result of a single bit error occurring in the output of a collection of trees (a forest): how important the error is depends on the position of the bit in the output vector. An error in the least significant bit of the vector makes a difference of one unit in the output integer; an error in the most significant bit causes a large difference in the output integer depending on the width of the vector. A better encoding is one where each bit varies at about the same rate; and we can create such an encoding by taking a random walk through Hamming space [Smit]. A randomly produced vector is chosen to represent the first integer value in a sequence. For each subsequent integer, a specified number of bits, picked a random, are changed to create the next vector. The routine atree_rand_walk() does this job, with the additional guarantee that each vector produced is unique. The parameter num gives the number of vectors, or "steps" in the walk, required, the parameter width gives the width in bits of each vector, and the parameter p is the distance of each step in the Hamming metric (the number of bits which change). The uniqueness requirement makes the routine rather more complex than one might expect. Because we expect to be using large random walks, it was felt that a simple check against all the previously created vectors would not be efficient enough. Instead all vectors with the same weight (the weight of a bit vector is the number of 1s in it; e. g., the weight of 10110 is 3) are chained together, and only those vectors with a weight equal to the one currently being checked for uniqueness are examined. If the vector is not unique, the routine will go back to the previous unique vector and try randomly changing some other bits. In order to avoid an infinite loop, it will only try MAX_RETRY times to do this. If it cannot proceed, the routine aborts. A better version of the software would check to assure a minimum distance between points. A bit of thought must go into the choice of width, the length of the bitstring used to encode a quantity, and to the stepsize p. Suppose we want num quantization levels for a variable x. Then the width used to code x must be at least as large as the logarithm base 2 of num to make the codes unique. A thermometer code would use num - 1 bits, where the quantization level i (starting at 0 and increasing to num - 1) is represented by i 1s at the left of the vector completed by 0s at the right. For example, if num = 100, then width must be at least 7, while the thermometer code would use 99 bits. The width for an input variable is not as critical as for an output variable, since we need to train one tree for each bit in the output. Suppose some training data contains vectors with two variables in the domain. Two domain vectors (x1, x2) could be (3.14, 9.33), corresponding to levels (11, 17), and (3.18, 9.48), corresponding to (13, 18), say. The function y=f(x1,x2) to be learned is supposed continuous, so the two function values could be 34.6 and 33.9, with neighboring quantization levels 67 and 66 respectively. If the training set has been learned perfectly, then we shall get the correct boolean codes for levels 67 and 66 from the trained forest of trees on input of these vectors. When we only have vectors close to the above two vectors in Euclidean distance, then problems arise. Suppose we have an input (3.15, 9.34), corresponding also to levels (11, 17). Obviously, the trees give the same response as for (3.14, .933), namely level 67 of y. As long as this is an acceptable approximation to the desired function, there is no problem. If the quantized function value varied too much within the set of real vectors corresponding to (11,17), we would have to use a finer quantization on the inputs. Next suppose that the training set contained no sample with quantization levels (12, 17). Then we would like the system to be able to take advantage of the similarity between the concatenated codes for (12, 17) and (11, 17) to be able to extrapolate its output. This can occur if the codes for levels 11 and 12 of x1 are close in Hamming distance. If, on the other hand, they were 1/2 of the width of the code for x1 apart, then the system could just as well extrapolate from a training point with levels (96, 17) as from (11, 71). So we would take p for the random walk for x1 to be less than, say, 1/4 width to make sure levels 11 and 12 of x1 are close. This is because random pairs of points in the Hamming space tend to be 1/2 width apart. If neighboring training samples tended to have x1 values which are four levels apart, e. g. (11, 17) and (15, 17), then 4 * p would have to be less than 1/4 width. Now if we vary both x1 and x2, then neighboring input vectors might tend to be four levels apart in x1 and 7 levels apart in x2. Then the values px1, px2 chosen for p for the two walks should be such that 4 * px1 + 7 * px2 is less than 1/4 the sum of the widths wx1, wx2 for coding x1, x2. There is a good reason for using a large value of the p for the output variable y. Namely, for a given input vector, some of the width trees may produce an output bit that is different from that of a code of the correct quantization level of y as one varies the input a bit. If fewer than p/2 output bits are changed, we are still close to the original code, and the same output quantization level would still be recovered by minimum distance decoding. Consider the case where there are only num = 2 levels of y, and they are encoded 00000 and 11111, with width = 5 and p = 5. As we move away from inputs resulting in a correct response, say 00000, to those having two bits different, like 01001, the decoded output will maintain its value. So for the output variables, choosing larger values for p and width can provide error correction just as taking a majority vote does for a boolean output. We are aware that this only touches the surface of the questions involved with choosing the Hamming codes for continuous variables. The general assumptions are that real intervals are mapped into random walks in a way that locally preserves "proximity", and it is the proximity of elements in the domain and codomain that determines the quality of extrapolation. Instead of using random walks, some work has been done using algebraic codes, in particular Golay codes. This will be discussed in a thesis at U. of A. by Allen Supynuk, which is soon to be completed. 3.6 public LPATREE atree_create(numvars,leaves) int numvars; int leaves; This is the routine used to create an atree of a given size. The parameter leaves gives the number of leaves or output leads to the tree, and hence controls its size, which is one less than this. A balanced tree is chosen if possible. The parameter numvars is the number of boolean variables in the bit vector input to the tree. It is used during initialization of the (random) connections between leaf nodes of the tree and the input bit vector. Usually the bits of the input vector, and their complements will be required as inputs to the tree since there are no NOT nodes in the tree itself. It is therefore recommended that there be at least twice as many inputs to the tree as there are bits in the input vector for a given problem: leaves >= 2 * numvars The atree library maintains two free lists, one each for leaves and nodes. atree_create() always uses memory from these lists. In the event that a free list is empty, a large block is allocated and added to the list. The size of the block can be adjusted by editing the compile-time constant NEWMALLOC defined in atree.c. 3.7 void atree_free(tree) LPATREE tree; This routine returns memory used by nodes and leaves of tree to the appropriate free list. Note that memory is not freed from the free lists. 3.8 BOOL atree_eval(tree,vec) LPATREE tree; LPBIT_VEC vec; This routine is responsible for calculating the output of a tree from a given bit vector. It takes advantage of the standard C definition of && and || to do this in the required parsimonious fashion [Meis][Arms5]. This routine also marks subtrees that are unevaluated, and sets the internal atree.n_sig_left and atree.n_sig_right values for a node. This information is used when atree_eval() is used from within atree_train(). 3.9 BOOL atree_train(tree,tset,...) LPATREE tree LPBIT_VEC tset; LPBIT_VEC correct_result; int bit_col; int tset_size; int no_correct; int epochs; int verbosity; This is the routine that adapts a tree to learn a particular function. It is a little more complex than you might expect as it has been arranged to make it convenient to train multiple trees on the same training set. The parameter tree is the tree to be trained, and the parameter tset is the array of bit vectors which the tree is to be trained on (the training set). An atree only produces a single bit, so in principle all that is needed for the correct_result parameter is an array of bits, with one bit corresponding to each bit vector in the training set. In training multiple trees (when learning a quantized real-valued function, for example), it is more convenient to keep the correct results in an array of bit vectors, and specify which column of the array a tree is supposed to be learning. This is the purpose of the array correct_result and the integer bit_col. The next parameter tset_size gives the number of elements in tset and correct_result (which have to be the same --- there must be a result for every input to the function). The next two parameters control the amount of training that is to be done. We train on the vectors of the training set in pseudo-random order. The term epoch here is used to mean a number of input vector presentations equal to the size of the training set. The parameter epochs states how many epochs may be completed before training halts. The parameter no_correct states how many elements in the training set the tree must get correct before training halts. The routine will therefore stop at whichever of these two conditions is true first. For example given that we have a training set with 10 elements and we wish to train for 15 epochs or until 90% of the elements in the training set have been responded to correctly. We can achieve this by setting no_correct to 9 and epochs to 15. The verbosity parameter controls how much diagnostic information the routine will produce. At the moment only 0 (silent) or 1 (progress information) is implemented. The progress information consists of an atree Status window that shows the progress of training. The routine decides which vector is the next to be presented to the tree and extracts the result bit from the correct_result array. It also keeps track of the number of epochs, and the number of correct responses from the tree. 3.10 void atree_print(tree,verbosity) LPATREE tree; int verbosity; This routine allows the programmer to output an atree to disk before, during, or after training, in a form suitable for printing. The parameter tree is the tree to be printed, and verbosity is the amount of information produced. The disk file is currently hard coded as "atree.out" (future versions of the software will allow user selected output streams). 3.11 int atree_store(tree, filename) LPATREE tree; LPSTR filename; (LPSTR is Windows for "char far *") This routine stores tree to filename. This routine is used to store a single tree, if you want to store a forest use atree_write(). Returns 0 for success, non-zero on failure. 3.12 LPATREE atree_load(filename) LPSTR filename; This routine reads filename and returns the tree stored therein. atree_load() reads exactly one tree from filename, if you want to read multiple trees use atree_read(). A NULL pointer is returned if any error or EOF is encountered. 3.13 LPATREE atree_read(stream) FILE *stream; This routine reads a single tree from the file referenced by stream and returns a pointer to it. Subsequent calls to atree_read() will read further trees from stream. A NULL pointer is returned if any error or EOF is encountered. 3.14 int atree_write(stream, tree) FILE *stream; LPATREE tree; This routine writes tree onto the file referenced by stream. Trees are stored in postfix notation, with the characters `&', `--', `L', `R' representing the node functions AND, OR, LEFT, RIGHT respectively. Leaves are stored as a number, representing the bit index, optionally preceded by a `!' for negation. The end of the tree is marked by a semicolon. Returns 0 for success, 1 on failure. 3.15 LPATREE atree_fold(tree) LPATREE tree; This routine removes all LEFT and RIGHT nodes from tree and returns the result. This does not change the function represented by the tree, but the resulting tree may be considerably smaller and hence faster to execute. Nodes and leaves that are discarded are added to the free lists. 3.16 LPFAST_TREE atree_compress(tree) LPATREE tree; This routine returns the fast_tree derived from tree. A fast_tree is essentially a list of leaves; each leaf includes two pointers to subsequent leaves to evaluate, one for each possible result of evaluating the current leaf. It is the function of atree_compress() to calculate these two "next" pointers for each leaf. Experiments show that evaluating a fast_tree is almost twice as fast as evaluating the corresponding folded atree. This is due to the fact that recursion is eliminated. Fast_trees are also slightly more compact than the equivalent atree. Note that there is no "decompression" routine, and there are no fast_tree I/O routines. 3.17 int atree_fast_eval(tree, vec) LPFAST_TREE tree; LPBIT_VEC vec; This routine is the equivalent of atree_eval, but for fast_trees. 3.18 void atree_fast_print(tree) LPFAST_TREE tree; This routine writes a representation of tree to the file "fasttree.out". Each line of output corresponds to a leaf and includes the leaf index, bit numbers (possible preceded by a `!' to indicate negation), and the two "next" pointers (shown as indices). NULL pointers are represented by -1. 3.19 int atree_set_code(code, high, low, ...) LPCODE_T code; double low; double high, int vector_count; int width; int dist; This is the constructor function for the type code_t. If width is greater than one, atree_set_code() calls atree_rand_walk() to get a random walk containing vector_count vectors, with adjacent vectors having a Hamming distance of dist between them. This random walk will represent numbers in the closed interval [low, high]. The functions atree_encode() and atree_decode() translate floating point quantities and bit vectors, respectively, into an index into the random walk. atree_set_code() also calculates the (real) distance between adjacent vectors and stores this in the step field of code. If width is equal to one, the code represents a boolean variable, and no random walk is produced. In this case low , high , and vector_count are taken to be 0, 1, and 2 respectively. The vector field will be set to point to bit vectors of length one having the appropriate values. 3.20 int atree_encode (x, code) double x; LPCODE_T code; This routine returns the quantization level of x as represented by code. To obtain the corresponding bit vector, use the expression: my_bit_vec = code -> vector + atree_encode(x, code) If the code is boolean (code -> width == 1), then atree_encode() returns 0 if x is 0, otherwise it returns 1. For non-boolean codes, atree_encode() issues a warning if x is out of range, and the output is clipped so that it lies within the range 0 .. code -> vector - 1. 3.21 int atree_decode(vec, code) LPBIT_VEC vec; LPCODE_T code; This routine returns the quantization level of vec as represented by code. To obtain the corresponding floating point value, use the expression: my_value = code -> low + (code -> step * atree_decode(vec, code) The quantization level corresponds to the first bit vector stored in the random walk having the smallest Hamming distance from vec. If the code is boolean, the quantization level is simply the value of vec (whose length must be 1). 3.22 LPCODE_T atree_read_code(stream, code) FILE *stream; LPCODE_T code; This routine reads a coding from stream and fills the entries of the code structure. A NULL pointer is returned if any error or EOF is encountered. 3.23 int atree_write_code(stream, code) FILE *stream; LPCODE_T code; This routine writes the contents of code onto stream. If the code is boolean, the vector field is not written. Returns 0 for success, 1 for failure. 4 The bv Library 4.1 LPBIT_VEC bv_create(length) int length; Creates a vector of length bits, where each bit is initialized to 0, and returns a long pointer to the bit vector. 4.2 LPBIT_VEC bv_pack(unpacked,length) LPSTR unpacked; int length; This routine has been provided to make it easy for the programmer to produce bit vectors. The routine is handed an array of characters containing the value 0 or 1 (unpacked) and an integer length giving the number of bits. The routine returns a long pointer to a bit_vec. 4.3 int bv_diff(v1,v2) LPBIT_VEC v1; LPBIT_VEC v2; This routine calculates the Hamming distance between v1 and v2, i.e. weight (v1 XOR v2) where weight is the number of 1 bits in a vector and XOR is the bitwise exclusive-or operation. This routine is used to find the closest vector in a random walk array to some arbitrary vector. Just search through the random walk for the vector with the smallest difference from the vector of tree output bits. (Inefficient, but easier to understand than decoding an algebraic code!). 4.4 LPBIT_VEC bv_concat(n,vectors) int n; LPBIT_VEC far *vectors; This routine is used by the programmer to join several bit vectors end-to-end to give the string concatenation of the vectors. This routine is most frequently used during the construction of training sets when elements of several random walks have to be joined together to obtain an input vector to a tree. The parameter vectors is an array of LPBIT_VEC pointers, and the parameter n states how many of them there are. Vector pointers are used to make this routine a little faster since there is less copying involved. A long pointer to the concatenated bit_vec is returned. 4.5 void bv_print(stream, vector) FILE *stream; LPBIT_VEC vector; This is a diagnostic routine used to print out a bit_vec. 4.6 void bv_set(n,vec,bit) int n; LPBIT_VEC vec; BOOL bit; This routine allows the programmer to explicitly set (or reset) the nth bit (0 to bit_vec.len - 1) bit in the vector vec to have the value in the parameter bit. 4.7 BOOL bv_extract(n,vec) int n; LPBIT_VEC vec; This routine returns the value of the nth bit (0 to bit_vec.len - 1) in the bit vector vec. 4.8 BOOL bv_equal(v1,v2) LPBIT_VEC v1; LPBIT_VEC v2; This routine tests two bit vectors for equality. 4.9 LPBIT_VEC bv_copy(vec) LPBIT_VEC vec; This routine returns a copy of vec. 4.10 void bv_free(vector) LPBIT_VEC vector; This routine frees the memory used by a bit_vec; accessing a bit_vec after it has been freed is usually disastrous. 5 Windows Support Library 5.1 void Windows_Interrupt(cElapsed) DWORD cElapsed; (DWORD is Windows for "unsigned long") When called, this procedure allows Windows to multitask an atree application with other Windows applications. This is accomplished with a PeekMessage() call (see the Windows Programmer's Reference for more details). The programmer may want to use this procedure during long tree evaluation and training set generation loops, or during other processing where control may not be passed back to the application's window procedure for lengthy periods of time (the price you pay for non-preemptive multitasking!). Since PeekMessage() calls can be quite time consuming, this procedure will only call PeekMessage() after cElapsed milliseconds have passed since the last call to PeekMessage(). Experimentation has shown a value for cElapsed of about 1500 to work fairly well. 5.2 LPSTR WinMem_Malloc(wFlags, wBytes) WORD wFlags; (WORD is Windows for "unsigned int(16-bit)") WORD wBytes; Since the segmented memory architecture of DOS based PC's can cause great grief when allocating large amounts of memory, the atree package includes its own memory manager. Requests for memory are obtained from dynamically allocated segments from the global heap in which local heaps have been initialized. The memory is actually allocated by Windows' local heap manager, and the resultant near (16 bit) pointer is combined with the global segment descriptor of the corresponding global heap segment to form a long (32 bit) pointer suitable for use in atree applications. wFlags indicates the kind of memory to allocate, usually LMEM_MOVEABLE, and wBytes indicate the number of bytes to allocate. See the Windows Programmer's Reference LocalAlloc() routine for more information on the different values wFlags may take. For ease of use, the programmer may simply wish to use the Malloc(wBytes) macro, which expands to WinMem_Malloc (LMEM_MOVEABLE | LMEM_ZEROINIT, wBytes). 5.3 LPSTR WinMem_Free(lpfree) LPSTR lpfree; This function frees the block of memory pointed to by lpfree, which is decomposed into a segment selector, which is used to identify the global segment from which the near pointer was allocated from, and a near pointer, which is used by Windows' LocalFree() to free memory from the local heap in the dynamically allocated segment. If there remains no more allocated memory in the local heap the global segment is deallocated. For ease of use, the Free(lp) macro expands to WinMem_Free((LPSTR) lp). The function returns NULL if successful, otherwise it returns lpfree. 6 The Language lf The second major product included in the current release is the "lf" language interpreter that allows a non- programmer to experiment with tree adaptation. The user specifies a training set, and a test set, and selects the encoding and quantization levels for a particular experiment. The interpreter checks the statements for errors then executes the desired experiment, finally outputting a table comparing the desired function with the function actually learned. Various post-processors can use the information to produce histograms of error or plots of the functions. It is recommended that the user read and understand [Arms5] before using this language. There are two versions of lf: LF.EXE and LFEDIT.EXE. LF.EXE inputs a file "lf.in" and outputs to a file "lf.out". LFEDIT.EXE is an interactive editor, but can only handle files of about 48K. Use LF.EXE to test SPHERE.LF (after copying it to "lf.in") or other lf files larger than 48K. 6.1 multiply.lf The language is best learned by examining an example. The file multiply.lf contains a simple experiment where we are trying to teach the system the multiplication table. The program is divided into a "tree" section which describes the tree and the length of training, and a "function" section which describes the data to be learned. Comments are started with a `#' mark and continue to the end of the line. # A comment. tree size = 4000 min correct = 144 max epochs = 20 The tree and function sections can be in any order, in this particular example the tree is described first. Apart from comments, tabs and newlines are not significant; the arrangement chosen above is only for readability. The first line after tree tells the system how large the atree is going to be. In this case we are choosing a tree with 4000 leaves (3999 nodes). We are going to train it until it gets 144 correct from the training set, or for 20 complete presentations of the training set, whichever comes first. Trees may also be read from a file with the "load tree from" statement. If this statement is specified, the tree size will be ignored and lf will output a warning message. Trees can be written to files using either the "save tree to" or "save folded tree to" statements. The statements in the tree section may be in any order. function domain dimension = 2 coding = 32:12 32:12 32:7 quantization = 12 12 144 training set size = 144 training set = 1 1 1 1 2 2 1 3 3 1 4 4 .... test set size = 144 test set = 1 1 1 1 2 2 1 3 3 1 4 4 .... The training set must start with a dimension statement which gives the number of columns in the function table. The domain dimension refers to the number of input columns. Lf supports training of multiple functions using the same inputs. This is done using the codomain dimension statement. If the codomain dimension statement is not specified, the number of codomains is assumed to be 1 (as in the above example). The total number of columns in the training and test sets must equal the sum of the domain and codomain dimensions (this doesn't mean a restriction on the format, just on what the number of elements in the table must be). In the above example, we are defining a problem with three columns: two input and one output. The other statements may come in any order; note however that the definition of the training set size must be defined before the training set. This also applies to the test set definition. The coding statement defines is a series of : definitions, one for each column. The is the number of bits in the bit vector for that column, the is the step size of the walk in Hamming space that defines the encoding of this column. Because a tree only produces a single bit in response to an input vector, the of the codomain columns (which come after the domain columns) actually defines how many trees will be learning output bits of this function. The quantization statement defines for each column the total number of coded bit vectors for that column. Entries in the test and training sets are encoded into the nearest step, so this statement defines the accuracy possible. Codings may also be read from a file using the "loading code from" statement. If this is specified, coding and quantization statements are ignored, and lf will warn the user. Note that codings must be specified by a "read coding from" statement, or combinations of coding and quantization statements. Codings can be saved to a file with the "save coding to" statement, which may be placed anywhere in the function section. The training set statement defines the actual function to be learned by the system. An entry in a table can be either a real number or an integer. If the width of the a column (as specified by the coding) is 1, then that column is boolean. For boolean columns, zero values are FALSE, and any non-zero value is considered TRUE. The test set statement defines the test that is run on the trees at the end of training to see how well the learned function performs. Like the training set, reals or integers are acceptable. After lf has executed, it produces a table of output showing how each element in the test set was quantized, and the value the trained tree returned. Consider the following results that multiply.lf produced. Note that the quantization level is one less than the number represented. This is because the range of numbers is from 1 to 144, and 0 corresponds to the first quantization level. 1 ..... 3.000000 2 11.000000 10 33.000000 32 33.000000 32 3.000000 2 12.000000 11 36.000000 35 36.000000 35 4.000000 3 1.000000 0 4.000000 3 4.000000 3 4.000000 3 2.000000 1 8.000000 7 8.000000 7 4.000000 3 3.000000 2 12.000000 11 12.000000 11 ..... Each column consists of two numbers, the entry specified by the user, and an integer describing the quantization level it was coded into. The fourth column is the result produced by the trained tree. It shows the quantization level produced (the second figure) and how this may be interpreted in the space of the codomain (the first figure). 6.2 sphere.lf This lf example uses a spherical harmonic function Y2 defined by: Y2(æ, í) = A0(3æý/2 - 1/2) + 3æ(1 - æý)^« [A1 cos í + B1 sin í] + 3(1 - æý) [A2 cos 2í + B2 sin 2í] where A0 = 1.0, A1 = 0.4, B1 = 0.9, A2 = 2.4, B2 = 7.9. The values of æ were in the interval [0.0, 1.0], and the values of í were in [0.0, ã]. The values of Y2 range between -26.0 and 26.0. The æ and í intervals were quantized into 100 levels each; the random walks had 64 bits and a stepsize of 3. The Y2 values were quantized into 100 levels, the random walk having 64 bits with a stepsize of 3. Training 64 networks of 8191 elements on 1000 samples resulted in a function which, during test on 1000 new samples, was decoded to the correct quantization level, plus or minus three, 88.6\% of the time. The error in the quantized result was no more than nine quantization levels for all of the test samples. (A slightly better learning algorithm got within three levels 95.8\% of the time, and was always within eight levels.) The function section introduces the optional "largest" and "smallest" statements. These may be used if the user needs to explicitly define the largest and smallest values in the test and training sets. If they are missing, lf will just use the largest and smallest values for each column in both the test and training sets. This problem takes about 80 minutes of CPU time on a Sun Sparcstation 1. We have included a sample set of results in the file sphere.out. You will need to have at least 12Mb of RAM (either real or virtual) to run this problem! 5.3 The Syntax of lf The syntax has been defined using YACC. Tokens have been written in quotes to distinguish them. Note that the following tokens are synonyms :- dimension, dimensions max, maximum min, minimum The syntax is defined as follows :- program : function_spec tree_spec | tree_spec function_spec function_spec : "function" dim codim function_statements dim : "domain dimension =" integer codim: /* empty */ | "codomain dimension =" integer function_statements : function_statement | function_statements function_statement function_statement : quantization | coding | coding_io | train_table_size | train_table | test_table_size | test_table | largest | smallest quantization : "quantization =" quant_list quant_list : integer | quant_list integer coding : "coding =" code_list code_list : integer ":" integer | code_list integer ":" integer coding_io: "save coding to" string | "load coding from" string train_table_size : "training set size =" integer train_table : "training set =" table test_table_size : "test set size =" integer test_table : "test set =" table table : num | table num num : real | integer largest : "largest =" largest_list largest_list : num | largest_list num smallest : "smallest =" smallest_list smallest_list : num | smallest_list num tree_spec : "tree" tree_statements tree_statements : tree_statement | tree_statements tree_statement tree_statement : tree_size | tree_io | min_correct | max_correct | max_epochs tree_size : "size =" integer tree_io: "save tree to" string | "save folded tree to" string | "load tree from" string max_correct : "min correct =" integer max_epochs : "max epochs =" integer 7 Other Demonstrations In this section we briefly present some boolean function problems which atrees have solved. 7.1 The Multiplexor Problem A multiplexor is a digital logic circuit which behaves as follows: there are k input leads called control leads, and 2k leads called the "other" input leads. If the input signals on the k control leads represent the number j in binary arithmetic, then the output of the circuit is defined to be equal to the value of the input signal on the jth one of the other leads (in some fixed order). A multiplexor is thus a boolean function of n = k + 2k variables and is often referred to as an n-multiplexor. Here is a program to define a multiplexor with three control leads, v[2], v[1] and v[0], the fact that they are these particular variables being irrelevant due to randomization in the programs: /* Windows window procedure and initialization omitted for clarity */ /* An eleven input multiplexor function test */ #include #include #include #include "atree.h" #define TRAINSETSIZE 2000 #define WIDTH 11 #define TESTSETSIZE 1000 #define TREESIZE 2047 char multiplexor(v) char *v; { return(v[ v[2]*4 + v[1]*2 + v[0] + 3]); } main(hInstance) HANDLE hInstance; { int i; int j; LPBIT_VEC training_set; LPBIT_VEC icres; LPBIT_VEC test; char vec[WIDTH]; char ui[1]; int correct = 0; LPATREE tree; char szBuffer[80]; /* Initialise */ training_set = (LPBIT_VEC) Malloc (TRAINSETSIZE * sizeof(bit_vec)); MEMCHECK(training_set); icres = (LPBIT_VEC) Malloc (TRAINSETSIZE * sizeof(bit_vec)); MEMCHECK(icres); atree_init(hInstance); /* Create the test data */ MessageBox(NULL, "Creating training data", "Multiplexor", MB_OK); for (i = 0; i < TRAINSETSIZE; i++) { for (j = 0; j < WIDTH; j++) { vec[j] = RANDOM(2); } training_set[i] = *(bv_pack(vec,WIDTH)); ui[0] = multiplexor(vec); icres[i] = *(bv_pack(ui,1)); } /* Create a tree and train it */ MessageBox(NULL,"Training tree", "Multiplexor", MB_OK); tree = atree_create(WIDTH,TREESIZE); (void) atree_train(tree,training_set,icres,0,TRAINSETSIZE, TRAINSETSIZE-1,100,1); /* Test the trained tree */ MessageBox(NULL,"Testing the tree", "Multiplexor", MB_OK); for (i = 0; i < TESTSETSIZE; i++) { for (j = 0; j < WIDTH; j++) { vec[j] = RANDOM(2); } test = bv_pack(vec,WIDTH); if (atree_eval(tree,test) == multiplexor(vec)) { correct++; } bv_free(test); } wsprintf(szBuff,"%d correct out of %d in final test",correct,TESTSETSIZE); /* discard training set */ for (i = 0; i < TESTSETSIZE; i++) { Free(training_set[i].bv); Free(icres[i].bv); } Free(training_set); Free(icres); /* Discard tree */ atree_free(tree); return; } This problem was solved to produce a circuit testing correctly on 99.4% of 1000 test vectors in 19 epochs, or about 530 seconds on a Sun 3/50. The time may vary considerably depending on the random numbers used. It is possible to learn multiplexors with twenty inputs (four control leads) with a straightforward but improved adaptation procedure, and multiplexors with up to 521 leads (nine of them control leads) using much more elaborate procedures which change the tree structure during learning [Arms5]. 7.2 The Mosquito Problem Suppose we are conducting medical research on malaria, and we don't know yet that malaria is caused by the bite of an anopheles mosquito, unless the person is taking quinine (in Gin and Tonics, say) or has sickle-cell anaemia. We are inquiring into eighty boolean-valued factors of which "bitten by anopheles mosquito", "drinks Gin and Tonics", and "has sickle-cell anaemia" are just three. For each of 500 persons in the sample, we also determine whether or not the person has malaria, represented by another boolean value, and we train a network on that data. We then test the learned function to see if it can predict, for a separately-chosen test set, whether person whose data were not used in training has malaria. Suppose on the test set, the result is 100% correct. (Training and test can be done in about five seconds on a Sun Sparcstation 1.) Then it would be reasonable to analyze the function produced by the tree, and note all the variables among the eighty that are not involved in producing the result. A complete data analysis system would have means of eliminating subtrees "cut off" by LEFT or RIGHT functions (such as atree_compress()), to produce a simple function which would help the researcher understand some factors important for the presence of the disease. If there were extraneous variables still left in the function in one trial, perhaps they would not show up in a second trial, so that one could see what variables are consistently important in drawing conclusions about malaria. We apologize for the simplistic example, however we feel the technique of data analysis using these trees may be successful in cases where there are complex interactions among features which tend to mask the true aetiology of the disease. The code for the problem can be found in mosquito.c. 8 References [Arms] W. W. Armstrong, J. Gecsei: Adaptation Algorithms for Binary Tree Networks, IEEE Trans. on Systems, Man and Cybernetics, SMC-9 (1979), pp. 276 - 285. [Arms2] W. W. Armstrong, Adaptive Boolean Logic Element, U. S. Patent 3,934,231, Jan. 20, 1976, assigned to Dendronic Decisions Limited. [Arms3] W. W. Armstrong, J. Gecsei, Architecture of a Tree-Based Image Processor, 12th Asilomar Conf. on Circuits, Systems and Computers, IEEE Cat. No. 78CHI369-8 C/CAS/CS Nov. 1978, 345-349. [Arms4] W. W. Armstrong, G. Godbout, Properties of binary trees of flexible elements useful in pattern recognition, Proc. IEEE Int'l. Conf. on Cybernetics and Society, San Francisco (1975) 447 - 450. [Arms5] W. W. Armstrong, Jiandong Liang, Dekang Lin, Scott Reynolds, Experiments using Parsimonious Adaptive Logic, Technical Report TR 90-30, Department of Computing Science, University of Alberta, September 1990. [Boch] G. v. Bochmann, W. W. Armstrong: Properties of Boolean Functions with a Tree Decomposition, BIT 14 (1974), pp. 1 - 13. [Hech] Robert Hecht-Nielsen, Neurocomputing, Addison-Wesley, 1990. [Meis] William S. Meisel, Parsimony in Neural Networks, Proc. IJCNN-90-WASH-DC, vol. I, pp. 443 - 446. [Rume] D. E. Rumelhart and J. L. McClelland: Parallel Distributed Processing, vols. 1&2, MIT Press, Cambridge, Mass. (1986). [Smit] Derek Smith, Paul Stanford: A Random Walk in Hamming Space, Proc. Int. Joint Conf. on Neural Networks, San Diego, vol. 2 (1990) 465 - 470.