人工智能：复杂问题求解的结构和策略（英文版.第4版）

.2.5 epilogue and references 79
2.6 exercises 79
part ii (continued)
3 structures and strategies for state space search
3.0 introduction 81
3.1 graph theory 84
3.2 strategies for state space search 93
3.3 using the state space to represent reasoning with the predicate calculus
3.4 epilogue and references 121
3.5 exercises 121
4 heuristic search 123
4.0 introduction 123
4.1 an algorithm for heuristic search 127
4.2 admissibility, monotonicity, and informedness 139
4.3 using heuristics in games 144
4.4 complexity issues 152
4.5 epilogue and references 156
4.6 exercises 156
5 control and implementation of state space search
5.0 introduction 159
5.1 recursion-based search 160
5.2 pattern-directed search 164
5.3 production systems 171
5.4 the blackboard architecture for problem solving 187
5.5 epilogue and references 189
5.6 exercises 190
part iii
representation and intelligence:
the al challenge 193
6 knowledge representation 197
6.0 issues in knowledge representation 197
6.1 a brief history of ai representational systems 198
6.2 conceptual graphs: a network language 218
6.3 alternatives to explicit representation 228
6.4 agent based and distributed problem solving 235
6.5 epilogue and references 240
6.6 exercises 243
part iii (continued)
7 strong method problem solving 247
7.0 introduction 247
7.1 overview of expert system technology 249
7.2 rule-based expert systems 256
7.3 model-based, case based, and hybrid systems 268
7.4 planning 284
7.5 epilogue and references 299
7.6 exercises 301
8 reasoning in uncertain situations 303
8.0 introduction 303
8.1 logic-based abductive inference 305
8.2 abduction: alternatives to logic 320
8.3 the stochastic approach to uncertainty 333
8.4 epilogue and references 344
8.5 exercises 346
part iv
machine learning 349
9 machine learning: symbol-based 351
9.0 introduction 603
9.1 a framework for symbol-based learning 354
9.2 version space search 360
9.3 the id3 decision tree induction algorithm 372
9.4 inductive bias and learnability 381
9.5 knowledge and learning 386
9.6 unsupervised learning 397
9.7 reinforcement learning 406
9.8 epilogue and references 413
9.9 exercises 414
10 machine learning: connectionist 417
10.0 introduction 417
10.1 foundations for connectionist networks 419
10.2 perceptron learning 422
10.3 backpropagation learning 431
10.4 competitive learning 438
10.5 hebbian coincidence learning 446
10.6 attractor networks or "memories" 457
10.7 epilogue and references 467
10.8 exercises 468
part iv (continued)
11 machine learning: social and emergent 469
11.0 social and emergent models of learning 469
11.1 the genetic algorithm 471
11.2 classifier systems and genetic programming 481
11.3 artificial life and society-based learning 492
11.4 epilogue and references 503
11.5 exercises 504
partv
advanced topics for al problem solving 507
12 automated reasoning 509
12.0 introduction to weak methods in theorem proving 509
12.1 the general problem solver and difference tables 510
12.2 resohtiontheorem proving 516
12.3 prolog and automated reasoning 537
12.4 further issues in automated reasoning 543
12.5 epilogue and references 550
12.6 exercises 551
13 understanding natural language 553
13.0 role of knowledge in language understanding 553
13.1 deconstructing language: a symbolic analysis 556
13.2 syntax 559
13.3 syntax and knowledge with atn parsers 568
13.4 stochastic tools for language analysis 578
13.5 natural language applications 585
13.6 epilogue and references 592
13.7 exercises 557
part vi
languages and programming techniques
for artificial intelligence 597
14 an introduction to prolog 603
14.0 introduction 603
14.1 syntax for predicate calculus programming 604
14.2 abstract data types (adts) in prolog 616
14.3 a production system example in prolog 620
part vi: 14 an introduction to prolog (continued)
14.4 designing alternative search strategies 625
14.5 a prolog planner 630
14.6 prolog: meta-predicates, types, and unification 633
14.7 meta-interpreters in prolog 641
t4.8 learning algorithms in prolog 656
14.9 natural language processing in prolog 666
14.10 epilogue and references 673
14.11 exercises 676
15 an introduction to lisp 679
15.0 introduction 679
15.1 lisp: a brief overview 680
15.2 search in lisp: a functional approach to the farmer, wolf, goat,
and cabbage problem 702
15.3 higher-order functions and procedural abstraction 707
15.4 search strategies in lisp 711
15.5 pattern matching in lisp 715
15.6 a recursive unification function 717
15.7 interpreters and embedded languages 721
15.8 logic programming in lisp 723
15.9 streams and delayed evaluation 732
15.15 an expert system shell in lisp 736
15.11 semantic networks and inheritance in lisp 743
15.12 object-oriented programming using clos 747
15.13 learning in lisp: the id3 algorithm 759
15.14 epilogue and references 771
15.15 exercises 772
part vii
epilogue 777
16 artificial intelligence as empirical enquiry 779
16.0 introduction 779
16.1 artificial intelligence: a revised definition 781
16.2 the science of intelligent systems 792
16.3 al: current issues and future directions 803
16.4 epilogue and references 807
bibliography 809
author index 837
subject index 843

