Extracting Knowledge From Expert Systems

1. Introduction

If those cf us involved in expert systems research have a common goal, surely it is to understand how to use large amounts of knowledge in solving problems. We have made some progress. In the l970"s progress promised to be rapid; a small number of interesting systems were developed, and their developers described the tasks the systems could perforrn and the var ious techniques used. Over the past few yt:ars, many more peorle have become involved , and expert systems are now springing Ufl all over. Unfortunately, this dramatic growth in the number of expert systems has not, as far as I can see, been accompanied by even a modest growth in our understanding of tlk relationship between knowledye and search. The problem is a lack of data. Though the number of expert systems that huve been developed is now sufficient to allow us to begin to deepen our understanding, the information available about those systems is inadequate.

I am aware of only a few attempts to draw general lessons from an examination of a number of expert systems. A paper by Feigenbaum focuses on several of the systems developed at Stanfrxd's Heuristic Programming Project (Feigenbaum "17]. Although the paper gives some indication of the nature of the task each system addresses, its primary purpose is to provide an existence proof that the by now well known tools of the knowledge engineer can be used with success in a variety of domains. More recently, a group of experienced expert system builders wrote a paper which offers a map linking task characteristics with techniques for solving the task [Stefik 82] ; the paper is one of the chapters in a forthcoming book on expert systems [Hayes-Roth 83]. While t11e paper will be a valuable guide to people trying to construct AI application systems, several of the systems discussed are by no stretch of the imagination knowledge-based; thus the relaticmship between some of the prescribed techniques and knowledge­ intensive tasks is not at al l clear. Two other works containing the insights of experienced expert systems builders will soon be avai lable [Buchanan 83a], [Buchanan 83b]. Though both works provide a number of important insights, they focus almost exclusively on a single task domain. Neither indicates very clearly the scope of the various lessons learned.

This paper assumes that what distinguishes expert systems from other AI systems (and hence what makes them interesting) is that they bring relatively large amounts of knowledge to bear in solving problems. The claim made here is that a few basic aspects of task domains are the sources of the signifi cant variety one finds among expert systems. If systems are described in terms of these aspects, we will gain an understanding of the various roles knowledge can play an<.l an appreciation oi the factors that define these roles. In the next section , four aspects of task domains are identified, and then in the third section, three expert systems are described in terms of those aspects. On the basis of these descriptions, several hypotheses about knowledge and its r<Jies in problem solving are generated. The four aspects identified are supposed to be taken seriously; though the set is undoubtedly incomplete, we cannot understand the roles knowledge plays in problem solving without attending to those four aspects. The hypotheses are not to be taken seriously; their function is to suggest what we might learn about knowledge if we had a large number of systems to serve as data points. Since each hypothesis was generated on the basis of at most three data points, all any of them can do is tentatively point the way.

2. Figuring out the questions

In order to understand the roles knowledge plays in any particular task domain, it is necessary to know at least the following sorts of things ahout the task:

• Compartmentalizability of the task knowledge.
• Uncertainty of the task information.
• Applicability of the task knowledge.
• Thickness of the task knowledge.

How and to what extent task knowledge can be compartmentalized depends almost exclusively on the structure of the task; the more compartmentalized the knowledge, the narrower its scope and the simpler the choice of what pieces of knowledge to apply. Knowledge operates on informalion made available by the task environment; the more uncertain that i:1formation, the less control the knowledge has. Each pi ece of knowledge has limited applicability; a piece of knowledge is more or less povicrful depending on how precisely it specifies the set of situations in which it is �pplic~blc. Finally, many different pieces of knowledge may be relevant in the same si tuation; the thicker the task knowledge. the more knowledge there is to bring to bear at any uiven time. The rest of this section further eluborates each of these aspects.

2 . 1 . The cornpartmentalizability of knowledge

