Artificial intelligence illuminated

Cover......Page 1
Title Page......Page 3
Who Should Read This Book......Page 7
How to Read This Book......Page 8
Acknowledgments......Page 10
Contents......Page 11
Part 1: Introduction to Artificial Intelligence......Page 29
1.1 Introduction......Page 31
1.2 What Is Artificial Intelligence?......Page 32
1.3 Strong Methods and Weak Methods......Page 33
1.4 From Aristotle to Babbage......Page 34
1.5 Alan Turing and the 1950s......Page 35
1.6 The 1960s to the 1990s......Page 37
1.7 Philosophy......Page 38
1.8 Linguistics......Page 39
1.10 AI Programming Languages......Page 40
1.10.1 PROLOG......Page 41
1.10.2 LISP......Page 42
1.11 Chapter Summary......Page 43
1.12 Review Questions......Page 44
1.13 Further Reading......Page 45
2.1 Introduction......Page 47
2.2 The Chinese Room......Page 48
2.3 HAL—Fantasy or Reality?......Page 49
2.4 AI in the 21st Century......Page 51
2.6 Review Questions......Page 52
2.7 Further Reading......Page 53
3.1 Introduction......Page 55
3.2 The Need for a Good Representation......Page 56
3.3 Semantic Nets......Page 57
3.4 Inheritance......Page 59
3.5 Frames......Page 60
3.5.2 Inheritance......Page 62
3.5.3 Slots as Frames......Page 63
3.5.4 Multiple Inheritance......Page 64
3.5.5 Procedures......Page 65
3.5.7 Implementation......Page 66
3.5.9 Representational Adequacy......Page 68
3.6 Object-Oriented Programming......Page 69
3.7 Search Spaces......Page 70
3.8 Semantic Trees......Page 72
3.9 Search Trees......Page 74
3.9.1 Example 1: Missionaries and Cannibals......Page 75
3.9.2 Improving the Representation......Page 77
3.9.3 Example 2: The Traveling Salesman......Page 78
3.9.4 Example 3: The Towers of Hanoi......Page 82
3.9.5 Example 4: Describe and Match......Page 84
3.11 Problem Reduction......Page 85
3.12 Goal Trees......Page 86
3.12.1 Top Down or Bottom Up?......Page 88
3.12.3 Example 1: Map Coloring......Page 89
3.12.4 Example 2: Proving Theorems......Page 90
3.12.6 Example 4: Games......Page 91
3.13 Chapter Summary......Page 92
3.15 Exercises......Page 93
3.16 Further Reading......Page 94
Part 2: Search......Page 97
4.1 Introduction......Page 99
4.2 Problem Solving as Search......Page 100
4.3 Data-Driven or Goal-Driven Search......Page 101
4.4 Generate and Test......Page 102
4.5 Depth-First Search......Page 103
4.6 Breadth-First Search......Page 104
4.7.1 Complexity......Page 106
4.7.3 Optimality......Page 107
4.8 Why Humans Use Depth-First Search......Page 108
4.8.2 Example 2: Searching for a Gift......Page 109
4.9 Implementing Depth-First and Breadth-First Search......Page 111
4.11 Depth-First Iterative Deepening......Page 116
4.12 Using Heuristics for Search......Page 118
4.12.1 Informed and Uninformed Methods......Page 119
4.12.3 The 8-puzzle......Page 120
4.12.4 Monotonicity......Page 123
4.12.5 Example: The Modified Traveling Salesman Problem......Page 124
4.13.1 Steepest Ascent Hill Climbing......Page 126
4.13.2 Foothills, Plateaus, and Ridges......Page 129
4.14 Best-First Search......Page 131
4.15 Beam Search......Page 133
4.16 Identifying Optimal Paths......Page 135
4.16.1 A* Algorithms......Page 136
4.16.2 Uniform Cost Search......Page 137
4.16.4 Example: The Knapsack Problem......Page 138
4.17 Chapter Summary......Page 140
4.18 Review Questions......Page 141
4.19 Exercises......Page 142
4.20 Further Reading......Page 143
5.1 Introduction......Page 145
5.2 Constraint Satisfaction Search......Page 146
5.4 Most-Constrained Variables......Page 149
5.5 Example: Cryptographic Problems......Page 150
5.6 Heuristic Repair......Page 151
5.7 Combinatorial Optimization Problems......Page 153
5.8.1 Exchanging Heuristics......Page 154
5.8.3 Tabu Search......Page 155
5.9 Simulated Annealing......Page 156
5.9.1 Uses of Simulated Annealing......Page 158
5.11 Real-Time A*......Page 159
5.13 Parallel Search......Page 160
5.13.1 Task Distribution......Page 162
5.13.3 Search Engines......Page 163
5.15 Nondeterministic Search......Page 164
5.17 Nonchronological Backtracking......Page 165
5.18 Chapter Summary......Page 166
5.19 Review Questions......Page 167
5.20 Exercises......Page 168
5.21 Further Reading......Page 169
6.1 Introduction......Page 171
6.2 Game Trees......Page 172
6.2.1 Rationality, Zero Sum, and Other Assumptions......Page 173
6.2.2 Evaluation Functions......Page 174
6.2.3 Searching Game Trees......Page 176
6.3 Minimax......Page 177
6.3.1 Bounded Lookahead......Page 179
6.4 Alpha–Beta Pruning......Page 181
6.4.1 The Effectiveness of Alpha–Beta Pruning......Page 182
6.4.2 Implementation......Page 183
6.5 Checkers......Page 187
6.5.1 Chinook......Page 188
6.5.2 Chinook’s Databases......Page 189
6.5.3 Chinook’s Evaluation Function......Page 190
6.5.5 Limitations of Minimax......Page 191
6.6 Chess......Page 192
6.7 Go......Page 193
6.9 Games of Chance......Page 194
6.10 Chapter Summary......Page 195
6.11 Review Questions......Page 196
6.12 Exercises......Page 197
6.13 Further Reading......Page 198
Part 3: Knowledge Representation and Automated Reasoning......Page 201
7.1 Introduction......Page 203
7.3 Why Logic Is Used in Artificial Intelligence......Page 204
7.4 Logical Operators......Page 205
7.5 Translating between English and Logic Notation......Page 206
7.6.1 Not......Page 209
7.6.3 Or......Page 210
7.6.4 Implies......Page 211
7.7 Complex Truth Tables......Page 212
7.8 Tautology......Page 214
7.9 Equivalence......Page 215
7.10.1 Syntax......Page 217
7.10.2 Semantics......Page 218
7.11.2 ∧-Elimination......Page 219
7.11.5 Reductio Ad Absurdum......Page 220
7.11.8 Example 1......Page 221
7.11.10 Example 3......Page 222
7.12 The Deduction Theorem......Page 223
7.13.1 Syntax......Page 224
7.13.2 Relationships between ∀ and ∃......Page 225
7.14 First-Order Predicate Logic......Page 227
7.17 Decidability......Page 228
7.19 Abduction and Inductive Reasoning......Page 229
7.20 Modal Logics and Possible Worlds......Page 231
7.20.1 Reasoning in Modal Logic......Page 232
7.23 Review Questions......Page 233
7.24 Exercises......Page 234
7.25 Further Reading......Page 236
8.1 Introduction......Page 237
8.2.1 Normal Forms......Page 238
8.2.2 The Resolution Rule......Page 240
8.2.3 Resolution Refutation......Page 241
8.2.4 Proof by Refutation......Page 242
8.3 Applications of Resolution......Page 244
8.4 Resolution in Predicate Logic......Page 246
8.5 Normal Forms for Predicate Logic......Page 247
8.6 Skolemization......Page 248
8.6.1 Example of Skolemization......Page 249
8.6.3 Unification......Page 250
8.6.5 Unification Algorithm......Page 252
8.6.6 Unification Example......Page 253
8.7 Resolution Algorithm......Page 254
8.8 Horn Clauses and PROLOG......Page 255
8.9 Herbrand Universes......Page 257
8.9.1 The Herbrand Base......Page 258
8.9.2 Herbrand Interpretations......Page 259
8.9.3 Example......Page 260
8.10 Resolution for Problem Solving......Page 261
8.11 Chapter Summary......Page 265
8.13 Exercises......Page 266
8.14 Further Reading......Page 267
9.1 Introduction......Page 269
9.2 Rules for Knowledge Representation......Page 270
9.3 Rule-Based Systems......Page 271
9.3.1 Forward Chaining......Page 272
9.3.2 Conflict Resolution......Page 274
9.3.3 Meta Rules......Page 275
9.3.4 Backward Chaining......Page 276
9.3.5 Comparing Forward and Backward Chaining......Page 277
9.4.1 The People Involved in an Expert System......Page 279
9.4.2 Architecture of an Expert System......Page 280
9.4.4 The Rete Algorithm......Page 281
9.4.5 Knowledge Engineering......Page 282
9.5 CLIPS (C Language Integrated Production System)......Page 283
9.6 Backward Chaining in Rule-Based Expert Systems......Page 285
9.7 CYC......Page 287
9.8 Chapter Summary......Page 288
9.11 Further Reading......Page 289
Part 4: Machine Learning......Page 293
10.1 Introduction......Page 295
10.2 Training......Page 296
10.4 Learning Concepts......Page 298
10.5 General-to-Specific Ordering......Page 300
10.5.1 A Simple Learning Algorithm......Page 301
10.6 Version Spaces......Page 302
10.7 Candidate Elimination......Page 303
10.9 Decision-Tree Induction......Page 304
10.9.1 Information Gain......Page 306
10.9.2 Example......Page 307
10.9.3 Inductive Bias of ID3......Page 309
10.10 The Problem of Overfitting......Page 310
10.11 The Nearest Neighbor Algorithm......Page 311
10.12 Learning Neural Networks......Page 312
10.14 Unsupervised Learning......Page 313
10.16 Chapter Summary......Page 314
10.17 Review Questions......Page 315
10.19 Further Reading......Page 316
11.1 Introduction......Page 319
11.2.1 Biological Neurons......Page 320
11.2.2 Artificial Neurons......Page 321
11.3 Perceptrons......Page 323
11.4 Multilayer Neural Networks......Page 328
11.4.1 Backpropagation......Page 330
11.4.2 Improving the Performance of Backpropagation......Page 333
11.5 Recurrent Networks......Page 334
11.5.1 Hopfield Networks......Page 335
11.5.2 Bidirectional Associative Memories (BAMs)......Page 341
11.6.1 Kohonen Maps......Page 344
11.6.2 Kohonen Map Example......Page 346
11.6.3 Hebbian Learning......Page 348
11.7 Evolving Neural Networks......Page 349
11.9 Review Questions......Page 350
11.10 Exercises......Page 351
11.11 Further Reading......Page 352
12.1 Introduction......Page 355
12.2 Probabilistic Reasoning......Page 356
12.4 Bayes’ Theorem......Page 358
12.4.1 Example: Medical Diagnosis......Page 359
12.4.2 Example: Witness Reliability......Page 360
12.4.3 Comparing Conditional Probabilities......Page 362
12.4.4 Normalization......Page 363
12.5 Simple Bayesian Concept Learning......Page 365
12.6 Bayesian Belief Networks......Page 367
12.6.1 Example: Life at College......Page 370
12.7 The Noisy-V Function......Page 374
12.8 Bayes’ Optimal Classifier......Page 377
12.9 The Naïve Bayes Classifier......Page 379
12.10 Collaborative Filtering......Page 384
12.11 Chapter Summary......Page 385
12.12 Review Questions......Page 386
12.14 Further Reading......Page 387
13.1 Introduction......Page 391
13.2 What Is Life?......Page 392
13.3 Emergent Behavior......Page 393
13.4 Finite State Automata......Page 394
13.5.1 Conway’s Life......Page 396
13.5.2 One-Dimensional Cellular Automata......Page 398
13.6 Self-Reproducing Systems......Page 399
13.7 Evolution......Page 400
13.8 Evolution Strategies......Page 401
13.9 Genetic Programming......Page 402
13.10 Evolutionary Programming......Page 403
13.11 L-Systems......Page 404
13.12 Classifier Systems......Page 405
13.13 Artificial Immune Systems......Page 409
13.15 Review Questions......Page 410
13.16 Further Reading......Page 411
14.1 Introduction......Page 415
14.2 Representations......Page 416
14.3 The Algorithm......Page 417
14.5 Crossover......Page 418
14.7 Termination Criteria......Page 420
14.8 Optimization of a Mathematic Function......Page 421
14.9 Why Genetic Algorithms Work......Page 424
14.9.1 Schemata......Page 425
14.9.2 How Reproduction Affects Schemata......Page 427
14.9.3 How Mutation and Crossover Affect Schemata......Page 429
14.9.4 The Building-Block Hypothesis......Page 431
14.9.5 Deception......Page 432
14.10 Messy Genetic Algorithms......Page 433
14.11 Prisoner’s Dilemma......Page 434
14.11.1 Strategy Representation......Page 435
14.11.2 Possible Strategies......Page 436
14.11.4 Choice of Opponents......Page 438
14.12 Diversity......Page 439
14.13 Evolving Pictures......Page 440
14.14 Predators and Co-evolution......Page 441
14.16 Chapter Summary......Page 442
14.17 Review Questions......Page 443
14.18 Exercises......Page 444
14.19 Further Reading......Page 445
Part 5: Planning......Page 447
15.1 Introduction......Page 449
15.2 Planning as Search......Page 451
15.3 Situation Calculus......Page 454
15.4 The Frame Problem......Page 455
15.5 Means–Ends Analysis......Page 456
15.6 Chapter Summary......Page 458
15.8 Exercises......Page 459
15.9 Further Reading......Page 460
16.1 Introduction......Page 461
16.2 STRIPS......Page 462
16.2.1 Planning and Executing......Page 463
16.2.2 Operators......Page 464
16.2.3 Implementation of STRIPS......Page 465
16.2.4 Example: STRIPS......Page 466
16.2.5 Example: STRIPS and Resolution......Page 469
16.3 The Sussman Anomaly......Page 471
16.4 Partial Order Planning......Page 472
16.5 The Principle of Least Commitment......Page 475
16.6 Propositional Planning......Page 476
16.7 SAT Planning......Page 478
16.8 Planning Graphs......Page 479
16.8.1 GraphPlan......Page 482
16.9 ADL and PDDL......Page 483
16.11 Dynamic World Planning......Page 484
16.12 Case-Based Planning Systems......Page 485
16.13 Planning and Scheduling......Page 486
16.14 Chapter Summary......Page 487
16.15 Review Questions......Page 488
16.17 Further Reading......Page 489
Part 6: Advanced Topics......Page 491
17.1 Introduction......Page 493
17.2 Representations and Semantics......Page 496
17.3 The Blackboard Architecture......Page 497
17.3.1 Implementation......Page 499
17.4 Scripts......Page 500
17.5 Copycat Architecture......Page 502
17.6 Nonmonotonic Reasoning......Page 504
17.6.2 Default Reasoning......Page 505
17.6.3 Truth Maintenance Systems......Page 506
17.6.6 Circumscription......Page 508
17.6.7 Abductive Reasoning......Page 510
17.6.8 The Dempster–Shafer Theory......Page 511
17.6.9 MYCIN and Certainty Factors......Page 513
17.7.1 Temporal Logic......Page 515
17.7.2 Using Temporal Logic......Page 517
17.7.3 Event Calculus......Page 518
17.7.4 Mental Situation Calculus......Page 520
17.8 Knowledge Engineering......Page 522
17.9 Case-Based Reasoning......Page 523
17.10 Chapter Summary......Page 524
17.11 Review Questions......Page 525
17.12 Exercises......Page 526
17.13 Further Reading......Page 528
18.1 Introduction......Page 531
18.3 Linguistic Variables......Page 532
18.4 Fuzzy Sets......Page 533
18.4.1 Fuzzy Set Membership Functions......Page 535
18.4.2 Fuzzy Set Operators......Page 536
18.4.3 Hedges......Page 538
18.5 Fuzzy Logic......Page 539
18.6 Fuzzy Logic as Applied to Traditional Logical Paradoxes......Page 543
18.8 Fuzzy Inference......Page 544
18.9 Fuzzy Expert Systems......Page 550
18.9.1 Defining the Fuzzy Sets......Page 551
18.9.2 Defining Fuzzy Rules......Page 555
18.9.3 Relating Observations to Fuzzy Sets......Page 556
18.9.4 Evaluating Each Case for the Fuzzy Rules......Page 558
18.9.5 Defuzzification......Page 559
18.10.1 Neuro-fuzzy Systems......Page 562
18.10.3 Layer 2: The Fuzzification Layer......Page 564
18.10.5 Layer 4: The Output Membership Function Layer......Page 565
18.10.7 How the System Learns......Page 566
18.12 Review Questions......Page 567
18.14 Further Reading......Page 568
19.1 Introduction......Page 571
19.2.1 Intelligence......Page 572
19.2.4 Cooperation......Page 573
19.3 Agent Classifications......Page 574
19.4 Reactive Agents......Page 575
19.4.1 Goal-based Agents......Page 576
19.4.3 Utility Functions......Page 577
19.5 Interface Agents......Page 579
19.6 Mobile Agents......Page 580
19.7 Information Agents......Page 581
19.8 Multiagent Systems......Page 582
19.10.1 Subsumption Architecture......Page 584
19.10.3 Other Architectures......Page 586
19.11 Accessibility......Page 588
19.12 Learning Agents......Page 589
19.13 Robotic Agents......Page 590
19.14 Braitenberg Vehicles......Page 591
19.15 Chapter Summary......Page 593
19.16 Review Questions......Page 594
19.18 Further Reading......Page 595
20.1 Introduction......Page 599
20.2 Natural Language Processing......Page 601
20.2.1 Morphological Analysis......Page 602
20.2.2 BNF......Page 603
20.2.3 Grammars......Page 607
20.2.4 Parsing: Syntactic Analysis......Page 609
20.2.5 Transition Networks......Page 610
20.2.7 Chart Parsing......Page 613
20.2.8 Semantic Analysis......Page 616
20.2.9 Ambiguity and Pragmatic Analysis......Page 617
20.3 Machine Translation......Page 620
20.3.1 Language Identification......Page 621
20.4 Information Retrieval......Page 622
20.4.1 Stemming......Page 624
20.4.2 Precision and Recall......Page 626
20.5 Chapter Summary......Page 627
20.7 Exercises......Page 628
20.8 Further Reading......Page 629
21.1 Introduction......Page 633
21.2 Human Vision......Page 634
21.3 Image Processing......Page 636
21.3.1 Edge Detection......Page 637
21.3.2 Convolution and the Canny Edge Detector......Page 639
21.3.3 Segmentation......Page 640
21.3.4 Classifying Edges in Line Drawings......Page 641
21.4 Using Texture......Page 643
21.4.1 Identifying Textures......Page 644
21.4.3 Determining Shape and Orientation from Texture......Page 648
21.5 Interpreting Motion......Page 651
21.6 Making Use of Vision......Page 653
21.7 Face Recognition......Page 654
21.8 Chapter Summary......Page 656
21.10 Exercises......Page 657
21.11 Further Reading......Page 658
A......Page 661
B......Page 664
C......Page 667
D......Page 675
E......Page 678
F......Page 680
G......Page 684
H......Page 686
I......Page 689
J......Page 691
L......Page 692
M......Page 694
N......Page 698
O......Page 701
P......Page 702
R......Page 707
S......Page 711
T......Page 717
U......Page 720
W......Page 721
Z......Page 723
B......Page 725
C......Page 727
D......Page 729
F......Page 730
G......Page 731
H......Page 732
J......Page 733
K......Page 734
L......Page 736
M......Page 737
N......Page 739
P......Page 740
R......Page 741
S......Page 742
V......Page 745
Z......Page 746
A......Page 747
B......Page 748
C......Page 749
D......Page 751
E......Page 752
F......Page 753
G......Page 754
I......Page 755
K......Page 756
L......Page 757
M......Page 758
N......Page 759
P......Page 760
R......Page 762
S......Page 763
T......Page 765
U......Page 766
Z......Page 767