Algorithmic Learning Theory

1. Front Matter

   PDF

2. Editors’ Introduction

   1. Editors’ Introduction

      • Marcus Hutter, Frank Stephan, Vladimir Vovk, Thomas Zeugmann

      Pages 1-10

3. Invited Papers

   1. Towards General Algorithms for Grammatical Inference

      • Alexander Clark

      Pages 11-30

   2. The Blessing and the Curse of the Multiplicative Updates

      • Manfred K. Warmuth

      Pages 31-31

   3. Discovery of Abstract Concepts by a Robot

      • Ivan Bratko

      Pages 32-32

   4. Contrast Pattern Mining and Its Application for Building Robust Classifiers

      • Kotagiri Ramamohanarao

      Pages 33-33

   5. Optimal Online Prediction in Adversarial Environments

      • Peter L. Bartlett

      Pages 34-34

4. Regular Contributions

   1. Statistical Learning

      1. An Algorithm for Iterative Selection of Blocks of Features

         • Pierre Alquier

         Pages 35-49

      2. Bayesian Active Learning Using Arbitrary Binary Valued Queries

         • Liu Yang, Steve Hanneke, Jaime Carbonell

         Pages 50-58

      3. Approximation Stability and Boosting

         • Wei Gao, Zhi-Hua Zhou

         Pages 59-73

   2. Grammatical Inference and Graph Learning

      1. A Spectral Approach for Probabilistic Grammatical Inference on Trees

         • Raphaël Bailly, Amaury Habrard, François Denis

         Pages 74-88

      2. PageRank Optimization in Polynomial Time by Stochastic Shortest Path Reformulation

         • Balázs Csanád Csáji, Raphaël M. Jungers, Vincent D. Blondel

         Pages 89-103

      3. Inferring Social Networks from Outbreaks

         • Dana Angluin, James Aspnes, Lev Reyzin

         Pages 104-118

   3. Probably Approximately Correct Learning

      1. Distribution-Dependent PAC-Bayes Priors

         • Guy Lever, François Laviolette, John Shawe-Taylor

         Pages 119-133

      2. PAC Learnability of a Concept Class under Non-atomic Measures: A Problem by Vidyasagar

         • Vladimir Pestov

         Pages 134-147

      3. A PAC-Bayes Bound for Tailored Density Estimation

         • Matthew Higgs, John Shawe-Taylor

         Pages 148-162

      4. Compressed Learning with Regular Concept

         • Jiawei Lv, Jianwen Zhang, Fei Wang, Zheng Wang, Changshui Zhang

         Pages 163-178

   4. Query Learning and Algorithmic Teaching

      1. A Lower Bound for Learning Distributions Generated by Probabilistic Automata

         • Borja Balle, Jorge Castro, Ricard Gavaldà

         Pages 179-193

      2. Lower Bounds on Learning Random Structures with Statistical Queries

         • Dana Angluin, David Eisenstat, Leonid (Aryeh) Kontorovich, Lev Reyzin

         Pages 194-208

      3. Recursive Teaching Dimension, Learning Complexity, and Maximum Classes

         • Thorsten Doliwa, Hans Ulrich Simon, Sandra Zilles

         Pages 209-223

This volume contains the papers presented at the 21st International Conf- ence on Algorithmic Learning Theory (ALT 2010), which was held in Canberra, Australia, October 6–8, 2010. The conference was co-located with the 13th - ternational Conference on Discovery Science (DS 2010) and with the Machine Learning Summer School, which was held just before ALT 2010. The tech- cal program of ALT 2010, contained 26 papers selected from 44 submissions and ?ve invited talks. The invited talks were presented in joint sessions of both conferences. ALT 2010 was dedicated to the theoretical foundations of machine learning and took place on the campus of the Australian National University, Canberra, Australia. ALT provides a forum for high-quality talks with a strong theore- cal background and scienti?c interchange in areas such as inductive inference, universal prediction, teaching models, grammatical inference, formal languages, inductive logic programming, query learning, complexity of learning, on-line learning and relative loss bounds, semi-supervised and unsupervised learning, clustering,activelearning,statisticallearning,supportvectormachines,Vapnik- Chervonenkisdimension,probablyapproximatelycorrectlearning,Bayesianand causal networks, boosting and bagging, information-based methods, minimum descriptionlength,Kolmogorovcomplexity,kernels,graphlearning,decisiontree methods, Markov decision processes, reinforcement learning, and real-world - plications of algorithmic learning theory. DS 2010 was the 13th International Conference on Discovery Science and focused on the development and analysis of methods for intelligent data an- ysis, knowledge discovery and machine learning, as well as their application to scienti?c knowledge discovery. As is the tradition, it wasco-located and held in parallel with Algorithmic Learning Theory.

• algorithmic learning theory
• algorithms
• classification
• complexity
• complexity theory
• decision trees
• grammtical inference
• inductive inference
• kolmogorov complexity
• logic programming
• query learning
• statistical learn
• support vector machines
• teaching models
• unsupervised learning
• algorithm analysis and problem complexity

• Research School of Information Sciences and Engineering, Australian National University and NICTA, Canberra, Australia

  Marcus Hutter

• Department of Mathematics, National University of Singapore, Singapore, Republic of Singapore

  Frank Stephan

• Department of Computer Science, University of London, Royal Holloway, Egham, Surrey, UK

  Vladimir Vovk

• Division of Computer Science, Hokkaido University, , ,, Japan

  Thomas Zeugmann

Policies and ethics