We propose to develop and to experimentally validate an integrated suite of mixed-initiative multistrategy learning and reasoning methods, an end-to-end methodology, and an integrated shell for rapid knowledge formation and reasoning. The developed technology will enable a distributed team of SMEs that do not have prior knowledge engineering experience to rapidly construct, update and extend a high quality integrated knowledge base for a complex application. This technology relies on developing a very capable learning and reasoning agent, called Disciple-RKF, that can collaborate with an SME to develop its KB consisting of an ontology that defines the terms from the application domain, and a set of general problem solving rules expressed with these terms. The process of developing the KB of the agent consists of importing ontological knowledge from existing repositories of knowledge, and on teaching the agent how to perform various tasks, in a way that resembles how the SME would teach a human apprentice.
The Disciple-RKF agent will have special capabilities for collaboration management, KB slicing, and KB merging that will allow a team of SMEs to rapidly build an Integrated Knowledge Base. Each SME will interact with a personal Disciple-RKF agent to build a portion of the IKB, to integrate it within the IKB, and to communicate with the other SMEs.
Much of the power of Disciple-RKF comes from several levels of synergism on which it is based, as indicated below.
Synergism between a team of SMEs that collaborate in developing an integrated KB
Several features of the proposed approach facilitate collaborative knowledge acquisition:
· The knowledge base is structured into an ontology that defines the terms of the representation language, and rules that are expressed using these terms. As a consequence, the SMEs have to agree on the shared ontology but they can develop the rules independently.
· The KB to be built is divided into parts that are as independent as possible with an SME responsible for development of each of the parts. The team leaders coordinate the partitioning and the integration of the KB, and facilitate a consensus among the SMEs concerning the developed knowledge that is to be shared.
· The integrated KB consists of a hierarchy of component KBs that are each internally consistent, but may contain portions that supersede or contradict portions from other KBs. This corresponds to the fact that the knowledge model of an SME is internally consistent but it may contain knowledge that contradicts aspects of the knowledge model of another SME. This KB organization not only facilitates knowledge acquisition from multiple SMEs, but also leads to a KB that can provide solutions to problems from different points of view.
Synergism between an SME and a Disciple-RKF agent that collaborate in developing a part of the IKB
The SME-Disciple team will be a mixed-initiative system that will integrate human and automated reasoning to take advantage of their respective communication capabilities, reasoning styles and computational strengths. This system will be based on a division of responsibility between the expert and the agent for those elements of knowledge engineering for which they have the most aptitude, such that together they form a complete team for KB development. This will require the coordination of the dialogue between the human and the agent, and the shift of initiative and control during problem solving, knowledge acquisition and learning.
The SME and Disciple will solve complex problems that include routine steps, innovative steps, inventive steps and creative steps, where the agent contributes more with the routine and the innovative steps, and the expert contributes more with the inventive and the creative ones. In the process, the agent will learn from the contributions of the expert, and its problem solving capabilities will evolve. Therefore, situations that initially required innovative problem solving steps for the agent gradually evolve to require routine steps, and those that required creative steps gradually require inventive steps, then innovative steps and ultimately routine steps. This mixed-initiative reasoning process will lead to a seamless integration of domain modeling and problem solving where the agent will help the SME with domain modeling and the SME will help the agent with problem solving. Because, up to now, the domain modeling was always done manually, this capability will make it possible to dramatically improve the rate of KB development, and will also lead to a significant increase in the quality of the developed KB.
Synergism between different learning methods employed by Disciple-RKF
Building on our previous work in machine learning, we will develop powerful and general methods of multistrategy learning that integrate complementary learning methods (such as inductive learning from examples, explanation-based learning, learning by analogy, abductive learning, learning by experimentation) in a dynamic, task-dependent way. This will enable the Disciple-RKF agent to learn from the human expert in situations in which no single strategy learning method would be sufficient. In particular, we will improve the previously developed multistrategy rule learning and refinement methods, and will develop new multistrategy methods for learning and refinement of the ontology. We will also develop multistrategy learning methods for discovery of ontological knowledge, as well as innovative methods for KB revision based on libraries of cases of problem-solution pairs.
Powerful and flexible solution for language to logic translation
The mixed-initiative approach, which is at the core of Disciple, coupled with Disciple’s ability to acquire knowledge about language and other media, brings about a synergy between interaction and acquisition that will allow the SME to teach Disciple in a natural way not only domain knowledge but also knowledge underlying the communication with natural language and diagrams. Thus, the Disciple agent will become increasingly able to understand the SME and to represent the natural language phrases of the SME into an equivalent logical representation. This, in turn, will make it easier for the SME to teach Disciple increasingly more complex knowledge.
Disciple-RKF eliminates the distinction between KB development and KB maintenance.
In the Disciple approach the whole process of developing the KB is one of creating and refining or adapting knowledge pieces to better represent the domain model of an SME. The same operations are involved in updating the KB in response to changes in the application environment or in the goals of the KB, that is, in maintaining the KB. Therefore, in the life-cycle of a Disciple KB there is no distinction between KB development and KB maintenance. If we take into account that the Disciple approach significantly speeds up the process of KB development (as demonstrated in the HPKB program), and that, traditionally, KB maintenance costs are about four times the (already high) KB development costs, then we can conclude that Disciple-RKF will have a very significant positive impact on KB development and maintenance costs.
Why will Disciple-RKF achieve the programmatic goals of the DARPA’s RKF program?
The short answer is that the Disciple approach reduces the complex operations required to build a KB to simpler ones that can be performed by an SME. In general, building a KB requires a knowledge engineer and an SME to create an ontology and to define a set of problem solving rules. These, in turn, require them to create sentences in a formal language, and to formulate general explanation patterns for the problem-solving behavior of the knowledge based system. Each of these operations is transformed into a simpler one in the Disciple approach. Rather than creating an ontology from scratch, one can import it from a repository of knowledge and update it accordingly. Rather than defining general problem solving rules the SME needs only to provide specific examples because Disciple can generalize them into rules. Rather than creating sentences in an unfamiliar formal language, the SME needs only to understand sentences generated by Disciple and select the relevant ones. Rather than providing explanations to the system the SME may only need to provide hints and allow the agent to find the explanations. Finally, Disciple-RKF builds on Disciple-COA that was developed as part of the HPKB program, and was already successfully used by military experts from the US Army Battle Command Battle Lab (BCBL) at Fort Leavenworth Kansas to rapidly extend a KB, with minimal training and assistance from a knowledge engineer. Moreover, GMU will cooperate with BCBL to develop, test, and evaluate Disciple-RKF, with periodic evaluations taking place in the BCBL “Futures Lab” at little or no cost to DARPA. This will create an innovation rich environment that is not likely to be matched elsewhere.
We propose to deliver advanced knowledge formation technology implemented into a set of tools called Disciple-RKF. Disciple-RKF will be used by distributed teams of SMEs to enter and modify knowledge directly and easily, without the need for specialized training in knowledge representation, acquisition, or manipulation.
The complete architecture of Disciple-RKF is presented in Figure 1. This complete architecture contains both base components and optional components (the ones marked with *).
The base architecture of Disciple-RKF has very strong knowledge formation capabilities and flexible human-KB interaction capabilities, but only minimal theory manipulation capabilities. Also, this version of Disciple will be developed to address the Expert Knowledge challenge problem. The tools for entering Textbook Knowledge will be developed primarily for teams of knowledge engineers and SMEs.
The complete architecture of Disciple-RKF is an integrated system that addresses both types of challenge problems. It contains additional advanced components for knowledge formation, human-KB interaction and theory management. However, the optional components are defined in such a way that each one adds new functionality to the system independent of the presence of the other optional components.
Disciple-RKF will be built starting from the current version of Disciple, called Disciple-COA, that was developed as part of the HPKB program. Therefore some of the tools of Disciple-RKF will be significantly improved versions of the corresponding Disciple-COA tools.
This tool will be a central component of Disciple-RKF. It will allow the SME and the Disciple-RKF agent to jointly find solutions to the attempted problems that include routine steps, innovative steps, inventive steps and creative steps, where the agent contributes more with the routine and innovative steps, and the expert contributes more with the inventive and creative ones. In this process, the agent will learn from the contributions of the expert, therefore the situations that initially require innovative problem solving steps for the agent will require gradually only routine steps. Also, the situations that initially require creative steps gradually will require inventive, then innovative and ultimately routine steps. The learning itself will be done by the other modules of Disciple, starting from the examples and the context provided by this tool. A very important characteristic of this tool is its flexibility. It will behave as a domain modeling tool when all or most of the steps required to solve a problem are creative. It will behave as problem solver when most of the required steps are routine. Finally, it will behave as a mixed domain modeling and problem solving tool for the other situations, involving all the four different types of problem solving steps: creative, inventive, innovative and routine. The interface to the expert, however, should not be different in any of these different circumstances.
A very important capability created by this tool is that the agent will be able to help the SME with domain modeling, something that up to now has always been done manually. We think that this capability will dramatically improve the rate of knowledge base development, and will also lead to a significant increase in the quality of the developed KB.
During the HPKB program we have developed a cooperative problem solver. We have also developed a domain modeling methodology but have not yet developed any domain modeling tool. We propose to build on these results in order to build this very flexible and powerful domain modeling and problem solving tool.
A separate but closely related tool is the autonomous problem solver. This tool will be used to automatically generate solutions without any intervention from the user, its problem solving steps being mostly routine and innovative. This tool will be an improved and expended version of the current autonomous problem solver of Disciple-COA.
This tool will be the other central component of Disciple-RKF. It will integrate and significantly extend the functionality of two tools from the current version of Disciple, the Rule Learner and the Rule Refiner. The objective of rule learning is to create a justified generalization of an example of a problem-solving episode. The objective of rule refinement is to improve a learned rule through the use of additional positive and negative examples of the rule. Both methods are based on apprenticeship and multistrategy learning, incorporating in a synergistic way learning from explanations, empirical learning from examples, analogical learning and abductive learning.
The existing rule learning and refinement modules of Disciple deserve most of the credit for the high rate of knowledge acquisition and the high problem solving performance achieved during the HPKB program (see Figure 6 for a summary of these results). The most important aspect is that they reduce the complex knowledge engineering task of manually defining and debugging a complex problem solving rule, to a sequence of much simpler operations that can be performed by an SME without any assistance from the knowledge engineer. The SME may interact with the tool by providing a concrete example of how to solve a problem or by simply analyzing an example generated by Disciple and characterizing it as correct or as incorrect. Then the SME has to help the agent to understand why the example is correct or why it is incorrect. However, most of the time the expert does not even need to provide an explanation because the agent may be able to propose plausible explanations by itself and the SME needs only to select the relevant ones. If the agent does not have enough knowledge about the current example to propose a reduced set of plausible explanations, then the SME may provide the agent some simple hints (such as pointing to a relevant object in the example). It is likely to be very difficult for an SME to give a formal explanation, and it may be just as difficult for the agent to understand a natural language explanation, but we reduce this complex action to a much simpler mixed initiative approach. The SME needs only provide a hint, and then based on this hint the system generates explanations (in natural language for instance). Finally, the SME needs only to select one of the explanations generated by the agent. The research in rule learning and refinement described in section 4.6 will make the teaching of the Disciple agent by the SME significantly more natural and easier. This is one of the main reasons we are very confident that the proposed approach will achieve the goals of the RKF program.
We think that much of the Expert Knowledge (as opposed to Textbook Knowledge) will be expressible as problem solving rules. Therefore we believe that the base version of Disciple-RKF, which includes the Rule Learning and Refinement Tool, will be well suited to address the Expert Knowledge Challenge Problem.
The browsers and editors will be improved versions of the current tools from Disciple-COA. They will be part of the base Disciple-RKF version. A characteristic feature of these browsers and editors is that they are specialized for the types of knowledge pieces in Disciple’s ontology. For instance, there is an object editor, an object feature editor, a task feature editor, a task editor and a rule editor. Although they have the same look and feel, the fact that they are specialized to a certain type of knowledge allows many operations to be automated because Disciple can make more assumptions about the knowledge piece to be defined. These editors and browsers will have a certain degree of “intelligence”, based on some control “wizards” that attempt to anticipate the most probable parameter settings in a tool and to pre-select them when the tool is invoked. The wizards will also help the user with the more complex operations. For instance, one of the wizards will be the delete wizard. This wizard will be automatically invoked when the user attempts to delete an element from the knowledge base. It will guide the user through a sequence of modifications of the KB that are necessary in order to maintain the consistency of the KB.
This tool will allow Disciple to learn and refine objects, features and tasks in a similar way to how it learns and refines rules, by using various learning strategies. There is no corresponding tool in the current version of Disciple. However, based on our experience with the development of the rule learning and refinement methods, we believe that we can develop and implement methods that will make as easy to learn the ontological knowledge pieces from specific examples as it is to learn rules from examples. This tool will allow the SME to communicate with Disciple by using concepts and features that are not yet defined in Disciple’s ontology. Disciple will attempt to learn the general definitions of these concepts and features by taking into account the context in which the new concepts and features are defined, performing analogies with known objects and features, and conducting a clarification dialog with the user.
The ontology learning and refinement tool is proposed as an optional component of Disciple-RKF. However, if funded, this would be the 3rd central component of Disciple. Its development would allow Disciple-RKF to also solve the Textbook Knowledge challenge problem.
The ontology import-export tools will allow Disciple-RKF to exchange knowledge with other knowledge servers, primarily with the CYC-based server. The current version of Disciple contains a specialized MELD to Disciple problem translator that allowed us to receive a problem (a COA to critique) in the MELD representation language, to represent it in Disciple, and to generate solutions in natural language. This was possible because both CYC and Disciple have shared much of their ontologies, including the input ontology. This capability was achieved in the HPKB program by importing the CYC’s COA ontology into Disciple.
We propose to develop two types of ontology import/export tools, one to be used by a Knowledge Engineer (this will be a component of the base Disciple-RKF version), and one to be used by an SME (this will be an optional component proposed for the integrated Disciple-RKF system).
The base Disciple-RKF version will contain an ontology import-export tool to be used by a knowledge engineer. This tool will translate ontological knowledge between MELD and Disciple and will be used to exchange ontological knowledge with the CYC-based Integrated Knowledge Base (IKB). To import knowledge from CYC IKB, first CYC’s ontology will be automatically translated into an “witness” Disciple KB. Then Disciple’s ontology browsers and editors will be used to transfer knowledge from the witness KB into the Disciple’s KB. Latter, changes in the CYC’s IKB will be reflected in changes in the “witness” KB so that future import operations from CYC’s IKB can concentrate only on the changes that have taken place in CYC’s IKB from the last import operation. Knowledge export from Disciple to CYC or other knowledge server will take place in a similar way. First Disciple’s ontology will be translated into MELD and then it will be incorporated into CYC’s IKB. We will also develop a MELD-Disciple problem/solution translator, to exchange problems and solutions between CYC and Disciple.
As an option, we also propose to develop a mixed-initiative ontology import-export tool that can be used directly by SMEs. The core of this tool will be the KE version of the import-export tool that will be extended as described below.
The translation of an external ontology from MELD (or other language, such as KIF) into a “witness” Disciple KB will be done automatically, using the translation module of the KE version. However, the searching and importing of knowledge from the “witness” KB into Disciple will now be done by a specialized Disciple agent that was specially trained for this purpose. For instance, in the case of CYC’s IKB and MELD, the Disciple importing/exporting agent will learn a correspondence between the equivalent concepts in CYC and Disciple. It will also be taught the naming conventions of CYC and Disciple. For instance, it can be taught that the names of CYC concepts may include the names of their superconcepts, subconcepts or instances (e.g., “ScreenMilitaryTask” includes “MilitaryTask” and part of “Screen1”). The Disciple importing/exporting agent will then be able to receive requests to search the witness KB for some ontological knowledge that satisfies a given specification. The search will involve natural language-based flexible matching strategies. The search request could come from the SME who has just identified the need for some new type of ontological knowledge (such as “weapon agents”) and wants to import this knowledge from the “witness” KB. Alternatively, the request may come from other components of Disciple-RKF, particularly the ontology learner, the ontology refiner and the ontology discovery tool. Each of these tools may generate an incomplete specification of some ontological knowledge and may ask the Disciple importing/exporting agent to search the “witness” KB for it.
This is an integrated set of tools that facilitate the communication between the SME and the Disciple-RKF agent. It includes a Dialog Management Tool, a Natural Language Understanding Tool, a Natural Language Generation Tool and, as options, a Sketch Input/Output Tool and a Voice Input/Output Tool.
The Dialog Management Tool is the central component of this set of tools. It exploits the complementary communication capabilities of the SME and the Disciple agent, namely, that it is easier for the agent to generate natural language sentences than to understand them, and that it is easier for the expert to understand sentences generated by the agent than to create sentences in the agent’s formal language. For instance, when the SME expresses some natural language sentence, the agent may need to generate alternative sentences, asking the SME which of them corresponds best to the input sentence. If the input sentence contains some unknown word, the agent will use the contextual information to guide the SME in defining a new concept or a new relation that corresponds to that word. If the agent needs an answer to some question, it may formulate the question and may hypothesize possible answers, asking the SME only to select the right answer. If the agent cannot generate an answer, then the expert may provide the agent some helpful hints to generate it. This type of communication is a generalization and extension of the types of interactions used by the current version of Disciple. Using its learning capabilities the agent will continuously learn the language of the SME. Therefore both its and the SME’s communication proficiency will continuously improve during their interaction.
Many types of communication are greatly facilitated by the use of sketches and sound. Therefore, we propose (as options) to explore a natural integration of various communication media, together with their appropriate representation in the knowledge base, and with corresponding output generation capabilities. This would be realized by the development and integration into Disciple-RKF of the Sketch Input/Output Tool (optional component) and of the Voice Input/Output Tool (optional component). The Sketch Input/Output Tool will be based on the corresponding tool developed by Henry Hamburger for the FLUENT system. The Voice Input/Output tool will be based on a commercial tool for voice recognition and generation.
The mixed-initiative approach, which is at the core of Disciple, coupled with Disciple’s ability to acquire knowledge about language and other media, brings about a synergy between interaction and acquisition that will allow the SME to teach Disciple in a natural way not only domain knowledge but also knowledge underlying the communication with natural language and diagrams. Thus, the Disciple agent will become increasingly able to understand the SME and to translate the natural language phrases of the SME into equivalent logical representation. This, in turn, will make it easier for the SME to teach Disciple increasingly more complex knowledge.
This is a set of tools for a knowledge engineer and an SME that helps in managing the development and integration of the KBs developed by the distributed teams of SMEs. It includes a Collaboration Management Tool and, as options, a Collaborative KB Merging Tool and a Collaborative KB Slicing Tool.
When a new expert joins the KB development team, she or he will not start from scratch but from an existing structured KB (see Figure 1). Therefore, the first thing that needs to be done is to create his or her view of the Integrated Knowledge Base. This activity will be supported by the Collaborative KB Slicing Tool (optional component). The purpose of this tool is to assist the new SME to become familiar with the content of the IKB and to identify the part of that knowledge base that is consistent with his or her representations and beliefs. The new SME will be allowed to redefine some of the KB components, gradually building a personalized KB that will be linked to the shared KB. As the SME will develop his or her part of the IKB, the team leader will attempt to incorporate as much as possible of it into the shared KB (while still preserving in that expert’s KB the knowledge that reflect his or her personal views that are not shared by the other experts). This activity will be based on a negotiation with the other SMEs and will be assisted by a Collaborative KB Merging Tool (optional component).
The Collaboration Management Tool is to be used by a team including a knowledge engineer and an SME that has the role of leading the collaborative knowledge based development effort (see Figure 1). This tool is based on a specialized Disciple-agent that will be developed to manage the communication between the SMEs that build the KB components. It will also assist in achieving a consensus between the SMEs on the created knowledge that is to be shared. It will also assist in KB merging and slicing, in the basic version of Disciple-RKF that does not contain the Collaborative KB Merging Tool and the Collaborative KB Slicing Tool.
In Disciple the ontology serves as the generalization hierarchy for learning. However, this ontology is incomplete and even partially incorrect, and it is itself evolving. The missing or imperfect concepts will manifest themselves as exceptions to the learned problem solving rules.
This mixed-initiative ontology discovery tool will identify a specification of new ontological knowledge that can be included in the ontology to improve the completeness and the consistency of the problem solving rules. Then this specification will be used to guide the elicitation of the corresponding concepts or features from the SME or to import them from an external repository, in conjunction with the Ontology Import Tools. There is no corresponding tool in the current version of Disciple.
This tool will be based on two classes of discovery methods, a class of local methods and a class of global methods. The local methods focus on one rule with its exceptions at a time, in conjunction with the current ontology. They will lead to the improvement of the descriptions of the concepts from the rule’s exceptions, by analogy with the concepts from the rule’s examples. The global methods will analyze all the rules with exceptions from the KB to discover a smaller set of new concepts that will collectively reduce the number of exceptions from all the rules.
This tool is based on the concept of a Plausible Justification Tree (PJT) described in section 4.6 (see also Figure 5). It will allow the incorporation into the knowledge base of the expertise represented in the repositories of previously solved problems and their complete solutions. The tool will receive as input a repository of previously solved problem P1, …, Pn, and their solutions S1, …, Sn, and will improve the KB such that, when the system receives the problem Pi it will generate and return the corresponding solution Si. This tool may be used in the interactive or in the autonomous mode, depending on the amount of knowledge in the KB of Disciple-RKF.
This tool is intended to take advantage of a common practice to maintain records of previously solved problems and their solutions. Assuming that the agent has already learned a certain number of rules in the domain, it can use the known problems and solutions to refine these rules and to learn new ones. As discussed in section 4.6, this tool will attempt to build the most plausible justification trees that can derive the solutions S1, …, Sn for the problems P1, …, Pn. The general intuition on which this tool is based is the following one: because it is known that Si is the correct solution to Pi then the reasoning steps from the most plausible tree that links Si to Pi are most likely to be correct. Therefore they are interpreted as positive examples of the rules that have generated them, and these rules could be generalized accordingly.
All of the developed tools will be instrumented to collect various types of data concerning the knowledge formation process and the interaction with the SME, as described in Section 4.9 “Claims and experimental evaluation.” In addition, we will develop a special Disciple-RKF module that will aggregate the collected data to produce evaluation results, as required by the Evaluation Contractor and by our specially developed, claims evaluation methods.
In addition to the developed software, deliverables will also include monthly reports of contract funds expended, presentation materials for meetings and conferences, and technical reports as required. Semi-annual demonstrations of deliverables will also be provided as part of In Process Reviews.
The following are the most important expected results of the proposed research:
· A mixed-initiative theory and methodology for developing, extending and updating an integrated knowledge base that will allow a collaborating team of SMEs that do not have prior knowledge engineering experience, to easily build large, comprehensive, and verified knowledge bases, by performing familiar tasks, similar to those performed when teaching an apprentice.
· Powerful, mixed-initiative, methods for problem solving, rule learning, rule refinement, ontology learning, ontology refinement, ontology discovery, knowledge import/export, and case-based knowledge revision. These methods will constitute the building blocks of the above theory and methodology.
· The implementation of the developed methods and associated methodology into a general learning agent shell, called Disciple-RKF, that can be trained by an SME to solve problems from a given expertise domain and to build a corresponding KB. A team of SMEs can also collaborate in developing an integrated KB, each using a personal copy of Disciple-RKF.
· A general approach to the experimental evaluation of mixed-initiative knowledge base development methods, methodologies and tools.
The products of this research will consist of:
· A set of integrated tools constituting the Disciple-RKF Learning Agent Shell, and associated documentation.
· Several knowledge based agents and an integrated knowledge base developed in connection with solving the BW challenge problems.
· The developed integrated knowledge base maintained as a reusable repository of knowledge.
The transferable technology will consist of:
· The developed learning, knowledge acquisition and problem solving methods and techniques.
· The developed methodology for building knowledge bases and knowledge based agents.
· The developed Disciple-RKF Learning Agent Shell and associated documentation.
· The developed agents and knowledge bases.
We will deliver the developed shell, agents, knowledge bases and associated documentation to laboratories and other government institutions that will be interested in using them. In particular, given our cooperation with BCBL, we expect that this technology transfer will not occur at the end of the RKF program, but it will be a continuous process.
We will also facilitate the transfer of the developed technology to other government and military organizations that will be interested in using Disciple. For instance, representatives of the US Army War College and GMU have agreed in principle to use Disciple cooperatively to investigate the application of artificial intelligence and machine learning to study the concept of “center of gravity” in military operations and other related topics. As with BCBL, this relationship will serve to greatly enhance GMU’s ability to develop, test and evaluate Disciple in the RKF challenge problem domain and other related defense topics at no additional cost to DARPA.
We will present the developed methods, methodology and shell in undergraduate and graduate courses at George Mason University, and will provide support for presenting these results at other institutions of higher education. For instance, representatives from both the US Army War College and Naval PostGraduate School have expressed interest in using Disciple and the Disciple-based agents in their courses.
We will participate in technical meetings and conferences, and will publish papers to report on results of our research to the larger technical and academic community.
George Mason University will bring Background Intellectual Property to this project. "Background Intellectual Property" means property and the legal right therein of either or both parties developed before or independent of this project including inventions, patent applications, patents, copyrights, trademarks, mask works, trade secrets and any information embodying proprietary data such as technical data and computer software.
The following Background Intellectual Property of GMU may be used nonexclusively and, except as noted, without compensation by the federal government, in connection with research or development activities for the DARPA proposal entitled "Collaborative Assistant for Rapid Knowledge Formation and Reasoning."
Background Intellectual Property: Disciple and systems based on Disciple.
The development of Disciple-RKF is based on a series of versions of the Disciple software that will be made available for this project at no cost. Disciple-RKF will be developed in the Learning Agents Laboratory of George Mason University, led by Gheorghe Tecuci. George Mason University will retain rights to the commercial application of Disciple-RKF and of any software that is developed using Disciple or Disciple-RKF as a base.
Generally, a knowledge base is developed by a knowledge engineer who attempts to understand how the SME solves problems and then formalizes this understanding. For several years we have been investigating a different, mixed-initiative, approach. This approach, relies on developing a very capable learning agent shell (called Disciple) that can collaborate with the SME so that together they can perform all the functions of a knowledge engineer (Tecuci 1998; Tecuci et al., 1999). The SME will teach the Disciple agent how to solve domain specific problems in a way that resembles how the expert would teach an apprentice. The expert may give the agent specific examples of problem solving episodes, will help it to understand them, and will supervise and correct its behavior, as the agent attempts to solve related problems. The agent, on the other hand, will learn from the SME, generalizing the examples into rules, refining the rules, and integrating them into its knowledge base.
Significant progress has been made in the development of the Disciple approach as part of the DARPA HPKB program where it has been applied to two challenge problems, the Workaround challenge problem and the Course of Action (COA) Critiquing challenge problem. In both cases, the results obtained by our team were superior to the results obtained by other teams attempting the same challenge problems, both in terms of the speed of knowledge acquisition, and the performance of the resulting systems, as is presented in Figure 6.
Stimulated by attempting to solve these challenge problems, the Disciple approach has evolved very rapidly through a sequence of significant milestones. In 1997-1998, its application to the Workaround challenge problem showed that a knowledge engineer can rapidly build a knowledge base capturing knowledge from Military Engineering manuals. During the 17 days of the DARPA evaluation, the KB of Disciple has increased by 72% with almost no decrease in performance (Cohen et al., 1998). The resulting workaround reasoner was selected to represent the HPKB program at EFX’98, the Air Force showcase of the most promising technologies.
During the 1998-1999 period of the HPKB program, several other significant milestones were successfully achieved. For the first time, we have developed a knowledge base around an ontology created by another group (Teknowledge and Cycorp), demonstrating the generality of the Disciple rule learning methods. Moreover, the Disciple knowledge base exhibited the best problem solving performance among those developed to solve the Course Of Action (COA) challenge problem. An interesting aspect is that the scores of our system were significantly higher even than the scores corresponding to the model answers (for instance, 114.69% for the total score). While an explanation of this result is that our system was trained by a very experienced active duty Army officer, it none-the-less demonstrates the high potential quality of Disciple-based agents which can be almost as good as the experts that train them. We have again demonstrated a very high rate of knowledge acquisition, the knowledge base increasing with 46% during the 8 days of the HPKB annual evaluation. Finally and most importantly, we have successfully performed a knowledge acquisition experiment at the Battle Command Battle Lab in Ft. Leavenworth, KS, where four military experts with no prior knowledge engineering experience have each succeeded to significantly extend the knowledge base of Disciple, while receiving only very limited support from a knowledge engineer.
The progression of these results demonstrate that the Disciple approach can be developed to achieve the central objective of the RKF Program, namely to enable SMEs to enter and modify knowledge directly and easily, without the need for specialized training in knowledge representation, acquisition, or manipulation. Indeed, we believe that the current methods of Disciple can be very significantly extended and improved and new methods can be developed, as will be briefly described in the rest of this section.
We will first present the proposed architecture of the Disciple-RKF agent that interacts with a single SME to jointly build and extend a knowledge base. Then we will describe a distributed architecture where several SMEs interact with several Disciple-RKF agents to rapidly build a large integrated knowledge base. After that we will present our proposal to overcome the main technical barriers encountered in each of the main technology areas of interest for this research program: knowledge content, human-KB interaction, knowledge formation, and theory manipulation.
The proposed architecture of Disciple-RKF is presented in the upper right side of Figure 1. At a general level, it is organized into four main components:
1) the intelligent user interface component,
2) the multistrategy learning and problem solving component,
3) the knowledge base management component and
4) the import/export component.
These components are linked together by the key mixed initiative manager module.
The intelligent user interface contains several modules that allow the SMEs to communicate with the agent in a manner as close as possible to the way they communicate in their environment. Its central component is the dialog manager that controls the interaction between the expert and Disciple.
The multistrategy learning and problem solving component is responsible for knowledge formation and problem solving. It contains specific modules for rule learning and refinement, ontology learning, ontology discovery, KB revision, domain modeling and problem solving. The synergism between learning and problem solving is governed by the mixed initiative manager and implemented through the cooperative domain modeling and problem solving module.
The knowledge base management component is constructed based on an OKBC framework (Chaudhri et. al, 1998) but with slight modifications to correspond to the Disciple knowledge representation. A dedicated collaboration management module controls KB operations in a multi expert environment. Optional modules for merging and slicing the KB based on the same mixed initiative philosophy are also present.
The import/export component includes modules for ontology import and export and for translation between the MELD language and the Disciple language.
Disciple-RKF builds on the Disciple-COA. Therefore some of its components are significant extensions of the corresponding Disciple-COA components, as indicated in Section 2.
The upper left side of Figure 1 represents a team of SMEs that collaborate to rapidly build an integrated KB. Each individual SME works with a personal Disciple-RKF agent to build a part of the integrated KB. These separately developed KBs are periodically integrated into a single KB by the team leaders that include a knowledge engineer, a subject matter expert, and a Disciple agent specialized in knowledge integration. The team leaders not only integrate the KBs, but also mediate the collaboration between all the experts from the team.
Several features of the proposed approach facilitate collaborative knowledge acquisition:
· The knowledge base is structured into an ontology that defines the terms of the representation language, and rules that are expressed using these terms. As a consequence, the SMEs have to agree on the shared ontology but they can develop the rules independently.
· The KB to be built is divided into parts that are as independent as possible with an SME responsible for development of each of the parts. The team leaders coordinate the partitioning and the integration of the KB, and facilitate a consensus among the SMEs concerning the developed knowledge that is to be shared.
· The integrated KB consists of a hierarchy of component KBs that are each internally consistent, but may contain portions that supersede or contradict portions from other KBs. This corresponds to the fact that the knowledge model of an SME is internally consistent but it may contain knowledge that contradicts aspects of the knowledge model of another SME. This KB organization not only facilitates knowledge acquisition from multiple SMEs, but also leads to a KB that can provide solutions to problems from different points of view.
In defining the content and the structure of Disciple’s KB we are primarily addressing the following challenges: knowledge reuse, easy formation of knowledge by an SME, accommodation of multiple (and partially conflicting) domain models, and problem solving from different points of view.
Teams of experts brought together to build and use an Integrated Knowledge Base will generally consist of experts with different backgrounds, levels of experience, and areas of expertise. In the BW domain, problem-solving teams are likely to include experts on terrorist and transnational organizations, experts on chemical and biological agents, and manufacturing and production facility experts. Each of these experts may have their own perspective on what the important issues and knowledge fragments are for related topics. For example, all three types of experts mentioned above are likely to be interested in the presence and capability of production facilities in a country of interest, but each with their own twist. The expert on terrorism is likely to be most interested in the possible ties between terrorist groups and the owners/controllers of the production facility. The biological agent expert may be most interested in the technical details of the machinery present in the production facility. The production facility expert may be most interested in production, storage and transportation capabilities of the facility. These experts may look at the same knowledge fragment, for example the known presence of a precursor chemical for a BW agent, and reach different and possibly unrelated conclusions. The terrorism expert may use this fact to reach a conclusion about what terrorist organization may be using the facility. The BW agent expert may use this fact to narrow his assessment of what agents might be produced at the facility, and the manufacturing expert may use the fact to determine what mode of transport is being used to bring BW agents out of the facility.
A collaborative problem solving system must allow each of these experts to add concepts, instances and rules to support their individual problem solving methods even if these inputs lead to contradictory assessments. The real power in a collaborative system will be taking these individual perspectives and approaches to problem solving based on individual expertise, experience and focus, and merge them into a much more holistic approach to solving more complex problems.
The KB of Disciple consists of an ontology that defines the concepts from a domain and a set of rules expressed in terms of these concepts. This allows us to clearly separate the knowledge that is characteristic to a certain domain (the ontology) from the knowledge that is specific to a certain application in that domain (the rules). For instance, in the BW domain, knowledge that is characteristic of this domain includes ontological entries for the organizational characteristics of terrorist, transnational, and national entities, uses and characteristics of biological and chemical materials, and manufacturing and transportation facilities. This type of knowledge is very likely to be useful in almost any BW application. On the other hand, specific BW applications, such as the assessment of what BW agent a particular manufacturing facility is able to produce, will require problem solving rules that are specific to that application, such as rules dealing with particular types of machinery. Therefore, in the proposed methodology, we develop the ontology of the agent by importing concepts from previously developed ontologies. In particular, we will use and build upon the integrated ontology that was developed as part of the HPKB program (to which we have also contributed).
To respond to the above requirements, the knowledge base of Disciple will be organized as a hierarchy of component KBs, as indicated in the lower right side of Figure 1.
The top level KB will contain knowledge that is shared by all the SMEs, such as the upper ontology. Most of this knowledge will be imported from (and will reflect) the CYC-based IKB. Intermediate KBs will contain knowledge that is shared by several but not all the SMEs. The leaf KBs will contain the knowledge that is specific to a particular subject matter expert.
The KB seen and developed by the expert E1, for instance is KB1, KB2 and KB4, while the KB seen and developed by the expert E2 is KB1, KB2, KB3 and KB5. The task of the mediating team is to integrate the knowledge developed by each SME into the common KB, mediating between the different experts in order to maintain the integrity and acceptability of this KB, while allowing for differences between the component KBs. In the base version of Disciple-RKF, the mediating team is responsible for importing/exporting knowledge between Disciple and the CYC-based IKB. However, we also propose (as an option) to develop the technology that will allow each SME to import knowledge from an external repository. This aspect is discussed in more details in section 4.7 (see also 2.2.5).
The proposed organization of the Disciple’s KB is essential for building an integrated KB by several SMEs, to accommodate the differences between their domain models. It will also allow the developed system to solve problems from different perspectives.
The SME and the agent will cooperate in developing the knowledge base of the agent that will represent the expertise of the SME. However, the SME is not a knowledge engineer and cannot be expected to be able to appropriately formalize his or her domain model. On the other hand, the learning agent does not know what is to be formalized and has to get this information from the expert. The most difficult technical challenge of RKF is finding a solution to bridge the informal logic of humans and the formal logic of the machines. Three of the main issues that need to be considered to solve this problem are: 1) the task and control issue; 2) the communication issue; and 3) the interface issue.
The task and control issue deals with the division of responsibility between the expert and the agent for the tasks that need to be performed in order to develop the knowledge base, and with the shift of initiative and control during knowledge base development. Some of these tasks are intrinsically difficult for the SME while others are intrinsically difficult for the learning agent. In the proposed mixed-initiative approach, each party should be responsible for performing the tasks that are easier for that party, while receiving help from the other party. For instance, it is generally very difficult for an SME (who is not a knowledge engineer) to define general problem solving rules that represent his or her problem solving expertise because this is not what the expert is trained to do. An expert is trained to solve problems. Therefore, it should be much easier for the expert to provide specific examples of how to solve problems, or to judge a specific solution to some problem as being correct or incorrect, or even to provide some justification of why a solution is correct or why it is incorrect. This, however, should provide enough information for a capable agent to learn and refine general rules. Similarly, it is generally very difficult for an agent to properly assign credit or blame to individual decisions or problem solving steps that have led to an overall result. This, in turn, is a very easy task for the expert, because it again reduces to the analysis of specific problem solving episodes. However, once the blame or credit has been established, the agent can use it to properly adapt its knowledge fragments. Another very complex task is the definition of new concepts in the ontology of the agent. This task can also have a manageable mixed-initiative solution where the agent identifies the need for an additional piece of knowledge and then guides the expert to either define it, or to import it from another knowledge repository.
In the Disciple’s architecture, the task and control issue is the responsibility of the “Mixed-Initiative Manager” (see Figure 1) that governs the overall functioning of Disciple and its interaction with the expert.
The communication issue consists of defining a protocol to exchange knowledge and information between the expert and the agent, in each direction, in forms that the source can easily create and the recipient can easily understand. We propose a communication strategy that directs the powerful knowledge acquisition capacity of the agent to the very process of having it learn to communicate. In the medium of language, for example, the agent will acquire lexical knowledge related to the ontology that characterizes a domain as well as syntactic-semantic knowledge associated with rules specific to the various applications within the domain.
The design of such an acquisition process hinges on what is arguably the most basic decision about communication: choosing among the possible media of communication and among interaction styles and constraints on the use of the media selected. Although for implementing the agent the use of graphical user interfaces is temptingly straightforward, human experts typically communicate most effectively with each other in human language, technical jargon and diagrams. We will incorporate all of these into the agent-expert communication process.
Human language is the medium that poses the most significant challenges from the viewpoint of constructing an agent. Compounding the difficulty is the fact that the agent must acquire knowledge about both the domain and whatever media of communication are to be used. We will sequence the learning of language and domain in a way that avoids confronting the agent with the difficulties faced by a student studying a new subject abroad. Various strategies are available for reigning in the human language problem, involving constraints on subject matter, dialogue structure, vocabulary and syntax. Judiciously incorporating such constraints has led to various levels of success in what is widely called natural language processing (NLP): the processing of language that is “natural” in the sense that it is like human language. As a discipline, NLP has sought to chip away at the constraints by handling an ever-widening range of human language phenomena. In Figure 2 we characterize the design dilemma for NLP interaction in terms of three factors: viewpoint, naturalness and direction of communication.
The three factors just mentioned show up
in the diagram in two different ways. Viewpoints are the axes. The horizontal
axis reflects the expert’s viewpoint: acceptability to the user depends on ease of
use. The vertical axis reflects the implementer’s viewpoint: the feasibility
requirement. The region in the upper right indicates that there should be high values on
both dimensions for feasible acceptable communication. Next, there is the choice between
relatively natural language - the “N” in NLU and NLG - versus a relatively
constrained sub-natural or formal language, F. Third and last is the distinction
between understanding - the “U” in NLU and FLU - versus generation, G. Whatever
is generated by the agent must be understood by the expert, at points in the diagram
indicated by the two little boxes as well as on the dotted line connecting them, which
reflects varying degrees of naturalness. Conversely, what the expert generates must be
understood by the agent, similarly indicated by two little circles and a connecting line.
Two-way communication requires a point on each of the dotted lines. Though inexact,
the values on the axes express the accepted fact that natural language is easy to use but
hard to implement while, relatively, the opposite is true of more formal language. Our
strategy for moving into the region of feasible acceptable communication is to apply our
hybrid interactive knowledge acquisition system to language knowledge to share the
implementation burden.
In addition to language, we propose diagrams as a method of human-computer interaction, for three reasons. First, diagrams complement language as a favored medium of communication of precise concepts and relationships in specialized domains. Second, we have extensive implementation experience. Finally, we claim that they will yield to an implementation strategy like the one proposed above for language, so that we can capitalize on our successful knowledge acquisition strategies. The role of diagram software is analogous to that of language. To communicate via diagrams, the agent needs both domain knowledge and diagram ability, but here the scaffolding problem is less problematic since diagram are far less complex than human language and can thus contribute to sequencing, since it is difficult to acquire both kinds of knowledge at once. Thus the agent's beginning knowledge will have to be acquired by relatively straightforward modes of interaction. For instance, it is clearly easier for the agent to generate (natural language) sentences than to understand an informal sentence created by the expert. Also, it is clearly easier for the expert to understand an even formal and less “natural” sentence generated by the agent than to create one that takes into account the “knowledge level” of the agent. In the current version of Disciple, when the agent needs some information from the expert, rather than asking the expert to provide it, the agent may formulate the question and possible answers and ask the expert to indicate the correct one. Or, when the agent cannot hypothesize the correct answer, it could ask the expert to only provide a hint and will use this hint to hypothesize possible answers. We also propose to investigate methods by which the agent will gradually learn the language of the expert, including “common sense” language understanding rules. For instance, a learned “common sense” lexical rule should allow the agent to infer that “intelligence-collection2” is very likely denoting an instance of “intelligence-collection-military-task”.
The interface issue is concerned with developing an advanced graphical user interface that will facilitate the interaction between the SME and Disciple-RKF. This should create an environment that is as familiar for the expert as possible. An implementation of Disciple on a specific platform will keep in mind the usual interaction between a typical user and that platform. For instance, for an implementation on PC systems, because the vast majority of users are likely to be familiar with PC software tools, such as Word, PowerPoint, or Internet Browser, we will attempt to incorporate into Disciple-RKF the same interaction conventions and graphic capabilities, wherever this is appropriate.
Experimental results from using Disciple in HPKB showed that this approach facilitates knowledge base development not only for SMEs but also for knowledge engineers. Moreover, the SMEs themselves will have different degrees of expertise with knowledge bases that will allow them to use more or less advanced features of Disciple-RKF. In fact, it is fully expected that as they use Disciple, their experience with it will increase and they will become increasingly willing to use more of its features. Also, as is presented in Figure 1, a knowledge engineer may still be needed for more complex operations, such as integrating, managing and maintaining the knowledge bases developed by different subject matter experts. For these reasons, we will create a wide range of capabilities for the developed modules of Disciple, allowing users to use Disciple in different modes, ranging from the novice SME who will be guided by wizards in performing operations, to knowledge engineers that will have total control over the operation of the module. We also expect that some of the modules (such as the rule browser or the rule editor) will never be used by a novice SME, but may be very useful to a knowledge engineer.
Among the four main technical areas that must be developed for RKF, Knowledge Formation is the one we consider to be central to our approach, and the one exhibiting the most innovative aspects.
A central
component of Disciple-RKF will be a mixed-initiative reasoner that will allow the expert
and the agent to find solutions to the attempted problems that range from routine
solutions, to innovative solutions, inventive solutions, and even creative solutions. In
this process the agent will learn from the contributions of the expert, gradually
developing its knowledge base. The ultimate goal is to develop a knowledge base that will
allow the agent to exhibit the same problem solving competence as the SME. We call the set
of all correct solutions generated with this "final" knowledge base the Target
solution space (see Figure 3). However, the current knowledge base of the agent is
incomplete and may be partially incorrect. Therefore, part of the target solution space is
not even included in the current representation space of the agent. Therefore, during
knowledge acquisition and learning, it will be necessary to extend the representation
language of the agent.
We propose to develop plausible reasoning methods that will allow the agent to distinguish between several types of problem solving situations:
· Situations where the agent is able to generate routine solutions. They are very likely to be correct.
· Situations where the agent can only attempt innovative solutions through the use of stronger forms of plausible reasoning. These solutions may or may not be correct and have to be checked by the SME who can accept or reject them. The agent will refine the rules of its KB from such situations.
· Situations where the agent can only attempt inventive solutions through the use of weaker forms of plausible reasoning. These solutions are less likely to be correct, but they may be close enough to correct solutions that the expert may find it easier to correct them than to define these solutions from scratch. From such situations the agent will learn new rules and will extend the ontology.
· Situations that require creative solutions that cannot even be expressed in the current agent’s representation language. These solutions must be provided by the SME, and will lead to an extension of the agent’s ontology with new objects, features or tasks. However, even in such a case the agent can assist the expert in defining the solutions. These are the primary situations from which the agent will learn new rules and concepts.
The agent’s ability to recognize the current problem solving situation can guide the interactions with the SME, leading to a cooperative problem solving process where the agent solves the more routine parts of the problem and the expert solves the more creative ones. In the process, the agent will learn from the expert. As a result, the problem solving situations that were innovative for the agent gradually become routine, and those that were creative gradually become inventive, then innovative and ultimately routine.
A very important feature of this very flexible mixed-initiative reasoner is that it fulfils multiple roles, supporting domain modeling, problem solving and learning, depending of the agent’s knowledge. Initially, when the agent does not have much knowledge, the emphasis is on domain modeling where most of the problems require “creative” solutions from which the agent will learn new rules. As the agent learns from the expert, it is increasingly able to propose routine and innovative solutions, and to help in defining inventive and creative solutions. During this process the existing rules will be refined and new rules will be learned. However, the emphasis now shifts from domain modeling to problem solving and rule refinement. Nevertheless, domain modeling may still be used when inventive and creative solutions are needed.
In the initial phase of KB development it will be the SME that will lead the problem solving process, following a methodology similar to the one developed for Disciple-COA, and illustrated in Figure 4.
Figure 4 illustrates how the SME might attempt to assess whether organization A can deploy a botulism toxin. This involves a top down analysis process (illustrated by the tree from the left hand side of Figure 4) followed by a bottom-up synthesis process (illustrated by the tree from the right hand side of Figure 4). During the top down process the expert is successively reducing the top-level assessment task to simpler and simpler assessment tasks, and ultimately to specific assessments, based on the available information. During the bottom-up process, specific assessments are aggregated to produce higher-level assessments, and ultimately to provide the top-level assessment.
Let us follow the decompositions from the tree in the left hand side of Figure 4. To "Assess whether organization A can deploy a botulism toxin" the SME (the analyst) may ask himself or herself: What people, places and things are necessary and available to A? This will lead the analyst to consider the presence of the various necessary aspects and to decompose the initial assessment task into five assessment subtasks, one of which being to "Assess whether organization A has access to botulism toxin experts." To perform this assessment, the analyst may ask what conditions are necessary for someone to act as an expert for organization A. Answering this question will lead to decomposing the current assessment task into three simpler ones, one of which being to "Assess organization A's physical connection with expert E". The question then to be asked is whether there is any evidence of physical connection between A and E. Because expert E has relocated to Country1, where organization A has a power base, one can "Conclude that organization A has physical access to expert E." Also, because it has been found out that expert E has often met F, who is an important member of organization A, one can "Conclude that organization A is in contact with expert E." Based on these two conclusions, the analyst will "Conclude that organization A may have a connection with expert E", as indicated in the bottom part of the tree from the right hand side of Figure 4. Similarly, from this and the other conclusions shown in Figure 4, the analyst will "Conclude that organization A may quickly obtain access to the expert E which may offer access to expertise in botulism toxin." This synthesis process continues until a final determination is made on whether organization A can deploy botulism toxin. Each such elementary problem solving step is an example from which the Disciple-RKF agent will learn a general problem solving rule. Let us consider, for instance, the following problem solving step:
IF the task to accomplish is
Assess organization A's physical connection with expert E
Question: Is there evidence of a physical connection?
Answer: Yes, expert E has relocated to Country1 where organization A has a power base
THEN Conclude that organization A has physical access to expert E
From this problem solving step the Disciple-RKF agent will learn the rule shown in the bottom part of Figure 4. This is a plausible version space IF-THEN rule that has two conditions, a plausible upper bound condition which, as an approximation, is more general than the hypothetical exact (but not yet known) condition of the rule, and a plausible lower bound condition which, as an approximation, is less general than the hypothetical exact condition. The general form of the plausible version space rule, as well as the relationships between its conditions, are shown in the bottom right hand side of Figure 4.
An important aspect of the plausible version space rules is that they are at the basis of the language to logic translation process. Indeed, the rule contains both the generalization of the natural language expressions used by the SME (i.e. the IF and THEN tasks, the question, and the answer), and the formal logical expressions that represent the applicability conditions of the rule (the plausible upper bound and the plausible lower bound). The justification is an intermediate expression that helps in the translation process. The collections of Disciple-RKF rules like the one in Figure 4 will represent generic analysis models. Similarly, Disciple-RKF will learn synthesis rules. It should be stressed, however, that the SMEs will not work directly with these rules, but only with their instances.
During rule refinement, the two conditions of the plausible version space rule will converge toward one another and toward the hypothetical exact condition. This process may involve adding new conditions to the rule, such as, "except-when" conditions (that should not hold in order for the rule to be applicable), "except-for" conditions (that specify negative exceptions of the rule), and "for" conditions (that specify positive exceptions).
The ontology of objects, features and tasks serves as the generalization hierarchy for Disciple. An example is basically generalized to a rule by replacing its objects with more general objects from the ontology. An important aspect of Disciple is that the ontology is itself evolving during knowledge acquisition and learning. This distinguishes Disciple from most of the other learning agents that make the less realistic assumption that the representation language for learning is completely defined before any learning could take place.
The illustration from Figure 4 corresponds to a situation where an agent’s knowledge is more limited and most of the problem solving steps are creative for the agent. However, from each such “creative” step the agent learns a plausible version space rule. This rule will allow the agent to propose routine, innovative or even inventive solutions to problems similar to the one reduced by the rule.
A routine problem solving situation could be considered one where the task to be performed is an instance of T1g (see the general form of the rule in the bottom right side of Figure 4) and the plausible lower bound condition of the rule is satisfied. In this case, there is significant confidence that the solution proposed by the rule is correct. However, if the solution is not correct, then it represents an exception to the rule and can guide the Ontology Discovery tool to extend the ontology, as indicated in section 2.2.8.
An innovative problem solving situation might be considered one where again the task to be performed is an instance of T1g, the plausible lower bound condition of the rule is not satisfied, but the plausible upper bound condition is satisfied. The expert would need to judge this solution as correct or incorrect and this will guide the refinement of the rule by the rule refinement module (see section 2.2.2 and the following discussion from this section on rule learning and refinement).
An inventive problem-solving situation would be one where no plausible version space rule is directly applicable. Nevertheless, the agent may use various forms of analogical or plausible reasoning to propose solutions that would most likely need to be corrected by the expert. The space of inventive solutions could be quite large, and many methods could be investigated. For instance, an inventive problem-solving situation would be one where the task to be solved is not an instance of T1g, but has some similarities to some instance of T1g. How inventive this might be considered depends upon which of the conditions of the rules corresponding to T1g are partially satisfied, and how much of the condition is satisfied. We expect that an inventive solution will be defined based on an analysis of several rules and will actually consist of elements of several of them. An inventive problem-solving situation may lead to an extension of the knowledge base within the current representation language. For instance, the description of an object may be extended with new features that are already part of the agent’s ontology.
As the agent learns more rules, the main
expert-agent activity shifts from domain modeling and knowledge acquisition to problem
solving and rule refinement. Let us consider, for instance, that the agent has to assist
the analyst in assessing whether a certain country B has a BW capability. The analyst and
the agent will attempt to build a plausible justification tree like the one in Figure 5.
The top of this tree is the assessment task, and the leaves represent elementary
assessments based on the available observations. The intermediate steps are the most
plausible connections that link the assessments and the observations to the top-level
assessment. Some of the intermediate reductions from this tree may correspond to routine
problem solving episodes, while others may correspond to innovative, inventive or even
creative problem solving episodes. This tree is built jointly by the agent and the
analyst, with the agent contributing more with the routine and the innovative solutions,
and the expert contributing more with the inventive and creative ones. As has been stated
before, the agent will learn from the problem solving steps in the Plausible Justification
Tree.
The other essential feature of Disciple-RKF is a very powerful and flexible rule learning and refinement capability. The objective of rule learning is to create a justified generalization of an example of a problem-solving episode. The objective of rule refinement is to improve a learned rule through the use of additional positive and negative examples of the rule. Both methods are based on apprenticeship and multistrategy learning, incorporating in a synergistic way learning from explanation, empirical learning from examples, analogical learning and abductive learning. Central to both methods is an ability to find an explanation of why an example of a problem solving step is correct or incorrect. The current methods are developed for situations where the agent’s knowledge is very limited. We propose to develop these methods also for situations where an agent’s knowledge is more complete and correct and could be used to boost learning.
One specific issue to be investigated is the formalization of the notion of a hint as an abstraction of an explanation along the relevance dimension. We will also investigate the use of analogical and abductive reasoning in explanation generation. Critical to these processes is the agent's ability to recognize similarities. We therefore propose to investigate a formal definition of similarity based on generalization. This will take advantage of the fact that the knowledge representation of the agent is specially designed to facilitate generalization and specialization operations. In this context, the similarity of two expressions will be judged by analyzing their most specific generalizations and the generalization operations that are applied to each to obtain these generalizations. A generalization of two expressions represents their common characteristics, while the generalization operations applied to each in order to obtain the common generalization identify the differences between the two expressions. This approach to similarity is based on the observation that two very similar expressions generalize to an expression that is very close to each of them, while two very different expressions generalize to a very general expression.
An important aspect of Disciple is that the agent hides the complexity of the rule from the expert who only needs to deal with very concrete cases. On the other hand, the expert supports the agent significantly in rule refinement by helping it to understand why the examples are correct or incorrect. As compared to a rule that was manually defined by the knowledge engineer, the refined rule has the advantage that it has already been verified by a certain number of examples. A potential disadvantage is that rule refinement may require a large number of examples to be analyzed by the expert. We propose to develop an approach that will reduce the number of necessary examples to only a few and will also lead to a verified rule of good quality. The general idea is to analyze the rule to be refined, in conjunction with the structure of the agent's ontology and the other rules from the knowledge base, in order to identify the most informative set of instances to be used in refining this rule. This method will formalize various intuitions that will be formally evaluated. Based on the obtained results we will develop and experimentally validate a measure of support given to the rule by its verified instances, a measure that will estimate the degree of verification of each rule and of the entire rule base. We believe that such a measure could also be used in verifying knowledge bases independent of how they have been developed (manually or through learning). Also, such a measure could be used in problem solving to estimate the plausibility of the instances of various applicable rules, and to generate the most plausible solutions.
Based on our experience with the development of the rule learning and refinement methods, we believe that we can also develop and implement methods that will make it as easy to learn the ontological knowledge pieces from specific examples, as it is to learn rules from examples. These methods will allow the subject matter expert to communicate with Disciple by using concepts and features that are not defined in Disciple’s ontology. Disciple will attempt to learn the general definitions of these concepts and features by taking into account the context in which the new concepts and features are defined, performing analogies with known objects and features, and conducting a clarification dialog with the user.
Disciple-RKF is specially designed to facilitate the collaboration between several SMEs. Central to this design is a hierarchical structure of the Integrated KB into several component KBs, as illustrated in the bottom right of Figure 1. This structure allows both for joint development of shared knowledge, and for personalization of knowledge that accounts for differences in the knowledge models of different experts. Through such a hierarchical structure, each expert is connected to the entire group of Disciple KBs. When a new expert joins the KB development team, he or she will not start from scratch but from an existing structured KB. Therefore, the first thing that needs to be done is to create his or her view of the IKB. This activity will be supported by the mediating team through the use of specially developed theory slicing methods. The purpose of these methods are to assist the new SME in becoming familiar with the content of the IKB and to identify the part of that knowledge base that is consistent with his or her representations and beliefs. The new SME will be allowed to redefine some of the KB components, gradually building a personalized KB that will be linked to the shared KB.
As the SME develops his or her part of the IKB, the team leaders will attempt to incorporate as much of it as possible into the shared part of the IKB (while still preserving in that expert’s part the knowledge that reflects his or her personal views that are not shared by the other experts). This activity will be based on a negotiation with the other subject matter experts and will be assisted by a Collaborative KB Merging tool.
Our view of communication between experts in constructing the IKB allows for a natural management of alternative belief structures. The common knowledge and beliefs will be kept in the upper KBs, and the personal beliefs of each expert will be kept in their personal KBs. We will also develop a dynamic knowledge base filtering capability that will allow our mixed-initiative reasoner to view and use only those parts of the KB that satisfy certain criteria in order to answer questions from various points of view. For instance, our system will be able to answer questions from the point of view of a given expert (based on his or her personal KB). But we can also answer questions by setting other filtering criteria, such as the actuality/recentness of the information or its certainty.
The IKB that we will develop will complement and extend the CYC-based IKB that was developed during HPKB and will be further extended during RKF. Therefore, central to our proposed approach is a facility to communicate and exchange information with that KB through the MELD language. As part of the HPKB program we have developed an import procedure that was used to represent a portion of the CYC-COA KB into Disciple. Based on this experience, we propose to develop advanced methods for import and export as described below.
The objective of ontology import is to transfer useful ontological knowledge from an external repository of information into the agent’s ontology. The general hypothesis is that it should be easier for the domain expert to reuse previously defined ontological knowledge than to define it from scratch. The difficulty, however, is that in general this would require the SME to use unfamiliar tools to browse a large and unfamiliar ontology in search of relevant knowledge. While this might be a reasonable task for a knowledge engineer, it is not a task that an SME should be expected to be able to perform. We therefore propose to investigate a mixed-initiative approach to ontology import that will render this task manageable for the expert and the agent.
We reduce the problem of importing knowledge from an outside knowledge server into two simpler problems: an ontology translation problem and a selective import problem. First, the agent automatically extracts ontological knowledge from an external knowledge server and translates it into an ontology in the agent's representation formalism. This copy of the external ontology can then be automatically searched by the agent to selectively import from it useful ontological knowledge.
Let us notice that we need not to be concerned here with the general problem of automatic translation between different knowledge representation systems. Indeed, we only attempt to import ontological knowledge, which generally has a much simpler syntax and semantics. We are not concerned with the translation of the axioms or the rules (which would be a much more difficult process) because we consider them to be less reusable across different applications, and because Disciple is specifically designed to easily learn such axioms or rules from the SME. We should also notice that this translation takes place only at a syntactic level, the translated ontology containing the same names as in the original knowledge base. Nevertheless, it results in a knowledge base that can be automatically searched by the Disciple agent and could be browsed by the expert by using familiar ontology tools. This is the kind of knowledge base from which the expert and the agent can now selectively import useful ontological knowledge. In the approach that we propose to investigate, either the expert or the agent can create a specification of some needed ontological knowledge. Then the agent can search the external ontology to identify a reduced set of candidate concepts from which the expert has to select the relevant ones. The search will involve natural language based flexible matching strategies.
In the Disciple approach, the creation and refinement processes are integrated, and take place continually from the first moment the expert begins to use the system. The rule and ontology learning and refinement methods are based on specific methods to detect and resolve the internal conflicts that are expected to appear, and also on generating case studies.
An important contribution to ease of testing and correcting the KB directly by the SME is provided by the its two problem solvers, the autonomous one, and the step-by-step one, which allows the SME to easily detect and correct possible errors or ambiguities. We will develop also an automated KB revision method based on plausible justification trees, which will test the KB with problems and solutions from a case repository.
With the development of the CYC-based Integrated Knowledge Base for COA critiquing, during the HPKB project, the Teknowledge-CyCorp team and the GMU team laid the basis for a powerful and flexible mode of integration between CYC and Disciple. While most of the IKB was developed by the Teknowledge-CyCorp team, the GMU team contributed to the ontology of military tasks. This CYC-based IKB was then imported into Disciple, and was used to rapidly learn high performance problem solving rules from a subject matter expert. This was a very significant HPKB result for both CYC and Disciple. On the one hand, it has demonstrated the generality of the CYC ontology that proved to be very useful to a system with a different knowledge representation. On the other hand, it has demonstrated the generality of Disciple’s learning methods, the SME being able to teach Disciple based on an ontology that was not specially designed for Disciple.
It is proposed that this very promising flexible integration between CYC and Disciple be extended as part of the RKF program by taking full advantage of the complementariness of CYC and Disciple. CYC is a powerful knowledge server with a very general knowledge representation language that can encapsulate, in a uniform and consistent way, large bodies of knowledge about any aspect of the real world. Disciple is powerful system for acquiring knowledge directly from SMEs and for building personal assistants. It relies on a learning-oriented knowledge representation and on general apprenticeship multistrategy learning and reasoning methods. When an SME needs to develop a knowledge-based agent, he or she can start by importing knowledge from CYC that will represent the initial knowledge base for the agent. The expert teaches Disciple problem solving logic which allows Disciple to extend its ontology and learn problem solving rules. The resulting knowledge base can then be exported back into CYC as a specific microtheory, this integration being facilitated by the fact that the core of the microtheory was imported from CYC to begin with. Viewed from this perspective, the CYC KB and the Disciple KB that would be developed as part of the RKF program would represent an integrated KB.
The communication between CYC (as well as the CYC-based KRAKEN system) and Disciple will be based on the MELD language and on the Disciple Import/Export tools that we propose to develop. These tools will import knowledge from the CYC-based IKB into the Disciple KB, and will export the Disciple KB into a CYC microtheory. For the problem input and solution output we will use both the MELD language and a customized expert-input and Disciple-generated output.
In conclusion, for CYC (and the CYC-based KRAKEN system), this flexible integration with Disciple will demonstrate that CYC’s knowledge repository is useful for other systems as well, and that it can easily incorporate knowledge acquired by other systems. For Disciple, it will demonstrate the generality of its learning and problem solving methods that can use an imported ontology, and the fact that the knowledge acquired with Disciple is useful for other systems as well. CYC will facilitate the development of knowledge-based agents with Disciple by providing an initial knowledge base, and Disciple will help extend the CYC knowledge base, increasing its value as a knowledge repository.
We claim that the proposed approach will enable a collaborative team of subject matter experts (as well as an individual expert) that do not have prior knowledge engineering experience to rapidly construct, update and extend a large and high quality knowledge base for a practical application.
We also claim that the proposed approach will significantly speed up the process of building a large and high quality knowledge base independent of the level of knowledge engineering experience of the domain expert, even for cases where the domain expert is also a knowledge engineer, or for cases where the domain expert receives significant support from a knowledge engineer. This is significant from two points of view. First, it shows the generality of our approach. Second, it shows that the more knowledgeable the expert becomes in using Disciple’s capabilities, the more efficient the knowledge base development process becomes.
In addition to these general claims we will formulate and test more specific claims, corresponding to each of the developed methods and tools. For instance, we claim that the rule learning method enables rapid acquisition of relevant problem solving knowledge from a subject matter expert. We claim that the rule refinement method will result in validated problem solving rules that will assure a high degree of correctness of the solutions generated by the agent. We claim that the ontology discovery method enables easy extension of the ontology with problem specific objects and features necessary for competent problem solving. We claim that the ontology import method will facilitate the reuse of ontological knowledge from external knowledge servers. We also claim that the knowledge acquired directly from the expert assures high performance of the problem solver (in terms of time needed to solve the problems).
For all the formulated claims we will design and conduct experiments to evaluate them. We will also participate in the evaluations administered by the evaluation management contractor. There will be different kinds of experiments. Some will be global experiments where an SME will develop an entire knowledge base, or a collaborative team of SMEs will develop an integrated knowledge base. These experiments will test the first two claims from the beginning of this section. In addition, we will conduct knowledge ablation experiments where various parts of a developed knowledge base are removed or changed, and the task will be to reconstruct or correct the knowledge base.
We will also design and conduct experiments intended to test a specific method, or a specific aspect of the knowledge base development methodology. In particular, we will conduct tool ablation experiments where a tool that has different capabilities will be used in different conditions, with some of the capabilities inhibited. These experiments will demonstrate the effectiveness of various capabilities.
To facilitate these evaluations, we will instrument the integrated Disciple-RKF system and each of its components. Each user of a Disciple-RKF agent will have to register before using it. Consequently, all the KB changes and measurements will be stamped accordingly (including user id, user role – KE, SME or end-user, user organization, time/date). Each Disciple-RKF component will also be instrumented to collect data on its operation, including the interactions with the user. We will develop a special analysis module that will automatically collect this data and will produce aggregated results, such as profiles on how the experts use their time during knowledge entry, what tool features they use and for how long, how many operations of a given type (such as KB repairs) occurs during a certain experiment, etc. The knowledge import module will automatically stamp the imported knowledge pieces with their source so that data on knowledge reuse can be automatically generated.
We think that the design and performance of such experiments will themselves be an important contribution of this research, leading to the development of a general approach to the evaluation of mixed-initiative knowledge base development methodologies.
Aamodt, A. (1995). Knowledge Acquisition and Learning by Experience - The Role of Case-Specific Knowledge. In Tecuci, G. and Kodratoff, Y. (editors), Machine Learning and Knowledge Acquisition: Integrated Approaches. Academic Press.
Buchanan, B. G. and Wilkins, D. C. (editors), (1993). Readings in Knowledge Acquisition and Learning: Automating the Construction and Improvement of Expert Systems, Morgan Kaufmann, San Mateo, CA.
Chaudhri, V. K., Farquhar, A., Fikes, R., Park, P. D., and Rice, J. P. (1998). OKBC: A Programmatic Foundation for Knowledge Base Interoperability. In Proc. AAAI-98, pp. 600 – 607, Menlo Park, CA: AAAI Press.Cypher, A. (editor), (1993). Watch what I do: programming by demonstration. MIT Press. Cambridge. MA.
Cohen P., Schrag R., Jones E., Pease A., Lin A., Starr B., Gunning D., and Burke M. (1998). The DARPA High-Per-formance Knowledge Bases Project, AI Magazine, 19(4), 25-49.
Cypher, A. (editor), (1993). Watch what I do: programming by demonstration. MIT Press. Cambridge. MA.
Farquhar, A., Fikes, R. and Rice, J. (1996). The Ontolingua Server: a Tool for Collaborative Ontology Construction. In Proceedings of the Tenth Knowledge Acquisition for Knowledge-Based Systems Workshop; Banff, Canada.
Fellbaum, C. ed. (1998). WordNet: An Electronic Lexical Database , MIT Press.
Fikes, R. and Farquhar, A. (1999). Large-Scale Repositories of Highly Expressive Reusable Knowledge. In IEEE Intelligent Systems, Vol. 14, No. 2.
Fridman Noy, N. and Musen, M. (1999). An Algorithm for Merging and Aligning Ontologies: Automation and Tool Support. In AAAI-99 Workshop on Ontology Management.
Gaines, B. R. and Shaw, M. L. G. (1992). Knowledge Acquisition Tools Based on Personal Construct Psychology, Knowledge Engineering Review special issue on automated knowledge acquisition tools.
Ginsberg, A. (1988). Automatic Refinement of Expert System Knowledge Bases, Pitman.
Hamburger, H. (1995). Structuring two-medium dialog for language learning. In Holland, M., Kaplan, J. and Sams, M. (Eds.) Intelligent Language Tutors: Balancing Theory and Technology. Hillsdale, NJ: L. Erlbaum Associates.
Hamburger H. and Tecuci G. (1998). Toward a Unification of Human-Computer Learning and Tutoring, Proceedings of the International Conference on Intelligent Tutoring Systems, ITS’98, San Antonio, Texas, Springer Verlag.
Koppel, M., Segre, A. and Feldman, R. (1995). An Integrated Framework for Knowledge Representation and Theory Revision, In Tecuci, G. and Kodratoff, Y. (editors), Machine Learning and Knowledge Acquisition: Integrated Approaches, Academic Press.
Lenat, D. (1995). CYC: A Large-scale investment in knowledge infrastructure, Communications of the ACM, Nov. Vol. 38, No. 11, pp. 33-38.
Mahadevan, S., Mitchell, T., Mostow, J., Steinberg, L., and Tadepalli, P. (1993). An Apprentice Based Approach to Knowledge Acquisition, Artificial Intelligence, 64(1): 1-52.
Michalski, R. S. and Tecuci, G. (editors), (1994). Machine Learning: A Multistrategy Approach Volume 4, Morgan Kaufmann Publishers, San Mateo, CA.
Mitchell T.M., Mahadevan S. and Steinberg L.I. (1990). LEAP: A Learning Apprentice System for VLSI Design, in Machine Learning: An Artificial Intelligence Approach, Vol. 3, Y. Kodratoff and R.S. Michalski (Eds.), San Mateo, CA, Morgan Kaufmann.
Mitchell, T. M., Caruana, R., Freitag, D., McDermott, J. and Zabowski, D. (1994). Experience with a Learning Personal Assistant, Communications of the ACM, Vol. 37, pp. 81-91.
Mitra, P., Wiederhold, G. and Jannink J. (1999). Semi-automatic Integration of Knowledge Sources. In Proceedings of Fusion '99, Sunnyvale CA.
Porter, B. W., Bareiss, R. and Holte, R. C. (1990). Concept Learning and Heuristic Classification in Weak-Theory Domains. In Shavlik, J. W. and Dietterich, T. G. (editors). Readings in Machine Learning, pp. 710-746. Morgan Kaufmann. San Mateo, CA.
Porter, B. and Clark, P. (1998). Building Concept representations from Reusable Components. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97) and Ninth Conference on Innovative Applications of Artificial Intelligence Conference (IAAI-97), Providence, Rhode Island.
Reeder, F., Hamburger, H. and Schoelles, M. (1999). Real Talk: Authentic Dialogue Practice. In Debski, R. and Levy, M. (Eds.) WORLDCALL: Global Perspectives on Computer-Assisted Language Learning. Swets & Zeitlinger, b.v., Lisse, Netherlands.
Schoelles, M. and Hamburger, H. (1996). Tools for cognition-based language pedagogy. Computer-Assisted Language Learning.
Sycara, K. and Miyashita, K. (1995). Learning Control Knowledge through Case-Based Acquisition of User Optimization Preferences in Ill-Structured Domains. In Tecuci, G. and Kodratoff, Y. (editors), Machine Learning and Knowledge Acquisition: Integrated Approaches. Academic Press.
Tallis, M. and Gil, Y. (1999). Designing Scripts to Users in Modifying Knowledge-based Systems. In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99) and Eleventh Conference on Innovative Applications of Artificial Intelligence Conference (IAAI-99), Orlando, Florida.
Tecuci G. (1988), DISCIPLE: A Theory, Methodology and System for Learning Expert Knowledge, 197 pages, Thèse de Docteur en Science, University of Paris-South, (in English).
Tecuci, G. (1993). Plausible Justification Trees: a Framework for the Deep and Dynamic Integration of Learning Strategies, Machine Learning Journal special issue on Multistrategy Learning, vol.11, pp. 237-261.
Tecuci, G., Kedar, S. and Kodratoff, Y. (editors), (1993). Proceedings of the IJCAI-93 Workshop on Machine Learning and Knowledge Acquisition: Common Issues, Contrasting Methods, and Integrated Approaches, Chambery, France.
Tecuci G. (1994). "An Inference-Based Framework for Multistrategy Learning," in Michalski R.S. and Tecuci G. (eds), Machine Learning: A Multistrategy Approach, vol. IV, pp. 107-138, Morgan Kaufmann, 1994.
Tecuci, G. and Kodratoff, Y. (editors), (1995). Machine Learning and Knowledge Acquisition: Integrated Approaches, Academic Press.
Tecuci G. and Hieb M.H. (1996). "Teaching Intelligent Agents: The Disciple Approach," International Journal of Human-Computer Interaction, vol.8, no.3, pp.259-285.
Tecuci G. (1998). BUILDING INTELLIGENT AGENTS: An Apprenticeship Multistrategy Learning Theory, Methodology, Tool and Case Studies, Academic Press, 320 pages.
Tecuci G. and Keeling H. (1998). Developing Intelligent Educational Agents with the Disciple Learning Agent Shell, in Proceedings of the International Conference on Intelligent Tutoring Systems, ITS’98, San Antonio, Texas, Springer Verlag, (best paper award).
Tecuci G. and Keeling H. (1999). Developing an Intelligent Educational Agent with Disciple, International Journal of Artificial Intelligence in Education, vol. 10, no.3-4.
Tecuci G., Boicu M., Wright K., Lee S.W., Marcu D., and Bowman M. (1999). "An Integrated Shell and Methodology for Rapid Development of Knowledge-Based Agents," in Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99), July 18-22, Orlando, Florida, AAAI Press, Menlo Park, CA.
Tufis, D., Hamburger, H. and Hashim, R. (1994). Generated natural language in an immersive language learning system. In Brouwer-Janse, M.D. and van Kuijck-Aerts, 1. (Eds.) Human-Machine Communication for Educational Systems Design. Berlin: Springer-Verlag.
UMLS (1998). Unified Medical Language System, UMLS Knowledge Sources 9th Edition, National Library of Medicine. (http://www.nlm.nih.gov/research/umls/)
Wilkins D.C. (1990). Knowledge Base Refinement as Improving an Incorrect and Incomplete Domain Theory, in Y. Kodratoff and R. S. Michalski (eds), Machine Learning: An Artificial Intelligence Approach, vol. 3, Morgan Kaufmann.