Network Learning on the Connection Machine

1 Introduction

Massively parallel, connectionist networks have undergone a re­ discovery in artificial intelligence and cognitive science, and have already lead to broad application in many areas of artificial in­ telligence and cognitive simulation, including knowledge repre­ sentation in semantic networks [8], speech recognition [4,17], di­ mensionality reduction [12,18], and backgammon [16]. However, connectionist networks are computationally intensive, and days or weeks are often required to train even moderate-sized networks using the fastest serial computers; The exploration of large net­ works consisting of more than a million links or connections is barely feasible given current technology.

One option being explored is the development of special-purpose hardware using VLSI technology [15,5,1] . Initial estimates of these so-called neuromorphic systems indicate that tremendous speed-up may be achievable, perhaps up to five to six orders of magnitude over a VAX780 implementation. However, one prob­ lem with special purpose hardware is that it does not allow one to explore different patterns of connectivity and different learning algorithms. Although neuromorphic systems will certainly have an important impact on the field, they may be limited as research tools.

A more flexible alternative is seen in the development of gen­ eral purpose, fine-grained, parallel computers. The Connection Machine (CM} is a massively parallel computer consisting of up to 65,536 (2 16 ) one-bit proceasors arranged in a hypercube ar­ chitecture [7]. In this paper we discuss the implementation of a connectionist network learning algorithm, back-propagation [11],

1 Thia r-rch waa aupported by Thinking Machinea Corporation, Cam­ bridge, Mau. The authora wiah to thank Terry Sejnowaki, David Walts, and Craig Stanfill for their aaaiatance.

Network Learning on the Connection Machine 1

Guy Blelloch M.I.T Artificial Intelligence Laboratory 545 Technology Square Cambridge, Massachusetts 02139

Charles R. Rosenberg Cognitive Science Laboratory Princeton University Princeton, New Jersey 08542

on the Connection Machine. Currently, the Connection Machine offers a factor of 500 speedup over a previous implementation on a V AX780 and a factor of two speed-up over an implementation of a similar network on a Cray-2. Considering that parallel com- ' puting is only in it's infancy, we expect the speed-up to be much greater in the near future. Finally, we present an application in the domain of speech synthesis, called NETtalk [14], that uses our implementation of back-propagation on the Connection Machine.

2 Error Back-Propagation

Connectionist network models are dynamic systems composed of a large number of simple processing units connected via weighted links, where the state of any unit in the network depends on the states of the units to which this unit connects. The values of the links or connections determine how one unit affects another; The overall behavior of the system is modified by adjusting the values of these connections through the repeated application of a learning rule.

The back-propagation learning algorithm is an error-correcting learning procedure for multilayered network architectures. Infor­ mation flows forward through the network from the input layer, through the intermediate, or hidden layer(s), to the output layer. The value of a unit is determined by first computing the weighted sum of the values of the units connected to this unit and then ap­ plying the logistic function; I+!-., to the result. This forward propagation rule is recursively applied to successively determine the unit values for each. layer.

The goal of the learning procedure is to minimize the aver­ age squared error between the values of the output unit!! and the correct pattern provided by a teacher. This is accomplished by first computing the error gradient for each unit on the output layer, which is proportional to the difference between the target value and the current output value. The error gradient is then recursively determined for layers from the output layer to the in­ put, by computing the weighted sum of the errors at the previous layer. These error gradients, or deltas, are then used to update the weights 2 ·

Computationally the forward and backward propagation steps are very similar. Forward propagation consists offour basic steps: distributing the activation values of the units to theil' respective fan-out weights, multiplying the activations by the weight val­ ues, summing these values from the weights into the next layer of units, and applying the logistic function to this value. The back­ ward propagation of error consists of four similar steps: distribut­ ing the error values of the units to their respective fan-in weights, multiplying the error by the weight values, summing these values from the weights into the previous layer of units, and evaluating the derivative of the logistic function. In addition to forward and backward propagation, the inputs and outputs mU:at be clamped to the appropriate values. In the next section, we will show how each of these steps is executed on the Connection Machine.

2 The original aource ahould be consulted for the detaU. of back­ propagation.

3 The Connection Machine

