Processing Symbols at Variable Speed in DUAL: Connectionist Activation as Power Supply

1 Introduction

There are two challenges that any computational system operating in a complex environment must face­ flexibility and efficiency. Stated in general terms, the en­ vironment presents some problems (or tasks) to the sys­ tem, which in turn has to generate solutions (or behav­ iors) . Under this formulation, flexibility implies that the set of potential solutions to any given problem should be as large and open-ended as possible. No options should be ruled out a priori. At the same time, the pressure for efficiency restricts the number of candidate-solutions that can actually be considered in any particular case.

Each of these requirements is hard enough in itself but the conjunction of the two is even more demanding because they push in opposite directions. This dual chal­ lenge has been addressed in various ways ranging from the exhaustive backtracking of the early AI programs, to heuristic search [Newell and Simon, 1976] and hill climbing, to the elaborate control strategies of modern cognitive architectures such as ACT-R [Anderson and Lebiere, 1998] and SOAR [Newell, 1990].

One approach [Hofstadter, 1983; Hofstadter, 1995 ; Kokinov, 1994a] to the flexibility/efficiency challenge rests on the following four ideas: (i) Multiple candidate­ solutions are considered in parallel. (ii) There is a very cheap mechanism that calculates rough on-line estimates of the 'promise' of each candidate. (iiz) The computa­ tional resources of the system are allocated unevenly among the candidates, favoring the more promising ones. (iv) Promise estimates are updated constantly, taking into account whatever new information becomes available and re-allocating the computational resources accordingly.

Spreading activation is one mechanism that seems ideally suited for points (ii) and (iv) above. It is cheap, runs continuously, and can poll information from various sources dynamically. On the other hand, many tasks require complex, structured, and hierarchically organized representations. Taken together, this suggests a hybrid symbolic/connectionist system. Such hybrid systems have a number of desirable properties [Dinsmore, 1992; Sun and Alexandre, 1997].

This article builds on the hybridization idea [Kokinov, 1997] and concentrates on the interface between the symbolic and the subsymbolic. The main idea is to have multiple symbolic processors running at variable speed. The speed is proportional to the activation level attached to each processor and estimating the 'promise' of the candidate-solution that the processor is working upon. This concretizes the general point (iiz) above. The speed varies dynamically, as the activation level varies.

The next section begins with a brief overview of some alternative proposals from the literature. The variable­ speed idea is then described in detail, followed by an illustrative example from an implemented simulation.

2 Variable-Speed Symbolic Processing

Symbol manipulation is done in discrete steps. The algorithm describing a symbolic process usually involves branching and loops, but during the execution it unfolds into a linear sequence of steps. As a first approximation, it may be assumed that all steps are of equal 'length '. (This approximation will be refined later on). Thus the speed of a symbolic process can be defined as the number of steps advanced during a given time interval.

Conventional multi-tasking operating systems support multiple processes running in parallel. A single physical processor serves all processes in turn by time-sharing. Different priorities can be assigned to control the number of time slices allotted to a given process. This scheme can easily be adapted to use activation levels as priori­ ties. However, it requires a centralized task manager and hence hinders the self-organizing kind of parallelism that is of interest here.

In production systems [Newell, 1973, 1990; Anderson, 1983], the equivalent of a symbolic step is called a production. There are production systems that use the notion of activation [Anderson, 1983; Just and Carpenter, 1992]. The cognitive architecture ACT-R [Anderson and Lebiere, 1998] is a representative example. Productions in ACT-R operate on declarative memory elements called chunks. There is an activation level associated with each chunk and a strength value for each production. These subsymbolic parameters are used by the conflict resolu­ tion mechanism to select (stochastically) which produc­ tion fires on a given cycle. Moreover, the time to execute a production depends on the activation of the chunk(s) that have matched its condition(s). This temporal rela­ tionship is used to predict reaction time data from psy­ chological experiments. The timing, however, is not used to control the processing within the architecture itself. The control is based on a goal stack and only the produc­ tions that match the chunk at the top of the stack are con­ sidered for firing. Thus there is little parallelism at the level of global symbolic processes. Rather, a single proc­ ess is carried out by manipulating the single goal stack.

In the models of Douglas Hofstadter and his collabora­ tors [Hofstadter, 1983, 1995; Mitchell, 1993; French, 1995] the equivalent of a symbolic step is called a codelet. Many such codelets wait in a repository called the coderack and vie for a chance to run. Codelets tend to form chains-when a codelet is executed, it posts one or more successors to the coderack. Each such chain cor­ responds to a symbolic process. The coderack contains codelets belonging to different chains, thus emulating parallelism. An urgency value is assigned to each code­ Jet. These urgencies depend on various things, including activation levels. On each cycle, a codelet is chosen from the coderack and run. The choice is probabilistic but not uniformly random-it is biased in favor of codelets with higher urgencies. When this sampling is repeated many times, the overall effect is that all symbolic processes (i.e. chains) advance in parallel at speeds proportional to the average urgency of the respective code lets.

