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

1 Introduction......Page 16
2 Approachability......Page 18
3 No-Regret Learning......Page 19
4 $\\Phi$-Equilibrium......Page 23
5 Conclusion......Page 26
1 Introduction......Page 27
 1.1 Preference Elicitation and Query Learning......Page 28
 1.2 Related Work on Combinatorial Auctions......Page 29
2 Notation and Definitions......Page 31
3 DNF Preferences......Page 32
4 General Relationships......Page 35
5 Conclusions and Open Problems......Page 37
References......Page 38
1 Introduction......Page 40
 1.1 Generalization......Page 42
 2.1 The Model......Page 43
 2.2 Follow the Perturbed Leader......Page 45
 2.4 Competitive Versions of FLL and FPL......Page 46
 2.5 Follow the Expected Leader and Online Linear Optimization......Page 47
 3.1 Predicting from Expert Advice......Page 48
4 Conclusions and Open Problems......Page 49
References......Page 50
 A.1 FPL......Page 51
 A.4 FPL* and FLL*......Page 53
References......Page 70
1 Introduction......Page 71
2 A Kernel on Distributions......Page 72
 2.1 Frequentist and Bayesian Methods of Estimation......Page 74
3 Exponential Families......Page 75
 3.1 Gaussian Models......Page 76
 3.3 Multinomial Models......Page 77
5 Hidden Markov Models and Bayesian Networks......Page 78
6 Sampling Approximation......Page 80
7 Reproducing Kernel Hilbert Spaces......Page 81
8 Text Experiments......Page 82
9 Sequence Experiments......Page 83
References......Page 84
1 Introduction......Page 86
 2.1 The RKHS and the Formulation of the SVM......Page 87
 2.2 The Input Space as a Semi-metric Space......Page 88
 2.3 Formulation of the SVM in Terms of the Semi-metric......Page 91
 3.1 Isometric Embedding of a General Metric Space into a Banach Space......Page 93
 3.2 Duality of Maximal Margin Hyperplanes and Distance of Convex Hulls in Banach Spaces......Page 94
4 Semi-metric Spaces Compared to Metric Spaces for Classification......Page 96
5 Generalization Bounds Using Rademacher Averages......Page 97
6 Conclusion and Perspectives......Page 99
References......Page 100
1 Introduction......Page 116
2 Prior Knowledge in a Nonlinear Kernel Classifier......Page 117
3 Knowledge-Based Linear Programming Formulation of Nonlinear Kernel Classifiers......Page 120
4 Numerical Experience......Page 122
References......Page 126
1 Introduction......Page 128
 2.1 Spectrum and Mismatch Kernels......Page 129
 2.2 Restricted Gappy Kernels......Page 130
 2.3 Substitution Kernels......Page 131
3 Efficient Computation......Page 132
 3.1 $g,k$-Gappy Kernel Computation......Page 133
 3.3 $k,m$-Wildcard Kernel Computation......Page 135
4 Transducer Representation......Page 136
5 Experiments......Page 138
 5.2 Substitution Kernels......Page 139
6 Discussion......Page 140
References......Page 141
1 Introduction......Page 143
 1.1 Motivation and Approach......Page 144
 2.1 Basic Terminology and Notation......Page 145
 2.3 Interpretation of Matrix Powers......Page 146
3 Complete Graph Kernels......Page 147
4 Kernels Based on Label Pairs......Page 149
5 Kernels Based on Contiguous Label Sequences......Page 150
 6.2 Transition Graphs......Page 152
 6.3 Non-contiguous Label Sequences......Page 153
