Algorithmic Learning Theory

by Hutter, Marcus; Stephan, Frank; Vovk, Vladimir; Zeugmann, Thomas

• ISBN13: 9783642161070
• ISBN10: 3642161073
• Format: Paperback
• Copyright: 2010-10-13
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 21th International Conference on Algorithmic Learning Theory, ALT 2010, held in Canberra, Australia, in October 2010, co-located with the 13th International Conference on Discovery Science, DS 2010. The 26 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from 44 submissions. The papers are divided into topical sections of papers on statistical learning; grammatical inference and graph learning; probably approximately correct learning; query learning and algorithmic teaching; on-line learning; inductive inference; reinforcement learning; and on-line learning and kernel methods.

Table of Contents

Editors' Introduction	p. 1
Invited Papers
Towards General Algorithms for Grammatical Inference	p. 11
The Blessing and the Curse of the Multiplicative Updates (Abstract)	p. 31
Discovery of Abstract Concepts by a Robot (Abstract)	p. 32
Contrast Pattern Mining and Its Application for Building Robust Classifiers (Abstract)	p. 33
Optimal Online Prediction in Adversarial Environments	p. 34
Regular Contributions
Statistical Learning
An Algorithm for Iterative Selection of Blocks of Features	p. 35
Bayesian Active Learning Using Arbitrary Binary Valued Queries	p. 50
Approximation Stability and Boosting	p. 59
Grammatical Inference and Graph Learning
A Spectral Approach for Probabilistic Grammatical Inference on Trees	p. 74
PageRank Optimization in Polynomial Time by Stochastic Shortest Path Reformulation	p. 89
Inferring Social Networks from Outbreaks	p. 104
Probably Approximately Correct Learning
Distribution-Dependent PAC-Bayes Priors	p. 119
PAC Learnability of a Concept Class under Non-atomic Measures: A Problem by Vidyasagar	p. 134
A PAC-Bayes Bound for Tailored Density Estimation	p. 148
Compressed Learning with Regular Concept	p. 163
Query Learning and Algorithmic Teaching
A Lower Bound for Learning Distributions Generated by Probabilistic Automata	p. 179
Lower Bounds on Learning Random Structures with Statistical Queries	p. 194
Recursive Teaching Dimension, Learning Complexity, and Maximum Classes	p. 209
On-line Learning
Toward a Classification of Finite Partial-Monitoring Games	p. 224
Switching Investments	p. 239
Prediction with Expert Advice under Discounted Loss	p. 255
A Regularization Approach to Metrical Task Systems	p. 270
Inductive Inference
Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations	p. 285
Learning without Coding	p. 300
Learning Figures with the Hausdorff Metric by Fractals	p. 315
Inductive Inference of Languages from Samplings	p. 330
Reinforcement Learning
Optimality Issues of Universal Greedy Agents with Static Priors	p. 345
Consistency of Feature Markov Processes	p. 360
Algorithms for Adversarial Bandit Problems with Multiple Plays	p. 375
On-line Learning and Kernel Methods
Online Multiple Kernel Learning: Algorithms and Mistake Bounds	p. 390
An Identity for Kernel Ridge Regression	p. 405
Author Index	p. 421
Table of Contents provided by Ingram. All Rights Reserved.