Artificial Intelligence: A Modern Approach: Prentice Hall Series in Artificial Intelligence
Autor Stuart J. Russell, Peter Norvigen Limba Engleză Hardback – 31 oct 2009
Dr. Peter Norvig, contributing "Artificial Intelligence "author and Professor Sebastian Thrun, a Pearson author are offering a free online course at Stanford University on artificial intelligence.
According to an article in " The New York Times ," the course on artificial intelligence is one of three being offered experimentally by the Stanford computer science department to extend technology knowledge and skills beyond this elite campus to the entire world. One of the other two courses, an introduction to database software, is being taught by Pearson author Dr. Jennifer Widom.
"Artificial Intelligence: A Modern Approach, 3e" is available to purchase as an eText for your Kindle, NOOK, and the iPhone(r)/iPad(r).
"
To learn more about the course on artificial intelligence, visit http: //www.ai-class.com. To read the full "New York Times" article, click here.""
Preț: 1318.23 lei
Preț vechi: 1711.99 lei
-23% Nou
Puncte Express: 1977
Preț estimativ în valută:
252.29€ • 266.16$ • 210.25£
252.29€ • 266.16$ • 210.25£
Carte disponibilă
Livrare economică 12-26 decembrie
Preluare comenzi: 021 569.72.76
Specificații
ISBN-13: 9780136042594
ISBN-10: 0136042597
Pagini: 1132
Dimensiuni: 210 x 255 x 45 mm
Greutate: 2.17 kg
Ediția:Nouă
Editura: Prentice Hall
Seria Prentice Hall Series in Artificial Intelligence
Locul publicării:Upper Saddle River, United States
ISBN-10: 0136042597
Pagini: 1132
Dimensiuni: 210 x 255 x 45 mm
Greutate: 2.17 kg
Ediția:Nouă
Editura: Prentice Hall
Seria Prentice Hall Series in Artificial Intelligence
Locul publicării:Upper Saddle River, United States
Cuprins
I Artificial Intelligence
1 Introduction
1.1 What is AI? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Foundations of Artificial Intelligence . . . . . . . . . . . . . . . . . . 5
1.3 The History of Artificial Intelligence . . . . . . . . . . . . . . . . . . . . 16
1.4 The State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 29
2 Intelligent Agents
2.1 Agents and Environments . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Good Behavior: The Concept of Rationality . . . . . . . . . . . . . . . . 36
2.3 The Nature of Environments . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 The Structure of Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 59
II Problem-solving
3 Solving Problems by Searching
3.1 Problem-Solving Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2 Example Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3 Searching for Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4 Uninformed Search Strategies . . . . . . . . . . . . . . . . . . . . . . . . 81
3.5 Informed (Heuristic) Search Strategies . . . . . . . . . . . . . . . . . . . 92
3.6 Heuristic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 108
4 Beyond Classical Search
4.1 Local Search Algorithms and Optimization Problems . . . . . . . . . . . 120
4.2 Local Search in Continuous Spaces . . . . . . . . . . . . . . . . . . . . . 129
4.3 Searching with Nondeterministic Actions . . . . . . . . . . . . . . . . . . 133
4.4 Searching with Partial Observations . . . . . . . . . . . . . . . . . . . . . 138
4.5 Online Search Agents and Unknown Environments . . . . . . . . . . . . 147
4.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 153
5 Adversarial Search
5.1 Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.2 Optimal Decisions in Games . . . . . . . . . . . . . . . . . . . . . . . . 163
5.3 Alpha—Beta Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.4 Imperfect Real-Time Decisions . . . . . . . . . . . . . . . . . . . . . . . 171
5.5 Stochastic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.6 Partially Observable Games . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.7 State-of-the-Art Game Programs . . . . . . . . . . . . . . . . . . . . . . 185
5.8 Alternative Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.9 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 189
6 Constraint Satisfaction Problems
6.1 Defining Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . 202
6.2 Constraint Propagation: Inference in CSPs . . . . . . . . . . . . . . . . . 208
6.3 Backtracking Search for CSPs . . . . . . . . . . . . . . . . . . . . . . . . 214
6.4 Local Search for CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.5 The Structure of Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 222
6.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 227
III Knowledge, Reasoning, and Planning
7 Logical Agents
7.1 Knowledge-Based Agents . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.2 The Wumpus World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.3 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
7.4 Propositional Logic: A Very Simple Logic . . . . . . . . . . . . . . . . . 243
7.5 Propositional Theorem Proving . . . . . . . . . . . . . . . . . . . . . . . 249
7.6 Effective Propositional Model Checking . . . . . . . . . . . . . . . . . . 259
7.7 Agents Based on Propositional Logic . . . . . . . . . . . . . . . . . . . . 265
7.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 274
8 First-Order Logic
8.1 Representation Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8.2 Syntax and Semantics of First-Order Logic . . . . . . . . . . . . . . . . . 290
8.3 Using First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
8.4 Knowledge Engineering in First-Order Logic . . . . . . . . . . . . . . . . 307
8.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 313
9 Inference in First-Order Logic
9.1 Propositional vs. First-Order Inference . . . . . . . . . . . . . . . . . . . 322
9.2 Unification and Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
9.3 Forward Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
9.4 Backward Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
9.5 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
9.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 357
10 Classical Planning
10.1 Definition of Classical Planning . . . . . . . . . . . . . . . . . . . . . . . 366
10.2 Algorithms for Planning as State-Space Search . . . . . . . . . . . . . . . 373
10.3 Planning Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
10.4 Other Classical Planning Approaches . . . . . . . . . . . . . . . . . . . . 387
10.5 Analysis of Planning Approaches . . . . . . . . . . . . . . . . . . . . . . 392
10.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 393
11 Planning and Acting in the Real World
11.1 Time, Schedules, and Resources . . . . . . . . . . . . . . . . . . . . . . . 401
11.2 Hierarchical Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
11.3 Planning and Acting in Nondeterministic Domains . . . . . . . . . . . . . 415
11.4 Multiagent Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
11.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 430
12 Knowledge Representation
12.1 Ontological Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
12.2 Categories and Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
12.3 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
12.4 Mental Events and Mental Objects . . . . . . . . . . . . . . . . . . . . . 450
12.5 Reasoning Systems for Categories . . . . . . . . . . . . . . . . . . . . . 453
12.6 Reasoning with Default Information . . . . . . . . . . . . . . . . . . . . 458
12.7 The Internet Shopping World . . . . . . . . . . . . . . . . . . . . . . . . 462
12.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 467
IV Uncertain Knowledge and Reasoning
13 Quantifying Uncertainty
13.1 Acting under Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . 480
13.2 Basic Probability Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 483
13.3 Inference Using Full Joint Distributions . . . . . . . . . . . . . . . . . . . 490
13.4 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
13.5 Bayes’ Rule and Its Use . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
13.6 The Wumpus World Revisited . . . . . . . . . . . . . . . . . . . . . . . . 499
13.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 503
14 Probabilistic Reasoning
14.1 Representing Knowledge in an Uncertain Domain . . . . . . . . . . . . . 510
14.2 The Semantics of Bayesian Networks . . . . . . . . . . . . . . . . . . . . 513
14.3 Efficient Representation of Conditional Distributions . . . . . . . . . . . . 518
14.4 Exact Inference in Bayesian Networks . . . . . . . . . . . . . . . . . . . 522
14.5 Approximate Inference in Bayesian Networks . . . . . . . . . . . . . . . 530
14.6 Relational and First-Order Probability Models . . . . . . . . . . . . . . . 539
14.7 Other Approaches to Uncertain Reasoning . . . . . . . . . . . . . . . . . 546
14.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 551
15 Probabilistic Reasoning over Time
15.1 Time and Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
15.2 Inference in Temporal Models . . . . . . . . . . . . . . . . . . . . . . . . 570
15.3 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
15.4 Kalman Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
15.5 Dynamic Bayesian Networks . . . . . . . . . . . . . . . . . . . . . . . . 590
15.6 Keeping Track of Many Objects . . . . . . . . . . . . . . . . . . . . . . . 599
15.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 603
16 Making Simple Decisions
16.1 Combining Beliefs and Desires under Uncertainty . . . . . . . . . . . . . 610
16.2 The Basis of Utility Theory . . . . . . . . . . . . . . . . . . . . . . . . . 611
16.3 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
16.4 Multiattribute Utility Functions . . . . . . . . . . . . . . . . . . . . . . . 622
16.5 Decision Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
16.6 The Value of Information . . . . . . . . . . . . . . . . . . . . . . . . . . 628
16.7 Decision-Theoretic Expert Systems . . . . . . . . . . . . . . . . . . . . . 633
16.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 636
17 Making Complex Decisions
17.1 Sequential Decision Problems . . . . . . . . . . . . . . . . . . . . . . . . 645
17.2 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652
17.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
17.4 Partially Observable MDPs . . . . . . . . . . . . . . . . . . . . . . . . . 658
17.5 Decisions with Multiple Agents: Game Theory . . . . . . . . . . . . . . . 666
17.6 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
17.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 684
V Learning
18 Learning from Examples
18.1 Forms of Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
18.2 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695
18.3 Learning Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 697
18.4 Evaluating and Choosing the Best Hypothesis . . . . . . . . . . . . . . . 708
18.5 The Theory of Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 713
18.6 Regression and Classification with Linear Models . . . . . . . . . . . . . 717
18.7 Artificial Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . 727
18.8 Nonparametric Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
18.9 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . 744
18.10 Ensemble Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
18.11 Practical Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . 753
18.12 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 757
19 Knowledge in Learning
19.1 A Logical Formulation of Learning . . . . . . . . . . . . . . . . . . . . . 768
19.2 Knowledge in Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
19.3 Explanation-Based Learning . . . . . . . . . . . . . . . . . . . . . . . . 780
19.4 Learning Using Relevance Information . . . . . . . . . . . . . . . . . . . 784
19.5 Inductive Logic Programming . . . . . . . . . . . . . . . . . . . . . . . . 788
19.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 797
20 Learning Probabilistic Models
20.1 Statistical Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802
20.2 Learning with Complete Data . . . . . . . . . . . . . . . . . . . . . . . . 806
20.3 Learning with Hidden Variables: The EM Algorithm . . . . . . . . . . . . 816
20.4 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 825
21 Reinforcement Learning
21.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 830
21.2 Passive Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . 832
21.3 Active Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . 839
21.4 Generalization in Reinforcement Learning . . . . . . . . . . . . . . . . . 845
21.5 Policy Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848
21.6 Applications of Reinforcement Learning . . . . . . . . . . . . . . . . . . 850
21.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 853
VI Communicating, Perceiving, and Acting
22 Natural Language Processing
22.1 Language Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860
22.2 Text Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865
22.3 Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867
22.4 Information Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873
22.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 882
23 Natural Language for Communication
23.1 Phrase Structure Grammars . . . . . . . . . . . . . . . . . . . . . . . . . 888
23.2 Syntactic Analysis (Parsing) . . . . . . . . . . . . . . . . . . . . . . . . . 892
23.3 Augmented Grammars and Semantic Interpretation . . . . . . . . . . . . 897
23.4 Machine Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
23.5 Speech Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
23.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 918
24 Perception
24.1 Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 929
24.2 Early Image-Processing Operations . . . . . . . . . . . . . . . . . . . . . 935
24.3 Object Recognition by Appearance . . . . . . . . . . . . . . . . . . . . . 942
24.4 Reconstructing the 3D World . . . . . . . . . . . . . . . . . . . . . . . . 947
24.5 Object Recognition from Structural Information . . . . . . . . . . . . . . 957
24.6 Using Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
24.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 965
25 Robotics
25.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971
25.2 Robot Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973
25.3 Robotic Perception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 978
25.4 Planning to Move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986
25.5 Planning Uncertain Movements . . . . . . . . . . . . . . . . . . . . . . . 993
25.6 Moving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997
25.7 Robotic Software Architectures . . . . . . . . . . . . . . . . . . . . . . . 1003
25.8 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006
25.9 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 1010
VII Conclusions
26 Philosophical Foundations
26.1 Weak AI: Can Machines Act Intelligently? . . . . . . . . . . . . . . . . . 1020
26.2 Strong AI: Can Machines Really Think? . . . . . . . . . . . . . . . . . . 1026
26.3 The Ethics and Risks of Developing Artificial Intelligence . . . . . . . . . 1034
26.4 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 1040
27 AI: The Present and Future 1044
27.1 Agent Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044
27.2 Agent Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047
27.3 Are We Going in the Right Direction? . . . . . . . . . . . . . . . . . . . 1049
27.4 What If AI Does Succeed? . . . . . . . . . . . . . . . . . . . . . . . . . 1051
A Mathematical Background
A.1 Complexity Analysis and O() Notation . . . . . . . . . . . . . . . . . . . 1053
A.2 Vectors, Matrices, and Linear Algebra . . . . . . . . . . . . . . . . . . . 1055
A.3 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1057
B Notes on Languages and Algorithms
B.1 Defining Languages with Backus—Naur Form (BNF) . . . . . . . . . . . . 1060
B.2 Describing Algorithms with Pseudocode . . . . . . . . . . . . . . . . . . 1061
B.3 Online Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062
Bibliography 1063
Index 1095
1 Introduction
1.1 What is AI? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Foundations of Artificial Intelligence . . . . . . . . . . . . . . . . . . 5
1.3 The History of Artificial Intelligence . . . . . . . . . . . . . . . . . . . . 16
1.4 The State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 29
2 Intelligent Agents
2.1 Agents and Environments . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Good Behavior: The Concept of Rationality . . . . . . . . . . . . . . . . 36
2.3 The Nature of Environments . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 The Structure of Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 59
II Problem-solving
3 Solving Problems by Searching
3.1 Problem-Solving Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2 Example Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3 Searching for Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4 Uninformed Search Strategies . . . . . . . . . . . . . . . . . . . . . . . . 81
3.5 Informed (Heuristic) Search Strategies . . . . . . . . . . . . . . . . . . . 92
3.6 Heuristic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 108
4 Beyond Classical Search
4.1 Local Search Algorithms and Optimization Problems . . . . . . . . . . . 120
4.2 Local Search in Continuous Spaces . . . . . . . . . . . . . . . . . . . . . 129
4.3 Searching with Nondeterministic Actions . . . . . . . . . . . . . . . . . . 133
4.4 Searching with Partial Observations . . . . . . . . . . . . . . . . . . . . . 138
4.5 Online Search Agents and Unknown Environments . . . . . . . . . . . . 147
4.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 153
5 Adversarial Search
5.1 Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.2 Optimal Decisions in Games . . . . . . . . . . . . . . . . . . . . . . . . 163
5.3 Alpha—Beta Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.4 Imperfect Real-Time Decisions . . . . . . . . . . . . . . . . . . . . . . . 171
5.5 Stochastic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.6 Partially Observable Games . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.7 State-of-the-Art Game Programs . . . . . . . . . . . . . . . . . . . . . . 185
5.8 Alternative Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.9 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 189
6 Constraint Satisfaction Problems
6.1 Defining Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . 202
6.2 Constraint Propagation: Inference in CSPs . . . . . . . . . . . . . . . . . 208
6.3 Backtracking Search for CSPs . . . . . . . . . . . . . . . . . . . . . . . . 214
6.4 Local Search for CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.5 The Structure of Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 222
6.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 227
III Knowledge, Reasoning, and Planning
7 Logical Agents
7.1 Knowledge-Based Agents . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.2 The Wumpus World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.3 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
7.4 Propositional Logic: A Very Simple Logic . . . . . . . . . . . . . . . . . 243
7.5 Propositional Theorem Proving . . . . . . . . . . . . . . . . . . . . . . . 249
7.6 Effective Propositional Model Checking . . . . . . . . . . . . . . . . . . 259
7.7 Agents Based on Propositional Logic . . . . . . . . . . . . . . . . . . . . 265
7.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 274
8 First-Order Logic
8.1 Representation Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8.2 Syntax and Semantics of First-Order Logic . . . . . . . . . . . . . . . . . 290
8.3 Using First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
8.4 Knowledge Engineering in First-Order Logic . . . . . . . . . . . . . . . . 307
8.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 313
9 Inference in First-Order Logic
9.1 Propositional vs. First-Order Inference . . . . . . . . . . . . . . . . . . . 322
9.2 Unification and Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
9.3 Forward Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
9.4 Backward Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
9.5 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
9.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 357
10 Classical Planning
10.1 Definition of Classical Planning . . . . . . . . . . . . . . . . . . . . . . . 366
10.2 Algorithms for Planning as State-Space Search . . . . . . . . . . . . . . . 373
10.3 Planning Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
10.4 Other Classical Planning Approaches . . . . . . . . . . . . . . . . . . . . 387
10.5 Analysis of Planning Approaches . . . . . . . . . . . . . . . . . . . . . . 392
10.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 393
11 Planning and Acting in the Real World
11.1 Time, Schedules, and Resources . . . . . . . . . . . . . . . . . . . . . . . 401
11.2 Hierarchical Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
11.3 Planning and Acting in Nondeterministic Domains . . . . . . . . . . . . . 415
11.4 Multiagent Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
11.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 430
12 Knowledge Representation
12.1 Ontological Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
12.2 Categories and Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
12.3 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
12.4 Mental Events and Mental Objects . . . . . . . . . . . . . . . . . . . . . 450
12.5 Reasoning Systems for Categories . . . . . . . . . . . . . . . . . . . . . 453
12.6 Reasoning with Default Information . . . . . . . . . . . . . . . . . . . . 458
12.7 The Internet Shopping World . . . . . . . . . . . . . . . . . . . . . . . . 462
12.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 467
IV Uncertain Knowledge and Reasoning
13 Quantifying Uncertainty
13.1 Acting under Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . 480
13.2 Basic Probability Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 483
13.3 Inference Using Full Joint Distributions . . . . . . . . . . . . . . . . . . . 490
13.4 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
13.5 Bayes’ Rule and Its Use . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
13.6 The Wumpus World Revisited . . . . . . . . . . . . . . . . . . . . . . . . 499
13.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 503
14 Probabilistic Reasoning
14.1 Representing Knowledge in an Uncertain Domain . . . . . . . . . . . . . 510
14.2 The Semantics of Bayesian Networks . . . . . . . . . . . . . . . . . . . . 513
14.3 Efficient Representation of Conditional Distributions . . . . . . . . . . . . 518
14.4 Exact Inference in Bayesian Networks . . . . . . . . . . . . . . . . . . . 522
14.5 Approximate Inference in Bayesian Networks . . . . . . . . . . . . . . . 530
14.6 Relational and First-Order Probability Models . . . . . . . . . . . . . . . 539
14.7 Other Approaches to Uncertain Reasoning . . . . . . . . . . . . . . . . . 546
14.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 551
15 Probabilistic Reasoning over Time
15.1 Time and Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
15.2 Inference in Temporal Models . . . . . . . . . . . . . . . . . . . . . . . . 570
15.3 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
15.4 Kalman Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
15.5 Dynamic Bayesian Networks . . . . . . . . . . . . . . . . . . . . . . . . 590
15.6 Keeping Track of Many Objects . . . . . . . . . . . . . . . . . . . . . . . 599
15.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 603
16 Making Simple Decisions
16.1 Combining Beliefs and Desires under Uncertainty . . . . . . . . . . . . . 610
16.2 The Basis of Utility Theory . . . . . . . . . . . . . . . . . . . . . . . . . 611
16.3 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
16.4 Multiattribute Utility Functions . . . . . . . . . . . . . . . . . . . . . . . 622
16.5 Decision Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
16.6 The Value of Information . . . . . . . . . . . . . . . . . . . . . . . . . . 628
16.7 Decision-Theoretic Expert Systems . . . . . . . . . . . . . . . . . . . . . 633
16.8 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 636
17 Making Complex Decisions
17.1 Sequential Decision Problems . . . . . . . . . . . . . . . . . . . . . . . . 645
17.2 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652
17.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
17.4 Partially Observable MDPs . . . . . . . . . . . . . . . . . . . . . . . . . 658
17.5 Decisions with Multiple Agents: Game Theory . . . . . . . . . . . . . . . 666
17.6 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
17.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 684
V Learning
18 Learning from Examples
18.1 Forms of Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
18.2 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695
18.3 Learning Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 697
18.4 Evaluating and Choosing the Best Hypothesis . . . . . . . . . . . . . . . 708
18.5 The Theory of Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 713
18.6 Regression and Classification with Linear Models . . . . . . . . . . . . . 717
18.7 Artificial Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . 727
18.8 Nonparametric Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
18.9 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . 744
18.10 Ensemble Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
18.11 Practical Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . 753
18.12 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 757
19 Knowledge in Learning
19.1 A Logical Formulation of Learning . . . . . . . . . . . . . . . . . . . . . 768
19.2 Knowledge in Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
19.3 Explanation-Based Learning . . . . . . . . . . . . . . . . . . . . . . . . 780
19.4 Learning Using Relevance Information . . . . . . . . . . . . . . . . . . . 784
19.5 Inductive Logic Programming . . . . . . . . . . . . . . . . . . . . . . . . 788
19.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 797
20 Learning Probabilistic Models
20.1 Statistical Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802
20.2 Learning with Complete Data . . . . . . . . . . . . . . . . . . . . . . . . 806
20.3 Learning with Hidden Variables: The EM Algorithm . . . . . . . . . . . . 816
20.4 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 825
21 Reinforcement Learning
21.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 830
21.2 Passive Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . 832
21.3 Active Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . 839
21.4 Generalization in Reinforcement Learning . . . . . . . . . . . . . . . . . 845
21.5 Policy Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848
21.6 Applications of Reinforcement Learning . . . . . . . . . . . . . . . . . . 850
21.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 853
VI Communicating, Perceiving, and Acting
22 Natural Language Processing
22.1 Language Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860
22.2 Text Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865
22.3 Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867
22.4 Information Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873
22.5 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 882
23 Natural Language for Communication
23.1 Phrase Structure Grammars . . . . . . . . . . . . . . . . . . . . . . . . . 888
23.2 Syntactic Analysis (Parsing) . . . . . . . . . . . . . . . . . . . . . . . . . 892
23.3 Augmented Grammars and Semantic Interpretation . . . . . . . . . . . . 897
23.4 Machine Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
23.5 Speech Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
23.6 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 918
24 Perception
24.1 Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 929
24.2 Early Image-Processing Operations . . . . . . . . . . . . . . . . . . . . . 935
24.3 Object Recognition by Appearance . . . . . . . . . . . . . . . . . . . . . 942
24.4 Reconstructing the 3D World . . . . . . . . . . . . . . . . . . . . . . . . 947
24.5 Object Recognition from Structural Information . . . . . . . . . . . . . . 957
24.6 Using Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
24.7 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 965
25 Robotics
25.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971
25.2 Robot Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973
25.3 Robotic Perception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 978
25.4 Planning to Move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986
25.5 Planning Uncertain Movements . . . . . . . . . . . . . . . . . . . . . . . 993
25.6 Moving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997
25.7 Robotic Software Architectures . . . . . . . . . . . . . . . . . . . . . . . 1003
25.8 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006
25.9 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 1010
VII Conclusions
26 Philosophical Foundations
26.1 Weak AI: Can Machines Act Intelligently? . . . . . . . . . . . . . . . . . 1020
26.2 Strong AI: Can Machines Really Think? . . . . . . . . . . . . . . . . . . 1026
26.3 The Ethics and Risks of Developing Artificial Intelligence . . . . . . . . . 1034
26.4 Summary, Bibliographical and Historical Notes, Exercises . . . . . . . . . 1040
27 AI: The Present and Future 1044
27.1 Agent Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044
27.2 Agent Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047
27.3 Are We Going in the Right Direction? . . . . . . . . . . . . . . . . . . . 1049
27.4 What If AI Does Succeed? . . . . . . . . . . . . . . . . . . . . . . . . . 1051
A Mathematical Background
A.1 Complexity Analysis and O() Notation . . . . . . . . . . . . . . . . . . . 1053
A.2 Vectors, Matrices, and Linear Algebra . . . . . . . . . . . . . . . . . . . 1055
A.3 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1057
B Notes on Languages and Algorithms
B.1 Defining Languages with Backus—Naur Form (BNF) . . . . . . . . . . . . 1060
B.2 Describing Algorithms with Pseudocode . . . . . . . . . . . . . . . . . . 1061
B.3 Online Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062
Bibliography 1063
Index 1095
Notă biografică
Stuart Russell was born in 1962 in Portsmouth, England. He received his B.A. with first-class honours in physics from Oxford University in 1982, and his Ph.D. in computer science from Stanford in 1986. He then joined the faculty of the University of California at Berkeley, where he is a professor of computer science, director of the Center for Intelligent Systems, and holder of the Smith–Zadeh Chair in Engineering. In 1990, he received the Presidential Young Investigator Award of the National Science Foundation, and in 1995 he was cowinner of the Computers and Thought Award. He was a 1996 Miller Professor of the University of California and was appointed to a Chancellor’s Professorship in 2000. In 1998, he gave the Forsythe Memorial Lectures at Stanford University. He is a Fellow and former Executive Council member of the American Association for Artificial Intelligence. He has published over 100 papers on a wide range of topics in artificial intelligence. His other books include The Use of Knowledge in Analogy and Induction and (with Eric Wefald) Do the Right Thing: Studies in Limited Rationality.
Peter Norvig is currently Director of Research at Google, Inc., and was the director responsible for the core Web search algorithms from 2002 to 2005. He is a Fellow of the American Association for Artificial Intelligence and the Association for Computing Machinery. Previously, he was head of the Computational Sciences Division at NASA Ames Research Center, where he oversaw NASA’s research and development in artificial intelligence and robotics, and chief scientist at Junglee, where he helped develop one of the first Internet information extraction services. He received a B.S. in applied mathematics from Brown University and a Ph.D. in computer science from the University of California at Berkeley. He received the Distinguished Alumni and Engineering Innovation awards from Berkeley and the Exceptional Achievement Medal from NASA. He has been a professor at the University of Southern California and a research faculty member at Berkeley. His other books are Paradigms of AI Programming: Case Studies in Common Lisp and Verbmobil: A Translation System for Faceto-Face Dialog and Intelligent Help Systems for UNIX.
Peter Norvig is currently Director of Research at Google, Inc., and was the director responsible for the core Web search algorithms from 2002 to 2005. He is a Fellow of the American Association for Artificial Intelligence and the Association for Computing Machinery. Previously, he was head of the Computational Sciences Division at NASA Ames Research Center, where he oversaw NASA’s research and development in artificial intelligence and robotics, and chief scientist at Junglee, where he helped develop one of the first Internet information extraction services. He received a B.S. in applied mathematics from Brown University and a Ph.D. in computer science from the University of California at Berkeley. He received the Distinguished Alumni and Engineering Innovation awards from Berkeley and the Exceptional Achievement Medal from NASA. He has been a professor at the University of Southern California and a research faculty member at Berkeley. His other books are Paradigms of AI Programming: Case Studies in Common Lisp and Verbmobil: A Translation System for Faceto-Face Dialog and Intelligent Help Systems for UNIX.
Caracteristici
- Nontechnical learning material.
- Provides a simple overview of major concepts, uses a nontechnical language to help increase understanding. Makes the book accessible to a broader range of students.
- Provides a simple overview of major concepts, uses a nontechnical language to help increase understanding. Makes the book accessible to a broader range of students.
- The Internet as a sample application for intelligent systems — Examples of logical reasoning, planning, and natural language processing using Internet agents.
- Promotes student interest with interesting, relevant exercises.
- Promotes student interest with interesting, relevant exercises.
- Increased coverage of material — New or expanded coverage of constraint satisfaction, local search planning methods, multi-agent systems, game theory, statistical natural language processing and uncertain reasoning over time. More detailed descriptions of algorithms for probabilistic inference, fast propositional inference, probabilistic learning approaches including EM, and other topics.
- Brings students up to date on the latest technologies, and presents concepts in a more unified manner.
- Brings students up to date on the latest technologies, and presents concepts in a more unified manner.
- Updated and expanded exercises — 30% of the exercises are revised or NEW.
- More Online Software.
- Allows many more opportunities for student projects on the web.
- Allows many more opportunities for student projects on the web.
- A unified, agent-based approach to AI — Organizes the material around the task of building intelligent agents.
- Shows students how the various subfields of AI fit together to build actual, useful programs.
- Shows students how the various subfields of AI fit together to build actual, useful programs.
- Comprehensive, up-to-date coverage — Includes a unified view of the field organized around the rational decision making paradigm.
- A flexible format.
- Makes the text adaptable for varying instructors' preferences.
- Makes the text adaptable for varying instructors' preferences.
- In-depth coverage of basic and advanced topics.
- Provides students with a basic understanding of the frontiers of AI without compromising complexity and depth.
- Provides students with a basic understanding of the frontiers of AI without compromising complexity and depth.
- Pseudo-code versions of the major AI algorithms are presented in a uniform fashion, and Actual Common Lisp and Python implementations of the presented algorithms are available via the Internet.
- Gives instructors and students a choice of projects; reading and running the code increases understanding.
- Gives instructors and students a choice of projects; reading and running the code increases understanding.
- Author Maintained Website
- Visit http://aima.cs.berkeley.edu/ to access text-related Comments and Discussions, AI Resources on the Web, and Online Code Repository, Instructor Resources, and more!
- Visit http://aima.cs.berkeley.edu/ to access text-related Comments and Discussions, AI Resources on the Web, and Online Code Repository, Instructor Resources, and more!
Caracteristici noi
This edition captures the changes in AI that have taken place since the last edition in 2003. There have been important applications of AI technology, such as the widespread deployment of practical speech recognition, machine translation, autonomous vehicles, and household robotics. There have been algorithmic landmarks, such as the solution of the game of checkers. And there has been a great deal of theoretical progress, particularly in areas such as probabilistic reasoning, machine learning, and computer vision. Most important from the authors' point of view is the continued evolution in how we think about the field, and thus how the book is organized. The major changes are as follows:
- More emphasis is placed on partially observable and nondeterministic environments, especially in the nonprobabilistic settings of search and planning. The concepts of belief state (a set of possible worlds) and state estimation (maintaining the belief state) are introduced in these settings; later in the book, probabilities are added.
- In addition to discussing the types of environments and types of agents, there is more in more depth coverage of the types of representations that an agent can use. Differences between atomic representations (in which each state of the world is treated as a black box), factored representations (in which a state is a set of attribute/value pairs), and structured representations (in which the world consists of objects and relations between them) are distinguished.
- Coverage of planning goes into more depth on contingent planning in partially observable environments and includes a new approach to hierarchical planning.
- New material on first-order probabilistic models is added, including open-universe models for cases where there is uncertainty as to what objects exist.
- The introductory machine-learning chapter is completely rewritten, stressing a wider variety of more modern learning algorithms and placing them on a firmer theoretical footing.
- Expanded coverage of Web search and information extraction, and of techniques for learning from very large data sets.
- 20% of the citations in this edition are to works published after 2003.
- Approximately 20% of the material is brand new. The remaining 80% reflects older work but is largely rewritten to present a more unified picture of the field.
Descriere
For one or two-semester, undergraduate or graduate-level courses in Artificial Intelligence.
The long-anticipated revision of this best-selling text offers the most comprehensive, up-to-date introduction to the theory and practice of artificial intelligence.
View chapters 3 and 4 from the Third Edition.
The long-anticipated revision of this best-selling text offers the most comprehensive, up-to-date introduction to the theory and practice of artificial intelligence.
View chapters 3 and 4 from the Third Edition.