Preface
General Description
This book presents a theory, methodology and tool for building intelligent agents, along with detailed case studies. The most significant, and unique, characteristic of building these agents is that a person directly teaches them how to perform domain-specific tasks in much the same way he or she would teach a student or apprentice: by giving the agent examples and explanations, and by supervising and correcting its behavior. This approach, in which the agent learns its behavior from its teacher, integrates many machine learning and knowledge acquisition techniques, taking advantage of their complementary strengths to compensate for each other weaknesses. As a consequence, it significantly reduces the involvement of a knowledge engineer in the process of building an intelligent agent. The book is unique in the comprehensive coverage of its subject. The first part of the book presents an original theory for building intelligent agents and a methodology and tool that implement the theory. The second part of the book presents complex and detail case studies of building different types of agents: an educational assessment agent that enhances the capability, generality and usefulness of an educational system for teaching higher-order thinking skills in the context of history; a statistical analysis assessment and support agent to support a university-level introductory science course; an engineering design assistant that cooperates with its user in configuring computer systems; and a virtual military commander integrated into a distributed interactice simulation environment.
Contents
Preface.
Intelligent Agents.
General Presentation of the Disciple Approach for Building Intelligent Agents.
Knowledge Representation and Reasoning.
Knowledge Acquisition and Learning.
The Disciple Shell and Methodology.
Case Study: Assessment Agent for Higher-Order Thinking Skills in History.
Case Study: The Statistical Analysis Assessment and Support Agent. Case Study: Design
Assistant for Configuring Computer Systems.
Case Study: Virtual Agent for Distributed Interactive Simulations.
Selected Bibliography of Machine Learning, Knowledge Acquisition, and Intelligent Agents
Research. Notation. Subject Index.
Preface
This book presents a theory, methodology, tool and case studies of building intelligent agents. The defining feature of this approach to building agents is that a person teaches the agent how to perform domain-specific tasks. This teaching of the agent is done in much the same way as teaching a student or apprentice, by giving the agent examples and explanations, as well as supervising and correcting its behavior. This approach, called Disciple, in which the agent learns its behavior from its teacher, integrates many machine learning and knowledge acquisition techniques, taking advantage of their complementary strengths to compensate for each other weaknesses. As a consequence, the Disciple approach significantly reduces (or even eliminates) the involvement of the knowledge engineer in the process of building an intelligent agent. The agent can be directly taught and trained by a user to assist him/her or other users in various ways, for instance, by helping the user to perform his/her tasks, by performing tasks on the user's behalf, by monitoring events or procedures for the user, by advising other users on how to perform a task, by training or teaching other users, or by helping different users collaborate. This work is part of a long term vision where personal computer users will no longer be simply consumers of ready-made software, as they are today, but also developers of their own software assistants.
Most of the current approaches to building intelligent knowledge-based agents can be divided into two broad categories: knowledge acquisition approaches and machine learning approaches. In the knowledge acquisition approaches, the agent is actually built by a knowledge engineer who manually encodes the expertise acquired from the domain expert into the agent's knowledge base. This indirect transfer of knowledge, from the domain expert through the knowledge engineer to the agent, leads to a long, painful and inefficient agent development process. In the machine learning approaches, the agent employs automated learning methods to learn all of its knowledge from data or experience. However, the difficulty of this task, and the capabilities of the current autonomous learning methods, limit the application of this approach to building simple prototype agents. As knowledge acquisition attempts to automate more of the agent development process and machine learning attempts to automatically develop more complex agents, there is an increasing realization within these two research communities that a better approach to building intelligent agents is through an integration of different knowledge acquisition and learning methods. In Chapter 1 we briefly review and contrast the main knowledge acquisition, machine learning and integrated approaches to building intelligent agents.
In Chapter 2 we present, at an intuitive level, the Disciple approach for building intelligent agents, illustrating it with two examples: building a manufacturing assistant and building an educational assessment agent. In the Disciple approach, a person (who is an expert in some domain, but may not have prior experience with computers or knowledge bases), receiving limited assistance from a knowledge engineer, can teach the agent in a way that resembles the way the expert would teach a student or his/her assistant. For instance, the expert may teach the agent how to solve a certain type of problem by providing a concrete example, helping the agent to understand the solution, supervising the agent as it attempts to solve analogous problems, and correcting its mistakes. Through only a few such natural interactions, the agent will be guided into learning complex problem solving rules, and in extending and correcting its knowledge base. This process is based on a cooperation between the agent and the human expert in which the agent helps the expert to express his/her knowledge using the agent's representation language, and the expert guides the learning actions of the agent. The central idea is the use of synergism at several levels. At an upper level is the synergism between teaching (of the agent by the expert) and learning (from the expert by the agent). For instance, the expert may select representative examples to teach the agent, may provide explanations, and may answer an agent's questions. The agent, on the other hand, will learn general rules that are difficult to be defined by the expert, and will consistently integrate them into the knowledge base. At a lower level is the synergism among different learning methods employed by the agent. By integrating complementary learning methods (such as inductive learning from examples, explanation-based learning, learning by analogy, learning by experimentation) in a dynamic, task-dependent way, the agent is able to learn from the human expert in situations in which no single strategy learning method would be sufficient.
The next two chapters of the book present in detail the concept-based knowledge representation of the Disciple approach, as well as the problem solving, knowledge acquisition and learning methods. They assume no prior knowledge from the reader. Chapter 3 covers knowledge representation, through semantic networks and rules, and the main inference methods used with these representations. Chapter 4 presents the methods of systematic elicitation of knowledge for developing an initial knowledge base, the rule learning method based on explanations and analogy, and the rule refinement method based on analogy, experimentation, and explanation-based and example-based induction. It also presents the exception-based refinement of the knowledge base that employs knowledge discovery and elicitation. These two chapters cover many of the topics introduced in artificial intelligence, machine learning, and knowledge acquisition courses, in a unified way.
Chapter 5 presents the methodology for building intelligent agents by using the Disciple Learning Agent Shell that implements the methods from the previous chapters. It shows in detail how a user interacts with the Disciple Learning Agent Shell to teach and train it to become a domain-specific agent. This chapter also makes the transition to the remaining chapters of the book. Each of the last four chapters presents a case study of using the Disciple methodology and shell to develop intelligent agents for complex domains. While all four case studies illustrate the same methodology, they are different in many ways, not only because the domains are different, but more importantly because the issues that we have stressed in developing these agents are different, yet complementary. Therefore, each case study will bring much more to the reader than yet another application of the same approach.
Chapter 6 presents in detail an application of the Disciple methodology to the building, training and using of two agents that generate history tests to assist in the assessment of students' understanding and use of higher-order thinking skills. These two agents are representative of the class of agents built by an expert (in education and history, in this case) to assist other users (history teachers and students). One of the assessment agents is integrated with the MMTS (Multimedia and Thinking Skills) educational system, creating a system with expanded capabilities, called Intelligent MMTS (IMMTS). The other agent is a stand-alone agent that can be used independently of the MMTS software. The IMMTS system has been field-tested in American history classes in several middle schools on American installations in Germany and Italy. This case study covers all the phases of the agent development process: analyzing the problem domain and defining agent requirements, defining the top level ontology of the knowledge base, developing domain dependent modules, building the initial knowledge base, teaching the agent how to generate tests, developing the assessment engine and the graphical-user interface, and finally, verifying, validating and maintaining the agent. The presentations of the other three case studies will only contain an overview of the applied methodology, stressing more those aspects that make them different from this case study.
Chapter 7 presents the case study of developing a Statistical Analysis Assessment and Support Agent. This agent is integrated in a university-level introductory science course and is accessed on the Internet through a web browser. The course, The Natural World, introduces students to the world of science using collaborative assignments and problem-centered group projects that look at scientific issues which underlie public policy making and stimulate the development of students' analytic skills. This web-based course focuses on three issues, diseases, evolutionary history, and nutrition, and is taught at George Mason University as part of an innovative curriculum designed for the New Century College, GMU's newest college. It responds to a growing belief that the goal of education should no longer be dominated by the need to transfer information, but by the need to help students locate, retrieve, understand, analyze, construct, and use information, and by the need to train lifelong learners. The agent supports two aspects of students' learning in this course: students' knowledge and understanding of statistics and students' analyses of issues related to statistics. It does this in three ways. First, it can be used as a traditional test generator, as in the case of the assessment agent discussed in Chapter 6. Second, it integrates the documents accessed by students on the web and interacts with the students during the learning process. Finally, it can be used as an assistant by the students as they work through their assigned projects. For most of these projects, students are required to include some data analysis to support their argument, and so students can use the Statistical Analysis Assessment and Support Agent to help them extract all possible relevant information from a particular data set and support their analysis of the data. This particular function, that of an assistant, is similar to the one of the design assistant presented in Chapter 8. An interesting feature of Chapter 7 is that it is written from the perspective of the domain expert who has trained the agent and therefore it gives a first-hand account of how an expert interacts with a Disciple agent.
Chapter 8 presents a case study of using the Disciple approach to develop an agent that behaves as a personal assistant to the user. As opposed to the agents presented in Chapters 6 and 7 that are built by an expert for other users, this agent is developed by a user to be an assistant to himself or herself. The agent is continuously supervised and customized by the user according to the changing practices in the user's domain, as well as the needs and the preferences of the user. In this case study we will focus on an engineering design domain, more specifically, computer configuration tasks. The growing complexity of contemporary engineering designs requires design tools that play a more active role over the whole design process. One way to make the design tools more active is to have them behave as assistants and partners in the design process. The human designer and the assistant create designs together. The level of interaction between them depends on the quantity and quality of the assistant's knowledge. Initially, the agent will behave as a novice that is unable to compose the majority of designs. In this case the designer takes initiative and creates the designs, and the assistant learns from the designer. Gradually, the assistant learns to perform most of the routine (but usually more labor intensive) designs within an application domain. Because of its plausible reasoning capabilities, the assistant can also propose innovative designs that are corrected and finalized by the designer. Creative designs are specified by the designer. As a result of learning, designs that were innovative for the assistant become routine, and designs that were creative become first innovative and later routine ones. This process constantly increases the capabilities of the design team consisting of the human expert and the computer assistant.
Chapter 9 presents a case study of building and training a Disciple agent to behave as a military commander in a virtual environment. This is a type of agent that is trained by a user to perform tasks on user's behalf. The virtual military environment is the ModSAF (Modular Semi-Automated Forces) distributed interactive simulation that enables human participants at various locations to enter a synthetic world containing the essential elements of a military operation. There are many applications of such interactive simulations, among the most important being that of training individuals that interact with each other, such as collective training of military forces in large-scale exercises, peace-keeping operations or disaster relief. ModSAF is a very complex real-time application which simulates military operations. It provides facilities for creating and controlling virtual agents (such as virtual tanks, planes, ships, or infantry) acting in a realistic representation of the physical environment that utilizes digital terrain databases. In the ModSAF environment, human participants may cooperate with, command or compete against virtual agents. In the case study presented, an officer trains the Disciple agent to behave as a virtual company commander in the ModSAF environment. The officer trains the agent to perform various missions (such as a road march, bounding overwatch, or occupying a position) using the graphical interface of ModSAF that consists of a topographical map and various editors. The officer instructs the agent by giving an initial example of how to perform the mission that is to be taught. Then the officer guides and helps the agent to understand why the example given is a good solution to the mission problem. Next the agent will engage the officer in a dialog, showing the officer examples of how it would solve other similar missions, and asking for explanations if its solution is not correct. Through such simple and natural interactions, the agent learns complex rules for accomplishing its missions.
Finally, the bibliography contains, in addition to the papers referred in the book, basic titles from the fields of Machine Learning, Knowledge Acquisition and Intelligent Agents.
This book addresses issues of interest to a large spectrum of readers from research, industry, and academia. Researchers interested in building intelligent agents, whether through knowledge acquisition methods or through machine learning methods, will find in this book an integrated approach that uses the complementariness of many basic knowledge acquisition and machine learning techniques in order to take advantage of their strengths and to compensate for each others weaknesses. We believe that through such an approach it will some day be possible to develop learning agent shells that will be customized, taught and trained by normal users as easily as they now use personal computers for text processing or email.
Practitioners that develop various types of systems (educational systems, simulation systems, database systems, knowledge-based systems, etc.) will find in this book a detailed, yet intuitive presentation of an agent development methodology and tool, as well as several case studies of developing intelligent agents that illustrate different types of agents that are relevant to a wide variety of application domains. Such an agent could either enhance the capability, generality and usefulness of another computer system (like the history assessment agent), could be integrated within and enhance a larger multi-system environment (like the virtual military commander or the statistical analysis assessment and support agent), or could be used as an assistant to the user (like the engineering design assistant or the manufacturing assistant) or as an agent that performs various tasks at the user's request (like the stand-alone history assessment agent). These are, of course, only the few examples that are treated in detail in this book, but they show the generality of the proposed approach and may inspire the practitioners to use the Disciple methodology and shell to develop other types of agents for their particular needs.
This volume could also be used as a textbook for an introductory course in artificial intelligence, machine learning or knowledge acquisition. Chapters 3 and 4 cover, in a unified way, many of the topics introduced in these courses, both at the level of general principles and with detailed methods and many examples. Then Chapter 5 presents a practical implementation of a learning agent shell that will allow the students a hands-on experience. Finally, Chapters 6 through 9 show detailed case studies on how to apply the principles, techniques, methods and the learning shell presented in the previous chapters to build practical intelligent agents. These case studies are good examples of collaborative student projects, and provide many ideas for simpler projects.
Contributing writers
Gheorghe Tecuci authored or co-authored all the chapters.
Tomasz Dybala co-authored Chapter 4, Chapter 5 and Chapter 8.
Michael Hieb co-authored Chapter 4 and Chapter 9.
Harry Keeling co-authored Chapter 6.
Kathryn Wright co-authored Chapter 5.
Philippe Loustaunou co-authored Chapter 7.
David Hille co-authored Chapter 9.
Seok Won Lee co-authored the Bibliography.
The Curriculum Vitae of an Idea*
The origin of the ideas that have evolved into the apprenticeship multistrategy approach for building intelligent agents, presented in this book, can be traced back to 1984, when I first addressed the problem of how to build an instructable system. At that time I was a researcher at the Romanian Research Institute for Informatics, headed by Mihai Drăgănescu, who has supported me in many ways and more than I can express during my entire research career. Soon after that I had the chance to meet and work with Zani Bodnaru, who enthusiastically reacted to my proposal of building an expert system that would assist him in designing plans for loudspeaker manufacturing and could learn the knowledge it needed to design these plans. While investigating how our expert system could learn, I realized that none of the learning methods I knew were applicable in that domain. There were not many examples from which to learn rules through empirical induction, and there was not the strong domain theory needed to use the newer explanation-based learning approach. But there was a cooperative expert that was willing to interact with the system and to help it learn. It is by trying to solve this concrete learning problem that led to my development of a new kind of learning method that would integrate a form of explanation-based learning (to understand an example, with the expert’s help, and to generalize it), a kind of learning by analogy and experimentation (to automatically generate additional examples to be shown to the expert), and a kind of empirical induction (to learn from these examples). Because the system was trying to learn from the expert in an apprentice style (Mitchell et al., 1985), I called it Disciple. This basic method turned out to be one of the first multistrategy approaches to learning that later grew into the subfield of multistrategy machine learning (Michalski and Tecuci, 1994; Tecuci, 1993). It also turned out to be one of the first attempts to integrate machine learning and knowledge acquisition (Tecuci, Kedar, Kodratoff, 1994; Tecuci and Kodratoff, 1995). Yves Kodratoff reacted very enthusiastically to this new learning approach and invited me to present it at the First European Working Session on Learning that he was organizing in Orsay, in February 1996. We presented a joint paper at that workshop and this marked the beginning of a long cooperation between us on this subject. Yves supported me in many ways and contributed many ideas to the Disciple approach, being also the adviser of my Ph.D. Thesis, “Disciple: A theory, methodology and system for learning expert knowledge”, that I completed in 1988. Our joint work was supported by the Romanian Academy and the French National Center for Scientific Research.
After the completion of the Ph.D. thesis, I continued the development of the Disciple approach, improving the learning methods and extending them with guided knowledge elicitation (Tecuci, 1991; 1992). This work, done at George Mason University, was supported by NSF, ONR and DARPA. The more recent developments to the Disciple approach have been done in collaboration with my PhD students at George Mason University. Tomasz Dybala developed the interface modules of Disciple, modularized the learning method, and developed a scaled-up version of the Disciple Learning Agent Shell. He also developed the Design Assistant presented in Chapter 8 and contributed to the assessment agent presented in Chapter 6 and the virtual commander agent presented in Chapter 9. Michael Hieb enhanced the interactions between Disciple and the user, and contributed to the development of Disciple’s knowledge elicitation methods. He is also the main developer of the agent presented in Chapter 9 to which David Hille and J. Mark Pullen have also contributed. Harry Keeling significantly contributed to the development of the assessment agent presented in chapter 6 and also contributed to the assessment and support agent presented in Chapter 7. Kathryn Wright ported the Disciple Shell on Macintosh, further developed it and contributed to the assessment and support agent presented in Chapter 7. My colleague, Philippe Loustanou, was the domain expert and the driving force behind the development of the assessment and support agent presented in Chapter 7. Seok Won Lee worked on the bibliography and helped significantly with finalizing the book. Hadi Rezazad and Ping Shyr read several drafts of the book and made valuable suggestions. Tom Mitchell contributed indirectly to the Disciple approach through his influential work in machine learning, especially the version space representation, apprenticeship learning and explanation-based learning.
Andrew Sage, Murray Black and Peter Denning have helped and supported me in many ways. Henry Hamburger has been a wonderful colleague and friend that was always available when I needed his help. I would also like to acknowledge the more recent support from AFOSR, DARPA, and NSF, and especially David Gunning and David Luginbuhl. This support has facilitated the latest developments and applications of the Disciple approach and the writing of this book. Kate Brewin and Bridget Shine from Academic Press have been very patient with us and are a great team to work with.
Finally, my wife Sanda and our daughter Miruna Gabriela, to whom I am dedicating my work, have an invaluable contribution to what I am and do.
Gheorghe Tecuci