Algorithmic Learning Theory

1. Front Matter

   Pages I-XI

   PDF

2. Editors’ Introduction

   1. Editors’ Introduction

      • Naoki Abe, Roni Khardon, Thomas Zeugmann

      Pages 1-7

3. Invited Papers

   1. The Discovery Science Project in Japan

      • Setsuo Arikawa

      Pages 9-11

   2. Queries Revisited

      • Dana Angluin

      Pages 12-31

   3. Robot Baby 2001

      • Paul R. Cohen, Tim Oates, Niall Adams, Carole R. Beal

      Pages 32-56

   4. Discovering Mechanisms: A Computational Philosophy of Science Perspective

      • Lindley Darden

      Pages 57-57

   5. Inventing Discovery Tools: Combining Information Visualization with Data Mining

      • Ben Shneiderman

      Pages 58-58

4. Complexity of Learning

   1. On Learning Correlated Boolean Functions Using Statistical Queries (Extended Abstract)

      • Ke Yang

      Pages 59-76

   2. A Simpler Analysis of the Multi-way Branching Decision Tree Boosting Algorithm

      • Kohei Hatano

      Pages 77-91

   3. Minimizing the Quadratic Training Error of a Sigmoid Neuron Is Hard

      • Jiří Šíma

      Pages 92-105

5. Support Vector Machines

   1. Learning of Boolean Functions Using Support Vector Machines

      • Ken Sadohara

      Pages 106-118

   2. A Random Sampling Technique for Training Support Vector Machines

      • Jose Balcázar, Yang Dai, Osamu Watanabe

      Pages 119-134

6. New Learning Models

   1. Learning Coherent Concepts

      • Ashutosh Garg, Dan Roth

      Pages 135-150

   2. Learning Intermediate Concepts

      • Stephen S. Kwek

      Pages 151-166

   3. Real-Valued Multiple-Instance Learning with Queries

      • Daniel R. Dooly, Sally A. Goldman, Stephen S. Kwek

      Pages 167-180

7. Online Learning

   1. Loss Functions, Complexities, and the Legendre Transformation

      • Yuri Kalnishkan, Michael V. Vyugin, Volodya Vovk

      Pages 181-189

   2. Non-linear Inequalities between Predictive and Kolmogorov Complexities

      • Michael V. Vyugin, Vladimir V. V'yugin

      Pages 190-204

8. Inductive Inference

   1. Learning by Switching Type of Information

      • Sanjay Jain, Frank Stephan

      Pages 205-218

   2. Learning How to Separate

      • Sanjay Jain, Frank Stephan

      Pages 219-234

   3. Learning Languages in a Union

      • Sanjay Jain, Yen Kaow Ng, Tiong Seng Tay

      Pages 235-250

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).

• Algorithmic Learning
• Computational Learning
• Concept Learning
• Discovery Science
• Inductive Inference
• Learning Algorithms
• Machine Learning
• Neural Network Learning
• Support Vector Machine
• Support Vector Machines
• algorithmic learning theory
• algorithms
• complexity
• learning
• learning theory
• algorithm analysis and problem complexity

• IBM, Thomas J.Watson Research Center, Yorktown, USA

  Naoki Abe

• Dept.of Electrical Engineering and Computer Science, Tufts University, Medford, USA

  Roni Khardon

• Medizinische Universität zu Lübeck,Inst.für Theoretische Informatik, Lübeck, Germany

  Thomas Zeugmann

Policies and ethics