Before much sense can be made of compartmentalizability, it is necessary to find a structure that can serve as a compartment. One plausible structure is the subtask. When human experts talk about what they do, they frequently first locate themselves by naming some subtask and then indicate what conditions have to be satisfied in order for some behavior to be appropriate. The subtask name appears to stand for a set of conditions all of which must be satisfied before any of the behaviors associated with that subtask are appropriate. Typically subtasks are organized hierarchically; higher level subtasks are partitioned into a set of smaller, more focused subtasks. It is not clear what the criteria for being a primitive subtask are; presumeably experts differ somewhat with respect to the level to which they decompose the task. But since experts can communicate successfully with others using subtasl~ names, it is unlikely that the decompositions differ to a very great extent. Pieces of knowledge with the same common set of applicability conditions are distinguished from other pieces of knowledge associated with other subtasks. But within the subtask there are no such obvious boundries; in that sense, all of the knowledge associated with lfle subtask is potentially relevant whenever the subtask is being performed.

Human e:<perts are not at all good at estimating how much knowledge is associated with each subtask. And in fact there is no apparent way of getting a reasonable estimate that does not involve building a system which performs the task. Without an estimate of the amount of knowledge associated with each subtask, it is impossible to understand the access requiremen ts the task imposes. If there is very little knowledge associated with each subtask, it may be rossible to statically impose a structure on that knowledge. The more knowledge that is relevant to a subtask. the more likely it is that there will be issues of how to determine dynamically when to apply which pieces of knowledge.

2.2. The uncertainty of information

Two ways in which the task environment strongly shapes the nature of the task are with ( 1) the reliability of the data it provides, and (2) the points in time, relat ive to the task, at which the data become available. The unreliability of data is a more or less serious issue depending on a variety of fac tors. If the agent can assume the data are correct (whether or not they are), then true reliability is irrelevant. If the task environment provides a measure of reliability for each datum, then (unless the measure is itself unreliable) reliability is only a minor issue. If there is ambiguity about the reliabi lity of at least some of the data, but there are ways of determining whether a dttlum is incorrect within the time frame imposed by the task, then although data reliability is a S')rious issue, it is at least more tractabl e than the case in which unreliability cannot be recognized.

If the task environment provides additional data to the agent during the course of the task, it makes a difference who iniliates whatever interaction there might be. If the tasl<. environment is passive and interactions are initiated only by the agent, the most significant question is what information does the agent have access to (eg, can the agent ask for new information and clarification or confirmation of data already provided?) If the task environment is active and intitiates interactions with the agent, the issue is whether new data can conflict with data provided earlier; if so, a significant question is whether the conflicting data are generated independently of what is happening in the task or because of the effects of the task on the task environment.

2.3. The applicability of knowledge

In any given situation, an agent may have some pieces of knowledge it is certain are applicable, other pieces of knowl edge it suspects may be applicable, and presumeably a great deal of knowledge it is certain is not applicable. 1 will use the term "applicability factor" to distinguish among these three cases. If the conditions on the applicability of an action h1-1ve an applicability factor of 1, performing the action will re~;u lt in a transition to a state that is on a solut ion path. If the conditions of applicability have an applicability factor less than 1 but greater than 0, there is some likelihood that performing the action will result in a transition to a state on a solution path . But an applicability factor less than 1 signals that if the ngent performs the action, it may have to backtrack.

