A Case Study of Knowledge Representation in UC

1. Introduction

UC, the UNIX· Consultant, is a natural language program that converses in English with users in the domain of the UNIX operating system. UC provides information on usage of system utilities, UNIX terminology, and plans for accomplishing specific tasks in the UNIX environment, all upon direct query by the user. In order to accom­ plish these tasks, UC must perforce have a considerable knowledge base, a large part of which is particular to the UNIX domain. The specific representations used in this knowledge base are essential to the successful operation of UC. Not only are the knowledge struc­ tures used in parsing, inference, planning, goal detection, and genera­ tion , but also the format of representation must permit the high efficiency in access and proce88ing of the knowledge that is required in an interactive system like UC. This paper deseribes the details of this representation scheme and how it manages to satisfy these goals of usability and efficiency. An overview of the UC system can be found in Wilensky (1Q82). For an introduction to the knowledge structures in UC, see Chin (1983). In contrast, a totally different approach to the same problem domain is described in Douglass and Hegner (1982).

1. The Repreaentatlon

UC uses a framelike representation where some of the contents are based on Schank's conceptual dependencies. The knowledge struc­ tures are stored in PEARL databases (PEARL is an AI package developed at Berkeley that provides efficient access to Lisp represen­ tations through hashing mechanisms, c.f. Deering, et. al ., 1Q81 and 1982). Since the knowledge to be represented is highly domain dependent, it is instructive to look at the range of queries that may be encountered by a UNIX consultant. The following dialogue is taken from actual UC sessions:

User: How can I delete a directory!

UC: To delete a directory with name directory name, type ' rm directory name '.

t Thio re,.&rch wu opoaoored ia pan by the Olice of N&nl Reoeud onder coDtrad NOOOJ4-8().C~732 &ad the NatiouJ ScieDce Fond&tioa under craat 1ST -8007Q.I5.

· UNIX ia tr&dem&rk of Bell L&bor&torieo

Once the input is parsed, UC which is a data driven program looks in its data base to find out what to do with the representation of the input. An auertlon frame would normally result in additions to the database and an Imperative might result in actions (depending on the goal analysis). In this case, when UC sees a question about why someone is unable to do something, it interprets this as a statement that the user failed to perform the action, and that it should check the preconditions for the plan Cor that action. This knowledge is aU encoded associatively in a memoey-auoelatlon frame where the recall-key is the associative component and the cluster slot contains a set of structures which are associated with the structure in the recall-key slot.

(memory-association (recall-key (question (cd (causation (antecedent ·unknown·) (consequent (able (actor !person) (value unable) (perform !act))))))) (cluster ((fail (cd !act)) (goal (planner !person) (objective !states)) (assertion (cd (planfor (result !states) (method !plan)))) (check-preconds (cd !plan)))))

The above memory-association circumvents the need to infer that the user failed, to delete the directory, that the user has a ~~ and there is a plan carrying out the objectives of that goal. Ill UC, knowledge about plans is encoded in a large number of planfor frames which are used almost directly to handle informational queries about UNIX commands. In this example the usage or the plan is less direct since UC must check the preconditions for that plan. This intention is stored in the check-precond· frame.

The plan itselr was actually activated earlier when "deleting the directory Tmp" was parsed and a memory-association reminded UC of the following plan for deleting the directory, Tmp, which was instantiated by unification with the patterns in the general planfor deleting directories:

(planfor (result (state-change (actor directory3) (state-name physical-state) (from existing) (to non-existing))) (method (mtrans (actor ·user·) (object (command (name rmdir) (from ·user·) (to ·Unix·)))) (args (Tmp)) (input ·stdin·) (output ·stdout·) (diagnostic ·stdout· )))

When UC processes the check-preconds, it looks for a precond· frame for the given plan and checks the preconditions listed therein:

