Preface
Who Should Read This Book
This book is intended for students of computer science at the college level,
or students of other subjects that cover Artificial Intelligence. It also is
intended to be an interesting and relevant introduction to the subject for
other students or individuals who simply have an interest in the subject.
The book assumes very little knowledge of computer science, but does
assume some familiarity with basic concepts of algorithms and computer
systems. Data structures such as trees, graphs, and stacks are explained
briefly in this book, but if you do not already have some familiarity with
these concepts, you should probably seek out a suitable book on algorithms
or data structures.
It would be an advantage to have some experience in a programming language
such as C++ or Java, or one of the languages commonly used in Artificial
Intelligence research, such as PROLOG and LISP, but this experience
is neither necessary nor assumed.
Many of the chapters include practical exercises that require the reader to
develop an algorithm or program in a programming language of his or her
choice. Most readers should have no difficulty with these exercises. However,
if any reader does not have the necessary skills he or she simply should
describe in words (or in pseudocode) how his or her programs work, giving
as much detail as possible.
How to Read This Book
This book can be read in several ways. Some readers will choose to read the
chapters through in order from Chapter 1 through Chapter 21.Any chapter
that uses material which is presented in another chapter gives a clear reference
to that chapter, and readers following the book from start to finish
should not need to jump forward at any point, as the chapter dependencies
tend to work in a forward direction.
Another perfectly reasonable way to use this book is as a reference.When a
reader needs to know more about a particular subject, he or she can pick up
this book and select the appropriate chapter or chapters, and can be illuminated
on the subject (at least, that is the author’s intent!)
Chapter 12 contains a diagram that shows how the dependencies between
chapters work (Section 12.6.2). This diagram shows, for example, that if a
reader wants to read Chapter 8, it would be a good idea to already have read
Chapter 7.
This book is divided into six parts, each of which is further divided into a
number of chapters. The chapters are laid out as follows:
Part 1: Introduction to Artificial Intelligence
Chapter 1: A Brief History of Artificial Intelligence
Chapter 2: Uses and Limitations
Chapter 3: Knowledge Representation
Part 2: Search
Chapter 4: Search Methodologies
Chapter 5: Advanced Search
Chapter 6: Game Playing
Part 3: Logic
Chapter 7: Propositional and Predicate Logic
Chapter 8: Inference and Resolution for Problem Solving
Chapter 9: Rules and Expert Systems
vi Preface
Part 4: Machine Learning
Chapter 10: Introduction to Machine Learning
Chapter 11: Neural Networks
Chapter 12: Probabilistic Reasoning and Bayesian Belief Networks
Chapter 13: Artificial Life: Learning through Emergent Behavior
Chapter 14: Genetic Algorithms
Part 5: Planning
Chapter 15: Introduction to Planning
Chapter 16: Planning Methods
Part 6: Advanced Topics
Chapter 17: Advanced Knowledge Representation
Chapter 18: Fuzzy Reasoning
Chapter 19: Intelligent Agents
Chapter 20: Understanding Language
Chapter 21:Machine Vision
Each chapter includes an introduction that explains what the chapter covers,
a summary of the chapter, some exercises and review questions, and
some suggestions for further reading. There is a complete bibliography at
the back of the book.
This book also has a glossary, which includes a brief definition of most of
the important terms used in this book.When a new term is introduced in
the text it is highlighted in bold, and most of these words are included in
the glossary. The only such terms that are not included in the glossary are
the ones that are defined in the text, but that are not used elsewhere in the
book.
The use of third person pronouns is always a contentious issue for authors
of text books, and this author has chosen to use he and she interchangeably.
In some cases the word “he” is used, and in other cases “she.” This is not
intended to follow any particular pattern, or to make any representations
The first few chapters of this book provide introductory material, explainingabout the genders, but simply is in the interests of balance.
the nature of Artificial Intelligence and providing a historical background,
as well as describing some of the connections with other
disciplines. Some readers will prefer to skip these chapters, but it is advisable
to at least glance through Chapter 3 to ensure that you are familiar
with the concepts of that chapter, as they are vital to the understanding of
most of the rest of the book.
Acknowledgments
Although I wrote this book single-handedly, it was not without help. I
would like to thank, in chronological order, Frank Abelson; Neil Salkind
and everyone at Studio B; Michael Stranz, Caroline Senay, Stephen
Solomon, and Tracey Chapman at Jones & Bartlett; also a number of people
who read chapters of the book: Martin Charlesworth, Patrick Coyle,
Peter and Petra Farrell, Robert Kealey, Geoffrey Price, Nick Pycraft, Chris
Swannack, Edwin Young, my parents, Tony and Frances, and of course
Erin—better late than never.
Thanks also to:
The MIT Press for the excerpt from ‘Learning in Multiagent Systems’ by
Sandip Sen and Gerhard Weiss, © 2001, The MIT Press.
The MIT Press for the excerpt from ‘Adaptation in Natural and Artificial
Systems’ by John H. Holland, © 1992, The MIT Press.
The MIT Press for the excerpt from ‘The Artificial Life Roots of Artificial
Intelligence’ by Luc Steels, © 1994, the Massachusetts Institute of Technology.
The IEEE for the excerpt from ‘Steps Towards Artificial Intelligence’ by
Marvin Minsky, © 2001, IEEE.
I have attempted to contact the copyright holders of all copyrighted quotes
used in this book. If I have used any quotes without permission, then this
was inadvertent, and I apologize. I will take all measures possible to rectify
the situation in future printings of the book.
Contents
PA R T 1 Introduction to Artificial Intelligence 1Chapter 1 A Brief History of Artificial Intelligence 3
1.1 Introduction 3
1.2 What Is Artificial Intelligence? 4
1.3 Strong Methods and Weak Methods 5
1.4 From Aristotle to Babbage 6
1.5 Alan Turing and the 1950s 7
1.6 The 1960s to the 1990s 9
1.7 Philosophy 10
1.8 Linguistics 11
1.9 Human Psychology and Biology 12
1.10 All Programming Languages 12
1.10.1 PROLOG 13
1.10.2 LISP 14
1.11 Chapter Summary 15
1.12 Review Questions 16
1.13 Further Reading 17
Chapter 2 Uses and Limitations 19
2.1 Introduction 19
2.2 The Chinese Room 20
2.3 HAL—Fantasy or Reality? 21
2.4 AI in the 21st Century 23
2.5 Chapter Summary 24
2.6 Review Questions 24
2.7 Further Reading 25
Chapter 3 Knowledge Representation 27
3.1 Introduction 27
3.2 The Need for a Good Representation 28
3.3 Semantic Nets 29
3.4 Inheritance 31
3.5 Frames 32
3.5.1 Why Are Frames Useful? 34
3.5.2 Inheritance 34
3.5.3 Slots as Frames 35
3.5.4 Multiple Inheritance 36
3.5.5 Procedures 37
3.5.6 Demons 38
3.5.7 Implementation 38
3.5.8 Combining Frames with Rules 40
3.5.9 Representational Adequacy 40
3.6 Object-Oriented Programming 41
3.7 Search Spaces 42
3.8 Semantic Trees 44
3.9 Search Trees 46
3.9.1 Example 1:Missionaries and Cannibals 47
3.9.2 Improving the Representation 49
3.9.3 Example 2: The Traveling Salesman 50
3.9.4 Example 3: The Towers of Hanoi 54
3.9.5 Example 4: Describe and Match 56
3.10 Combinatorial Explosion 57
3.11 Problem Reduction 57
3.12 Goal Trees 58
3.12.1 Top Down or Bottom Up? 60
3.12.2 Uses of Goal Trees 61
Example 1:Map Coloring
Example 2: Proving Theorems
Example 3: Parsing Sentences 63
Example 4: Games
3.13 Chapter Summary 64
3.14 Review Questions 65
3.15 Exercises 65
3.16 Further Reading 66
PA R T 2 Search 69
Chapter 4 Search Methodologies 71
4.1 Introduction 71
4.2 Problem Solving as Search 72
4.3 Data-Driven or Goal-Driven Search 73
4.4 Generate and Test 74
4.5 Depth-First Search 75
4.6 Breadth-First Search 76
4.7 Properties of Search Methods 78
4.7.1 Complexity 78
4.7.2 Completeness 79
4.7.3 Optimality 79
4.7.4 Irrevocability 80
4.8 Why Humans Use Depth-First Search? 80
4.8.1 Example 1: Traversing a Maze 81
4.8.2 Example 2: Searching for a Gift 81
4.9 Implementing Depth-First and Breadth-First Search 83
4.10 Example:Web Spidering 88
4.11 Depth-First Iterative Deepening 88
4.12 Using Heuristics for Search 90
4.12.1 Informed and Uninformed Methods 91
4.12.2 Choosing a Good Heuristic 92
4.12.3 The 8-Puzzle 92
4.12.4 Monotonicity 95
4.12.5 Example: The Modified Traveling Salesman
Problem 96
4.13 Hill Climbing 98
4.13.1 Steepest Ascent Hill Climbing 98
4.13.2 Foothills, Plateaus, and Ridges 101
4.14 Best-First Search 104
4.15 Beam Search 106
4.16 Identifying Optimal Paths 107
4.16.1 A* Algorithms 108
4.16.2 Uniform Cost Search 110
4.16.3 Greedy Search 111
4.16.4 Example: The Knapsack Problem 111
4.17 Chapter Summary 113
4.18 Review Questions 114
4.19 Exercises 115
4.20 Further Reading 116
Chapter 5 Advanced Search 117
5.1 Introduction 117
5.2 Constraint Satisfaction Search 118
5.3 Forward Checking 121
5.4 Most-Constrained Variables 121
5.5 Example: Cryptographic Problems 122
5.6 Heuristic Repair 123
5.7 Combinatorial Optimization Problems 125
5.8 Local Search and Metaheuristics 126
5.8.1 Exchanging Heuristics 126
5.8.2 Iterated Local Search 127
5.8.3 Tabu Search 127
5.8.4 Ant Colony Optimization 128
5.9 Simulated Annealing 128
5.9.1 Uses of Simulated Annealing 130
5.10 Genetic Algorithms for Search 131
5.11 Real-Time A* 131
5.12 Iterative-Deepening A* (IDA*) 132
5.13 Parallel Search 132
5.13.1 Task Distribution 134
5.13.2 Tree Ordering 135
5.13.3 Search Engines 135
5.14 Bidirectional Search 136
5.15 Nondeterministic Search 136
5.16 Island-Driven Search 137
5.17 Nonchronological Backtracking 137
5.18 Chapter Summary 138
5.19 Review Questions 139
5.20 Exercises 140
5.21 Further Reading 141
Chapter 6 Game Playing 143
6.1 Introduction 143
6.2 Game Trees 144
6.2.1 Rationality, Zero Sum, and Other
Assumptions 145
6.2.2 Evaluation Functions 146
6.2.3 Searching Game Trees 148
6.3 Minimax 149
6.3.1 Bounded Lookahead 151
6.4 Alpha-Beta Pruning 153
6.4.1 The Effectiveness of Alpha-Beta Pruning 154
6.4.2 Implementation 155
6.5 Checkers 159
6.5.1 Chinook 160
6.5.2 Chinook’s Databases 161
6.5.3 Chinook’s Evaluation Function 162
6.5.4 Forward Pruning 163
6.5.5 Limitations of Minimax 163
6.5.6 Blondie 24 164
6.6 Chess 164
6.7 Go 165
6.7.1 Go-Moku 166
6.8 Othello (Reversi) 166
6.9 Games of Chance 166
6.9.1 Expectiminimax 167
6.10 Chapter Summary 167
6.11 Review Questions 168
6.12 Exercises 169
6.13 Further Reading 170
PA R T 3 Knowledge Representation and Automated
Reasoning 173
Chapter 7 Propositional and Predicate Logic 175
7.1 Introduction 175
7.2 What Is Logic? 176
7.3 Why Logic Is Used in Artificial Intelligence 176
7.4 Logical Operators 177
7.5 Translating between English and Logic Notation 178
7.6 Truth Tables 181
7.6.1 Not 181
7.6.2 And 182
7.6.3 Or 182
7.6.4 Implies 183
7.6.5 iff 184
7.7 Complex Truth Tables 184
7.8 Tautology 186
7.9 Equivalence 187
7.10 Propositional Logic 189
7.10.1 Syntax 189
7.10.2 Semantics 190
7.11 Deduction 191
7.11.1 ^-Introduction 191
7.11.2 ^-Eliminations 191
7.11.3 Or-Introduction 192
7.11.4 ?Elimination 192
7.11.5 Reductio Ad Absurdum 192
7.11.6 ?Introduction 193
7.11.7 ¬¬Elimination 193
7.11.8 Example 1 193
7.11.9 Example 2 194
7.11.10 Example 3 194
7.11.11 Example 4 195
7.12 The Deduction Theorem 195
7.13 Predicate Calculus 196
7.13.1 Syntax 196
7.13.2 Relationships between " and $ 197
7.13.3 Functions 199
7.14 First-Order Predicate Logic 199
7.15 Soundness 200
7.16 Completeness 200
7.17 Decidability 200
7.18 Monotonicity 201
7.19 Abduction and Inductive Reasoning 201
7.20 Modal Logics and Possible Worlds 203
7.20.1 Reasoning in Modal Logic 204
7.21 Dealing with Change 205
7.22 Chapter Summary 205
7.23 Review Questions 205
7.24 Exercises 206
7.25 Further Reading 208
Chapter 8 Inference and Resolution for Problem Solving 209
8.1 Introduction 209
8.2 Resolution in Propositional Logic 210
8.2.1 Normal Forms 210
8.2.2 The Resolution Rule 212
8.2.3 Resolution Refutation 213
8.2.4 Proof by Refutation 214
8.3 Applications of Resolution 216
8.4 Resolution in Predicate Logic 218
8.5 Normal Forms for Predicate Logic 219
8.6 Skolemization 220
8.6.1 Example of Skolemization 221
8.6.2 Second Example of Skolemization 222
8.6.3 Unification 222
8.6.4 Most General Unifiers 224
8.6.5 Unification Algorithm 224
8.6.6 Unification Example 225
8.7 Resolution Algorithm 226
8.8 Horn Clauses and PROLOG 227
8.9 Herbrand Universes 229
8.9.1 The Herbrand Base 230
8.9.2 Herbrand Interpretations 231
8.9.3 Example 232
8.10 Resolution for Problem Solving 233
8.11 Chapter Summary 237
8.12 Review Questions 238
8.13 Exercises 238
8.14 Further Reading 239
Chapter 9 Rules and Expert Systems 241
9.1 Introduction 241
9.2 Rules for Knowledge Representation 242
9.3 Rule-Based Systems 243
9.3.1 Forward Chaining 244
9.3.2 Conflict Resolution 246
9.3.3 Meta Rules 247
9.3.4 Backward Chaining 248
9.3.5 Comparing Forward and Backward Chaining 249
9.4 Rule-Based Expert Systems 251
9.4.1 The People Involved in an Expert System 251
9.4.2 Architecture of an Expert System 252
9.4.3 The Expert Shell System 253
9.4.4 The Rete Algorithm 253
9.4.5 Knowledge Engineering 254
9.5 CLIPS (C Language Integrated Production System) 255
xvi Contents
9.6 Backward Chaining in Rule-Based Expert Systems 257
9.7 CYC 259
9.8 Chapter Summary 260
9.9 Review Questions 261
9.10 Exercises 261
9.11 Further Reading 261
PA R T 4 Machine Learning 265
Chapter 10 Introduction to Machine Learning 267
10.1 Introduction 267
10.2 Training 268
10.3 Rote Learning 270
10.4 Learning Concepts 270
10.5 General-to-Specific Ordering 272
10.5.1 A Simple Learning Algorithm 273
10.6 Version Spaces 274
10.7 Candidate Elimination 275
10.8 Inductive Bias 276
10.9 Decision-Tree Induction 276
10.9.1 Information Gain 278
10.9.2 Example 279
10.9.3 Inductive Bias of ID3 281
10.10 The Problem of Overfitting 282
10.11 The Nearest Neighbor Algorithm 283
10.12 Learning Neural Networks 284
10.13 Supervised Learning 285
10.14 Unsupervised Learning 285
10.15 Reinforcement Learning 286
10.16 Chapter Summary 286
10.17 Review Questions 287
10.18 Exercises 288
10.19 Further Reading 288
Chapter 11 Neural Networks 291
11.1 Introduction 291
11.2 Neurons 292
11.2.1 Biological Neurons 292
11.2.2 Artificial Neurons 293
11.3 Perceptrons 295
11.4 Multilayer Neural Networks 300
11.4.1 Backpropagation 302
11.4.2 Improving the Performance of
Backpropagation 305
11.5 Recurrent Networks 306
11.5.1 Hopfield Networks 307
11.5.2 Bidirectional Associative Memories (BAMs) 314
11.6 Unsupervised Learning Networks 317
11.6.1 Kohonen Maps 317
11.6.2 Kohonen Map Example 319
11.6.3 Hebbian Learning 321
11.7 Evolving Neural Networks 322
11.8 Chapter Summary 323
11.9 Review Questions 324
11.10 Exercises 325
11.11 Further Reading 326
Chapter 12 Probabilistic Reasoning and Bayesian Belief
Networks 327
12.1 Introduction 327
12.2 Probabilistic Reasoning 328
12.3 Joint Probability Distributions 330
12.4 Bayes’ Theorem 330
12.4.1 Example:Medical Diagnosis 331
12.4.2 Example:Witness Reliability 332
12.4.3 Comparing Conditional Probabilities 334
12.4.4 Normalization 335
12.5 Simple Bayesian Concept Learning 337
12.6 Bayesian Belief Networks 339
12.6.1 Example: Life at College 342
12.6.2 Example: Chapter Dependencies 346
12.7 The Noisy-V Function 346
12.8 Bayes’ Optimal Classifier 349
12.9 The Naïve Bayes Classifier 351
12.10 Collaborative Filtering 356
12.11 Chapter Summary 357
12.12 Review Questions 358
12.13 Exercises 359
12.14 Further Reading 359
Chapter 13 Artificial Life: Learning through Emergent
Behavior 363
13.1 Introduction 363
13.2 What Is Life? 364
13.3 Emergent Behavior 365
13.4 Finite State Automata 366
13.5 Cellular Automata 368
13.5.1 Conway’s Life 368
13.5.2 One-Dimensional Cellular Automata 370
13.6 Self-Reproducing Systems 371
13.7 Evolution 372
13.7.1 Ramps 373
13.8 Evolution Strategies 373
13.9 Genetic Programming 374
13.10 Evolutionary Programming 375
13.11 L-Systems 376
13.12 Classifier Systems 377
13.13 Artificial Immune Systems 381
13.14 Chapter Summary 382
13.15 Review Questions 382
13.16 Further Reading 383
Chapter 14 Genetic Algorithms 387
14.1 Introduction 387
14.2 Representations 388
14.3 The Algorithm 389
14.4 Fitness 390
14.5 Crossover 390
14.6 Mutation 392
14.7 Termination Criteria 392
14.8 Optimization of a Mathematic Function 393
14.9 Why Genetic Algorithms Work 396
14.9.1 Schemata 397
14.9.2 How Reproduction Affects Schemata 399
14.9.3 How Mutation and Crossover Affect
Schemata 401
14.9.4 The Building-Block Hypothesis 403
14.9.5 Deception 404
14.10 Messy Genetic Algorithms 405
14.11 Prisoner’s Dilemma 406
14.11.1 Strategy Representation 407
14.11.2 Possible Strategies 408
14.11.3 Evolution of Strategies 410
14.11.4 Choice of Opponents 410
14.12 Diversity 411
14.13 Evolving Pictures 412
14.14 Predators and Coevolution 413
14.15 Other Problems 414
14.16 Chapter Summary 414
14.17 Review Questions 415
14.18 Exercises 416
14.19 Further Reading 417
PA R T 5 Planning 419
Chapter 15 Introduction to Planning 421
15.1 Introduction 421
15.2 Planning as Search 423
15.3 Situation Calculus 426
15.4 The Frame Problem 427
15.5 Means-Ends Analysis 428
15.6 Chapter Summary 430
15.7 Review Questions 431
15.8 Exercises 431
15.9 Further Reading 432
Chapter 16 Planning Methods 433
16.1 Introduction 433
16.2 STRIPS 434
16.2.1 Planning and Executing 435
16.2.2 Operators 436
16.2.3 Implementation of STRIPS 437
16.2.4 Example: STRIPS 438
16.2.5 Example: STRIPS and Resolution 441
16.3 The Sussman Anomaly 443
16.4 Partial Order Planning 444
16.5 The Principle of Least Commitment 447
16.6 Propositional Planning 448
16.7 SAT Planning 450
16.8 Planning Graphs 451
16.8.1 GraphPlan 454
16.8.2 Mutex Conditions 455
16.9 ADL and PDDL 455
16.10 Probabilistic Planning 456
16.11 Dynamic World Planning 456
16.12 Case-Based Planning Systems 457
16.13 Planning and Scheduling 458
16.14 Chapter Summary 459
16.15 Review Questions 460
16.16 Exercises 461
16.17 Further Reading 461
PA R T 6 Advanced Topics 463
Chapter 17 Advanced Knowledge Representation 465
17.1 Introduction 465
17.2 Representations and Semantics 468
17.3 The Blackboard Architecture 469
17.3.1 Implementation 471
17.3.2 HEARSAY 472
17.4 Scripts 472
17.5 Copycat Architecture 474
17.6 Nonmonotonic Reasoning 476
17.6.1 Nonmonotonic Logic with the Modal
Operator 477
17.6.2 Default Reasoning 477
17.6.3 Truth Maintenance Systems 478
17.6.4 Closed-World Assumption 480
17.6.5 The Ramification Problem 480
17.6.6 Circumscription 480
17.6.7 Abductive Reasoning 482
17.6.8 The Dempster-Shafer Theory 483
17.6.9 MYCIN and Certainty Factors 485
17.7 Reasoning about Change 487
17.7.1 Temporal Logic 487
17.7.2 Using Temporal Logic 488
17.7.3 Event Calculus 490
17.7.4 Mental Situation Calculus 492
17.8 Knowledge Engineering 494
17.9 Case-Based Reasoning 495
17.10 Chapter Summary 496
17.11 Review Questions 497
17.12 Exercises 498
17.13 Further Reading 500
Chapter 18 Fuzzy Reasoning 503
18.1 Introduction 503
18.2 Bivalent and Multivalent Logics 504
18.3 Linguistic Variables 504
18.4 Fuzzy Sets 505
18.4.1 Fuzzy Set Membership Functions 507
18.4.2 Fuzzy Set Operators 508
18.4.3 Hedges 510
18.5 Fuzzy Logic 511
18.6 Fuzzy Logic as Applied to Traditional Logical
Paradoxes 515
18.7 Fuzzy Rules 516
18.8 Fuzzy Inference 516
18.9 Fuzzy Expert Systems 522
18.9.1 Defining the Fuzzy Sets 523
18.9.2 Defining Fuzzy Rules 527
18.9.3 Relating Observations to Fuzzy Sets 528
18.9.4 Evaluating Each Case for the Fuzzy Rules 530
18.9.5 Defuzzification 531
18.10 Fuzzy Systems that Learn 534
18.10.1 Neuro-fuzzy Systems 534
18.10.2 Layer 1: The Input Layer 536
18.10.3 Layer 2: The Fuzzification Layer 536
18.10.4 Layer 3: The Fuzzy Rule Layer 537
18.10.5 Layer 4: The Output Membership Function
Layer 537
18.10.6 Layer 5: The Defuzzification Layer 538
18.10.7 How the System Learns 538
18.11 Chapter Summary 539
18.12 Review Questions 539
18.13 Exercises 540
18.14 Further Reading 540
Chapter 19 Intelligent Agents 543
19.1 Introduction 543
19.2 Properties of Agents 544
19.2.1 Intelligence 544
19.2.2 Autonomy 545
19.2.3 Ability to Learn 545
19.2.4 Cooperation 545
19.2.5 Other Agent Properties 546
19.3 Agent Classification 546
19.4 Reactive Agents 547
19.4.1 Goal-based Agents 548
19.4.2 Utility-based Agents 549
19.4.3 Utility Functions 549
19.5 Interface Agents 551
19.6 Mobile Agents 552
19.7 Information Agents 553
19.8 Multiagent Systems 554
19.9 Collaborative Agents 556
19.10 Agent Architectures 556
19.10.1 Subsumption Architecture 556
19.10.2 BDI Architectures 558
19.10.3 Other Architectures 558
19.11 Accessibility 560
19.12 Learning Agents 561
19.12.1 Multiagent Learning 562
19.13 Robotic Agents 562
19.14 Braitenberg Vehicles 563
19.15 Chapter Summary 565
19.16 Review Questions 566
19.17 Exercises 567
19.18 Further Reading 567
Chapter 20 Understanding Language 571
20.1 Introduction 571
20.2 Natural Language Processing 573
20.2.1 Morphologic Analysis 574
20.2.2 BNF 575
20.2.3 Grammers 579
20.2.4 Parsing: Syntactic Analysis 581
20.2.5 Transition Networks 582
20.2.6 Augmented Transition Networks 585
20.2.7 Chart Parsing 585
20.2.8 Semantic Analysis 588
20.2.9 Ambiguity and Pragmatic Analysis 589
20.3 Machine Translation 592
20.3.1 Language Identification 593
20.4 Information Retrieval 594
20.4.1 Stemming 596
20.4.2 Precision and Recall 598
20.5 Chapter Summary 599
20.6 Review Questions 600
20.7 Exercises 600
20.8 Further Reading 601
Chapter 21 Machine Vision 605
21.1 Introduction 605
21.2 Human Vision 606
21.3 Image Processing 608
21.3.1 Edge Detection 609
21.3.2 Convolution and the Canny Edge Detector 611
21.3.3 Segmentation 612
21.3.4 Classifying Edges in Line Drawings 613
21.4 Using Texture 616
21.4.1 Identifying Textures 616
21.4.2 Structural Texture Analysis 620
21.4.3 Determining Shape and Orientation from
Texture 620
21.5 Interpreting Motion 623
21.6 Making Use of Vision 625
21.7 Face Recognition 627
21.8 Chapter Summary 628
21.9 Review Questions 629
21.10 Exercises 630
21.11 Further Reading 630
Glossary 633
Bibliography 697
Index 719
Contents
No comments:
Post a Comment