7 Discussion and Related Work......Page 154
8 Conclusions and Future Work......Page 156
References......Page 157
1 Introduction......Page 173
2 Problem Formulation and Preliminary Results......Page 174
3 Convex Upper Bounds on the $0-1$ Loss......Page 175
4 Data-Dependent Bounds......Page 179
5 Discussion......Page 184
References......Page 185
References......Page 227
1 Introduction......Page 257
2 Review of RSVM Formulations......Page 258
3 Characteristics of RSVM......Page 261
4 Comparison with Other SVMs......Page 263
5 Choosing $H$ and the Decomposition Scheme......Page 265
6 Experimental Studies......Page 268
7 Conclusion......Page 270
References......Page 271
1 Introduction......Page 302
Appendix 1......Page 314
References......Page 315
1 Introduction......Page 317
2 Main Definition and Lower Bounds......Page 319
3 Attainability of the Lower Bounds......Page 323
References......Page 326
1 Introduction......Page 328
2 Preliminaries: Lipschitz Function Spaces......Page 330
3 The Lipschitz Classifier......Page 332
4 Representer Theorems......Page 334
 5.1 The Duality Approach......Page 336
 5.2 Covering Number Approach......Page 337
 5.3 Complexity of Lipschitz RBF Classifiers......Page 339
6 Conclusion......Page 340
Appendix: Proof of Theorem 10......Page 341
References......Page 342
1 Introduction......Page 343
 2.1 Symmetrization......Page 346
 2.2 Concentration Result......Page 349
 3.1 Uniform Glivenko-Cantelli Classes......Page 350
 3.2 Data-Dependent Class Bounds......Page 351
 3.3 Compression Schemes......Page 352
References......Page 357
1 Introduction......Page 358
 1.1 Viewing Sample Complexity Bounds as Label Compression......Page 359
 1.2 Stating a PAC-MDL Bound......Page 360
3 Realizable Case......Page 361
 3.1 Comparison to Standard Bounds: Qualitative Results......Page 362
 3.2 VC-Bounds......Page 363
 3.3 PAC-Bayes Bounds......Page 364
4 The Agnostic Case......Page 365
 4.1 Lower Bound......Page 366
5 Comparison to Standard Bounds: Quantitative Results......Page 367
 5.1 The Occam\'s Razor bound......Page 368
 5.2 The Compression Bound......Page 369
6 Discussion......Page 370
References......Page 371
1 Introduction......Page 372
2 Main Result......Page 373
 3.1 Preliminaries......Page 377
 3.3 Universal TCM......Page 378
4 Fine Details of Region Prediction......Page 379
 A.1 Proof Sketch of Proposition 2......Page 382
 A.2 Proof Sketch of Proposition 4......Page 384
1 Introduction......Page 387
2 Learning Model, Preliminaries and Notation......Page 389
3 Definition and Analysis of the Algorithm......Page 390
References......Page 400
1 Introduction......Page 417
2 Sequential Prediction......Page 418
3 Sequential Portfolio Selection......Page 421
4 Internal Regret of Investment Strategies......Page 425
5 Investment Strategies with Small Internal Regret......Page 426
 5.1 Generalized Buy-and-Hold Strategy......Page 427
 5.2 A Strategy with Small Internal and External Regrets......Page 428
6 A Generalized Universal Portfolio......Page 430
References......Page 431
1 Introduction......Page 432
2 Problem Definition......Page 434
3 A Lower Bound on the Sample Complexity......Page 435
4 The Bayesian Setup......Page 438
5 A Lower Bound on the Sample Complexity -- General Probabilities......Page 439
References......Page 446
1 Introduction......Page 447
2 Regularization......Page 450
3 Log-Additive Update for Batch Regression......Page 451
4 Additive Update for Batch Regression......Page 455
5 Online Regression Algorithms......Page 458
6 Discussion......Page 460
References......Page 461
1 Introduction......Page 477
2 Preliminaries......Page 481
3 Characterizing Learnability via Partial Derivatives......Page 484
4 Learning Multilinear Depth-3 Arithmetic Circuits......Page 486
5 Further Results......Page 488
References......Page 489
1 Introduction and Results......Page 491
2 Proofs......Page 498
References......Page 504
1 Introduction......Page 506
2 Main Results......Page 508
3 Proofs......Page 511
4 Experiments with Learning Algorithms......Page 515
References......Page 518
1 Introduction......Page 520
2 Notation and Setup......Page 522
4 Alternatives to Solomonoff\'s Prior $M$......Page 524
5 General Predictive Functions......Page 526
6 Predictive Properties of $m=2^{-Km}$......Page 527
7 Proof of Theorem 5......Page 529
8 Outlook and Open Problems......Page 532
References......Page 534
References......Page 544
1 Introduction......Page 566
2 The Model......Page 568
3 P2 Determines the Signals......Page 569
 3.1 Reward is Observed......Page 571
 3.2 Unobserved Reward......Page 572
 3.3 An Example......Page 573
