Ontology construction is a complex collaborative process that crosses individual, organizational, and geographic boundaries. It involves several types of groups with differing expertise, goals, and interactions. An ontology server must be carefully structured to support this complexity. Consider, for example, the task of building schema to support the command and control (C2) process. A common C2 schema, such as the one being developed as part of the JTF-ATD, would provide a substrate for numerous applications in planning, logistics, intelligence, and so on. With the proper underlying technology, it could support advanced knowledge-based applications as well as conventional data base and software systems. To construct this schema, small groups of experts in each of the key sub-areas collaborate to specify ontologies describing the essential concepts, their properties, and interrelationships. The products of these groups of authors must be merged and checked for consistency by a supervisory board of editors. The editors must then invite comments from a large group of reviewers and critics that include expert peers, end users, and application developers. As portions of the ontologies stabilize and the editors release them from the reviewing process, larger groups of application developers must become familiar with them and incorporate them into existing and new applications. Furthermore, the developers need support to convert the ontologies into a form that they can readily work with in a specific knowledge representation language, database schema language, interface language, or programming language, and they need support for extracting domain models from the ontologies that can be used by problem solving modules.
We are developing technology that will make this scenario a reality by addressing key barriers to representing essential knowledge in and about ontologies, constructing ontologies, accessing the content of ontologies, and obtaining domain models from large-scale ontology repositories. In particular:
Representing essential knowledge in and about ontologies. How can ontologies express uncertainty inherent in a domain? How can ontologies support multiple views and abstractions of objects in a domain? How can the competency of an ontology be expressed?
Ontology construction. How can ontology components be efficiently constructed? How can they be adapted to data? How can teams of domain experts collaborate to build ontologies? How can ontologies be tested during development?
Accessing the contents of ontologies. How can "ontology servers" provide efficient reliable access that respects organizational and institutional boundaries? How can servers provide useful reasoning support for ontologies represented in highly expressive languages?
Obtaining domain models from large-scale ontology repositories. How can a user find relevant ontology components? How can relevant components be extracted, composed, and translated for a specific application? How can a probabilistic model tailored to a specific context be extracted from the ontology?
We will build on the results of the DARPA Knowledge Sharing Effort (Patil et al. 1992), specifically by using the Knowledge Interchange Format (KIF) (Genesereth and Fikes 1991; Genesereth and Fikes 1992) as a core representation language and the Ontolingua system (Farquhar, Fikes, and Rice 1996; Gruber 1993) as a core ontology development environment. KIF is a highly expressive formally defined language specifically designed for representing knowledge in a reusable and translatable form. Ontolingua is a system in wide-spread use that adds object-oriented constructs to KIF, includes a library of reusable ontologies, supports collaborative ontology construction by assembling and extending building block ontologies from the library, provides an HTML-based user interface (Rice et al. 1996) accessible via a World Wide Web navigator (e.g., Netscape), and supports a network GFP API (Karp, Myers, and Gruber 1995) for object-oriented access and editing of ontologies.
Uncertainty is a familiar problem in knowledge representation to which many solutions have been proposed. Among these, the probabilistic framework is unique in its clear and coherent semantics which supports fundamental operations such as incorporating evidence from various sources and deciding on optimal courses of actions, including information gathering actions.
Traditionally, the barrier to the use of probability theory has been the complexity both of acquiring complex numerical knowledge and of reasoning with it. Recent years, however, have seen the emergence of a new framework for representing probabilistic knowledge: Bayesian belief networks (Pearl 1988). Bayesian networks utilize the locality of the world, i.e., the fact that only a few attributes directly affect each other, to allow a concise and natural specification of complex probability distributions. The same representation also supports probabilistic inference algorithms that, while computationally expensive in the worst case, are efficient in practice.
Bayesian networks are currently the leading technology for reasoning under uncertainty. However, their usefulness is restricted to situations that can be encoded, in advance, using a static model over a fixed set of attributes. This limitation makes Bayesian networks inadequate for large-scale complex knowledge representation tasks. We will integrate the representations and algorithms developed for Bayesian networks with the more traditional knowledge representation languages, designed to support large-scale knowledge bases.
For a frame-based language, our main task in representing uncertainty is to capture the probability distribution over the values (fillers) of the slots in a frame. We will accomplish this task by allowing the specification of a Bayesian network fragment over the slots of a frame corresponding to a class. The fragment would capture the probabilistic relations between the slot values of a generic instance of this class.
Current Bayesian network representations cannot directly support this type of modeling for several reasons: the number of fillers for a given slot can vary for different objects; the fillers of a slot can be complex objects on their own right; potential dependencies between slot-values of the object and slot values of its fillers (when these are also objects). We will extend the Bayesian network representation to support this functionality. In particular, we will allow for distributions over the number and the type of fillers for a given role, and allow the distributions over the properties of the filler to depend (probabilistically) on properties of the object.
The ability to specify a probabilistic model for an entire class of objects at once allows the reuse of the model in a variety of situations. For example, we can describe the probabilistic dependencies of the behavior of a SCUD battery on its mission, and apply this knowledge in a variety of situations, each involving a different configuration of the battlefield. We can also relate the behavior of the battery to the properties of other objects in the domain, for example the elevation of the site where the battery is located.
This object-oriented view of the world naturally supports several important hierarchical abstraction mechanisms. Using a component hierarchy, we can relate the properties of an object to the properties of its components. For example, we can probabilistically derive the mission of a battery from the mission of the entire battalion, and conversely, the status of the battalion from the status of the individual batteries.
Using an inheritance hierarchy over classes, we can reuse parts of a model constructed for a superclass in defining the properties of a subclass. For example, we can derive certain aspects of a SCUD battery launch activity from the properties of a generic SCUD battery activity.
High-level actions are typically implemented as a sequence of lower-level actions (Erol, Hendler, and Nau 1994). Viewing each action as an object, we can view the low-level actions as components in the object representing the high-level action. The effects of one action on the preconditions required for the next can then be encoded using probabilistic relations between frame components, as described above. Alternative implementations of the same high-level action can be modeled using inheritance hierarchies. The generic effects of the high-level action can then be inherited by all of its implementations, while effects that are specific to some subset of the implementations are specified at lower levels of the inheritance hierarchy.
This framework allows a uniform treatment of actions and plans as simply a type of object. Thus, the same problem-solving tools developed for the framework as a whole can be used to support plan modeling and evaluation, and ultimately even planning.
* Views, where each view corresponds to a class with its own set of descriptive properties and attributes. Each view class could be linked to classes that can be used as other views of a common object and each instance of a view class could be linked to the other instance descriptions of the same object.
* Abstractions, where each abstraction corresponds to a class with its own set of descriptive properties and attributes. Classes could have class slots (e.g., "Abstracts" and "Abstraction-Of") whose values define an abstraction hierarchy. We would also develop a formalism for describing the relationships between levels of abstractions to support reasoning across abstraction levels and propagation of changes through abstraction levels.
* Sets of incompatible alternative descriptions (e.g., with different simplifying assumptions) to assure that at most one alternative from each group is included in an ontology.
We will extend the Ontolingua representation language to include contexts as formalized by McCarthy and Buvac (Buvac, Buvac, and Mason 1995; McCarthy and Buvac 1994). The extension will enable ontologies to include statements made with respect to a context, statements relating what is true in one context to what is true in other contexts, and statements that describe and relate contexts.
If a constructive proof can be given for a sentence of the form [[Phi]](x1,...,xn) => R(x1,...,xn), where R is a relation and [[Phi]](x1,...,xn) is a sentence containing only computable functions and relations, then R becomes a computable relation. We will develop a compiler that produces a method that computes R(x1,...,xn) from such a constructive proof. The resulting method would serve as a reference implementation of the method in some widely available implementation language (e.g., JAVA or C). Such methods associated with an ontology could be considered to be extensions of the API used to access the ontology.
We will develop a computer interpretable annotation language for use in structuring ontology repositories that will include relations among ontologies such as "abstracts", "approximates", and "alternative". The annotation language may need to include a domain specific vocabulary so that provision will need to be made for an ontology to have associated with it an annotation ontology for that domain. Annotations may also provide examples of the competency of an ontology by describing example situations using the ontology and sets of queries about those situations whose answers are derivable from the ontology.
We will also provide support for a broader range of the ontology development cycle, including the early phases which often require compound edits such as taxonomy restructuring as well as adding descriptions of new classes. An example of an editor for early stages of ontology development is one that mimics Microsoft Word's outline mode and is used to specify basic frame language constructs like class-subclass relationships, slots in classes, and value type restrictions. The editor could include a spelling corrector that uses the ontology's vocabulary as its dictionary. We would consider adapting existing outline editors (e.g., in the form of JAVA applets) to produce such an editing tool. A simple frame structure input language for Ontolingua would enable developers to use their own text editors to produce a document loadable by Ontolingua describing class-subclass relationships, slots in classes, and value type restrictions.
* Tools that enable a developer to use an ontology to describe familiar situations and to query those situations to determine if the situations as described have expected properties. The ontology server's general purpose reasoner will be used to derive answers to queries, and the algorithm for extracting Bayesian network models for specific situations from a knowledge base will be used for testing the uncertainty information in an ontology.
* A facility for specifying a test suite for an ontology, where each test consists of a situation specification, a set of queries about the situation, and the expected answers to the queries. Such test suites can be used as requirements specifications for ontologies, for regression testing of ontologies, and as examples of the computations supported by ontologies.
* A single ontology that is a merger of the component ontologies, or
* A set of rules for translating sentences in one ontology into sentences in another ontology.
Integrating the vocabularies of two ontologies involves determining and specifying relationships between the intended meanings of the non-logical symbols (i.e., symbols that name the classes, predicates, and functions) of the first ontology and the non-logical symbols of the second ontology. The ontology server's reasoner can assist with that task by deriving equivalence, subsumption, and disjointness relationships among the classes, predicates, and functions of the ontologies. When the integration is to produce a merger of the two ontologies, these derivations can be added to the resulting ontology. Facilities are then needed to enable the user to rename classes, predicates, and functions in the resulting ontology, and to combine classes, predicates, and functions that have differing definitions but are intended to be equivalent. When the integration is to produce a set of translation rules, then the derivations can be represented as rules, and facilities are needed to enable the user to add rules that rename and combine symbols.
Our use of the same underlying knowledge base to construct models for a variety of different situations will support learning from training sets where the instances are qualitatively very different. For example, we can learn the parameters for the behavior of a SCUD battery from past scenarios that are radically different, involving a variety of different units, with different missions, or even in different armies. The ability to use each training instance to learn about all of the aspects to which it pertains will allow us to learn more from smaller training sets.
We will also investigate the question of learning the qualitative structure of the relations between frame components (i.e., which components directly influence each other). We believe that this can be accomplished by combining techniques for learning Bayesian network structure and for inductive logic programming. We intend to execute some of this work in collaboration with Professor Tom Mitchell's work (at CMU) on learning qualitative frame structure.
We will design and build a prototype ontology server which provides access to the contents of ontologies via a network API and to information derived from the contents by a general purpose reasoner. Ontology servers will be analogous to data base servers and will support distributed repositories and distributed servers for editing, browsing, etc. which access the repositories.
The ontology server will support distributed ontologies by enabling component (i.e., included) ontologies to be resident on remote servers. This capability will be achieved by implementing various forms of remote references within an ontology for classes, relations, functions, and axiom schema loaded on remote servers.
The ontology server will also provide the capabilities described in the following sections.
* Version tracking of component ontologies so that a given version of an ontology always contains the same components;
* Author notification when there is a more recent version of a component ontology available;
* Commands for upgrading a component ontology to its later version;
* Facilities for specifying rules for translating descriptions in one version to descriptions in another version;
* Facilities for performing regression testing on new versions;
* Facilities for succinctly describing the differences between versions of an ontology; and
* Facilities to notify running applications and developers as releases are made.
The idiom-based retrieval facility will employ a general purpose reasoner (i.e., theorem prover) and classifier that can be run as a background process to infer sentences that match certain schematic patterns. These derived facts will be cached using a truth maintenance facility so that they can be removed in case the statements on which they are based are deleted.
We will develop a general purpose reasoner (i.e., theorem prover) for the Ontolingua representation language to provide basic reasoning support for ontology services, including:
* Classification;
* Deriving and caching instances of sentence schema to support idiom-based ontology access;
* Ontology testing in which an ontology is used to describe a familiar situation and the description is queried to determine if it has expected properties;
* Client-side execution. In order to make effective use of the server's resources, some inference will need to be done on client machines. A client-side inference tool that uses the network API to access an ontology's contents will be able to perform analysis, consistency checking, and inference without placing undo strain on the server's performance.
We will include a truth maintenance system in the ontology server that will enable derived sentences (i.e., theorems) to be cached in ontologies accompanied by the axioms that support their derivation, and will automatically delete derived sentences when their supporting axioms are deleted. This facility will enable servers to augment ontologies with derived sentences that support specific server capabilities, such as sentences that match axiom schema recognizable by translators or API's and sentences that define evaluable functions and relations.
The API will use the ontology server's idiom-based retrieval mechanism as its basic mechanism for obtaining information from an ontology. For example, to obtain the subclasses of a given class C, the API will retrieve true instances of the sentence "(Subclass-Of ?x C)". The API will augment the server's idiom-based retrieval mechanism by tasking the server's background derivation facility to derive and add to each ontology true instances of the idioms that are used by the API's retrieval functions. For example, the derivation facility could derive the sentence "(Subclass-Of Csub C)" from the sentences:
(=> (Csub ?x) (C ?x))
(<=> (subclass-Of ?c1 ?c2) (=> (holds ?c1 ?x) (holds ?c2 ?x)))
The API's response to a retrieval request will then include the results derived during the background processing.
A consensus standard "upper level" reference taxonomy could serve as an index into an ontology repository for class-based retrieval by asking ontology developers to specify for each class in their ontologies which if any immediate superclasses that class has in the reference ontology. (This is a generalization of the current notion of specifying "Thing" as the superclass of top level classes in an ontology.) The result would be that one could browse the reference ontology looking for classes of interest in the repository. The repository would look like one big ontology with all the repository classes reachable from the reference ontology. One could also search the reference repository to find a class of interest and then browse from the retrieved class as before.
We are working as members of the ANSI committee on ontology standards to develop and make generally available a consensus standard reference ontology. The goal of that committee is to build a large, reusable, widely-held, representation-neutral ontology to serve as a central terminology base and inter-model fulcrum. We intend to focus our work in that committee on extending the reference ontology to include a reference set of slot names and augmenting the reference classes with slots, slot constraints, and disjointness constraints so that each class has a distinct semantics from other classes in the reference set.
In addition to the top down index provided by a reference ontology, a retrieval facility could provide suggestions for alternatives to a given class based on abstraction and view links associated with the class.
We will develop vocabulary translation tools that:
* Enable a knowledge base builder to declaratively specify translation rules between the vocabulary used in a source ontology and the vocabulary used in a target ontology, and
* Apply declarative translation rules to translate a source ontology into an ontology that uses the vocabulary of a target ontology.
We will develop a suite of Ontolingua translators for standard schema languages (e.g., IDL), data base languages (e.g., SQL), object-oriented programming languages (e.g., C++), and knowledge representation languages (e.g., LOOM). These translators will:
* Support the additional expressive power being added to Ontolingua, and
* Include a declarative translation rule language that enables knowledge base builders to extend and customize the translators for particular uses.
Translating from Ontolingua into a given representation language is in general a difficult problem, because in most cases the expressive power of the target language is less than that of Ontolingua. Hence, there will not be a translation in the target language of every possible Ontolingua sentence. Instead, some subset of Ontolingua will be translatable into the target language. For example, the only form of quantified statement representable in an object schema language might be:
(forall <variable>1) (=> (member-Of <variable>1 <class>) <quantifier_free_sentence>)
All quantified Ontolingua statements that are not in the above form would not be translatable into the object schema language.
In order to translate Ontolingua into a given target language, one needs to specify the subset of Ontolingua sentences that are translatable into the language and the translation of each such sentence. Given such a specification, the task of a translator, then, is to determine for each sentence in the ontology to be translated whether it is in the translatable subset or is equivalent to a sentence in the translatable subset. The test of whether a given sentence is in the translatable subset can be performed by describing the subset as a grammar and applying standard pattern matching techniques for "recognizing" the grammar (Baalen and Fikes 1993; Buvac and Fikes 1994). Thus, for example, we might specify that the following form of quantified statement is representable in a simple target frame language:
(forall <variable>1) (=> (member-Of <variable>1 <class>) {TRANS <sentence>})
where "{TRANS <sentence>}" matches against any sentence that is itself translatable.
The difficulty in the translation arises in determining whether a given sentence is equivalent to a translatable sentence. As simple examples, consider the following sentence forms that are equivalent to the example above:
(forall <variable>1) (=> (class-Of <class> <variable>1)) {TRANS <sentence>})
(forall <variable>1) (=> (<unary relation> <variable>1) {TRANS <sentence>})
In the first form, the "Member-Of" relation has been replaced by its inverse "Class-Of", and in the second, the class is considered to be a unary relation rather than a set. In general, a translator can be considered to have available a set of axioms that can be used to reformulate sentences that are not recognizable by the translation grammar by deriving sentences that are recognizable and therefore translatable by the grammar. For example, sentences of the forms given above could be transformed into translatable sentences by using the following axioms:
(<=> (member-Of ?x ?c) (class-Of ?c ?x))
(<=> (member-Of ?x ?c) (holds ?c ?x))
Translation servers can prepare for requests to translate a given ontology by tasking the ontology server on which the ontology resides with deriving in the background and adding to the ontology translatable reformulations of sentences in the ontology that would otherwise not be translatable.
The ability to tailor the network to circumstances is the key to solving another important problem: the computational difficulties of dealing with the potentially very complex models that can be extracted from a large knowledge base. We will utilize the hierarchical structure of the knowledge base to support the construction of Bayesian networks at varying granularities, as appropriate to the situation. For example, for some problems, units are best represented at the battalion level, while in others, reasoning at the level of batteries is required. In order to support this capability, we will provide algorithms that precompute "compiled" models of higher-level objects, to be used where needed.
The choice of the optimal granularity is a difficult one. We will design algorithms that automatically choose a granularity based on the type of problem for which the model is constructed. In particular, in some situations, no accuracy is lost by going to a less refined model. In others, the accuracy loss is small enough to justify the computational savings. We will provide tools to analyze the loss of accuracy and to automatically choose an appropriate level of granularity. The system will also provide the capability for the user to guide this choice.
While the Bayesian networks constructed can be used by any Bayesian problem solver, they incorporate additional structure derived from the hierarchical structure of the knowledge base. In particular, the locality of the probabilistic influences within frames induces modularity in the resulting network. We will provide Bayesian problem-solving algorithms that are designed to take advantage of this additional structure. These algorithms will support our ability to deal with significantly larger problems than possible using current technology.
Bibliography
Baalen, J. V. and R. E. Fikes. (1993). The Role of Reversible Grammars in Translating Between Representation Languages. KSL-93-67. Knowledge Systems Laboratory.
Buvac, S., V. Buvac, and I. A. Mason. (1995). Metamathematics of contexts. Fundamenta Informaticae 23 (3).
Buvac, S. and R. Fikes. (1994). A Declarative Formalization of Knowledge Translation. KSL-94-59. Knowledge Systems Laboratory.
Erol, K., J. Hendler, and D. Nau. (1994). HTN Planning: Complexity and Expressivity. In Proceedings of the Twelfth National Conference on Artificial Intelligence. Seattle, WA: AAAI/MIT Press.
Falkenhainer, B., A. Farquhar, D. Bobrow, R. Fikes, K. Forbus, T. Gruber, Y. Iwasaki, and B. Kuipers. (1994). CML: A compositional modeling language. KSL-94-16. Stanford Knowledge Systems Laboratory.
Farquhar, A., R. Fikes, and J. Rice. (1996). The Ontolingua Server: a Tool for Collaborative Ontology Construction. In Knowedge Acquistion Workshop, ed. Brian Gaines. Banff,. Canada.
Genesereth, M. R. and R. Fikes. (1991). Knowledge Interchange Format, Version 2.2. Logic-90-4. Computer Science Department, Stanford University.
Genesereth, M. R. and R. E. Fikes. (1992). Knowledge Interchange Format, Version 3.0 Reference Manual. Logic-92-1. Computer Science Department, Stanford University.
Gruber, T. R. (1993). A Translation Approach to Portable Ontology Specifications. Knowledge Acquisition 5 (2): 199-220.
Halpern, J. Y. (1990) An analysis of first-order logics of probability. Artificial Intelligence 46: 311-350.
Karp, P. D., K. Myers, and T. Gruber. (1995). The Generic Frame Protocol. In 14th International Joint Conference on Artificial Intelligence. Montreal, Canada.
Levy, A. Y. (1993). Irrelevance Reasoning in Knowledge Based Systems. Ph.D., Stanford University.
Low, C. M. and Y. Iwasaki. (1992). Device Modeling Environment: An integrated model formulation and simulation environment for continuous and discrete phenomenon. In Proceedings of the First International Conference on Intelligent Systems Engineering: The Institute of Electrical Engineers, London.
McCarthy, J. and S. Buvac. (1994). Formalizing Context (Expanded Notes). Technical Note STAN-CS-TN-94-13. Stanford University.
Mowbray, T. J. and R. Zahavi. (1995). The ESSENTIAL CORBA: System Integration Using Distributed Objects.: John Wiley and Object Management Group.
Patil, R. S., R. E. Fikes, P. F. Patel-Schneider, D. McKay, T. Finin, T. R. Gruber, and R. Neches. (1992). The DARPA Knowledge Sharing Effort: Progress report. In Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference. Cambridge, MA: Morgan Kaufmann.
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Morgan Kaufmann.
Rice, J., A. Farquhar, P. Piernot, and T. Gruber. (1996). Using the Web Instead of a Window System. In Conference on Human Factors in Computing Systems (CHI96):103-110. Vancouver, CA: Addison Wesley.