(preconds (plan (mtrans (actor !user)

(object (command (name rmdir) (from !user) (to ·Unix·))) (args (!directoryname)) (input ·stdin·) (output ·stdout·) (diagnostic ·stdout·))) (are ((state (actor (aU (var !file) (desc (file)) (pred (inside-or (object !directory))))) (state-name physical-state) (value non-existin_g)) )))

One precondition in this case is that the directory must be empty before it can be deleted. Upon querying UNIX directly, UC deter­ mines that this precondition is not satisfied, so it generates a message using the Phred generator (Jacobs, 1983) to inform the user of this fact . or course if this precondition was not the problem, uc would continue to check the rest. Also in multi-step plans, UC would make sure that the steps were carried out in the proper order.

The informational query of "How can I delete a directory" is handled in an even more straight forward way. It is first parsed into a ques­ tion frame:

(question (cd (planfor (result (state-change (actor directory4) (state-name physical-state) (from existing) (to non-existing))) (method ·unknown·)))) Then the following memory-association directs UC to look for an out-planfor frame whenever a question about how to do something (expressed as a planfor with an unknown method) is encountered: (memory-association (recall-key (question (cd (planfor (result !cone) (method ·unknown·))))) (cluster ((out-planfor (query !cone) (plan !·any· )))))

The meaning of an out-planfor is that an answer to the query in the query slot is to simply execute the plan in the plan slot. Theoreti­ cally out-planfors represent compiled answers to queries which the expert consultant has encountered so often that an immediate solu­ tion is already available.

(out-planfor (query (state-change (actor ?directory) (state-name physical-state) (from existing) (to non-existing))) (plan (output (cd (planforlg)))))

In this case, the plan in the out-planfor is an output frame, the con­ tents or which are passed to the generator. PlanCorlg in the output frame is the general version of the planfor shown in the previous dis­ cu55ion. Ill more complex queries where UC does not have an out­ planfor compiled away, the problem or creating a plan to handle that particular situation is done by the planning component or UC, Pan­ dora (Faletti, 1gg2).