A very interesting feature of this scheme is the so­ called computational temperature. It is a global para­ meter controlling the degree of randomness in the sys­ tem. The temperature modulates the strength of the bias that the urgencies introduce into the coderack. At inter­ mediate temperatures the probability of selecting a given codelet is roughly linearly related to its urgency. At high temperatures, however, all codelets have approximately equal chances to run regardless of their urgencies. By contrast, at low (freezing) temperatures the bias becomes overwhelming and the most urgent codelet is chosen almost deterministically. There are specialized code lets that measure the temperature and change it dynamically.

Restated in terms of speed, the Hofstadter's proposal allows for parallel symbolic processes running at differ­ ent speeds. The speed can be controlled both by local factors (urgencies) and a global one (temperature) . Both kinds of factors vary dynamically.

Sometimes, however, a phenomenon called urgency explosion occurs in the coderack [French, 1995]. It is analogous to inflation in economics and occurs when many new codelets of high urgency are posted to the coderack, thus inflating the urgencies of the old code lets waiting therein. The urgency explosion has undesirable consequences and special measures must be taken to prevent it [French, 1995].

Finally, the task of designing a system in which paral­ lel symbolic processes run at variable speed may be addressed in a straightforward manner. The cognitive ar­ chitecture DUAL [Kokinov, 1994a, 1994b] represents such an attempt. It consists of a population of small computational entities called DUAL agents. Each agent is hybrid and has a symbolic and a connectionist aspect. The symbolic aspect consists of a micro-frame and a symbolic processor. The connectionist aspect is analo­ gous to a unit in a neural network. The micro-frame is a bundle of labeled slots filled with references to other agents. The agent interacts with the agents referenced in its micro-frame by sending them messages and activa­ tion. An activation level is associated with each DUAL agent and the interactions between the agents can be regarded as links. The activation level of a given agent represents the system's internal estimate of its relevance to the problem being solved, the surrounding context, etc. It changes dynamically as these factors change. A threshold is imposed on the activation so that the agents that fail to reach some minimal degree of relevance are kept dormant.

The symbolic processor of each agent runs at a speed proportional to its activation level. Thus very active agents run rapidly and determine the overall flow of com­ putation, moderately active agents run slowly, and in­ active agents do not run at all. All agents above the threshold run in parallel and there is no central executive in the system to coordinate their work. Rather, coordina­ tion and global consistency are achieved by massive local interactions: both symbolic (exchange of messages) and connectionist (exchange of activation). The behavior of the system as a whole emerges out of these local acti­ vities. This style of dynamic emergent computation allows for great flexibility, efficiency, and context sensi­ tivity [Kokinov eta!., 1996].

The presentation so far simply postulated that the sym­ bolic processors in DUAL run at a speed proportional to the activation level of the corresponding agent. The next two sections concretize this abstract specification.

3 The Energetic Analogy: Activation as Power

The exact relationship between symbolic speed and con­ nectionist activation in the architecture DUAL rests on the following energetic analogy: the manipulation of sym­ bols can be conceptualized as work and the connectionist activation as power. Doing work requires energy, which is supplied to the symbolic processor by the connectionist aspect of the agent. The energy is calculated by inte­ grating the power over time. The speed of the symbolic computation depends on the power (i.e. the activation level). The same amount of work is completed rapidly when there is plenty of power, slowly when power is scarce, and not at all if it is lacking completely.

The symbolic processing in the architecture can be categorized into segments of increasing complexity [Petrov, 1998] . (i) A symbolic operation is the smallest unit of symbol manipulation. The operations are simple, atomic, and deterministic. They are the elementary in­ structions of the symbolic processor. (ii) A symbolic step is a sequence of operations performed by a single agent without intervening symbolic interactions with other agents. (iiz) A rigid symbolic process is a fixed and a priory specified sequence of steps performed by a single agent. There may be intervening interactions. (iv) An emergent symbolic process is distributed over a coalition of interacting agents. It does not have any complete a priory specification. Rather, the course of computation is determined dynamically by the interplay of various pressures [Kokinov eta!., 1996].

