Artificial Intelligence | PDF下载|ePub下载

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
· · · · · ·