Integrating Problem-Solving Methods into CYC

1 Introduction

Developing reusable ontologies which specify the struc­ ture and content of domain knowledge has become a central problem in the construction of large and scal­ able knowledge based systems. For example, a key step in KBS construction using the Cyc system [Lenat and Guha, 1990] is to extend the existing upper-level ontology by creating new classes and representations. Methodologies for ontology development have been pro­ posed [Lenat and Guha, 1990; Uschold and Gruninger, 1996; Blazquez et al., 1998] . However, many unsolved problems remain. Other important issues concern the relationship between the domain representation and its intended use [Wielinga et al., 1994; van Heijst et al. , 1997]. We shall concentrate on the representational and performance issues focusing initially on the reasoning processes, and reflect on the implications for domain rep­ resentation in the light of these findings.

Versions of Cyc are currently being used as an integra­ tion platform by the DARPA-funded High Performance Knowledge Bases (HPKB) program. Key issues on the HPKB program are the scalability, robustness , and reusability of knowledge-based system solutions. Cyc

Dimitrios Sklavakis

School of Artificial Intelligence Division of Informatics University of Edinburgh

Edinburgh EHl lHN, Scotland

Email: dimi tris@dai. ed. ac. uk

is unique in that it has potential solutions to each of these problems.

Cyc uses a resolution-based inference procedure .that has a number of optimisations that improve the scalabil­ ity of the architecture. For example, a specialised taxo­ nomic reasoning module replaces the application of the logical rule for transitivity of class membership. Where specialised modules are not implemented, Cyc makes use of weak search methods to perform inference. Cyc lacks any principles for structuring inference at a conceptual level. Problem-solving methods provide precisely this structure, hence the importance of integrating structur­ ing principles into a scalable KBS architecture.

Robustness and reusability are related properties of the knowledge representation scheme and the inference rules: Predicates such as bordersOn and between, defined in the upper-level ontology, can be reused in many dif­ ferent contexts. The combination of predicate properties (such as symmetry) and existing inference rules means that the use of these predicates is robust. Reconciling units of measure is a similar problem. In this case, Cyc has sufficient knowledge to prove (greaterThan {Meter 1) (Centimeter 2)) using its existing definitions and rules about units of measure. Reusability is also an impor­ tant motivation for defining a upper-level ontology as the basis of knowledge representation. The upper-level ontology can be shared among more specialised reason­ ing contexts or applications. Extensions to the upper­ level can themselves be shared, and can be regarded as ontologies in their own right .

We describe the implementation of a PSM for fault diagnosis in Cyc. The diagnostic method was applied to two different domains to investigate whether the po­ tential for method reuse was actually achievable. As implementation was preceded by a significant amount of domain and task analysis, this work allows us to review the value of the methodological approach and to investi­ gate issues such as the task-dependence of the ontologies constructed. This paper begins with an introduction to the component technologies used-CommonKADS and Cyc-and then describes the implementation of the PSM and the associated knowledge modelling.

2 Component Technologies

2.1 PSMs: The CommonKADS View

In CommonKADS, problem-solving methods are the product of expertise analysis - one of several analysis steps which are specified by the methodology. PSMs are also used in Protege [Puerta et al., 1992], and in Ex­ pect [Gil and Melz, 1996] (although in different forms) . PSMs define distinct methods for performing a task, for example, diagnosis can be modelled as involving a heuris­ tic association between observations and solutions, or as a process of decomposing a system and testing its sub­ components for correct operation. In addition to speci­ fying an inference procedure, PSMs require that domain knowledge be modelled in particular ways, i.e. a method ontology is associated with a PSM.

CommonKADS is a methodology for KBS develop­ ment which addresses not only the desired problem­ solving performance of the end system, but the context in which it will operate. A number of models are con­ structed in the analysis phase: an organisational model represents the processes, structure, and resources of the organisation which is to use the KBS, a task model describes the activities of the process of interest , an agent model represents the agents involved in the process and their capabilities, a communication model describes agent (human and machine) communication, an exper­ tise model defines domain and problem-solving knowl­ edge, and, finally, a design model describes the struc­ ture and function of the system that will implement the knowledge-based task. More details of the various mod­ els, and appropriate modelling techniques can be found in [Kingston et al. , 1997].