Each symbolic operation is characterized by some consumption C. This is a real number specifying the amount of symbolic work embedded in the operation. Different operations may have different consumptions. They are free parameters of the particular model and may be fixed on theoretical grounds and/or estimated from empirical data. This scheme offers considerably more freedom than the alternative proposals that typically assume equal consumption for all operations.

If a fine-grained analysis at the level of individual op­ erations is not warranted, consumptions may be specified at the level of symbolic steps. The latter are often more convenient due to their larger grain size. A symbolic step is performed by a single agent and by definition there is no symbolic exchange with other agents during the step. Thus as far as the inter-agent communication is concerned, steps can be treated as units, disregarding the constituent operations. What matters is the final outcome

(in the form of a message send to another agent) and the timing of its appearance.

Each symbolic processor acts as a machine that trans­ forms connectionist energy into symbolic work. Not all energy, however, is converted into useful work. There is some overhead for covering the internal needs of the processor itself. The efficiency coefficient 11 is defined as the ratio of the useful work A to the total energy input E: 11=AIE. This coefficient characterizes the symbolic proc­ essor. Different processors can have different efficien­ cies. In a cognitive model, for instance, processors per­ forming highly automated tasks have 11 close to I while processors performing novel tasks have low efficiency. The efficiency can even be adjusted dynamically by some kind of learning-the basic rule is that it increases with practice.

Suppose a symbolic processor starts working on some operation (or step) at time t 0· The amount of energy needed for the operation can be calculated in advance-it is E=C/11, where C is the consumption of the operation. This energy must be provided by the connectionist aspect of the agent. This takes time, as the rate of supply is limited. The energy function that describes the accumu­ lation of energy in time is defined by the integral:

where a('t) is the activation level. Activation levels in DUAL must be above some positive threshold in order for the symbolic processor to work. (If a( "C) drops below the threshold even for a moment, the symbolic processing is aborted and all intermediate results are lost.) Because a('t) is always positive, E(t) is an increasing function and thus has an inverse E- 1 · The inverse function expresses the time needed to produce a given amount of energy.

Putting all pieces together, the exact moment in which the symbolic operation is completed is t = t0 + K 1 (CfTt) . The outcome of the operation becomes available at that moment. It may be a message sent to another agent or a modification of the internal micro-frame. Then the proc­ essor moves to the next operation as prescribed by the algorithm and the whole cycle repeats.

When the symbolic processor is idle, all energy pro­ duced by the connectionist aspect of the agent goes unused. It cannot be accumulated. In other words, it is not allowed to amass energy 'on store' and then expend it all at once, thus attaining very high peak power.

The energetic analogy offers the following advantages: (i) It provides for variable-speed symbolic computation and hence for all associated benefits. Indeed, it is clear that the specification described in this section implies that the more active agents run more rapidly. (ii) The ac­ tivation levels can change dynamically and all changes have instant effect. (iiz) The architecture DUAL has a well-defined notion of time. It is measured on a continuous scale and frames the occurrence of all sym­ bolic events. (iv) The speed of each DUAL agent is defined independently of that of the other agents. Thus the architecture can be run without any modification on parallel hardware. (v) The relationship between symbolic speed and connectionist activation is specified without recourse to any particular implementation. (vi) Symbolic processes can be finely parameterized and the parame­ ters have straightforward interpretation-consumptions and efficiency coefficients.

4 S-LISP: A Language For Variable Speed Symbolic Computations

The DUAL architecture has been fully implemented. All programs are written in COMMON LiSP using CLOS 1 · An extension of LISP called S-LISP ('suspendable' LISP) has been developed [Petrov, 1998] for the purposes of the variable-speed symbolic computations. A rudimentary compiler translates S-L!SP programs into 'plain' LISP. This section outlines the main features of the language and the principles of its implementation.

S-LISP is an extension of COMMON LISP. Its main dif­ ference from plain LISP is that it supports four additional special operators: s-progn, s-eval, s-values, and suspended-value-bind. They are 'suspendable' ana­ logs to the respective LISP operators. S-LISP also supports most (but not all) 'plain' LISP primitives such as progn, if, let, and setq. The language also supports function calls and recursion, which in turn allows for loops.

S-progn establishes a sequence of symbolic steps to be executed at variable speed by the processor of some DUAL agent called a host. The complementary suspen­ sion primitive, s-eval, signals that a given S-Lisp form is suspendable and announces the amount of energy needed for it. The two suspension primitives go together. s-eval may appear only within the lexical scope of an s-progn; it is an error elsewhere. Conversely, s-progn is like an ordinary progn in all respects except the treatment of s-eval and the other suspension primitives. A very simpleS-LISP program is illustrated below:

