Algorithmic Learning Theory: 12th International Conference, ALT 2001 Washington, DC, USA, November 25–28, 2001 Proceedings

Naoki Abe, Roni Khardon, Thomas Zeugmann (eds.)3540428755, 9783540428756

This volume contains the papers presented at the 12th Annual Conference on Algorithmic Learning Theory (ALT 2001), which was held in Washington DC, USA, during November 25–28, 2001. The main objective of the conference is to provide an inter-disciplinary forum for the discussion of theoretical foundations of machine learning, as well as their relevance to practical applications. The conference was co-located with the Fourth International Conference on Discovery Science (DS 2001). The volume includes 21 contributed papers. These papers were selected by the program committee from 42 submissions based on clarity, signi?cance, o- ginality, and relevance to theory and practice of machine learning. Additionally, the volume contains the invited talks of ALT 2001 presented by Dana Angluin of Yale University, USA, Paul R. Cohen of the University of Massachusetts at Amherst, USA, and the joint invited talk for ALT 2001 and DS 2001 presented by Setsuo Arikawa of Kyushu University, Japan. Furthermore, this volume includes abstracts of the invited talks for DS 2001 presented by Lindley Darden and Ben Shneiderman both of the University of Maryland at College Park, USA. The complete versions of these papers are published in the DS 2001 proceedings (Lecture Notes in Arti?cial Intelligence Vol. 2226).

---

Table of contents :
Editors’ Introduction….Pages 1-7
The Discovery Science Project in Japan….Pages 9-11
Queries Revisited….Pages 12-31
Robot Baby 2001….Pages 32-56
Discovering Mechanisms: A Computational Philosophy of Science Perspective….Pages 57-57
Inventing Discovery Tools: Combining Information Visualization with Data Mining….Pages 58-58
On Learning Correlated Boolean Functions Using Statistical Queries (Extended Abstract)….Pages 59-76
A Simpler Analysis of the Multi-way Branching Decision Tree Boosting Algorithm….Pages 77-91
Minimizing the Quadratic Training Error of a Sigmoid Neuron Is Hard….Pages 92-105
Learning of Boolean Functions Using Support Vector Machines….Pages 106-118
A Random Sampling Technique for Training Support Vector Machines….Pages 119-134
Learning Coherent Concepts….Pages 135-150
Learning Intermediate Concepts….Pages 151-166
Real-Valued Multiple-Instance Learning with Queries….Pages 167-180
Loss Functions, Complexities, and the Legendre Transformation….Pages 181-189
Non-linear Inequalities between Predictive and Kolmogorov Complexities….Pages 190-204
Learning by Switching Type of Information….Pages 205-218
Learning How to Separate….Pages 219-234
Learning Languages in a Union….Pages 235-250
On the Comparison of Inductive Inference Criteria for Uniform Learning of Finite Classes….Pages 251-266
Refutable Language Learning with a Neighbor System….Pages 267-282
Learning Recursive Functions Refutably….Pages 283-298
Refuting Learning Revisited….Pages 299-314
Efficient Learning of Semi-structured Data from Queries….Pages 315-331
Extending Elementary Formal Systems….Pages 332-347
Learning Regular Languages Using RFSA….Pages 348-363
Inference of ω-Languages from Prefixes….Pages 364-377