From simple associations to systematic reasoning: A connectionist representation of rules, variables and dynamic bindings using temporal synchrony

BEHAVIORAL AND BRAIN SCIENCES (1993) 16, 417-494

(Abstract and Section 1.)

Abstract: Human agents draw a variety of inferences effortlessly, spontaneously, and with remarkable efficiency -- as though these inferences were a reflexive response of their cognitive apparatus. Furthermore, these inferences are drawn with reference to a large body of background knowledge. This remarkable human ability seems paradoxical given the complexity of reasoning reported by researchers in artificial intelligence. It also poses a challenge for cognitive science and computational neuroscience: How can a system of simple and slow neuronlike elements represent a large body of systemic knowledge and perform a range of inferences with such speed? We describe a computational model that takes a step toward addressing the cognitive science challenge and resolving the artificial intelligence paradox. We show how a connectionist network can encode millions of facts and rules involving n-ary predicates and variables and perform a class of inferences in a few hundred milliseconds. Efficient reasoning requires the rapid representation and propagation of dynamic bindings. Our model (which we refer to as SHRUTI) achieves this by representing (1) dynamic bindings as the synchronous firing of appropriate nodes, (2) rules as interconnection patterns that direct the propagation of rhythmic activity, and (3) long-term facts as temporal pattern-matching subnetworks. The model is consistent with recent neurophysiological evidence that synchronous activity occurs in the brain and may play a representational role in neural information processing. The model also makes specific psychologically significant predictions about the nature of reflexive reasoning. It identifies constraints on the form of rules that may participate in such reasoning and relates the capacity of the working memory underlying reflexive reasoning to biological parameters such as the lowest frequency at which nodes can sustain synchronous oscillations and the coarseness of synchronization.

Keywords: binding problem; connectionism; knowledge representation; long-term memory; neural oscillations; reasoning; short-term memory; systematicity; temporal synchrony; working memory
 
 

1. Introduction

The ability to represent and reason with a large body of knowledge in an effective and systematic manner is a central characteristic of cognition. This is borne out by research on artificial intelligence and cognitive science, which suggests that reasoning underlies even the most commonplace intelligent behavior. For example, language understanding, a task we usually perform rapidly and effortlessly, depends upon our ability to make predictions, generate explanations, and recognize speakers' plans.' To appreciate the richness and speed of human reasoning, consider the following example derived from Schubert (1989). Imagine a person reading a variation of the Little Red Riding Hood (LRRH) story, in which the wolf intends to eat LRRH in the woods. The reader is at the point in the story where the wolf, who has followed LRRH into the woods, is about to attack her. The next sentence reads: "The wolf heard some woodcutters nearby and so he decided to wait." It seems reasonable to claim that the reader will understand this sentence spontaneously and without conscious effort. However, a careful analysis suggests that even though the reader remains unaware of it, understanding this sentence requires a [page 418] chain of reasoning that may be described informally as follows (parenthetical text identifies the background knowledge that might mediate the reasoning process):

