Algorithmic Learning Theory: 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004, Proceedings

David Sh. B. (Ed), Case J. (Ed), Maruoka A. (Ed)3540302158

This book constitutes the refereed proceedings of the 15th International Conference on Algorithmic Learning Theory, ALT 2004, held in Padova, Italy in October 2004.The 29 revised full papers presented together with 5 invited papers and 3 tutorial summaries were carefully reviewed and selected from 91 submissions. The papers are organized in topical sections on inductive inference, PAC learning and boosting, statistical supervised learning, online sequence learning, approximate optimization algorithms, logic based learning, and query and reinforcement learning.

---

Table of contents :
Table of Contents……Page 12
String Pattern Discovery……Page 16
Applications of Regularized Least Squares to Classification Problems……Page 29
Probabilistic Inductive Logic Programming……Page 34
Hidden Markov Modelling Techniques for Haplotype Analysis……Page 52
Learning, Logic, and Probability: A Unified View……Page 68
Learning Languages from Positive Data and Negative Counterexamples……Page 69
Inductive Inference of Term Rewriting Systems from Positive Data……Page 84
On the Data Consumption Benefits of Accepting Increased Uncertainty……Page 98
Comparison of Query Learning and Gold-Style Learning in Dependence of the Hypothesis Space……Page 114
Learning r-of-k Functions by Boosting……Page 129
Boosting Based on Divide and Merge……Page 142
Learning Boolean Functions in AC[sup(0)] on Attribute and Classification Noise……Page 157
Decision Trees: More Theoretical Justification for Practical Algorithms……Page 171
Application of Classical Nonparametric Predictors to Learning Conditionally I.I.D. Data……Page 186
Complexity of Pattern Classes and Lipschitz Property……Page 196
On Kernels, Margins, and Low-Dimensional Mappings……Page 209
Estimation of the Data Region Using Extreme-Value Distributions……Page 221
Maximum Entropy Principle in Non-ordered Setting……Page 236
Universal Convergence of Semimeasures on Individual Random Sequences……Page 249
A Criterion for the Existence of Predictive Complexity for Binary Games……Page 264
Full Information Game with Gains and Losses……Page 279
Prediction with Expert Advice by Following the Perturbed Leader for General Weights……Page 294
On the Convergence Speed of MDL Predictions for Bernoulli Sequences……Page 309
Relative Loss Bounds and Polynomial-Time Predictions for the K-LMS-NET Algorithm……Page 324
On the Complexity of Working Set Selection……Page 339
Convergence of a Generalized Gradient Selection Approach for the Decomposition Method……Page 353
Newton Diagram and Stochastic Complexity in Mixture of Binomial Distributions……Page 365
Learnability of Relatively Quantified Generalized Formulas……Page 380
Learning Languages Generated by Elementary Formal Systems and Its Application to SH Languages……Page 395
New Revision Algorithms……Page 410
The Subsumption Lattice and Query Learning……Page 425
Learning of Ordered Tree Languages with Height-Bounded Variables Using Queries……Page 440
Learning Tree Languages from Positive Examples and Membership Queries……Page 455
Learning Content Sequencing in an Educational Environment According to Student Needs……Page 469
Statistical Learning in Digital Wireless Communications……Page 479
A BP-Based Algorithm for Performing Bayesian Inference in Large Perceptron-Type Networks……Page 494
Approximate Inference in Probabilistic Models……Page 509
Author Index……Page 520