Algorithmic Learning Theory
Author(s):        J. L. Balcazar, Ph. M. Long, F. Stephan (Eds.)
Series:        Lecture notes in computer science 4264        Periodical:       
Publisher:        Springer

Language:        English       
Pages:        404
ISBN:        0302974335


Table of contents :
000......Page 1
001......Page 12
010......Page 21
012......Page 23
Introduction......Page 24
Definitions and Notations......Page 25
Statistical Queries Versus Correlation Queries......Page 28
A Lower Bound in Terms of the Spectral Norm......Page 29
Related Lower Bounds......Page 30
Characterizations of Statistical Query Learnability......Page 33
Hidden Number Problem and Bit Security......Page 34
Hidden Number Problem and Learning......Page 35
028......Page 39
029......Page 40
Introduction......Page 43
Preliminaries......Page 45
The Generalized Harmonic Sieve Algorithm......Page 48
Correlated Fourier Basis Elements for Functions in $\mathfrak{C}$......Page 49
The Second Approach......Page 51
Locating Sensitive Elements and Learning with GHS on a Restricted Grid......Page 52
Learning Majorities of Many Low-Dimensional Rectangles......Page 55
Learning Majorities of Unions of Disjoint Rectangles......Page 56
Conclusions and Future Work......Page 57
Preliminaries......Page 59
Probability......Page 60
Halfspace......Page 61
Dual Domain......Page 62
Convex Set......Page 63
Old and New Results......Page 64
The Dual Concept Class......Page 66
Polynomial Time Learning Halfspaces......Page 68
Maass-Turan Algorithm......Page 69
Our Algorithm......Page 70
Open Problems......Page 72
Introduction......Page 74
Learning Model......Page 77
Positive Result......Page 79
Negative Result......Page 82
Lower Bound for the Noisy Case......Page 83
Lower Bound for Deterministic Targets......Page 84
Conclusions......Page 87
Introduction......Page 89
Quantum Computation......Page 91
Quantum Protocols......Page 92
Query Complexity......Page 94
Answering Schemes......Page 95
The General Halving Dimension......Page 96
A Lower Bound for the Quantum Query Complexity......Page 97
Upper Bounds for the Query Complexity......Page 98
The General Halving Dimension and the Query Complexity of Randomized Learners......Page 101
Polynomial Learnability......Page 102
Introduction......Page 104
The Teaching Model......Page 106
Existence of Optimal Teachers......Page 108
Finding Optimal Teachers......Page 111
Cyclic Teachers......Page 115
Greedy Teachers......Page 117
Introduction......Page 120
Definitions About Subsequences......Page 122
Classes of Languages......Page 123
Standard Learning......Page 124
Anomalies......Page 125
Mind Changes......Page 126
Teams......Page 129
Rich Classes......Page 132
Open Questions......Page 133
Introduction......Page 135
Inductive Inference from Positive Data......Page 136
Well-Partial-Orders......Page 137
Mind Change Complexity......Page 138
Closed Set Systems......Page 139
Upper and Lower Mind Change Bounds for $L$(RP$_l$)$^{\omega}$......Page 141
Mind Change Bounds and Reverse Mathematics......Page 144
Discussion and Conclusion......Page 146
Introduction......Page 150
Notation and Preliminaries......Page 152
Learning Sublanguages: Definitions and Separations......Page 154
Some Characterizations......Page 159
Monotonicity Constraints......Page 161
Introduction......Page 165
Notation and Preliminaries......Page 168
Learning with Negative Counterexamples......Page 171
Relationship Among Different Variations of NCIt-Criteria......Page 172
Comparison with Other Criteria of Learning......Page 173
Results Related to Indexed Families......Page 177
Non-U-shaped Learning......Page 178
Introduction......Page 180
Preliminaries......Page 182
Learning from Text......Page 183
Learning from Informant......Page 184
A Case Study: The Regular Erasing Pattern Languages......Page 185
Incremental Learning and Consistency......Page 187
The Case of Learning from Text......Page 189
The Case of Learning from Informant......Page 190
Some Concluding Remarks......Page 193
Introduction......Page 195
Learning Models and Definitions......Page 196
Negative Results for Random Walk Learning......Page 197
Learning Boolean Functions That Depend on logn Variables......Page 199
Learning Read-Once Monotone DNF Functions......Page 202
Introduction......Page 210
Preliminaries......Page 212
A Lower Bound for MV......Page 214
A Bicriteria Upper Bound......Page 215
No-Regret Results for Localized Risk......Page 216
Empirical Results......Page 218
Proof of Theorem 1......Page 220
Proof of Theorem 2......Page 221
Proof of Theorem 4......Page 224
Introduction......Page 225
On-Line Quadratic-Loss Regression......Page 226
Predictions Evaluated by Bregman Divergences......Page 229
Predictions Evaluated by Strictly Proper Scoring Rules......Page 231
Stochastic Reality and Jeffreys's Law......Page 233
Proofs......Page 235
Conclusion......Page 237
Introduction......Page 240
Sequential Prediction and Partial Monitoring Models......Page 241
The Algorithm......Page 243
Bounds on the Expected Regret......Page 244
Hannan Consistency......Page 247
Proof......Page 249
Introduction......Page 255
Example Discount and Reward Sequences......Page 257
Average Value......Page 261
Discounted Value......Page 262
Average Implies Discounted Value......Page 263
Discounted Implies Average Value......Page 265
Average Equals Discounted Value......Page 267
Discussion......Page 268
Introduction......Page 270
Setup and Bayes Mixture......Page 274
Stochastic Model Selection......Page 277
Entropy Potential and Countable Classes......Page 281
The Magnitude of the Entropy Potential......Page 283
Introduction......Page 285
Preliminaries......Page 286
Prediction of Computable Sequences......Page 288
Prediction of Simple Computable Sequences......Page 290
Complexity of Prediction......Page 292
Hard to Predict Sequences......Page 293
The Limits of Mathematical Analysis......Page 294
Discussion......Page 296
Motivation......Page 299
Linear Separability of Piecewise-Testable Languages......Page 301
Efficient Kernel Computation......Page 305
Learning Linearly Separable Languages......Page 306
Finite Cover with Regular Languages......Page 309
Main Result......Page 310
Representer Theorem......Page 311
Conclusion......Page 312
Introduction......Page 315
Boosting Approach......Page 317
Derivation......Page 318
Our Algorithm......Page 320
Boosting by Filtering......Page 322
Improvement on Sampling......Page 324
Experimental Results......Page 326
Summary and Future Work......Page 327
Introduction......Page 330
Thresholded Ensemble Model for Ordinal Regression......Page 331
Large-Margin Bounds for Thresholded Ensembles......Page 332
Margins......Page 333
Large-Margin Bounds......Page 334
RankBoost for Ordinal Regression......Page 336
Ordinal Regression Boosting with Left-Right Margins......Page 337
Ordinal Regression Boosting with All Margins......Page 338
Artificial Dataset......Page 339
Benchmark Datasets......Page 340
Conclusion......Page 342
Proof of Theorem 1......Page 344
Introduction......Page 345
Notation and Definitions......Page 347
Setup......Page 348
Main Results......Page 349
Necessity of Value-Stability......Page 353
Discussion......Page 354
Proof of Theorem 2......Page 355
Introduction......Page 359
Preliminaries......Page 360
Probabilistic Generality of Subclasses of Simple Grammars......Page 362
A Unifiable Subclass of Simple Grammars......Page 364
Application to Reinforcement Learning......Page 368
Introduction......Page 374
Hilbert Schmidt Operators......Page 378
Mixing Coefficients and Inequalities......Page 379
Generalization......Page 380
A Generic Error Bound......Page 383
Experiments......Page 385
Introduction......Page 389
VC Dimension Analysis......Page 391
Graph Dimension Analysis......Page 392
Graph Dimension of DL$_{\mathcal{L}}$......Page 393
Graph Dimension of LR......Page 394
Vapnik's Framework of Risk Minimization......Page 398
Error Probability Bounds in the Multi-class Classification Setting......Page 399
Risk Bounds in the Ordinal Regression Setting......Page 400
Concluding Remarks......Page 402
999......Page 404