There are three reasons why an agent might misuse its knowledge: (1) the agent does not have sufficient information about the current situation (ie. the conditions of ap,)licability on an action are not satisf ied), (2) it has misleading information about the current situation, or (3) it does not know the precise conditions under which its knowledge is relevant (ie, the appli cability fac tor is less than 1) . In the first case, if the ayent can recognize when rt is lacking such information and can get the existing information from its ex ternal environment, it will not fail to apply relev;111t knowledge. In the third case, it may be that the agent is simply ignorant; if the condi tions under which the knowledge is relevant can he more pr 8cisely defined. then the conditions of applicabi lity may be <:ble to be elalwraterl to the point that the applicability factor becomes 1; see [Dr,yle 83] for a more thorounh discussion of this point. However, if the condi tions under which a piece of kntJwledge is relevant are highly complex or if no one knows them, the possihility of mi:>applying the knowledge will remain. In such cases it r.1ay be pos::;ible to extract from an ex[Jert or otherwise acquire a rt:asonably accurate measure of the likelihood that <Jflplying tire l'.nowlcdge ·Nil! result in a state on the solution path; if so. the applicability factor can be taken into account !n guiding the search.

It is important to distinguish between tasks in which the agent can know when it has accomplished the task (achieved its goal) and task. in which this is not possible. In tasks in which the <:~gent uses only knowledge whose applic;·.bility factor is 1, it knows when it hGs accomplished its task because it sees there is nothing more to do. In tasks where some or all of the knowledge used has an applicability factor less than 1, if the agent knows enough about its goal to determine whether it is on a path leading to that goal , then although it may have to search extensively, it will recogni ze when it has achieved the goal; in such cases, the only role for applicability factors is to make search more efficient. In tasks in which the agent cannot know whether it has achieved its goal, the appl icabili ty factors not only can help direct the search , but cun also serve as indirect measures of the likelihood that the goal has been achieved.

2.4. The thickness of knowledge

Task knowledge is thick if the same situations can evoke a wide variety of actions depending on the agent's meta-goals. If, for example, the agent can deal with its task at a number of levels of abstraction, its knowledge is thicker than that of an agent who can deal with the tasl\ at fewer levels of abstraction. A more interesting example of how the same situation can invoke different knowledge arises when we ask how the association between an ac~ion and the conditions of applicability on that action are justified. If someone who claims some piece of knowledge K is always relevant in situation S is asked to justify that claim, the knowledge K' that is used as justification is also relevant in situation S; K' has the same function as K, but presumeably is more basic and thus relev;:wt in many situations besides S. At the limit is analogy. If proulcms that arise while a task is being performed can be solved ·.vith k110wledge having no direct connection to the task, endless opportunities for creative problem solving open up.

3. Converting expert systems to data points

In this section, the aspects of task domains identified above are used to analyze three knowledge-IJased systems; the results of the analyses are several hypotheses about the effects on problem solving competence of large amounts of domain knowledge. Since only three systems are considered, the analyses will collectively prove to be woefully inadequate, and the hypotheses will be at best suggestive. It will hopefully be clear, however, that if the set of aspects were extended a bit and if fifty or a hundred data points were u.;;ed instead of three, a number of interesting hypotheses could be generated.

The three systems we will consider were (or are being) developed at CMU for Digital Equipment Corporation. R1 is a computer system con fi 'Jurer (McDnmott 82<~]; given a set of components, it adds any support components that might be missing and determines what the spatial relationship among all ot the components should be. XSEL is a salesperson's assistant [McDermott 82b]: it helps the salesperson select a set of components tailored to the customer's needs a.nd design a floor layout for the resulting system. The XSEL user can call on R1 to configure or reconfigure the current set of component selections and can provide infOI'mation to R1 which insures that the resulting configuration will satisfy speci<!l requirements of individual customers [McDermott 81]. PTRANS is a manufacturing management assistant [Haley 83]; it helps insure that the inevi table problems which arise and threaten to delay the delivery of sys tems to customers are resolved satisfactorily. In time, XSEL will interact with PTRANS so that a delivery date can be confirmed as soon as an order is booked.

R1 's original task was to generate the configuration diagram and do the order-completeness checking required before a VAX-11 order could be built in one of Digital's final assembly and test plants; the original version of R 1 was tested in the Fall of 1979 and began to be used on a regular basis in January, 1980, to configure all 'VAX-11 orders. The information available to R1 consisted of just the set of components (line· items) ordered by the customer; no information was available about how the customer intended to use various components or how he intended to lay them out on the floor. As XSEL. was being developed, it became clear that it cou ld collect and pass on to R1 information that would enable R1 to tailor its configurations to the requirements of individual customers; consequently, R1 was extended to be able to use this additional information. More recently R 1 's knowledge has ty~en augmented , by developers at Digital , so that it ca<1 now confi~1ure systems other t11an the VAX-11. The version of Rl discussed below is the version currently used by Digital.

XSEL's development is occurring in two stagns. Tile initial version of the system assists salespeople with both component selection and floor layout de~ign; the assistance provided in component selection assumes the user already has a good appreciation of the customer's computing needs. This version of XSEL began to be field tested in May, 1983. Though its capabilities have been strongly sh:.\Ped by a user­ design group which w::~s formed early in its development , no significant redefinition of XSEL's task has occurred. A major extension to XSEL is being developed at CMU; the extended system will be an expert in sizing a customer's computing needs. The version of XSEL discussed in this paper is the version which includes the yet to be refined sizing capability.

PTRANS will ultimately be able to assist with the management tasks that arise from the time an order is receiveJ by Digital's manuf<lctu,ing organization until it is delivered to the customer. The initial version of PTRANS, however, deals only with rnanagem0nt issues which arise in final assembly and test plants. These plants build complex systems from components produced by high-volume plants. The principal management tasks are determining when ancl where on the floor to build each system, insuring that the necessary parts are on hand when it is time to issue them to the floor , and tracking the proyr. ~ ss of each system on the floor so th<Jt problems can be resolved as they arise. In order to perform these tasks, PTnANS must be able to construct plans and then modify these plans appropriately as unforeseen circurnst8nces arise. The initial version of ?TRANS began to be tested at Digital in July, 1983, and is the version discussed in this paper.

All three of these systems are implemented in OPS5 [Forgy 81]. OPS5 is a general-purpose rule-based language; like other rule-based languages, OPS5 provides a rule memory, a global working memory, and an interpreter which tests the rules to determine which ones are satisfied by the descriptions in working memory. An OPS5 rule is an IF-THEN statement consisting of a set of patterns which can be matched by the descriptions in working memory and a set of actions which modify working memory when the rule is applied. On each cycle. tile interpreter selects a satisfied rule and applies it. Since :.~pplying a rule results in changes to working memory, different subsets of rules are satisfied on successive cycles. OPS5 does not impose any organization on rule memory; all rules are evaluated on every cycle.

:3.1. Tho compartmentalizability of knowledge

Fl1 's 280 subtasks conform rtuite closely to the 200 300 subtasl·.s human configuration experts identify. 111 has about 2<100 rules distributed among these 280 subtasks. On the average, then, tlwre are 9 rules (piece::; of domain knowledge) associated with each subtask; thouqh there is some variation in the amount of knowledge asso<;iated with each subtask, for most of the subtasks there are between 5 and 15 relevant rules, and no subtask has more than 30 rules associated with it. Typically 2 or 3 of the rules associated with each subtask recogni ze when other subtasks must be performed and enable those subtasks by depositing the subtask names in working memory. Almost none of Fl1 's knowledge is relevant to more than one subtask.

XSEL has about 3000 rules distributed among 289 subtasks. All but about 30 of ils rules are relevant to only a single sub task; thus, on the average, there are about 10 rules associated with ec~ch subtask. At any given time, typically 2 of the 30 rule~; relevant to more than one subtask are potentially rlolevant. Thus the total number of ru!es potentially relevant at any given time is, on the average, about 12.

The tasks PTRANS assists with are performed simultaneously by a number of different people. The responsibility of some of these agents is to insure that the information other agents use is as accurate as possible. Since these monitoring tasks a:·e not associated exclusively with any particular part of the process, their relevance comes and goes as the various tasks which rely on the monitoring tasks come and go. PHlANS has about 1'100 rules. Approximately 700 of these are distributed among 175 subtasks; thus there are about 4 rules associated with each subtask. At any given time, 34 of the 700 rules relevant to more than one subtask are potentially relevant. Thus the total number of rules potentially relevant at any given time is, on the average, about 38. The 34 demon rules associated with each task are not easily compartmentalized. The mean number of demons that any two subtasks have in common is 4.3 and the mode is 2; a few subtasks have no demons in common and a few have more than 20 in common. Thus whatever structure might characterize the interrelationships among the demons, it appears to have nothing to do with the task structure. We have had little success so far in identifying any organizational principles at all.

One might expect in tasks like the configuration task, which have a fairly well-defined structure, that only a relatively small amount of knowledge would be potentially relevant at any given time. But the data for all three systems appears to support the following hypothesis:

H1: Only a relatively small amount of an expc}rt's knowledge is potentially relevant in any given situation.

