A Comparison of Concept Identification in Human Learning and Network Learning with the Generalized Delta Rule

Introduction

The generalized delta rule for network learning has received a great deal of attention recently. The generalized delta rule is a learning procedure for associative networks which contain hidden units. It is a significant advance over previous network learning procedures which either (1) were limited to two-layer networks (23) which are incapable of solving a number of interesting problems (12), or (2) required stochastic units [9) and a large amount of computation for each learning cycle.

Figure 1 presents a simple network with two input units, three hidden units, and one output unit. For each unit j in a network, the output o Pi given an input pattern p is:

where w .. is the weight from unit ito j and e. is a ,hreshok:l" for unit p J j.

A Comparison of Concept Identification in Human Learning and Network Learning with the Generalized Delta Rule

Michael Pazzani The Aerospace Corporation P.O.Box 92957 Los Angeles, CA 90009 and UCLA AI Laboratory Michael Dyer UCLA AI Laboratory 3531 Boelter Hall Los Angeles, CA 90024

The generalized delta rule indicates how the weight wii on the connection from unit i to unit j should be changed after presentation of an input pattern p :

where 11 is a parameter which controls the learning rate; 1 . is the target output for unit j with input pattern p; S k is tlf~ error propagated back to unitj from a unit k whose inpu{is oi; and wki is the weight of the connection from unit j to unit k. The interested reader is referred to (16) for a derivation of the generalized delta rule.

· The concept identification task (3) has been extensively studied in psychology. In this paper, we review a number of findings on concept identification in human subjects, and compare these findings to network learning with the generalized delta rule. In a typical concept identification experiment, a subject is shown a set of cards with different objects on them. The cards are presented to the subject one at a time in a random order and the 'SUbject is to determine whether the card belongs to the class to be learned. After each presentation, the subject is given feedback on the correctness of his response. Typically, the subject is told which attributes of the objects on the card (e.g., the number of objects, the shape of the objects, and the color of the objects) are potentially relevant. The trials continue until the subject makes no errors.

The concept identification task seems ideal for network learning. The attributes on the card are treated as input to the network. In most of the experiments, the attributes are two valued, so a binary encoding of the input is possible (e.g., for shape 1 =square and 0 =circle). The output of the network is 1 if the card is an instance of the concept and 0 otherwise. After the network classifies an input pattern, it is given feedback on the correctness of its output so that the weights on connections between units can be modified.

For all of the simulations, the network learning algorithm is simulated on a Symbolics 3600. To ensure that the algorithm has been correctly implemented, we have run it on many of the examples in (16) and obtained similar results.

The issue addressed in this paper is an evaluation of what might be called the strong PDP hypothesis: that all cognitive processes are realized directly in a homogeneous network of connected units. This hypothesis has been entertained by Churchland (5). At the other extreme Is the physical symbol system hypothesis [14): that all cognitive processes are symbolic manipulations of the sort in logic and lisp.

The most fundamental contribution so far of artfficial intelligence and computer science to this joint enterprise has been the notion of a physical symbol system. This concept of a broad class of systems that is capable of having and manipulating symbols, yet is also realizable w~hin our physical universe, has emerged from our growing experienoe and analysis of the oomputer and how to program It to perform intellectual and perceptual tasks. The notion of symbol that It defines is Internal to this oonc:ept of a system. Thus, M Is a hypothesis that these symbols are in fact the ssme symbols that we humans have and use everyday of our lives. Stated another way, the hypothesis is that humans are lnstanoea of physical symbol systems. (14)

In between these two extremes, there are a number of possible hypotheses. After presenting the results of our simulations, we shall comment on other alternative hypotheses.

Relative ease of concept Identification

There have been a large number of experiments investigating the ease of learning combination of attributes. For example, Bower and Trabasso (2) have reported that concept Identification by a single affirmative attribute (e.g., blue) is easier than concept Identification on a conjunction of cues (e.g., blue and square). Others [3) have found that conjunctive concepts are easier than disjunctive concepts (e.g., blue or square) and that disjunctive concepts are easier than exclusive disjunctive concepts (e.g., blue or square but not blue and square) (22). Finally, polymorphous concepts, also called m-out-of-n, (e.g., at least two of square, blue and symmetric) have been found to be more difficult than disjunctive concepts [7]. To our knowledge, there has been no comparison of polymorphous and exclusive disjunctive concepts; both are more difficult than disjunctive. Figure 2 summarizes the relative ease of acquiring concepts.

Figure 2: Relative ease of concept Identification, as determined by the number of trials required to learn the concept

We tested the generalized delta rule in a large number of different networks and conditions. In all of the tests, there were three input units, one output unit, and a number of hidden units connected to the output unit. The following parameters were varied in the trials:

• Number of hidden units: two, eight, and twenty-four.
• Connections between units: For all of the tests each input unit was connected to every hidden unit. In addition, in the case of the twenty-four hidden unit test, random connections between the input and hidden units were tested.
• The value of 11: varied from .1 to .8 in increments of .1.

The weights W·k were set to random numbers between -5.5 and 5.5. The thres~ld a 1 of the hidden units were also set to random values between -5.5 and 5.5 subject to the constraint that the output was never more than than .995 or less than .005 for any input combination. 1 An output value of greater than .85 was considered to be 1, and less than .15 was considered to be 0. For each condition, five concepts corresponding to one of the classes of concepts were learned from 1 000 random initial conditions and the number of presentations of each input pattern was recorded.

In the conditions tested, the number of hidden units and the value of 11 did not affect the relative ordering of the ease of concept Identification considerably. Results from several simulations are shown in Figure 3. For all of the simulations, if the network failed to · learn after 5000 presentations of each input pattern, the simulation was terminated.

1 The rationale lor constraining the tlvvlhold value was ID lnaeaae the rate of learning. From the generslized delta rule, k Is easy to - thst leaming Ia slowest when the output approaches 0 or 1.

; 1l:

There are several conclusions which can be drawn from this simulation.

• Affirmation is always easier than other classes of concepts (p < .001). This result is identical to the result with human subjects.
• Usually, there is no significant difference between conjunctive disjunctive, and polymorphous concepts.2 This result differs from the findings on human subjects (22). A bit of analysis Indicates why conjunction and disjunction are equally difficult, since by Interchanging 1 's and O's the disjunction becomes conjunction (i.e., in digital circuits, an or-gate in positive logic is an and-gate in negative logic). Bruner [3) has argued that disjunction is more difficult for human subjects because they find it more difficult to work with negative Instances. The generalized delta rule does not share this difficulty.
• Exclusive disjunctions were always significantly (p < .001) more difficult than disjunctions. This result Is Identical to the result with roman subjects. ·
• The average number of presentations required for learning in all conditions Is much greater than that required by roman subjects. For example, In (7], with three two-valued attributes the mean number of cards presented was nine for conjunctive, twenty-eight for disjunCtive, and forty for polymorphous concepts. Note that in Figure 3, the results are reported in decks of cards (i.e., presentations of all eight input patterns). The results in Figure 3 must iJe multiplied by eight before being compared to human performance on this task.

Redundant relevant cues

Bower and Trabasso have extensively Investigated concept ldentHication when there are redundant attributes (2]. For example, if two attributes always vary together, (I.e, squares are always bh.Je, and blue things are always squares), then roman subjects fall into three classes: those that use one of the relevant attributes (e.g., blue), those that use the other relevant attribute (e.g., square) and those that use both (2). Since Bower and Trabasso were primarily concerned with determining whether or not subjects attended to both attributes, they group together those . subjects who conjunctively and disjunctively combined the redundant attributes.

Encouraged by the results in the earlier simulation where the value of 11 did not alter the result, In these simulations we did not vary the value of 11 (.25). We simulated networks with 8 and 1 hidden unit(s)s. In this simulation there were three Input attributes, x,y and :. 4 The value of z was always the same as the value of x. Presentation of the four Input patterns were repeated until the network would respond with 1 when x (and, therefore, z) was 1 and with 0 otherwise. After the network had learned this concept, It was presented with all eight possible Input patterns. The output value of the network determined what function It had learned. For example, If the network reported 1 only when x was 1, then It had learned that x was the relevant attrblte.

2AJthough with twenty-four hidden unill and 11· .6, conjunction wu aignificantly (p <.05) more difficult than disjunction and polymorphy.

~ networi(a generalize better with fewer hidden unka. If there a large num_ber of hidden unill, there can be one hidden unit unit whk:h "'ooks lor" each pos11ble input combination.

In this simulation, for some Input patterns which were never seen the output value might not be greater than .85 (which we consider 1) or less than .15 which we consider 0. In their simulations on generalization, Rumelhart, Hinton, and Williams (16) accept a value of greater than or equal to .5 for 1, and less then .5 for 0. We also adopted this strategy. The results of these simulations are In Figure 4.

There are sixteen possible boolean functions consistent with the four Input patterns which were presented. 01 these, human subjects only report the first four z, x, xz and xvz In Figure 4. In human subjects, the attribute which Is not at all correlated with the output (y) Is not considered relevant. The exact dlstrbltlon among the four functions depends on a number factors such as the saliency of the cues. In the Trabasso and Bower experiment, 34% classified on one attribute, 51% classlffed on another, and 15% classified on both attributes. In network learning with eight hidden units, the rule learned to classify the concept contains the irrelevant attribute (y) slightly more than 50% of the time. With just one hidden unit, the irrelevant attribute was included more than 25% of the time.

The results of this simulation question the ability of the generalized delta rule to arrive at a reasonable generalization when some input configurations have not presented. The concept descriptions of human subjects in the redundant relevant cue experiments are simpler than those which are learned by the generalized delta rule. Occam's razor favors a simpler hypothesis over a more complex hypothesis when both are consistent with the data. Note that "simpler- Is defined symbolically. A distributed network which computes x is just a complex as one that computes xzvx'jv'Jz.

4 1n ., experiment with human IUbjecll, " might repNeent lhtlpe with 0 · &qU8AI .net 1 · circle, '1 might repNeent color with 0 · red and 1 · blue, and r might repN18nt llze with 0 · big and 1 · 111181.

In the psychology literature, the models of the concept Identification task (e.g., (2, 11)) are consistent with the physical symbol system hypothesis. These models postulate that subjects generate a potential concept description in an an-or-none fashion and then confirm (or reject) the potential concept description with future examples. When learning simple affirmative concepts, in · which only one attribute is relevant (i.e., discrimination learning) the pattern of performance remains at chance for a period of time and then suddenly jumps to perfect (20). These results are in contrast with the strong PDP hypothesis.

Some have criticized the concept identification task because the categories learned are artificial (17]. Many natural categories such as ·games" do not appear to have a set of necessary and sufficient features. Instead, It is argued (24) that many concepts are polymorphous. One encouraging result of our simulation is that the polymorphous concepts are no harder for the generalized delta rule to learn than conjunctive or disjunctive concepts. 5 However, a full model of concept Identification should be able to account for the acquisition of simple concepts like "square" whiCh have necessery and sufficient features.

Others have criticized the concept Identification task because the learning takes place in an artificial environment without regard to the Ieamer's goals or prior knowledge (13, 10). For example, consider the following more realistic redundant relevant cue experiment. Someone familiar with many sports but who ha8 never seen a game of basketball notices that there ara five players with green shirts, blond hair, and various color sneakers. When one of these players has the ball, all the players run to one end of the court. Five other players have yellow shirts, black hair, and various color sneakers. When one of these players has the ball, everyone runs to the other end of the court. 8 Two opposing players collide, and are Injured. Two replacements come in, one with a green shirt and black hair, the other with a yellow shirt and blond hair. The new player with the green shirt and black hair gets the bali. To which end will everyone run? An intelligent person would use his prior knowledge of sports (I.e., players on the same team wear the same color uniform) to determine that shirt color is relevant and hair color Is not relevant and make the correct prediction. This is in sharp contrast to an artificial situation In which a Ieamer must decide whether the color or the size of a rectangle is relevant. However, the nature of the concept Identification task makes no difference to the networks we have been simulating. One way to bias the saliency of attributes in network learning Is to set the initial weights differently (e.g., shirt color Is Initially stronger than hair color) . However, a simple bias would not suffice for all problems. To see this, consider the following different task: One of the players with the green shirt and blond hair also endorses hair products. He is arrested on drug charges and the company decides to find another basketball player to represent their products. in this situation, hair color may be more Important than uniform color. Instead of always favoring one attnbute over another, a more complex process is required which takes Into account the goals of the Ieamer.

In our simulations, network learning with the generalized delta rule failed to exhibit a number of similarities with human learning on a number of concept Identification tasks. This Is In contrast with the results of network learning on other tasks, such as classical conditioning in animals (1] and human skill learning (6]. Models such as these seem to weaken support for the strongest version of the physical symbol system hypothesis.

~. it lhould be noted that the results on the relalive - of concept ldentiftcatlon UIIMIMI filii the Ieamer hu no prior knowledge. A theoly wlidl explain· a parllcul.- oomblnallon of te-. lacilltaln leaning. Far example, wl*l cauul explanatlona - preMnt, "'-1y aepara* ca~ are ...- II) learn flail nonlne.ty aepatllble catgoriel. The ,._ Ia ""' wl*l the!e Ia no explanation [13]. It Ia not cle· how the· reiUita could be modaled dlrec:lly In network ~ II) ~ learning, Iince the genel'llllzed delta nAil II not aflec:ted by the ability 10 oonatruct a cauaale)Cj)lanation.

'some may raoognlze thll ·· a l..alwra-Celllcl game.

Conclusion

Human learning is a very complex process and it is not clear that any single rule or strategy can account for all human learning (15]. Tulving [21] has distinguished three types of human memory, each with its own type of learning (following Rumelhart and Norman (15]) and retrieval:

• In procedural memory, which retains connections between stimuli and responses, the learning mechanism is tuning. Retrieval from procedural memory is by performing (i.e., acting or perceiving) .
• In semantic memory, which represents knowledge of the world, the learning mechanism is called restructuring. Retrieval from semantic memory is called knowing.
• In episodic memory, which represents knowledge about personally experienced events, the learning mechanism is termed accretion. Retrieval from episodic memory Is called remembering.

The generalized delta rule seems to correspond most directly with tuning. Indeed, it has been most successful at simulating the learning of those activities of humans and animals which improve gradually over time.

We conclude that although (1) manipulating symbolic representation is not a necessary condition for intelligent behavior (8], and (2) the symbolic level is not the best level of description for some intelligent behaviors, the symbolic level is the appropriate level of description of other human behaviors. For example, in the redundant relevant cue experiment, human subjects consistently generate concept definitions which are simpler symbolically. There are two possible ways of unifying these different levels of description within the parallel distributed processing framework:

1. Look for network architectures which implement "virtual machines" which manipulate symbols (18, 19]. This approach ackowledges that humans have "connectionist" hardware, but admits that (at least by adulthood) humans have built up some capabilities which are better characterized at the symbolic level.
2. Look for network architectures and learning rules which explain intelligent behaviors without reference to symbols (4]. For example, it is possible that such an architecture can follow Occam's razor without explicitly representing hypotheses as symbols and Occam's razor as a rule.