The Connection Machine is a highly parallel computer with b~ tween 16,384 and 65,536 procenora. Each proceaaor has two singl~bit arithmetic logic units (ALUe), and some local mem· ory - currently 64K bits. In addition, every 32 proceaaors shares a floating point unit. All the proceaaore are controlled by a sin­ gle instruction stream (SIMD) broadcast from a microcontroller. Figure 1 shows a block diagram of the Connection Machine. Pro­ cenors can communicate using a few different techniques - the only two of concern in this paper are the router and the ·con operations. The router operations allow any proceaaor to write into the memory or read from the memory of any other procenor. The ScGn operations allow a quick 8 summation of many values from different procenors into a single procenor, or the copying of a single value to many procenors (3).

In the implementation of back-propagation, we allocate one proceaaor for each unit and two procenors for each weight· . The proceaaor for each unit is immediately followed by all the pro­ eenora for it's outgoing, or fan-out, weights, and immediately preceded by all of it's incoming, or fan-in, weights (see Figure 2). The beginning and ending of these contiguous segments of pro­ ceeeora are marked by flags. A 1con operation called segmented co~r-·con ia used to quickly copy a value from the beginning or end of a segment of contiguous procenora to all the other proces­ sors in the segment and an operation called segmented plu1-scon is used to quickly sum all the values in a segment of processors and leave the result in either the first or last procenor of the segment. Thus our layout enables us to use the scan operations to distribute the unit values from the units to their output links and to sum the values from their input links.

1 Uaually falter than a router cycle.

The forward propagation step proceeds as follows. Firat, the activations of the input units are clamped according to the in­ put text. The algorithm then distributes the activations to the weights using a copr-·con operation (step A in Figure 3), and then all weights multiply their weight by these activations. The result is sent from the output weights to the input weights of the unit in the next layer (step B) using the router. A plus-scon then sums these input values into the next layer of units (step C), and the lol1tic function is applied to the result at all the unit proces­ sors to determine the unit activations. This forward propagation step must be applied once for each layer of Iinke in the network.

Once forward-propagation is completed, we determined the error at the output layer, and propagate this error backward. This error. back-propagation consists of running copr-·cGn backwards, copymg the deltas from the output units into their input weights, then sending the deltas from the input weights to the output weights of the unite at the previous layer. The deltas can then be multiplied by the weight values, and summed in the reverse direction into the units at the previous layer. The derivative of the logistic function is then evaluated to determine the error of units at the previous layer. As in forward propagation, this step must be applied once for each layer of links.

The algorithm as deacribed so far uses the processors ineffi­ ciently for two reasons. Firstly, we use two procenors for each weight when only one of them is busy at a time, and secondly, when we are running one layer, the proce880rs for all the other layers are idle. To overcome the first inefficiency and use one processer per weight, we overlap the input and output weights. We alec overlap the unite with the weights. To overcome the second problem and keep the processors for each layer busy we pipeline the layers as follows. Given a set of n input vectors 111 (0 ~ i < n), and m layers 1;, pipelining consists of propagating the i 1 " input vector across the first layer, while propagating the previous input vector (111-1) acrou the second layer, tli-3 acrou the third layer, ... , and tli-m acrou the last layer. We also interleave the back­ propagation with the forward-propagation so that immediately after presenting 111 to the input, we start back-propagation 111-m backward from the output. The depth of the whole pipe for m layers is 2m.

·Later In thla paper we wlllahow how the proceuon can be ahared between unit· and welchta, requlrln& only one proceuor per weight.

This implementation has some important advantages over other possible implementations. Firstly, with pipelining, the implemen­ tation unwraps all the potential concurrency. 5 Since it is pouible to simulate a concurrent computer with a serial computer but the opposite is not true, our method can be used efficiently on any machine ranging from a completely serial computer to a very fine grained parallel computer. If we did not expose all the con­ currency, we would not utilize as many processors in a very fine grained computer. Secondly, the implementation works well with sparse connectivity. Methods based on dense matrix multiplies, such as some of the serial implementations, although faster for dense connectivity, are extremely inefficient with sparse connec­ tivity. Thirdly, in our implementation, all proceseors are kept active even if different units have different fan-ins. This would not be true if we used one processor per unit and serially looped over the fan-ins of each unit - as one might be tempted to do in a more coarse grained parallel computer. Lastly, the time taken by each step i8 independent of the largest fan-in.

Networks with more links than physical processors can be simulated in the Connection Machine using an abstraction called the virtual proce1sor (VP) [7] . A virtual proce11or is a slice of memory within a physical processor. Many such VPs can exist within each physical proceBSOr. Looping over the VPs in general causes a linear slow-down.

Similar layouts of static networks have been used to imple­ menta rule based system [2], a SPICE circuit simulator and a maximum-flow algorithm.

