Algorithmic Learning Theory: 13th International Conference, ALT 2002 Lübeck, Germany, November 24–26, 2002 Proceedings

Nicolò Cesa-Bianchi, Masayuki Numao, Rüdiger Reischuk (eds.)3540001700, 9783540001706

This volume contains the papers presented at the 13th Annual Conference on Algorithmic Learning Theory (ALT 2002), which was held in Lub ¨ eck (Germany) during November 24–26, 2002. The main objective of the conference was to p- vide an interdisciplinary forum discussing the theoretical foundations of machine learning as well as their relevance to practical applications. The conference was colocated with the Fifth International Conference on Discovery Science (DS 2002). The volume includes 26 technical contributions which were selected by the program committee from 49 submissions. It also contains the ALT 2002 invited talks presented by Susumu Hayashi (Kobe University, Japan) on “Mathematics Based on Learning”, by John Shawe-Taylor (Royal Holloway University of L- don, UK) on “On the Eigenspectrum of the Gram Matrix and Its Relationship to the Operator Eigenspectrum”, and by Ian H. Witten (University of Waikato, New Zealand) on “Learning Structure from Sequences, with Applications in a Digital Library” (joint invited talk with DS 2002). Furthermore, this volume – cludes abstracts of the invited talks for DS 2002 presented by Gerhard Widmer (Austrian Research Institute for Arti?cial Intelligence, Vienna) on “In Search of the Horowitz Factor: Interim Report on a Musical Discovery Project” and by Rudolf Kruse (University of Magdeburg, Germany) on “Data Mining with Graphical Models”. The complete versions of these papers are published in the DS 2002 proceedings (Lecture Notes in Arti?cial Intelligence, Vol. 2534). ALT has been awarding the E.

---

Table of contents :
Editors’ Introduction….Pages 1-6
Mathematics Based on Learning….Pages 7-21
Data Mining with Graphical Models….Pages 22-22
On the Eigenspectrum of the Gram Matrix and Its Relationship to the Operator Eigenspectrum….Pages 23-40
In Search of the Horowitz Factor: Interim Report on a Musical Discovery Project….Pages 41-41
Learning Structure from Sequences, with Applications in a Digital Library….Pages 42-56
Consistency Queries in Information Extraction….Pages 173-187
Ordered Term Tree Languages which Are Polynomial Time Inductively Inferable from Positive Data….Pages 188-202
Reflective Inductive Inference of Recursive Functions….Pages 203-217
Classes with Easily Learnable Subclasses….Pages 218-232
On the Learnability of Vector Spaces….Pages 233-247
On Learning Monotone Boolean Functions under the Uniform Distribution….Pages 57-68
On Learning Embedded Midbit Functions….Pages 69-82
Maximizing Agreements and CoAgnostic Learning….Pages 83-97
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning….Pages 98-112
Large Margin Classification for Moving Targets….Pages 113-127
On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution….Pages 128-138
A General Dimension for Approximately Learning Boolean Functions….Pages 139-148
The Complexity of Learning Concept Classes with Polynomial General Dimension….Pages 149-163
On the Absence of Predictive Complexity for Some Games….Pages 164-172
RBF Neural Networks and Descartes’ Rule of Signs….Pages 321-335
Asymptotic Optimality of Transductive Confidence Machine….Pages 336-350
An Efficient PAC Algorithm for Reconstructing a Mixture of Lines….Pages 351-364
Constraint Classification: A New Approach to Multiclass Classification….Pages 365-379
How to Achieve Minimax Expected Kullback-Leibler Distance from an Unknown Finite Distribution….Pages 380-394
Classification with Intersecting Rules….Pages 395-402
Feedforward Neural Networks in Reinforcement Learning Applied to High-Dimensional Motor Control….Pages 403-413
Learning, Logic, and Topology in a Common Framework….Pages 248-262
A Pathology of Bottom-Up Hill-Climbing in Inductive Rule Learning….Pages 263-277
Minimised Residue Hypotheses in Relevant Logic….Pages 278-292
Compactness and Learning of Classes of Unions of Erasing Regular Pattern Languages….Pages 293-307
A Negative Result on Inductive Inference of Extended Pattern Languages….Pages 308-320