4 The General Case......Page 575
A Proof of Theorem 2......Page 576
1 Introduction......Page 581
 1.1 Previous Work......Page 582
 2.1 Our Notion of Relatedness between Learning Tasks......Page 583
3 Learning $\\mathcal {F}$-Related Tasks......Page 584
 3.1 Background from Baxter [Bax00]......Page 586
 3.2 Bounding the Generalization Error for \\textit {Each} Task......Page 587
 3.3 Analysis of Axis-Aligned Rectangles under Euclidean Shifts......Page 588
4 Multiple Task Learning versus the Single Task Approach......Page 589
 4.1 Analysis of $d_{\\mathbf {H}}n$......Page 590
References......Page 593
1 Introduction......Page 595
2 Model......Page 596
3 Markov Decision Process Minimization......Page 597
4 Hardness of Epsilon Equivalence......Page 598
5 $L_1$ versus $L_infty $......Page 599
6 Approximation Scheme......Page 601
 6.1 A Heuristic Finer Partition......Page 604
7 Markov Decision Process Equivalence......Page 605
References......Page 607
6 Learning Random $1/2 log n$-Depth Trees......Page 632
1 Introduction......Page 639
2 Preliminaries......Page 641
3 Projective DNF......Page 642
4 Exclusion Dimension......Page 643
5 A Characterization of 1-PDNF......Page 645
 6.1 Revising Disjunctions......Page 648
 6.2 Revising k-PDNF......Page 651
References......Page 653
1 Introduction......Page 654
 2.1 PAC Framework in the Product Space......Page 657
 2.2 The Connection between Solution Quality of the Two Problems......Page 658
 2.3 The Connection between Sample Size Complexity......Page 662
 3.1 Partitioning Using a Product Space Hypothesis......Page 664
 3.2 Classifing Using a Product Space Hypothesis......Page 667
References......Page 668
1 Introduction......Page 670
2 Prelimaries......Page 672
 3.1 Definition......Page 674
 3.2 Algorithm......Page 675
 4.1 Definition......Page 677
 4.2 Examples of Rational Kernels......Page 678
5 Clustering......Page 680
References......Page 683
1 Introduction......Page 685
2 Lexical-Functional Grammar......Page 686
3 Maxwell-Kaplan Packed Parse Representations......Page 687
4 Stochastic Unification-Based Grammars......Page 690
5 Packed Representations and Graphical Models......Page 691
 5.1 Graphical Model Calculations......Page 693
6 Conclusion......Page 695
References......Page 696
1 Introduction......Page 698
2 Conventions and Notation......Page 701
3 Inseparability Notions......Page 703
4 Sufficient Conditions Theorems......Page 704
5 A Few More Diagonalization and Structural Tools......Page 707
6 Negative, Almost Everywhere Results for $\\mathrm {EX}^*$ and $\\mathrm {BC}^0$......Page 708
7 Infinitely Often Results for $\\mathrm {BC}^m$......Page 710
8 Positive, Almost Everywhere Results for $\\mathrm {BC}^*$......Page 711
References......Page 712
1 Introduction......Page 713
2 Mathematical Preliminaries......Page 716
3 Probabilistic vs. Deterministic Coordinators......Page 717
References......Page 726
1 Introduction......Page 728
2 Notation and Preliminaries......Page 732
 2.1 Function Identification......Page 733
3 Definitions for Sublearning......Page 734
 4.1 Comparing the Basic Types of Sublearning to Each Other......Page 735
 4.2 Consistent Sublearning......Page 737
5 Characterizations for Sublearning......Page 738
References......Page 741
References......Page 747
References......Page 748
References......Page 751
References......Page 753
References......Page 756
References......Page 758