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