COLT '89 - Proceedings of the Second Annual Workshop, UC Santa Cruz, California, July 31 - August 2 1989

Front Cover

Proceedings of the Second Annual Workshop on Computational Learning Theory

Copyright Page

Table of Contents

Foreword

Part 1: Invited Lecture

Chapter 1. Inductive Principles of the Search for Empirical Dependences

§1. Introduction

§2. The problem of expected risk minimization

§3. The principle of empirical risk minimization

§4. The concept of consistency and strong consistency

§5. Strong consistency and uniform convergence

§6. Necessary and sufficient conditions of uniform convergence

§7. The relation to the theory of falsifiability by K. Popper

§8. The capacity of a set of functions

§9. Theorems about the rate of uniform convergence

§10. The principle of structural risk minimization

§11. Concluding remarks

REFERENCES

Part 2: Technical Papers

Chapter 2. Polynomial Learnability of Semilinear Sets

Abstract

1 Introduction

2 Results and Significance

3 Learnability Models Used

4 Classes of Concepts Considered

5 Technical Details

6 Open Problems

Acknowledgments

References

Chapter 3. LEARNING NESTED DIFFERENCES OF INTERSECTION-CLOSED CONCEPT CLASSES

ABSTRACT

1 Introduction

2 The Inclusion-Exclusion Algorithms

3 Conclusions and Open Problems

4 Acknowledgements

References

Chapter 4. A Polynomial-time Algorithm for Learningfc-variable Pattern Languages from Examples

1 Introduction

2 Definitions and Notation

3 The Algorithm COVER

4 Good Things and Bad Things

5 The Event Tree

6 Putting it All Together

7 Conclusions and Future Research

References

Chapter 5. ON LEARNING FROM EXERCISES

ABSTRACT

1. INTRODUCTION

2. LEARNING FROM SOLVED INSTANCES

3. AN APPLICATION

4. LEARNING FROM EXERCISES

5. CONCLUSION

Acknowledgements

References

Appendix A

Chapter 6. On Approximate Truth

Abstract

1 Introduction

2 Approximate Truth

3 Some deductive logic of approximate truth

4 Some inductive logic of approximate truth

5 Stable predicates

6 Concluding remarks

7 References

Chapter 7. Informed parsimonious inference of prototypical genetic sequences

Abstract

1 Introduction

2 Model of sequence generation

3 Bayes model

4 Expressing the inductive assumptions

5 Computing the optimal theory

6 Experimental results

7 Comparison to the biological parsimony methods

8 Acknowledgements

References

Chapter 8. COMPLEXITY ISSUES IN LEARNING BY NEURAL NETS

Abstract

1 INTRODUCTION

2 DEFINITIONS

3 NEURAL NET DESIGN PROBLEMS

4 TRAINING NEURAL NETS

5 CASCADE NEURAL NETS

6 CONCLUSIONS

REFERENCES

Chapter 9. Equivalence Queries and Approximate Fingerprints

Abstract

1 Introduction

2 The basic idea

3 Representations of concepts

4 Some examples of approximate fingerprints

5 Comments

6 Acknowledgments

References

Chapter 10. LEARNING READ-ONCE FORMULAS USING MEMBERSHIP QUERIES

ABSTRACT

1. INTRODUCTION

2. LEARNING EQUIVALENT READ-ONCE FORMULAS FROM EXPLICITLY GIVEN FORMULAS

3. PRELIMINARIES

4. LEARNING READ-ONCE FORMULAS WITH A RELEVANT POSSIBILITY ORACLE

5. LEARNING MONOTONE READ-ONCE FORMULAS USING MEMBERSHIP QUERIES

6. LEARNING READ-ONCE FORMULAS USING A PROJECTIVE EQUIVALENCE ORACLE

7. EXTENSIONS AND OPEN PROBLEMS

8. SUMMARY

References

Chapter 11. LEARNING SIMPLE DETERMINISTIC LANGUAGES

ABSTRACT

INTRODUCTION

PRELIMINARIES

CONTEXT-FREE GRAMMARS AND LANGUAGES

SDG AND SDL

MODELS AND INCORRECTNESS/CORRECTNESS

TYPES OF QUERIES

THE LEARNING ALGORITHM

AN OUTLINE OF THE ALGORITHM

GENERATING NONTERMINALS WITH THEIR MODELS

CORRECTNESS AND COMPLEXITY

CONCLUSION

Acknowledgements

References

Chapter 12. Learning in the Presence of Inaccurate Information

ABSTRACT

INTRODUCTION

NOTATION

IDENTIFICATION WITH INACCURATE INPUT

HIERARCHY RESULTS

RELATIVE EFFECTS OF DIFFERENT TYPES OF INACCURACIES

LANGUAGE LEARNING

CONCLUDING REMARKS

Acknowledgements

References

Chapter 13. Convergence to Nearly Minimal Size Grammars by Vacillating Learning Machines

ABSTRACT

Preliminaries

Language Learning by Vacillating Machines

Convergence to Nearly Minimal Size Grammars

A Characterization of TxtMfexab Criteria

Comparison of Learning with and without Size Restrictions

References