4 CM-NETtalk

NETtalk is a connectionist network that uses back-propagation to learn the pronunciations of English words. We have implemented NETtalk on the Connection Machine, and present the results of our implementation here 8 ·

NETtalk is is composed of three layers of unite, an input layer, an output layer, and an intermediate or hidden layer. Each unit in each layer is connected to each unit in the layer immediately above and/or below it. The representations at the input and output layers are fixed to be representations of letters and phonemes respectively. The representation at the hidden layer, on the other hand, is constructed automatically by back-propagation.

NETtalk uses a fixed-size input window of seven letters to allow the textual context of three letters on either side of the current letter to be taken ac~ount in the determination of that letter's pronunciation (see Figure 4) . This window is progres­ sively stepped through the text. At each step, the output of the network generates its guese for the pronunciation of the middle, or fourth, letter of the sequence of letters currently within the input window. This guese is compared to the correct pronuncia­ tion, and the values of the weights are iteratively adjusted using back-propagation to minimize this difference. Good pronuncia­ tions (95% of the phonemes correct) of a thousand-word corpus of high-frequency words are typically achieved after ten passes through the corpus.

6 This is not strictly true aince we could get &nother factor of 2 by running the forward and backward propagation concurrently.

"Interested readers should consult the original aourcea for detalla.

We have experimented with a network consisting of 203 input units (71etters with 29 units each), 60 hidden units and 26 output unite. This required a total of 13826links (processors) -12180 in the first layer, 1560 in the second layer and 76 to the true units 7 · The learning rate was approximately the same as that achieved by a C implementation on various serial machines.

In the current implementation, using a 16,384 processor ma­ chine, the time required for each letter during the learning stage was 5 milliseconds. This includes the forward propagation, the backward propagation, the time necessary to clamp the input and output, and the time required to calculate the error. The time is broken up by the type of operation as follows:

• Scanning 30% -This includes two segmented plus-scans and two segmented copll··can·.
• Routing 40%- This includes two routing cycles.
• Arithmetic 20% -This includes seven multiplies and several additions, subtracti9ns and comparisons.
• Clamping 5% - This is the time needed to get the characters to the input unite and the expected phonemes to the output unite.
• Other 5% - Mostly for mo~ing values around.

With improvements in the coding of the implementation and in microcode, we expect that this time could be improved by a factor of three or more.

Table 5 shows comparative running times of the error back­ propagation algorithm for several machines. On an existing im­ plementation of back-propagation on a VAX 780, the same net­ work required 650 microseconds per letter. This represents a 130 to 1 improvement in speed. On a 64K machine and larger net­ works, we could get a 500 to 1 improvement. This is about twice the speed of an implementation of the algorithm on a Cray-2, yet a Connection Machine costs a quarter of the price. Fanty [6] has implemented a connectionist network using the BBN Butterfly, a coarse grained parallel computer with up to 128 processors, but because the type of networks he used were considerably different, we cannot compare the performances.

1 True unlta &re unlta th&t &re &!ways kept In the activo state. Their function Ia to allow the threaholds of the other unih In the network to be modl!led In a almple way.

Using virtual processors, on the Connection Machine it is pos­ sible to simulate up to 16 million links in physical memory. With software currently being developed to use the Connection Ma­ chine's disks, the CM will be able to simulate many more than this.

5 Conclusions

We have discussed the first implementation of a connectionist learning network on a fine-grained parallel machine. Our ex­ periments indicate that the Connection Machine can currently simulate rather large networks of over 65 thousand connections at speed over twice as fast as the most powerful serial machines such as the Cray-2. The method outlined here should general­ ize to any highly concurrent computer with a routing network and, with small modifications, can be used with many variations of connectionist network. Unlike neuromorphic, hardware-based systems, our method places no restrictions on the computations performed at the links or the units, nor on the topology of the network.

In our implementation we were able to keep all of the pro­ cessors busy most of the time using a single instruction stream; multiple instruction streams do not seem to be necessary. Rather, communication was the bottleneck- at least on the current Con­ nection Machine. Effort needs to be spent designing faster routing networks.

The lack of computational power was a major factor in the dissolution of the first wave of connectionism in the 1950's and 60's. Alternative, symbolic techniques were more successful in part because they better fit the computational resource available at the time. With the advent of fine-grained parallel computers, this situation is beginning to change; the exploration of large-scale connectionist networks is starting to become computationally fea­ sible.