Algorithmic Learning Theory: 10th International Conference, ALT '99 Tokyo, Japan, December 6-8, 1999 Proceedings(Lecture Notes in Artificial Intelligence)

ThisvolumecontainsallthepaperspresentedattheInternationalConferenceon Algorithmic Learning Theory 1999 (ALT'99), held at Waseda University Int- nationalConferenceCenter,Tokyo,Japan,December 6?8,1999.Theconference was sponsored by the Japanese Society for Arti cial Intelligence (JSAI). In response to the call for papers, 51 papers on all aspects of algorithmic learning theory and related areas were submitted, of which 26 papers were - lected for presentation by the program committee based on their originality, quality, and relevance to the theory of machine learning. In addition to these regular papers, this volume contains three papers of invited lectures presented byKatharinaMorikoftheUniversityofDortmund,RobertE.SchapireofAT&T Labs, Shannon Lab., and Kenji Yamanishi of NEC, C&C Media Research Lab. ALT'99 is not just one of the ALT conference series, but this conference marks the tenth anniversary in the series that was launched in Tokyo, in Oc- ber 1990, for the discussion of research topics on all areas related to algorithmic learning theory. The ALT series was renamedlast year from\ALT workshop"to \ALT conference",expressing its wider goalof providing an ideal forum to bring together researchers from both theoretical and practical learning communities, producing novel concepts and criteria that would bene t both. This movement wasre?ectedinthepaperspresentedatALT'99,wheretherewereseveralpapers motivated by application oriented problems such as noise, data precision, etc. Furthermore, ALT'99 benet ed from being held jointly with the 2nd Inter- tional Conference on Discovery Science (DS'99), the conference for discussing, among other things, more applied aspects of machine learning. Also, we could celebrate the tenth anniversary of the ALT series with researchers from both theoretical and practical communities.

Table of Contents:
Invited Lectures.- Tailoring Representations to Different Requirements.- Theoretical Views of Boosting and Applications.- Extended Stochastic Complexity and Minimax Relative Loss Analysis.- Regular Contributions.- Algebraic Analysis for Singular Statistical Estimation.- Generalization Error of Linear Neural Networks in Unidentifiable Cases.- The Computational Limits to the Cognitive Power of the Neuroidal Tabula Rasa.- The Consistency Dimension and Distribution-Dependent Learning from Queries (Extended Abstract).- The VC-Dimension of Subclasses of Pattern Languages.- On the V ? Dimension for Regression in Reproducing Kernel Hilbert Spaces.- On the Strength of Incremental Learning.- Learning from Random Text.- Inductive Learning with Corroboration.- Flattening and Implication.- Induction of Logic Programs Based on ?-Terms.- Complexity in the Case Against Accuracy: When Building One Function-Free Horn Clause Is as Hard as Any.- A Method of Similarity-Driven Knowledge Revision for Type Specializations.- PAC Learning with Nasty Noise.- Positive and Unlabeled Examples Help Learning.- Learning Real Polynomials with a Turing Machine.- Faster Near-Optimal Reinforcement Learning: Adding Adaptiveness to the E3 Algorithm.- A Note on Support Vector Machine Degeneracy.- Learnability of Enumerable Classes of Recursive Functions from “Typical” Examples.- On the Uniform Learnability of Approximations to Non-recursive Functions.- Learning Minimal Covers of Functional Dependencies with Queries.- Boolean Formulas Are Hard to Learn for Most Gate Bases.- Finding Relevant Variables in PAC Model with Membership Queries.- General Linear Relations among Different Types of Predictive Complexity.- Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph.- On Learning Unionsof Pattern Languages and Tree Patterns.