Learning Theory and Kernel Machines: 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings

Front Cover
Bernhard Schoelkopf, Manfred K. Warmuth
Springer Science & Business Media, Aug 11, 2003 - Computers - 754 pages
This volume contains papers presented at the joint 16th Annual Conference on Learning Theory (COLT) and the 7th Annual Workshop on Kernel Machines, heldinWashington,DC,USA,duringAugust24–27,2003.COLT,whichrecently merged with EuroCOLT, has traditionally been a meeting place for learning theorists. We hope that COLT will bene?t from the collocation with the annual workshoponkernelmachines,formerlyheldasaNIPSpostconferenceworkshop. The technical program contained 47 papers selected from 92 submissions. All 47paperswerepresentedasposters;22ofthepaperswereadditionallypresented astalks.Therewerealsotwotargetareaswithinvitedcontributions.Incompu- tional game theory,atutorialentitled“LearningTopicsinGame-TheoreticDe- sionMaking”wasgivenbyMichaelLittman,andaninvitedpaperon“AGeneral Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria” was contributed by Amy Greenwald. In natural language processing, a tutorial on “Machine Learning Methods in Natural Language Processing” was presented by Michael Collins, followed by two invited talks, “Learning from Uncertain Data” by Mehryar Mohri and “Learning and Parsing Stochastic Uni?cation- Based Grammars” by Mark Johnson. In addition to the accepted papers and invited presentations, we solicited short open problems that were reviewed and included in the proceedings. We hope that reviewed open problems might become a new tradition for COLT. Our goal was to select simple signature problems whose solutions are likely to inspire further research. For some of the problems the authors o?ered monetary rewards. Yoav Freund acted as the open problem area chair. The open problems were presented as posters at the conference.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

A General Class of NoRegret Learning Algorithms and GameTheoretic Equilibria
2
Preference Elicitation and Query Learning
13
Efficient Algorithms for Online Decision Problems
26
Positive Definite Rational Kernels
41
Bhattacharyya and Expected Likelihood Kernels
57
Maximal Margin Classification for Metric Spaces
72
Maximum Margin Algorithms with Boolean Kernels
87
KnowledgeBased Nonlinear Kernel Classifiers
102
On Finding Large Conjunctive Clusters
448
Learning Arithmetic Circuits via Partial Derivatives
463
Using a Linear Fit to Determine Monotonicity Directions
477
Generalization Bounds for Voting Classifiers Based on Sparsity and Clustering
492
Sequence Prediction Based on Monotone Complexity
506
How Many Strings Are Easy to Predict?
522
Polynomial Certificates for Propositional Classes
537
OnLine Learning with Imperfect Monitoring
552

Fast Kernels for Inexact String Matching
114
Hardness Results and Efficient Alternatives
129
Kernels and Regularization on Graphs
144
DataDependent Bounds for Multicategory Classification Based on Convex Losses
159
Comparing Clusterings by the Variation of Information
173
Multiplicative Updates for Large Margin Classifiers
188
Simplified PACBayesian Margin Bounds
203
Sparse Kernel Partial Least Squares Regression
216
Sparse Probability Regression by Label Partitioning
231
Learning with Rigorous Support Vector Machines
243
Robust Regression by Boosting the Median
258
Boosting with Diverse Base Classifiers
273
Reducing Kernel Matrix Diagonal Dominance Using Semidefinite Programming
288
Optimal Rates of Aggregation
303
DistanceBased Classification with Lipschitz Functions
314
Random Subclass Bounds
329
PACMDL Bounds
344
Universal WellCalibrated Algorithm for OnLine Classification
358
Learning Probabilistic LinearThreshold Classifiers via Selective Sampling
373
Learning Algorithms for Enclosing Points in Bregmanian Spheres
388
Internal Regret in OnLine Portfolio Selection
403
Lower Bounds on the Sample Complexity of Exploration in the Multiarmed Bandit Problem
418
Smooth εInsensitive Regression by Loss Symmetrization
433
Exploiting Task Relatedness for Multiple Task Learning
567
Approximate Equivalence of Markov Decision Processes
581
An Information Theoretic Tradeoff between Complexity and Accuracy
595
Learning Random LogDepth Decision Trees under the Uniform Distribution
610
Projective DNF Formulae and Their Revision
625
Learning with Equivalence Constraints and the Relation to Multiclass Learning
640
Machine Learning Methods in Natural Language Processing
655
Learning from Uncertain Data
656
Learning and Parsing Stochastic UnificationBased Grammars
671
Inescapable Deficiencies in MachineLearned Programs
684
Random Bits Help Insightful Normal Forms and Competency Isomorphisms
699
Learning All Subfunctions of a Function
714
When Is Small Beautiful?
729
Learning a Function of r Relevant Variables
731
A Robust Statistics Formulation
734
How Fast Is kMeans?
735
Universal Coding of Zipf Distributions
736
An Open Problem Regarding the Convergence of Universal A Priori Probability
738
Entropy Bounds for Restricted Convex Hulls
741
Compressing to VC Dimension Many Points
743
Author Index
745
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information