Artificial intelligence : a modern approach

Artificial Intelligence: A Modern Approach, 3e offers the most comprehensive, up-to-date introduction to the theory and practice of artificial intelligence. Number one in its field, this textbook is ideal for one or two-semester, undergraduate or graduate-level courses in Artificial Intelligence. 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 KindleTM, NOOKTM, and the iPhone®/iPad®. 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. From The Publisher: The Long-anticipated Revision Of This Number 1 Selling Book Offers The Most Comprehensive, State Of The Art Introduction To The Theory And Practice Of Artificial Intelligence For Modern Applications. Intelligent Agents. Solving Problems By Searching. Informed Search Methods. Game Playing. Agents That Reason Logically. First-order Logic. Building A Knowledge Base. Inference In First-order Logic. Logical Reasoning Systems. Practical Planning. Planning And Acting. Uncertainty. Probabilistic Reasoning Systems. Making Simple Decisions. Making Complex Decisions. Learning From Observations. Learning With Neural Networks. Reinforcement Learning. Knowledge In Learning. Agents That Communicate. Practical Communication In English. Perception. Robotics. For Computer Professionals, Linguists, And Cognitive Scientists Interested In Artificial Intelligence. 1: Artificial Intelligence -- 1: Introduction -- 1-1: What Is Ai? -- 1-2: Foundations Of Artificial Intelligence -- 1-3: History Of Artificial Intelligence -- 1-4: State Of The Art -- 1-5: Summary, Bibliographical And Historical Notes, Exercises -- 2: Intelligent Agents -- 2-1: Agents And Environments -- 2-2: Good Behavior: The Concepts Of Rationality -- 2-3: Nature Of Environments -- 2-4: Structure Of Agents -- 2-5: Summary, Bibliographical And Historical Notes, Exercises -- 2: Problem-solving -- 3: Solving Problems By Searching -- 3-1: Problem-solving Agents -- 3-2: Example Problems -- 3-3: Searching For Solutions -- 3-4: Uninformed Search Strategies -- 3-5: Informed (heuristic) Search Strategies -- 3-6: Heuristic Functions -- 3-7: Summary, Bibliographical And Historical Notes, Exercises -- 4: Beyond Classical Search -- 4-1: Local Search Algorithms And Optimization Problems -- 4-2: Local Search In Continuous Spaces -- 4-3: Searching With Nondeterministic Actions --^ 4-4: Searching With Partial Observations -- 4-5: Online Search Agents And Unknown Environments -- 4-6: Summary, Bibliographical And Historical Notes, Exercises -- 5: Adversarial Search -- 5-1: Games -- 5-2: Optimal Decisions In Games -- 5-3: Alpha-beta Pruning -- 5-4: Imperfect Real-time Decisions -- 5-5: Stochastic Games -- 5-6: Partially Observable Games -- 5-7: State-of-the-art Game Programs -- 5-8: Alternative Approaches -- 5-9: Summary, Bibliographical And Historical Notes, Exercises -- 6: Constraint Satisfaction Problems -- 6-1: Defining Constraint Satisfaction Problems -- 6-2: Constraint Propagation: Inference In Csps -- 6-3: Backtracking Search For Csps -- 6-4: Local Search For Csps -- 6-5: Structure Of Problems -- 6-6: Summary, Bibliographical And Historical Notes, Exercises -- 3: Knowledge. Reasoning And Planning -- 7: Logical Agents -- 7-1: Knowledge-based Agents -- 7-2: Wumpus World -- 7-3: Logic -- 7-4: Propositional Logic: A Very Simple Logic --^ 7-5: Propositional Theorem Proving -- 7-6: Effective Propositional Model Checking -- 7-7: Agents Based On Propositional Logic -- 7-8: Summary, Bibliographical And Historical Notes, Exercises -- 8: First-order Logic -- 8-1: Representation Revisited -- 8-2: Syntax And Semantics Of First-order Logic -- 8-3: Using First-order Logic -- 8-4: Knowledge Engineering In First-order Logic -- 8-5: Summary, Bibliographical And Historical Notes, Exercises -- 9: Inference In First-order Logic -- 9-1: Propositional Vs First-order Inference -- 9-2: Unification And Lifting -- 9-3: Forward Chaining -- 9-4: Backward Chaining -- 9-5: Resolution -- 9-6: Summary , Bibliographical And Historical Notes, Exercises -- 10: Classical Planning -- 10-1: Definition Of Classical Planning -- 10-2: Algorithms For Planning As State-space Search -- 10-3: Planning Graphs -- 10-4: Other Classical Planning Approaches -- 10-5: Analysis Of Planning Approaches --^ 10-6: Summary, Bibliographical And Historical Notes, Exercises -- 11: Planning And Acting In The Real World -- 11-1: Time, Schedules, And Resources -- 11-2: Hierarchical Planning -- 11-3: Planning And Acting In Nondeterministic Domains -- 11-4: Multiagent Planning -- 11-5: Summary, Bibliographical And Historical Notes, Exercises -- 12: Knowledge Representation -- 12-1: Ontological Engineering -- 12-2: Categories And Objects -- 12-3: Events -- 12-4: Mental Events And Mental Objects -- 12-5: Reasoning Systems For Categories -- 12-6: Reasoning With Default Information -- 12-7: Internet Shopping World -- 12-8: Summary, Bibliographical And Historical Notes, Exercises -- 4: Uncertain Knowledge And Reasoning -- 13: Quantifying Uncertainty -- 13-1: Acting Under Uncertainty -- 13-2: Basic Probability Notation -- 13-3: Inference Using Full Joint Distributions -- 13-4: Independence -- 13-5: Bayes' Rule And Its Use -- 13-6: Wumpus World Revisited --^ 13-7: Summary, Bibliographical And Historical Notes, Exercises -- 14: Probabilistic Reasoning -- 14-1: Representing Knowledge In An Uncertain Domain -- 14-2: Semantics Of Bayesian Networks -- 14-3: Efficient Representation Of Conditional Distributions -- 14-4: Exact Inference In Bayesian Networks -- 14-5: Approximate Inference In Bayesian Networks -- 14-6: Relational And First-order Probability Models -- 14-7: Other Approaches To Uncertain Reasoning -- 14-8: Summary, Bibliographical And Historical Notes, Exercises -- 15: Probabilistic Reasoning Over Time -- 15-1: Time And Uncertainty -- 15-2: Inference In Temporal Models -- 15-3: Hidden Markov Models -- 15-4: Kalman Filters -- 15-5: Dynamic Bayesian Networks -- 15-6: Keeping Track Of Many Objects -- 15-7: Summary, Bibliographical And Historical Notes, Exercises -- 16: Making Simple Decisions -- 16-1: Combining Beliefs And Desires Under Uncertainty -- 16-2: Basis Of Utility Theory -- 16-3: Utility Functions --^ 16-4: Multiattribute Utility Functions -- 16-5: Decision Networks -- 16-6: Value Of Information -- 16-7: Decision-theoretic Expert Systems -- 16-8: Summary, Bibliographical And Historical Notes, Exercises -- 17: Making Complex Decisions -- 17-1: Sequential Decision Problems -- 17-2: Value Iteration -- 17-3: Policy Iteration -- 17-4: Partially Observable Mdps -- 17-5: Decisions With Multiple Agents: Game Theory -- 17-6: Mechanism Design -- 17-7: Summary, Bibliographical And Historical Notes, Exercises -- Learning -- 18: Learning From Examples -- 18-1: Forms Of Learning -- 18-2: Supervised Learning -- 18-3: Learning Decision Trees -- 18-4: Evaluating And Choosing The Best Hypothesis -- 18-5: Theory Of Learning -- 18-6: Regression And Classification With Linear Models -- 18-7: Artificial Neural Networks -- 18-8: Nonparametric Models -- 18-9: Support Vector Machines -- 18-10: Ensemble Learning -- 18-11: Practical Machine Learning -- 18-12: Summary, Bibliographical And Historical Notes, Exercises -- 19: Knowledge In Learning -- 19-1: Logical Formulation Of Learning -- 19-2: Knowledge In Learning -- 19-3: Explanation-based Learning -- 19-4: Learning Using Relevance Information -- 19-5: Inductive Logic Programming -- 19-6: Summary, Bibliographical And Historical Notes, Exercises -- 20: Learning Probabilistic Models -- 20-1: Statistical Learning -- 20-2: Learning With Complete Data -- 20-3: Learning With Hidden Variables: The Em Algorithm --^ 20-4: Summary, Bibliographical And Historical Notes, Exercises -- 21: Reinforcement Learning -- 21-1: Introduction -- 21-2: Passive Reinforcement Learning -- 21-3: Active Reinforcement Learning -- 21-4: Generalization In Reinforcement Learning -- 21-5: Policy Search -- 21-6: Applications Of Reinforcement Learning -- 21-7: Summary, Bibliographical And Historical Notes, Exercises -- 6: Communicating, Perceiving, And Acting -- 22: Natural Language Processing -- 22-1: Language Models -- 22-2: Text Classification -- 22-3: Information Retrieval -- 22-4: Information Extraction -- 22-5: Summary, Bibliographical And Historical Notes, Exercises -- 23: Natural Language For Communication -- 23-1: Phrase Structure Grammars -- 23-2: Syntactic Analysis (parsing) -- 23-3: Augmented Grammars And Semantic Interpretation -- 23-4: Machine Translation -- 23-5: Speech Recognition -- 23-6: Summary, Bibliographical And Historical Notes, Exercises -- 24: Perception -- 24-1: Image Formation --^ 24-2: Early Image-processing Operations -- 24-3: Object Recognition By Appearance -- 24-4: Reconstructing The 3d World -- 24-5: Object Recognition Form Structural Information -- 24-6: Using Vision -- 24-7: Summary, Bibliographical And Historical Notes, Exercises -- 25: Robotics -- 25-1: Introduction -- 25-2: Robot Hardware -- 25-3: Robotic Perception -- 25-4: Planning To Move -- 25-5: Planning Uncertain Movements -- 25-6: Moving -- 25-7: Robotic Software Architectures -- 25-8: Application Domains -- 25-9: Summary, Bibliographical And Historical Notes, Exercises -- 7: Conclusions -- 26: Philosophical Foundations -- 26-1: Weak Ai: Can Machines Act Intelligently? -- 26-2: Strong Ai: Can Machines Really Think? -- 26-3: Ethics And Risks Of Developing Artificial Intelligence -- 26-4: Summary, Bibliographical And Historical Notes, Exercises -- 27: Ai: Present And Future -- 27-1: Agent Components -- 27-2: Agent Architectures -- 27-3: Are We Going In The Right Direction? --^ 27-4: What If Ai Does Succeed? -- A: Mathematical Background -- A-1: Complexity Analysis And O() Notation -- A-2: Vectors, Matrices, And Linear Algebra -- A-3: Probability Distributions -- B: Notes On Languages And Algorithms --b-1: Defining Languages With Backus-naur Form (bnf) -- B-2: Describing Algorithms With Pseudocode -- B-3: Online Help -- Bibliography -- Index. Stuart J. Russell And Peter Norvig ; Contributing Writers, Ernest Davis ... [et Al.]. Includes Bibliographical References (p. 1063-1093) And Index. Cover......Page 1 Title Page......Page 5 Copyright......Page 6 Preface......Page 9 About the Authors......Page 14 Contents......Page 15 1.1 What Is AI?......Page 21 1.2 The Foundations of Artificial Intelligence......Page 25 1.3 The History of Artificial Intelligence......Page 36 1.4 The State of the Art......Page 48 1.5 Summary, Bibliographical and Historical Notes, Exercises......Page 49 2.1 Agents and Environments......Page 54 2.2 Good Behavior: The Concept of Rationality......Page 56 2.3 The Nature of Environments......Page 60 2.4 The Structure of Agents......Page 66 2.5 Summary, Bibliographical and Historical Notes, Exercises......Page 79 3.1 Problem-Solving Agents......Page 84 3.2 Example Problems......Page 89 3.3 Searching for Solutions......Page 95 3.4 Uninformed Search Strategies......Page 101 3.5 Informed (Heuristic) Search Strategies......Page 112 3.6 Heuristic Functions......Page 122 3.7 Summary, Bibliographical and Historical Notes, Exercises......Page 128 4.1 Local Search Algorithms and Optimization Problems......Page 140 4.2 Local Search in Continuous Spaces......Page 149 4.3 Searching with Nondeterministic Actions......Page 153 4.4 Searching with Partial Observations......Page 158 4.5 Online Search Agents and Unknown Environments......Page 167 4.6 Summary, Bibliographical and Historical Notes, Exercises......Page 173 5.1 Games......Page 181 5.2 Optimal Decisions in Games......Page 183 5.3 Alpha–Beta Pruning......Page 187 5.4 Imperfect Real-Time Decisions......Page 191 5.5 Stochastic Games......Page 197 5.6 Partially Observable Games......Page 200 5.7 State-of-the-Art Game Programs......Page 205 5.8 Alternative Approaches......Page 207 5.9 Summary, Bibliographical and Historical Notes, Exercises......Page 209 6.1 Defining Constraint Satisfaction Problems......Page 222 6.2 Constraint Propagation: Inference in CSPs......Page 228 6.3 Backtracking Search for CSPs......Page 234 6.4 Local Search for CSPs......Page 240 6.5 The Structure of Problems......Page 242 6.6 Summary, Bibliographical and Historical Notes, Exercises......Page 247 7 Logical Agents......Page 254 7.1 Knowledge-Based Agents......Page 255 7.2 The Wumpus World......Page 256 7.3 Logic......Page 260 7.4 Propositional Logic: A Very Simple Logic......Page 263 7.5 Propositional Theorem Proving......Page 269 7.6 Effective Propositional Model Checking......Page 279 7.7 Agents Based on Propositional Logic......Page 285 7.8 Summary, Bibliographical and Historical Notes, Exercises......Page 294 8.1 Representation Revisited......Page 305 8.2 Syntax and Semantics of First-Order Logic......Page 310 8.3 Using First-Order Logic......Page 320 8.4 Knowledge Engineering in First-Order Logic......Page 327 8.5 Summary, Bibliographical and Historical Notes, Exercises......Page 333 9.1 Propositional vs. First-Order Inference......Page 342 9.2 Unification and Lifting......Page 345 9.3 Forward Chaining......Page 350 9.4 Backward Chaining......Page 357 9.5 Resolution......Page 365 9.6 Summary, Bibliographical and Historical Notes, Exercises......Page 377 10.1 Definition of Classical Planning......Page 386 10.2 Algorithms for Planning as State-Space Search......Page 393 10.3 Planning Graphs......Page 399 10.4 Other Classical Planning Approaches......Page 407 10.5 Analysis of Planning Approaches......Page 412 10.6 Summary, Bibliographical and Historical Notes, Exercises......Page 413 11.1 Time, Schedules, and Resources......Page 421 11.2 Hierarchical Planning......Page 426 11.3 Planning and Acting in Nondeterministic Domains......Page 435 11.4 Multiagent Planning......Page 445 11.5 Summary, Bibliographical and Historical Notes, Exercises......Page 450 12.1 Ontological Engineering......Page 457 12.2 Categories and Objects......Page 460 12.3 Events......Page 466 12.4 Mental Events and Mental Objects......Page 470 12.5 Reasoning Systems for Categories......Page 473 12.6 Reasoning with Default Information......Page 478 12.7 The Internet Shopping World......Page 482 12.8 Summary, Bibliographical and Historical Notes, Exercises......Page 487 13.1 Acting under Uncertainty......Page 500 13.2 Basic Probability Notation......Page 503 13.3 Inference Using Full Joint Distributions......Page 510 13.4 Independence......Page 514 13.5 Bayes’ Rule and Its Use......Page 515 13.6 The Wumpus World Revisited......Page 519 13.7 Summary, Bibliographical and Historical Notes, Exercises......Page 523 14.1 Representing Knowledge in an Uncertain Domain......Page 530 14.2 The Semantics of Bayesian Networks......Page 533 14.3 Efficient Representation of Conditional Distributions......Page 538 14.4 Exact Inference in Bayesian Networks......Page 542 14.5 Approximate Inference in Bayesian Networks......Page 550 14.6 Relational and First-Order Probability Models......Page 559 14.7 Other Approaches to Uncertain Reasoning......Page 566 14.8 Summary, Bibliographical and Historical Notes, Exercises......Page 571 15.1 Time and Uncertainty......Page 586 15.2 Inference in Temporal Models......Page 590 15.3 Hidden Markov Models......Page 598 15.4 Kalman Filters......Page 604 15.5 Dynamic Bayesian Networks......Page 610 15.6 Keeping Track of Many Objects......Page 619 15.7 Summary, Bibliographical and Historical Notes, Exercises......Page 623 16.1 Combining Beliefs and Desires under Uncertainty......Page 630 16.2 The Basis of Utility Theory......Page 631 16.3 Utility Functions......Page 635 16.4 Multiattribute Utility Functions......Page 642 16.5 Decision Networks......Page 646 16.6 The Value of Information......Page 648 16.7 Decision-Theoretic Expert Systems......Page 653 16.8 Summary, Bibliographical and Historical Notes, Exercises......Page 656 17.1 Sequential Decision Problems......Page 665 17.2 Value Iteration......Page 672 17.3 Policy Iteration......Page 676 17.4 Partially Observable MDPs......Page 678 17.5 Decisions with Multiple Agents: Game Theory......Page 686 17.6 Mechanism Design......Page 699 17.7 Summary, Bibliographical and Historical Notes, Exercises......Page 704 18.1 Forms of Learning......Page 713 18.2 Supervised Learning......Page 715 18.3 Learning Decision Trees......Page 717 18.4 Evaluating and Choosing the Best Hypothesis......Page 728 18.5 The Theory of Learning......Page 733 18.6 Regression and Classification with Linear Models......Page 737 18.7 Artificial Neural Networks......Page 747 18.8 Nonparametric Models......Page 757 18.9 Support Vector Machines......Page 764 18.10 Ensemble Learning......Page 768 18.11 Practical Machine Learning......Page 773 18.12 Summary, Bibliographical and Historical Notes, Exercises......Page 777 19.1 A Logical Formulation of Learning......Page 788 19.2 Knowledge in Learning......Page 797 19.3 Explanation-Based Learning......Page 800 19.4 Learning Using Relevance Information......Page 804 19.5 Inductive Logic Programming......Page 808 19.6 Summary, Bibliographical and Historical Notes, Exercises......Page 817 20.1 Statistical Learning......Page 822 20.2 Learning with Complete Data......Page 826 20.3 Learning with Hidden Variables: The EM Algorithm......Page 836 20.4 Summary, Bibliographical and Historical Notes, Exercises......Page 845 21.1 Introduction......Page 850 21.2 Passive Reinforcement Learning......Page 852 21.3 Active Reinforcement Learning......Page 859 21.4 Generalization in Reinforcement Learning......Page 865 21.5 Policy Search......Page 868 21.6 Applications of Reinforcement Learning......Page 870 21.7 Summary, Bibliographical and Historical Notes, Exercises......Page 873 22.1 Language Models......Page 880 22.2 Text Classification......Page 885 22.3 Information Retrieval......Page 887 22.4 Information Extraction......Page 893 22.5 Summary, Bibliographical and Historical Notes, Exercises......Page 902 23.1 Phrase Structure Grammars......Page 908 23.2 Syntactic Analysis (Parsing)......Page 912 23.3 Augmented Grammars and Semantic Interpretation......Page 917 23.4 Machine Translation......Page 927 23.5 Speech Recognition......Page 932 23.6 Summary, Bibliographical and Historical Notes, Exercises......Page 938 24 Perception......Page 948 24.1 Image Formation......Page 949 24.2 Early Image-Processing Operations......Page 955 24.3 Object Recognition by Appearance......Page 962 24.4 Reconstructing the 3D World......Page 967 24.5 Object Recognition from Structural Information......Page 977 24.6 Using Vision......Page 981 24.7 Summary, Bibliographical and Historical Notes, Exercises......Page 985 25.1 Introduction......Page 991 25.2 Robot Hardware......Page 993 25.3 Robotic Perception......Page 998 25.4 Planning to Move......Page 1006 25.5 Planning Uncertain Movements......Page 1013 25.6 Moving......Page 1017 25.7 Robotic Software Architectures......Page 1023 25.8 Application Domains......Page 1026 25.9 Summary, Bibliographical and Historical Notes, Exercises......Page 1030 26.1 Weak AI: Can Machines Act Intelligently?......Page 1040 26.2 Strong AI: Can Machines Really Think?......Page 1046 26.3 The Ethics and Risks of Developing Artificial Intelligence......Page 1054 26.4 Summary, Bibliographical and Historical Notes, Exercises......Page 1060 27.1 Agent Components......Page 1064 27.2 Agent Architectures......Page 1067 27.3 Are We Going in the Right Direction?......Page 1069 27.4 What If AI Does Succeed?......Page 1071 A.1 Complexity Analysis and O() Notation......Page 1073 A.2 Vectors, Matrices, and Linear Algebra......Page 1075 A.3 Probability Distributions......Page 1077 B.1 Defining Languages with Backus–Naur Form (BNF)......Page 1080 B.2 Describing Algorithms with Pseudocode......Page 1081 B.3 Online Help......Page 1082 Bibliography......Page 1083 Part I Artificial Intelligence 1 Introduction 2 Intelligent Agents Part II Problem Solving 3 Solving Problems by Searching 4 Beyond Classical Search 5 Adversarial Search 6 Constraint Satisfaction Problems Part III Knowledge and Reasoning 7 Logical Agents 8 First-Order Logic 9 Inference in First-Order Logic 10 Classical Planning 11 Planning and Acting in the Real World 12 Knowledge Representation Part IV Uncertain Knowledge and Reasoning 13 Quantifying Uncertainty 14 Probabilistic Reasoning 15 Probabilistic Reasoning over Time 16 Making Simple Decisions 17 Making Complex Decisions Part V Learning 18 Learning from Examples 19 Knowledge in Learning 20 Learning Probabilistic Models 21 Reinforcement Learning Part VII Communicating, Perceiving, and Acting 22 Natural Language Processing 23 Natural Language for Communication 24 Perception 25 Robotics Part VIII Conclusions 26 Philosophical Foundations 27 AI: The Present and Future "In this third edition, the authors have updated the treatment of all major areas. A new organizing principle--the representational dimension of atomic, factored, and structured models--has been added. Significant new material has been provided in areas such as partially observable search, contingency planning, hierarchical planning, relational and first-order probability models, regularization and loss functions in machine learning, kernel methods, Web search engines, information extraction, and learning in vision and robotics. The book also includes hundreds of new exercises"--Back cover