ALT 10 Logo

This volume contains the papers presented at the 21st International Conference on Algorithmic Learning Theory (ALT 2010), which was held in Canberra, Australia, October 6-8, 2010. The conference was co-located with the 13th International Conference on Discovery Science (DS 2010) and with the Machine Learning Summer School, which was held just before ALT 2010. The technical program of ALT 2010 contained 26 papers selected from 44 submissions, and 5 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 theoretical background and scientific 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, active learning, statistical learning, support vector machines, Vapnik-Chervonenkis dimension, probably approximately correct learning, Bayesian and causal networks, boosting and bagging, information-based methods, minimum description length, Kolmogorov complexity, kernels, graph learning, decision tree methods, Markov decision processes, reinforcement learning, and real-world applications of algorithmic learning theory.

DS 2010 was the 13th International Conference on Discovery Science and focuses on the development and analysis of methods for intelligent data analysis, knowledge discovery and machine learning, as well as their application to scientific knowledge discovery. As is the tradition, it was co-located and held in parallel with Algorithmic Learning Theory.

In addition to these two conferences, the Machine Learning Summer School taught fundamental knowledge and recent results to PhD students and other interested researchers.

The present volume contains the texts of the 26 papers presented at ALT 2010, divided into groups 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 kernel methods. The volume also contains the texts or abstracts of the invited talks:

Papers presented at DS 2010 are contained in the DS 2010 proceedings.

Since 1999, ALT has been awarding the E. M. Gold Award for the most outstanding student contribution. This year, the award was given to Gábor Bartók for his paper ``Toward a Classification of Finite Partial-Monitoring Games'', co-authored by Dávid Pál and Csaba Szepesvári.

ALT 2010 was the 21st in the ALT conference series, established in Japan in 1990. A second root is the conference series Analogical and Inductive Inference previously held in 1986, 1989, 1992 which merged with the conference series ALT after a co-location in the year 1994. From then on, ALT became an international conference series which kept its strong links to Japan but also was regularly held at overseas destinations including Australia, Germany, Hungary, Italy, Portugal, Singapore, Spain and the USA.

The ALT series is supervised by its Steering Committee: Naoki Abe (IBM Thomas J. Watson Research Center, Yorktown, USA), Shai Ben-David (University of Waterloo, Canada), Philip M. Long (Google, Mountain View, USA), Akira Maruoka (Ishinomaki Senshu University, Japan), Takeshi Shinohara (Kyushu Institute of Technology, Iizuka, Japan), Frank Stephan (National University of Singapore, Republic of Singapore), Einoshin Suzuki (Kyushu University, Fukuoka, Japan), Eiji Takimoto (Kyushu University, Fukuoka, Japan), György Turán (University of Illinois at Chicago, USA and University of Szeged, Hungary), Osamu Watanabe (Tokyo Institute of Technology, Japan), Thomas Zeugmann (Chair, Hokkaido University, Japan), and Sandra Zilles (Publicity Chair, University of Regina, Saskatchewan, Canada).

We would like to thank the many people and institutions who contributed to the success of the conference. In particular, we want to thank our authors for contributing to the conference and for coming to Canberra in October 2010. Without their efforts and their willingness to choose ALT 2010 as a forum to report on their research, this conference would not have been possible.

We would like to thank the National ICT Australia for generously sponsoring the conference ALT 2010; NICTA is an Australian research institute dedicated to information and communications technology, and its founding members are the University of New South Wales, the Australian National University, the NSW Government and the ACT Government; later The University of Sydney, the Victorian Government, the University of Melbourne, the Queensland Government, the University of Queensland, the Griffith University and the Queensland University of Technologies became partners. We are furthermore grateful to the Australian National University (ANU) for hosting the event; ANU is a leading public teaching and research university in Canberra, Australia. The support of ANU and NICTA was a great help, organisationally and financially, for the conferences ALT 2010 and DS 2010. We are also grateful that we could use the excellent conference management system EasyChair for putting together the programme for ALT 2010; EasyChair was developed mainly by Andrei Voronkov and is hosted at the University of Manchester. The system is cost-free.

As already mentioned the conference series ALT has in this year, as in many previous years, been co-located with the series Discovery Science. We are grateful for this continuous collaboration. In particular, we would like to thank the Conference Chair Achim Hoffmann and the Programme Committee chairs Geoffrey Holmes and Bernhard Pfahringer of Discovery Science 2010.

We would like to thank Mark Reid for organising the conference and the tremendous amount of work he has dedicated to making ALT 2010 a success. We want to extend our thanks to the other members of the local organisation committee, who were there to organise the reception, to sit at the information desk and to do the other duties which are connected to organising and hosting a conference.

We are grateful to the members of the Programme Committee for ALT 2010 and the subreferees for their hard work to select a good programme for ALT 2010. Reviewing papers and checking the correctness of results is demanding in time and skills and we very much appreciate this contribution to the conference. Last but not least we thank Springer for their support in preparing and publishing this volume of the Lecture Notes in Artificial Intelligence series.

July 2010   Marcus Hutter
  Frank Stephan
  Vladimir Vovk
  Thomas Zeugmann


Conference Chair

Marcus Hutter Australian National University
and National ICT Australia

Program Committee

Local Arrangements

Mark Reid Australian National University


Nir AilonTetsuhiro Miyahara
Nicolas BaskiotisNovi Quadrianto
Avrim BlumAfshin Rostamizadeh
Sébastien BubeckCynthia Rudin
Joseph DefretinHiroshi Sakamoto
Nicolás Della PennaRavi Sastry
Christos DimitrakakisRocco Servedio
Mohammad GhavamzadehJinwoo Shin
Daniel GolovinKilho Shin
Steve HannekeGilles Stoltz
Eiju HirowatariMahito Sugiyama
Yuri KalnishkanPeter Sunehag
Varun KanadeAmeet Talwalkar
Anna KasprzikFranck Thollard
Alessandro LazaricRyota Tomioka
Odalric-Ambrym MaillardFedor Zhdanov
Daniel Meister

Sponsoring Institutions

National ICT Australia

Australian National University

©Copyright Notice:
The document of this page is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provision of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under German Copyright Law.

uparrowback to the ALT 2010 Proceedings Page

uparrowuparrow back to the ALT Archives

Valid HTML 4.0