Nội dung

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 Representation is the area of Artificial Intelligence (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 intelligently, and what computational mechanisms could allow this knowledge to be made available to the agent as required. This book is intended as a text for an 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 thinks of Knowledge Representation in a Cognitive Science setting, where the focus is on plausible models of human mental states. The philosophy of this book is different from each of these. Here, we concentrate on reasoning as much as on representation . Indeed, we feel that it is the interplay between reasoning and representation that makes the field both intellectually exciting and relevant to practice. Why would anyone consider a representation scheme that was less expressive than that of a higher-order intensional “kitchensink” 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 represented knowledge is to be made available in an automated way to a system requiring it. Finally, psychological models of mental states that minimize the computational c 2003 R. Brachman and H. Levesque July 17, 2003 v aspects run the risk of not scaling up properly to account for human level competence. In the end, our view is 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 proposed in the literature. By exposing the heart of each style of representation, complemented 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 basic 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 procedural control; among the important concepts covered there we find rule-based production systems. Chapters 8 through 10 deal with a more object-oriented approach 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, including default reasoning and probabilities. Chapters 13 through 15 deal with forms of reasoning that are not concerned with deriving new beliefs from old ones, including 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 occasional tutorials, and is intended for upper-level undergraduate students or entrylevel graduate students in Computer Science or a related discipline. Students are expected to have already taken an introductory course in AI where the larger picture c 2003 R. Brachman and H. Levesque July 17, 2003 vi of intelligent agents is presented and explored, and to have some working knowledge 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 course fits well between a basic course in AI and research-oriented graduate courses (on topics like probabilistic reasoning, nonmonotonic reasoning, logics of knowledge 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 instructor 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. Brachman and H. Levesque 2.6 2.7 Contents Acknowledgments iii Preface iv 1 Introduction 1.1 The key concepts: knowledge, representation, and reasoning : : : : : : : : : : : : : : : : : : : : : 1.2 Why knowledge representation and reasoning? : 1.2.1 Knowledge-based systems : : : : : : : : 1.2.2 Why knowledge representation? : : : : : 1.2.3 Why reasoning? : : : : : : : : : : : : : 1.3 The role of logic : : : : : : : : : : : : : : : : : 1.4 Bibliographic notes : : : : : : : : : : : : : : : : 1.5 Exercises : : : : : : : : : : : : : : : : : : : : : 1 2 The Language of First-Order Logic 2.1 Introduction : : : : : : : : : : : 2.2 The syntax : : : : : : : : : : : : 2.3 The semantics : : : : : : : : : : 2.3.1 Interpretations : : : : : : 2.3.2 Denotation : : : : : : : : 2.3.3 Satisfaction and models : 2.4 The pragmatics : : : : : : : : : : 2.4.1 Logical consequence : : : 2.4.2 Why we care : : : : : : : 2.5 Explicit and implicit belief : : : : 2.5.1 An example : : : : : : : 2.5.2 Knowledge-based systems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 4 6 7 9 11 12 12 15 15 16 18 20 21 21 22 23 23 25 25 27 Bibliographic notes : Exercises : : : : : : July 17, 2003 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 Expressing Knowledge 3.1 Knowledge engineering 3.2 Vocabulary : : : : : : : 3.3 Basic facts : : : : : : : 3.4 Complex facts : : : : : 3.5 Terminological facts : : 3.6 Entailments : : : : : : 3.7 Abstract individuals : : 3.8 Other sorts of facts : : : 3.9 Bibliographic notes : : : 3.10 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 Resolution 4.1 The propositional case : : : : : : : : : : 4.1.1 Resolution derivations : : : : : : 4.1.2 An entailment procedure : : : : : 4.2 Handling variables and quantifiers : : : : 4.2.1 First-order Resolution : : : : : : 4.2.2 Answer extraction : : : : : : : : 4.2.3 Skolemization : : : : : : : : : : 4.2.4 Equality : : : : : : : : : : : : : 4.3 Dealing with computational intractability 4.3.1 The first-order case : : : : : : : : 4.3.2 The Herbrand Theorem : : : : : 4.3.3 The propositional case : : : : : : 4.3.4 The implications : : : : : : : : : 4.3.5 SAT solvers : : : : : : : : : : : 4.3.6 Most general unifiers : : : : : : : 4.3.7 Other refinements : : : : : : : : 4.4 Bibliographic notes : : : : : : : : : : : : 4.5 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 Reasoning with Horn Clauses 5.1 Horn clauses : : : : : : : : : : : : : : : : : : : 5.1.1 Resolution derivations with Horn clauses 5.2 SLD Resolution : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : viii 28 28 31 31 32 33 34 36 37 40 43 44 44 49 50 52 53 55 57 60 64 65 66 67 68 69 70 71 71 72 75 75 85 85 86 87 c 2003 R. Brachman and H. Levesque 5.3 5.4 5.5 5.2.1 Goal trees : : : : : Computing SLD derivations 5.3.1 Back-chaining : : : 5.3.2 Forward-chaining : 5.3.3 The first-order case : Bibliographic notes : : : : : Exercises : : : : : : : : : : July 17, 2003 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 Procedural Control of Reasoning 6.1 Facts and rules : : : : : : : : : : 6.2 Rule formation and search strategy 6.3 Algorithm design : : : : : : : : : 6.4 Specifying goal order : : : : : : 6.5 Committing to proof methods : : 6.6 Controlling backtracking : : : : : 6.7 Negation as failure : : : : : : : : 6.8 Dynamic databases : : : : : : : : 6.8.1 The PLANNER approach 6.9 Bibliographic notes : : : : : : : : 6.10 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 Rules in Production Systems 7.1 Production Systems — Basic Operation : : 7.2 Working Memory : : : : : : : : : : : : : 7.3 Production Rules : : : : : : : : : : : : : : 7.4 A First Example : : : : : : : : : : : : : : 7.5 A Second Example : : : : : : : : : : : : : 7.6 Conflict Resolution : : : : : : : : : : : : : 7.7 Making Production Systems More Efficient 7.8 Applications and Advantages : : : : : : : 7.9 Some Significant Production Rule Systems 7.10 Bibliographic notes : : : : : : : : : : : : : 7.11 Exercises : : : : : : : : : : : : : : : : : : 8 Object-Oriented Representation 8.1 Objects and frames : : : : : : : : : : 8.2 A basic frame formalism : : : : : : : 8.2.1 Generic and individual frames 8.2.2 Inheritance : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : ix 89 91 91 93 94 95 95 99 100 101 102 103 104 106 108 110 111 112 112 117 118 119 120 123 125 126 127 129 130 132 132 135 135 136 136 138 c 2003 R. Brachman and H. Levesque 8.3 8.4 8.5 8.6 x July 17, 2003 8.2.3 Reasoning with frames : : : : : : : : : An example: using frames to plan a trip : : : : 8.3.1 Using the example frames : : : : : : : Beyond the basics : : : : : : : : : : : : : : : 8.4.1 Other uses of frames : : : : : : : : : : 8.4.2 Extensions to the frame formalism : : : 8.4.3 Object-driven programming with frames Bibliographic notes : : : : : : : : : : : : : : : Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 Structured Descriptions 9.1 Descriptions : : : : : : : : : : : : : : : : : : : : : : : 9.1.1 Noun phrases : : : : : : : : : : : : : : : : : : 9.1.2 Concepts, roles, and constants : : : : : : : : : : 9.2 A description language : : : : : : : : : : : : : : : : : : 9.3 Meaning and Entailment : : : : : : : : : : : : : : : : : 9.3.1 Interpretations : : : : : : : : : : : : : : : : : : 9.3.2 Truth in an interpretation : : : : : : : : : : : : : 9.3.3 Entailment : : : : : : : : : : : : : : : : : : : : 9.4 Computing entailments : : : : : : : : : : : : : : : : : : 9.4.1 Simplifying the knowledge base : : : : : : : : : 9.4.2 Normalization : : : : : : : : : : : : : : : : : : 9.4.3 Structure matching : : : : : : : : : : : : : : : : 9.4.4 Computing satisfaction : : : : : : : : : : : : : : 9.4.5 The correctness of the subsumption computation 9.5 Taxonomies and classification : : : : : : : : : : : : : : 9.5.1 A taxonomy of atomic concepts and constants : : 9.5.2 Computing classification : : : : : : : : : : : : : 9.5.3 Answering the questions : : : : : : : : : : : : : 9.5.4 Taxonomies vs. frame hierarchies : : : : : : : : 9.5.5 Inheritance and propagation : : : : : : : : : : : 9.6 Beyond the basics : : : : : : : : : : : : : : : : : : : : 9.6.1 Extensions to the language : : : : : : : : : : : : 9.6.2 Applications of description logics : : : : : : : : 9.7 Bibliographic notes : : : : : : : : : : : : : : : : : : : : 9.8 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 140 141 146 148 149 149 151 152 152 155 156 156 157 158 160 160 161 162 163 164 164 167 168 169 170 170 171 174 174 174 175 175 178 180 180 c 2003 R. Brachman and H. Levesque July 17, 2003 10 Inheritance 10.1 Inheritance networks : : : : : : : : : : : : : : 10.1.1 Strict inheritance : : : : : : : : : : : : 10.1.2 Defeasible inheritance : : : : : : : : : 10.2 Strategies for defeasible inheritance : : : : : : 10.2.1 The shortest path heuristic : : : : : : : 10.2.2 Problems with shortest path : : : : : : 10.2.3 Inferential distance : : : : : : : : : : : 10.3 A formal account of inheritance networks : : : 10.3.1 Extensions : : : : : : : : : : : : : : : 10.3.2 Some subtleties of inheritance reasoning 10.4 Bibliographic notes : : : : : : : : : : : : : : : 10.5 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 Defaults 11.1 Introduction : : : : : : : : : : : : : : : : : : : : : 11.1.1 Generics and Universals : : : : : : : : : : : 11.1.2 Default reasoning : : : : : : : : : : : : : : 11.1.3 Non-monotonicity : : : : : : : : : : : : : : 11.2 Closed-world Reasoning : : : : : : : : : : : : : : : 11.2.1 The closed-world assumption : : : : : : : : 11.2.2 Consistency and completeness of knowledge 11.2.3 Query evaluation : : : : : : : : : : : : : : : 11.2.4 Consistency and a generalized assumption : : 11.2.5 Quantifiers and domain closure : : : : : : : 11.3 Circumscription : : : : : : : : : : : : : : : : : : : 11.3.1 Minimal entailment : : : : : : : : : : : : : 11.3.2 The circumscription axiom : : : : : : : : : : 11.3.3 Fixed and variable predicates : : : : : : : : 11.4 Default logic : : : : : : : : : : : : : : : : : : : : : 11.4.1 Default rules : : : : : : : : : : : : : : : : : 11.4.2 Default extensions : : : : : : : : : : : : : : 11.4.3 Multiple extensions : : : : : : : : : : : : : 11.5 Autoepistemic logic : : : : : : : : : : : : : : : : : 11.5.1 Stable sets and expansions : : : : : : : : : : 11.5.2 Enumerating stable expansions : : : : : : : : 11.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : 11.7 Bibliographic notes : : : : : : : : : : : : : : : : : : 11.8 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xi 185 186 188 189 191 191 193 193 195 197 200 202 202 203 203 204 205 207 207 208 209 209 210 211 213 214 216 217 219 220 221 222 225 226 227 230 230 230 c 2003 R. Brachman and H. Levesque July 17, 2003 12 Vagueness, Uncertainty, and Degrees of Belief 12.1 Non-categorical reasoning : : : : : : : : : : : : 12.2 Objective probability : : : : : : : : : : : : : : : 12.2.1 The basic postulates : : : : : : : : : : : 12.2.2 Conditional probability and independence 12.3 Subjective probability : : : : : : : : : : : : : : 12.3.1 From statistics to belief : : : : : : : : : 12.3.2 A basic Bayesian approach : : : : : : : : 12.3.3 Belief networks : : : : : : : : : : : : : 12.3.4 An example network : : : : : : : : : : : 12.3.5 Influence diagrams : : : : : : : : : : : : 12.3.6 Dempster-Shafer theory : : : : : : : : : 12.4 Vagueness : : : : : : : : : : : : : : : : : : : : 12.4.1 Conjunction and disjunction : : : : : : : 12.4.2 Rules : : : : : : : : : : : : : : : : : : : 12.4.3 A Bayesian reconstruction : : : : : : : : 12.5 Bibliographic notes : : : : : : : : : : : : : : : : 12.6 Exercises : : : : : : : : : : : : : : : : : : : : : 13 Abductive Reasoning 13.1 Diagnosis : : : : : : : : : : : : : 13.2 Explanation : : : : : : : : : : : : 13.2.1 Some simplifications : : : : 13.2.2 Prime implicates : : : : : : 13.2.3 Computing explanations : : 13.3 A circuit example : : : : : : : : : 13.3.1 The diagnosis : : : : : : : 13.3.2 Consistency-based diagnosis 13.4 Beyond the basics : : : : : : : : : 13.4.1 Extensions : : : : : : : : : 13.4.2 Other applications : : : : : 13.5 Bibliographic notes : : : : : : : : : 13.6 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 Actions 14.1 The situation calculus : : : : : : : : : 14.1.1 Fluents : : : : : : : : : : : : : 14.1.2 Precondition and effect axioms 14.1.3 Frame axioms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xii 233 234 235 236 237 239 239 240 241 243 246 247 249 251 251 255 258 258 263 264 265 266 267 268 269 270 273 274 274 275 276 276 279 280 280 281 282 c 2003 R. Brachman and H. Levesque July 17, 2003 14.1.4 Using the situation calculus : : 14.2 A simple solution to the frame problem 14.2.1 Explanation closure : : : : : : 14.2.2 Successor state axioms : : : : : 14.2.3 Summary : : : : : : : : : : : 14.3 Complex actions : : : : : : : : : : : : 14.3.1 The Do formula : : : : : : : : 14.3.2 GOLOG : : : : : : : : : : : : 14.3.3 An example : : : : : : : : : : 14.4 Bibliographic notes : : : : : : : : : : : 14.5 Exercises : : : : : : : : : : : : : : : : 15 Planning 15.1 Planning in the situation calculus : : : 15.1.1 An example : : : : : : : : : 15.1.2 Using Resolution : : : : : : : 15.2 The STRIPS Representation : : : : : 15.2.1 Progressive planning : : : : : 15.2.2 Regressive planning : : : : : 15.3 Planning as a reasoning task : : : : : 15.3.1 Avoiding redundant search : : 15.3.2 Application-dependent control 15.4 Beyond the basics : : : : : : : : : : 15.4.1 Hierarchical planning : : : : 15.4.2 Conditional planning : : : : : 15.4.3 “Even the best-laid plans. . . ” 15.5 Bibliographic notes : : : : : : : : : : 15.6 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 The Tradeoff Between Expressiveness and Tractability 16.1 A description logic case study : : : : : : : : : : : 16.1.1 Two description logic languages : : : : : : 16.1.2 Computing subsumption : : : : : : : : : : 16.2 Limited languages : : : : : : : : : : : : : : : : : 16.3 What makes reasoning hard? : : : : : : : : : : : : 16.4 Vivid knowledge : : : : : : : : : : : : : : : : : : 16.4.1 Analogues : : : : : : : : : : : : : : : : : 16.5 Beyond vivid : : : : : : : : : : : : : : : : : : : : 16.5.1 Sets of literals : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xiii 283 285 285 286 287 288 289 290 291 293 293 297 298 298 300 304 306 307 308 309 310 312 312 312 313 314 314 317 318 319 320 322 323 325 327 328 328 c 2003 R. Brachman and H. Levesque 16.5.2 Incorporating definitions 16.5.3 Hybrid reasoning : : : : 16.6 Bibliographic notes : : : : : : : 16.7 Exercises : : : : : : : : : : : : Bibliography July 17, 2003 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xiv 329 330 331 331 339 c 2003 R. Brachman and H. Levesque Chapter 1 Intelligence, as exhibited by people anyway, is surely one of the most complex and mysterious phenomena that we are aware of. One striking aspect of intelligent behaviour is that it is clearly conditioned by knowledge: for a very wide range of activities, we make decisions about what to do based on what we know (or believe) about the world, effortlessly and unconsciously. Using what we know in this way is so commonplace, that we only really pay attention to it when it is not there. When we say that someone behaved unintelligently, like when someone uses a lit match to see if there is any gas in a car’s gas tank, what we usually mean is not that there is something that the person did not know, but rather that the person has failed to use what he or she did know. We might say: “You weren’t thinking!” Indeed, it is thinking that is supposed to bring what is relevant in what we know to bear on what we are trying to do. One definition of Artificial Intelligence (AI) is that it is the study of intelligent behaviour achieved through computational means. Knowledge Representation and Reasoning, then, is that part of AI that is concerned with how an agent uses what it knows in deciding what to do. It is the study of thinking as a computational process. This book is an introduction to that field and the ways that it has invented to create representations of knowledge, and computational processes that reason by manipulating these knowledge representation structures. If this book is an introduction to the area, then this chapter is an introduction to the introduction. In it, we will try to address, if only briefly, some significant questions that surround the deep and challenging topics of the field: what exactly do we mean by “knowledge,” by “representation,” and by “reasoning,” and why do we think these concepts are useful for building AI systems? In the end, these are philosophical questions, and thorny ones at that; they bear considerable inves- 2 tigation by those with a more philosophical bent and can be the subject matter of whole careers. But the purpose of this chapter is not to cover in any detail what philosophers, logicians, and computer scientists have said about knowledge over the years; it is rather to glance at some of the main issues involved, and examine their bearings on Artificial Intelligence and the prospect of a machine that could think. 1.1 Introduction July 17, 2003 The key concepts: knowledge, representation, and reasoning Knowledge What is knowledge? This is a question that has been discussed by philosophers since the ancient Greeks, and it is still not totally demystified. We certainly will not attempt to be done with it here. But to get a rough sense of what knowledge is supposed to be, it is useful to look at how we talk about it informally. First, observe that when we say something like “John knows that . . . ,” we fill in the blank with a simple declarative sentence. So we might say that “John knows that Mary will come to the party” or that “John knows that Abraham Lincoln was assassinated.” This suggests that, among other things, knowledge is a relation between a knower, like John, and a proposition, that is, the idea expressed by a simple declarative sentence, like “Mary will come to the party”. Part of the mystery surrounding knowledge is due to the nature of propositions. What can we say about them? As far as we are concerned, what matters about propositions is that they are abstract entities that can be true or false, right or wrong.1 When we say that “John knows that p,” we can just as well say that “John knows that it is true that p:” Either way, to say that John knows something is to say that John has formed a judgment of some sort, and has come to realize that the world is one way and not another. In talking about this judgment, we use propositions to classify the two cases. A similar story can be told about a sentence like “John hopes that Mary will come to the party.” The same proposition is involved, but the relationship John has to it is different. Verbs like “knows,” “hopes,” “regrets,” “fears,” and “doubts” all denote propositional attitudes, relationships between agents and propositions. In all cases, what matters about the proposition is its truth: if John hopes that Mary 1 Strictly speaking, we might want to say that the sentences expressing the proposition are true or false, and that the propositions themselves are either factual or non-factual. Further, because of linguistic features such as indexicals (that is, words whose referents change with the context in which they are uttered, such as “me” and “yesterday”), we more accurately say that it is actual tokens of sentences or their uses in specific contexts that are true or false, not the sentences themselves. c 2003 R. Brachman and H. Levesque July 17, 2003 3 will come to the party, then John is hoping that the world is one way and not another, as classified by the proposition. Of course, there are sentences involving knowledge that do not explicitly mention a proposition. When we say “John knows who Mary is taking to the party,” or “John knows how to get there,” we can at least imagine the implicit propositions: “John knows that Mary is taking so-and-so to the party”, or “John knows that to get to the party, you go two blocks past Main Street, turn left, . . . ,” and so on. On the other hand, when we say that John has a skill as in “John knows how to play piano,” or a deep understanding of someone or something as in “John knows Bill well,” it is not so clear that any useful proposition is involved. While this is certainly challenging subject matter, we will have nothing further to say about this latter form of knowledge in this book. A related notion that we are concerned with, however, is the concept of belief. The sentence “John believes that p” is clearly related to “John knows that p.” We use the former when we do not wish to claim that John’s judgment about the world is necessarily accurate or held for appropriate reasons. We sometimes use it when we feel that John might not be completely convinced. In fact, we have a full range of propositional attitudes, expressed by sentences like “John is absolutely certain that p,” “John is confident that p,” “John is of the opinion that p,” “John suspects that p,” and so on, that differ only in the level of conviction they attribute. For now, we will not distinguish amongst any of them. What matters is that they all share with knowledge a very basic idea: John takes the world to be one way and not another. Representation The concept of representation is as philosophically vexing as that of knowledge. Very roughly speaking, representation is a relationship between two domains where the first is meant to “stand for” or take the place of the second. Usually, the first domain, the representor, is more concrete, immediate, or accessible in some way than the second. For example, a drawing of a milkshake and a hamburger on a sign might stand for a less immediately visible fast food restaurant; the drawing of a circle with a plus below it might stand for the much more abstract concept of womanhood; an elected legislator might stand for his or her constituency. The type of representor that we will be most concerned with here is the formal symbol, that is, a character or group of them taken from some predetermined alphabet. The digit “7,” for example, stands for the number 7, as does the group of letters “VII,” and in other contexts, the words “sept” and “shichi .” As with all representation, it is assumed to be easier to deal with symbols (recognize them, distinguish them from each other, display them, etc.) than with what the symbols represent. In some cases, a word like “John” might stand for something quite concrete; but many c 2003 R. Brachman and H. Levesque July 17, 2003 4 words, like “love” or “truth,” stand for abstractions. Of special concern to us is when a group of formal symbols stands for a proposition: “John loves Mary” stands for the proposition that John loves Mary. Again, the symbolic English sentence is fairly concrete: it has distinguishable parts involving the 3 words, for example, and a recognizable syntax. The proposition, on the other hand, is abstract: it is something like a classification of all the different ways we can imagine the world to be into two groups: those where John loves Mary, and those where he does not. Knowledge Representation, then, is this: it is the field of study concerned with using formal symbols to represent a collection of propositions believed by some putative agent. As we will see, however, we do not want to insist that these symbols must represent all the propositions believed by the agent. There may very well be an infinite number of propositions believed, only a finite number of which are ever represented. It will be the role of reasoning to bridge the gap between what is represented and what is believed. Reasoning So what is reasoning? In general, it is the formal manipulation of the symbols representing a collection of believed propositions to produce representations of new ones. It is here that we use the fact that symbols are more accessible than the propositions they represent: they must be concrete enough that we can manipulate them (move them around, take them apart, copy them, string them together) in such a way as to construct representations of new propositions. The analogy here is with arithmetic. We can think of binary addition as being a certain formal manipulation: we start with symbols like “1011” and “10,” for instance, and end up with “1101.” The manipulation here is addition since the final symbol represents the sum of the numbers represented by the initial ones. Reasoning is similar: we might start with the sentences “John loves Mary” and “Mary is coming to the party,” and after a certain amount of manipulation produce the sentence “Someone John loves is coming to the party.” We would call this form of reasoning logical inference because the final sentence represents a logical conclusion of the propositions represented by the initial ones, as we will discuss below. According to this view (first put forward, incidentally, by the philosopher Gottfried Leibniz in the 17th century), reasoning is a form of calculation, not unlike arithmetic, but over symbols standing for propositions rather than numbers. 1.2 Why knowledge representation and reasoning? Why is knowledge even relevant at all to AI systems? The first answer that comes to mind is that it is sometimes useful to describe the behaviour of sufficiently complex c 2003 R. Brachman and H. Levesque July 17, 2003 5 systems (human or otherwise) using a vocabulary involving terms like “beliefs,” “goals,” “intentions,” “hopes,” and so on. Imagine, for example, playing a game of chess against a complex chess-playing program. In looking at one of its moves, we might say to ourselves something like this: “It moved this way because it believed its queen was vulnerable, but still wanted to attack the rook.” In terms of how the chess-playing program is actually constructed, we might have said something more like, “It moved this way because evaluation procedure P using static evaluation function Q returned a value of +7 after an alpha-beta minimax search to depth d.” The problem is that this second description, although perhaps quite accurate, is at the wrong level of detail, and does not help us determine what chess move we should make in response. Much more useful is to understand the behaviour of the program in terms of the immediate goals being pursued, relative to its beliefs, long-term intentions, and so on. This is what the philosopher Daniel Dennett calls taking an intentional stance towards the chess-playing system. This is not to say that an intentional stance is always appropriate. We might think of a thermostat, to take a classic example, as “knowing” that the room is too cold and “wanting” to warm it up. But this type of anthropomorphization is typically inappropriate: there is a perfectly workable electrical account of what is going on. Moreover, it can often be quite misleading to describe an AI system in intentional terms: using this kind of vocabulary, we could end up fooling ourselves into thinking we are dealing with something much more sophisticated than it actually is. But there’s a more basic question: is this what Knowledge Representation is all about? Is all the talk about knowledge just that—talk—a stance one may or may not choose to take towards a complex system? To understand the answer, first observe that the intentional stance says nothing about what is or is not represented symbolically within a system. In the chessplaying program, the board position might be represented symbolically, say, but the goal of getting a knight out early, for instance, may not be. Such a goal might only emerge out of a complex interplay of many different aspects of the program, its evaluation functions, book move library, and so on. Yet, we may still choose to describe the system as “having” this goal, if this properly explains its behaviour. So what role is played by a symbolic representation? The hypothesis underlying work in Knowledge Representation is that we will want to construct systems that contain symbolic representations with two important properties. First is that we (from the outside) can understand them as standing for propositions. Second is that the system is designed to behave the way that it does because of these symbolic representations. This is what is called the Knowledge Representation Hypothesis c 2003 R. Brachman and H. Levesque July 17, 2003 6 by the philosopher Brian Smith: Any mechanically embodied intelligent process will be comprised of structural ingredients that a) we as external observers naturally take to represent a propositional account of the knowledge that the overall process exhibits, and b) independent of such external semantic attribution, play a formal but causal and essential role in engendering the behaviour that manifests that knowledge. In other words, the Knowledge Representation Hypothesis implies that we will want to construct systems for which the intentional stance is grounded by design in symbolic representations. We will call such systems knowledge-based systems and the symbolic representations involved their knowledge bases (KB’s). 1.2.1 Knowledge-based systems To see what a knowledge-based system amounts to, it is helpful to look at two very simple prolog programs with identical behaviour. Consider the first: printColour(snow) :- !, write("It’s white."). printColour(grass) :- !, write("It’s green."). printColour(sky) :- !, write("It’s yellow."). printColour(X) :- write("Beats me."). And here is an alternate: printColour(X) :- colour(X,Y), !, write("It’s "), write(Y), write("."). printColour(X) :- write("Beats me."). colour(snow,white). colour(sky,yellow). colour(X,Y) :- madeof(X,Z), colour(Z,Y). madeof(grass,vegetation). colour(vegetation,green). Observe that both programs are able to print out the colour of various items (getting the sky wrong, as it turns out). Taking an intentional stance, both might be said to “know” that the colour of snow is white. The crucial point, as we will see, however, is that only the second program is designed according to the Knowledge Representation Hypothesis.