Learning Theory and Kernel Machines

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.- LearningArithmetic 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.