Tools for Assembling and Managing Scalable Knowledge Bases

A. Abstract

• Current ontology tools support browsing and editing, but they lack support for merging ontologies, pruning them, or extracting focused ontologies from larger ones. These capabilities are essential for rapid construction of large ontologies, since they enable reuse of existing resources.
• Ontology tools provide little help in organizing ontologies into hierarchies, identifying and debugging inconsistencies or maintaining their consistency and completeness.
• Most tools are limited to small to medium scale ontologies by the inherent limitations of their underlying representation systems, and thus cannot support the goals of the HPKB program.
• Some ontology tools are "dead ends" in the sense that the knowledge in the ontologies cannot be used directly in implementations--it must first be translated into some implementation language with some loss of fidelity, making the overall maintenance of systems developed from the ontology more difficult.

B. Innovative Claims

C. Technical Rationale, Approach, and Plan

C.1. Introduction

• Tools and techniques to define, test, verify, validate, and edit large libraries of ontologies, domain theories, and problem-solving strategies;
• Tools and techniques to extend and specialize those ontologies, domain theories, and problem-solving strategies to create new foundation knowledge;
• Tools and techniques to compare and compose independently developed ontologies, domain theories, and problem-solving, especially to compare independently developed or modified theories to detect conflicting information;
• Tools and techniques to translate ontologies, domain theories, and problem-solving strategies among different KR systems and programming languages, and
• Tools and techniques to import data dictionaries, data schemas, lexicons, and knowledge bases from legacy expert systems to create initial ontologies and skeleton theories for elaboration and completion;
• Tools to manage library containing foundation ontologies e.g., space, time, actions and processes, and physical objects, domain theories and KBs for challenge problem domains, and broad coverage ontologies such as the SENSUS/WordNet ontology.
• Web-based tools that enable easy browsing, visualization, and understanding of large libraries of ontologies, and domain theories hyperlinked to multimedia documentation.
• A highly expressive KR system that can represent knowledge for reuse by multiple applications and reasoning at different levels of abstraction and is scalable to effectively represent and reason with large libraries of reusable knowledge bases.

Figure 1. Architecture for the proposed Ontology Server.

Figure 1 shows the proposed structure for the Knowledge Builder system. The proposed system will significantly enhance the capabilities of the current version of the Ontosaurus Ontology Server. The present version of Ontosaurus is built around the Loom KR system. During our implementation of Ontosaurus, we have discovered that a number of capabilities, such as a view mechanism and semantic analysis, require data structures and reasoning capabilities not commonly implemented in KR systems. The proposed implementation will be integrated with PowerLoom, a much more powerful scalable KR system. The PowerLoom system being developed under an existing DARPA contract will provide many of the features we consider important in an ontology server. This effort will extend those features with a particular emphasis on scaling and performance issues. The PowerLoom will provide a wider array of services for ontology construction, validation and maintenance, as well as for the construction of intelligent knowledge-based systems. Other key features of the Ontosaurus-PowerLoom system will be its scalability (to operate on very large knowledge bases), its just-in-time classifier that provide scalable reasoning (workstations can be added incrementally to meet the computational load), and its modular design (to allow user configuration and easier upgrades).

C.2. Ontosaurus Ontology Server

• the collaborative development and maintenance of large ontologies, and KBs.
• a user customizable view mechanism that allows a single ontology to be viewed from multiple perspectives such as the logistics planning and force application.
• tools for constructing application-specific ontologies by composing, merging, pruning, extracting, and customizing components from a library of foundation ontologies and re-usable domain KBs.
• Semantic analysis tools to validate the consistency and completeness of an ontology, detect incompatibilities between ontologies, and highlight semantic differences between successive versions of an ontology.
• tools for translating Loom ontologies into and out of other KR languages, and schemas for programming languages such as C++, CLOS, IDL interface specifications, and , Java objects.

Figure 2. Composing Ontologies	Figure 3. Pruning an ontology

