Machine Learning Proceedings 1992 (eBook)

Proceedings of the Ninth International Workshop (ML92)

Peter Edwards, Derek Sleeman (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
448 Seiten
Elsevier Science (Verlag)
978-1-4832-9853-5 (ISBN)

Infos

Machine Learning Proceedings 1992

Inhalt

Front Cover 1
Machine Learning 2
Copyright Page 3
Table of Contents 4
Preface 8
Program Committee 9
ML 92 Informal Workshop Themes and Coordinators 9
Chapter 1. Generalizing from Case Studies: A Case Study 10
Abstract 10
1 PROBLEM AND OBJECTIVES 10
2 GENERALIZING CASE STUDIES 11
3 AN APPLICATION 12
4 LIMITATIONS 18
5 CONCLUSION 19
Acknowledgements 19
References 19
Chapter 2. On Learning More Concepts 20
Abstract 20
1 INTRODUCTION 20
3 UPPER BOUND ON COVERAGE 22
4 THE MULTI-BALLS LEARNING ALGORITHM 22
5 THE LARGE-BALL LEARNING ALGORITHM 25
6 COVERAGE OF CURRENT LEARNING ALGORITHMS 26
7 DISCUSSION 27
Acknowledgements 27
References 27
Chapter 3. The Principal Axes Method for Constructive Induction 29
Abstract 29
1 INTRODUCTION 29
2 LEARNING PRINCIPAL AXES 30
3 DISTANCE METRIC 31
4 GENERATING SIMILARITY MATRIX 31
5 DESCRIPTION SPACE TRANSFORMATION 32
6 EMPIRICAL EVALUATION 34
7 SUMMARY 34
Acknowledgments 35
References 36
Chapter 4. Learning by Incomplete Explanations of Failures in Recursive Domains 39
Abstract 39
1 Introduction 39
2 Means-ends analysis search in recursive domains 39
3 Problem solving and learning in FS2 40
4 Experimental results 42
5 Related work 43
6 Conclusions and future work 44
References 44
Chapter 5. Eliminating Redundancy in Explanation-Based Learning 46
Abstract 46
1 INTRODUCTION 46
2 PRELIMINARIES 47
3 EXAMPLE-GUIDEDUNFOLDING 47
4 EXPERIMENTAL RESULTS 49
5 RELATED WORK 49
6 CONCLUDING REMARKS 50
References 50
Chapter 6. Trading off Consistency and Efficiency in Version-Space Induction 52
Abstract 52
1 INTRODUCTION 52
2 LEARNING WITH VARIABLE-FACTORED CONJUNCTIVE CONCEPT LANGUAGES 53
3 THE FCE LEARNING ALGORITHM 53
4 UTILITY 55
5 RELATION TO INDUCTIVE LANGUAGE SHIFT 57
6 CONCLUSION 57
Acknowledgements 57
References 57
Chapter 7. Peepholing: choosing attributes efficiently for megainduction 58
Abstract 58
1 INTRODUCTION AND MOTIVATION 58
2 PEEPHOLING 59
3 SHORTLISTING 59
4 BLINKERING 61
5 EMPIRICAL EVALUATION 62
6 CONCLUSIONS 63
Acknowledgements 63
References 63
Chapter 8. Improving Path Planning with Learning 64
Abstract 64
1 INTRODUCTION 64
2 ALGORITHM 64
3 GENERAL ANALYSIS 66
4 SPECIFIC CASE ANALYSIS 68
5 COMPUTATIONAL EXPERIENCE 69
6 FUTURE WORK 70
7 CONCLUSION 70
Acknowledgements 70
References 70
CHAPTER 9. THE RIGHT REPRESENTATION FOR DISCOVERY: FINDING THE CONSERVATION OF MOMENTUM 71
Abstract 71
1 INTRODUCTION 71
2 CONSERVATION OF MOMENTUM 72
3 CONVENTIONAL MATHEMATICAL APPROACH 72
4 THE DIAGRAMMATIC APPROACH 75
5 DISCUSSION 79
6 CONCLUSIONS 80
Acknowledgements 80
References 80
Chapter 10. Learning to Predict in Uncertain Continuous Tasks 81
Abstract 81
1 Introduction 81
2 Assumptions 82
3 Manipulation Tasks 82
4 Noise and Uncertainty 83
5 Generalization 83
6 Funnels 83
7 Learning Funnels 84
8 Experiments 87
9 Assumptions Revisited 89
Acknowledgements 90
References 90
Chapter 11. Lazy Partial Evaluation: An Integration of Explanation-Based Generalisation and Partial Evaluation 91
Abstract 91
1 Introduction 91
2 Lazy Partial Evaluation 92
3 Application to Constraint Satisfaction 94
4 Discussion 98
5 Conclusion 98
Acknowledgements and Availability 98
References 98
Chapter 12. A Teaching Method for Reinforcement Learning 101
Abstract 101
1 INTRODUCTION 101
2 TEACHING METHOD 102
3 INTEGRATING THE METHOD 102
4 EXPERIMENT ONE: CART-POLE AND ACE/ASE 103
5 EXPERIMENT TWO: RACE TRACK AND Q-LEARNING 106
6 CONCLUSIONS 109
Acknowledgments 110
References 110
Chapter 13. Compiling Prior Knowledge Into an Explicit Bias 111
Abstract 111
1 PROBLEMS FACING THEORY-GUIDED LEARNING 111
2 EXPLICITLY BIASED LEARNING 113
3 ANTECEDENT DESCRIPTION GRAMMARS 113
4 EXPERIMENTAL RESULTS 116
5 CONCLUSIONS 117
Acknowledgements 118
A GRENDEL's LEARNING ALGORITHM 118
References 119
Chapter 14. Spatial analogy and subsumption 120
1 Introduction 120
2 Spatio–analogical inference 120
3 Subsumption and generalization 121
4 Retrieval and indexing 122
5 Results 124
6 Discussion 124
Acknowledgements 125
References 125
Chapter 15. Learning to Satisfy Conjunctive Goals 126
Abstract 126
1 Motivation 126
2 Opportunism and Learning 127
3 An example 128
4 When are plans for conjunctive goals necessary? 129
5 Reasons for saving plans for conjunctive goals 129
6 Stability and Enforcement 130
7 Stability and evaluation 130
8 Conclusion 131
Acknowledgements 131
References 131
Chapter 16. Multistrategy Learning with Introspective Meta-Explanations 132
Abstract 132
1 INTRODUCTION 132
2 REPRESENTATION OF INTROSPECTIVE META-XPS 133
3 DISCUSSION 136
Acknowledgements 136
References 136
Chapter 17. An Asymptotic Analysis of Speedup Learning 138
Abstract 138
1 Introduction 138
2 Meta-Level Problem Solvers 138
3 Polynomial-time Problem Solving 141
4 Macro Problem Solvers 141
5 Conclusion 143
Acknowledgments 144
References 144
Chapter 18. Why EBL Produces Overly-Specific Knowledge: A Critique of the PRODIGY Approaches 146
Abstract 146
1 Motivation 146
2 The Problem of Logical Minimization 147
3 Avoiding Overly-Specific Conditions 148
4 Related Work 151
5 Conclusion 152
References 152
Chapter 19. Automatic Feature Generation for Problem Solving Systems 153
Abstract 153
1 INTRODUCTION 153
2 PROBLEM SOLVING, EVALUATION FUNCTIONS AND FEATURES 154
3 A THEORY OF FEATURE GENERATION 154
4 THE ZENITH SYSTEM 155
5 DOMAINS AND RESULTS 159
6 CONCLUSION 162
Acknowledgements 162
References 162
Chapter 20. Towards Inductive Generalisation in Higher Order Logic 163
Abstract 163
1 Introduction 163
2 Motivation 164
3 M.: a restricted higher order language 165
4 M. normal and nonredundant terms 165
5 Implementation 166
6 Applications 167
7 Conclusion and future research directions 168
Acknowledgements 169
A Syntax of .-calculus terms 169
B Extension to d0 conversion 170
References 170
Chapter 21. Ordering Effects in Clustering 172
Abstract 172
1 INTRODUCTION 172
2 A REVIEW OF COBWEB 172
3 ORDERING EFFECTS 173
4 CONTROL STRATEGIES 174
5 ORDER INDEPENDENCE 175
6 CONCLUDING REMARKS 177
References 177
Chapter 22. Learning Structured Concepts Using Genetic Algorithms 178
Abstract 178
1 INTRODUCTION 178
2 WHY A GENETIC ALGORITHM? 179
3 GA-SMART OVERVIEW 179
4 MAPPING FORMULAE TO BIT STRINGS 180
5 GENETIC ALGORITHM DETAILS 181
6. EXPERIMENTATION WITH STANDARD TEST CASES 183
7 DISCUSSION 186
Acknowledgements 186
References 186
Chapter 23. An Analysis of Learning to Plan as a Search Problem 188
Abstract 188
1 INTRODUCTION 188
2 LEARNING AS SEARCH 188
3 FRAMEWORK OF SIMPLIFICATIONS 189
4 APPLYING THE FRAMEWORK 192
5 CONCLUSIONS 196
Acknowledgements 196
References 196
Chapter 24. An Approach to Anytime Learning 198
Abstract 198
1 INTRODUCTION 198
2 AN ARCHITECTURE FOR ANYTIME LEARNING 199
3 A CASE STUDY 200
4 SUMMARY 203
References 204
Chapter 25. Artificial Universes - Towards a Systematic Approach to Evaluating Algorithms which Learn from Examples 205
Abstract 205
1. INTRODUCTION 205
2. MODELLING NOISE IN THE DOMAIN RULES 205
3. A UNIVERSE: A PROBABILISTIC MODEL OF A DOMAIN 206
4. CONSTRUCTING A UNIVERSE - A WORKED EXAMPLE 207
5. INFORMATION IN THE UNIVERSE -EVALUATING INDUCED RULES 207
6 EXPERIMENTS USING ID3 ON GENERATED EXAMPLES 211
7 CONCLUSION AND FUTURE WORK 213
References 213
Chapter 26. Average Case Analysis of Learning k-CNF Concepts 215
Abstract 215
1 INTRODUCTION 215
2 AN AVERAGE CASE MODEL OF k-CNF 215
3 IMPLICATIONS OF THE MODEL 218
4 VIOLATING ASSUMPTIONS 219
5 CONCLUSION 219
Acknowledgements 220
References 220
Chapter 27. The MENTLE Approach to Learning Heuristics for the Control of Logic Programs 221
Abstract 221
1 INTRODUCTION 221
2 HEURISTICS FOR GOAL SELECTION 221
3 MENTLE LEARNING ALGORITHM 222
4 CONTRADICTION 225
5 RESULTS FROM MENTLE 225
6 FURTHER DEVELOPMENT 226
References 226
Chapter 28. Fuzzy Substructure Discovery 227
Abstract 227
1 INTRODUCTION 227
2 SUBSTRUCTURE DISCOVERY 227
3 FUZZY GRAPH MATCH 229
4 FUZZY SUBSTRUCTURE DISCOVERY 230
5 EXAMPLES 231
6 CONCLUSIONS 232
References 232
Chapter 29. Efficient Classification of Massive, Unsegmented Datastreams 233
Abstract 233
1 INTRODUCTION 233
2 EXISTING ML APPROACHES FOR FINDING MOTIFS IN DATASTREAMS 234
3 OUR APPROACH 234
4. TESTING THE CLUSTERER: THE PROTEIN EVOLUTION SIMULATOR 238
5. APPLICATION TO REAL DATA 238
6. CONCLUSIONS 240
References 240
Chapter 30. Induction of One-Level Decision Trees 242
Abstract 242
1 INTRODUCTION 242
2 ANALYSIS OF THE ONE-LEVEL ALGORITHM 242
3 BEHAVIOR OF THE ONE-LEVEL ALGORITHM 245
4 DISCUSSION 248
Acknowledgements 249
References 249
Chapter 31. Combining Competition and Cooperation in Supervised Inductive Learning 250
Abstract 250
1 Preliminaries 250
2 DESIGN 251
3 EXPERIMENTS 254
4 SUMMARY 256
References 256
Chapter 32. A Practical Approach to Feature Selection 258
Abstract 258
1 INTRODUCTION 258
2 Relief ALGORITHM 259
3 EMPIRICAL EVALUATION 259
4 CURRENT LIMITATION AND FUTURE WORK 263
5 RELATED WORK 263
6 CONCLUSION 264
Acknowledgements 264
References 265
Chapter 33. Learning as Optimization: Stochastic Generation of Multiple Knowledge 266
Abstract 266
1 INTRODUCTION 266
2 HEURISTIC FUNCTIONS 267
3 STOCHASTIC LEARNING 267
4 COMBINING MULTIPLE RULES 268
5 EXPERIMENTS 269
6 DISCUSSION 270
Acknowledgements 271
References 271
Chapter 34. Dynamic Optimization 272
Abstract 272
1 Introduction 272
2 Related Work 273
3 The TDAG 274
4 Using a TDAG to learn Clause Sequences 275
5 The Optimizer Algorithm 276
6 The Learn-Optimize Cycle 277
7 Experimental Results 278
8 Summary: the Learn-Optimize Model 280
9 Acknowledgments 281
References 281
Chapter 35. Sub-unification: A Tool for Efficient Induction of Recursive Programs 282
Abstract 282
1 INTRODUCTION 282
2 THE FRAMEWORK 283
3 SUB-UNIFICATION 284
4 A LEARNING SYSTEM BASED ON SUB-UNIFICATION 286
5 IMPLEMENTATION AND FIRST COMPARISON 288
6 CONCLUSION AND FUTURE WORK 289
Acknowledgements 289
References 289
Chapter 36. Augmenting and Efficiently Utilizing Domain Theory in Explanation-Based Natural Language Acquisition 291
Abstract 291
1 Introduction 291
2 Extending the dynamic domain theory 292
3 Problem solving strategies and the knowledge utility problem 294
4 Experiment and discussion 295
5 Conclusion 297
Acknowledgement 297
References 297
Chapter 37. Enhancing Transfer in Reinforcement Learning by Building Stochastic Models of Robot Actions 299
Abstract 299
1 Motivation 299
2 Action Models 300
3 Temporal Projection 302
4 A Simulated Robot Testbed 303
5 Experimental Results 304
6 Discussion 306
7 Related Work 307
8 Conclusions 307
9 Acknowledgements 307
References 308
Chapter 38. THOUGHT: An Integrated Learning System for Acquiring Knowledge Structure 309
Abstract 309
1. Introduction 309
2. Comparison between SSK and SOK 310
3. Construction of SOK 310
4. Sample Results 314
5. Comparison with Related Work 317
6. Conclusion 317
Acknowledgements 318
References 318
Chapter 39. An Approach to Concept Learning Based on Term Generalization 319
Abstract 319
1 INTRODUCTION 319
2 NET-CLAUSE LANGUAGE 319
3 PATTERN GENERALIZATION 321
4 NCL DATA-DRIVEN LEARNING 322
5 CONCLUSION 324
Acknowledgements 324
References 324
Chapter 40. Using Transitional Proximity for Faster Reinforcement Learning 325
Abstract 325
1 Introduction 325
2 Reinforcement Learning and Q-learning 325
3 Kohonen Networks 326
4 Transitional Proximity Q-learning 327
5 Experimental Results 329
6 Conclusions and Future Work 329
Acknowledgments 330
References 330
Chapter 41. NFDT: A System that Learns Flexible Concepts based on Decision Trees for Numerical Attributes 331
Abstract 331
1 INTRODUCTION 331
2 USING CONTINUOUS ATTRIBUTES IN TDIDT TECHNIQUES 332
3 THE NFDT MODEL 333
4. EMPIRICAL RESULTS 336
5. DISCUSSION 338
6 CONCLUSION & FUTURE WORKS
References 339
Chapter 42. A symbolic algorithm for computing coefficients' accuracy in regression 341
Abstract 341
1 INTRODUCTION 341
2 LINEAR REGRESSION AND ARC 342
3 TWO MAIN SOLUTIONS 342
4 THE HEURISTIC METHOD 343
5. HIGHER DEGREES 344
6. RESULTS ON HIGHER DEGREES 345
7 CONCLUSION 346
Acknowledgments 346
References 346
Chapter 43. Compression, Significance and Accuracy 347
Abstract 347
1 INTRODUCTION 347
2 HYPOTHESIS–PROOF (HP)COMPRESSION 349
3 COMPRESSION AND PROOF ENCODING 350
4 COMPRESSION AND SIGNIFICANCE 351
5 COMPRESSION AND NOISE 351
6 CONCLUSIONS 353
Acknowledgements 353
A HP–COMPRESSION: A GENERAL CODING SCHEME FOR LOGICAL HYPOTHESES AND PROOFS 353
References 355
Chapter 44. Guiding Example Acquisition by Generating Scenarios 357
Abstract 357
1 Introduction 357
2 Guiding Example Postprocessing by Generating Scenarios 358
3 Use and Interest of a New Example 359
4 Guiding Example Postprocessing for an Attribute-Based Learning Algorithm 359
5 Guiding Example Postprocessing for Predicate-Based Learning Algorithms 362
6 Conclusions and Directions 363
References 363
Chapter 45. Constructive Induction Using a Non-Greedy Strategy for Feature Selection 364
Abstract 364
1 Introduction 364
2 Definitions 365
3 Approach description 365
4 The covering algorithm 366
5 Experimental results 368
6 Conclusions 369
Acknowledgements 369
References 369
Chapter 46. Training Second-Order Recurrent Neural Networks using Hints 370
Abstract 370
1 MOTIVATION 370
2 RECURRENT NETWORK 370
3 INSERTING RULES 371
4 LEARNING WITH HINTS 372
5 CONCLUSIONS 374
Acknowledgements 375
References 375
Chapter 47. DYNAMIC: A new role for training problems in EBL 376
Abstract 376
1 MOTIVATION 376
2 BACKGROUND 377
3 DYNAMIC 378
4 LOCAL ANALYSIS VERSUS GLOBAL ANALYSIS (AN EXAMPLE) 379
5 EXPERIMENTAL RESULTS 379
6 COMPARATIVE ANALYSIS 380
7 CONCLUSION 381
Acknowledgments 381
References 381
Chapter 48. A Framework for Discovering Discrete Event Models 382
Abstract 382
1 Introduction 382
2 Fundamentals of Discrete Event Modeling 383
3 Discovering a DE Model 385
4 Summary 387
References 387
Chapter 49. Learning Episodes for Optimization 388
Abstract 388
1 INTRODUCTION 388
2 AUGMENTING SEARCH WITH EPISODES 388
3 DESIGN OPTIMIZATION WITH EASE 390
4 OPTIMIZATIONS FOR LOGIC SYNTHESIS 391
5 RELATED WORK 392
6 CONCLUSIONS 393
Acknowledgments 393
References 393
Chapter 50. Learning to Fly 394
Abstract 394
1. THE PROBLEM 394
2. THE FLIGHT SIMULATOR 394
3. LOGGING FLIGHT INFORMATION 395
4. DATA ANALYSIS 396
5. GENERATING THE AUTOPILOT 398
6. LINKING THE AUTOPILOT WITH THE SIMULATOR 399
7. FLYING ON AUTOPILOT 399
8. DISCUSSION 401
9. CONCLUSION 401
ACKNOWLEDGMENTS 402
REFERENCES 402
Chapter 51. Deconstructing the Digit Recognition Problem 403
Abstract 403
1 Introduction 403
2 The Digit Recognition Problem 404
3 Three Approaches to Pruning 404
4 Experiments 404
5 Discussion 407
6 Acknowledgements 408
References 408
Chapter 52. On Combining Multiple Speedup Techniques 409
Abstract 409
1. INTRODUCTION 409
2. RESOURCE-LIMITED INFERENCE 409
3. EXPERIMENTAL METHODOLOGY 410
4. EXPERIMENTAL RESULTS 411
5. DISCUSSION 413
Acknowledgements 414
References 414
Chapter 53. Scaling Reinforcement Learning Algorithms by Learning Variable Temporal Resolution Models 415
Abstract 415
1 INTRODUCTION 415
2 SCALING ISSUES FOR LEARNING ALGORITHMS BASED ON DYNAMIC PROGRAMMING 416
3 VARIABLE TEMPORAL RESOLUTION MODELS 417
4 A HIERARCHY OF ENVIRONMENT MODELS 420
5 DISCUSSION 422
6 CONCLUSION 423
Acknowledgments 423
References 423
Chapter 54. Detecting Novel Classes with Applications to Fault Diagnosis 425
Abstract 425
1 Introduction 425
2 Discriminative versus Generative Models 426
3 A Probabilistic Formulation of the Problem 428
4 Density Estimation Techniques 429
5 Kernel Approximation using Mixture Densities 429
6 Summary of the EM Procedure 430
7 An Algorithm for Building Centroid Kernel Classifiers 431
8 Application to Fault Diagnosis and Results 432
9 Conclusion 433
Acknowledgements 434
References 434
Chapter 55. Measuring Utility and the Design of Provably Good EBL Algorithms 435
Abstract 435
1 INTRODUCTION 435
2 THE DETAILED COST MODEL 436
3 USE OF THE COST MODEL 439
4 DISCUSSION AND CONCLUSIONS 443
References 444
Chapter 56. Refining a Relational Theory with Multiple Faults in the Concept and Subconcepts 445
Abstract 445
1 Introduction 445
2 Rx and FOIL 445
3 The Refinement Algorithm 446
4 Example of a Refinement 447
5 Experimental Evaluation of Rx 450
6 Comparison with Related Work 450
7 Conclusion 452
Acknowledgements 452
Refernces 452
Chapter 57. Cooperation in Knowledge Base Refinement 454
Abstract 454
1 INTRODUCTION 454
2 AN EXEMPLARY KB SYSTEM 454
3 THE KB REFINEMENT PROBLEM AND METHOD 455
4 ILLUSTRATION OF THE KB REFINEMENT METHOD 456
5 CONCLUSION 459
Acknowledgments 459
References 459
Chapter 58. Temporal Difference Learning of Backgammon Strategy 460
Abstract 460
1 INTRODUCTION 460
2 A CASE STUDY: TD LEARNING OF BACKGAMMON STRATEGY 461
3 TD LEARNING WITH BUILT-IN FEATURES 464
4 Conclusions 464
References 465
Chapter 59. AGIL: solving the Exploration versus Exploitation dilemma in a simple classifier system applied to simulated robotics 467
Abstract 467
1 INTRODUCTION 467
2 AGIL: AN ADAPTIVE GENETIC INCREMENTAL LEARNER 468
3 RESULTS WITH F6 470
4 RESULTS IN ROBOTICS 471
5 CONCLUSION 471
Acknowledgements 472
References 472
Chapter 60. Conceptual Clustering with Systematic Missing Values 473
Abstract 473
1 Introduction 473
2 The ITERATE Algorithm 474
3 Handling Systematic Missing Values 475
4 Experimental Results 476
5 Discussion and Conclusions 477
Acknowledgements 477
References 477
Chapter 61. Selecting Typical Instances in Instance-Based Learning 479
Abstract 479
1 INTRODUCTION 479
2 MEASURING TYPICALITY OF INSTANCES 480
3 SELECTING TYPICAL INSTANCES 482
4 EMPIRICAL EVALUATION 483
5 CONCLUSION 486
Acknowledgements 487
References 487
Chapter 62. The first phase of real-world discovery: determining repeatability and error of experiments 489
Abstract 489
1 Real world discovery: background and motivation 489
2 How FAHRENHEIT interacts with the real world 490
4 How FAHRENHEIT determines repeatability and error 492
5 Conclusions 494
References 494
Author Index 495
Subject Index 496

Produkt-Details

• Erscheint lt. Verlag: 28.6.2014
• Sprache: englisch
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• ISBN-10: 1-4832-9853-1 / 1483298531
• ISBN-13: 978-1-4832-9853-5 / 9781483298535