Learning Theory and Kernel Machines

This book constitutes the joint refereed proceedings of the 16th Annual Conference on Computational Learning Theory, COLT 2003, and the 7th Kernel Workshop, Kernel 2003, held in Washington, DC in August 2003. The 47 revised full papers presented together with 5 invited contributions and 8 open problem statements were carefully reviewed and selected from 92 submissions. The papers are organized in topical sections on kernel machines, statistical learning theory, online learning, other approaches, and inductive inference learning.

Inhalt

Target Area: Computational Game Theory.- Tutorial: Learning Topics in Game-Theoretic Decision Making.- A General Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria.- Preference Elicitation and Query Learning.- Efficient Algorithms for Online Decision Problems.- Positive Definite Rational Kernels.- Bhattacharyya and Expected Likelihood Kernels.- Maximal Margin Classification for Metric Spaces.- Maximum Margin Algorithms with Boolean Kernels.- Knowledge-Based Nonlinear Kernel Classifiers.- Fast Kernels for Inexact String Matching.- On Graph Kernels: Hardness Results and Efficient Alternatives.- Kernels and Regularization on Graphs.- Data-Dependent Bounds for Multi-category Classification Based on Convex Losses.- Poster Session 1.- Comparing Clusterings by the Variation of Information.- Multiplicative Updates for Large Margin Classifiers.- Simplified PAC-Bayesian Margin Bounds.- Sparse Kernel Partial Least Squares Regression.- Sparse Probability Regression by Label Partitioning.- Learning with Rigorous Support Vector Machines.- Robust Regression by Boosting the Median.- Boosting with Diverse Base Classifiers.- Reducing Kernel Matrix Diagonal Dominance Using Semi-definite Programming.- Optimal Rates of Aggregation.- Distance-Based Classification with Lipschitz Functions.- Random Subclass Bounds.- PAC-MDL Bounds.- Universal Well-Calibrated Algorithm for On-Line Classification.- Learning Probabilistic Linear-Threshold Classifiers via Selective Sampling.- Learning Algorithms for Enclosing Points in Bregmanian Spheres.- Internal Regret in On-Line Portfolio Selection.- Lower Bounds on the Sample Complexity of Exploration in the Multi-armed Bandit Problem.- Smooth ?-Insensitive Regression by Loss Symmetrization.- On Finding Large Conjunctive Clusters.- Learning Arithmetic Circuits via Partial Derivatives.- Poster Session 2.- Using a Linear Fit to Determine Monotonicity Directions.- Generalization Bounds for Voting Classifiers Based on Sparsity and Clustering.- Sequence Prediction Based on Monotone Complexity.- How Many Strings Are Easy to Predict?.- Polynomial Certificates for Propositional Classes.- On-Line Learning with Imperfect Monitoring.- Exploiting Task Relatedness for Multiple Task Learning.- Approximate Equivalence of Markov Decision Processes.- An Information Theoretic Tradeoff between Complexity and Accuracy.- Learning Random Log-Depth Decision Trees under the Uniform Distribution.- Projective DNF Formulae and Their Revision.- Learning with Equivalence Constraints and the Relation to Multiclass Learning.- Target Area: Natural Language Processing.- Tutorial: Machine Learning Methods in Natural Language Processing.- Learning from Uncertain Data.- Learning and Parsing Stochastic Unification-Based Grammars.- Generality's Price.- On Learning to Coordinate.- Learning All Subfunctions of a Function.- When Is Small Beautiful?.- Learning a Function of r Relevant Variables.- Subspace Detection: A Robust Statistics Formulation.- How Fast Is k-Means?.- Universal Coding of Zipf Distributions.- An Open Problem Regarding the Convergence of Universal A Priori Probability.- Entropy Bounds for Restricted Convex Hulls.- Compressing to VC Dimension Many Points.