Tlie intriguing question is to wh~t extent this is true of more general problem solvers. It would seern plausible that in domains in which there is not a clear focus 011 <.1 s1roall set of issues (ie, in wl1ich there are not st~ong expectations about what set of events might occur), much more knowledge would be potentially relevar1t. What is not at all clear is how much more and whether there is anything at al l in common between the sort of compartmentalization of knowledge that we find in expert systems anu that which we could expect to find in general problem solvers.

Since the only system with a significant amount of knowledge not associated VJith specific subtasl1s is PTRANS and since the knowledge it has that is not associated with specific subtasks appears to be structureless, a possible hypothesis is:

H2: Subtasks organizing knowledge. serve as principle the for an dominant expert's

Much of the knowleJge that an expert has appears to be relevant in the context of only a single subtask. Decause subtasks often form a i1ierarcl1y. this is not quite as restrictive as it rnay sound ; knowledue that is relevant in seve r ·~! subtasks will be ass·Jciated with a hig!11er levr; l, subsuming subtask. When a piece cJf know!edge is useful in ::t variety of subtasks that have no common ~ncestor, there is no obvious way to characterize the relatioo1Ship amonn those uses.

3 .2. The uncert:1inty of information

Dee<wse the configuration task as originally defined for R 1 did not include direc t interaction with a salesperson or customer, the only data available to Rl was that provided at the beginning of the task. This input consists of a list of quantity/component-narne pairs and sometimes other information describing customer-specific configuration requirements. The major uncertainty associated with the data is whether the set of specified comronents a1·e orderable, play together , and are complete; and these uncertainties are precisely those which the t<Jsk is there to resolve. Any changes to the order, or additional information which a salesperson or customer might want to provide, occur after the task has been performed; such changes define a new configuration task, rather than reflecting uncertainty in the data for the initial task.

