ALT 09 Logo

This volume contains the papers presented at the 20th International Conference on Algorithmic Learning Theory (ALT 2009), which was held in Porto, Portugal, October 3-5, 2009. The conference was co-located with the 12th International Conference on Discovery Science (DS 2009). The technical program of ALT 2009 contained 26 papers selected from 60 submissions, and 5 invited talks. The invited talks were presented during the joint sessions of both conferences.

ALT 2009 was the 20th in the ALT conference series, established in Japan in 1990. The series Analogical and Inductive Inference is a predecessor of this series: it was held in 1986, 1989 and 1992, co-located with ALT in 1994, and subsequently merged with ALT. ALT maintains its strong connections to Japan, but has also been held in other countries, such as Australia, Germany, Hungary, Italy, 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), Phil Long (Google, Mountain View, USA), Gábor Lugosi (Pompeu Fabra University, Barcelona, Spain), 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, Canada). The ALT web pages have been set up (together with Frank Balbach and Jan Poland) and are maintained by Thomas Zeugmann.

The present volume contains the texts of the 26 papers presented at ALT 2009, divided into groups of papers on online learning, learning graphs, active learning and query learning, statistical learning, inductive inference, and semi-supervised and unsupervised learning. The volume also contains abstracts of the invited talks:

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

The E. Mark Gold Award has been presented annually at the ALT conferences since 1999, for the most outstanding student contribution. This year, the award was given to Hanna Mazzawi for the paper Reconstructing Weighted Graphs with Minimal Query Complexity, co-authored by Nader Bshouty.

We would like to thank the many people and institutions who contributed to the success of the conference. Thanks to the authors of the papers for their submissions, and to the invited speakers for presenting exciting overviews of important recent research developments. We are very grateful to the sponsors of the conference for their generous financial support: University of Porto, Artificial Intelligence and Decision Support Laboratory, Center for Research in Advanced Computing Systems, Portuguese Science and Technology Foundation, Portuguese Artificial Intelligence Association, SAS, Alberta Ingenuity Centre for Machine Learning, and Division of Computer Science, Hokkaido University.

We are grateful to the members of the Program Committee for ALT 2009. Their hard work in reviewing and discussing the papers made sure that we had an interesting and strong program. We also thank the subreferees assisting the Program Committee. Special thanks go to the local arrangement chair João Gama (University of Porto). We would like to thank the Discovery Science conference for its ongoing collaboration with ALT, which makes it possible to provide a well-rounded picture of the current theoretical and practical advances in machine learning and the related areas. In particular, we are grateful to the conference chair João Gama (University of Porto) and Program Committee chairs Vãtor Santos Costa (University of Porto) and Alãpio Jorge (University of Porto) for their cooperation. Last but not least, we thank Springer for their support in preparing and publishing this volume of the Lecture Notes in Artificial Intelligence series.

August 2009   Ricard Gavaldà
  Gábor Lugosi
  Thomas Zeugmann
  Sandra Zilles


Conference Chair

Ricard Gavaldà Universitat Politècnica de Catalunya, Barcelona

Program Committee

Local Arrangements

João Gama University of Porto, Portugal


Jacob AbernethySteffen Lange
Andreas ArgyriouAlex Leung
Marta AriasGuy Lever
John CaseTyler Lu
Nicolò Cesa-BianchiEric Martin
Alexey ChernovMario Martin
Jiang ChenSamuel Moelius III
Alexander ClarkRémi Munos
Sanjoy DasguptaFrancesco Orabona
Tom DietheRonald Ortner
Ran El-YanivDávid Pál
Tim van ErvenJoel Ratsaby
Steve HannekeNicola Rebagliati
Kohei HatanoLev Reyzin
Tamir HazanSivan Sabato
Colin de la HigueraOhad Shamir
Jeffrey JacksonRobert Sloan
Sanjay JainJun'ichi Takeuchi
Sham KakadeChristino Tamon
Jyrki KivinenGyörgy Turán
Wouter KoolenVladimir Vovk
Timo KötzingYiming Ying
Lucy KunchevaThomas Zeugmann

Sponsoring Institutions

University of Porto
Artificial Intelligence and Decision Support Laboratory
Center for Research in Advanced Computing Systems
Portuguese Science and Technology Foundation
Portuguese Artificial Intelligence Association
Alberta Ingenuity Centre for Machine Learning
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 2009 Proceedings Page

uparrowuparrow back to the ALT Archives

Valid HTML 4.0