ALT 06 Logo

This volume contains the papers presented at the 17th Annual International Conference on Algorithmic Learning Theory (ALT 2006) which was held in Barcelona (Catalunya, Spain),
7 - 10 October 2006. The conference was organized with support of the PASCAL Network within the framework of PASCAL Dialogues 2006, which comprised three conferences:

Learning 2006 provided a forum for interdisciplinary study and discussion of the different aspects of learning and took place 2 - 5 October 2006 in the campus of Vilanova i La Geltrú.

ALT 2006 is dedicated to the theoretical foundations of machine learning and took place in the rooms of the Institute of Catalan Studies in Barcelona. ALT provides a forum of high quality talks with a strong theoretical background and scientific interchange in areas like query models, on-line learning, inductive inference, algorithmic forecasting, boosting, support vector machines, kernel methods, reinforcement learning and statistical learning models.

DS 2006 is the 9th 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 already tradition, it was collocated and held in parallel with Algorithmic Learning Theory.

In addition to these three conferences, the European Workshop on Curricular Issues in Learning Theory initiated as the first regular meeting the Curriculum Development Programme of the PASCAL Network taking place on 11 October 2006.

The volume includes 24 contributions which the programme committee selected out of 53 submissions. It also contains descriptions of the 5 invited talks of ALT and DS; longer versions of the DS papers are available in the proceedings of DS 2006. These invited talks were presented to the audience of both conferences in joint sessions.

Since 1999, ALT has been awarding the E. M. Gold Award for the most outstanding contribution by a student. This year the award was given to Alp Atıcı for his paper “Learning unions of ω(1)-dimensional rectangles”, co-authored by Rocco A. Servedio. We would like to thank Google for sponsoring the E. M. Gold Award.

Algorithmic Learning Theory 2006 is the 17th in a series of annual conferences 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 collocation 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, Italy, Singapore, Spain and the United States of America.

Continuation of ALT 2006 is supervised by its steering committee consisting of Naoki Abe (IBM Thomas J. Watson Research Center, Yorktown, USA), Shai Ben-David (University of Waterloo, Canada), Roni Khardon (Tufts University, Medford, USA), Steffen Lange (FH Darmstadt, Germany), Philip M. Long (Google, Mountain View, USA), Hiroshi Motoda (Osaka University, Japan), Akira Maruoka (Tohoku University, Sendai, Japan), Takeshi Shinohara (Kyushu Institute of Technology, Iizuka, Japan), Osamu Watanabe (Tokyo Institute of Technology, Japan), Arun Sharma (Queensland University of Technology, Brisbane, Australia - Co-Chair), Frank Stephan (National University of Singapore, Republic of Singapore) and Thomas Zeugmann (Hokkaido University, Japan - Chair).

We would in particular like to thank Thomas Zeugmann for his continuous support of the ALT conference series and in particular for running the ALT webpage and the ALT submission system which he programmed together with Frank Balbach and Jan Poland. Thomas Zeugmann assisted us in many questions with respect to running the conference and to preparing the proceedings.

The conference ALT 2006 was made possible by the financial and administrative support of the PASCAL network, which organised this meeting together with others in the framework of PASCAL Dialogues 2006. Furthermore, we acknowledge the support of Google by financing the E. M. Gold Award (the corresponding award at Discovery Science 2006 was sponsored by Yahoo). We are grateful for the dedication of the host, the Universitat Politècnica de Catalunya (UPC), who organised the conference with much dedication and contributed to ALT in many ways. We want to express our gratitudes to the Local Arrangement Chair Ricard Gavaldá and all other colleagues from the UPC, UPF and UB, who have put so much time into making ALT 2006 to become a success. Here we want also acknowledge the local sponsor Idescat, Statistical Institute of Catalonia. Furthermore, the Institute for Theoretical Computer Science of the University of Lübeck as well as the Division of Computer Science, Hokkaido University, Sapporo, supported ALT 2006.

The conference series ALT has in this year as in many previous years been collocated with the series Discovery Science. We are greatful for this continuous collaboration and would like in particular to thank the conference chair Klaus P. Jantke and the programme committee chairs Nada Lavrač and Ljupčo Todorovski of Discovery Science 2006.

We also want to thank the programme committee and the subreferees (both listed on the next pages) for their hard work to select a good programme for ALT 2006. Reviewing papers and checking the correctness of results is demanding in time and skills and we very much appreciated this contribution to the conference.

Last but not least we want also thank the authors for choosing ALT 2006 as a forum to report on their research.

August 2006 José L. Balcázar
Philip M. Long
Frank Stephan

Conference Chair

José L. Balcázar Universitat Politècnica de Catalunya, Barcelona, Spain

Program Committee

Local Arrangements

Ricard Gavaldà Universitat Politècnica de Catalunya, Barcelona, Spain


Hiroki Arimura Sayan Mukherjee
Amos Beimel Thomas Nichols
Jochen Blath Jan Poland
Francisco Casacuberta Michael Richter
Alexey Chernov Sebastien Roch
Alexander Clark Joseph Romano
Frank Drewes Daniel Reidenbach
Vitaly Feldman Cynthia Rudin
Dmitry Gavinsky Daniil Ryabko
Robert Glaubius Hiroshi Sakamoto
Gunter Grieser Rocco Servedio
Colin de la Higuera Takeshi Shinohara
Hiroki Ishizaka William D. Smart
Yuri Kalnishkan Yasuhiro Tajima
Roni Khardon Eiji Takimoto
Adam Klivans Franck Thollard
Shigenobu Kobayashi Vladimir Vovk
Shane Legg Mitsuo Wakatsuki
Hanna Mazzawi Osamu Watanabe
Tetsuhiro Miyahara

Sponsoring Institutions

Spanish Ministry of Science


Pascal Network of Excellence

PASCAL Dialogues 2006

Universitat Politècnica de Calalunya

Idescat, Statistical Institute of Catalonia

Institut für Theoretische Informatik, Universität Lübeck

Division of Computer Science, Hokkaido 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 2006 Proceedings Page

uparrowuparrow back to the ALT Archives

Valid HTML 4.0