.　　 In creating this fourth edition, we considered all topics presented earlier and brought them into a modern perspective. In particular, we added a reinforcement learning section to Chapter 9. Algorithms for reinforcement learning, taking cues from an environment to establish a policy for state change, including temporal difference and Q-learning, are presented.
　　 Besides our previous analysis of data-driven and goal-driven rule-based systems,
　　 Chapter 7 now contains case-based and model-based reasoning, including examples from the NASA space program. The chapter includes a section on the strengths and weaknesses of each of these approaches to knowledge-intensive problem solving.
　　 Chapter 8 describes reasoning with uncertain or incomplete information. A number of important approaches to this problem are presented, including Bayesian reasoning, belief networks, the Dempster-Shafer model, and the Stanford certainty factor algebra. Techniques for truth maintenance in nonmonotonic situations are also presented, as well as reasoning with minimal models and logic-based abduction. We conclude the chapter with an in-depth presentation of Bayesian Belief Networks and the clique-tree algorithm for propagating confidences through a belief network in the context of new evidence.
　　 Chapter 13 presents issues in natural language understanding, including a section on stochastic models for language comprehension. The presentation includes Markov models, CART trees, mutual information clustering, and statistic-based parsing. The chapter closes with several examples, including the applications of text mining and text summarization techniques to the WWW.
　　 Finally, in a revised Chapter 16, we return to the deeper questions of the nature of intelligence and the possibility of intelligent machines. We comment on the A1 endeavour from the perspectives of philosophy, psychology, and neuro-physiology.
　　 The Contents
　　 Chapter I introduces artificial intelligence, beginning with a brief history of attempts to
　　understand mind and intelligence in philosophy, psychology, and other areas of research. In an important sense, Al is an old science, tracing its roots back at least to Aristotle. An appreciation of this background is essential for an understanding of the issues addressed in modern research. We also present an overview of some of the important application areas in Al. Our goal in Chapter I is to provide both background and a motivation for the theory and applications that follow.
　　 Chapters 2, 3, 4, and 5 (Part II) introduce the research tools for AI problem solving.These include the predicate calculus language to describe the essential features of a problem domain (Chapter 2), search to reason about these descriptions (Chapter 3) and the algorithms and data structures used to implement search. In Chapters 4 and 5, we discuss the essential role of heuristics in focusing and constraining search-based problem solving.We also present a number of architectures, including the blackboard and production system, for building these search algorithms.
　　 Chapters 6, 7, and 8 make up Part III of the book: representations for Al and knowl-edge-intensive problem solving. In Chapter 6 we present the evolving story of AI representational schemes. We begin with a discussion of semantic networks and extend this model to include conceptual dependency theory, frames, and scripts. We then present an in-depth examination of a particular formalism, conceptual graphs, emphasizing the epistemological issues involved in representing knowledge and showing how these issues are addressed in a modern representation language. In Chapter 13, we show how conceptual graphs can be used to implement a natural language database front end. We conclude
　　 Chapter 6 with more modern approaches to representation, including Copycat and agentoriented architectures.
　　 Chapter 7 presents the rule-based expert system along with case-based and modelbased reasoning systems, including examples from the NASA space program. These approaches to problem solving are presented as a natural evolution of the material in the first five chapters: using a production system of predicate calculus expressions to orchestrate a graph search. We end with an analysis of the strengths and weaknesses of each of these approaches to knowledge-intensive problem solving.
　　 Chapter 8 presents models for reasoning with uncertainty as well as the use of unreliable information. We discuss Bayesian models, belief networks, Dempster-Shafer, causal models, and the Stanford certainty algebra for reasoning in uncertain situations. Chapter 8 also contains algorithms for truth maintenance, reasoning with minimum models, logicbased abduction, and the clique-tree algorithm for Bayesian belief networks.
　　 Part IV, Chapters 9 through 11, offers an extensive presentation of issues in machine learning. In Chapter 9 we offer a detailed look at algorithms for symbol-based learning, a fruitful area of research spawning a number of different problems and solution approaches. These learning algorithms vary in their goals, the training data considered,their learning strategies, and the knowledge representations they employ. Symbol-based learning includes induction, concept learning, version-space search, and ID3. The role of inductive bias is considered, generalizations from patterns of data, as well as the effective use of knowledge to learn from a single example in explanation-based learning. Category learning, or conceptual clustering, is presented with unsupervised learning. Reinforcement learning, or the ability to integrate feedback from the environment into a policy for making new decisions concludes the chapter.
　　 In Chapter 10 we present neural networks, often referred to as sub-symbolic or connectionist models of learning. In a neural net, information is implicit in the organization and weights on a set of connected processors, and learning involves a re-arrangement and modification of the overall weighting of nodes and structure of the system. We present a number of connectionist architectures, including perceptron learning, backpropagation,and counterpropagation. We demonstrate Kohonen, Grossberg, and Hebbian network models. We present associative learning and attractor models, including Hopfield networks.
　　 Genetic algorithms and evolutionary approaches to learning are introduced in Chapter 11. On this viewpoint, learning is cast as an emerging and adaptive process. After several examples of problem solutions based on genetic algorithms, we introduce the application of genetic techniques to more general problem solvers. These include classifier systems and genetic programming. We then describe society-based learning with examples from artificial life, called a-life, research. We conclude the chapter with an example of emergent computation from research at the Santa Fe Institute. We compare and contrast the three approaches we present to machine learning (symbol-based, connectionist, social and emergent) in Chapter 16.Part V, Chapters 12 and 13, continues our presentation of important Al application areas. Theorem proving, often referred to as automated reasoning, is one of the oldest areas of AI research. In Chapter 12, we discuss the first programs in this area, including the Logic Theorist and the General Problem Solver. The primary focus of the chapter is binary resolution proof procedures, especially resolution refutations. More advanced inferencing with hyper-resolution and paramodulation is also presented. Finally, we describe the PROLOG interpreter as a Horn clause and resolution-based inferencing system, and see PROLOG computing to as an instance of the logic programming paradigm.
　　 Chapter 13 presents natural language understanding. Our traditional approach to language understanding, exemplified by many of the semantic structures presented in Chapter 6, is complemented with the stochastic approach. These include Markov models,CART trees, mutual information clustering, and statistics-based parsing. The chapter coneludes with examples applying these natural language techniques to database query systems and also to a text summarization system for use on the WWW.
　　 Part VI presents LISP and PROLOG. Chapter 14 covers PROLOG, and Chapter 15, LISR We demonstrate these languages as tools for AI problem solving by building the search and representation techniques of the earlier chapters, including breadth-, depth-,and best-first search algorithms. We implement these search techniques in a problem-inde-pendent fashion so that they may be extended to create shells for search in rule-based expert systems, to build semantic networks, natural language understanding systems, and learning applications.
　　 Finally, Chapter 16 serves as an epilogue for the book. It addresses the issue of the possibility of a science of intelligent systems, and considers contemporary challenges to AI; it discusses AI's current limitations, and projects its exciting future.Using This Book Artificial intelligence is a big field, and consequently, this is a big book. Although it would require more than a single semester to cover all of the material in the text, we have designed it so that a number of paths may be taken through the material. By selecting subsets of the material, we have used this text for single semester and full year (two semester) courses.
　　 We assume that most students will have had introductory courses in discrete mathematics, including predicate calculus and introductory graph theory. If this is not true, the instructor should spend more time on these concepts in the sections at the beginning of the text (2.1, 3.1). We also assume that students have had courses in data structures including trees, graphs, and recursion-based search, using stacks, queues, and priority queues. If they have not, then spend more time on the beginning sections of Chapters 3, 4, and 5.
　　 In a one semester course, we go quickly through the first two parts of the book. With this preparation, students are able to appreciate the material in Part III. We then consider the PROLOG and LISP in Part VI and require students to build many of the representation and search techniques of the first sections. Alternatively, one of the languages, PROLOG,for example, can be introduced early in the course and be used to test out the data structures and search techniques as they are encountered. We feel the recta-interpreters presented in the language chapters are very helpful for building rule-based and other knowledge-intensive problem solvers. PROLOG is an excellent tool for building natural language understanding systems.
　　 In a two-semester course, we are able to cover the application areas of Parts IV and V, especially the machine learning chapters, in appropriate detail. We also expect a much more detailed programming project from students. We think that it is very important in the second semester for students to revisit many of the primary sources in the AI literature. It is crucial for students to see both where we are, as well as how we got here, and to have an appreciation of the future promises of artificial intelligence. We use a collected set of readings for this purpose, Computation and Intelligence (Luger 1995).
　　 The algorithms of our book are described using a Pascal-like pseudo-code. This notation uses the control structures of Pascal along with English descriptions of the tests and operations. We have added two useful constructs to the Pascal control structures. The first is a modified case statement that, rather than comparing the value of a variable with constant case labels, as in standard Pascal, lets each item be labeled with an arbitrary boolean test. The case evaluates these tests in order until one of them is true and then performs the associated action; all other actions are ignored. Those familiar with LISP will note that this has the same semantics as the LISP cond statement.
　　 The other addition to the language is a return statement which takes one argument and can appear anywhere within a procedure or function. When the return is encountered,it causes the program to immediately exit the function, returning its argument as a result.Other than these modifications we used Pascal structure, with a reliance on the English descriptions, to make the algorithms clear.