Artificial Intelligence: A Modern Approach, Global Edition

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, Berkeley, where he is a Professor and former Chair of Computer Science, Director of the Centre for Human-Compatible AI, 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 co-winner of the Computers and Thought Award. He is a Fellow of the American Association for Artificial Intelligence, the Association for Computing Machinery, and the American Association for the Advancement of Science, and Honorary Fellow of Wadham College, Oxford, and an Andrew Carnegie Fellow. He held the Chaire Blaise Pascal in Paris from 2012 to 2014. He has published over 300 papers on a wide range of topics in artificial intelligence. His other books include: The Use of Knowledge in Analogy and Induction, Do the Right Thing: Studies in Limited Rationality (with Eric Wefald), and Human Compatible: Artificial Intelligence and the Problem of Control. 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 are research faculty member at Berkeley. His other books are: Paradigms of AI Programming: Case Studies in Common Lisp, Verbmobil: A Translation System for Face-to-Face Dialog, and Intelligent Help Systems for UNIX. The two authors shared the inaugural AAAI/EAAI Outstanding Educator award in 2016.

Chapter I  Artificial Intelligence

Introduction

What Is AI?
The Foundations of Artificial Intelligence
The History of Artificial Intelligence
The State of the Art
Risks and Benefits of AI

SummaryBibliographical and Historical Notes
Intelligent Agents

Agents and Environments
Good Behavior: The Concept of Rationality
The Nature of Environments
The Structure of Agents

SummaryBibliographical and Historical Notes
Chapter II  Problem Solving
Solving Problems by Searching

Problem-Solving Agents
Example Problems
Search Algorithms
Uninformed Search Strategies
Informed (Heuristic) Search Strategies
Heuristic Functions

SummaryBibliographical and Historical Notes
Search in Complex Environments

Local Search and Optimization Problems
Local Search in Continuous Spaces
Search with Nondeterministic Actions
Search in Partially Observable Environments
Online Search Agents and Unknown Environments

SummaryBibliographical and Historical Notes
Constraint Satisfaction Problems

Defining Constraint Satisfaction Problems
Constraint Propagation: Inference in CSPs
Backtracking Search for CSPs
Local Search for CSPs
The Structure of Problems

SummaryBibliographical and Historical Notes
Adversarial Search and Games

Game Theory
Optimal Decisions in Games
Heuristic Alpha--Beta Tree Search
Monte Carlo Tree Search
Stochastic Games
Partially Observable Games
Limitations of Game Search Algorithms

SummaryBibliographical and Historical Notes
Chapter III  Knowledge, Reasoning and Planning
Logical Agents

Knowledge-Based Agents
The Wumpus World
Logic
Propositional Logic: A Very Simple Logic
Propositional Theorem Proving
Effective Propositional Model Checking
Agents Based on Propositional Logic

SummaryBibliographical and Historical Notes
First-Order Logic

Representation Revisited
Syntax and Semantics of First-Order Logic
Using First-Order Logic
Knowledge Engineering in First-Order Logic

SummaryBibliographical and Historical Notes
Inference in First-Order Logic

Propositional vs. First-Order Inference
Unification and First-Order Inference
Forward Chaining
Backward Chaining
Resolution

SummaryBibliographical and Historical Notes
Knowledge Representation

Ontological Engineering
Categories and Objects
Events
Mental Objects and Modal Logic
for Categories
Reasoning with Default Information

SummaryBibliographical and Historical Notes
Automated Planning

Definition of Classical Planning
Algorithms for Classical Planning
Heuristics for Planning
Hierarchical Planning
Planning and Acting in Nondeterministic Domains
Time, Schedules, and Resources
Analysis of Planning Approaches

SummaryBibliographical and Historical Notes
Chapter IV  Uncertain Knowledge and Reasoning
Quantifying Uncertainty

Acting under Uncertainty
Basic Probability Notation
Inference Using Full Joint Distributions
Independence 12.5 Bayes' Rule and Its Use
Naive Bayes Models
The Wumpus World Revisited

SummaryBibliographical and Historical Notes
Probabilistic Reasoning

