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

This book constitutes the refereed proceedings of the 4th European Conference on Computational Learning Theory, EuroCOLT'99, held in Nordkirchen, Germany in March 1999. The 21 revised full papers presented were selected from a total of 35 submissions; also included are two invited contributions. The book is divided in topical sections on learning from queries and counterexamples, reinforcement learning, online learning and export advice, teaching and learning, inductive inference, and statistical theory of learning and pattern recognition. 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. Theoretical Views of Boosting....Pages 1-10 Open Theoretical Questions in Reinforcement Learning....Pages 11-17 A Geometric Approach to Leveraging Weak Learners....Pages 18-33 Query by Committee, Linear Separation and Random Walks....Pages 34-49 Hardness Results for Neural Network Approximation Problems....Pages 50-62 Learnability of Quantified Formulas....Pages 63-78 Learning Multiplicity Automata from Smallest Counterexamples....Pages 79-90 Exact Learning when Irrelevant Variables Abound....Pages 91-100 An Application of Codes to Attribute-Efficient Learning....Pages 101-110 Learning Range Restricted Horn Expressions....Pages 111-125 On the Asymptotic Behavior of a Constant Stepsize Temporal-Difference Learning Algorithm....Pages 126-137 Direct and Indirect Algorithms for On-line Learning of Disjunctions....Pages 138-152 Averaging Expert Predictions....Pages 153-167 On Teaching and Learning Intersection-Closed Concept Classes....Pages 168-182 Avoiding Coding Tricks by Hyperrobust Learning....Pages 183-197 Mind Change Complexity of Learning Logic Programs....Pages 198-213 Regularized Principal Manifolds....Pages 214-229 Distribution-Dependent Vapnik-Chervonenkis Bounds....Pages 230-240 Lower Bounds on the Rate of Convergence of Nonparametric Pattern Recognition....Pages 241-252 On Error Estimation for the Partitioning Classification Rule....Pages 253-262 Margin Distribution Bounds on Generalization....Pages 263-273 Generalization Performance of Classifiers in Terms of Observed Covering Numbers....Pages 274-285 Entropy Numbers, Operators and Support Vector Kernels....Pages 285-299 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.