{s-progn host {s-eval 0.5 (prepare x)) {when {s-eval 0.2 (check x)) {s-eval 2.5 {work-on x))) {s-eval O.l {cleanup)) )

The remaining two suspension primitives, s-values and suspended-value-bind, are used to export and import values from functions defined via s-progn.

The implementation of s-progn and s-eval is based on delayed evaluation. While the theoretical specification of DUAL postulates that symbolic processes run smoothly and at variable speed, the implementation carries them out in instantaneous jumps. Pauses are imposed between the jumps to produce the timing postulated by the theory.

When a processor begins working on some symbolic operation, it does not actually execute it. Instead, it wraps it in a closure and stores it on a stack. One such stack is maintained for each processor (i.e. DUAL agent). There is an energy balance associated with each stack. The energy balance is equal to the difference between supplied and consumed energy. When the balance is negative, the processor waits until it becomes positive. On each con­ nectionist cycle, the connectionist machinery increases the balance with some small amount depending on the ac­ tivation level and the efficiency coefficient of the host. After some time, the balance becomes positive and the top closure on the stack is popped and executed.

1 The full source code and the accompanying documentation are available from the authors upon request.

The S-LISP compiler analyzes the source code, traps all occurrences of s-eval and replaces them with 'plain' LISP forms that generate closures and arrange them on the stack. The stack is established by the enclosing s­ progn form. The top-level loop of the implementation checks the stacks of all active DUAL agents and pops the ones with positive energetic balance. This scheme also supports the parallel work of multiple agents.

S-LISP programs should be written with care because many intuitions from 'plain' LiSP are violated. In particular, s-progn does not return any useful value. This is because a call to s-progn does not execute the forms in its body; it delays them. Thus the value that the programmer expects will be computed later, long after the original call to s-progn is over. s-values must be used to export a value out of a suspendable function and this value must be bound via suspended-value-bind.

A mailbox technique is used to transfer suspended values through destructive operations executed as side effects. A mailbox is a data structure containing a field that can be modified destructively. The job of s-values is to make a new empty mailbox and to arrange that the suspended value (or multiple values) will be stored in it when the suspended computation is completed. The job of suspended-value-bind is to catch the mailbox, open it at the appropriate time, and bind the values to local variables accessible within its lexical scope.

S Variable-Speed Symbol Processing at Work: An Example

This final section provides an example of variable-speed symbolic processing in action. It also illustrates the util­ ity of symbolic/connectionist hybridization. The material for the example is taken from actual simulation experi­ ments with a DUAL-based cognitive model called AMBR [Kokinov, 1994a; Petrov, 1998]. In these simulations AMBR tries to solve simple everyday problems such as: "There is some milk in a teapot. There is also a hot plate. The goal is to heat the milk." The model solves these problems by analogy to previous cases. The long-term memory of the system contains a number of past prob­ lems with solutions. It also contains semantic knowledge about general regularities in the domain. When faced with a new target problem, AMBR attempts to retrieve an appropriate source analog, map it to the target, and trans­ fer the solution. Several such retrievals and mappings are attempted in parallel and at variable speed.

AMBR, like all DUAL-based models, consists entirely of DUAL agents. They carry out all representational and computational functions in the system. The long-term memory is just a population of interacting agents. Some of them, the so-called concept-agents, represent classes of objects such as milk, water, and liquid. These agents form the backbone of AMBR's semantic memory. There are also instance-agents standing for individual instances such as milk-S. The agents form coalitions to represent propositions (e.g. in-6 (milk-S, teapot-3)) and episodes. Finally, hypothesis-agents are created during the problem-solving process to represent tentative correspondences such as milk-S<->water-3 .

Note that these are not passive data structures . Rather, each agent is a semi-autonomous entity that heavily inter­ acts with its peers. For instance, the agent milk sends symbolic messages and connectionist activation to the agent liquid. The symbolic processor of liquid then handles and re-sends these messages at variable speed according to the principles discussed above.

For the sake of concreteness, the example here concen­ trates on one of the several computational mechanisms used in AMBR. The marker passing mechanism stems from the semantic network tradition (see [Hendler, 1988] for an overview). In its most basic form it is a tool for answering the question: "Given two nodes in a semantic network, is there a path connecting them?" The under­ lying idea is simple-the two nodes of origin are marked. They then mark their neighbors, which in turn mark further. If the two 'waves' of markers intersect, a path is found. AMBR uses these intersections to build hypotheses about similarity-based correspondences between instance agents. Consider the following coalition:

The words in the figure denote agents. The lines denote interactions, usually bi-directional. The agents at the bot­ tom row are instances; all others are concepts. Note that milk treats two different agents as 'parents'.

