Proceedings of the Third Annual Workshop on Computational Learning Theory University of Rochester, Rochester, New York, August 6-8, 1990
COLT Proceedings 1990
| Autor principal: | |
|---|---|
| Autores Corporativos: | , , |
| Otros Autores: | , |
| Formato: | Libro electrónico |
| Idioma: | Inglés |
| Publicado: |
San Mateo, Calif. :
Morgan Kaufmann Publishers
c1990.
|
| Colección: | ACM Conferences
|
| Materias: | |
| Ver en Biblioteca Universitat Ramon Llull: | https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009634674506719 |
Tabla de Contenidos:
- Front Cover; Computational Learning Theory; Copyright Page; Foreword; Table of Contents; Part 1: Invited Lecture; Chapter 1. INDUCTIVE INFERENCE OF MINIMAL PROGRAMS; Abstract; 1. INTRODUCTION; 2. UNIONS OF IDENTIFIABLE CLASSES; 3. STRUCTURE OF THE PARTIAL ORDERING; 4. NEARLY MINIMAL INDICES; 5. KOLMOGOROV NUMBERINGS; ACKNOWLEDGMENT; REFERENCES; Part 2: Technical Papers; Chapter 2. Identifying μ-Formula Decision Trees with Queries; Abstract; 1 Introduction; 2 Definitions and Terminology; 3 The Identification Algorithm; 4 Identification with Membership or Equivalence Queries Alone; 5 Conclusion
- ReferencesChapter 3. LEARNING SWITCH CONFIGURATIONS; ABSTRACT; INTRODUCTION; DEFINITIONS AND CONCEPTS; AN ALGORITHM FOR LEARNING SWITCH CONFIGURATIONS; PROOFS OF CORRECTNESS AND TIME COMPLEXITY; CONCLUSIONS; References; Chapter 4. On the Computational Complexity of Approximating Distributions by Probabilistic Automata; Abstract; 1 Introduction; 2 Statement of Results; 3 The Sample Complexity Bounds; 4 Computational Complexity of Training Probabilistic Automata; 5 Concluding Remarks; Acknowledgements; References; Chapter 5. A Learning Criterion for Stochastic Rules; Abstract; 1 Introduction
- 2 Stochastic Rules and Their Hierarchical Parameter Structures3 A Learning Criterion for Stochastic Rules - A Stochastic PAC Model; 4 Hierarchical Learning Based on the MDL Principle; 5 The Optimality of MDL Rules and Their Convergence Rates; 6 Sample Complexity and Learnability of Stochastic Decision List Classes; 7 Concluding Remarks; References; Chapter 6. ON THE COMPLEXITY OF LEARNING MINIMUM TIME-BOUNDED TURING MACHINES; Abstract; 1. INTRODUCTION; 2. DEFINITIONS; 3. MAIN RESULTS; 4. PROOFS; 5. OPEN QUESTIONS; References; Chapter 7. INDUCTIVE INFERENCE FROM POSITIVE DATA IS POWERFUL
- ABSTRACTINTRODUCTION; PRELIMINARIES; ELEMENTARY FORMAL SYSTEMS; INDUCTIVE INFERENCE FROM POSITIVE DATA; INDUCTIVE INFERENCE OF EFS MODELS FROM POSITIVE DATA; INDUCTIVE INFERENCE OF EFS LANGUAGES FROM POSITIVE DATA; DISCUSSION; Acknowledgments; References; Chapter 8. INDUCTIVE IDENTIFICATION OF PATTERN LANGUAGES WITH RESTRICTED SUBSTITUTIONS; ABSTRACT; PATTERN LANGUAGES OVER AN ARBITRARY BASE; PUMPING LEMMA; APPLICATION TO INDUCTIVE INFERENCE; References; Chapter 9. Pattern Languages Are Not Learnable; 1 Introduction; 2 PRELIMINAR IES; 3 The Main Result; Acknowledgments; References
- Chapter 10. On Learning Ring-Sum-ExpansionsAbstract; 1· Introduction and Definitions; 2. Learnability of k-RSE; 3· Nonlearnability of k-term-RSE; 4. Learnability from negative examples only; 5. Predictability; 6. Sample size and worstcase mistake bounds; 7· Summary; References; Chapter 11. Learning Functions of κ Terms; Abstract; 1 Introduction; 2 Notation and definitions; 3 The learning algorithm; 4 Hardness results; 5 Conclusion; References; Chapter 12. On the Sample Complexity of Pac-Learning using Random and Chosen Examples*; Abstract; 1 Introduction; 2 Definitions; 3 Lower Bound
- 4 Smoothness Guarantees