The proce55ing or queries about terminology r('quires a somewhat different approach. Definitions are actually generated from basic knowledge. For example, the definition or a directory uses the fact that a directory is a kind or file in the type hierarchy or frames in UC. Also, used is the fact that a direct~ry is a kind of functional­ object all of which have function·. The function or directories is to hold files. Although it would be poseible Cor a consultant like UC to have definitions "compiled" away in its memory, it was Celt that requests Cor definitions are so rare that this was unlikely, so UC gen­ erates all definitions from scratch.

4. Auoclatlve Proceulns for EMclenc;y

A common theme in the knowledge representation or UC is the use oC associative proce55ing to achieve efficiency. IDstead oC potentially exponential cost inference engines, the knowledge structures in UC are designed to provide direct associations among relevant knowledge. For example, planCors provide immediate links between plans and their elects, out-planCors connect common queries to their generator ready outputs, and memory-associations provide a general mechanism Cor associative links or almost any kind.

Although computational methods of inference are undoubted still needed and desired, the premise taken in UC is that most common everyday inferences made by humans are not computational but rather fall out of the structure of memory. This can be modeled in AI programs like UC through appropriate design of knowledge representations.

Lacking true associative memory, UC uses the hash indexing pro­ vided in PEARL databases to simulate associative access. Frames stored in PEARL databases are indexed by combinations of the frame type and/or the contents of selected slots. For instance, the planfor of the example is indexed using a hash key based on the state-change in the planfor's result slot. It is stored by the fact that it is a planfor for the state-change or a directory's physical-state. This degree of detail in the indexing scheme allows this planfor to be immediately recovered whenever a ref~rence is made to deleting a directory.

Similarly, a memory-association is indexed by the filler of the recall­ key slot, an out-planfor is indexed using the contents of the query slot of the out-planfor, and a preconds is indexed by the plan in the plan slot of the preconds. Indeed all knowledge structures in UC have associated with them one or more indexing schemes which specify how to generate hashing keys for storage or the knowledge structure in the UC databases. These indexing methods are specified at the time that the knowledge structures are defined. Thus although care must be taken to choose good indexing schemes when defining the structure of a frame, the indexing scheme is used automatically whenever another instance or the frame is added to the UC databases. Also, even though the indexing schemes for large structures like planfors involve many levels or embedded slots and frames, simpler knowledge structures usually have simpler indexing schemes. For example, the representation for users in UC are stored in two ways: by the fact that they are users and have a specific account name, and by the fact that they are users and have some given real name. Thus although extra work must be done to work out usable and efficient hash indexing schemes for structures, the gain in processing effici~ncy is well worthwhile.

&. Technical Data

UC is a working system which is still under development. In size, UC is currently two and a half megabytes or which half a megabyte is FRANZ lisp. Since the knowledge base is still growing, it is uncer­ tain how much of an impact even more knowledge will have on the system especially when the program becomes too large to fit in main memory. In efficiency, queries to UC take between two and seven seconds or CPU time on a VAX ll/78JJ. Currently, all the knowledge in UC is hand coded, however efforts are under way to automate the process.

e. Acknowledamenta

Some or the knowledge structures used in UC are refinements or for­ mats developed by Joe Faletti and Peter Norvig. Yigal Arens is responsible for the underlying memory structure used in UC (Arens, 1982) and or course, this project would not be possible without the guidance and advice of Robert Wilensky.

7. Reference·

Arens, Y. 1982. The Context Model: Language Understand­ ing in Context. In the Proceeding8 of the Fourth Annu<JI Conference of the Cognitit·e Science Societu. Ann Arbor, MI. August 1982.

Chin, D. 1983. Knowledge Structures in UC, the UNIX Con­ sultant. In the Proceeding8 of the £18! Annu<JI Meeting of the Auociation for Computation<JI Linguistic8. Boston, MA. June, 1983.

Deering, M., J. Faletti, and R. Wilensky. 1981. PEJ\RL: An Efficient Language for Artificial Intelligence Programming. In the Proceedings of the Seventh Inlernation<JI Joint Conference on Artifici<JI Int elligence. Vancouver, British Columbia. August, 1981.

Deering, M., J. Faletti, and R. Wilensky. 1982. The PEARL Users Manual. Berkeley Electronic Research Laboratory Memorandum No. UCB/ERL/M82/19. March, 1982.

Douglass, R., and S. Hegner. 1982. An Expert Consultant for the Unix System: Bridging the Gap Between the User and Command Language Semantics. In the Proceedings of the Fourth National Conference of Conadi<Jn Societufor Computa­ tional Studies of Intelligence. University of Saskatchewan, Saskatoon, Canada. ·

Faletti, J. 1982. PANDORA -- A Program for Doing Com­ monsense Planning in Complex Situations. In the Proceedings of the National Conference on Artificial Intelligence. Pitts­ burgh, P A. August, 1982.

Jacobs, P. 1983. Generation ill a Natural Language Interface. In the Proceedings of the Eighth Inlern<Jiion<JI Joint Conference on Artifici<JI Intelligence. Karl&ruhe, Germany. August, 1983.

Wilensky, R. 1982. Talking to UNIX in English: An Overview of UC. In the Proceedings of the Nation<JI Conference on Artificial Intelligence. Pittsburgh, PA. August, 1982.

Wilensky, R. 198l{b). A Knowledge-based Approach to Natural Language Processing: A Progress Report. In the ProceedingB of the Set,enth Int ern<Jtional Joint Conference on Artificial Intelligence. Vancouver, British Columbia. August, 1981.

Wilensky, R., and Arens, Y. 1980(a). PHHA!\ -- a Knowledg~Based Natural Language Undcrstander. In the Proceeding8 of the 18th Annu<JI Meeting of the AsBociation for Computational LinguiBtics. Philadelphia, PA.

Wilensky, R., and Arens, Y. 198o(b). PHRAN- a Knowledge Based Approach to Natural Language Analysis. University of California at Berkeley, Electronic Research Laboratory Memorandum No. UCB/ERL M8JJ/34.