UPML: A Framework for Knowledge System Reuse

1 Introduction

Problem-solving methods (PSMs) for knowledge-based systems (KBSs) (cf. [Schreiber et al., 1994]; [Benjamins & Fensel, 1998]) decompose the reasoning task of a KBS in a number of subtasks and inference actions that are connected by knowledge roles. Several problem solving method libraries are now available [Breuker & van de Velde, 1994], [Motta & Zdrahal, 1998]. The IBROW project [Benjarnins et al., 1998] has been set up with the aim of enabling semiautomatic reuse of PSMs. This reuse is provided by integrating PSM libraries in an internet-based environment. A software broker selects and combines PSMs from different libraries and provides a knowledge engineer with semi­ automated support for configuring a reasoning system. Hence, a description language for these reasoning components (i.e. , PSMs) must provide human­ understandable, high-level descriptions, which should also be grounded on a formal representation, to allow automated support by the broker. To this purpose we have developed the Unified Problem-Solving Method Development Language, UPML [Fensel et al., 1999b]. UPML is a software architecture for knowledge-based systems providing components, adapters and a configuration (called architectural constraints) of how the components should be connected using the adapters. Finally design guidelines

Enrico Motta

Knowledge Media Institute The Open University MK7 6AA, Milton Keynes United Kingdom Bob Wielinga Dep. SWI Univ. of Amsterdam 1 018 WB Amsterdam The Netherlands

specify how to develop a system constructed· from the components and connectors that satisfies the architectural constraints.

In knowledge engineering terms UPML provides a meta-ontology for describing knowledge-based systems. The different elements of a specification correspond to concepts of this ontology and the architectural constraints are axioms in this ontology.

In this paper we outline the main features of the approach we have taken to define a framework for knowledge sharing and reuse. In particular we illustrate the basic meta-ontology of UPML, its underlying architecture, support tools and development guidelines. Because of space constraints we can only provide a limited number of technical details. Hence, the paper is better seen as an overview report on the main issues we are facing and the solutions we are developing.

The paper is organized as follows. In Section 2, we will briefly sketch the overall structure of UPML. Then we will discuss the (meta-)ontology that can be used to formalize UPML. Section 4 intrtlduces the architectural constraints of UPML and Section 5 shows various ways in which tools for developing, selecting, and combining PSMs can make use of the (meta-)ontology. Section 6 briefly mentions the development guidelines of UPML. Conclusions, related work and outlook are discussed in Section 7.

2 The Overall Structure of UPML

[Fensel et al., 1999a] introduce the four components types of a UPML specification:

• Tasks define the problems that should be solved by the KBS.
• PSMs define the reasoning process of a KBS in domain-independent terms.
• Domain models describe the domain knowledge of the KBS.
• Ontologies provide the terminology used in tasks, PSMs and domain definitions.

Each of these elements is described independently to enable the reuse of task descriptions in different domains, the reuse of PSMs across different tasks and domain, and the reuse of domain knowledge for different tasks and PSMs. Therefore, adapters are required to adjust the (reusable) parts to each other and to the specific application problem. UPML provides two types of adapters: bridges and refiners.

• Bridges explicitly model the relationships between two distinct parts of an architecture, e.g. between domain and task or task and PSM.
• Refiners can be used to express the stepwise specialization of a cla.Ss of elements of a specification, e.g. a task is refined or a PSM is refined.

Very generic PSMs and tasks can be refined to more specific ones by applying a sequence of refiners ( cf. [Fensel, 1997]). Again, separating generic and specific parts of a reasoning process maximizes reusability.

Together, the six UPML building blocks define a software architecture. The overall structure of a UPML specification is presented in Figure 1 (a more detailed discussion of the example can be found in [Fensel et al., 1999b]). A task called "complete and parsimonious diagnoses" is defined by importing an ontology called "diagnosis". The PSM applied to solve the task is "hill climbing". A bridge is required to connect the generic terminology of hill climbing with the diagnostic task: states and states transitions of the method have to be rephrased in terms of the task ontology.

Hill climbing is only one possible refinement of a generic search method that decomposes an entire search task into five more elementary subtasks: Initialize, Derive Successor Nodes, Select Node, Stop and Update Nodes. Hill climbing can be derived from this generic search method by (i) refining one of its subtasks (i.e., update node forgets all earlier nodes and only processes the currently derived successors further) and (ii) introducing a preference ordering.

PSM-mediated task decomposition and PSM specialization through a refiner are analogous to the part-of and is-a constructs of knowledge representation formalisms. Subtasking corresponds to the part-of construct because it decomposes a task into subtasks. The refinement of problem-solving methods, as introduced in [Fensel, 1997], corresponds to the is-a relationship of knowledge representation formalisms - e.g., Hill-climbing is a specialization of a general search method by refining some of its attributes (i.e., sub tasks).

3 The Meta Ontology of UPML

We used PROTEGE-II [Puerta et al., 1992] to develop a meta ontology of UPML. PROTEGE-II is a knowledge acquisition tool-generator. After defining an ontology it semiautomatically generates a graphical interface for collecting the knowledge that is described by the ontology. The ontology can be described in terms of classes and