Whether XSEL is providing assistance with component selection or with floor layout, it asks the user for some initial information. In the case of component selection, the in1ormation consists (possibly of a mixture) of direct and indirect meusures of the customer's computing needs together with an indication of how much the customer is willing to pay to satisfy those needs. In the case of floor layout, the information consists of descriptions of the rooms which will house the system and possibly customer preferences for the placement of some or al l of the components. In both cases, there are two ways in which the information provided is unreliable. ( 1) Viewed as a measurement, a piece of information can sirnply be incorrect; more frequently the measurement cannot be (eGsi ly) made with precision and thus the value provided is only an approximation. (2) Viewed as a constraint. a piece of information can be more or less significant: if the construints that define the customer's needs cannot all be simultaneously sati ~~ fi ecl , some of those constraints must be relaxed. It is sornetirnes important for XSEL to deal explicitly ·with these uncerta inties. When XSEL provides assistance in sizing a customer 's needs, for example, it keeps tract\ of tile expected precision of each value; thus when it encounters an inconsistency, it has information it can cse to determine which constraints to relax and how much to relax them.

Whenever P rRANS is asked to Gssist with the processing of an order, it is provided a standard set of initial information. Part of the information is R 1 's output along with other custo~ncr-related information· such as the desired delivery date. Th,~ other information PTRI\NS is provided is for the most part related to resource avaiiGbility (mater ials, floor space, etc). All of this inforrnnt10n is unreliable. If any of the custorno:r-rela ted information changes, a chan9e order is issued ; the change order indic<1tes what information has chvn;ted and what the new values are. Every resource has time information associated with it that indicates how much of the resource is expected to be available at specific points in the future; whenever an expectation changes. this information is updated. PTRANS is desi9ned to munage (create, implement , and modify) plans precisely because of these kinds of uncertilinties; that is, it is built on the premise that these uncertainties are inevitable and thus tries to cushion their impact rather than eliminate them. Becnuse it is impossible to predict the precise nature of the changes (customer and resource) that will occur and exactly where they will occur and because the number of possible changes is extremely large, PTRANS does not explicitly keep track of the uncertainties, but just adapts to the changes when they occur.