Marker passing in AMBR goes hand in hand with spreading activation. Suppose milk-S is a newly created agent participating in the representation of the target problem and that all other agents in the figure are dormant (i .e. with zero activation) in the long-term mem­ ory. Milk-8, being related to the goal, is a strong activa­ tion source. It spreads this activation to the agents refer­ enced in its micro-frame. One such agent is the parent concept milk. This input from milk-S brings its acti­ vation level above the critical threshold and it enters the working memory (WM) of AMBR. In turn, milk activates other agents. The coalition gradually enters the WM:

T=0.04, MILK enters WM. T=0.20, BEVERAGE enters WM.

T=0.24, DAIRY-PROD enters WM.

T=0.42, LIQUID enters WM. T=O.S4, CHEESE enters WM. T=O.S6, TEA enters WM. T=0.56, FOOD enters WM. T=0.70, WATER enters WM. T=0.92, WATER-3 enters WM. T=0.92, BREAD enters WM. T=1.24, BREAD-123 enters WM.

Note that the two branches of the hierarchy receive un­ equal amounts of activation. This is due to both perma­ nent and transient factors . The permanent factors reflect domain knowledge and are embodied in the 'weights' of the interactions. For example, milk may send more acti­ vation to beverage than to dairy-prod. The transient factors are due to goal-related, context, and priming ef­ fects. In the above example, the target problem involves a teapot that indirectly activates liquid via the liquid-holder agent (not shown in the figure). All these factors vary across and within problem-solving episodes. The pattern of activation over the population of agents changes dynamically, as the estimated relevance of each agent varies.

The stage is now ready for the marker-passing mecha­ nism per se. Whenever an instance-agent enters the work­ ing memory it sends a marker to its parent concept(s). The concept-agents in turn spread the markers to their superclass( es ). Each marker carries a reference to the instance-agent that originated it as well as a color tag in­ dicating whether the origin is a target agent. The follow­ ing transcript illustrates the marker passing process:

T=0.14, I<M milk-S> received in MILK. T=0.30, I<M milk-S> received in BEVERAGE. T=O.SO, I<M milk-S> reeved in DAIRY-PROD. T=0.60, I<M milk-S> received in LIQUID. T=O.SS, I<M milk-S> received in FOOD. T=1.14, I<M water-3> received in WATER. T=l.34, I<M water-3> received in LIQUID. T=1.54, I<M bread-123> received in BREAD. T=1.SS, LIQUID detects marker intersectn.

When two markers of different colors meet in some concept-agent, the latter detects the intersection and initiates a sequence of interactions with various agents that ultimately results in creating a new hypothesis. In our example this would be milk-S<->water-3. Alter­ native hypotheses (e.g. milk-S<->bread-123) are being constructed in parallel. The respective agents, how­ ever, are less active and hence handle their markers more slowly. The net effect is that the population of agents as a whole explores various paths in parallel at speed pro­ portional to their dynamically estimated 'promise'. In a different context, the same agent milk-S could be mapped to another instance-agent retrieved from some other past episode. There is a vast number of possibilities but only a few of them are considered in any given case.

One of the biggest issues in marker-passing systems is the attenuation of the marking. Without such attenuation there would be too many intersections, most of which are useless and overwhelm the useful ones. Several attenu­ ation strategies have been explored over the years (re­ viewed by [Hendler, 1988]): limitation of the number of links each marker can traverse, checks of the outbranch­ ing factor of 'promiscuous nodes', etc. In AMBR there is no need for any ad-hoc attenuation mechanism as it fol­ lows naturally from the architectural principles of DUAL. Two such attenuation factors are relevant here: (i) The markers cannot reach the agents that have been left totally inactive by the spreading activation mechanism. (ii) Marker passing, as any other symbolic activity in the architecture, depends on the speed of the symbolic proc­ essors handling the markers. As a consequence, the markers move rapidly through the 'promising' portions of the semantic memory and then slow down as they reach the periphery of the area delineated by activation levels. The net effect of these and other similar factors is that marker intersections are reported in a temporal order reflecting their potential usefulness for the particular task and the particular context.

It is worthwhile to stress that the global marker passing is a dynamic emergent process. A whole coali­ tion of DUAL agents is needed to cooperatively produce the final result. Each individual agent does local marker passing only. The overall result is determined by a multi­ tude of factors (or 'pressures') each of which has rela­ tively minor impact on its own. Moreover, the strength of these factors varies dynamically in response to various external and internal events. The variable-speed symbolic processing and the energetic analogy presented in this paper are instrumental for these desirable properties.