Preface

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:

• Alexander Clark (Royal Holloway, University of London, United Kingdom), ``Towards General Algorithms for Grammatical Inference'' (invited speaker for ALT 2010)
• Manfred K. Warmuth (University of California Santa Cruz, USA), ``The Blessing and the Curse of the Multiplicative Updates'' (invited speaker for ALT 2010)
• Ivan Bratko (University of Ljubljana, Slovenia), ``Discovery of Abstract Concepts by a Robot'' (invited speaker for DS 2010)
• Kotagiri Ramamohanarao (University of Melbourne, Australia), ``Contrast Pattern Mining and its Application for Building Robust Classifiers'' (invited speaker for DS 2010)
• Peter L. Bartlett (University of California Berkeley, USA), Optimal Online Prediction in Adversarial Environments'' (joint invited speaker for ALT 2010 and DS 2010).

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.

Conference Chair

Program Committee

Local Arrangements

Subreferees

Sponsoring Institutions

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.