Since Rl , XSEL, and PTRANS all, though in different ways, directly address issues of data validity, a possible hypothesis is:

H3: An expert's task is almost always, at least in part, one ot data validation.

Since Rl 's task is to determine the completeness and configurability of a set of components, it is primarily a data validation task. XSEL's task often requires drawing the attention of the user to an inconsistency between the resources required and the desired purchase price. PTRANS task is primarily one of respondin9 opportunistically to more current, and thus presumeably more accurate, task information. In all three cases, the reason for the data validation is to simplify or avoid what would otherwise be impossibly complex problems.

Because the initial version of n 1 had no way of interacting with salespeople. when it discovered a problem with nn order, it had no way of getting the customer ·specific information it needed to resolve the problem: :hus a possible llypothesis is:

H4: Tasks which are defined in such a way that the environmen t cannot intrude after the task has begun should always be redefined to allow intrusion.

Until R1 's task was redefined , its only recourse when it encountered either a completeness or a configuration rroblem was to selec t one of the possible solutions somewhat arbitrarily. In the absence of additional data from the salesperson , it had to make a nun1ber of questionable assumptions.

3.3 . The applicability of knowledge

Though R 1 typically has about 9 rules that are potentially relevant at any given time, ordinarily only 2 or ~~ of those rules ha·Je condi t1ons that are fully satisfied. That a rule's conditiens are satisfied is <l necessrtry but not a sufficient conditio:\ for the rule to be applied. In addition a ru:e must satisfy OPSS's con flict resolution strateyi es; these str <:~ tcgies order rule instantiations on tile basis of conside:rations such as the recency of the data satisfying tlla rules nnd the n:l::.tive specificity of the rules. Almost all of R 1 's rules have an applicabiii ty f:Jctor of 1. That means if a rule's conditions are sntisfied and if that rule is net dominated by some other rule on t11e basis of OPS5's conflict resolution strategies, applying the rule will result in a transition to a state that is on a solution patl1 . Those pieces of R1 's knowledge that have an applicability factor less than 1 bear on unibus configuration. R1 is uncertain of the refevanc'e of some of its unibus con figuration knowledge because the relevance of the knowledge can only be judged after it is applied. R1 may, for example. begin to create a unibus configuration that turns out to be unacccp!CJble because there is insufficient space; when it recognizes such a si tuation it backtracks. In order for R1 to have unibus con figuration knowledge whose applicability factor is 1, it wou ld have to have knowledge which explicitly identified all valid (or all invalid) unibus configurations.

In many respects the applicability of XSEL's knowledge is very simi lar in character to R 1 's. Of the 12 or so rules that are potcmtially relevant at any yiven time, ordinarily only 2 or 3 are fully satisfied. Much of XSEL's knowledge has an applicability factor of 1. The kl)owledge that has an applicability factor less than 1 is that which maps from indirect to more direct measures of computing needs. This knowledge associates some (possibly very indirect) measure of a computing resource need with some set of cues. Since XSEL cannot verify the adequacy of its proposed sizings, it uses applicability factors not only to order its search, but to provide an indicati on to the user of the degree of variation in possibly acceptuble (correctly sized) computer systems. XSEL can recognize when sorne set of constwints appear to be inconsistent. Before asking the user to relax some of the constraints. it checks to see whether there is an interpretation of the constraints which makes them con~;istent.