Root Competence Competence CPSM Competence Task Competence PPSM Cost expression Formula MCL-Program Operational Description Pragmatics Renaming Role Input/Output Role Input Role Output Role Intermediate Role Knowledge Role Signature Specification Units Bridge PSM-Domain Bridge PSM-Task Bridge Task-Domain Bridge Domain Model Domain Refmer Ontology Ontology Refiner PSM ComplexPSM Primitive PSM PSM Refiner Task Complex PSM Ref. Primitive PSM Ref. Task Refiner UPML Specification

attributes and organized with an is-a hierarchy and attribute inheritance. Viewing UPML as an ontology and structuring this ontology with the help of PROTEGE-II, helped us to realize some missing elements in sub-specifications and we obtained a much clearer view of the overall structure of UPML. It turned out that the two adapter types, refiners and bridges are rather different entities in the ontology. Refiners are a subconcept of the specification element they refine, while bridges are a class by themselves. Figure 2 provides the class hierarchy of the UPML meta ontology. The organizational principle of the class hierarchy was to minimize the definitions of attributes, i.e. to maximize attribute inheritance. The definitions of the attributes of the class task and task competence are provided in Figure 3.

This ontology has been used to formulate architectural constraints, and to develop tools like editors, browsing, querying and reasoning services for UPML.

4. Architectural Constraints

Architectural constraints ensure well-defined components and composed systems. The conceptual model of UPML decomposes the overall specification and verification tasks into subtasks of smaller grainsize and clearer focus. The architectural constraints of UPML consist of requirements that are imposed on the intra- and interrelationships of the different parts of the architecture. They either ensure a valid part (for example, a task or a problem-solving method) by restricting possible relationships between its subspecifications or they ensure a valid composition of different elements of the architecture (for example, constraints on connecting a problem-solving method with a task). These architectural constraints can be formulated as axioms of the UPML meta ontology.

For example, we require the consistency of a task specification, i.e.

T 1 ontology axioms U preconditions U assumptions must have a model.

Otherwise we would define an inconsistent task specification which would never be solved. In addition, it must hold:

T2 'dx1, .. ,x 0 (ontology axioms U preconditions U assumptions -t 3yt. .. ,Ym goal)

That is, if the ontology axioms, preconditions, and assumptions are fulfilled by a domain and the provided case data then the goal of a task must be achievable. This constraint ensures that the task model makes the underlying assumption of a task explicit. For example, when defining a global optimum as a goal of a task it must be ensured that a preference relation exists and that this relation has certain properties. For example that x < y and y < x (i.e., reflexivity) is prohibited because otherwise the existence of a global optimum cannot be guaranteed.

These are the two architectural constraints UPML imposes to guarantee well-defined task specifications. A third optional constraint ensures minimality of assumptions and preconditions (called weakest preconditions in software engineering) and therefore maximizes the reusability of the task specification. It prevents overspecialization of assumptions and preconditions (i.e., it ensures that a task is not applied to an unsuitable domain).

T3 'dxl> .. ,x 0 3y1,..,ym (goal -t ontology axioms U preconditions U assumptions)

Similar constraints have been developed for the other components. Correct relationships between components are formalized as axioms concerning the relevant bridges. For

Task[ pragmatics ~ Pragmatics ontologies ~ Ontology import~ Task competence~ Competence Task] Competence Task[ goal ~ Formula precondition~ Formula roles ~ Input/Output Role assumptions ~ Formula]

example

TPB2

renaming(PSM preconditions U PSM assumptions U PSM postconditions) U

task ontology U task preconditionsUtask assumptionsU bridge ontology U mappingaxiomsU bridgeassumptions --7 task goal

ensures that the goal of the task is fulfilled by the postcondition of the selected method. Further axioms can be found in [Fensel et al., 1999b].

5. Tool Support

We used PROTEGE-II to implement an editor for UPML specifications. First PROTEGE-II helps to define an ontology (in our case the meta ontology of UPML). In a second step it automatically derives an editor from it that requires some human interaction to derive a suitable tool from it.

The output of the UPML editor delivers files of the ontology and UPML specifications in a lisp-like syntax. We implemented a tool that translates these files into Frame Logic [Kifer et al., 1995] . The reason for this is to be able to use On2broker 1 as a browsing and query interface for UPML specifications. On2broker (cf. [Fensel et al. , 1998]) is an advanced tool for browsing and querying WWW information sources. It provides a hyperbolic browsing and querying interface for formulating queries, an inference engine used to derive answers, and a webcrawler used to collect the required knowledge from the web. Figure 4 provides the hyperbolic presentation of the UPML meta ontology: classes in the center are depicted with a large circle, whereas classes at the border of the surrounding circle are only marked with a small circle. The visualization technique allows a quick navigation to classes far away from the center as well as a closer examination of classes and their vicinity. The structure of the frame-based representation language is used to define a tabular querying interface that frees users from typing logical formulas (see Figure 4). When a user selects a class from the hyperbolic ontology view, the class name appears in the class field of the tabular query interface and the user can select one of the attributes from the attribute choice menu because the pre­ selected class determines the possible attributes. The discussed tool set is implemented in Java and available via the WWW.