CommonKADS is relatively neutral on questions of implementation. However, expertise modelling does make a number of assumptions about knowledge rep­ resentation constructs and their interaction. The exper­ tise model has three layers: the domain layer represents knowledge about the domain, the inference layer defines the procedures applied during problem solving, and the task layer specifies the ordering of inference steps. As the expertise model is the only CommonKADS model that captures expert problem-solving behaviour, we shall limit our attention to representing this model in Cyc.

2.2 Cyc

Cyc is a very large, multi-contextual knowledge-based system which is currently being used commercially by Cycorp. Cyc is also used for research purposes, and, in the HPKB program, Cyc is being used as a platform for technology integration.

The arguments for Cyc proposed in Lenat and Guha [1990] remain the cornerstones of the Cyc project; namely, the need to overcome the brittleness of tradi­ tional expert systems, and the means of achieving this through the development of a shared ontology represent­ ing 'consensus reality'. The upper-level ontology, which constitutes the basis of knowledge representation in Cyc, has been made publicly available. However, this represents only a fraction of the knowledge which has been entered into Cyc.

The upper-level ontology is represented in a variant of first-order logic known as CycL. The ontology in­ cludes: classes used for constructing representations, for example SetOrCollection and Predicate; classes for high-level concepts such as Event and Agent; and more specific classes representing commonly occurring objects and events such as Book and BirthEvent.

Assertions in CycL are always associated with a mi­ crotheory context. The BaseKB contains the upper-level ontology and new contexts can be defined which spe­ cialise this theory. Multiple inheritance of microtheory contexts is allowed. Alternative specialisations of a mi­ crotheory need not be consistent with each other: a mi­ crotheory can contain ontology extensions and assertions which are inconsistent with those defined in a different theory - providing neither context is defined as subsum­ ing the other. The microtheory mechanism plays an im­ portant role in structuring inference.

Cyc performs inferencing in response to a query by the user (by backward chaining) or in response to an asser­ tion (by forward chaining with rules which are explicitly specified to be forward rules) . Queries are made in a specific microtheory which forms the local search con­ text. Typically, a microtheory will be a specialisation of one or more theories and in this case search will progress out to wider contexts should a solution not be found lo­ cally. Queries are treated in a purely logical manner: the order of conjuncts is not considered to be significant and may be changed by optimisations operating at the clause-form level. The preconditions of rules are also treated in this way - prohibiting the user from influenc­ ing the search process in a predictable way. The depen­ dencies between derived facts, rules and assertions are recorded and maintained by a truth maintenance mech­ anism.

Cyc's purely declarative treatment of rules differs from other approaches to logic-based knowledge representa­ tion, such as Prolog, where the ordering of clauses, and of literals within clauses, is used to determine the order of search.

The Cyc system includes a number of tools for view­ ing and browsing the ontology. In common with other browsers, including that for Loom [MacGregor, 1994], terms in the ontology ai:e hyperlinked in a web-based interface. This allows the user to explore the concepts which define, or are subsidiary to, the concepts currently being displayed.

The Cyc system also gives the KBS developer access to a LISP-like environment where new procedures can be defined in the SubL language. The Cyc knowledge base and inference engine can be accessed via the SubL functions ask and assert. Due to the treatment of rules described above, imposing structure on the search pro­ cess necessarily requires SubL coding.

3 Systematic Diagnosis in Cyc

This section describes the expertise modelling process and presents its products. The implementation of these models in Cyc is then outlined. We begin with a brief introduction to the domain and the diagnostic task.

The task of diagnosis was selected because a set of well understood methods for solving such tasks already exists [Wielinga et al., 1992] . An important part of expertise modelling is the selection between alternative methods - with their accompanying behaviours and as­ sumptions. The choice of a specific diagnostic method was not made prior to domain analysis. It is readily apparent that we have chosen a problem type that falls within the scope of the methodology we intend to apply. However , it is not at all obvious that diagnosis-which is inherently an incremental procedure requiring infor­ mation gathering- can be adequately implemented by backward chaining driven by a query-based interaction (i.e. by the default environment provided by Cyc). We shall return to this point below.