How many of PTRANS' 38 potentially relevant rules are actually relevant on any given cycle depends to a great extent on whether any part of the environment is changing in an unexpected way. When the envi ronment is relatively stable, ordinarily only 1 or 2 rules are ac tually relevant; but when unexpected cl1anges occur , as many as 10 or 20 demon rules may also be relevant. Most of PTRANS' demon rules have an applicability factor of 1. Most of the ru!es associated with sub tasks have an 0pplicability factor less than I; this uncertainty manifests itself both in the form we saw in R1 and in the form we saw in XSEL. The knowledge PTRANS has that is like R 1 's unibus configuration knowledye is used to generate floor ·1ssignmonts; both tasks can be viewed as instances of the \Jenera! bin·packiny problem. The knowledge that is lil\e i<SEL's sizing knowiE:dge is used to estimate the amount of tin1e various events ;>rc going to take. XSCL and PTR.Al..JS must both predict the future performance of ·~ntities they neither fully understand nor control. However the tasks differ because what PTRi\NS predicts are events that will occur while it is performing its task; thus PTRi\NS can recognize when it has failed and recover by backtracking.

What is common to those subtasks in which R 1, XSEL, and PTRANS search is the relatively large number of different actions that can be appropriate; thus a possible hypothesis is:

• H5: If the situations in which an expert can find itself evoke a relatively small number of different behaviors, the pieces of knowledge that the expert uses to determine how to act in those si tuations will have an applicability factor of 1.

There are many different ways in which a large number of situations can be mapped onto a smal l number of behaviors. One that is fn~q uently useful for expert systems is to treat a large fraction of the situations as an equivalence class and single out a relatively small number of situations as special cases. Thus there are a few situations that are particularly interesting and the rest evoke an "ordinary" response.

Since R1 's domain is narrower than either XSEL's or PTRANS' and since most of R1 's knowledge has an applicability factor of 1, a possible hypothesis is:

• 1-16: The narrower the domain , the more likely it is that the expert will almost never search.

I suspect that this hypothesis is false. Currently, R1 is quite expert, seldom needs to search, and yet is able to discriminate among only 2500 different types of situations. XSEL, on the ot11er h:.md. is as yet much less expert, searches much more frequ·:::ntly, but is able to discriminate among 3000 different types of siiuations. It is possible that XSEL searches more than R 1 because its domain is not as nc:rrow. But it is likely, I think, thctt XSEL searches more because it is less well developed. I suspect that by the time XSEL has 9000 or 10,000 rules it will be as expert at computer system sizing as f~ 1 is at configuration and will do as little search.

3.4. The thi.-kness of knowledge

For the most part. R 1 deals with the world at a single level of abstraction Its knowledge is primarily <Jbout configurable components and their possible interrelcttionships. It does understand lhat the task it performs has a hierarchical decomposition, and it performs a variety of abstract tasks. But the knowltK:ge it uses to make its way around in those abstract tasks is still knowledge of confiumable components. Moreover, its !1nowledgc is single-level; it doe:> not know why its rul·:s (as opposed to 1ts conclusions) are valid. Though many of its rules could be justified on the bilsis of more ~wner<JI engin:=cring ~nowledge, a significant number could be f1illy just1f11od only by <lppealing to custom.

XSEL also ceals with the world at a single level cf abstraction ; but its level of <·.bstraction is somewhat higher thnn R 1 's. Whereas R I deals with individual configurable components, XSEL deals with sets of identical configurable components. Like R 1, XSEL cannot explain why its rules are valid. However it comes closer than R 1 to being able to do so. Its sizing rules associate indicators of need with descriptions of computing resources. Since XSEL has to interact with users of widely varying degrees of sophistication, these indicators vary widely in their clegree of generality. Highly unsophisticated users force XSEL back to first principles.

