Algorithmic Learning Theory

1. Front Matter

   PDF

2. Invited Papers

   1. The Two Faces of Active Learning

      • Sanjoy Dasgupta

      Pages 1-1

   2. Inference and Learning in Planning

      • Hector Geffner

      Pages 2-2

   3. Mining Heterogeneous Information Networks by Exploring the Power of Links

      • Jiawei Han

      Pages 3-3

   4. Learning and Domain Adaptation

      • Yishay Mansour

      Pages 4-6

   5. Learning on the Web

      • Fernando C. N. Pereira

      Pages 7-7

3. Regular Contributions

   1. Online Learning

      1. Prediction with Expert Evaluators’ Advice

         • Alexey Chernov, Vladimir Vovk

         Pages 8-22

      2. Pure Exploration in Multi-armed Bandits Problems

         • Sébastien Bubeck, Rémi Munos, Gilles Stoltz

         Pages 23-37

      3. The Follow Perturbed Leader Algorithm Protected from Unbounded One-Step Losses

         • Vladimir V. V’yugin

         Pages 38-52

      4. Computable Bayesian Compression for Uniformly Discretizable Statistical Models

         • Łukasz Dębowski

         Pages 53-67

      5. Calibration and Internal No-Regret with Random Signals

         • Vianney Perchet

         Pages 68-82

      6. St. Petersburg Portfolio Games

         • László Györfi, Péter Kevei

         Pages 83-96

   2. Learning Graphs

      1. Reconstructing Weighted Graphs with Minimal Query Complexity

         • Nader H. Bshouty, Hanna Mazzawi

         Pages 97-109

      2. Learning Unknown Graphs

         • Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale

         Pages 110-125

      3. Completing Networks Using Observed Data

         • Tatsuya Akutsu, Takeyuki Tamura, Katsuhisa Horimoto

         Pages 126-140

   3. Active Learning and Query Learning

      1. Average-Case Active Learning with Costs

         • Andrew Guillory, Jeff Bilmes

         Pages 141-155

      2. Canonical Horn Representations and Query Learning

         • Marta Arias, José L. Balcázar

         Pages 156-170

      3. Learning Finite Automata Using Label Queries

         • Dana Angluin, Leonor Becerra-Bonache, Adrian Horia Dediu, Lev Reyzin

         Pages 171-185

      4. Characterizing Statistical Query Learning: Simplified Notions and Proofs

         • Balázs Szörényi

         Pages 186-200

      5. An Algebraic Perspective on Boolean Function Learning

         • Ricard Gavaldà, Denis Thérien

         Pages 201-215

This book constitutes the refereed proceedings of the 20th International Conference on Algorithmic Learning Theory, ALT 2009, held in Porto, Portugal, in October 2009, co-located with the 12th International Conference on Discovery Science, DS 2009. The 26 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from 60 submissions. The papers are divided into topical sections of papers on online learning, learning graphs, active learning and query learning, statistical learning, inductive inference, and semisupervised and unsupervised learning. The volume also contains abstracts of the invited talks: Sanjoy Dasgupta, The Two Faces of Active Learning; Hector Geffner, Inference and Learning in Planning; Jiawei Han, Mining Heterogeneous; Information Networks By Exploring the Power of Links, Yishay Mansour, Learning and Domain Adaptation; Fernando C.N. Pereira, Learning on the Web.

• active learning
• algorithms
• boolean function learning
• complexity
• data mining
• half-space learning
• iterative learning
• language learning
• learning
• machine learning
• query learning
• tensor clustering
• visualization

• Research Group, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya,, Barcelona, Spain

  Ricard Gavaldà

• ICREA and Department of Economics, Pompeu Fabra Universitat, Barcelona, Spain

  Gábor Lugosi

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

  Thomas Zeugmann

• Department of Computer Science, University of Regina, Regina, Canada

  Sandra Zilles

Policies and ethics