However, typical UPML queries may be more complex. For example, Figure 5 shows parts of an On2broker's answer. to a complex query which asks for all attribute values of a task specification. Such queries are closer to short logical programs than to typical database queries. To ameliorate this problem we have used the UPML meta-ontology to define generic query patterns such as the one shown in Figure 5 which are instantiated for specific queries. Moreover, because the query interface is implemented as a Java Remote Method Invocation (RMI) Server.

1. http://www.aifb.uni-karlsruhe.de/www-broker.

6. Development Guidelines

Design guidelines define a process model for building complex KBSs out of elementary components. In general, the guidelines of UPML fall into three categories ( cf. [Fensel et al. , 1999b]):

• How to develop an application system out of reusable components. Guidelines describe the sequence and interrelationships of component selection and adaptation in developing an application system.
• How to develop a library of reusable task definitions and problem-solving methods. A three dimensional design space with predefined transition types provides structured support in developing and refming PSMs according to algorithmic paradigms, task terminologies and assumptions on domain knowledge.
• Which components of UPML correspond to an implementation and how can such components be implemented in an object-oriented framework. We developed and refined some Design Patterns that guide this translation process and defined certain interface guidelines.

7. Conclusions

Ontologies were introduced as means to support knowledge sharing and reuse (cf. (Gruber, 1993]). UPML provides an ontology for sharing and reusing knowledge-based systems. That is, it provides a (meta-)ontology for describing tasks, PSMs, domain models, ontologies, their mappings via bridges and refiners that express adaptation of the components. A number of tools have been developed and configured for supporting the definition and use of UPML components. A PROTEGE-II based editor enables the development of UPML descriptions, while On2broker can be used to browse and query such descriptions. In addition, the IBROW broker matches user requirements with knowledge components specified in UPML and supports their distributed execution.

Related Work

UPML is close in spirit to CML which has been developed in the ComrnonKADS project (cf. [Schreiber et al., 1994]). CML provides a layered conceptual model of K.BS by distinguishing between domain, inference, and task layers according to the ComrnonKADS model of expertise. UPML took this model as a starting point, but refined it according to the component-oriented style of software architectures. UPML decomposes a knowledge-based system - via an architecture - into a set of related elements: tasks, problem-solving methods, domain models and bridges that define their relationships. CML does not provide task-independent specification of problem-solving methods nor the encapsulation mechanism of UPML for problem-solving method. In UPML, the operational specification of a method is an internal aspect that is externally described by the competence of the method. In addition, CML does not provide means to refine tasks and problem-solving methods. In general, UPML is much more oriented to problem-solving method reuse (i .e., component reuse) than CML. Finally, CML is a semiformal language whereas UPML can be used as a semiformal language (using its structuring primitives) and as a formal language (UPML provides logical formalisms to formally define the elementary slots).

UPML has also many similarities with other standardization efforts in the area of knowledge-based systems. OK.BC (Chaudhri et al., 1998] jointly developed at SRI International and Stanford University, provides a set of functions that support a generic interface to underlying frame representation systems. The Knowledge Interchange Format [KIF] is a computer-oriented first-order language for the interchange of knowledge among disparate programs. [KQML] or the Knowledge Query and Manipulation Language is a language and protocol for exchanging information and knowledge. KQML can be used as a language for an application program to interact with an intelligent system or for two or more intelligent systems to share knowledge in support of cooperative problem solving. The distinctive feature of UPML is that it is about sharing and exchange of problem-solving methods, i.e. software components that realize complex reasoning tasks of knowledge-based systems. Moreover, UPML is less a standardization formalism than a standard architecture, which is defined by its meta-ontology. A similar approach is taken in Ontolingua [Gruber, 1993], which defines a meta-ontology for describing frame-based ontologies. Although UPML aims for a much broader scope, Ontolingua could be used at the object level of UPML for describing the elementary attribute values of specifications.

Finally, [Fensel et al. , 1999b] put UPML in the general context of software architectures and also sketch how it can be translated into UML.

Outlook

An important issue concerns the integration of components subscribing to different ontologies. This integration can be specified by means of bridges. Bridges can either be defined by hand (i.e. by library providers or application developers) or can be generated automatically by an intelligent broker ( cf. [Benjamins et al. , 1999]). However, the automatic generation of bridges requires that the library providers do not only agree on a shared language (i.e., UPML) but also on a shared vocabulary, i.e., they do not only have to use the same UPML meta-ontology but also partially the same ontology at the object level.

Acknowledgment. We thank Igor Becker, Stefan Decker, Mauro Gaspari, John Gennari, Rix Groenboom, William Grosso, Frank van Harmelen, Mark Musen, John Park, Rainer Perkun, Enric Plaza, Guus Schreiber, Rudi Studer, Annette ten Teije, and Andre Valente for valuable comments on early drafts of the paper.