Jyrki Kivinen / Robert H. Sloan (eds.)

Computational Learning Theory

15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002. Proceedings
Herausgegeben:Kivinen, Jyrki; Sloan, Robert H.

• Broschiertes Buch

Produktbeschreibung

ThisvolumecontainspaperspresentedattheFifteenthAnnualConferenceon ComputationalLearningTheory(COLT2002)heldonthemaincampusofthe UniversityofNewSouthWalesinSydney,AustraliafromJuly8to10,2002. Naturally,thesearepapersinthe?eldofcomputationallearningtheory,a- search?elddevotedtostudyingthedesignandanalysisofalgorithmsformaking predictionsaboutthefuturebasedonpastexperiences,withanemphasisonr- orousmathematicalanalysis. COLT2002wasco-locatedwiththeNineteenthInternationalConferenceon MachineLearning(ICML2002)andwiththeTwelfthInternationalConference onInductiveLogicProgramming(ILP2002). NotethatCOLT2002wasthe?rstconferencetotakeplaceafterthefull mergeroftheAnnualConferenceonComputationalLearningTheorywiththe EuropeanConferenceonComputationalLearningTheory. (In2001ajointc- ferenceconsistingofthe5thEuropeanConferenceonComputationalLearning Theoryandthe14thAnnualConferenceonComputationalLearningTheory washeld;thelastindependentEuropeanConferenceonComputationalLea- ingTheorywasheldin1999. ) ThetechnicalprogramofCOLT2002contained26papersselectedfrom 55submissions. Inaddition,ChristosPapadimitriou(UniversityofCaliforniaat Berkeley)wasinvitedtogiveakeynotelectureandtocontributeanabstractof hislecturetotheseproceedings. TheMarkFulkAwardispresentedannuallyforthebestpapercoauthored byastudent. Thisyear sawardwaswonbySandraZillesforthepaper Merging UniformInductiveLearners. April2002 JyrkiKivinen RobertH. Sloan Thanks and Acknowledgments Wegratefullythankalltheindividualsandorganizationsresponsibleforthe successoftheconference. ProgramCommittee Weespeciallywanttothanktheprogramcommittee:DanaAngluin(Yale), JavedAslam(Dartmouth),PeterBartlett(BIOwulfTechnologies),ShaiBen- David(Technion),JohnCase(Univ. ofDelaware),PeterGru nwald(CWI),Ralf Herbrich(MicrosoftResearch),MarkHerbster(UniversityCollegeLondon), G aborLugosi(PompeuFabraUniversity),RonMeir(Technion),ShaharMend- son(AustralianNationalUniv. ),MichaelSchmitt(Ruhr-Universit atBochum), RoccoServedio(Harvard),andSantoshVempala(MIT). WealsoacknowledgethecreatorsoftheCyberChairsoftwareformakinga softwarepackagethathelpedthecommitteedoitswork. Local Arrangements, Co-located Conferences Support SpecialthanksgotoourconferencechairArunSharmaandlocalarrangements chairEricMartin(bothatUniv. ofNewSouthWales)forsettingupCOLT2002 inSydney. RochelleMcDonaldandSueLewisprovidedadministrativesupport. ClaudeSammutinhisroleasconferencechairofICMLandprogramco-chair ofILPensuredsmoothcoordinationwiththetwoco-locatedconferences. COLT Community ForkeepingtheCOLTseriesgoing,wethanktheCOLTsteeringcommittee, andespeciallyChairJohnShawe-TaylorandTreasurerJohnCaseforalltheir hardwork. WealsothankStephenKwekformaintainingtheCOLTwebsiteat learningtheory. org. Sponsoring Institution SchoolofComputerScienceandEngineering,UniversityofNewSouthWales, Australia VIII Thanks and Acknowledgments Referees PeterAuer LisaHellerstein AlainPajor AndrewBarto DanielHerrmann GunnarR atsch StephaneBoucheron ColindelaHiguera RobertSchapire OlivierBousquet SeanHolden JohnShawe-Taylor Nicol`oCesa-Bianchi MarcusHutter TakeshiShinohara TapioElomaa SanjayJain DavidShmoys RanEl-Yaniv YuriKalnishkan YoramSinger AllanErskine MakotoKanazawa CarlSmith HenningFernau SatoshiKobayashi FrankStephan J urgenForster VladimirKoltchinskii Gy orgyTur an DeanFoster MattiKa ariai nen PaulVitan yi ClaudioGentile WeeSunLee ManfredWarmuth JudyGoldsmith ShieMannor JonA. Wellner ThoreGraepel RyanO Donnell RobertC. Williamson Table of Contents Statistical Learning Theory AgnosticLearningNonconvexFunctionClasses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Shahar Mendelson andRobertC. Williamson Entropy,CombinatorialDimensionsandRandomAverages. . . . . . . . . . . . . . . . . 14 Shahar Mendelson andRoman Vershynin GeometricParametersofKernelMachines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Shahar Mendelson LocalizedRademacherComplexities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 44 PeterL.

Produktdetails

• Lecture Notes in Computer Science 2375
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-540-43836-6
• 2002
• Seitenzahl: 424
• Erscheinungstermin: 26. Juni 2002
• Englisch
• Abmessung: 235mm x 155mm x 23mm
• Gewicht: 594g
• ISBN-13: 9783540438366
• ISBN-10: 354043836X
• Artikelnr.: 23380463

Autorenporträt

Jyrki Kivinen, Australian National University, Canberra, ACT, Australia / Robert H. Sloan, University of Illinois at Chicago, IL, USA

Inhaltsangabe

Statistical Learning Theory.- Agnostic Learning Nonconvex Function Classes.- Entropy, Combinatorial Dimensions and Random Averages.- Geometric Parameters of Kernel Machines.- Localized Rademacher Complexities.- Some Local Measures of Complexity of Convex Hulls and Generalization Bounds.- Online Learning.- Path Kernels and Multiplicative Updates.- Predictive Complexity and Information.- Mixability and the Existence of Weak Complexities.- A Second-Order Perceptron Algorithm.- Tracking Linear-Threshold Concepts with Winnow.- Inductive Inference.- Learning Tree Languages from Text.- Polynomial Time Inductive Inference of Ordered Tree Patterns with Internal Structured Variables from Positive Data.- Inferring Deterministic Linear Languages.- Merging Uniform Inductive Learners.- The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions.- PAC Learning.- New Lower Bounds for Statistical Query Learning.- Exploring Learnability between Exact and PAC.- PAC Bounds for Multi-armed Bandit and Markov Decision Processes.- Bounds for the Minimum Disagreement Problem with Applications to Learning Theory.- On the Proper Learning of Axis Parallel Concepts.- Boosting.- A Consistent Strategy for Boosting Algorithms.- The Consistency of Greedy Algorithms for Classification.- Maximizing the Margin with Boosting.- Other Learning Paradigms.- Performance Guarantees for Hierarchical Clustering.- Self-Optimizing and Pareto-Optimal Policies in General Environments Based on Bayes-Mixtures.- Prediction and Dimension.- Invited Talk.- Learning the Internet.