Riassunto
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 http://www. 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. Bartlett,Olivier Bousquet,and Shahar Mendelson SomeLocalMeasuresofComplexityofConvexHulls andGeneralizationBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Olivier Bousquet,Vladimir Koltchinskii, and DmitriyPanchenko OnlineLearning PathKernelsandMultiplicativeUpdates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Eiji Takimoto andManfred K. Warmuth PredictiveComplexityandInformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Michael V. Vyugin andVladimir V. V’yugin MixabilityandtheExistenceofWeakComplexities. . . . . . . . . . . . . . . . . . . . . . . 105 YuriKalnishkan andMichael V. Vyugin ASecond-OrderPerceptronAlgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Nicolo ` Cesa-Bianchi, AlexConconi, and Claudio Gentile TrackingLinear-ThresholdConceptswithWinnow . . . . . . . . . . . . . . . . . . . . . . . . 138 Chris Mesterharm Inductive Inference LearningTreeLanguagesfromText. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 HenningFernau PolynomialTimeInductiveInferenceofOrderedTreePatterns withInternalStructuredVariablesfromPositiveData . . . . . . . . . . . . . . . . . . . . 169 YusukeSuzuki,RyutaAkanuma,Takayoshi Shoudai, TetsuhiroMiyahara, andTomoyuki Uchida X Table of Contents InferringDeterministicLinearLanguages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Colin dela HigueraandJoseOncina MergingUniformInductiveLearners. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 SandraZilles TheSpeedPrior:ANewSimplicityMeasure YieldingNear-OptimalComputablePredictions. . . . . . . . .
Contenuti
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.
Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.
