Cognitive Economy in Artificial Intelligence Systems

1. INTRODUCTION

When we build an AI program, we often find our­ selves caught in a tradeoff between expresRibility and r.fficiency. Many AI reRr.archcrs cum language desig· ners have focused on cxpres.~ibilitv, the problem of rapidly constructing a working experimental vehicle. Four fundamr.ntal techniques utilized in highly ex­ prCMivc programs are: (i) reliance upon a very-high· level language, (i1) plarining and reasoning at multiple levels of abatraction, (ii1) inference by pattern-directed knowledge sources, and ( iv) minimal, nonredundant rep· resentation, as in a canonical generalization/specializa· tion hierarchy.

This paper addreRReR the second goal of AI program· rning, efficiency: ~~:ettin~~: pro~~:rams to liRe as few resources (time, space) as possible. We present techniques which do not sacrifice expressibility, yet enable programs to (semi)·automatically improve themRclvcs and thus in· crease their productivity. The basic source of power is the ability to predict the way that the program will be used in the future, and to tailor the program to expedite such uses.

The traditional approach to program optimization has assumed that the programmer characterizes the predicted program behavior (e.g., by explicitly prov ui· ing assertions) or that static analysis can identify significant optimization opportunities. Three types or methode for analyzing program descriptions in this way include: (1) analyzing program flow and structure Ia la Knuth and Dijkatra), (i1) designing data struc­ tures to be appropriate, and (ii1) compiling (as in the FORTRAN H compiler) and optimizing transformations of the program (as in [1,2)).

lThia reaearch wna aupported in port by the National Science Foundation under aranta MCS77-04440 and MCS77-0J373.

We propose the use of methode more dJifUJm1C than these. Rather than improving the static description of a program, we advocate a plastic program structure which adapts to its operational environment. We believe that a program 'a "intelligence" can be increased in this way; that is, by increasing ita ability to acquire ap· propriate knowledge, to organize that knowledge, and to refine the conditione under which that knowledge is recognized to be applicable. For any fixed quantum of manpower resources we expend, there is a limit to the size/complexity of programs which can be success· fully implemented. This barrier might be overcome by programs which are self-extending, which actively reason -and reprogram themsrlves - to enlarge their input domain, their capabilities.

Abilities which make a program efficient include:

· Dynamle 11lf-monitorin1 (the ability to sense, record,

and analyze dynamic usage) and nlf·modlfication (the ability to usc that knowledge to redesign/recompile it· self with more appropriate representation&, algorithms, data structures; i.e., intelligent learning.)