Because PTRANS' world changes so frequently, it deals with the distant future at a high level of abstraction in an effort to avoid getting bogged down in ephemeral details. It deals with the present and near future at a variety of levels of abstraction depending on the nature of its current subtask. To perform its various scheduling functions, it requires very little information about the objects it is dealing with. But to provide assembly and testing assistance to technicians, it must descend into a rococo world similar in rnnny respects to R·l 's. Like R1 and XSEL, PTRANS cannot explain why its rules are valid.

Since R1 deals with computer systems at a lower level of abstraction than XSEL and since R1 does almost no search, a possible hypothesis is:

• H7: The more abstract a piece of knowledge is relative to other knowledge about the same situation, the lower its applicability factor will be.

In order for a piece of knowledge to have an applicability factor of 1, it must be possible to specify prec isely the sit11ations in which the knowledge is relevant; tllat requirement delimits the base level of ahstraction for that piece of knowledge. If the knowledge is to be used in a more abstract space, not all of the information required to determine the applicability of the knowledge will be available.

Since R1, XSEL, and PTRANS all have quite thin knowledge and since all of them occassionally encounter problems they cannot resolve and all of them must do at least some search, a possible hypothesis is:

• HB: Thick knowledge reduces the nurnher of int··actable problems; it can also reduce the amount of search.

When a expert encounters a difficult problem, he can sometimes uncover the knowledge needed to solve the problem by trying to justify the~ knowledge ordinarily used to solve such problems. Pr.esumeably this strategy works because as different layers of knowledge are built up for different purposes, pieces of knowledge that wou ld be highly redundunt at some level are not included at that level ; these omissions reduce the size of the search space, but at the cost of incompleteness.

4. Concluding remarks

It occured to me, as I began working on this p::Jper , that it might have more validity if it included, as data points, systems from a wide variety of backgrounds, rather than jL:st ;,ysterns developed at CMU. As I pursued this idea, however, I discovered that the kind of system data I wanted is not very easy to find in the literature. That may, of course, be because the data I was looking for is not very valuable, or is odd, or is peculiar to a particular approach to developing systems. But I suspect not. The area of knowledge-based systems is new enough that we have not yet had time to define our needs. The purpose of this paper is not to define those needs, but to raise the issue and make some stabs.

One general point that I think does come through even from the narrow base I have provided is thut the analyses of expert systems and their tasks is likely to look quite different from that of classical search ·intcnsive systems and tasks. Knowledge is certainly used in t110s8 programs, but it is a very small amount of general knowledge, mostly with a low applicability factor.

Given juc: t the data available from R1 , XSEL, and PT8ANS, the hypotheses presented above ::~re not implausible. Rut mostly they an; simplistic. What is surely missing is an <!clequate amount cf data from which to generate substantive hypotheses. Though my shadow hypotheses lack substance, they do suggest the sort of advantages substantive hypotheses could confer. First, having a partial de~cription of a role that knowledge can play gives us something to refine and exploit or falsify: we can focus our efforts on pushing and sl1 :1ping promising insights. Second, substantive hypotheses also provide an avenue of discovery; given a set of hypotheses to reflect on , we are in a position to discover holes (approaches that have not been tried). But we are not going to have substantive hypotheses about the role of knowledge in problem solving unless our analyses of the expert systems we build lay bare the natures of their tasks.

Acknowledgements

The ideas in this paper have evolved as a result of discussions with many people. Helpful comments on earlier drafts were made by Danny Bobrow, Bruce Buchanan, Dick Duda, Bob Engelmore, Lee Erman, Paul Haley, Gary Kahn, Dave McKeown , Allen Newell , Dennis O'Connor, Ted Short liffe, and Mark Stefik; I um sorry to say that in several cases, I was not able to do justice to their suggestions. Paul Haley and Kemal Oflazcr helped with s01T1e of the data analysis.