Chapter 14. Inductive Inference with Bounded Number of Mind Changes

ABSTRACT

OVERVIEW

NOTATIONS, DEFINITIOS AND PRIOR RESULTS

INFERENCE WITH BOUNDED NUMBER OF MIND CHANGES

CONCLUSIONS AND OPEN PROBLEMS

ACKNOWLEDGEMENTS

REFERENCES

Chapter 15. LEARNING VIA QUERIES TO AN ORACLE

ABSTRACT

1. INTRODUCTION

2. NOTATION AND DEFINITIONS

3. INFERRING REC

4. WHEN ORACLES DO NOT HELP

5. WHEN ORACLES DO HELP

6. BOUNDING MIND CHANGES

7. OPEN QUESTIONS AND THE DEGREE OF INFERABILITY

REFERENCES

Chapter 16. LEARNING STRUCTURE FROM DATA: A SURVEY

ABSTRACT

1. INTRODUCTION

2. IDENTIFYING TREES

3. IDENTIFYING POLYTREES

4. IDENTIFYING TREES WITH HIDDEN VARIABLES

5. IDENTIFYING TREE STRUCTURES IN CATEGORICAL RELATIONS

6. IDENTIFIABILITY VS. LEARNABILITY

EXAMPLES

CONCLUSIONS

Acknowledgements

References

Chapter 17. A Statistical Approach to Learning and Generalization in Layered Neural Networks

Abstract

1. Introduction

2. Probability inference in the network space

3. Predictions and generalization

4. Asymptotic learning curves in the self-averaging case

Acknowledgment

REFERENCE

Chapter 18. THE LIGHT BULB PROBLEM

ABSTRACT

INTRODUCTION

A QUADRATIC-TIME ALGORITHM

ALGORITHM A

ALGORITHM B

BOOTSTRAP TECHNIQUE

k–WAY CORRELATION

k–WAY CORRELATION FOR ARBITRARY k

Acknowledgments

References

Chapter 19. From On-line to Batch Learning

Abstract

1 Introduction

2 Description of Models and Terminology

3 Converting from On-line to Batch

4 Chernoff Bounds for Supermartingales

5 The Conversion

6 Comparisons

References

Chapter 20. A PARAMETRIZATION SCHEME FOR CLASSIFYING MODELS OF LEARNABILITY

Abstract

1. INTRODUCTION

2. BASIC DEFINITIONS

3. THE UNIFORMITY PARAMETER

4. SOLID LEARNABILITY

5. COVERING RELATIONS BETWEEN CONCEPT CLASSES

Acknowledgements

REFERENCES

Chapter 21. On the Role of Search for Learning

Abstract

1 Introduction

2 Preliminaries

3 A More Powerful Enumeration Technique

4 Barzdins' Conjecture

5 Implications for Systems that Learn

6 Acknowledgments

References

Chapter 22. ELEMENTARY FORMAL SYSTEM AS A UNIFYING FRAMEWORK FOR LANGUAGE LEARNING

ABSTRACT

1 INTRODUCTION

2 PRELIMINARIES

3 EFS AS A LOGIC PROGRAMMING LANGUAGE

4 THE CLASSES OF EFS LANGUAGES

5 INDUCTIVE INFERENCE OF EFS LANGUAGES

6 CONCLUSION

References

Chapter 23. IDENTIFICATION OF UNIONS OF LANGUAGES DRAWN FROM AN IDENTIFIABLE CLASS

ABSTRACT

INTRODUCTION

BASIC CONCEPTS

NEW RESULTS

Chapter 24. INDUCTION FROM THE GENERALTO THE MORE GENERAL

ABSTRACT

1. INTRODUCTION

2. FORMAL PRELIMINARIES

3. RESULTS

4. CONCLUSION

Acknowledgments

References

Chapter 25. SPACE-BOUNDED LEARNING AND THE VAPNIK-CHERVONENKIS DIMENSION

ABSTRACT

INTRODUCTION

THE DATA COMPRESSION SCHEME

AN ALGORITHM FOR THE COMPRESSION FUNCTION

SIMPLE PLANAR ARRANGEMENTS

MAXIMUM CLASSES OF VC DIMENSION TWO

APPLICATIONS

SIMPLE ARRANGEMENTS

POSITIVE HALF-SPACES

VECTOR SPACES OF REAL FUNCTIONS

CONCLUSIONS AND OPEN PROBLEMS

Acknowledgements

References

Chapter 26. Reliable and Useful Learning

Abstract

1 Introduction

2 Reliable and probably useful learning

3 Basic results

4 Learnability of boolean concepts

5 Learnability of rectangles

6 General conditions for learnability

7 Summary and conclusions

Acknowledgements

References

Part 3: Short Abstracts

Chapter 27. The Strength of Weak Learnability

Chapter 28. ON THE COMPLEXITY OF LEARNING FROM COUNTEREXAMPLES

ABSTRACT

Chapter 29. Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results

Chapter 30. A Theory of Learning Simple Concepts Under Simple Distributions

ABSTRACT

Chapter 31. Learning Binary Relations and Total Orders

Chapter 32. The Weighted Majority Algorithm

Abstract

Author Index