Representing Knowledge in an Uncertain Domain
The Semantics of Bayesian Networks
Exact Inference in Bayesian Networks
Approximate Inference for Bayesian Networks
Causal Networks

SummaryBibliographical and Historical Notes
Probabilistic Reasoning over Time

Time and Uncertainty
Inference in Temporal Models
Hidden Markov Models
Kalman Filters
Dynamic Bayesian Networks

SummaryBibliographical and Historical Notes
Making Simple Decisions

Combining Beliefs and Desires under Uncertainty
The Basis of Utility Theory
Utility Functions
Multiattribute Utility Functions
Decision Networks
The Value of Information
Unknown Preferences

SummaryBibliographical and Historical Notes
Making Complex Decisions

Sequential Decision Problems
Algorithms for MDPs
Bandit Problems
Partially Observable MDPs
Algorithms for Solving POMDPs

SummaryBibliographical and Historical Notes
Multiagent Decision Making

Properties of Multiagent Environments
Non-Cooperative Game Theory
Cooperative Game Theory
Making Collective Decisions

SummaryBibliographical and Historical Notes
Probabilistic Programming

Relational Probability Models
Open-Universe Probability Models
Keeping Track of a Complex World
Programs as Probability Models

SummaryBibliographical and Historical Notes
Chapter V  Machine Learning
Learning from Examples

Forms of Leaming
Supervised Learning .
Learning Decision Trees .
Model Selection and Optimization
The Theory of Learning
Linear Regression and Classification
Nonparametric Models
Ensemble Learning
Developing Machine Learning Systen

SummaryBibliographical and Historical Notes
Knowledge in Learning

A Logical Formulation of Learning
Knowledge in Learning
Exmplanation-Based Leaening
Learning Using Relevance Information
Inductive Logic Programming

SummaryBibliographical and Historical Notes
Learning Probabilistic Models

Statistical Learning
Learning with Complete Data
Learning with Hidden Variables: The EM Algorithm

SummaryBibliographical and Historical Notes
Deep Learning

Simple Feedforward Networks
Computation Graphs for Deep Learning
Convolutional Networks
Learning Algorithms
Generalization
Recurrent Neural Networks
Unsupervised Learning and Transfer Learning
Applications

SummaryBibliographical and Historical Notes
Reinforcement Learning

Learning from Rewards
Passive Reinforcement Learning
Active Reinforcement Learning
Generalization in Reinforcement Learning
Policy Search
Apprenticeship and Inverse Reinforcement Leaming
Applications of Reinforcement Learning

SummaryBibliographical and Historical Notes
Chapter VI  Communicating, perceiving, and acting
Natural Language Processing

Language Models
Grammar
Parsing
Augmented Grammars
Complications of Real Natural Languagr
Natural Language Tasks

SummaryBibliographical and Historical Notes
Deep Learning for Natural Language Processing

Word Embeddings
Recurrent Neural Networks for NLP
Sequence-to-Sequence Models
The Transformer Architecture
Pretraining and Transfer Learning
State of the art

SummaryBibliographical and Historical Notes
Robotics

Robots
Robot Hardware
What kind of problem is robotics solving?
Robotic Perception
Planning and Control
Planning Uncertain Movements
Reinforcement Laming in Robotics
Humans and Robots
Alternative Robotic Frameworks
Application Domains

SummaryBibliographical and Historical Notes
Computer Vision

Introduction
Image Formation
Simple Image Features
Classifying Images
Detecting Objects
The 3D World
Using Computer Vision

SummaryBibliographical and Historical Notes
Chapter VII  Conclusions
Philosophy, Ethics, and Safety of Al

The Limits of Al
Can Machines Really Think?
The Ethics of Al

SummaryBibliographical and Historical Notes
The Future of AI

Al Components
Al Architectures



A Mathematical Background

A.1 Complexity Analysis and O0 Notation
A.2 Vectors, Matrices, and Linear Algebra
A.3 Probability Distributions
Bibliographical and Historical Notes

 

B Notes on Languages and Algorithms

B.1 Defining Languages with Backus-Naur Form (BNF)
B.2 Describing Algorithms with Pseudocode
B.3 Online Supplemental Material

 

Bibliography Index