The wolf will approach LRRH (to eat something you have to be near it); LRRH will scream (because a child is scared by an approaching wild animal); upon hearing the scream the woodcutters will know that a child is in danger (because a child's screaming suggests that she is in danger); the woodcutters will go to the child (people want to protect children in danger, and in part this involves determining the source of the danger); the woodcutters will try to prevent the wolf from attacking LRRH (people want to protect children); in doing so the woodcutters may hurt the wolf (preventing an animal from attacking may involve physical force); so the wolf decides to wait (because an animal does not want to get hurt).

As the above examples suggest, we can draw a variety of inferences rapidly, spontaneously, and without conscious effort -- as though they were a reflexive response of our cognitive apparatus. Let us accordingly describe such reasoning as reflexive (Shastri 1990). Reflexive reasoning may be contrasted with reflective reasoning, which requires reflection, conscious deliberation, and often an overt consideration of alternatives and weighing of possibilities. Reflective reasoning takes longer and often requires the use of external props such as a paper and pencil. Examples of such reasoning are solving logic puzzles, doing cryptarithmetic, or planning a vacation.

Our remarkable ability to perform reflexive reasoning poses a challenge for cognitive science and neuroscience: How can a system of simple and slow neuronlike elements represent a large body of systematic knowledge and perform a range of inferences with such speed? With nearly 10¹² computing elements and 10¹⁵ interconnections, the brain's capacity for encoding, communicating, and processing information seems overwhelming. But if the brain is extremely powerful, it is also extremely limited: First, neurons are slow computing devices. Second, they communicate relatively simple messages that can encode only a few bits of information. Hence a neuron's output cannot encode names, pointers, or complex structures. Finally, the computation performed by a neuron is best described as an analog spatio-temporal integration of its inputs. The relative simplicity of a neuron's processing ability with reference to the needs of symbolic computation, and the restriction on the complexity of messages exchanged by neurons, impose strong constraints on the nature of neural representations and processes (Feldman 1989; Feldman & Ballard 1982; Shastri 1991). [See also Feldman: "Four frames suffice: A provisional model of vision and space" BBS 8(2) 1985; Ballard: "Cortical connections and parallel processing: Structure and function" BBS 9(l) 1986.] As we discuss in section 2, a reasoning system must be capable of encoding systematic and abstract knowledge and instantiating it in specific situations to draw appropriate inferences, This means that the system must solve a complex version of the variable-binding problem (see Section 2 and Feldman 1982; von der Malsburg 1986). In particular, the system must be capable of representing composite structures in a dynamic fashion and systematically propagating them to instantiate other composite structures. This turns out to be a difficult problem for neurally motivated models. As McCarthy (1988) observed, most connectionist systems suffer from the "unary or even propositional fixation" with their representational power restricted to unary predicates applied to a fixed object. Fodor and Pylyshyn (1988a) have even questioned the ability of connectionist networks to embody systematicity and compositionality.

1.1. Reflexive reasoning: Some assumptions, observations and hypotheses

Reflexive reasoning occurs with reference to a large body of long-term knowledge. This knowledge forms an integral part of an agent's conceptual representation and is retained for a considerable period of time once it is acquired. We wish to distinguish long-term knowledge from short-term as well as medium-term knowledge. By the last we mean knowledge that persists longer than short-term knowledge and may be remembered for days or even weeks. Such medium-term knowledge, however, may be forgotten without being integrated into the agent's long-term conceptual representation. The distinction between medium- and long-term knowledge is not arbitrary and seems to have a neurological basis. It has been suggested that medium-term memories are encoded via long-term potentiation (LTP) (Lynch 1986), and some of them subsequently converted into long-term memories and encoded via essentially permanent structural changes (see, e.g., Marr 1971, Squire 1987; Squire & Zola-Morgan 1991).

An agent's long-term knowledge base (LTKB) encodes several kinds of knowledge. These include specific knowledge about particular entities, relations, events, and situations, and general systematic knowledge about the regularities and dependencies in the agent's environment. For example, an agent's LTKB may contain specific knowledge such as "Paris is the capital of France" and "Susan bought a Rolls-Royce," as well as systematic and instantiation-independent knowledge such as "if one buys something then one owns it." We will refer to specific knowledge as facts, and general instantiation-independent knowledge as rules (note that by a rule we do not mean a "rule of inference" such as modus ponens). The LTKB may also include knowledge about the attributes of features of concepts and the superordinate/subordinate relations among concepts, and also procedural knowledge such as "how to mow a lawn." [page 418]

In discussing the LTKB we are focusing on representational adequacy, that is, the need to represent entities, relations, inferential dependencies, and specific as well as general knowledge. The expressiveness implied by this generic specification, however, is sufficient to represent knowledge structures such as frames (Minsky 1975), scripts (Schank & Abelson 1977), and productions or if-then rules (Newell & Simon 1972).

A serious attempt at compiling commonsense knowledge suggests that the LTKB may contain as many as 10⁸ items (Guha & Lenat 1990). This should not be very surprising given that it must include, besides other things, our knowledge of naive physics and naive psychology; facts about ourselves, our family, and friends; facts about history and geography; our knowledge of artifacts; sports, art, and music trivia; and our models of social and civic interactions.

1.1.1. Space and time constraints on a reflexive reasoner. Given that there are about 10¹² cells in the brain, the expected size of the LTKB (10⁸) rules out any encoding scheme whose node requirement is quadratic (or higher) in the size of the LTKB. In view of this we adopt the working hypothesis that the node requirement of a model of reflexive reasoning should be no more than linear in (i.e., proportional to) the size of the LTKB. This is a reasonable hypothesis. Observe that (1) a node in an idealized computational model may easily correspond to a hundred or so actual cells, and (2) the number of cells available for encoding the LTKB can only be a fraction of the total number of cells.

We believe that although the size of an agent's LTKB increases considerably from, say, age 10 to 30, the time taken by an agent to understand natural language does not. This leads us to suspect that the time taken by an episode of reflexive reasoning does not depend on the overall size of the LTKB but only on the complexity of the particular episode of reasoning. Hence we adopt the working hypothesis that the time required to perform reflexive reasoning is independent of the size of the LTKB.

The independence of (1) the time taken by reflexive reasoning and (2) the size of the LTKB implies that reflexive reasoning is a parallel process and involves the simultaneous exploration of a number of inferential paths. Hence, a model of reflexive reasoning must be parallel at the level of rule application and reasoning, that is, it must support knowledge-level parallelism. This is a critical constraint and one that is not necessarily satisfied by a connectionist model simply because it is "connectionist" (see also Sumida & Dyer 1989).

We understand written language at the rate of somewhere between 150 and 400 words per minute (Carpenter & just 1977). In other words, we can understand a typical sentence in a matter of one to two seconds. Given that reflexive reasoning occurs during language understanding, it follows that episodes of reflexive reasoning may take as little as a few hundred milliseconds.

1.1.2. Reflexive reasoning is limited reasoning. Complexity theory rules out the existence of a general-purpose reasoning system that derives all inferences efficiently. This entails that there must exist constraints on the class of reasoning that may be performed in a reflexive manner. Not surprisingly, cognitive agents can perform only a limited class of inferences with extreme efficiency. Naturally, we expect that the representational and reasoning ability of the proposed system will also be constrained and limited in a number of ways. However, we would like the strengths and limitations of the system to be psychologically plausible and to mirror some of the strengths and limitations of human reasoning.

1.2. Computational constraints

Connectionist models (Feldman & Ballard 1982; Rumelhart & McClelland 1986) are intended to emulate the information-processing characteristics of the brain -- albeit at an abstract computational level -- and to reflect its strengths and weaknesses. Typically, a node in a connectionist network corresponds to an idealized neuron, and a link corresponds to an idealized synaptic connection. Let us enumerate some core computational features of connectionist models: (1) Nodes compute very simple functions of their inputs. (2) They can only hold limited state information -- while a node may maintain a scalar "potential," it cannot store and selectively manipulate bit strings. (3) Node outputs do not have sufficient resolution to encode symbolic names or pointers. (4) There is no central controller that instructs individual nodes to perform specific operations at each step of processing.

1.3. A preview

We discuss the variable-binding problem as it arises in the context of reasoning and describe a neurally plausible solution to this problem. The solution involves maintaining and propagating dynamic bindings using synchronous firing of appropriate nodes. We show how our solution leads to a connectionist knowledge representation and reasoning system (which we call SHRUTI, see Response, Note 1) that can encode a large LTKB consisting of facts and rules involving n-ary predicates and variables, and perform a broad class of reasoning with extreme efficiency. Once a query is posed to the system by initializing the activity of appropriate nodes, the system computes an answer automatically and in time proportional to the length of the shortest chain of reasoning leading to the conclusion. The ability to reason rapidly is a consequence, in part, of the system's ability to maintain and propagate a large number of dynamic bindings simultaneously.

The view of information processing implied by the proposed system is one where (1) reasoning is the transient but systematic propagation of a rhythmic pattern of activity, (2) each entity in the dynamic memory is a phase in this rhythmic activity, (3) dynamic bindings are represented as the synchronous firing of appropriate nodes, (4) long-term facts are subnetworks that act as temporal pattern matchers, and (5) rules are interconnection patterns that cause the propagation and transformation of rhythmic patterns of activity.

We cite neurophysiological data that suggest that the basic mechanisms proposed for representing and propagating dynamic variable bindings, namely, the propagation of rhythmic patterns of activity and the synchronous activation of nodes, exist in the brain and appear to play a role in the representation and processing of information. [page 419]

Our system predicts a number of constraints on reflexive reasoning that have psychological implications. These predictions concern the capacity of the working memory underlying reflexive reasoning (WMRR) and the form of rules that can participate in such reasoning. The predictions also relate the capacity of the WMRR and the time it would take to perform one step of reasoning to biological parameters such as the lowest frequency at which nodes can sustain synchronous oscillations, the coarseness of' synchronization, and the time it takes connected nodes to synchronize. By choosing biologically plausible system parameters, we show that it is possible for a system of

neuronlike elements to encode millions of facts and rules and yet perform multistep inferences in a few hundred milliseconds.

Reasoning is the spontaneous and natural outcome of the system's behavior. The system does not apply syntactic rules of inference such as modus ponens. There is no separate interpreter or inference mechanism that manipulates and rewrites symbols. The network encoding of the LTKB is best viewed as a vivid internal model of the agent's environment, where the interconnections between (internal) representations directly encode the dependencies between the associated (external) entities. When the nodes in this model are activated to reflect a given state of affairs in the environment, the model spontaneously simulates the behavior of the external world and in doing so makes predictions and draws inferences.

The representational and inferential machinery developed in this work has wider significance and can be applied to other problems whose formulation requires the expressive power of n-ary predicates, and whose solution requires the rapid and systematic interaction between long-term and dynamic structures. Some examples of such problems are (1) parsing and the dynamic linking of syntactic and semantic structures during language processing, and (2) model-based visual object recognition requiring the dynamic representation and analysis of spatial relations between objects and/or parts of objects. Recently, Henderson (1992) has proposed the design of a natural language parser based on our computational model.

1.4. Caveats

Our primary concern has been to extend the representational and inferential power of neurally plausible (connectionist) models and to demonstrate their scalability, We are also concerned that the strengths and limitations of our system be psychologically plausible. However, our aim has not been to model data from specific psychological experiments. What we describe is a partial model of reflexive reasoning. It demonstrates how a range of reasoning can be performed in a reflexive manner, and it also identifies certain types of reasoning that cannot be performed in a reflexive manner. Our system, however, does not model all aspects of reflexive reasoning. For example, we focus primarily on declarative and semantic knowledge and do not model reflexive analogical reasoning, or reflexive reasoning involving episodic memory (Tulving 1983) and imagery. We do not say much about what the actual contents of an agent's LTKB ought to be, nor do we provide a detailed answer to the question of learning. We do, however, discuss in brief how specific facts may be learned and existing rules modified (sect. 10.6). Neural plausibility is an important aspect of this work -- we show that the proposed system can be realized by using neurally plausible nodes and mechanisms, and we investigate the consequences of choosing biologically motivated values of system parameters. Needless to say, what we describe is an idealized computational model and it is not intended to be a blueprint of how the brain encodes an LTKB and performs reflexive reasoning.

1.4.1. An outline of the paper. Section 2 discusses the dynamic-binding problem in the context of reasoning. Section 3 presents our solution to this problem and the encoding of long-term rules and facts. Section 4 describes a reasoning system capable of encoding an LTKB and answering queries on the basis of the encoded knowledge. The interface of the basic reasoning system with an IS-A hierarchy that represents entities, types (categories), and the super-/ subordinate concept relations between them is described in section 5. Section 6 discusses a solution to the multiple instantiation problem. Section 7 discusses the biological plausibility of our system and identifies neurally plausible values of certain system parameters. Section 8 points out the psychological implications of the constraints on reflexive reasoning suggested by the system. Section 9 discusses related connectionist models and the marker-passing system NETL. Finally, section 10 discusses some open problems related to integrating the proposed reflexive-reasoning system with an extended cognitive system. Certain portions of the text are set in small type. These cover detailed technical material and may be skipped without loss of continuity.