Page 2
~ ~ i ® ~ l i~i~Ii~ii~llll il~lllIl~II~lliilIIi~llliiIl~l!IIIIi~i ili i !iiiii~iii Artificial Intelligence
Contenu du document
Page 3
~' ~ ~ ~ ~ ~ "~ ~ ..... ~2~ . . . . . . . . . Handbook of Perception and Cognition 2nd Edition Series Editors Edward Carterette and M o r t o n F r i e d m a n
Page 4
: : ~ N ~ ' . " ~ " ~ ~~:~"~"*~ : : : ~ : " : " ~ " : ~ ~ X "~ /~NJg~~~:~I~'..~N~NN ~:~~l~N~!liii~J~Nli!~.liilliiiili!i!lliN~:.~..... jii~q.i~ii~}~NiN~iiiNiiiiiiii/iiiiiiiiil~Nliliiiiiiii Artificial Intelligence Edited by Margaret A. Boden School of Cognitive and Computing Sciences University of Sussex Brighton, England Academic Press San Diego New York Boston London Sydney Tokyo Toronto
Page 5
This book is printed on acid-free paper. @ Copyright 01996 by ACADEMIC PRESS, INC. All Rights Reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Academic Press, Inc. A Division of Harcourt Brace & Company 525 B Street, Suite 1900, San Diego, California 92101-4495 United Kingdom Edition published by Academic Press Limited 24-28 Oval Road, London NWl 7DX Library of Congress Cataloging-in-Publication Data Artificial intelligence / edited by Margaret A. Boden. P. cm. -- (Handbook of perception and cognition, 2nd ed. series) Includes bibliographical references and index. ISBN 0-12-161964-8 (case : alk paper) 1. Artificial intelligence. I. Boden, Margaret A. I . Series: Handbook of perception and cognition (2nd ed). Q335.A7857 1996 006.3-dc20 95-44625 CIP PRINTED IN THE UNITED STATES OF AMERICA 96 97 9 8 9 9 00 0 1 B C 9 8 7 6 5 4 3 2 1
Page 6
Contents Contributors xi Foreword xiii Preface xv 1 Philosophical Foundations Andy Clark I. An Evolving Engagement 1 11. Symbol-System A1 3 111. Connectionism 7 IV. Artificial Life 14 V. The Wasteland 19 References 20 2 Planfzing and Problem Solving Robert Inder I. Some Basic Ideas 24 11. The General Problem Solver 28 A . GPS in Action: The Tower of Hanoi 30 111. STRIPS 33 IV. Handling Interference 36 V. Nonlinear Planning 38 VI. More Sophisticated Planning 43 V
Page 7
vi Contents VII. Planning and Cognitive Science 48 References 53 3 Representation ofKnowledge Derek Partridge I. Representation and Knowledge 55 A. Representation as Structure and Function 56 B. Representational Choice 58 C. What Is Knowledge? 64 D. A Pair of Paradigms 66 11. Classical Approaches 68 A. Semantic Networks 68 B. Frames, Scripts, and Schemata 74 C. Logic-Based Representations 78 D. Procedural Representations 81 E. Analogical and Iconic Representation 84 References 85 Machine Learning Stuart Russell I. Introduction 89 A. A General Model of Learning 90 B. Types of Learning Systems 92 11. Knowledge-Free Inductive Learning Systems 93 A. Learning Attribute-Based Representations 96 B. Learning General Logical Representations 102 C. Learning Neural Networks 107 D. Learning Probabilistic Representations 108 111. Learning in Situated Agents 110 A. Learning and Using Models of Uncertain Environments 112 B. Learning Utilities 115 C. Learning the Value of Actions 116 D. Generalization in Reinforcement Learning 116 IV. Theoretical Models of Learning 118 A. Identification of Functions in the Limit 118 B. Simplicity and Kolmogorov Complexity 119 C. Computational Learning Theory 120 V. Learning from Single Examples 123 A. Analogical and Case-Based Reasoning 123 B. Learning by Explaining Observations 125
Page 8
Contents vii VI. Forming New Concepts 127 A. Forming New Concepts in Inductive Learning 128 B. Concept Formation Systems 128 VII. Summary 129 References 130 5 Connectionism and Neural Networks Harry Barrow I. Introduction 135 11. Understanding and Modeling Cognition and Perception 135 111. Reference Sources 137 IV. Biological Origins 137 V. Early Developments: Logical Models 140 VI. Adaptive Networks 141 VII. The Dartmouth Conference 141 VIII. Perceptrons 142 IX. Adalines and the LMS Algorithm 145 X. Minsky and Papert’s Perceptrons 145 XI. Back Propagation 146 XII. NETtalk 150 XIII. The Future 152 References 154 Expert Systems and Theories of Knowledge John Fox I. Introduction 157 11. Knowledge Engineering-The First Decade 158 A. The Nature of Expert Systems 158 B. Making Knowledge Explicit 159 C. Semantic Networks, Frames, and Objects 163 D. Assessment of the First Generation of Expert Systems 165 111. Second-Generation Expert Systems-From Decision Making to Expertise 165 A. Task-Oriented Analysis of Knowledge 166 €3. Reasoning with Uncertainty 170 C. Assessment and Critique 172 IV. The Third Decade-Systematic Engineering of Knowledge 173 A. Ontological Engineering 175 B. Developing Formal Theories of Knowledge 178
Page 9
viii Contents V. Conclusions 180 References 180 7 Machine Vision David C. H o g g I. Introduction 183 A. Aims of Machine Vision 183 B. A Hierarchy of Models 185 C. Computational Models of Biological Vision Systems 187 11. Image Formation 187 A. Projection 187 B. Digital Images 188 C. Steerable Cameras 190 111. Feature Detection 191 IV. Building Descriptions Using General Properties of Objects 195 A. Image Segmentation 198 B. Stereo Vision 201 V. Using Object Models 210 A. Feature Space Methods 210 B. “Model-Based” Methods 211 C . Dealing with Generic Objects and Nonrigid Objects 221 VI. Conclusion 224 References 225 8 Natural Language Processing Mark Steedman I. Introduction 229 A. Scope of the Study 229 B. The Anatomy of a Processor 230 C . The Relevance of Computation 231 11. Computational Theories of Processing 232 A. The Grammar 232 B. The Algorithm 245 C . The Oracle 255 111. Conclusion 262 IV. Further Reading 263 References 264 9 Creativity Margaret A. Boden I. The Definition of Creativity 267
Page 10
Contents ix A. Psychological Studies of Creativity 267 B. Defining Creativity 268 11. Impossibilist Creativity 269 A. Mapping Conceptual Spaces 269 B. Exploring Conceptual Spaces 270 C. Transforming Conceptual Spaces 271 111. Improbabilist Creativity 272 A. A1 Models of Association 272 B. A1 Models of Analogy 273 C. A1 Models of Induction 276 IV. A1 Models of the Arts 277 A. Music 277 B. Visual Arts 279 C. Verbal Tcxts 281 V. A1 Models of Science 282 A. Meta-DENDRAL 282 B. The BACON Family 283 C. An Integrated Discovery System 284 D. Scientific Revolutions 284 VI. Self-Transforming Programs 285 A. AM and EURISKO 285 B. Genetic Algorithms 286 VII. Conclusion 289 References 289 10 Human-Computer Interaction Mike Sharples I. Interacting with Computers 293 A. Pioneers of HCI 294 B. Interfaces 296 C . Interaction Devices 296 D. Communicating with a Computer 297 E. Styles of Communication 298 F. Communicating through the Computer 301 11. The Psychology of Computer Use 301 A. Applying Psychology to Design 302 B. Using Psychology to Create New Models 305 C. Applying Psychology to Evaluation 306 D. Applying Studies of Human-Computer Interaction to Psychology 306 111. Modeling Human-Computer Interaction 307 A. The Designer’s Model of the Computer 307
Page 11
x Contents B. The Designer’s Model of the User 309 C . The User’s Model of the Computer 311 IV. System Development 311 A. Adaptations of the Conventional Software Development Method 312 B. Departures from the Conventional Software Development Method 313 V. Evaluation 315 VI. Beyond Human-Computer Interaction 318 A. Computer-Supported Cooperative Work 319 B. Autonomous Agents 320 C. Ubiquitous Computing 320 D . The Challenge of Human-Computer Interaction 321 References 322 11 Artificial Lifeand the Animat Approach to Artificial Intelligence Jean-Arcady Meyer I. What Is Artificial Life? 325 11. The Animat Approach to A1 326 A. Objective and Methods of Standard A1 326 B. Objectives and Methods of the Animat Approach 327 C . How the Two Approaches Complement One Another 328 111. What Is Adaptive Behavior? 329 IV. Preprogrammed Behaviors 330 A. Individual Intelligence 331 B. Swarm Intelligence 332 V. Learned Behaviors 334 A. Learning in Neural Networks 334 B. Unsupervised Learning 336 C. Reinforcement Learning 339 VI. Evolved Behaviors 342 A. Genetic Algorithms 343 B. Evolution of the Control Parameters of a Neural Network 344 C . Evolution of a Control Program 347 VII. Conclusion 350 References 351 Index 355
Page 12
Contributors Numbers in parentheses indicate the pages on which the authors' contributions begin. H a r r y Barrow^ (135) J o h n F o x (157) School of Cognitive and C o m p u t i n g Advanced C o m p u t a t i o n Laboratory Sciences Imperial Cancer Research Fund University of Sussex Lincoln's Inn Fields, Brighton B N l 9 Q H , England L o n d o n W C 2 A 3 P X , England Margaret A . B o d e n (267) School of Cognitive and C o m p u t i n g D a v i d C . H o g g (183) Sciences School of C o m p u t e r Studies University of Sussex University of Leeds Brighton B N l 9 Q H , England Leeds LS2 9JT, England A n d y Clark^ (1) R o b e r t Inder (23) School of Cognitive and C o m p u t i n g H u m a n C o m m u n i c a t i o n Research Sciences Centre University of Sussex University of E d i n b u r g h B r i g h t o n B N l 9 Q H , England E d i n b u r g h E H 8 9LW, Scotland ^Present Address: Schlumberger Research Lab, Cambridge CB3 OEL, England. ^Present Address: Philosophy/Neuroscience/Psychology Program, Washington University, St. Louis, Missouri 63130
Page 13
xii Contributors Jean-Arcady Meyer (325) Mike Sharpies (293) Groupe de Bioinformatique School of Cognitive and Computing Ecole Normale Superieure Sciences 75230 Paris, France University of Sussex Brighton B N l 9QH, England Derek Partridge (55) Department of Computer Science Mark Steedman (229) University of Exeter Department of Computer and Exeter EX4 4PT, England Information Sciences University of Pennsylvania Stuart Russell (89) Philadelphia, Pennsylvania 19143 Computer Science Division University of California, Berkeley Berkeley, California 94720
Page 14
Foreword T h e problem of perception and cognition is understanding how the organ- ism transforms, organizes, stores, and uses information arising from the world in sense data or memory. With this definition of perception and cognition in mind, this handbook is designed to bring together the essential aspects of this very large, diverse, and scattered literature and to give a precis of the state of knowledge in every area of perception and cognition. T h e w o r k is aimed at the psychologist, the cognitive scientist in particular, and at the natural scientist in general. Topics are covered in comprehensive surveys in which fundamental facts and concepts are presented, and i m p o r - tant leads to journals and monographs of the specialized literature are p r o - vided. Perception and cognition are considered in the widest sense. There- fore, the w o r k will treat a wide range of experimental and theoretical work. T h e Handbook of Perception and Cognition should serve as a basic source and reference w o r k for those in the arts or sciences, indeed for all w h o are interested in h u m a n perception, action, and cognition. Edward C. Carterette and M o r t o n P. Friedman
Page 16
Preface Computational psychologists use computational concepts in formulating their theories. They typically employ computer models to improve the theories' clarity and internal coherence and to test their generative power (and limitations). These concepts and methods are drawn from artificial intelligence (AI). AI is the study of h o w to build or program computers to enable them to do what minds can do (for introductory texts, see Boden, 1987; Broadbent, 1993; Rich & Knight, 1991). AI is a broad church, whose members differ about general methodology as well as detail. Accordingly, computational psychology is diverse, too. This volume outlines the major theoretical ap- proaches and some promising recent developments. Some of the work herein discussed was done by psychologists. But most was done by AI professionals. However, the distinction is not always clear. Many AI workers are not primarily interested in technological "fixes," ingenious ways of getting computers to do things irrespective of h o w real minds do them. Rather, they hope to illuminate the structural and process- ing principles underlying minds in general and human minds in particular. Even technological AI has a psychological tinge, since its ideas are often suggested by the human (or animal) case. For instance, a team designing an early lunar robot, capable of switching between its goals without waiting for radio signals from Earth, modeled the role of the mammalian reticu- lar formation in scheduling different instinctive behaviors (Kilmer, M c -
Page 17
xvi Preface CuUoch, & Blum, 1969). Technological AI has benefited enormously from the psychologically motivated work of Allen Newell and Herbert Simon (Newell, 1990; Newell, Shaw, & Simon, 1957; Newell & Simon, 1961, 1972). Newell and Simon's 40-year research program on human thinking pi- oneered several lasting AI techniques: list processing, hierarchical planning, heuristic search, production systems, and "blackboard" memories. This example illustrates the potential for links between advances in AI and in computational psychology. Significantly, if sadly, a recent overview of AI written by and for AI professionals (Bobrow, 1993) includes 200 pages reviewing Newell's last book. Unified Theories ofCognition, plus an obituary by his intellectual alter ego (Simon). Early AI (from the mid-1950s), like current "symbolic" AI, ignored neurophysiology. This attitude sprang from a reasoned philosophical posi- tion, the "physical symbol-system hypothesis" (see Chapter 1). Some philosophical critiques, and work on parallel-processing "connectionist" systems, have suggested that computational psychologists ignore the brain at their peril. These issues are featured in Chapters 1 and 5, and relevant neuroscientific work is cited there, but there is not a chapter devoted to computational neuroscience (for a review of this area, see Churchland & Sejnowski, 1992). Nor does any chapter concentrate on motivation and emotion. Little computational work has been done on these matters. Purposive behavior has been a concern of AI from the early days (Boden, 1972), although most AI models still have only one or two goals (plus subgoals). Truly multiple- goal systems will show aspects of emotional behavior. Any intelligent sys- tem capable of scheduling multiple conflicting goals, and of reacting to emergencies and opportunities, would need the sorts of goal-scheduling mechanisms characteristic of emotions (Frijda, 1986; Ortony, Clore, & Col- lins, 1991; Sloman, 1990). Whether the conscious aspects of emotion—or anything else—could be explained in AI terms is more controversial (see Chapter 1). Most computa- tional psychologists simply ignore this question. The same is true of most other psychologists: consciousness is typically taken for granted, no scien- tific or philosophical explanation being sought. These comments would have been even more apt 10 years ago. Recently, however, several extended discussions of consciousness have appeared, both within (Dennett, 1991; Jackendoff, 1987) and outside (Bock & Marsh, 1993; Marcel & Bisiach, 1988) the computational paradigm. Fundamental philosophical questions such as this are discussed in Chap- ter 1. Other topics explored there include the differences between symbolic and connectionist AI, and the nature of computation and representation. Chapter 1 also comments on the philosophical significance of artificial life
Page 18
Preface xvii (ALife), a recently revivified research field described in the final chapter. ALife uses computer modeling to study self-organizing systems, and refers m o r e often to insects than to h u m a n beings. It merits inclusion in this volume partly because of its ethological interest, and partly because AI can be seen as a subarea of ALife: ALife studies self-organization in general, while AI focuses on intelligent systems (Boden, 1996). T h e intervening chapters tackle specific topics within computational psy- chology and AI. These are planning and problem solving, knowledge rep- resentation, learning, connectionism, expert systems, vision, natural lan- guage, robotics, creativity, and h u m a n - c o m p u t e r interaction. Most of these topics are studied by noncomputational methods too, so for a rounded view the reader should also consult other volumes of the Handbook of Perception and Cognition series. T h e diversity and excitement of computational psychology life not only in its "in-house" theoretical disagreements, but also in its interdisciplinarity. This characterized the field from the start. The lunar-robot team which imported neurophysiology into space technology included the polymath Warren McCuUoch. McCuUoch was a psychiatrist, a physiologist, a cyber- netician, a philosopher, a poet . . . and his most influential work was p u b - lished with a mathematician, Walter Pitts. Their papers of 1943 ("A Logical Calculus of the Ideas Immanent in Nervous Activity") and 1947 ("How We K n o w Universals: T h e Perception of Auditory and Visual Forms") were crucial in founding both computational psychology and AI, of both the symbolic and connectionist varieties. McCuUoch (and Pitts) also co- authored, in 1959, the neurophysiologically influential paper on "What the Frog's Eye Tells the Frog's Brain" (McCuUoch, 1965.) We cannot all hope to be a McCuUoch. But AI and computational psy- chology are inescapably interdisciplinary. They need insights from the sci- ences (biology, ethology, psychology, neuroscience, physics, and computer science), and from the humanities too (philosophy, linguistics, and the his- tory of art and science). If this wide-ranging enterprise appears difficult, even daunting, so be it. We should expect no less, in aiming to understand the mind. References Bobrow, D. G. (Ed.). (1993). Artificial intelligence in perspective [Special issue]. Artificial Intelligence, 59, 1-462. Bock, G. R., & Marsh, J. (Eds.). (1993). Experimental and theoretical studies of consciousness. Chichester: Wiley. Boden, M. A. (1972). Purposive explanation in psychology. Cambridge, MA: Harvard University Press. Boden, M. A. (1987). Artificial intelligence and natural man (2nd ed.). New York: Basic Books. Boden, M. A. (Ed.). (1996). The philosophy of artificial life. Oxford: Oxford University Press. Broadbent, D. (Ed.). (1993). The simulation of human intelligence. Oxford: Blackwell.
Page 19
xviii Preface Churchland, P. S., & Sejnowski, T. J. (1992). The computational brain. Cambridge, MA: MIT Press. Dennett, D. C. (1991). Consciousness explained. Boston: Little, Brown. Frijda, N. (1986). The emotions. Cambridge, UK: Cambridge University Press. Jackendoff, R. (1987). Consciousness and the computational mind. Cambridge, MA: MIT Press. Kilmer, W. L., McCulloch, W. S., & Blum, J. (1969). A model of the vertebrate central command system. International Journal of Man-Machine Studies, 1, 279-309. Marcel, A. J., & Bisiach, E. (Eds.). Consciousness in contemporary science. Oxford: Oxford University Press. McCulloch, W. S. (1965). Embodiments of mind, Cambridge, MA: MIT Press. Newell, A. (1990). Unified theories of cognition.Cambridge, MA: Harvard University Press. Newell, A., Shaw, J. C , & Simon, H. A. (1957). Empirical explorations with the Logic Theory Machine. Proceedings—Western Joint Computer Conference, 15, 218-239. Newell, A., & Simon, H. A. (1961). GPS—A program that simulates human thought. In H. Billing (Ed.), Lernende automaten (pp. 109-124). Munich: Oldenbourg. Newell, A., & Simon, H. A. (1972). Human problem solving. Englewood Chffs, NJ: Prentice- Hall. Ortony, A., Clore, G. L., & Collins, A. (1991). The cognitive structure of emotions. Cambridge, UK: Cambridge University Press. Rich, E., & Knight, K. (1991). Artificial intelligence (2nd ed.). New York: McGraw-Hill. Sloman, A. (1990). Motives, mechanisms, and emotions. In M. A. Boden (Ed.), The philoso- phy of artificial intelligence (pp. 231-247). Oxford: Oxford University Press.
Page 20
C H A P T E R Philosophical Foundations Andy Clark I. AN EVOLVING ENGAGEMENT In the beginning, the nature of philosophy's engagement with artificial intelligence and cognitive science was clear enough. The new sciences of the mind were to provide the long-awaited vindication of the most potent dreams of naturalism and materialism. Mind would at last be located firmly within the natural order. We would see in detail how the most perplexing features of the mental realm could be supported by the operations of solely physical laws upon solely physical stuff. Mental causation (the power of, e.g., a belief to cause an action) would emerge as just another species of physical causation. Reasoning would be understood as a kind of automated theorem proving. And the key to both was to be the depiction of the brain as the implementation of multiple higher level programs whose task was to manipulate and transform symbols or representations: inner items with one foot in the physical (they were realized as brain states) and one in the mental (they were bearers of contents, and their physical gymnastics were cleverly designed to respect semantic relationships such as truth preservation). A compelling virtue of this image lay in its unique combination of physi- cal dependence and multiple realizability. Everything bottomed out in a solid physical implementation with impeccable causal credentials. But one Artificial Intelligence Copyright © 1996 by Academic Press, Inc. All rights of reproduction in any form reserved.
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !