Knowledge Representation and Reasoning

by Brachman; Levesque

• ISBN13: 9781558609327
• ISBN10: 1558609326
• Format: Hardcover
• Copyright: 2004-05-19
• Publisher: Elsevier Science

Summary

Knowledge representation is at the very core of a radical idea for understanding intelligence. Instead of trying to understand or build brains from the bottom up, its goal is to understand and build intelligent behavior from the top down, putting the focus on what an agent needs to know in order to behave intelligently, how this knowledge can be represented symbolically, and how automated reasoning procedures can make this knowledge available as needed. This landmark text takes the central concepts of knowledge representation developed over the last 50 years and illustrates them in a lucid and compelling way. Each of the various styles of representation is presented in a simple and intuitive form, and the basics of reasoning with that representation are explained in detail. This approach gives readers a solid foundation for understanding the more advanced work found in the research literature. The presentation is clear enough to be accessible to a broad audience, including researchers and practitioners in database management, information retrieval, and object-oriented systems as well as artificial intelligence. This book provides the foundation in knowledge representation and reasoning that every AI practitioner needs.

Table of Contents

Preface	xvii
Acknowledgments	xxvii
1 Introduction	1	(186)
1.1 The Key Concepts: Knowledge, Representation, and Reasoning	2	(3)
1.2 Why Knowledge Representation and Reasoning?	5	(6)
1.2.1 Knowledge-Based Systems	6	(1)
1.2.2 Why Knowledge Representation?	7	(2)
1.2.3 Why Reasoning?	9	(2)
1.3 The Role of Logic	11	(1)
1.4 Bibliographic Notes	12	(1)
1.5 Exercises	13	(2)
2 The Language of First-Order Logic	15	(16)
2.1 Introduction	15	(1)
2.2 The Syntax	16	(2)
2.3 The Semantics	18	(4)
2.3.1 Interpretations	20	(1)
2.3.2 Denotation	21	(1)
2.3.3 Satisfaction and Models	22	(1)
2.4 The Pragmatics	22	(3)
2.4.1 Logical Consequence	23	(1)
2.4.2 Why We Care	23	(2)
2.5 Explicit and Implicit Belief	25	(3)
2.5.1 An Example	25	(2)
2.5.2 Knowledge-Based Systems	27	(1)
2.6 Bibliographic Notes	28	(1)
2.7 Exercises	28	(3)
3 Expressing Knowledge	31	(18)
3.1 Knowledge Engineering	31	(1)
3.2 Vocabulary	32	(1)
3.3 Basic Facts	33	(1)
3.4 Complex Facts	34	(2)
3.5 Terminological Facts	36	(1)
3.6 Entailments	37	(4)
3.7 Abstract Individuals	41	(2)
3.8 Other Sorts of Facts	43	(1)
3.9 Bibliographic Notes	44	(1)
3.10 Exercises	45	(4)
4 Resolution	49	(36)
4.1 The Propositional Case	50	(5)
4.1.1 Resolution Derivations	52	(1)
4.1.2 An Entailment Procedure	53	(2)
4.2 Handling Variables and Quantifiers	55	(12)
4.2.1 First-Order Resolution	58	(3)
4.2.2 Answer Extraction	61	(3)
4.2.3 Skolemization	64	(1)
4.2.4 Equality	65	(2)
4.3 Dealing with Computational Intractability	67	(7)
4.3.1 The First-Order Case	67	(1)
4.3.2 The Herbrand Theorem	68	(1)
4.3.3 The Propositional Case	69	(1)
4.3.4 The Implications	70	(1)
4.3.5 SAT Solvers	70	(1)
4.3.6 Most General Unifiers	71	(1)
4.3.7 Other Refinements	72	(2)
4.4 Bibliographic Notes	74	(1)
4.5 Exercises	75	(10)
5 Reasoning with Horn Clauses	85	(14)
5.1 Horn Clauses	85	(1)
5.1.1 Resolution Derivations with Horn Clauses	86	(1)
5.2 SLD Resolution	87	(4)
5.2.1 Goal Trees	89	(2)
5.3 Computing SLD Derivations	91	(3)
5.3.1 Backward Chaining	91	(2)
5.3.2 Forward Chaining	93	(1)
5.3.3 The First-Order Case	94	(1)
5.4 Bibliographic Notes	94	(1)
5.5 Exercises	95	(4)
6 Procedural Control of Reasoning	99	(18)
6.1 Facts and Rules	100	(1)
6.2 Rule Formation and Search Strategy	101	(1)
6.3 Algorithm Design	102	(1)
6.4 Specifying Goal Order	103	(1)
6.5 Committing to Proof Methods	104	(2)
6.6 Controlling Backtracking	106	(2)
6.7 Negation as Failure	108	(2)
6.8 Dynamic Databases	110	(2)
6.8.1 The PLANNER Approach	111	(1)
6.9 Bibliographic Notes	112	(1)
6.10 Exercises	113	(4)
7 Rules in Production Systems	117	(18)
7.1 Production Systems: Basic Operation	118	(1)
7.2 Working Memory	119	(1)
7.3 Production Rules	120	(2)
7.4 A First Example	122	(3)
7.5 A Second Example	125	(1)
7.6 Conflict Resolution	126	(1)
7.7 Making Production Systems More Efficient	127	(2)
7.8 Applications and Advantages	129	(1)
7.9 Some Significant Production Rule Systems	130	(2)
7.10 Bibliographic Notes	132	(1)
7.11 Exercises	133	(2)
8 Object-Oriented Representation	135	(20)
8.1 Objects and Frames	135	(1)
8.2 A Basic Frame Formalism	136	(5)
8.2.1 Generic and Individual Frames	136	(2)
8.2.2 Inheritance	138	(2)
8.2.3 Reasoning with Frames	140	(1)
8.3 An Example: Using Frames to Plan a Trip	141	(8)
8.3.1 Using the Example Frames	146	(3)
8.4 Beyond the Basics	149	(3)
8.4.1 Other Uses of Frames	149	(1)
8.4.2 Extensions to the Frame Formalism	150	(1)
8.4.3 Object-Driven Programming with Frames	151	(1)
8.5 Bibliographic Notes	152	(1)
8.6 Exercises	153	(2)
9 Structured Descriptions	155	(32)
9.1 Descriptions	156	(2)
9.1.1 Noun Phrases	156	(1)
9.1.2 Concepts, Roles, and Constants	157	(1)
9.2 A Description Language	158	(2)
9.3 Meaning and Entailment	160	(3)
9.3.1 Interpretations	160	(1)
9.3.2 Truth in an Interpretation	161	(1)
9.3.3 Entailment	162	(1)
9.4 Computing Entailments	163	(8)
9.4.1 Simplifying the Knowledge Base	164	(1)
9.4.2 Normalization	165	(2)
9.4.3 Structure Matching	167	(1)
9.4.4 The Correctness of the Subsumption Computation	168	(1)
9.4.5 Computing Satisfaction	169	(2)
9.5 Taxonomies and Classification	171	(6)
9.5.1 A Taxonomy of Atomic Concepts and Constants	172	(1)
9.5.2 Computing Classification	173	(2)
9.5.3 Answering the Questions	175	(1)
9.5.4 Taxonomies versus Frame Hierarchies	175	(1)
9.5.5 Inheritance and Propagation	176	(1)
9.6 Beyond the Basics	177	(4)
9.6.1 Extensions to the Language	177	(2)
9.6.2 Applications of Description Logics	179	(2)
9.7 Bibliographic Notes	181	(1)
9.8 Exercises	182	(5)
10 Inheritance	187	(18)
10.1 Inheritance Networks	188	(1)
10.1.1 Strict Inheritance	189	(1)
10.1.2 Defeasible Inheritance	190	(2)
10.2 Strategies for Defeasible Inheritance	192	(1)
10.2.1 The Shortest Path Heuristic	192	(1)
10.2.2 Problems with Shortest Path	194	(1)
10.2.3 Inferential Distance	195	(1)
10.3 A Formal Account of Inheritance Networks	196	(1)
10.3.1 Extensions	199	(1)
10.3.2 Some Subtleties of Inheritance Reasoning	201	(1)
10.4 Bibliographic Notes	202	(1)
10.5 Exercises	203	(2)
11 Defaults	205	(32)
11.1 Introduction	205	(1)
11.1.1 Generics and Universals	206	(1)
11.1.2 Default Reasoning	207	(1)
11.1.3 Nonmonotonicity	209	(1)
11.2 Closed-World Reasoning	209	(1)
11.2.1 The Closed-World Assumption	210	(1)
11.2.2 Consistency and Completeness of Knowledge	211	(1)
11.2.3 Query Evaluation	211	(1)
11.2.4 Consistency and a Generalized Assumption	212	(1)
11.2.5 Quantifiers and Domain Closure	213	(2)
11.3 Circumscription	215	(1)
11.3.1 Minimal Entailment	216	(1)
11.3.2 The Circumscription Axiom	219	(1)
11.3.3 Fixed and Variable Predicates	219	(3)
11.4 Default Logic	222	(1)
11.4.1 Default Rules	222	(1)
11.4.2 Default Extensions	223	(1)
11.4.3 Multiple Extensions	224	(3)
11.5 Autoepistemic Logic	227	(1)
11.5.1 Stable Sets and Expansions	228	(1)
11.5.2 Enumerating Stable Expansions	230	(2)
11.6 Conclusion	232	(1)
11.7 Bibliographic Notes	233	(1)
11.8 Exercises	233	(4)
12 Vagueness, Uncertainty, and Degrees of Belief	237	(30)
12.1 Noncategorical Reasoning	238	(1)
12.2 Objective Probability	239	(1)
12.2.1 The Basic Postulates	240	(1)
12.2.2 Conditional Probability and Independence	241	(2)
12.3 Subjective Probability	243	(1)
12.3.1 From Statistics to Belief	244	(1)
12.3.2 A Basic Bayesian Approach	245	(1)
12.3.3 Belief Networks	246	(1)
12.3.4 An Example Network	247	(1)
12.3.5 Influence Diagrams	250	(1)
12.3.6 Dempster-Shafer Theory	251	(2)
12.4 Vagueness	253	(1)
12.4.1 Conjunction and Disjunction	255	(1)
12.4.2 Rules	255	(1)
12.4.3 A Bayesian Reconstruction	259	(3)
12.5 Bibliographic Notes	262	(1)
12.6 Exercises	263	(4)
13 Explanation and Diagnosis	267	(18)
13.1 Diagnosis	268	(1)
13.2 Explanation	269	(1)
13.2.1 Some Simplifications	270	(1)
13.2.2 Prime Implicates	271	(1)
13.2.3 Computing Explanations	272	(1)
13.3 A Circuit Example	273	(1)
13.3.1 Abductive Diagnosis	275	(1)
13.3.2 Consistency-Based Diagnosis	277	(2)
13.4 Beyond the Basics	279	(1)
13.4.1 Extensions	279	(1)
13.4.2 Other Applications	280	(1)
13.5 Bibliographic Notes	281	(1)
13.6 Exercises	282	(3)
14 Actions	285	(20)
14.1 The Situation Calculus	286	(1)
14.1.1 Fluents	286	(1)
14.1.2 Precondition and Effect Axioms	287	(1)
14.1.3 Frame Axioms	288	(1)
14.1.4 Using the Situation Calculus	289	(2)
14.2 A Simple Solution to the Frame Problem	291	(1)
14.2.1 Explanation Closure	292	(1)
14.2.2 Successor State Axioms	292	(1)
14.2.3 Summary	294	(1)
14.3 Complex Actions	295	(1)
14.3.1 The Do Formula	295	(1)
14.3.2 GoLoG	297	(1)
14.3.3 An Example	298	(1)
14.4 Bibliographic Notes	299	(2)
14.5 Exercises	301	(4)
15 Planning	305	(22)
15.1 Planning in the Situation Calculus	306	(1)
15.1.1 An Example	307	(1)
15.1.2 Using Resolution	308	(4)
15.2 The STRIPS Representation	312	(1)
15.2.1 Progressive Planning	314	(1)
15.2.2 Regressive Planning	315	(1)
15.3 Planning as a Reasoning Task	316	(1)
15.3.1 Avoiding Redundant Search	317	(1)
15.3.2 Application-Dependent Control	318	(2)
15.4 Beyond the Basics	320	(1)
15.4.1 Hierarchical Planning	320	(1)
15.4.2 Conditional Planning	321	(1)
15.4.3 "Even the Best-Laid Plans..."	322	(1)
15.5 Bibliographic Notes	322	(1)
15.6 Exercises	323	(4)
16 The Tradeoff between Expressiveness and Tractability	327	(22)
16.1 A Description Logic Case Study	329	(1)
16.1.1 Two Description Logic Languages	329	(1)
16.1.2 Computing Subsumption	330	(2)
16.2 Limited Languages	332	(2)
16.3 What Makes Reasoning Hard?	334	(2)
16.4 Vivid Knowledge	336	(1)
16.4.1 Analogues, Diagrams, Models	337	(2)
16.5 Beyond Vivid	339	(1)
16.5.1 Sets of Literals	339	(1)
16.5.2 Incorporating Definitions	340	(1)
16.5.3 Hybrid Reasoning	340	(2)
16.6 Bibliographic Notes	342	(1)
16.7 Exercises	343	(6)
Bibliography	349	(28)
Index	377