Lecture Notes in Artificial Intelligence 2111 SubseriesofLectureNotesinComputerScience EditedbyJ.G.CarbonellandJ.Siekmann Lecture Notes in Computer Science EditedbyG.Goos,J.HartmanisandJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo David Helmbold Bob Williamson (Eds.) Computational Learning Theory 14thAnnual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 Amsterdam, The Netherlands, July 16-19, 2001 Proceedings 1 3 SeriesEditors JaimeG.Carbonell,CarnegieMellonUniversity,Pittsburgh,PA,USA Jo¨rgSiekmann,UniversityofSaarland,Saarbru¨cken,Germany VolumeEditors DavidHelmbold UniversityofCalifornia,SantaCruz SchoolofEngineering,DepartmentofComputerScience SantaCruz,CA95064,USA E-mail:[email protected] BobWilliamson AustralianNationalUniversity ResearchSchoolofInformationSciencesandEngineering DepartmentofTelecommunicationsEngineering Canberra0200,Australia E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Computationallearningtheory:proceedings/14thAnnualConferenceon ComputationalLearningTheory,COLT2001and5thEuropeanConferenceon ComputationalLearningTheory,EuroCOLT2001,Amsterdam,TheNetherlands, July16-19,2001.DavidHelmbold;BobWilliamson(ed.).-Berlin; Heidelberg;NewYork;Barcelona;HongKong;London;Milan;Paris; Singapore;Tokyo:Springer,2001 (Lecturenotesincomputerscience;Vol.2111:Lecturenotesin artificialintelligence) ISBN3-540-42343-5 CRSubjectClassification(1998):I.2.6,I.2.3,F.4.1,F.1.1,F.2 ISBN3-540-42343-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 Printedonacid-freepaper SPIN:10839809 06/3142 543210 Preface This volume contains papers presented at the joint 14th Annual Conference on Computational Learning Theory and 5th European Conference on Computatio- nal Learning Theory, held at the Trippenhuis in Amsterdam, The Netherlands from July 16 to 19, 2001. The technical program contained 40 papers selected from 69 submissions. In addition,DavidStork(RicohCaliforniaResearchCenter)wasinvitedtogivean invited lecture and make a written contribution to the proceedings. The Mark Fulk Award is presented annually for the best paper co-authored by a student. This year’s award was won by Olivier Bousquet for the paper “Tracking a Small Set of Modes by Mixing Past Posteriors” (co-authored with Manfred K. Warmuth). We gratefully thank all of the individuals and organizations responsible for the success of the conference. We are especially grateful to the program com- mittee: Dana Angluin (Yale), Peter Auer (Univ. of Technology, Graz), Nello Christianini(RoyalHolloway),ClaudioGentile(Universit`adiMilano),LisaHel- lerstein (Polytechnic Univ.), Jyrki Kivinen (Univ. of Helsinki), Phil Long (Na- tional Univ. of Singapore), Manfred Opper (Aston Univ.), John Shawe-Taylor (Royal Holloway), Yoram Singer (Hebrew Univ.), Bob Sloan (Univ. of Illinois at Chicago), Carl Smith (Univ. of Maryland), Alex Smola (Australian National Univ.), and Frank Stephan (Univ. of Heidelberg), for their efforts in reviewing and selecting the papers in this volume. Special thanks go to our conference co-chairs, Peter Gru¨nwald and Paul Vita´nyi, as well as Marja Hegt. Together they handled the conference publi- city and all the local arrangements to ensure a successful conference. We would alsoliketothankACMSIGACTforthesoftwareusedintheprogramcommittee deliberations and Stephen Kwek for maintaining the COLT web site. Finally, we would like to thank The National Research Institute for Ma- thematics and Computer Science in the Netherlands (CWI), The Amsterdam Historical Museum, and The Netherlands Organization for Scientific Research (NWO) for their sponsorship of the conference. May 2001 David Helmbold Bob Williamson Program Co-chairs COLT/EuroCOLT 2001 Table of Contents How Many Queries Are Needed to Learn One Bit of Information? .......... 1 Hans Ulrich Simon Radial Basis Function Neural Networks Have Superlinear VC Dimension .. 14 Michael Schmitt Tracking a Small Set of Experts by Mixing Past Posteriors ................ 31 Olivier Bousquet and Manfred K. Warmuth Potential-Based Algorithms in Online Prediction and Game Theory ....... 48 Nicolo` Cesa-Bianchi and Ga´bor Lugosi A Sequential Approximation Bound for Some Sample-Dependent Convex Optimization Problems with Applications in Learning ..................... 65 Tong Zhang Efficiently Approximating Weighted Sums with Exponentially Many Terms 82 Deepak Chawla, Lin Li, and Stephen Scott Ultraconservative Online Algorithms for Multiclass Problems .............. 99 Koby Crammer and Yoram Singer Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required ...................................... 116 Paul W. Goldberg Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments ............................................................ 128 Shie Mannor and Nahum Shimkin Robust Learning — Rich and Poor ....................................... 143 John Case, Sanjay Jain, Frank Stephan, and Rolf Wiehagen On the Synthesis of Strategies Identifying Recursive Functions ........... 160 Sandra Zilles IntrinsicComplexityofLearningGeometricalConceptsfromPositiveData 177 Sanjay Jain and Efim Kinber Toward a Computational Theory of Data Acquisition and Truthing ...... 194 David G. Stork Discrete Prediction Games with Arbitrary Feedback and Loss ............ 208 Antonio Piccolboni and Christian Schindelhauer Rademacher and Gaussian Complexities: Risk Bounds and Structural Results ...................................... 224 Peter L. Bartlett and Shahar Mendelson Further Explanation of the Effectiveness of Voting Methods: The Game between Margins and Weights ................................ 241 Vladimir Koltchinskii, Dmitriy Panchenko, and Fernando Lozano VIII Table of Contents Geometric Methods in the Analysis of Glivenko-Cantelli Classes .......... 256 Shahar Mendelson Learning Relatively Small Classes ........................................ 273 Shahar Mendelson On Agnostic Learning with {0,∗,1}-Valued and Real-Valued Hypotheses . 289 Philip M. Long When Can Two Unsupervised Learners Achieve PAC Separation? ........ 303 Paul W. Goldberg Strong Entropy Concentration, Game Theory, and Algorithmic Randomness ............................................ 320 Peter Gru¨nwald Pattern Recognition and Density Estimation under the General i.i.d. Assumption .............................................................. 337 Ilia Nouretdinov, Volodya Vovk, Michael Vyugin, and Alex Gammerman A General Dimension for Exact Learning ................................. 354 Jos´e L. Balca´zar, Jorge Castro, and David Guijarro Data-Dependent Margin-Based Generalization Bounds for Classification .. 368 Bala´zs K´egl, Tama´s Linder, and Ga´bor Lugosi Limitations of Learning via Embeddings in Euclidean Half-Spaces ........ 385 Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces 402 Ju¨rgen Forster, Niels Schmitt, and Hans Ulrich Simon A Generalized Representer Theorem ..................................... 416 Bernhard Scho¨lkopf, Ralf Herbrich, and Alex J. Smola A Leave-One-out Cross Validation Bound for Kernel Methods with Applications in Learning ............................................ 427 Tong Zhang Learning Additive Models Online with Fast Evaluating Kernels .......... 444 Mark Herbster Geometric Bounds for Generalization in Boosting ........................ 461 Shie Mannor and Ron Meir Smooth Boosting and Learning with Malicious Noise ..................... 473 Rocco A. Servedio On Boosting with Optimal Poly-Bounded Distributions .................. 490 Nader H. Bshouty and Dmitry Gavinsky Agnostic Boosting ....................................................... 507 Shai Ben-David, Philip M. Long, and Yishay Mansour A Theoretical Analysis of Query Selection for Collaborative Filtering ..... 517 Wee Sun Lee and Philip M. Long On Using Extended Statistical Queries to Avoid Membership Queries .... 529 Nader H. Bshouty and Vitaly Feldman Table of Contents IX Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries ..................................................... 546 Nader H. Bshouty and Nadav Eiron On Learning Monotone DNF under Product Distributions ................ 558 Rocco A. Servedio Learning Regular Sets with an Incomplete Membership Oracle ........... 574 Nader Bshouty and Avi Owshanko Learning Rates for Q-Learning ........................................... 589 Eyal Even-Dar and Yishay Mansour Optimizing Average Reward Using Discounted Rewards .................. 605 Sham Kakade Bounds on Sample Size for Policy Evaluation in Markov Environments ... 616 Leonid Peshkin and Sayan Mukherjee Author Index .......................................................... 631 How Many Queries Are Needed to Learn One Bit of Information?(cid:1) Hans Ulrich Simon1 Fakult¨at fu¨r Mathematik, Ruhr-Universit¨at Bochum, D-44780 Bochum, Germany [email protected] Abstract. In this paper we study the question how many queries are needed to “halve a given version space”. In other words: how many queries are needed to extract from the learning environment the one bit of information that rules out fifty percent of the concepts which are still candidates for the unknown target concept. We relate this problem totheclassicalexactlearningproblem.Forinstance,weshowthatlower bounds on the number of queries needed to halve a version space also applytorandomizedlearners(whereastheclassicaladversaryarguments do not readily apply). Furthermore, we introduce two new combinato- rial parameters, the halving dimension and the strong halving dimen- sion, which determine the halving complexity (modulo a small constant factor) for two popular models of query learning: learning by a mini- mum adequate teacher (equivalence queries combined with membership queries) and learning by counterexamples (equivalence queries alone). These parameters are finally used to characterize the additional power provided by membership queries (compared to the power of equivalence queries alone). All investigations are purely information-theoretic and ignore computational issues. 1 Introduction The exact learning model was introduced by Angluin in [1]. In this model, a learner A tries to identify an unknown target conceptC (of the form C :X → ∗ ∗ {0,1} for a finite set X) by means of queries that must be honestly answered by an oracle. Although the oracle must not lie, it may select its answers in a worstcasefashionsuchastoslowdownthelearningprocessasmuchaspossible. Inthe(worstcase)analysisofA,weassumethattheoracleisindeedanadversary of A that makes full use of this freedom. (In the sequel, we sometimes say “adversary”insteadof“oracle”forthisreason.)Furthermore,Amustbeableto identifyanytargetconceptselectedfroma(known)conceptclassC.Again,Ais subjectedtoaworstcaseanalysis,i.e.,wecountthenumberofqueriesneededto identify the hardest concept from C (that is the concept that forces A to invest a maximal number of queries). Among the most popular query types are the following ones: (cid:1) ThisworkhasbeensupportedinpartbytheESPRITWorkingGroupinNeuraland ComputationalLearningII,NeuroCOLT2,No.27150.Theauthorwasalsosupported by the Deutsche Forschungsgemeinschaft Grant SI 498/4-1. D.HelmboldandB.Williamson(Eds.):COLT/EuroCOLT2001,LNAI2111,pp.1–13,2001. (cid:2)c Springer-VerlagBerlinHeidelberg2001