Pruning: The pruning operation allows a designer to delete concepts or a sub-hierarchy of concepts (see Figure 3) that are not needed for a given domain. Some KRSs (including Loom) provide support for recursively deleting all sub-concepts and other concepts which refer to a given concept. In our experience with Ontosaurus, we have identified a number of additional pruning operations that are less drastic than the existing pruning operations. These include selective deletion of offending clauses from the definition of referring concepts and generalization of the definitions to eliminate references to deleted concepts. These additional deletion capabilities will be implemented within the PowerLoom system and made available to the user as options in the pruning process.

Figure 4. Extracting a domain-specific ontology from a broad coverage ontology

Ontology Extraction: One of the most time consuming aspect of modeling a domain is the enumeration and organization of tens of thousands of domain concepts. ISI has been exploring a novel approach to assist in this process using existing broad coverage ontologies such as the SENSUS [Knight and Luk 1994] and WordNet [Miller 1990] ontologies [Swartout et. al. 1996]. Our approach begins by identifying a small number of key domain terms (called seeds). These terms are then mapped to concepts in the SENSUS ontology (Figure 4a). Using a variety of structural and probabilistic heuristics, we then identify concepts in the ontology that relate to the seed concepts (Figure 4b). These concepts delimit the domain relevant aspects of the larger ontology, and are extracted to create an approximate domain-specific ontology (Figure 4c). The designer can then browse this ontology and delete unrelated terms or import additional terms to arrive at an initial domain model. This process was used to create the ACP-SENSUS ontology for air campaign planning (ARPI). Using 50 seed terms provided by experts, an initial ontology of approximately 1200 domain concepts was created in less than a week. A detailed description of this process is in [Swartout et. al. 1996].

Figure 5. Merging parts of one ontology into another.

Knowledge Base Merging: The merging operation allows a designer to augment one ontology or knowledge base by extracting and incorporating selected parts from independently developed ontologies (shown in Figure 5). A prototype of an interactive merging capability was demonstrated at the I*3 workshop in November 1996. In this demonstration, Ontosaurus was used to augment the C2 Schema (JTF-ATD) with more detailed information about combat aircraft from an independently developed ACP ontology (ARPI). During this demonstration, we were able to extend the C2 Schema by approximately 200 additional concepts within 10 minutes, a process which would take hours to days to complete without this tool.

The extraction and merging operation presents a variety of technical challenges. For example, the two knowledge bases may use different naming conventions, they may refer to the same underlying concept with different names, or different concepts with same name. Furthermore, because ontologies are richly interconnected, the process of extracting only selected concepts requires deciding how to isolate the desired portions from the remainder of the ontology. Finally, the axioms and definitions written in the context of the originating ontology must be reinterpreted and made consistent with those in the receiving context. Some of these problems can be solved pragmatically. For example, the problem with naming conventions is solved in the Ontosaurus using a mapping table that can translate between common naming conventions. The problem of name mismatch between ontologies can be solved by mapping concepts in both ontologies to a common reference ontology (e.g. SENSUS) and using the reference ontology for name alignment. The problem of different definitions can be resolved by merging the definitions and allowing the user to resolve conflicts when they arise. The problems with lifting axioms from one context to another, however, is considerably harder and requires fundamental advances in the theory of contexts. We will collaborate with Professor John McCarthy (they have independently submitted a proposal for the development of the theory of contexts) on further development of the formal theory of contexts with the goal of (1) providing formal understanding of the process of combining ontologies, and (2) pragmatically making the merging of ontologies efficient.

Semantic Analysis and Maintenance: General KR systems have traditionally provided powerful reasoning services aimed towards the development of knowledge-based systems. Many of these reasoning services can also be used to develop intelligent tools for the development and maintenance of ontologies. Ontology maintenance, however, requires additional meta-level reasoning capabilities that allow tools to inspect inferences and their logical dependencies. Through the use of Ontosaurus we have identified a number of such reasoning services. These include: (a) identifying undefined concepts and relations, (b) identifying inconsistencies and conflicts within ontologies, (c) verifying completeness, and (d) identifying semantic differences between related concepts. These capabilities are described below.

