DOCUMENT RESUME ED 238 727 SE 043 748 VanLehn, Xurt AUTHOR Felicity Conditions for Human Skill Acquisition: TITLE Validating an AI-Based Theory. Cognitive and Instructional Sciences Series. INSTITUTION Xerox Corp., Palo Alto, CA. Palo Alto Research Center. Office of Naval Research, Arlington, Va. Personnel SPONS AGENCY and Training Research Programs Office. CIS-21 REPORT NO Nov 83 PUB DATE CONTRACT N00014-82C-0067 NOTE 338p. PUB TYPE Research/TeChnical (143) Reports EDRS PRICE MF01/PC14 Plus Postage. DESCRIPTORS Algebra; *Artificial Intelligence; Cognitive Development; *Cognitive Processes; Computer Programs; Elementary Secondary Education; Error Patterns; Fractions; Language Patterns; *Language Processing; Learning; *Learning Theories; Linguistic Performance; *Mathematics Education; Mathezlatics Instruction; *Skill Development; Subtraction *Mathematics Education Research IDENTIFIERS ABSTRACT -44 theory of how people learn certain procedural skills is pre.sented. t is based on the idea that the teaching and learning that goes on in a classroom is like an ordinary conversation. The speaker (teacher) compresses a non-linear knowledge structure (the target procedure) into a linear sequence of utterances (lessons). The listener (student) constructs a knowledge structure (the learned procedureirfrom the utterance sequence (lesson sequence). Speakers unknowingly obey certain constraints, called felicity conditions or conversationarpostulates, which help listeners construct an appropriate knowledge structure. This research has shown that there are felicity conditions on lesson sequences that 'aelp students learn procedures. Three-felicity conditions were discovered, forming the central hypotheses in the learning theory, which was embedded in a model, a large computer program using artificial intelligence (AI) techniques. The model's performance was compared to data from several thousand students learning to subtract multidigit numbers, add fractions, and solve simple algebraic equations. A key criterion for the theory is that the set of procedures that the model "learns" should exactly match the set of procedures that students actually acquire. Both testing the predictions and arguing for the validity of the theory are included in the report. (Author/MNS) ***********************************************************************. Reproductions supplied by EDRS are the best that can be made from the original document. *********************************************************************** U.S DEPARTMENT OF EDUIDATIO NATIONAL INSTITUTE OF EDUCATION EDUCATIONAL RESOURCES INFORMATION CENTER IERICI This document has been teprodecod as recosed 'from the canon 00 gandaton encomiast," ot himor changes nave been made to improv reproduckn quaky. Pores of it or *pawns stored on Ibis dote menr do nol nosessardy represent office' ME pontoon or pokey t.. mi Felicity Conditions for Human Skill Acquisition: 00N r^ Validating an Al.Based Theory. N CI EL) Kurt Van Lehn r "PERMISSION TO REPRODUCE THIS MATERIAL HAS SEEN GRANTED BY di 5. *Li:Wumuff e TO THE EDUCATIONAL RESOURCES INFORMATION CENTER (ERIC).": Unclassified SECURITY CLASSIFICATION OF THIS PAGE NINA Soto entered) READ INSTRUCTIONS REPORT DOCUMENYATON PAGE BEFORE COMPLETING FORM 1. REPORT NUMBER S. RECIPIENT'S CATALOG NUMBER 2. GOVT ACCESSION HO. CIS-21 fond &than.) 4. TITLE C TYPE OF REPORT 6 PERIOD COVERED Interim Report Felicity Conditions fo, Human Skill Acquisition: Validating an AI-based Theory 6. PERFORMING ORG. REPORT HUMBER P8300048 AUTHOR(.) 8. CONTRACT OR GRANT HUMBER(.) 7. N00014-82C-0067' Kurt VanLehn .00) W. pROGRAM ELEMENT. PROJECT. TASK 9. PERFORMING ORGANIZATION NAME AND ADDRESS AREA 6 WORK ut/IT NUMBERS Cognitive and Instructional Sciences Group NR 667-477 Xerox Corporation/Palo Alto Research Center 94304 3333 Coyote Hill Road, Palo Alto, CA 12. REPORT DATE CONTROLLING OFFICE NAME ANO ADDRESS I1. Personnel and Training Research Programs November 1983 Office of Naval Research (code 458) 13. HUMBER OF PAGES Arlington, VA 335 22217 MONITORING AGENCY NAME 6 ADDRESS(/' different from Controlling Office) 1$. SECURITY CLASS. (of IMP report) 14. c 4 . .Unclassified DEcLASSiFICATION/DOWNGRAOING ise. SCHEDULE 16. DISTRIBUTION STATEN vol. (of Wm Report) Approved for public release, distribution unlimited 17. DIST''.13UTIOU STATEMENT (ol the obeffeel entered in Block 20. It different from RePort) lit SUPPLEMENTARY NOTES IL, KEY WORDS (Continue on row.* mide ll rtoeemeary rale, Id ;Orly by block neenbor) Cognitive Science, Learning, Artif.cial Intelligence, Skill Acquisition, Human Cognition, Arithmetic 20. ABSTRACT (Continua on reverie *Ida Il rummer end identity by block number) See reverse side. DD EOITION OF I NOV 6S IS OBSOLETE 1473 1 JAN 73 3 Unclassified SIN MOE LF 014.6601 SECURITY CLASSIFICATION OF THIS PAGE (Whop Data S1710,040 Abstract A theory of how people team certain procedural skills is presented. :t is based on the idea that the teaching and learning that goes on in a classroom is like an ordinary conversation. The speaker (teacher) compresses a nonlinear knowledge structure (the target procedure) into a linear sequence of utterances (lessons). The listener (student) constructs a from the knowledge structure utterance eefquence (lesson (the procedure) learned In recent years, linguists have discovered that speakers unknowingly obey sequence), constraints on the sequential form of their utterances. certain Apparently, these tacit conventions, caned felicity conditions or conversational postulates, help listeners construct The analogy between an appropriate knowledge structure from the utterance sequence. conversations and classrooms suggests that there might be felicity conditions on lesson sequences that help students learn procedures. This research has shown that there are. For the particular kind of skill acquisition studied here, three felicity conditions were discovered. They are the central hypotheses in the learning theory. The theory has been embedded in a model, a large computer program that uses artificial intelligence (Al) techniques. The model's performance has been compared to data from several thousand students learning ordinary mathematical procedures: subtracting multidigit numbers, adding fractions and solving simple algebraic equations. A key criterion for the theory is that the set of procedures that the model "learns" should exactly match the set of procedures that students actually acquire, including their "buggy" procedures. However, much more is need for psychological validation of this theory, or any complex Al-based theory, than merely Its predictions. Part of the research has involved Priding ways to argue for the testing validity of the theory. 4 1 Felicity Conditions for Human Skill 'Acquisition: Validating an Al-based Theory Kurt VanLehn November 1983 Cognitive and Instructional Sciences Series CIS-21 Corporate Accession P8300048 © Copyright Kurt VanLehn 1983. . The author hereby grants to M.I.T. and to Xerox Corporation permission to reproduce and to distribute copies of this document in whole or in part. XEROX PALO ALTO RESEARCH CENTER 3333 Coyote Hill Road / Palo Alto / California 94304 Approved for public release; Distribution unlimited. '2 *R. Felicity Conditions for Human Skill Acquisition: Validating an Al-based Theory cs ) Kurt Vani.ehn Abstract It is based on the idea that the A theory of how people IkE.n ! certain procedural skills is presented. teaching and learning that goes on in a classroom is like an ordinary conversation. The speaker (teacher) compresses a non-linear knowledge structure (the target procedure) into a linear sequence The listener (student) constructs a knowledge structure (the learned of utterances (lessons). procedure) from the utterance sequence (lesson sequence). In recent years, linguists have discovered that speakers unknowingly obey certain constraints on the sequential form of their utterances. Apparently, these tacit conventions, called felicity conditions or conversational postulates, help listeners construct an appropriate knowledge structure fromothe utterance sequence. '!lie analogy between conversations and classrooms suggests that there ,might be felicity conditions on lesson For the sequences that help students learn procedures. This research has shown that there arc. particular kind of skill acquisition studied here, three felicity conditions were discovered. They are the central hypotheses in the learning theory. The theory has been embedded in a model. a la,ge computer program that uses artificial intelligence (Al) techniques. The model's performance has been compared to data from several thousand students learning ordinary mathematical procedures: subtracting multidigit numbers, adding fractions and solving simple algebraic equations. A key criterion for the theory is that the set of procedures that the model "learns" should exactly match the set o'' procedures that students actually acquire, including their "buggy" procedures. However, much more is need for psychological validation of this theory, or any complex AI-based theory, Part of the research has involved finding ways to argue for the than merely testing its predictions. of the theory. validity , Acknowledgments . I would like to express my thanks to the people who encouraged and aided me in this work: John Seely Brown, for providing me with ten new ideas every time I talked with him, and for supporting me so :onerously for so many years: Hai Abelson, for helping me turn a shambles of arguments into a presentable piece of work, and for moral support at the critical times; Patrick Winston, for opening doors that I feared were closed, and for reading far too many pages; Andy DiSessa, for help in the clutch; Johan deKleer, for reading unreadable first drafts, and %incredibly) finding the Richard Burton, fOr Lisp support. for Debuggy, for windsurfing, and for onion theory; holes; Jarnesine Friend, for the Southbay study and a dash of reality in the ivory tower: Elizabeth Berg, Joan Bresnan, Haj Ross, Mitch Marcus. Candy Sidner: for for cheerfully coding the data; permanently warping me in just the right ways; ; Jim Greeno. for early support and a proper Peter Andrea and Stu Card, for thorough critiques of an early draft; Steve scientific perspective; Purcell, for an early reading, not to mention the John Muir trail and constant encouragement; Betsey Summers, for loving support amid years of receding deadlines. This research was supported by the Personnel and Training Research Programs, Psychological Sciences Division, Office of Naval Research, under Contract Number N00014-82C0067, Contract Reproduction in whole or in part is permitted for Authority Identification Number NR 667-477. any purpose of the United States Government. Approved for public release: distribution unlimited. 6 3 0 TABLE OP CONTENTS 1. Objectives of the Research 6 1.1 The psychological goal: Step theory and repair theory 6 1.2 "1 he methodological goal: competitive arguments for each hypothesis 11 1.3 Overview of the theory and the document 17 2. Sierra. the Model 21 2.1 The top level of Sierra 22 2.2 The representation of observables: lessons and diagnostic tests 26 2.3 The representation of procedures 31 2.4 The representation of grammars 34 2.5 The representation of patterns 37* 2.6 An introduction to induction 39 2.7 The learner 43 2.8 Core procedure trees for the Southbay experiment 2.9 The solver 55' 2.10 Observational adequacy 61 2.11 A comparison with other generative theoricsof bugs 68 rrEcrukil PART 1: ARCH LEVgL 3. Getting Started 72 3.1 Teleology or program? 72 3.2 What kind of learning goes on in the classroom? 75 3.3 Learning by discovery 79 3.4 Learning by analogy 80 3.5 Learning by being told 82 3.6 Summary and formalization 83 4. The Disjunction Problem 86 4.1 An introduction to the disjunction problem 86 4.2 Barring disjunction from procedures 92. 4.3 Neves' ALEX learner 94 4.4 Exactly one disjunct per lesson 95 4.5 Minimal disjuncts vs. one-disjunct-per-lesson 96 4.6 Formal hypotheses 99 5. The Invisible Objects Problem 101 5.1 Barring invisible objects 104 5.2 Unbiased induction with Jots of examplei 104 5.3 Minimal number of invisible object designators 105 5.4 Show work 107 5.5 invisible objects, disjunctions, and Occam's Razor 110 6. Local Problem Solving 111 6.1 Explaining bugs with overgeneralization 111 6.2 Stretching overgcneralization to account for certain bugs 115 6.3 impasse-repair independence 117 6.4 Dynamic vs. static local problem solving 122 .6.5 Formal hypotheses 127 C. 4 7. Deletion 129 7.1 I.ocal problem sok'ng will not gcncratc certain bugs 129 7.2 Overgencralization should not gcncratc the deletion bugs 130 7.3 "l he problems of defining a deletion operator 131 8. Summary: Architecture Level 132 8.1 The architecture of the model 132 8.2 Hypotheses and their support 133 8.3 Commentary on the arguments and inherent problems 137 8.4 Preview of Part 2 138 PART 2: REPRESENTATION LEVEL 9. Control Flow 141 9.1 Chronological, Dependency-directed and Hierarchical Backup 142 9.2 One-disjunctper-lesson entails recursive cor trot structure 144 9.3 More powerful control structures 147 9.4 Summary and formalization 147 152 10. Goal Types 10.1 Assimilation is incompatible with the And hypothesis 154 10.2 The And-Or hypothesis simplifies the Backup repair 156 10.3 Rule deletion needs the And-or distinction 156 10.4 Satisfaction Conditions 160 10.5 Summary, formal hypotheses and conflict resolution 163 (II. Data Flow 0 167 11.1 The hypothesis that there is no data flow 168 11.2 Focus is not globally bound 169 11.3 The applicative hypothesis 172 11.4 Summary and formalization 173 12. Searching the Current Problem State 175 12.1 Search loops 175 12.2 Pattern matching 176 0 12.3 Function nests as representations of paths 177 12.4 Summary and fortnalhation 178 13. Ontology 180 , 13.1 Problem state spaces 181 -------132 Aggregate- object-definitionsnflxed spatial relations 183 13.3 Grammars 185 0 13.4 Summary and formal hypotheses 188 14. Pattern Power 191 14.1 Viewing patterns as logics 191 14.2 Predicates, conjunctions and Skolcm constants 193 14.3 Constants, negations and functions 193 14.4 Disjunctions arc needed for variables and Skolem functions 194 14.5 Disjunctions in patterns 195 14.6 Summary and formal hypotheses 197 8 5 ,, . % 9 15. Syntax of the Representation Languages 198 ,. 198 ,15.1 Syntax of the procedure representation language 15.2 Syntax of the grammar representation language 202 . . 16. Summary: Representation 206 IANCi l6.1 Tile interface issue 207 16.2 The internal state issue 209 16.3 The lei rner 211 16.4 'Ile solver 214 of the bias level 16.5 Preview 219 PART 3: BIAS LEVEL Ar or One 17. Two Pasterns 220 17.1 The fetch bugs 220 17.2 Test patterns * fetch patterns 223 224' 17.3 Fonnalihypotheses 18. Fetch Patterns 225 3 18.1 Version spaces 225 18.2 Two hypotheses 227 18.3 The patiern focus nypothesis 228 18.4 Teleological rationalizations 230 18.5 Exact matching vs. Closest matching 231 18.6 When does mismatching trigger repair? 233 18.7 Summary 233 19. Test Patterns and Skeletons 234 19.1 The topological bias hypothesis 235 19.2 Step Schemata 243 19.3 Summary 247 20. Summary: Bias level 248 21. Conclusions 254 21.1 Strengths and weaknesses in the theory 254 21.2 Directions for future research 256 References 258 Appendices Al A bug glossary 266 A2 Observed bug sets 273 'A3 Bug occurrence 'frequencies 277 A4 Predicted bug sets 281 AS Observed bug sets, overlapped by predicted bug sets 284 A6 Predicted bug sets, overlapped by observed bug sets 289 A7 Verdon spaces as applicability conditions 293 AS Interstate reference 297 A9 The Backup repair and the goal stack 303 MO Satisfaction conditions 319 9 6 Chapter 1 ' Objectives of the Research 'V 1 , i N,. ThCri arc two goals for the research presented here. One is psychological and the other is "r1 methodological. 'The psychological goal is to formulate and validate a theory of a certain kind of human learning. The methodological goal is to use artificial intelligence (Al) techniques to model that learning, and to do it in such a way that the complexity of the Al-based model does not prdent the theory from meeting rigorous criteria of scientific validity. The first section of this chapter discusses the psychological goal; the sccodd section discusses the methodological one. The third section introduces -the organization of the rest of the document: . . 111 The psychological goal: Step theory and repair theory One goat of this research is a psychologically valid theory of how people learn certain There arc .other Al-based theories of skill acquisition (e.g.. Anderson. 1982; procedural skills. However, their objectives differ from the ones pursued here. They Newell & Rosenbloom. 1981). concentrate on the transformation of slow, stumbling performance into knowledge compilation: performance that is "faster and more judicious in choice" (Anderson. 1982. pg. 404). They sjudy skills that arc taught in a simple way: first the task is explained, then it is practiced until proficiency is attained. For instance, Anzai and Simon (1979) modelled a subject whose skill at, solving the Tower of Hanoi puzzle evolved frcim a slow, stumbling first attempt into an ability to solve the puzzle rapidly using the optimal sequence of moves. The subject received no instruction after the' The research presented here studies initial description of the puzzle's operations and objectives. skills that arc taught in a more complex way: the instruction is a lesson sequence. where each lesson consists of explanation and practice of some small piece (subskill) of the ultimate procedural skill. Studying multilesson skill acquisition shifts the central focui away from practice effects (knowlcdie compilation) and towards a kind of student cognition that could be called the knowledge integration: construction of a procedural skill from lessons on its subskills. This study puts more emphasis on the teacher's role than the knowledge compilation research I( is not the case that multi-lesson skill acquisition occurs with just any lesson sequence. does. Rather, the lesson sequences arc designed by the teacher to facilitate knowledge integration. Knowledge integration, in turn, is "designed" to work only with certain kinds/of lesson sequences. So, what is really being studied is a teacher-student system that has both cognitive and cultural An equally appropriate name for the central focus of this research is Anowledgc roots. the transmission of a procedural skill via lessons on subskilts. its communication: The skills chosen fOr the present investigation are ordinary, written mathematical calculations. The main advantage of mathematitial procedures. from the experimenter's point of view, is that they are virtually meaningless for the learner. They seem as isolated Rom common sense intuitions as In the case of the subtraction procedure, for the nonsense syllables of early learning research. example, most elementary school students have only a dim conception of its underlying semantics, which is rooted in the base-ten representation of numbers. When compared to the procedures they use to operate vending machines or play games, arithmetic procedures are as dry, formal and 10