• Caehin1 of computed result. (storing the results or frequently-requested searches, so they necdn 't be repeated over and over again; i.e., intelligent redun· dancy.)
• Expec:tatlon·fllterlnK (using predictions to filter away expected, unsurprising data, thereby freeing up process­ ing time for more productive subtasks; i.e., intelligent focus of attention.)

"OJgnilivc ccr:mom!l' is the term by which we describe such heightened productivity. Computer programs, no leAs than biological crcature11, mu11t perform in an en· vironment: an externally imposed set of demands, pres· surcs, opportunities, regularities. Extending this anal­ ogy, we find that co~nitive economy is the degree to wltich a program is adapted to its environment, the ex· tent to which its internal capabilities (structures and proce11scs) accurately and efficiently reHcct its environ· mental niche.

Notice that representing a corpus of knowledge as a mi­ nimal (canonical) p;encralization/specialization hierar­ chy, with interpretatively-computed inheritance, is not cognitively economical: this technique favors expressi· biJity, compaction of rcpreRentation, at the expense of performance. It i11 true that a dog is a mammal, and a mammal is an animal, and from those two we could compute that a dog is an animal, but it is more cogni­ tively economical to store one redundant arc than to recompute it frrquently . Psychological studies [JJ in­ dicate just such redundancies being created in human memory.

Obviously, the economy of 11pccific representations and related inference mdhods depends heavily on under· lying machine architecture-S and costs. We assume that intelligent Rystr.rJJR aim chieHy to produce useful rcAUIL!I (e.g., novrl hypotheses) as rapidly a~ possible. In short, they should search cleverly and fast. But we arc advocating efliciency in addition to, not in lieu of, cxprcssihility (interpretability, intcrruptibility, and modifiability). In typical situations, both efliciency of compiled forms and accessibility to declarative forms are intermittently needed. These different needs point to the economic benefits or simultaneously maintaining alternative and redundant representations.

2. THE ASSUMPTIONS

Every scientific theory is constructed in a rich conte:x t of surrounding theories, methods, and standards deter­ mining which experiments are reasonable ones to per­ form and which point or view to take when interpreting the result&- in short, a paradigm. We feel it useful to articulate the "core" of our paradigm (the assumptions our theory rests upon) before delving into more detail about cognitive economy:

• (i) We continually face 11earches in more or less im­ mense spaces; intelligence is the ability to bring ap­ propriate knowledge to bear, to speed up such search­ ing. Increasing intelligence then comprises increasing knowledge, improving its organization, and refining the conditions for its applicability.
• (ii) Since we want intelligent systemR to access, reason about, and expand their own knowledge bases, it is use­ ful to represent such knowledge in a clean, modular form (e.g., employing any one of the current schematized rep­ resentations.) Its applicabiJitv can be made explicit by encoding it as condition-action (ir/then) rules.
• (iii) Current computing technology presents us with limited cycles, cheap storage, and expensive knowledge acquisition. They arc the symbol manipulators we use, but were not designed for that purpose.

3. SELF-IMPROVEMENT

NOTE: Due to IJOAIIength limitation~, the authors han been forced to eliminate man,y sections of this paper; usually, at least their summariu remain. The complete version can be obtained as 15).

3.1. DYNAMICALLY MODIFYING ITSELF

Summary1 We ill/ustrate various ways in which a program might usc to advantage knowledge gleaned dynamically: selecting {6] (or perhaps even discovering)

new data structures, rcp.rescntations, algorithms, etc. wiJich seem better suited to tl1e current runtime en­ vironment, the current user, tl1e current problem, etc.

3.l. l. E:xtendlnQ · Schemetlzed Repreunt·tlon.

For a schcmatizcd representation,' "extension" could occur by defining new typc11 of slots. The Eurisko program (succcesor to the AM program (1]) has this capability, and we briefly describe how this mechanism was developed. First, we isolated four ways in which new slots arc defined from old ones:

STAR (e.g., Ancestor =dt Parent· which means a Parent of a Parent of.. . of a Parent of me; the general case should be aparcnt);

UNION (e.g., Parent =dt Father U Mother); COMPOSITION (e.g., Cou8in =dtChildoSiblingoParent); DIFFERENCE (e.g., RemoteAncestor =dt Ancestor­ Parent).

These four operators which define new types of slots (", U, o, -)are called &lol-<.omhiru!r~.

Next, we added to AM's knowledge base a concept for each type of slot, and a concept for each type of slot· combiner. Figure 1 shows part of the Generalizations and Star concepts. Note in particular the way in which Generalizations is defined as Genl· - i.e., immediate generalizations, their immediate generalizations, and so on.

GENF:RALIZATIONS

STAR

ISA: Slot

SI'EC: Extreme-Generalizations, Genl,

Pnlpcr-Gcncralizations

WOifl'll: 875 (out of 1000)

A \'G·SIZE: 7 entries

INV 1-:HSE: Specializations

ANALOGS: Supcrsets, Relaxations,

SLOT-COMBI NER: Star

BUILT-FROM: Genl

1 Knowledge broken in pieces called schemata, framu, ron­ t epta, beings, association fish, unih, atriph,... whith in t urn are merelyc.ollettione of amaller pietu tailed propertiea, alote, faeete, atipette.

Finally, we modified the way in which slot entries are accessed. To illustrate this, we choose a simple task in mathematics, whose paraphrase is, "What arc all the generalizations of the concept 'primes'?" The tradi­ tional way in which (GET PRlMES GENERALIZATIONS) would work is to examine the property list of PRIMES, looking for the attribute GENERALIZATIONS; if found, the entries listed there would be returned. ABBume that there is no such property recorded for PRIMES. If we looked, we would find a property called GENL ( immcdiaU: generalization}, whose value would be NUMBERS. Similarly, the NUMBERS concept has only a GENL slot, containing the entry OBJECTS. Anyway, since there is no GENERALIZATIONS attribute, the call upon GET will return NIL (the empty list).

In Eurisko, we modified the way in which any retrieval request of the form (GET c F) operates. In case the F attribute of c has no entries (or doesn't exist}, we examine the definition of F and - if one exists - try to usc it to compute the entries that could legally be stored on the F attribute of c . More precisely, before quitting we try to (GET F DEFN), and if that succeeds we apply it to o. Let's continue the example of (GI'JT PRIMES GENERALIZATIONS) . As we stated in the last paragraph, there are none recorded. So GET now calls itself recursively; our original call is replaced by ((GET GENERALIZATIONS DEFN) PRIMES) . But as Fig. 1 shows, there is no slot labelled DEFN on the concept for GENERALIZATIONS. So we recur one more time. By now our call has become

(((GET DEFN DEFN) GENERALIZATIONS) PRIMES).

DEFN

ISA: Slot-combiner WOIHII: 488 ANALOGS: Repeat. Closure COMBINEH·FOR: Generalizations. Specializations, Ancestor, ...

l>EFN: A (s) (suBST s for SLOT in: [A (c) (CONS c (seif (GET c SLOT)))) )

ISA: Slot

SI'EC: Necccssary·Defn, Sufficient·Dcfn, Operationai·Defn. Recursivc·Dcfn

WORTH: 975

AVG-SIZE: 1.3 entries

ANALOGS: Statement. Algorithm

m:FN: A (x) ( [GET (GET X Slot-Combiner) Dcfn]

(GET x Built-From))

Luckily, the DEFN concept docs have a DEFN slot (see Fig. 1), 10 we end tl4e recursion. Applying the entry stored there to the argument "GENERALIZATIONS," we see our original call becoming transformed into (((GET '(OET OENERALIZATIONS SLOT-COMBINER) DEFN)

(GET GENERALIZATIONS BUILT-FROM))

PRIMES)

We see from Fig. 1 that the slot-combiner of Gene· ralizations is "Star," and the argument (old slot) which it is built from is "Genl." So the entire call shrinks into (((GET STAR DEFN) GENL) PRIMES). The Star concept has an entry for its Defn slot; it turns the preceding call into ((~ (c) (CONS c (sel£ (GET c GENL)))) PRIMES). This function first calls for (GET PRIMES GENL), which is NUMBERS, then calls itsclC on NUMDERS; tl1at in turn calls for (GET NUMBERS GENL), which is OBJECTS, and calla itself recursively on OBJECTS; that calls for (GET OBJECTS GENL), which is ANYTHING, and the next recursive call terminates when it is discovered that ANYTIDNG has no GENL (no immediate generalization.) The list CONStructed and returned is thus (PlUMES NUMBERS OBJECTS ANYTHING). These four items are the legal entries for the GENERALIZATIONS slot of PRIMES, according to the definition of GENERALIZATIONS.

Notationally there is no distinction between slots which are "primitive" (values actually stored as attributes on a property list) and slots which arc "virtual" (valuea must be computed using the slot's definition). A heuris· tic might refer to the Generalizations or Primes without knowing, or caring, whether that initiated a single ac· cess or a dizzy chase.

To define a new kind of slot, then, one need merely specify one of the slot-combiners and list the old pre· existing slots from which it is built. Thus we might define a new slot, by creating a new concept (calling it, say, "DG" ), filling its Slot-combiner slot with the entry "Difference", filling its "Built-from" slot with the arguments "Generalizations Gcnl." This would be a new kind of slot, one which returned all generalizations of a concept except its immediate generalizations; the tall (GET PRIMES DG) would return (PRIMES OBJECTS ANYTHING).

It is only a small extcn11ion to see how new kinds of slot· combiners can be defined. For instance, one which took two old slotnames as arguments, f and g, and defined a J;leW slot Which Wall f 0 0 g 0 f 0 1 WOuld be extremely useful (e.g., in database searches). In particular the crucial slot

"Examples" is defined as Spec" olmmed-Exso Spec" .

We have discussed how a new slot can be defined; con· sider now how a program is to know u.hcn,lfww to defi ne a new one. The new type of slot might be defined for purely exploratory reasons (e.g., it's aesthetic to define "first cousins" : the speciali:~:ations of the generalizations or a concept). The slot's definition might be based soundly upon need - or the absence of need. For ex­ ample, by monitoring usage, we might notice that many concepts have a large number of entries for their F slot, and infer that the F slot should be specialized into several new slots.

3.2. DYNAMICALLY MONITORING THE TASK ENVIRONMENT

Summary1 Tl1e previous section i/lw:t.rot t ed how a program might profit from knowl~dse it g~throrerl dynamically. This suggests that ratl1er than wotlc · ing on the given problem exclusively, a program may be better off to expend some time learning (about ,the specific problem, its broader domain, or problem-solving in general). Note this suggestion would encompass traditional education (being told), empirical researcl1 (observing), and theoretical exploration (predicting) . While such "very high-level" problem-solving strategies typify human problem-solvers (especially those of us wl1o have rationalized spending twenty or more years "in school"), very lew programs to date have employed any of these forms of learning to improve their opera· tion.

4. CACHING

Summary1 "Caching" the results of computations can dramatically improve the performance of many programs. Reasoning can be brought to bear to decide whether to cache, if so what to remember, and (later) whether or not to ignore the cached value and recom· pute it. We often refer differently to "caching" depend· ing upon what it is that 's being retained: open-ended, inductive searches can be condensed in hindsigl1t (i .e. cached) into heuristics, deductive searches can be cached into much less branchy algorithms, subroutines can be cached into tables of frequently called arguments and resultant values, and variable quantities have their value cached simply by the process of binding.

Hardware designers have long recognized the tremen· dous gain in efficiency affordable by ctU'hing: recording a result, at least temporarily, in case it is called for again soon. Here we consider an analogous technique: (Jt)jtware caching. The simplest ca~;e occurs just after com· puting F(x), for some function F called with argument x: simply store the value returned. Whenever F is later called, check first to see if a cached value is stored.

A more sophisticated kind of caching would involve saving information about the proce&& of computing F(x), the path that was followed, the traps, the blind al· leys, the overall type of successful approach, etc. The analogue in Search is to have the subtr~r.s intercom· municate.

To illustrate the process of caching values, consider again our old access, (GET PRIMES GENERALIZATIONS) . After computing (PRIMES NUMJlERS ODJECTS ANYTIIING) as the answer, Eurisko simply st.ores that list as the value of the GENERALIZATIONS attribute of PRIMES. Jf the same call to GET is rei11sued, it tries to access this very spot. Though it had failed previously, it now would succeed, and it would return Lhr. cached list almost instantly. Thus, with but a small one-time cost, our program might run as quickly as if all slots were primitive.

Note that in originally computing Generalizations of Primes, it. was necessary to call for (GET GENERALIZATIONS DBFN), and the value of this virtual slot was also computed. The Eurisko policy is to cache this value also. It is useful be.cause, when a request such as (GET DUCK GBNERALIZATIONS) is received, it would otherwise have to be recomputed all over again. The definitions of slots arc very slowly- if ever- changing, hence the recomputation of Ddn of Gene.ralizations is quite a rare event. Caching that value must be cost· effective in the long run.

In general, we sec that caching a value for slot F of concept Cis most. applicable when the value can be ex· pccted to vary quite infrequently. In Eurisko, this gives us the flexibility to redefine a slot's definition if we wish, but (since this change of representation will be rare) the program will run jUf;t about as efTicicnUy as if that capability were absent . This is analogous to compiling: so long as the definition or a function doesn't change too oft.en, it's undisputcdly wortl;awhile to compile it.

What happenil if the value doc& change? Eurisko handles this in a passive manner: it doesn't attempt to maintain a completely consistent, up-to-date knowledge base. Rather, when a call on GET is executed, and a cached value is encountered, a formula then determines whether to accept that cache, or to ignore it and recompute a fresher value. Each call on GET is supplied with a few extra parameters which specify how much cpu time and space are budgeted for this particular function call, whether the user may be queried about this, how recent a cache must be to be acceptable, and a minimum amount of resources which must have been expended at the time the cache was written.

So (GET PRIMES GENERALIZATIONS 200 40 NIL 3 0) would allow any cached value to be accepted if it ap­ peared that recomputing would take more than 200 mil­ liseconds, or would use up more than 40 list cells, or if the value had been put there less than three Tasks ago. Otherwise, the cache would be ignored, a newer value would be computed, and it would be stored away. With it would al110 be recorded the following information: (i) the fact that it was a cached value, not a primitive one, (ii) how long it took to compute, (iii) how many list cells it used up in computing this value, (iv) the current Task number. The above call on GET might result in the following value being stored on the GENERALIZATIONS slot of PRIMES: (·cache· (PRIMES NUMBERS OBJECTS ANYTHING) 54 6 II).

(At thi· point in (!I) cornu a discuuion contrasting our ldeu with psycholo&lcalldeas of economy. Similarly omitted here Is a len&thy section contalnln& heuristics for Storlnc and Updatlnc cached valuu: when (not) t.o, how t.o, and what t.o.)

5. Expectation-Filtering

Summar)': For efficiency's sake, o1n intelligent system should be willing and able to add new facts, but should be eager to add surprising new facts. Surprises can only be noticed by contrast with expectations, so an intelligent system should maintain a context of expectations and filter incoming observatiom against that. Furtl1ermorc, expectations and surprises co1n aid an intelligent system in comparing its model and processing of the domain to tl1e real world. Tl~rough such monitoring, discrepencies may be found and diagnosed, leading to change!J in the model making it more consistent with observed be­ havior. Such expectations can be used to focus and filter intelligent processing.

6. CONCLUSIONS

Summorya We identified tl~ree cltaracteristicll that serve the needs of intelligent adaptation. Firllt, we showed tltat most inferential systems can benefit from learning about their task environment and their own behavior. For example, tl1ey c.1n exploit new schemata or different slot-names to simplify and rel'tructure their knowledge. Second, tlte need to explore large search spaces with some repetitive regularity motivates the use of cach­ ing to save partial results. We described a variety of tcchniquCJJ to implement caclting, and explained how caching specific results is one of a spectrum of methods tltat can make tradc-offs among precision, speed, cer· tainty, and generality. Tlte third dynamic capability we identified was ex,x:ckllion-fiJicring. In general, intel· ligent systems need to exploit their knowledge about typicality to reduce tlteir cognitive load and increase Uteir attention to important data. In many situations, we believe that expectations can both reduce process· ing requirements for handling ordinary events as well as simplify the identification of surprising events.

In the years to come, AI programs will employ greatly expanded knowledge bases and, as a consequence, they will explore increasingly open-ended problem spaces. Already, a few existing systems show signa of having more potentially interc11ting things to do than they have rCRources to pursue (e.g., AM, Eurisko). In the past decades of intelligent systems R&D, several design con­ cepts have emerged in reRponRe to contemporary needs for creating ever larJtcr knowledJte bases. For example, many researchers proposed multiple levels of abstrac· tion and automatic property inheritance a11 keystones of efficiency or "cognitive economy:" We believe that the value of such mechanism A derives largely from their usefulness in describing initial knowledge ba~~es . Once an intelligent system begins to explore the consequences of its knowledge and to solve novel problems in a dynamic environment, it needs to adapt ita knowledge to achieve faster and more profitable retrievals.

A theory of cognitive economy should explain why knowledge needs to be adapted and should prescribe how to do it. In this paper, we have tried to lay the groundwork for such a theory.

In conclusion, we have tried to show what cognitive economy i6 and i6 not. It docs not' consist of a set of static knowledge-base design principles; such as tho11e proposing taxonomic concept structures with automatic property inheritance. Rather, cognitive economy is a feature of those intelligent systems that learn to solve problema efficiently and consec1uently realize more of their lifetime potential. Toward that end, we have proposed an initial act of three basic design charac­ teristics. We anticipate these characteristics will find widespread application in many future AI tiysternR. Ae knowledge bases expand and basic software obstacles arc overcome, AI systems will increasingly address the same question facing intelligent humans: "What would I most like to accomplish next, and how can I do that economically?"

Acknowledgements

We wish to thank Dave Barstow, John Seely Brown, Bruce Buchanan, Ed Feigenbaum, Cordell Green, Greg Harris, Barbara Hayes-Roth, Allen Newell , Herbert Simon, and Don Waterman for several discussions which have left their mark in this paper.