Part I: Artificial Intelligence
Chapter 1: Introduction ... 1
1.1. What Is AI? ... 1
1.1.1. Acting humanly: The Turing Test approach ... 2
1.1.2. Thinking humanly: The cognitive modeling approach ... 3
1.1.3. Thinking rationally: The ``laws of thought'' approach ... 4
1.1.4. Acting rationally: The rational agent approach ... 4
1.2. The Foundations of Artificial Intelligence ... 5
1.2.1. Philosophy ... 5
1.2.2. Mathematics ... 7
1.2.3. Economics ... 9
1.2.4. Neuroscience ... 10
1.2.5. Psychology ... 12
1.2.6. Computer engineering ... 13
1.2.7. Control theory and cybernetics ... 15
1.2.8. Linguistics ... 15
1.3. The History of Artificial Intelligence ... 16
1.3.1. The gestation of artificial intelligence (1943--1955) ... 16
1.3.2. The birth of artificial intelligence (1956) ... 17
1.3.3. Early enthusiasm, great expectations (1952--1969) ... 18
1.3.4. A dose of reality (1966--1973) ... 20
1.3.5. Knowledge-based systems: The key to power? (1969--1979) ... 22
1.3.6. AI becomes an industry (1980--present) ... 24
1.3.7. The return of neural networks (1986--present) ... 24
1.3.8. AI adopts the scientific method (1987--present) ... 25
1.3.9. The emergence of intelligent agents (1995--present) ... 26
1.3.10. The availability of very large data sets (2001--present) ... 27
1.4. The State of the Art ... 28
1.5. Summary ... 29
Bibliographical and Historical Notes ... 30
Exercises ... 31
Chapter 2: Intelligent Agents ... 34
2.1. Agents and Environments ... 34
2.2. Good Behavior: The Concept of Rationality ... 36
2.2.1. Rationality ... 37
2.2.2. Omniscience, learning, and autonomy ... 38
2.3. The Nature of Environments ... 40
2.3.1. Specifying the task environment ... 40
2.3.2. Properties of task environments ... 41
2.4. The Structure of Agents ... 46
2.4.1. Agent programs ... 46
2.4.2. Simple reflex agents ... 48
2.4.3. Model-based reflex agents ... 50
2.4.4. Goal-based agents ... 52
2.4.5. Utility-based agents ... 53
2.4.6. Learning agents ... 54
2.4.7. How the components of agent programs work ... 57
2.5. Summary ... 59
Bibliographical and Historical Notes ... 59
Exercises ... 61
Part II: Problem-solving
Chapter 3: Solving Problems by Searching ... 64
3.1. Problem-Solving Agents ... 64
3.1.1. Well-defined problems and solutions ... 66
3.1.2. Formulating problems ... 68
3.2. Example Problems ... 69
3.2.1. Toy problems ... 70
3.2.2. Real-world problems ... 73
3.3. Searching for Solutions ... 75
3.3.1. Infrastructure for search algorithms ... 78
3.3.2. Measuring problem-solving performance ... 80
3.4. Uninformed Search Strategies ... 81
3.4.1. Breadth-first search ... 81
3.4.2. Uniform-cost search ... 83
3.4.3. Depth-first search ... 85
3.4.4. Depth-limited search ... 87
3.4.5. Iterative deepening depth-first search ... 88
3.4.6. Bidirectional search ... 90
3.4.7. Comparing uninformed search strategies ... 91
3.5. Informed (Heuristic) Search Strategies ... 92
3.5.1. Greedy best-first search ... 92
3.5.2. A* search: Minimizing the total estimated solution cost ... 93
Conditions for optimality: Admissibility and consistency ... 94
Optimality of A* ... 95
3.5.3. Memory-bounded heuristic search ... 99
3.5.4. Learning to search better ... 102
3.6. Heuristic Functions ... 102
3.6.1. The effect of heuristic accuracy on performance ... 103
3.6.2. Generating admissible heuristics from relaxed problems ... 104
3.6.3. Generating admissible heuristics from subproblems: Pattern databases ... 106
3.6.4. Learning heuristics from experience ... 107
3.7. Summary ... 108
Bibliographical and Historical Notes ... 109
Exercises ... 112
Chapter 4: Beyond Classical Search ... 120
4.1. Local Search Algorithms and Optimization Problems ... 120
4.1.1. Hill-climbing search ... 122
4.1.2. Simulated annealing ... 125
4.1.3. Local beam search ... 125
4.1.4. Genetic algorithms ... 126
4.2. Local Search in Continuous Spaces ... 129
4.3. Searching with Nondeterministic Actions ... 133
4.3.1. The erratic vacuum world ... 133
4.3.2 AND-OR search trees ... 135
4.3.3. Try, try again ... 137
4.4. Searching with Partial Observations ... 138
4.4.1. Searching with no observation ... 138
4.4.2. Searching with observations ... 142
4.4.3. Solving partially observable problems ... 143
4.4.4. An agent for partially observable environments ... 144
4.5. Online Search Agents and Unknown Environments ... 147
4.5.1. Online search problems ... 147
4.5.2. Online search agents ... 149
4.5.3. Online local search ... 150
4.5.4. Learning in online search ... 153
4.6. Summary ... 153
Bibliographical and Historical Notes ... 154
Exercises ... 157
Chapter 5: Adversarial Search ... 161
5.1. Games ... 161
5.2. Optimal Decisions in Games ... 163
5.2.1. The minimax algorithm ... 165
5.2.2. Optimal decisions in multiplayer games ... 165
5.3. Alpha--Beta Pruning ... 167
5.3.1. Move ordering ... 169
5.4. Imperfect Real-Time Decisions ... 171
5.4.1. Evaluation functions ... 171
5.4.2. Cutting off search ... 173
5.4.3. Forward pruning ... 174
5.4.4. Search versus lookup ... 176
5.5. Stochastic Games ... 177
5.5.1. Evaluation functions for games of chance ... 178
5.6. Partially Observable Games ... 180
5.6.1. Kriegspiel: Partially observable chess ... 180
5.6.2. Card games ... 183
5.7. State-of-the-Art Game Programs ... 185
5.8. Alternative Approaches ... 187
5.9. Summary ... 189
Bibliographical and Historical Notes ... 190
Exercises ... 195
Chapter 6: Constraint Satisfaction Problems ... 202
6.1. Defining Constraint Satisfaction Problems ... 202
6.1.1. Example problem: Map coloring ... 203
6.1.2. Example problem: Job-shop scheduling ... 204
6.1.3. Variations on the CSP formalism ... 205
6.2. Constraint Propagation: Inference in CSPs ... 208
6.2.1. Node consistency ... 208
6.2.2. Arc consistency ... 208
6.2.3. Path consistency ... 210
6.2.4. K-consistency. ... 211
6.2.5. Global constraints ... 211
6.2.6. Sudoku example ... 212
6.3. Backtracking Search for CSPs ... 214
6.3.1. Variable and value ordering ... 216
6.3.2. Interleaving search and inference ... 217
6.3.3. Intelligent backtracking: Looking backward ... 218
6.4. Local Search for CSPs ... 220
6.5. The Structure of Problems ... 222
6.6. Summary ... 227
Bibliographical and Historical Notes ... 227
Exercises ... 230
Part III: Knowledge, reasoning, and planning
Chapter 7: Logical Agents ... 234
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.4.1. Syntax ... 244
7.4.2. Semantics ... 245
7.4.3. A simple knowledge base ... 246
7.4.4. A simple inference procedure ... 247
7.5. Propositional Theorem Proving ... 249
7.5.1. Inference and proofs ... 250
7.5.2. Proof by resolution ... 252
Conjunctive normal form ... 253
A resolution algorithm ... 254
Completeness of resolution ... 255
7.5.3. Horn clauses and definite clauses ... 256
7.5.4. Forward and backward chaining ... 257
7.6. Effective Propositional Model Checking ... 259
7.6.1. A complete backtracking algorithm ... 260
7.6.2. Local search algorithms ... 262
7.6.3. The landscape of random SAT problems ... 263
7.7. Agents Based on Propositional Logic ... 265
7.7.1. The current state of the world ... 265
7.7.2. A hybrid agent ... 268
7.7.3. Logical state estimation ... 269
7.7.4. Making plans by propositional inference ... 271
7.8. Summary ... 274
Bibliographical and Historical Notes ... 275
Exercises ... 279
Chapter 8: First-Order Logic ... 285
8.1. Representation Revisited ... 285
8.1.1. The language of thought ... 286
8.1.2. Combining the best of formal and natural languages ... 288
8.2. Syntax and Semantics of First-Order Logic ... 290
8.2.1. Models for first-order logic ... 290
8.2.2. Symbols and interpretations ... 292
8.2.3. Terms ... 294
8.2.4. Atomic sentences ... 294
8.2.5. Complex sentences ... 295
8.2.6. Quantifiers ... 295
Universal quantification (∀) ... 295
Existential quantification (∃) ... 297
Nested quantifiers ... 297
Connections between ∀ and ∃ ... 298
8.2.7. Equality ... 299
8.2.8. An alternative semantics? ... 299
8.3. Using First-Order Logic ... 300
8.3.1. Assertions and queries in first-order logic ... 301
8.3.2. The kinship domain ... 301
8.3.3. Numbers, sets, and lists ... 303
8.3.4. The wumpus world ... 305
8.4. Knowledge Engineering in First-Order Logic ... 307
8.4.1. The knowledge-engineering process ... 307
8.4.2. The electronic circuits domain ... 309
Identify the task ... 309
Assemble the relevant knowledge ... 309
Decide on a vocabulary ... 310
Encode general knowledge of the domain ... 310
Encode the specific problem instance ... 311
Pose queries to the inference procedure ... 312
Debug the knowledge base ... 312
8.5. Summary ... 313
Bibliographical and Historical Notes ... 313
Exercises ... 315
Chapter 9: Inference in First-Order Logic ... 322
9.1. Propositional vs. First-Order Inference ... 322
9.1.1. Inference rules for quantifiers ... 322
9.1.2. Reduction to propositional inference ... 324
9.2. Unification and Lifting ... 325
9.2.1. A first-order inference rule ... 325
9.2.2. Unification ... 326
9.2.3. Storage and retrieval ... 327
9.3. Forward Chaining ... 330
9.3.1. First-order definite clauses ... 330
9.3.2. A simple forward-chaining algorithm ... 331
9.3.3. Efficient forward chaining ... 333
Matching rules against known facts ... 333
Incremental forward chaining ... 335
Irrelevant facts ... 336
9.4. Backward Chaining ... 337
9.4.1. A backward-chaining algorithm ... 337
9.4.2. Logic programming ... 339
9.4.3. Efficient implementation of logic programs ... 340
9.4.4. Redundant inference and infinite loops ... 342
9.4.5. Database semantics of Prolog ... 343
9.4.6. Constraint logic programming ... 344
9.5. Resolution ... 345
9.5.1. Conjunctive normal form for first-order logic ... 345
9.5.2. The resolution inference rule ... 347
9.5.3. Example proofs ... 347
9.5.4. Completeness of resolution ... 350
9.5.5. Equality ... 353
9.5.6. Resolution strategies ... 355
Practical uses of resolution theorem provers ... 356
9.6. Summary ... 357
Bibliographical and Historical Notes ... 357
Exercises ... 360
Chapter 10: Classical Planning ... 366
10.1. Definition of Classical Planning ... 366
10.1.1. Example: Air cargo transport ... 369
10.1.2. Example: The spare tire problem ... 370
10.1.3. Example: The blocks world ... 370
10.1.4. The complexity of classical planning ... 372
10.2. Algorithms for Planning as State-Space Search ... 373
10.2.1. Forward (progression) state-space search ... 373
10.2.2. Backward (regression) relevant-states search ... 374
10.2.3. Heuristics for planning ... 376
10.3. Planning Graphs ... 379
10.3.1. Planning graphs for heuristic estimation ... 381
10.3.2. The Graphplan algorithm ... 383
10.3.3. Termination of Graphplan ... 385
10.4. Other Classical Planning Approaches ... 387
10.4.1. Classical planning as Boolean satisfiability ... 387
10.4.2. Planning as first-order logical deduction: Situation calculus ... 388
10.4.3. Planning as constraint satisfaction ... 390
10.4.4. Planning as refinement of partially ordered plans ... 390
10.5. Analysis of Planning Approaches ... 392
10.6. Summary ... 393
Bibliographical and Historical Notes ... 393
Exercises ... 396
Chapter 11: Planning and Acting in the Real World ... 401
11.1. Time, Schedules, and Resources ... 401
11.1.1. Representing temporal and resource constraints ... 402
11.1.2. Solving scheduling problems ... 403
11.2. Hierarchical Planning ... 406
11.2.1. High-level actions ... 406
11.2.2. Searching for primitive solutions ... 408
11.2.3. Searching for abstract solutions ... 410
11.3. Planning and Acting in Nondeterministic Domains ... 415
11.3.1. Sensorless planning ... 417
11.3.2. Contingent planning ... 421
11.3.3. Online replanning ... 422
11.4. Multiagent Planning ... 425
11.4.1. Planning with multiple simultaneous actions ... 426
11.4.2. Planning with multiple agents: Cooperation and coordination ... 428
11.5. Summary ... 430
Bibliographical and Historical Notes ... 431
Exercises ... 435
Chapter 12: Knowledge Representation ... 437
12.1. Ontological Engineering ... 437
12.2. Categories and Objects ... 440
12.2.1. Physical composition ... 441
12.2.2. Measurements ... 444
12.2.3. Objects: Things and stuff ... 445
12.3. Events ... 446
12.3.1. Processes ... 447
12.3.2. Time intervals ... 448
12.3.3. Fluents and objects ... 449
12.4. Mental Events and Mental Objects ... 450
12.5. Reasoning Systems for Categories ... 453
12.5.1. Semantic networks ... 454
12.5.2. Description logics ... 456
12.6. Reasoning with Default Information ... 458
12.6.1. Circumscription and default logic ... 458
12.6.2. Truth maintenance systems ... 460
12.7. The Internet Shopping World ... 462
12.7.1. Following links ... 464
12.7.2. Comparing offers ... 466
12.8. Summary ... 467
Bibliographical and Historical Notes ... 468
Exercises ... 473
Part IV: Uncertain knowledge and reasoning
Chapter 13: Quantifying Uncertainty ... 480
13.1. Acting under Uncertainty ... 480
13.1.1. Summarizing uncertainty ... 481
13.1.2. Uncertainty and rational decisions ... 482
13.2. Basic Probability Notation ... 483
13.2.1. What probabilities are about ... 484
13.2.2. The language of propositions in probability assertions ... 486
13.2.3. Probability axioms and their reasonableness ... 488
13.3. Inference Using Full Joint Distributions ... 490
13.4. Independence ... 494
13.5. Bayes' Rule and Its Use ... 495
13.5.1. Applying Bayes' rule: The simple case ... 496
13.5.2. Using Bayes' rule: Combining evidence ... 497
13.6. The Wumpus World Revisited ... 499
13.7. Summary ... 503
Bibliographical and Historical Notes ... 503
Exercises ... 506
Chapter 14: Probabilistic Reasoning ... 510
14.1. Representing Knowledge in an Uncertain Domain ... 510
14.2. The Semantics of Bayesian Networks ... 513
14.2.1. Representing the full joint distribution ... 513
A method for constructing Bayesian networks ... 514
Compactness and node ordering ... 515
14.2.2. Conditional independence relations in Bayesian networks ... 517
14.3. Efficient Representation of Conditional Distributions ... 518
Bayesian nets with continuous variables ... 519
14.4. Exact Inference in Bayesian Networks ... 522
14.4.1. Inference by enumeration ... 523
14.4.2. The variable elimination algorithm ... 524
Operations on factors ... 526
Variable ordering and variable relevance ... 527
14.4.3. The complexity of exact inference ... 528
14.4.4. Clustering algorithms ... 529
14.5. Approximate Inference in Bayesian Networks ... 530
14.5.1. Direct sampling methods ... 530
Rejection sampling in Bayesian networks ... 532
Likelihood weighting ... 532
14.5.2. Inference by Markov chain simulation ... 535
Gibbs sampling in Bayesian networks ... 536
Why Gibbs sampling works ... 536
14.6. Relational and First-Order Probability Models ... 539
14.6.1. Possible worlds ... 540
14.6.2. Relational probability models ... 542
14.6.3. Open-universe probability models ... 544
14.7. Other Approaches to Uncertain Reasoning ... 546
14.7.1. Rule-based methods for uncertain reasoning ... 547
14.7.2. Representing ignorance: Dempster--Shafer theory ... 549
14.7.3. Representing vagueness: Fuzzy sets and fuzzy logic ... 550
14.8. Summary ... 551
Bibliographical and Historical Notes ... 552
Exercises ... 558
Chapter 15: Probabilistic Reasoning over Time ... 566
15.1. Time and Uncertainty ... 566
15.1.1. States and observations ... 567
15.1.2. Transition and sensor models ... 568
15.2. Inference in Temporal Models ... 570
15.2.1. Filtering and prediction ... 571
15.2.2. Smoothing ... 574
15.2.3. Finding the most likely sequence ... 576
15.3. Hidden Markov Models ... 578
15.3.1. Simplified matrix algorithms ... 579
15.3.2. Hidden Markov model example: Localization ... 581
15.4. Kalman Filters ... 584
15.4.1. Updating Gaussian distributions ... 584
15.4.2. A simple one-dimensional example ... 585
15.4.3. The general case ... 587
15.4.4. Applicability of Kalman filtering ... 588
15.5. Dynamic Bayesian Networks ... 590
15.5.1. Constructing DBNs ... 591
15.5.2. Exact inference in DBNs ... 595
15.5.3. Approximate inference in DBNs ... 596
15.6. Keeping Track of Many Objects ... 599
15.7. Summary ... 603
Bibliographical and Historical Notes ... 603
Exercises ... 606
Chapter 16: Making Simple Decisions ... 610
16.1. Combining Beliefs and Desires under Uncertainty ... 610
16.2. The Basis of Utility Theory ... 611
16.2.1. Constraints on rational preferences ... 612
16.2.2. Preferences lead to utility ... 613
16.3. Utility Functions ... 615
16.3.1. Utility assessment and utility scales ... 615
16.3.2. The utility of money ... 616
16.3.3. Expected utility and post-decision disappointment ... 618
16.3.4. Human judgment and irrationality ... 619
16.4. Multiattribute Utility Functions ... 622
16.4.1. Dominance ... 622
16.4.2. Preference structure and multiattribute utility ... 624
Preferences without uncertainty ... 624
Preferences with uncertainty ... 625
16.5. Decision Networks ... 626
16.5.1. Representing a decision problem with a decision network ... 626
16.5.2. Evaluating decision networks ... 628
16.6. The Value of Information ... 628
16.6.1. A simple example ... 629
16.6.2. A general formula for perfect information ... 630
16.6.3. Properties of the value of information ... 631
16.6.4. Implementation of an information-gathering agent ... 632
16.7. Decision-Theoretic Expert Systems ... 633
16.8. Summary ... 636
Bibliographical and Historical Notes ... 636
Exercises ... 640
Chapter 17: Making Complex Decisions ... 645
17.1. Sequential Decision Problems ... 645
17.1.1. Utilities over time ... 648
17.1.2. Optimal policies and the utilities of states ... 650
17.2. Value Iteration ... 652
17.2.1. The Bellman equation for utilities ... 652
17.2.2. The value iteration algorithm ... 652
17.2.3. Convergence of value iteration ... 654
17.3. Policy Iteration ... 656
17.4. Partially Observable MDPs ... 658
17.4.1. Definition of POMDPs ... 658
17.4.2. Value iteration for POMDPs ... 660
17.4.3. Online agents for POMDPs ... 664
17.5. Decisions with Multiple Agents: Game Theory ... 666
17.5.1. Single-move games ... 667
17.5.2. Repeated games ... 673
17.5.3. Sequential games ... 674
17.6. Mechanism Design ... 679
17.6.1. Auctions ... 679
17.6.2. Common goods ... 683
17.7. Summary ... 684
Bibliographical and Historical Notes ... 685
Exercises ... 688
Part V: Learning
Chapter 18: Learning from Examples ... 693
18.1. Forms of Learning ... 693
Components to be learned ... 694
Representation and prior knowledge ... 694
Feedback to learn from ... 694
18.2. Supervised Learning ... 695
18.3. Learning Decision Trees ... 697
18.3.1. The decision tree representation ... 698
18.3.2. Expressiveness of decision trees ... 698
18.3.3. Inducing decision trees from examples ... 699
18.3.4. Choosing attribute tests ... 703
18.3.5. Generalization and overfitting ... 705
18.3.6. Broadening the applicability of decision trees ... 706
18.4. Evaluating and Choosing the Best Hypothesis ... 708
18.4.1. Model selection: Complexity versus goodness of fit ... 709
18.4.2. From error rates to loss ... 710
18.4.3. Regularization ... 712
18.5. The Theory of Learning ... 713
18.5.1. PAC learning example: Learning decision lists ... 715
18.6. Regression and Classification with Linear Models ... 717
18.6.1. Univariate linear regression ... 718
18.6.2. Multivariate linear regression ... 720
18.6.3. Linear classifiers with a hard threshold ... 723
18.6.4. Linear classification with logistic regression ... 725
18.7. Artificial Neural Networks ... 727
18.7.1. Neural network structures ... 728
18.7.2. Single-layer feed-forward neural networks (perceptrons) ... 729
18.7.3. Multilayer feed-forward neural networks ... 731
18.7.4. Learning in multilayer networks ... 733
18.7.5. Learning neural network structures ... 736
18.8. Nonparametric Models ... 737
18.8.1. Nearest neighbor models ... 738
18.8.2. Finding nearest neighbors with k-d trees ... 739
18.8.3. Locality-sensitive hashing ... 740
18.8.4. Nonparametric regression ... 741
18.9. Support Vector Machines ... 744
18.10. Ensemble Learning ... 748
18.10.1. Online Learning ... 752
18.11. Practical Machine Learning ... 753
18.11.1. Case study: Handwritten digit recognition ... 753
18.11.2. Case study: Word senses and house prices ... 755
18.12. Summary ... 757
Bibliographical and Historical Notes ... 758
Exercises ... 763
Chapter 19: Knowledge in Learning ... 768
19.1. A Logical Formulation of Learning ... 768
19.1.1. Examples and hypotheses ... 768
19.1.2. Current-best-hypothesis search ... 770
19.1.3. Least-commitment search ... 773
19.2. Knowledge in Learning ... 777
19.2.1. Some simple examples ... 778
19.2.2. Some general schemes ... 778
19.3. Explanation-Based Learning ... 780
19.3.1. Extracting general rules from examples ... 781
19.3.2. Improving efficiency ... 783
19.4. Learning Using Relevance Information ... 784
19.4.1. Determining the hypothesis space ... 785
19.4.2. Learning and using relevance information ... 785
19.5. Inductive Logic Programming ... 788
19.5.1. An example ... 788
19.5.2. Top-down inductive learning methods ... 791
19.5.3. Inductive learning with inverse deduction ... 794
19.5.4. Making discoveries with inductive logic programming ... 796
19.6. Summary ... 797
Bibliographical and Historical Notes ... 798
Exercises ... 801
Chapter 20: Learning Probabilistic Models ... 802
20.1. Statistical Learning ... 802
20.2. Learning with Complete Data ... 806
20.2.1. Maximum-likelihood parameter learning: Discrete models ... 806
20.2.2. Naive Bayes models ... 808
20.2.3. Maximum-likelihood parameter learning: Continuous models ... 809
20.2.4. Bayesian parameter learning ... 810
20.2.5. Learning Bayes net structures ... 813
20.2.6. Density estimation with nonparametric models ... 814
20.3. Learning with Hidden Variables: The EM Algorithm ... 816
20.3.1. Unsupervised clustering: Learning mixtures of Gaussians ... 817
20.3.2. Learning Bayesian networks with hidden variables ... 820
20.3.3. Learning hidden Markov models ... 822
20.3.4. The general form of the EM algorithm ... 823
20.3.5. Learning Bayes net structures with hidden variables ... 824
20.4. Summary ... 825
Bibliographical and Historical Notes ... 825
Exercises ... 827
Chapter 21: Reinforcement Learning ... 830
21.1. Introduction ... 830
21.2. Passive Reinforcement Learning ... 832
21.2.1. Direct utility estimation ... 833
21.2.2. Adaptive dynamic programming ... 834
21.2.3. Temporal-difference learning ... 836
21.3. Active Reinforcement Learning ... 839
21.3.1. Exploration ... 839
21.3.2. Learning an action-utility function ... 842
21.4. Generalization in Reinforcement Learning ... 845
21.5. Policy Search ... 848
21.6. Applications of Reinforcement Learning ... 850
21.6.1. Applications to game playing ... 850
21.6.2. Application to robot control ... 851
21.7. Summary ... 853
Bibliographical and Historical Notes ... 854
Exercises ... 858
Part VI: Communicating, perceiving, and acting
Chapter 22: Natural Language Processing ... 860
22.1. Language Models ... 860
22.1.1 N-gram character models ... 861
22.1.2. Smoothing n-gram models ... 862
22.1.3. Model evaluation ... 863
22.1.4 N-gram word models ... 864
22.2. Text Classification ... 865
22.2.1. Classification by data compression ... 866
22.3. Information Retrieval ... 867
22.3.1. IR scoring functions ... 868
22.3.2. IR system evaluation ... 869
22.3.3. IR refinements ... 869
22.3.4. The PageRank algorithm ... 870
22.3.5. The HITS algorithm ... 872
22.3.6. Question answering ... 872
22.4. Information Extraction ... 873
22.4.1. Finite-state automata for information extraction ... 874
22.4.2. Probabilistic models for information extraction ... 876
22.4.3. Conditional random fields for information extraction ... 878
22.4.4. Ontology extraction from large corpora ... 879
22.4.5. Automated template construction ... 880
22.4.6. Machine reading ... 881
22.5. Summary ... 882
Bibliographical and Historical Notes ... 883
Exercises ... 885
Chapter 23: Natural Language for Communication ... 888
23.1. Phrase Structure Grammars ... 888
23.1.1. The lexicon of E0 ... 890
23.1.2. The Grammar of E0 ... 890
23.2. Syntactic Analysis (Parsing) ... 892
23.2.1. Learning probabilities for PCFGs ... 895
23.2.2. Comparing context-free and Markov models ... 896
23.3. Augmented Grammars and Semantic Interpretation ... 897
23.3.1. Lexicalized PCFGs ... 897
23.3.2. Formal definition of augmented grammar rules ... 898
23.3.3. Case agreement and subject--verb agreement ... 899
23.3.4. Semantic interpretation ... 900
23.3.5. Complications ... 902
23.4. Machine Translation ... 907
23.4.1. Machine translation systems ... 908
23.4.2. Statistical machine translation ... 909
23.5. Speech Recognition ... 912
23.5.1. Acoustic model ... 914
23.5.2. Language model ... 917
23.5.3. Building a speech recognizer ... 917
23.6. Summary ... 918
Bibliographical and Historical Notes ... 919
Exercises ... 923
Chapter 24: Perception ... 928
24.1. Image Formation ... 929
24.1.1. Images without lenses: The pinhole camera ... 929
24.1.2. Lens systems ... 931
24.1.3. Scaled orthographic projection ... 932
24.1.4. Light and shading ... 932
24.1.5. Color ... 935
24.2. Early Image-Processing Operations ... 935
24.2.1. Edge detection ... 936
24.2.2. Texture ... 939
24.2.3. Optical flow ... 939
24.2.4. Segmentation of images ... 941
24.3. Object Recognition by Appearance ... 942
24.3.1. Complex appearance and pattern elements ... 944
24.3.2. Pedestrian detection with HOG features ... 945
24.4. Reconstructing the 3D World ... 947
24.4.1. Motion parallax ... 948
24.4.2. Binocular stereopsis ... 949
24.4.3. Multiple views ... 951
24.4.4. Texture ... 951
24.4.5. Shading ... 952
24.4.6. Contour ... 953
24.4.7. Objects and the geometric structure of scenes ... 954
24.5. Object Recognition from Structural Information ... 957
24.5.1. The geometry of bodies: Finding arms and legs ... 958
24.5.2. Coherent appearance: Tracking people in video ... 959
24.6. Using Vision ... 961
24.6.1. Words and pictures ... 962
24.6.2. Reconstruction from many views ... 962
24.6.3. Using vision for controlling movement ... 963
24.7. Summary ... 965
Bibliographical and Historical Notes ... 966
Exercises ... 969
Chapter 25: Robotics ... 971
25.1. Introduction ... 971
25.2. Robot Hardware ... 973
25.2.1. Sensors ... 973
25.2.2. Effectors ... 975
25.3. Robotic Perception ... 978
25.3.1. Localization and mapping ... 979
25.3.2. Other types of perception ... 984
25.3.3. Machine learning in robot perception ... 985
25.4. Planning to Move ... 986
25.4.1. Configuration space ... 986
25.4.2. Cell decomposition methods ... 989
25.4.3. Modified cost functions ... 991
25.4.4. Skeletonization methods ... 991
25.5. Planning Uncertain Movements ... 993
25.5.1. Robust methods ... 994
25.6. Moving ... 997
25.6.1. Dynamics and control ... 997
25.6.2. Potential-field control ... 999
25.6.3. Reactive control ... 1001
25.6.4. Reinforcement learning control ... 1002
25.7. Robotic Software Architectures ... 1003
25.7.1. Subsumption architecture ... 1003
25.7.2. Three-layer architecture ... 1004
25.7.3. Pipeline architecture ... 1005
25.8. Application Domains ... 1006
25.9. Summary ... 1010
Bibliographical and Historical Notes ... 1011
Exercises ... 1014
Part VII: Conclusions
Chapter 26: Philosophical Foundations ... 1020
26.1. Weak AI: Can Machines Act Intelligently? ... 1020
26.1.1. The argument from disability ... 1021
26.1.2. The mathematical objection ... 1022
26.1.3. The argument from informality ... 1024
26.2. Strong AI: Can Machines Really Think? ... 1026
26.2.1. Mental states and the brain in a vat ... 1028
26.2.2. Functionalism and the brain replacement experiment ... 1029
26.2.3. Biological naturalism and the Chinese Room ... 1031
26.2.4. Consciousness, qualia, and the explanatory gap ... 1033
26.3. The Ethics and Risks of Developing Artificial Intelligence ... 1034
26.4. Summary ... 1040
Bibliographical and Historical Notes ... 1040
Exercises ... 1043
Chapter 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
Chapter A: Mathematical background ... 1053
A.1. Complexity Analysis and O() Notation ... 1053
A.1.1. Asymptotic analysis ... 1053
A.1.2. NP and inherently hard problems ... 1054
A.2. Vectors, Matrices, and Linear Algebra ... 1055
A.3. Probability Distributions ... 1057
Bibliographical and Historical Notes ... 1059
Chapter B: Notes on Languages and Algorithms ... 1060
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 ... 1109