Undefined terms: The construction of a domain ontology is an incremental process. While this process is in progress, many terms remain undefined. It is essential that the ontology development environment identify these undefined items and allow the user to incrementally complete the ontologies. Furthermore, the KR system must continue to function in the presence of undefined concepts. The current implementation of Ontosaurus provides the capability for identifying and editing undefined concepts. The proposed implementation will extend this capability by providing an agenda mechanism similar to that implemented in Expect system [Gil and Melz 1996; Swartout and Gil 1995] to further enhance the usability of this function.

Inconsistencies and conflicts: A good ontology construction tool must provide capabilities for identifying conflicts and inconsistencies. Furthermore, when such conflicts arise, the tool must assist user in identifying the source of the problem and resolving it. Many KR systems detect logical conflicts, but do not provide enough information to analyze the sources of conflicts (i.e. sets of conflicting assumptions). In the proposed effort we will develop reasoning capabilities for identifying sources of conflicts and develop tools to assist users in detecting and resolving inconsistencies.

Completeness: The completeness of an ontology can be characterized in two ways. First, within the knowledge specification of the ontology, we can verify that all referenced terms are defined, all required fields of an instance are filled, and when a concept is exhaustively partitioned, that all its instances belong to exactly one of the partition subclasses, and that all subsumption relations implicit in the definitions have been made explicit. These capabilities are not only useful during the initial construction of an ontology, but are also essential for continued integrity and maintenance of the knowledge bases. Determining completeness of a KB with respect to the knowledge needed for problem solving-- a task commonly performed by knowledge acquisition tools such as the EXPECT system. In a separate proposal submitted to the HPKB BAA, our team will work closely with ISX (or other selected integration contractors) to integrate Knowledge Builder with problem-solvers and knowledge acquisition tools to support this functionality.

Semantic differences between related definitions: While composing, merging or updating ontologies, one is often faced with the need to identify semantic differences between two concepts ( similar concepts in different ontologies, or the same concept in different versions of a single ontology). To assist in this process, we will develop reasoning capabilities that can compare two concepts to identify semantic differences between them and develop tools for comparing different versions of an ontology. Pairwise comparison between concepts is needed both for merging and maintenance.

Translation Toolkit: Although the ontologies in the ontology library are represented in a common representation language, different knowledge-based systems that use these ontologies will no doubt use a variety of knowledge representation systems and programming languages. To fully benefit from a common ontology development environment, it is necessary to make the ontologies developed in Ontosaurus available in different languages and KR formalisms. The current Ontosaurus system has a small number of translators for producing KIF, Ontolingua, KRSS, and C++. In a companion proposal (PALINDROME, ISX), we will develop a common translation toolkit for the rapid construction of translators based on declarative mappings between PowerLoom and the target language. We will use this toolkit to create additional translators from Loom to IDL and Java. We expect our users to be able to assemble additional translators for translating ontologies into frame-based and logic-based representation languages.

C.3. PowerLoom

