INTRODUCTION
Robot?Explorers,?2
1.1
Artificial?IntelLigence?in?Practice??3
Examples?of?Artificial?Intelligence?Systems,?4
1.2
Artificial?Intelligence?Theory?5
Examples?of?Artificial?Intelligence?Theory,?6
1.3
Identifying?and?Measuring?Intelligence
1.4
Computational?Theories?of?Behavior??9
Representation,?10
Syntax?and?Semantics,?11
1.5
Automated?Reasoning??12
Inference?and?Symbolic?Manipulation,?13
Representing?Common-Sense?Knowledge,?14
Combinatorial?Problems?and?Search,?14
Complexity?and?Expressivity,?15
1.6
How?This?Book?Is?Organized??16
Summary??18
Background??19
Exercises?20
SYMBOLIC?PROGRAMMING
2.1
Rule-Based?Reactive?System?Example?25
Representing?Sensors?and?Sensor?Values?as?Symbols,?26
2.2
Introduction?to?Lisp?27
Language?Requirements,27
Common?Lisp,?27
Lists?and?Lisp?Syntax,?28
Symbols,?28
Programs?and?Documentation,?28
2.3??Interacting?with?Lisp?29
The?Lisp?Interpreter,?29
2.4
Functions?in?Lisp??31
Function?Invocation,?31
Procedural?Abstraction,?32
Conditional?Statements,?33
Recursive?Functions,?35
Evaluating?Functions?in?Fa.?les,?35
2.5
Environments,?Symbols,?and?Scope?36
Assigning?Values?to?Symbols,?36
Eval?and?Apply?Revisited,?37
Structured?Environments,?38
Variables,?39
Lexical?Scoping,?40
2.6
More?on?Functions??42
Functions?with?Local?State,?42
Lambda?and?Functions?as?Arguments,?43
2.7
List?Processing?44
Suspending?Evaluation?Using?Quote,?44
Building?and?Accessing?Elements?in?Lists,?45
Lists?in?Memory,?45
Modifying?List?Structures?in?Memory,?46
Alternative?Parameter-Passing?Conventions,?47
Predicates?on?Lists,?48
Built-In?List?Manipulation?Functions,?48
Optional?Arguments,?49
List-Processing?Examples,?49
Data?Abstraction,?51
2.8
Iterative?Constructs??53
Mapping?Functions?to?Arguments,?53
General?Iteration,?54
Simple?Iteration,?55
2.9
Monitoring?and?Debugging?Programs?56
Tracing?and?Stepping?Through?Programs,?56
Formatted?Output,?58
2.10??Rule-Based?Reactive?System?Revisited??58
Summary?64
Background??65
Exercises?65
REPRESENTATION?AND?LOGIC
3.1
Propositional?Logic??73
Syntax?for?P,?74
Semantics?for?P,?75
32
Formal?System?for/v?76
Logical?Axioms?of?P,?77
Normal?Forms,?78
Rules?of?Inference,?79
Proofs?and?Theorems,?79
Resolution?Rule?of?Inference,?80
Completeness,?Soundness,?and?Decidability,?81
Computational?Complexity,?82
Solving?Problems?with?Logic,?82
3.3
Automated?Theorem?Proving?in?P?84
Goal?Reduction?in?P,?85
Proof?by?Contradiction,?87
3.4
Predicate?Calculus?88
Syntax?for?PC,?89
Translating?English?Sentences?into?Logic,?90
More?About?Quantification,?91
Semantics?for?PC,?91
3.5
Formal?System?for?PC?93
Specifying?Programs?in?Prolog,?94
Eliminating?Quantifiars,?94
Learning?and?Deductive?Inference,?96
Decidability,?98
3.6
Automated?Theorem?Proving?in?PC??99
Matching?and?Universal?Instantiation,?99
Goal?Reduction?in?PC,?101
Unification,?103
Concept?Description?Languages,?107
Semantic?Networks,?108
3.7
Nonmonotonic?Logic??109
Closed-World?Assumption,?109
Abductive?and?Default?Reasoning,?111
Minimal?Models,?112
3.8
Deductive?Retrieval?Systems??113
Forward?and?Backward?Chaining,?114
Reason?Maintenance?Systems,?116
Nonmonotonic?Data?Dependencies,?118
Summary?119
Background??121
Exercises??122
Lisp?Implementation:?Data?Dependencies??127
SEARCH
4.1
Basic?Search?Issues??133
Search?Spaces?and?Operators,?134
Appliance?Assembly?Example,?135
Exploiting?Structure?to?Expedite?Search,?136
4.2
Blind?Search?137
Depth-First?Search,?138
Depth-First?Search?Is?Space?Efficient,?139
Breadth-First?Search,?140
Breadth-First?Search?Is?Guaranteed,?141
Iterative-Deepening?Search,?141
Iterative-Deepening?Search?Is?Asymptotically?Optimal,?143
Searching?in?Graphs,?144
4.3
Heuristic?Search??144
Best-First?Search,?145
Admissible?Evaluation?Functions,?146
4.4
Optimization?and?Search??149
Hill-Climbing?Search,?149
Local?Minima?and?Maxima,?151
Gradient?Search,?153
Simulated?Annealing,?153
Simulated?Evolution?and?Genetic?Algorithms,?154
Application?to?Vehicle?Routing,?158
4.5
Adversary?Search??160
Minimax?Search,?160
a-B?Search,?163
4.6
Indexing?in?Discrimination?Trees??166
Storing?and?Retrieving?Predicate?Calculus?Formulas,?167
Decision?Trees,?168
Summary?169
Background??171
Exercises??171
Lisp?Implementation:?Discrimination?Trees??174
5?LEARNING
5.1
Classifying?Inductive?Learning?Problems??180
Supervised?Learning,?180
Classification?and?Concept?Learning,?182
Unsupervised?Learning,?183
Online?and?Batch?Learning?Methods,?183
52
Theory?of?Inductive?Inference??183
The?Role?of?Inductive?Bias,?184
Restricted?Hypothesis?Space?Biases,?184
Preference?Biases,?185
Probably?Approximately?Correct?Learning,?186
PAC?Learnable?Concept?Classes,?187
Finding?Consistent?Hypotheses,?188
5.3
Version?Spaces??188
Attributes,?Features,?and?Dimensions,?189
Specializing?and?Generalizing?Concepts,?190
Maintaining?Version-Space?Boundaries,?191
Data?Structures?for?Learning,?192
Implementing?the?Version-Space?Method,?194
Optimal?Method?for?Conjunctions?of?Positive?Literals,?195
5.4
Decision?Trees??195
Implementing?a?Preference?for?Small?Decision?Trees,?196
Disorder?and?Information?Theory,?199
Decision?Trees?in?Practice,?202
5.5
Network?Learning?Methods?202
Model?for?Computation?in?Biological?Systems,?2113
Adjustable?Weights?and?Restricted?Hypothesis?Spaces,?205
5.6
Gradient?Guided?Search?206
Searching?in?Linear?Function?Spaces,?207
Experimental?Validation,?208
Nonlinear?Function?Spaces?and?Artificial?Neural
Networks,?210
Deriving?the?Gradient?for?Multilayer?Networks,?211
Error?Backpropagation?Procedure,?212
Implementing?Artificial?Neural?Networks?in?Lisp,?214
Representational?and?Computational?Issues,?217
Networks?with?Adjustable?Thresholds,?218
Comparing?the?Performance?of?Different?Networks,?220
5.7
Perceptrons??221
Perceptron?Learning?Rule,?222
Linearly?Separable?Funct/ons,?223
5.8
Radial?Basis?Functions??224
Approximating?Functions?by?Combining?Gaussians,?225
Two-Step?Strategy?for?Adjusting?Weights,?227
Functions?with?Multidimensional?Input?Spaces,?230
5.9
Learning?in?Dynamic?Environments??231
Reinforcement?Learning.?231
Computing?an?Optimal?Policy,?235
Online?Methods?for?Learning?Value?Functions,?235
Learning?by?Exploration.?239
Summary?24O
Background??242
Exercises??243
Lisp?Implementation:?Learning?Algorithms?249
6??ADVANCED?REPRESENTATION
6.1??Temporal?Reasoning??256
6.2
The?Situation?Calculus?257
Constraining?Fluents?in?Situations,?260
Frame?Problem,?260
Qualification?Problem,?262
6.3
First-Order?Interval?Temporal?Logic?264
Syntax?for?the?Interval?Logic,?265
Representing?Change?in?the?Interval?Logic,?267
Semantics?for?the?Interval?Logic,?268
6.4
Managing?Temporal?Knowledge??269
6.5
Knowledge?and?Belief??273
Possible-Worlds?Semantics,?277
6.6
Spatial?Reasoning?279
Representing?Spatial?Knowledge,?279
Planning?Paths?in?Configuration?Space,?281
Path?Planning?as?Graph?Search,?282
Locally?Distinctive?Places,?285
Summary?286
Background??287
Exercises??288
Lisp?Implementation:?Temporal?Reasoning?291
PLANNING
7.1
State-Space?Search?298
What?is?Planning?,?298
Planning?as?.%arch,?300
Representing?and?Solving?Search?Problems,?301
State?Progression,?3O2
Goal?Regression,?303
Means/Ends?Analysis,
Machine?Assembly?Example,?305
Operant?Schemas,?306
Block-Stacking?Problems,?307
7.2
Least?Commitment?Planning?308
Search?in?the?Space?of?Partially?Ordered?Plans,?309
Sound,?Complete,?andSystematic?Search,?312
Block-Stacking?Example,?313
Recognizing?and?Resolving?Conflicts,?316
Variables?in?Par''dally?Ordered?Plans,?317
7.3
Planning?in?a?Hierarchy?of?Abstraction?Spaces??320
Analysis?of?Planning?with?levels?of?Abstraction,?321
Towers-of-Hanoi?Problems,?322
Task?Reduction?Planning,?325
7.4
Adapting?Previously?Generated?Plans?326
IndexLng,?Retrieving,?and?Adapting?Plans,?326
Analysis?of?Adaptive?Planning,?331
7.5
Planning?with?Incomplete?Information?332
The?Copier-Repair?Problem,?332
Generating?Conditional?Plans,?335
Contexts?Represent?Possible?Sets?of?Observations,?336
7.6
More?Expressive?Models?of?Action??340
Conditional?Effects,?341
isjunctive?Preconditions,?342
Universally?Quantified?Effects,?343
Wandering?Briefcase?Example,?344
Processes?Outside?the?Planner''s?Control,?345
Summary?346
Background??347
Exercises??348
Lisp?Implementation:?Refining?Partially?Ordered
Plans?351
UNCERTAINTY
8.1
Motivation?for?Reasoning?Under?Uncertainty??357
Sources?of?Uncertainty,?357
Representing?Uncertain?Knowledge,?357
Applications?Involving?Uncertainty,?358
8.2
Probability?Theory??359
Frequency?Interpretation?of?Probability,?359
Save?Interpretation?of?Probability,?359
Desrees?of?Belief,?360
Random?Variables?and?Distributions,?361
Conditional?Probability,?362
Calculus?for?Combining?Probabilities,
Conclitional?Independence,?366
Maintaining?Consistency,?367
8.3
Probabilisfic?Networks?368
Graphical?Models,?369
Path-Based?Characterization?of?Independence,?371
Quantifying?Probabilistic?Networks,?372
Inference?in?Probabflistic?Networks,?373
Exact?Inference?in?Tree-Structured?Networks,?374
Propagating?Evidence?in?Trees,?378
Exact?Inference?in?Singly?Connected?Networks,?380
Approximate?Inference?Using?Stochastic?Simulation,?382
Likelihood-Weighting?Algorithm,?384
Probabilistic?Reasoning?in?Medicine,?386
8.4
Decision?Theory??388
Preferences?and?Utilities,?389
Decision?Tree?Methods,?390
Computing?the?Value?of?Information,?393
Automated?Decision?Making?in?Medidne,?394
Summary??395
Background??396
Exercises?397
Lisp?Implementation:?Inference?in?Probabilistic
Networks??399
9??IMAGE?UNDERSTANDING
9.1
Sensors?and?Images?410
Digital?Images,?410
Noise?in?Image?Processing,?410
9.2
Computer?Vision?412
Understanding?Images,?413
Vision?Versus?Thought,?414
9.3
Human?Vision??415
Transferring?Information?from?the?Eye?to?the?Brain,?415
Compressing?Visit?Information,?417
9.4
Vision?as?a?Recovery?Problem??418
What?to?Recover,?420
Geometric?Aspects?of?Image?Formation,?420
Perspective?Projection,?420
Orthographic?Projection,?423
Paraperspective?Projection,?425
Shape?Representation,?426
Surface?Orientation?and?Shape?Under?Perspective,?426
Surface?Orientation?and?Shape?Under?Orthography,?426
Stereographic?Projection,?427
Geometric?Properties?of?the?Perspective?Projection,?427
Imaging?with?tenses,?430
Photometric?Aspects?of?Image?Formation,?430
9.5
Recovery?of?Image?Descriptions??431
Edge?Detection,?431
Differentiation?Approaches,?432
Model-Based?Approaches,?436
Edge?Grouping?and?Hough?Transform,?437
Image?Segmentation,?438
9.6
Shape?from?Contour?440
Qualitative?Analysis?Using?Edge?Labels,?441
Quantitative?Analysis?Using?Skewed?Symmetries,?442
9.7??Shape?from?Shading?444
Reflectance?Maps,?445
Solving?Ill-Posed?Problems,?448
Photometric?Stereo,?449
9.8
Shape?from?Texture?450
Density?of?Textural?Elements,?450
Textural?Reflectance?Maps,?451
9.9
Stereo??453
Addressing?the?Correspondence?Problem,?453
Intensity-Based?Matching,?455
Edge-Based?Matching,?456
9.10??Analysis?of?Visual?Motion??457
Motion?Fields,?458
Motion?Field?Estimation,?460
Motion?Field?Interpretation,?463
9.11??Active?Vision??465
9.12??Applications??466
Autonomous?Vehicle?Navigation,?467
Object?Recognition,?469
Summary?471
Background?474
Exercises?476
Lisp?Implementation:?Labeling?Polyhedral?Scenes
10??NATURAL?LANGUAGE?PROCESSING
10.1??Components?of?Language?491
Ccmtent?and?Function?Words,?491
Structure?of?Phrases,?492
10.2??Context-Free?Grammars?493
Parsing,?495
10.3??Parsing?Context-Free?Grammars??496
Exploiting?the?Lexicon,?498
Building?a?Parse?Tree,?499
10.4??Grammars?Involving?Features??502
Matching?with?Features,?5O5
10.5??Efficient?Parsing?with?Charts?507
Ambiguous?Sentences,?507
10.6??Semantic?Interpretation?511
Word?Senses,?512
Semantic?Interpretation?Using?Features,?515
Disambiguating?Word?Senses,?517
10.7??Generating?Natural?Language??519
10.8??Natural?Language?in?Context?521
Speech?Acts,?521
Establishing?Reference,?522
Handling?Database?Assertions?and?Queries,?524
10.9?Quantifier?Scoping?529
Summary?530
Background??530
Exercises??531
Lisp?Implementation:?Simple?Parser?533
BIBLIOGRAPHY
VOCABULARY?INDEX
CODE?INDEX
鄂公网安备 42010302001612号 