Fault finding in personal computers (PCs) was chosen as the primary task domain. This task can be modelled accurately, i.e. the actual behaviour of human experts is known and has been documented [Kozierok, 1998], yet the amount of electronics knowledge required is low as fault finding never progresses to a level where sophisti­ cated test equipment is required. The second domain chosen was fault finding in an automobile ignition sys­ tem. This task ought to be soluble by the method devel­ oped for PC diagnosis, despite differences in the charac­ teristics of the domain and in the method ontology.

3.1 Modelling Expertise

The selection of a problem-solving method is one of the central modelling decisions in CommonKADS. This will typically have an impact on domain representation. Fol­ lowing this approach, the PC-diagnosis problem was ad­ dressed by investigating candidate PSMs. As PSMs may be refined in several different ways, alternative instanti­ ations were also investigated. This is a notable contrast with a domain-oriented approach which would focus on developing an ontology of the domain being reasoned about, PC systems and their components in this case.

The systematic diagnosis PSM was found to match the expert reasoning process most closely. The generic model had to be adapted to reflect expert reasoning more faith­ fully. The central steps in systematic diagnosis are the decomposition of the system being diagnosed into sub­ systems, and the testing of the subsystems for correct operation by making tests and comparing the observed with the predicted outcomes. The subsystem currently being tested is said to play the role of the current hy­ pothesis. Testing may rule out this hypothesis, in which case another subsystem becomes the hypothesis. Test­ ing may yield an inconclusive result , in which case more tests are required, or testing may indicate a fault , in which case the diagnosis is concluded-if the current hypothesis .cannot be further decomposed (i.e. it is a component), or diagnosis continues at a lower level of system decomposition- if the current hypothesis can be decomposed (i.e. it is a system). The system model may describe how the system is decomposed into (phys­ ical) parts, or may describe the functional relationships between systems.

It was discovered that the the part-of model, which lies at the heart of systematic diagnosis, had to be instan­ tiated to functional-part-of in the PC diagnosis domain. That is, problem solving requires a functional view of the system, rather than a component/subcomponent view. The functional-part-of predicate is clearly a representa­ tional construct at the domain level, and is one of several part-of views that might be taken of a system. In fact, there was no need to represent the physical-part-of rela­ tion in order to solve this problem.

Another important refinement of the generic model was the addition of theories of test ordering. Where there are several decompositions of a system, the model per­ mits any subsystem to play the role of hypothesis. How­ ever, in PC diagnosis it is important to establish first, for example, that the power system is operational, then that the video system is operational. Once the video system is known to work we can be sure that the re­ sults of BIOS system tests are being displayed correctly. Similar ordering constraints were found for all subsys­ tems, and at all levels of decomposition. Consequently, there is a need to impose an order on hypothesis se­ lection (or, equivalently, system decomposition) and we chose to represent this knowledge in a heuristic fashion via a testAfter predicate. Figure 1 shows the specialised PSM in a diagrammatic form.

Determining the overall view of the desired problem­ solving behaviour aided knowledge acquisition, much of which concerned the extraction and structuring of in­ formation from an on-line source [Kozierok, 1998]. Our experience confirmed the claimed advantages of the mod­ elling approach. In addition to specifying an inference­ level procedure, knowledge acquisition also requires the content and scope of domain knowledge to be deter­ mined. The task of representing domain knowledge in Cyc followed the standard procedure of extending the ontology by defining new collections and predicates, and linking these to existing constants. We now describe the Cyc implementation in more detail.

3.2 Cyc Implementation

Diagnosis requires interactive data gathering, and the subsequent evaluation of test results and updating of the current hypothesis. Such a procedure cannot be imple­ mented by logical inference alone, and so it is clearly necessary to use Cyc's LISP-like language, SubL, to im­ plement a control regime. In CommonKADS, control knowledge is divided between the inference layer, where knowledge roles and inference steps are defined, and the task layer, where the order of application of inference steps is specified. Our aim was to represent the levels of the expertise model in Cyc in as faithful a manner as possible. We begin by considering domain knowledge.

Domain knowledge was represented by extending ex­ isting collections where possible. Figure 2 shows a small illustrative set of the extensions made. The collection PCSubsystem was added as a subcollection of Composite­ TangibleAndlntangibleThing, and PCComponent was de­ fined as a specialisation of it. Both types of object have a tangible component, and may carry information hence have an intangible component also. TestAction was de­ fined as a new collection of PurposefuiAction, and the instances of Remove, Replace, and ConfirmSensorially (i.e. confirm by observation) were added [Sklavakis, 1998]. functionaiPartOf was introduced to represent the func­ tional decomposition of a system, and stated to gener­ alise to parts, being the most general existing part-of predicate in the upper ontology 1 . Other specialisations of parts include physicaiDecompositions and timeSiices.