1. Scalable Knowledge Base. The server can access a knowledge base of definitions and axioms larger than what can be stored run-time memory. It will efficiently support navigation across the entire knowledge space.
2. Fully expressive. The server will allow concept definitions and axioms at least as expressive as the first order predicate calculus.
3. Efficient deductive support for ontology validation and organization. Today, only servers that include a concept classifier provide an adequate combination of efficiency and depth of inference to support this feature.
4. Deliverable in a commercially-oriented language. Today, this means a C or C++ version of the server.
5. Query processor. The server supports a query language, equivalent to SQL in power, to query all parts of an ontology.
6. Concept editing. Users can edit already loaded concepts (some classifier-based KRSs don't support this).
7. Contexts. Knowledge can be partitioned into a hierarchy of contexts, some of which inherit from others. Reusable ontologies depend on this form of modularity.
8. Scalable Inference. Multiple machines can run in parallel to solve an inference problem (e.g., to classify a concept hierarchy).

• Knowledge Pager. The Knowledge Pager manages the transfer (paging) of knowledge from a backend storage system (e.g., an RDBMS) into run-time memory. The addition of the Knowledge Pager to PowerLoom enables it to manage very large knowledge bases. A research task is to efficiently store and index complex knowledge structures that don't conform to a tabular or object representation.
• Built-in Schema Mapper. Enhancing the Knowledge Pager with the ability to map between pairs of schemas enables PowerLoom to access data from data stores (e.g., legacy data) whose schemas don't conform to its own schemas.
• Configurable Distributed Inference Architecture. By generalizing the Knowledge Pager to interface PowerLoom to another PowerLoom server, we can produce multiple client/server configurations. Then, by adding a mechanism for remote classification and remote query processing, PowerLoom can by configured to reduce bottleneck computations and to accelerate classification and queries using parallel processing.
• Preference-based (Just-in-Time) Classifier. While conventional concept classifiers introduce a computational overhead that increases at least linearly with the size of a knowledge base, PowerLoom's just-in-time classifier has a sublinear overhead (proportional to the quantity of data accessed by an application). We will experiment with preference heuristics that maximize PowerLoom's ability to focus the classifier's efforts only on knowledge accessed by a user or application.
• Java-based PowerLoom. PowerLoom is programmed in a language called STELLA that translates into either C++ or Common Lisp. By developing a STELLA-to-Java translator, we can release C++, Common Lisp and Java versions of the PowerLoom KRS.
• Extensible Classification. Incompleteness of classification-based deduction is unavoidable in a fully expressive KRS. Enhancing PowerLoom with user-extensible classification rules will enable users to augment the deductive capabilities of the classifier to satisfy the specific demands of their applications.

Figure 6. Configurable Distributed Inference Architecture

The Knowledge Pager mediates all accesses between the server and the RDBMS, pulling knowledge structures into the KRS's local memory on demand. The Knowledge Pager wrapper comes in three versions. The first interfaces to the RDBMS. The second version attaches to a client- enabling the client to "page in" knowledge from a remote server. A third version attaches to a "satellite" KRS, and enables that KRS to upload knowledge from a server over a (high bandwidth) local network. These different wrappers make it possible to assemble many different client/server/satellite configurations.

Scalable inference is achieved by (i) moving inference from the central server onto client-side servers or satellite workstations, and by (ii) eliminating the need to reason with knowledge not directly accessed by a user or application. The configurable architecture just described provides the scalable processing power needed to achieve (i). The other piece of needed technology is a "just-in-time" (JIT) classifier. Conventional concept classifiers operate efficiently only in a "batch mode" where they classify all instances and concepts in a knowledge base in one pass. This approach to classification does not scale well. A JIT classifier is capable of classifying any subset of existing concepts and instances, in any order. PowerLoom implements the world's first and only JIT concept classifier. Having a JIT classifier means that portions of a knowledge base can be transferred onto a client or satellite processor and classified independently of the central server. The results of such classifications (which have a very concise encoding) are returned to the server to be shared by all clients. Thus, the sharing of processing described in (i) above becomes feasible. The batch mode approach to classification used by conventional classifiers requires that all concepts and instances in a knowledge base be classified. This makes the process of loading very large knowledge bases increasingly slow, i.e., the batch classification process does not scale well (for example, Loom hits an upper limit around 50,000 concepts). A JIT classifier makes it possible to classify only those portions of a knowledge base actually referenced by an application, leaving the remainder of the KB untouched. The overhead of classification can be sublinear in the size of the KB, solving the objective of (ii) above.

A. Bibliography