Computational Learning Theory

1. Front Matter

   PDF

2. The discovery of algorithmic probability: A guide for the programming of true creativity

   • Ray J. Solomonoff

   Pages 1-22

3. A desicion-theoretic generalization of on-line learning and an application to boosting

   • Yoav Freund, Robert E. Schapire

   Pages 23-37

4. Online learning versus offline learning

   • Shai Ben-David, Eyal Kushilevitz, Yishay Mansour

   Pages 38-52

5. Learning distributions by their density levels — A paradigm for learning without a teacher

   • Shai Ben-David, Michael Lindenbaum

   Pages 53-68

6. Tight worst-case loss bounds for predicting with expert advice

   • David Haussler, Jyrki Kivinen, Manfred K. Warmuth

   Pages 69-83

7. On-line maximum likelihood prediction with respect to general loss functions

   • Kenji Yamanishi

   Pages 84-98

8. The power of procrastination in inductive inference: How it depends on used ordinal notations

   • Andris Ambainis

   Pages 99-111

9. Learnability of Kolmogorov-easy circuit expressions via queries

   • José L. Balcázar, Harry Buhrman, Montserrat Hermo

   Pages 112-124

10. Trading monotonicity demands versus mind changes

    • Steffen Lange, Thomas Zeugmann

    Pages 125-139

11. Learning recursive functions from approximations

    • John Case, Susanne Kaufmann, Efim Kinber, Martin Kummer

    Pages 140-153

12. On the intrinsic complexity of learning

    • Rūsiņš Freivalds, Efim Kinber, Carl H. Smith

    Pages 154-168

13. The structure of intrinsic complexity of learning

    • Sanjay Jain, Arun Sharma

    Pages 169-181

14. Kolmogorov numberings and minimal identification

    • Rusins Freivalds, Sanjay Jain

    Pages 182-195

15. Stochastic complexity in learning

    • J. Rissanen

    Pages 196-210

16. Function learning from interpolation (extended abstract)

    • Martin Anthony, Peter Bartlett

    Pages 211-221

17. Approximation and learning of convex superpositions

    • Leonid Gurvits, Pascal Koiran

    Pages 222-236

18. Minimum description length estimators under the optimal coding scheme

    • V. G. Vovk

    Pages 237-251

19. MDL learning of unions of simple pattern languages from positive examples

    • Pekka Kilpeläinen, Heikki Mannila, Esko Ukkonen

    Pages 252-260

20. A note on the use of probabilities by mechanical learners

    • Eric Martin, Daniel Osherson

    Pages 261-271

This volume presents the proceedings of the Second European Conference on Computational Learning Theory (EuroCOLT '95), held in Barcelona, Spain in March 1995.
The book contains full versions of the 28 papers accepted for presentation at the conference as well as three invited papers. All relevant topics in fundamental studies of computational aspects of artificial and natural learning systems and machine learning are covered; in particular artificial and biological neural networks, genetic and evolutionary algorithms, robotics, pattern recognition, inductive logic programming, decision theory, Bayesian/MDL estimation, statistical physics, and cryptography are addressed.

• Algorithms
• algorithm
• evolutionary algorithm
• learning
• learning theory
• logic
• machine learning
• programming
• robot
• robotics
• algorithm analysis and problem complexity

Policies and ethics