The predicates testFirst and testAfter were introduced as predicates to represent the test ordering theory. A test is defined by three components: a TestAction, a PC­ Subsystem and a PossibleObservable. The collections Pos­ sibleObservable, PossibleObservableValue, and ResultType were defined as subcollections of Attribute Value. The rep­ resentation of testing knowledge can be made more ro­ bust by grounding it extensively in the upper ontology . In contrast, part-of facts are not likely to be derivable by appeal to background knowledge.

At the inference level, knowledge roles are represented by predicates, and inference steps are rules which have knowledge roles as preconditions and conclusions. Fig­ ure 2 shows the introduction of the KnowledgeRole col­ lection, a specialisation of the Predicate class of the up­ per ontology. Instances of Knowledge Role predicates take domain-level formulae or collections as arguments. Ex­ amples include; the unary predicate hypothesis - appli­ cable to PCSubsystem - denotes the current hypothesis, possibleTest holds of applicable tests, and the relation predictedTestOutcome holds of a test, PossibleObservabl­ eValue and a Result Type. More complex mappings to the inference level, and the definition of additional collec­ tions and terms, are also possible within this approach. The CycL language is sufficiently expressive to allow complex mappings of the type described in [Wielinga et al., 1994] where the inference-level ontology (in our ter­ minology) might define relations holding of domain-level ontology, e.g. we could express the fact that Physicai­ PartOf is a relation: relation(PhysicalPartOf ).

In a similar way, the currently invoked inference step (e.g. decompose, select) is also explicitly asserted in the KB by predicates which belong to the inference level.

Inference steps are invoked by querying or asserting knowledge roles. For example, the role hypothesis holds of the subsystem currently playing the role of the hy­ pothesised fault. The rules for selecting the test ordering theory depend on the current hypothesis, for example:

·F: (implies (and (hypothesis PCSystem) (plausibleinference Decompose)) (and (testFirst PowerSystem) (testAfter PowerSystem VideoSystem))).

This is a forward rule which fires when hypothesis and plausiblelnference are asserted. The current hypothesis assertion must be deleted and replaced as diagnosis pro­ ceeds. These operations are implemented in SubL by functional-interface functions , within the larger struc­ ture of the systematic diagnosis task function. The user could make this series of deductions themselves, and in the implemented system, the user is able to inspect the state of the reasoning process as it progresses. As an example, the following SubL code is called at the start of diagnosis and simply asserts that the entire system is the hypothesis, and then calls another SubL function, sd-select2-3, which performs system decomposition.

1 Note that terms defined in the ontology, or its extension, are written in sans-serif, following the Cyc convention, names of collections begin with a capital letter and predicates begin with a lower case letter.

