TY - BOOK AU - Dean,Thomas L. AU - Allen,James AU - Aloimonos,Yiannis TI - Artificial intelligence : : theory and practice / SN - 0805325476 PY - 1995/// CY - California PB - Addison-Wesley KW - INTELIGENCIA ARTIFICIAL N1 - CONTENIDO 1 INTRODUCTION 1 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 2 SYMBOLIC PROGRAMMING 23 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 Files, 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 3 REPRESENTATION AND LOGIC 71 3.1 Propositional Logic 73 Syntax for P, 74 Semantics for P, 75 3.2 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 Quantifiers, 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 Lisp Implementation: Data Dependencies 127 4 SEARCH 131 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 Lisp Implementation: Discrimination Trees 174 5 LEARNING 179 5.1 Classifying Inductive Learning Problems 180 Supervised Learning, 180 Classification and Concept Learning, 182 Unsupervised Learning, 183 Online and Batch Learning Methods, 183 5.2 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, 203 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 Functions, 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 Lisp Implementation: Learning Algorithms 249 6 ADVANCED REPRESENTATION 255 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 Lisp Implementation: Temporal Reasoning 291 7 PLANNING 297 7.1 State-Space Search 298 What is Planning?, 298 Planning as Search, 300 Representing and Solving Search Problems, 301 State Progression, 3O2 Goal Regression, 303 Means/Ends Analysis, 303 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, and Systematic Search, 312 Block-Stacking Example, 313 Recognizing and Resolving Conflicts, 316 Variables in Partially 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 Indexing, 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 Disjunctive Preconditions, 342 Universally Quantified Effects, 343 Wandering Briefcase Example, 344 Processes Outside the Planner's Control, 345 Lisp Implementation: Refining Partially Ordered Plans 351 8 UNCERTAINTY 355 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 Degrees of Belief, 360 Random Variables and Distributions, 361 Conditional Probability, 362 Calculus for Combining Probabilities, 364 Conditional Independence, 366 Maintaining Consistency, 367 8.3 Probabilistic Networks 368 Graphical Models, 369 Path-Based Characterization of Independence, 371 Quantifying Probabilistic Networks, 372 Inference in Probabilistic 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 Medicine, 394 Lisp Implementation: Inference in Probabilistic Networks 399 9 IMAGE UNDERSTANDING 409 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 Lisp Implementation: Labeling Polyhedral Scenes 482 10 NATURAL LANGUAGE PROCESSING 489 10.1 Components of Language 491 Content 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, 505 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 Lisp Implementation: Simple Parser 533 ER -