Computational Learning Theory: 4th European Conference, EuroCOLT'99 Nordkirchen, Germany, March 29-31, 1999 Proceedings (Lecture Notes in Computer Science, 1572)

This volume contains papers presented at the Fourth European Conference on ComputationalLearningTheory, whichwasheldatNordkirchenCastle, inNo- kirchen, NRW, Germany, from March 29 to 31, 1999. This conference is the fourth in a series of bi-annual conferences established in 1993. TheEuroCOLTconferencesarefocusedontheanalysisoflearningalgorithms and the theory of machine learning, and bring together researchers from a wide variety of related elds. Some of the issues and topics that are addressed include the sample and computational complexity of learning speci c model classes, frameworks modeling the interaction between the learner, teacher and the en- ronment (such as learning with queries, learning control policies and inductive inference), learningwithcomplexmodels(suchasdecisiontrees, neuralnetworks, and support vector machines), learning with minimal prior assumptions (such as mistake-bound models, universal prediction, and agnostic learning), and the study of model selection techniques. We hope that these conferences stimulate an interdisciplinary scienti c interaction that will be fruitful in all represented elds. Thirty- ve papers were submitted to the program committee for conside- tion, and twenty-one of these were accepted for presentation at the conference and publication in these proceedings. In addition, Robert Schapire (AT & T Labs), and Richard Sutton (AT & T Labs) were invited to give lectures and contribute a written version to these proceedings. There were a number of other joint events including a banquet and an excursion to Munster ] . The IFIP WG 1.4 Scholarship was awarded to Andra s Antos for his paper \Lower bounds on the rate of convergence of nonparametric pattern recognition". Computational Learning Theory Preface Organization Table of Contents Theoretical Views of Boosting Background Analyzing the training error AdaBoost Generalization error A connection to game theory Estimating probabilities Multiclass classi cation Experiments and applications Open Theoretical Questions in Reinforcement Leraning Control with Function Approximation Monte Carlo Control Efficiency of Bootstrapping A VC Dimension for RL A Geometric Approach to Leveraging Weak Learners Introduction GeoLev - A Geometric Algorithm Relation to Previous Work Convergence Bound Conversion to an Arcing Algorithm Preliminary Experiments Conclusions and Directions for Further Study Query by Committee, Linear Separation and Random Walks Introduction Mathematical Notation Preliminary Observations Few Results about Convex Bodies Modified Query By Committee Algorithms Using Volume Approximation in the QBC Algorithm (QBC') Using Sampling in the QBC algorithm (QBC'') Deriving the Main Results Conclusions and Further Research Acknowledgment Lemmas for QBC'' Hardness Results for Neural Network Approximation Problems Introduction Approximate Optimization Definitions Results Reductions Future Work Learnability of Quantifled Formulas Introduction Formulas and Relations Generating Set Algorithm Learning Subuniverses Coset Generating Operations Near-unanimity Operations Non-learnability results Boolean Case revisited Learning Multiplicity Automata from Smallest Counterexamples Introduction Definitions and Notations Prefixtree Representations The MA Learning Algorithm A Lower Bound on the Number of EQSC Queries Acknowledgements Exact Learning when Irrelevant Variables Abound Introduction Preliminaries Learning with Non-adaptive Membership Queries Learning with Equivalence Queries Approximate Fingerprints The Negative Results Acknowledgments An Application of Codes to Attribute-Efficient Learning Introduction Basic Definitions Learning Parity Functions with k Essential Variables Finding an Input on Which the Teacher Says ``Yes'' Designing Learning Strategies Nearly--Optimal Non--Adaptive Strategies Fine--Tuning Remarks Learning Range Restricted Horn Expressions* Introduction Preliminaries First Order Horn Expressions The Learning Model Range Restricted Horn Expressions Learning from Interpretations Modifying the Hypothesis Language Learning from Entailment The Implication Problem Discussion On the Asymptotic Behavior of a Constant Stepsize Temporal-Difference Learning Algorithm Introduction Algorithm and Assumptions Analysis Conclusion Direct and Indirect Algorithms for On-line Learning of Disjunctions* Introduction An Overview of On-line Learning of Disjunctions The Direct Bayes Algorithm for Disjunctions A Technique for Deriving Indirect Algorithms The Bayesian Framework The Mistake-driven protect elax Bayes-BEG Algorithm The Thresholded-BEG Algorithm The Normalized Winnow Algorithm Conclusions Averaging Expert Predictions Introduction The Setting and the Algorithm Basic Loss Bounds The Basic Upper Bound Proof Bounds Based on the Relative Entropy Multi-dimensional predictions On Teaching and Learning Intersection-Closed Concept Classes Introduction Basic Definitions and Learning Models Preliminary Results Self-directed learning of intersection-closed concept classes and the VC-Dimension The structure of intersection-closed concept classes with high learning complexity Teacher-directed learning - average case Teacher-directed learning - best case Conclusion and Open Problems Appendix Avoiding Coding Tricks by Hyperrobust Learning Introduction General Results Hyperrobust BC-Learning is not Trivial Team-Learning and the Union-Theorem Conclusion Mind Change Complexity of Learning Logic Programs * Motivation and Introduction Ordinal Mind Change Identification Conditions for learnability with mind change bound Learnability from positive data Learnability from positive and negative data Classes of logic programs Conclusion Regularized Principal Manifolds* Introduction The Quantization Error Functional Invariant Regularizers A Regularized Quantization Functional An Algorithm for minimizing R_reg[f] Examples of Regularizers The Connection to the GTM Experiments Uniform Convergence Bounds Covering and Entropy Numbers Rates of Convergence Summing Up Distribution-Dependent Vapnik-Chervonenkis Bounds Introduction and motivations Classical VC bounds Rigorous distribution-dependent results Comparison with Universal VC Bounds PAC-Learning Application of the Result Elements of proof for Theorem 2 Appendix - Chernoff's bound on large deviations Lower Bounds on the Rate of Convergence of Nonparametric Pattern Recognition * Introduction Lower Bounds Proofs On Error Estimation for the Partitioning Classification Rule Introduction Resubstitution estimate Deleted estimate Proofs Margin Distribution Bounds on Generalization Introduction Background Results Main Result Algorithmics Experiments Conclusion Generalization Performance of Classifiers in Terms of Observed Covering Numbers* Introduction Background Results Covering Numbers on a Double Sample Generalization from Covering Numbers Conclusions Entropy Numbers, Operators and Support Vector Kernels* Introduction, Definitions and Notation Operator Theory Methods for Entropy Numbers Generalization Bounds via Uniform Convergence Entropy Numbers for Kernel Machines Mercer's Theorem, Feature Spaces and Scaling Entropy Numbers Empirical Bounds Eigenvalue Decay Rates The Missing Pieces and Some Conclusions Author Index This Volume Contains Papers Presented At The Fourth European Conference On Computationallearningtheory,whichwasheldatnordkirchencastle,inno- Kirchen, Nrw, Germany, From March 29 To 31, 1999. This Conference Is The Fourth In A Series Of Bi-annual Conferences Established In 1993. Theeurocoltconferencesarefocusedontheanalysisoflearningalgorithms And The Theory Of Machine Learning, And Bring Together Researchers From A Wide Variety Of Related Elds. Some Of The Issues And Topics That Are Addressed Include The Sample And Computational Complexity Of Learning Speci C Model Classes, Frameworks Modeling The Interaction Between The Learner, Teacher And The En- Ronment (such As Learning With Queries, Learning Control Policies And Inductive Inference),learningwithcomplexmodels(suchasdecisiontrees,neuralnetworks, And Support Vector Machines), Learning With Minimal Prior Assumptions (such As Mistake-bound Models, Universal Prediction, And Agnostic Learning), And The Study Of Model Selection Techniques. We Hope That These Conferences Stimulate An Interdisciplinary Scienti C Interaction That Will Be Fruitful In All Represented Elds. Thirty- Ve Papers Were Submitted To The Program Committee For Conside- Tion, And Twenty-one Of These Were Accepted For Presentation At The Conference And Publication In These Proceedings. In Addition, Robert Schapire (at & T Labs), And Richard Sutton (at & T Labs) Were Invited To Give Lectures And Contribute A Written Version To These Proceedings. There Were A Number Of Other Joint Events Including A Banquet And An Excursion To Munster ̈ . The Ifip Wg 1.4 Scholarship Was Awarded To Andra S Antos For His Paper \lower Bounds On The Rate Of Convergence Of Nonparametric Pattern Recognition. Invited Lectures -- Theoretical Views Of Boosting -- Open Theoretical Questions In Reinforcement Learning -- Learning From Random Examples -- A Geometric Approach To Leveraging Weak Learners -- Query By Committee, Linear Separation And Random Walks -- Hardness Results For Neural Network Approximation Problems -- Learning From Queries And Counterexamples -- Learnability Of Quantified Formulas -- Learning Multiplicity Automata From Smallest Counterexamples -- Exact Learning When Irrelevant Variables Abound -- An Application Of Codes To Attribute-efficient Learning -- Learning Range Restricted Horn Expressions -- Reinforcement Learning -- On The Asymptotic Behavior Of A Constant Stepsize Temporal-difference Learning Algorithm -- On-line Learning And Expert Advice -- Direct And Indirect Algorithms For On-line Learning Of Disjunctions -- Averaging Expert Predictions -- Teaching And Learning -- On Teaching And Learning Intersection-closed Concept Classes -- Inductive Inference -- Avoiding Coding Tricks By Hyperrobust Learning -- Mind Change Complexity Of Learning Logic Programs -- Statistical Theory Of Learning And Pattern Recognition -- Regularized Principal Manifolds -- Distribution-dependent Vapnik-chervonenkis Bounds -- Lower Bounds On The Rate Of Convergence Of Nonparametric Pattern Recognition -- On Error Estimation For The Partitioning Classification Rule -- Margin Distribution Bounds On Generalization -- Generalization Performance Of Classifiers In Terms Of Observed Covering Numbers -- Entropy Numbers, Operators And Support Vector Kernels. Paul Fischer, Hans Ulrich Simon (eds.). Includes Bibliographical References And Index. This text presents the proceedings of the 4th European Conference on Computational Learning Theory. The 23 contributions address topics such as learning from queries and counter examples, reinforcement learning, online learning and export advice, teaching and learning and inductive inference.