Computational Learning Theory

This book constitutes the refereed proceedings of the 15th Annual Conference on Computational Learning Theory, COLT 2002, held in Sydney, Australia, in July 2002.The 26 revised full papers presented were carefully reviewed and selected from 55 submissions. The papers are organized in topical sections on statistical learning theory, online learning, inductive inference, PAC learning, boosting, and other learning paradigms.

Inhalt

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.