Lecture Notes in Artificial Intelligence 2225 SubseriesofLectureNotesinComputerScience EditedbyJ.G.CarbonellandJ.Siekmann Lecture Notes in Computer Science EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Tokyo Naoki Abe Roni Khardon Thomas Zeugmann (Eds.) Algorithmic Learning Theory 12th International Conference,ALT 2001 Washington, DC, USA, November 25-28, 2001 Proceedings 1 3 SeriesEditors JaimeG.Carbonell,CarnegieMellonUniversity,Pittsburgh,PA,USA Jo¨rgSiekmann,UniversityofSaarland,Saarbru¨cken,Germany VolumeEditors NaokiAbe IBM,ThomasJ.WatsonResearchCenter,Room33-237 P.O.Box218,Yorktown,NY10598,USA E-mail:[email protected] RoniKhardon TuftsUniversity,Dept.ofElectricalEngineeringandComputerScience 161CollegeAve.,Medford,MA02155,USA E-mail:[email protected] ThomasZeugmann MedizinischeUniversita¨tzuLu¨beck,Inst.fürTheoretischeInformatik Wallstr.40,23560Lu¨beck,Germany E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Algorithmiclearningtheory:12thinternationalconference;proceedings/ ALT2001,Washington,DC,USA,November25-28,2001.NaokiAbe...(ed.). Berlin;Heidelberg;NewYork;Barcelona;HongKong;London;Milan; Paris;Tokyo:Springer,2001 (Lecturenotesincomputerscience;Vol.2225:Lecturenotesin artificialintelligence) ISBN3-540-42875-5 CRSubjectClassification(1998):I.2.6,I.2.3,F.1,F.2,F.4.1,I.7 ISBN3-540-42875-5Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork amemberofBertelsmannSpringerScience+BusinessMediaGmbH http://www.springer.de ©Springer-VerlagBerlinHeidelberg2001 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTPBerlin,StefanSossna Printedonacid-freepaper SPIN10840965 06/3142 543210 Preface This volume contains the papers presented at the 12th Annual Conference on Algorithmic Learning Theory (ALT 2001), which was held in Washington DC, USA, during November 25–28, 2001. The main objective of the conference is to provide an inter-disciplinary forum for the discussion of theoretical foundations of machine learning, as well as their relevance to practical applications. The conferencewasco-locatedwiththeFourthInternationalConferenceonDiscovery Science (DS 2001). The volume includes 21 contributed papers. These papers were selected by the program committee from 42 submissions based on clarity, significance, ori- ginality, and relevance to theory and practice of machine learning. Additionally, the volume contains the invited talks of ALT 2001 presented by Dana Angluin of Yale University, USA, Paul R. Cohen of the University of MassachusettsatAmherst,USA,andthejointinvitedtalkforALT2001andDS 2001 presented by Setsuo Arikawa of Kyushu University, Japan. Furthermore, this volume includes abstracts of the invited talks for DS 2001 presented by Lindley Darden and Ben Shneiderman both of the University of Maryland at College Park, USA. The complete versions of these papers are published in the DS 2001 proceedings (Lecture Notes in Artificial Intelligence Vol. 2226). ALT has been awarding the E Mark Gold Award for the most outstanding paper by a student author since 1999. This year the award was given to Ke Yangforhispaper“OnLearningCorrelatedBooleanFunctionsUsingStatistical Queries.” This conference was the 12th in a series of annual conferences established in 1990.ContinuationoftheALTseriesissupervisedbyitssteeringcommitteecon- sistingofNaokiAbe(IBMThomasJ.WatsonResearchCenter,Yorktown,USA), Peter Bartlett (Australian National Univ.), Klaus P. Jantke (DFKI, Germany), RoniKhardon(TuftsUniversity,USA),PhilLong(NationalUniv.ofSingapore), Heikki Mannila (Nokia Research Center, USA), Akira Maruoka (Tohoku Univ., Sendai, Japan), Luc De Raedt (Albert-Ludwigs-Univ., Freiburg, Germany), Ta- keshi Shinohara (Kyushu Inst. of Technology, Japan), Osamu Watanabe (Tokyo Inst. of Technology, Japan), Arun Sharma (co-chair, Univ. of New South Wales, Australia), and Thomas Zeugmann (chair, Med. Univ. of Lu¨beck, Germany). We would like to thank all individuals and institutions who contributed to the success of the conference: the authors for submitting papers, the invited speakers for accepting our invitation and lending us their insight into recent developments in their research areas, the sponsors, and Springer-Verlag. We are particularly grateful to the program committee for their work in reviewing papers and participating in on-line discussions. We are also grateful to the external referees whose reviews made a considerable contribution to this process. The program committee consisted of: VI Preface Hiroki Arimura (Kyushu Univ., Japan) Javed Aslam (Dartmouth College, USA) Peter Bartlett (Barnhill Technologies, Australia) Anselm Blumer (Tufts Univ., USA) Carlos Domingo (Synera Systems, Spain) Colin de la Higuera (Univ. St. Etienne, France) Steffen Lange (DFKI, Saarbru¨cken, Germany) Phil Long (National Univ., Singapore) Eric Martin (UNSW, Australia) Atsuyoshi Nakamura (NEC Labs., Japan) Vijay Raghavan (Vanderbilt Univ., USA) Dan Roth (UIUC, USA) John Shawe-Taylor (Univ. of London, UK) Eiji Takimoto (Tohoku Univ., Japan) Christino Tamon (Clarkson Univ., USA) WearegratefultoDS2001chairsMasahikoSato(KyotoUniv.,Japan),Klaus P. Jantke (DFKI, Germany), and Ayumi Shinohara (Kyushu Univ., Japan) for their effort in coordinating with ALT 2001 and to Carl Smith of the University of Maryland at College Park for his work as the local arrangements chair for both conferences. Finally, we would like to thank the National Science Foundation, the Office of Naval Research, Agilent Technologies, Avaya Labs, and the University of Maryland for their generous financial support for the conference. September 2001 Naoki Abe Roni Khardon Thomas Zeugmann Preface VII Additional Reviewers Kazuyuki Amano Hugh Mallinson Jose Luis Balc´azar Hiroshi Mamitsuka Asa Ben-Hur Ron Meir Avrim Blum Tatsuya Motoki Samir Chopra Yasuhito Mukouchi Nello Cristianini Jochen Nessel Philippe Ezequel Kazuhiko Ohno Paul Fischer Jos´e Oncina Ashutosh Garg Krishnan Pillaipakkamnatt Ricard Gavalda Lenny Pitt Gunter Grieser Vasin Punyakanok Peter Grunwald Yoshifumi Sakai David Guijarro Arun Sharma Ralf Herbrich Frank Stephan Joerg Herrmann Noriko Sugimoto Kouichi Hirata Ichiro Tajika Michael Houle Atsuhiro Takasu Don Hush Jun-ichi Takeuchi Jeff Jackson Paul Vitanyi Jean-Christophe Janodet Volodya Vovk Jaz Kandola Chris Watkins Christopher Kermorvant Dawn Wilkins Efim Kinber Bob Williamson John Langford Dav Zimak Table of Contents Editors’ Introduction ............................................... 1 N. Abe, R. Khardon, T. Zeugmann Invited Papers The Discovery Science Project in Japan............................... 9 S. Arikawa Queries Revisited .................................................. 12 D. Angluin Robot Baby 2001 .................................................. 32 P.R. Cohen, T. Oates, N. Adams, C.R. Beal Discovering Mechanisms: A Computational Philosophy of Science Perspective........................................................ 57 L. Darden Inventing Discovery Tools: Combining Information Visualization with Data Mining.................................................. 58 B. Shneiderman Complexity of Learning On Learning Correlated Boolean Functions Using Statistical Queries ........................................................... 59 K. Yang A Simpler Analysis of the Multi-way Branching Decision Tree Boosting Algorithm ................................................ 77 K. Hatano Minimizing the Quadratic Training Error of a Sigmoid Neuron Is Hard ... 92 J. Sˇ´ıma Support Vector Machines Learning of Boolean Functions Using Support Vector Machines .......... 106 K. Sadohara A Random Sampling Technique for Training Support Vector Machines (For Primal-Form Maximal-Margin Classifiers) ......... 119 J. Balca´zar, Y. Dai, O. Watanabe X Table of Contents New Learning Models Learning Coherent Concepts......................................... 135 A. Garg, D. Roth Learning Intermediate Concepts ..................................... 151 S.S. Kwek Real-Valued Multiple-Instance Learning with Queries................... 167 D.R. Dooly, S.A. Goldman, S.S. Kwek Online Learning Loss Functions, Complexities, and the Legendre Transformation ......... 181 Y. Kalnishkan, M.V. Vyugin, V. Vovk Non-linear Inequalities between Predictive and Kolmogorov Complexities ...................................................... 190 M.V. Vyugin, V.V. V’yugin Inductive Inference Learning by Switching Type of Information ........................... 205 S. Jain, F. Stephan Learning How to Separate........................................... 219 S. Jain, F. Stephan Learning Languages in a Union ...................................... 235 S. Jain, Y.K. Ng, T.S. Tay On the Comparison of Inductive Inference Criteria for Uniform Learning of Finite Classes ................................................... 251 S. Zilles Refutable Inductive Inference Refutable Language Learning with a Neighbor System .................. 267 Y. Mukouchi, M. Sato Learning Recursive Functions Refutably .............................. 283 S. Jain, E. Kinber, R. Wiehagen, T. Zeugmann Refuting Learning Revisited......................................... 299 W. Merkle, F. Stephan Learning Structures and Languages Efficient Learning of Semi-structured Data from Queries ................ 315 H. Arimura, H. Sakamoto, S. Arikawa