Ebook Knowledge Representation and Reasonin - Ronald J. Brachman

Knowledge Representation and Reasoning Ronald J. Brachman AT&T Labs – Research Florham Park, New Jersey USA 07932 rjb@research.att.com Hector J. Levesque Department of Computer Science University of Toronto Toronto, Ontario Canada M5S 3H5 hector@cs.toronto.edu c 2003 Ronald J. Brachman and Hector J. Levesque Acknowledgments Preface Knowledge Representationisthe areaof ArtificialIntelligence(AI)concerned with how knowledge can be represented symbolically and manipulated in an automated way by reasoning programs. It is at the very core of a radical idea about how to understand intelligence: instead of trying to understand or build brains from the bottom up, we try to understand or build intelligent behavior from the top down. In particular, we ask what an agent would need to know in order to behave intelli-gently,andwhatcomputationalmechanismscouldallowthisknowledgetobemade availabletotheagentas required. Thisbook isintended asatextforan introductory course in this area of research. There are many different ways to approach and study the area of Knowledge Representation. One might think in terms of a representation language like that of symbolic logic, and concentrate on how logic can be applied to problems in AI. This has led to courses and research in what is sometimes called “logic-based AI.” In a different vein, it is possible to study Knowledge Representation in terms of the specification and development of large knowledge-based systems. From this line of thinking arise courses and research in specification languages, knowledge engineering, and what are sometimes called “ontologies.” Yet a different approach thinksofKnowledgeRepresentationinaCognitiveSciencesetting,wherethefocus is on plausible models of human mental states. The philosophy of this book is different from each of these. Here, we con-centrate on reasoning as much as on representation. Indeed, we feel that it is the interplay between reasoning and representation that makesthe field both intellectu-ally exciting and relevant to practice. Why would anyone consider a representation scheme that was less expressive than that of a higher-order intensional “kitchen-sink” logic if it were not for the computational demands imposed by automated reasoning? Similarly, even the most comprehensive ontology or common sense knowledge base will remain inert without a clear formulation of how the repre-sentedknowledgeistobemadeavailableinan automatedwaytoasystemrequiring it. Finally, psychological models of mental states that minimize the computational c 2003 R. BrachmanandH.Levesque July17, 2003 v c 2003 R. BrachmanandH.Levesque July17, 2003 vi aspects run the risk of not scaling up properly to account for human level compe-tence. In the end, our viewis that Knowledge Representation is the study of how what we know can at the same time be represented as comprehensibly as possible and reasoned with as effectively as possibly. There is a tradeoff between these two concerns, which is an implicit theme throughout the book, and explicit in the final chapter. Although we start with full first-order logic as a representation language, and logical entailment as the basis for reasoning, this is just the starting point, and a somewhat unrealistic one at that. Subsequent chapters expand and enhance the picture by looking at languages with very different intuitions and emphases, and approaches to reasoning sometimes quite removed from logical entailment. Our approach is to explain the key concepts underlying a wide variety of formalisms, without trying to account for the quirks of particular representation schemes pro-posed in the literature. By exposing the heart of each style of representation, com-plemented by a discussion of the basics of reasoning with that representation, we aim to give the reader a solid foundation for understanding the more detailed and sophisticated work found in the research literature. The book is organized as follows. The first chapter provides an overview and motivation for the whole area. Chapters 2 through 5 are concerned with the ba-sic techniques of Knowledge Representation using first-order logic in a direct way. These early chapters introduce the notation of first-order logic, show how it can be used to represent commonsense worlds, and cover the key reasoning technique of Resolution theorem-proving. Chapters 6 and 7 are concerned with representing knowledge in a more limited way, so that the reasoning is more amenable to pro-cedural control; among the important concepts covered there we find rule-based production systems. Chapters 8 through 10 deal with a more object-oriented ap-proach to Knowledge Representation and the taxonomic reasoning that goes with it. Here we delve into the ideas of frame representations and description logics, as well as spending time on the notion of inheritance. Chapters 11 and 12 deal with reasoning that is uncertain or not logically guaranteed to be correct, includ-ing default reasoning and probabilities. Chapters 13 through 15 deal with forms of reasoning that are not concerned with deriving new beliefs from old ones, includ-ing the notion of planning, which is central to AI. Finally, Chapter 16 explores the tradeoff mentioned above. A course based on the topics of this book has been taught a number of times at the University of Toronto. The course comprises about 24 hours of lectures and oc-casional tutorials, and is intended for upper-level undergraduate students or entry-level graduate students in Computer Science or a related discipline. Students are expectedtohave alreadytakenan introductorycourseinAI wherethe largerpicture of intelligent agents is presented and explored, and to have some working knowl-edge of symbolic logic and symbolic computation, for example, in Prolog or Lisp. As part of a program in AI or Cognitive Science, the Knowledge Representation coursefitswellbetweenabasiccourseinAIandresearch-orientedgraduatecourses (on topics like probabilistic reasoning, nonmonotonic reasoning, logics of knowl-edge and belief, and so on). A number of the exercises used in the course are included at the end of each chapter of the book. These exercises focus on the technical aspects of Knowledge Representation, although it should be possible with this book to consider some essay-type questions as well. Depending on the students involved, a course in-structor may want to emphasize the programming questions and de-emphasize the mathematics, or perhaps vice-versa. Comments and corrections on all aspects of the book are most welcome and should be sent to the authors. c 2003 R. BrachmanandH.Levesque July17, 2003 viii 2.6 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 28 2.7 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28 3 Expressing Knowledge 31 3.1 Knowledge engineering : : : : : : : : : : : : : : : : : : : : : : 31 Contents 3.2 Vocabulary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32 3.3 Basic facts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 3.4 Complex facts : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 3.5 Terminological facts : : : : : : : : : : : : : : : : : : : : : : : : 36 3.6 Entailments : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 3.7 Acknowledgments iii 3.8 Abstract individuals : : : : : : : : : : : : : : : : : : : : : : : : 40 Other sorts of facts : : : : : : : : : : : : : : : : : : : : : : : : : 43 Preface iv 3.9 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 44 3.10 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44 1 Introduction 1 1.1 The key concepts: knowledge, representation, and reasoning : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Why knowledge representation and reasoning? : : : : : : : : : : 4 1.2.1 Knowledge-based systems : : : : : : : : : : : : : : : : : 6 1.2.2 Why knowledge representation? : : : : : : : : : : : : : : 7 1.2.3 Why reasoning? : : : : : : : : : : : : : : : : : : : : : : 9 1.3 The role of logic : : : : : : : : : : : : : : : : : : : : : : : : : : 11 1.4 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 12 1.5 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 4 Resolution 49 4.1 The propositional case : : : : : : : : : : : : : : : : : : : : : : : 50 4.1.1 Resolution derivations : : : : : : : : : : : : : : : : : : : 52 4.1.2 An entailment procedure : : : : : : : : : : : : : : : : : : 53 4.2 Handling variables and quantifiers : : : : : : : : : : : : : : : : : 55 4.2.1 First-order Resolution : : : : : : : : : : : : : : : : : : : 57 4.2.2 Answer extraction : : : : : : : : : : : : : : : : : : : : : 60 4.2.3 Skolemization : : : : : : : : : : : : : : : : : : : : : : : 64 4.2.4 Equality : : : : : : : : : : : : : : : : : : : : : : : : : : 65 4.3 Dealing with computational intractability : : : : : : : : : : : : : 66 2 The Language of First-Order Logic 15 2.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 2.2 The syntax : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.3 The semantics : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 2.3.1 Interpretations : : : : : : : : : : : : : : : : : : : : : : : 20 2.3.2 Denotation : : : : : : : : : : : : : : : : : : : : : : : : : 21 2.3.3 Satisfaction and models : : : : : : : : : : : : : : : : : : 21 2.4 The pragmatics : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 2.4.1 Logical consequence : : : : : : : : : : : : : : : : : : : : 23 4.3.1 The first-order case : : : : : : : : : : : : : : : : : : : : : 67 4.3.2 The Herbrand Theorem : : : : : : : : : : : : : : : : : : 68 4.3.3 The propositional case : : : : : : : : : : : : : : : : : : : 69 4.3.4 The implications : : : : : : : : : : : : : : : : : : : : : : 70 4.3.5 SAT solvers : : : : : : : : : : : : : : : : : : : : : : : : 71 4.3.6 Most general unifiers : : : : : : : : : : : : : : : : : : : : 71 4.3.7 Other refinements : : : : : : : : : : : : : : : : : : : : : 72 4.4 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 75 4.5 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75 2.4.2 Why we care : : : : : : : : : : : : : : : : : : : : : : : : 23 2.5 Explicit and implicit belief : : : : : : : : : : : : : : : : : : : : : 25 2.5.1 An example : : : : : : : : : : : : : : : : : : : : : : : : 25 2.5.2 Knowledge-based systems : : : : : : : : : : : : : : : : : 27 5 Reasoning with Horn Clauses 85 5.1 Horn clauses : : : : : : : : : : : : : : : : : : : : : : : : : : : : 85 5.1.1 Resolution derivations with Horn clauses : : : : : : : : : 86 5.2 SLD Resolution : : : : : : : : : : : : : : : : : : : : : : : : : : 87 c 2003 R. BrachmanandH.Levesque July17, 2003 ix c 2003 R. BrachmanandH.Levesque July17, 2003 x 5.2.1 Goal trees : : : : : : : : : : : : : : : : : : : : : : : : : 89 8.2.3 Reasoning with frames : : : : : : : : : : : : : : : : : : : 140 5.3 Computing SLD derivations : : : : : : : : : : : : : : : : : : : : 91 8.3 An example: using frames to plan a trip : : : : : : : : : : : : : : 141 5.3.1 Back-chaining : : : : : : : : : : : : : : : : : : : : : : : 91 8.3.1 Using the example frames : : : : : : : : : : : : : : : : : 146 5.3.2 Forward-chaining : : : : : : : : : : : : : : : : : : : : : 93 8.4 Beyond the basics : : : : : : : : : : : : : : : : : : : : : : : : : 148 5.3.3 The first-order case : : : : : : : : : : : : : : : : : : : : : 94 8.4.1 Other uses of frames : : : : : : : : : : : : : : : : : : : : 149 5.4 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 95 5.5 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 95 8.4.2 Extensions to the frame formalism : : : : : : : : : : : : : 149 8.4.3 Object-driven programming with frames : : : : : : : : : : 151 6 Procedural Control of Reasoning 99 6.1 Facts and rules : : : : : : : : : : : : : : : : : : : : : : : : : : : 100 8.5 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 152 8.6 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 152 6.2 Rule formation and search strategy : : : : : : : : : : : : : : : : : 101 9 Structured Descriptions 155 6.3 Algorithm design : : : : : : : : : : : : : : : : : : : : : : : : : : 102 9.1 Descriptions : : : : : : : : : : : : : : : : : : : : : : : : : : : : 156 6.4 Specifying goal order : : : : : : : : : : : : : : : : : : : : : : : 103 9.1.1 Noun phrases : : : : : : : : : : : : : : : : : : : : : : : 156 6.5 Committing to proof methods : : : : : : : : : : : : : : : : : : : 104 9.1.2 Concepts, roles, and constants : : : : : : : : : : : : : : : 157 6.6 Controlling backtracking : : : : : : : : : : : : : : : : : : : : : : 106 6.7 Negation as failure : : : : : : : : : : : : : : : : : : : : : : : : : 108 9.2 A description language : : : : : : : : : : : : : : : : : : : : : : : 158 9.3 Meaning and Entailment : : : : : : : : : : : : : : : : : : : : : : 160 6.8 Dynamic databases : : : : : : : : : : : : : : : : : : : : : : : : : 110 9.3.1 Interpretations : : : : : : : : : : : : : : : : : : : : : : : 160 6.8.1 The PLANNER approach : : : : : : : : : : : : : : : : : 111 9.3.2 Truth in an interpretation : : : : : : : : : : : : : : : : : : 161 6.9 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 112 9.3.3 Entailment : : : : : : : : : : : : : : : : : : : : : : : : : 162 6.10 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 112 7 Rules in Production Systems 117 7.1 Production Systems — Basic Operation : : : : : : : : : : : : : : 118 7.2 Working Memory : : : : : : : : : : : : : : : : : : : : : : : : : 119 7.3 Production Rules : : : : : : : : : : : : : : : : : : : : : : : : : : 120 7.4 A First Example : : : : : : : : : : : : : : : : : : : : : : : : : : 123 7.5 A Second Example : : : : : : : : : : : : : : : : : : : : : : : : : 125 7.6 Conflict Resolution : : : : : : : : : : : : : : : : : : : : : : : : : 126 7.7 Making Production Systems More Efficient : : : : : : : : : : : : 127 7.8 Applications and Advantages : : : : : : : : : : : : : : : : : : : 129 7.9 Some Significant Production Rule Systems : : : : : : : : : : : : 130 7.10 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 132 7.11 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 132 8 Object-Oriented Representation 135 8.1 Objects and frames : : : : : : : : : : : : : : : : : : : : : : : : : 135 8.2 A basic frame formalism : : : : : : : : : : : : : : : : : : : : : : 136 9.4 Computing entailments : : : : : : : : : : : : : : : : : : : : : : : 163 9.4.1 Simplifying the knowledge base : : : : : : : : : : : : : : 164 9.4.2 Normalization : : : : : : : : : : : : : : : : : : : : : : : 164 9.4.3 Structure matching : : : : : : : : : : : : : : : : : : : : : 167 9.4.4 Computing satisfaction : : : : : : : : : : : : : : : : : : : 168 9.4.5 The correctness of the subsumption computation : : : : : 169 9.5 Taxonomies and classification : : : : : : : : : : : : : : : : : : : 170 9.5.1 A taxonomy of atomic concepts and constants : : : : : : : 170 9.5.2 Computing classification : : : : : : : : : : : : : : : : : : 171 9.5.3 Answering the questions : : : : : : : : : : : : : : : : : : 174 9.5.4 Taxonomies vs. frame hierarchies : : : : : : : : : : : : : 174 9.5.5 Inheritance and propagation : : : : : : : : : : : : : : : : 174 9.6 Beyond the basics : : : : : : : : : : : : : : : : : : : : : : : : : 175 9.6.1 Extensions to the language : : : : : : : : : : : : : : : : : 175 9.6.2 Applications of description logics : : : : : : : : : : : : : 178 9.7 Bibliographic notes : : : : : : : : : : : : : : : : : : : : : : : : : 180 9.8 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 180 8.2.1 Generic and individual frames : : : : : : : : : : : : : : : 136 8.2.2 Inheritance : : : : : : : : : : : : : : : : : : : : : : : : : 138 ... - tailieumienphi.vn