(define sd-selectl (system) (fi-assert (#$hypothesis system) ·defaultMt·) (sd-select2-3))

We have achieved an explicit representation of knowl­ edge roles and of inference steps in Cyc that reflects the knowlede;e typing principles advocated in [van Heijst et al., 1997j. Control over the search process is achieved by making a series of simple queries, structured to imple­ ment the pattern of inference of the PSM. We found no need to extend the functionality of Cyc, or the expres­ sivity of its representation language(s) in order to im­ plement the PSM. The central problem was to combine the available features into structured architecture, in or­ der to to take advantage of the model-based approach to problem solving.

We tested the reusability of the domain and inference level definitions, and of the SubL code, by considering diagnosis in the domain of automobile ignition systems. This experience is discussed in the wider context of the reusability, scalability, and robustness of our approach.

4 Representation and Reasoning

4.1 Domain Ontologies

The view of domain ontology construction which results from the prior selection and adaption of an explicit prob­ lem solving method is more focussed on concepts relevant to problem solving than a task-neutral view would be. The resulting domain ontology is not task-specific in its formalisation, e.g. the definition of the functional-part-of relation has no intrinsic task-related properties. But, the coverage of the resulting ontology may only be partial - we did not need to elicit physical-part-of knowledge.

Had we taken a view that focussed on the domain alone, we would have had no explicit guidance as to which concepts were or were not relevant to the on­ tology definition effort. We have gained experience of constructing ontologies where the primary aim was to represent the domain, with ontology definition only in­ formally guided by considering the task. Under these conditions it is difficult to determine the relevance of a potential domain concept, and the distinction between concepts that are intrinsic to the representation of the domain, and those that are related to the task to be performed was difficult to make.

Reusability of domain knowledge is an important is­ sue, and our approach has been to use the microthe­ ory mechanism of Cyc to encapsulate the generic com­ ponents of the extended ontology. The resulting mir­ cotheory structure, shown in Figure 3, places the generic system models for PCs and automobile systems in dis­ tinct microtheories, that are extensions of the BaseKB, and are included in the specific diagnosis microtheories. Strictly speaking, these microtheories are not extensions of the ontology as they make no new specifications. In­ stead, the BaseKB is extended by adding the definitions of the functionaiPartOf predicate and the collections Sub­ system and Component as these concepts are sufficiently general to be reusable across domains. The method­ specific ontology, comprising domain and inference level components, is also a specialisation of the BaseKB, and this theory is shared by both PC and Automobile di­ agnosis theories. The microtheory structure shows that the generic system models can be used in any context which includes the (now extended) BaseKB, and that these theories can be thought of as parameters of the diagnosis microtheories.

4.2 Inference Knowledge

The application of systematic diagnosis to the automo­ bile domain required a change in system theory from functionalPartOf to physicalDecomposition. While this is a significant change in the modelling of the diagnostic process (physical parts play the role of hypotheses) there were few implications for formalisation of the inference level as no new knowledge roles were found. Similarly, the SubL code was only modified to take the specific di­ agnosis microtheory as a parameter. In future, we aim implement other PSMs and this may permit us to gen­ eralise inference-level theories across PSMs.

4.3 Scalability

The domain and inference level knowledge representa­ tions that we have used are extensions of the basic rep­ resentation, and can make use of the existing optimi­ sations for indexing large KBs, performing taxonomic reasoning and theory structuring. Our approach to PSM implementation is based on structuring a series of queries and assertions to implement a problem-solving method. As the individual queries are simple, the space searched is small (we can specify the depth of search to be 13 levels). This contrasts with the basic query mecha­ nism where the only means of getting an answer to query which requires many rules to be combined is to increase the depth of search - with the resulting exponential in­ crease in search space.

4.4 Robustness

At present we are unable to reason about inference struc­ tures or about the mappings from the domain to the in­ ference level within Cyc. There are no rules which allow PSMs to be modified or to be configured. Consequently, the system lacks robustness as it cannot fall back to first principles when an existing method is not immediately applicable. The problems of PSM modification and con­ figuration are significant, even for human experts, but we believe that automatically specialising PSMs is a fea­ sible proposition. We also plan to explore the idea of falling back to more general methods, when more spe­ cific methods are inapplicable, to regain robustness.

Inference steps (implemented by rules) require proving domain-level predicates, and robustness at the level of reasoning about domain knowledge occurs exactly as in Cyc.

5 Discussion

We have described an approach to implementing problem-solving methods in Cyc which makes use of the existing optimisations developed for large-scale knowl­ edge bases, and adds additional structure to the infer­ ence process. Extensions to the existing ontology distin­ guished generic extensions to the upper-level ontology, extensions to the knowledge base, and task-related ex­ tensions. Knowledge typing principles were used within the task-related ontology to further structure problem­ solving knowledge.

Our investigation of diagnostic problem solving has not only raised issues of knowledge reuse and scalabil­ ity, but also of system-environment interaction. Intelli­ gent systems cannot rely on large amounts of background knowledge alone as many classes of problems require in­ formation gathering or user interaction. If such interac­ tion is to happen in an intelligent fashion then there is a requirement to represent and reason about the inferences which require interaction.

Acknowledgments

This work is sponsored by the Defense Advanced Re­ search Projects Agency (DARPA) under grant number F30602-97-1-0203. The u.s. Government is authorised to reproduce and distribute reprints for Governmen­ tal purposes notwithstanding any copyright annotation hereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing official policies or endorsements, either express or implied, of DARPA, Rome Laboratory or the u.s. Government.