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.
Author(s): Ray J. Solomonoff (auth.), Paul Vitányi (eds.)
Series: Lecture Notes in Computer Science 904 : Lecture Notes in Artificial Intelligence
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1995
Language: English
Pages: 422
Tags: Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages; Algorithm Analysis and Problem Complexity
The discovery of algorithmic probability: A guide for the programming of true creativity....Pages 1-22
A desicion-theoretic generalization of on-line learning and an application to boosting....Pages 23-37
Online learning versus offline learning....Pages 38-52
Learning distributions by their density levels — A paradigm for learning without a teacher....Pages 53-68
Tight worst-case loss bounds for predicting with expert advice....Pages 69-83
On-line maximum likelihood prediction with respect to general loss functions....Pages 84-98
The power of procrastination in inductive inference: How it depends on used ordinal notations....Pages 99-111
Learnability of Kolmogorov-easy circuit expressions via queries....Pages 112-124
Trading monotonicity demands versus mind changes....Pages 125-139
Learning recursive functions from approximations....Pages 140-153
On the intrinsic complexity of learning....Pages 154-168
The structure of intrinsic complexity of learning....Pages 169-181
Kolmogorov numberings and minimal identification....Pages 182-195
Stochastic complexity in learning....Pages 196-210
Function learning from interpolation (extended abstract)....Pages 211-221
Approximation and learning of convex superpositions....Pages 222-236
Minimum description length estimators under the optimal coding scheme....Pages 237-251
MDL learning of unions of simple pattern languages from positive examples....Pages 252-260
A note on the use of probabilities by mechanical learners....Pages 261-271
Characterizing rational versus exponential learning curves....Pages 272-286
Is pocket algorithm optimal?....Pages 287-297
Some theorems concerning the free energy of (Un) constrained stochastic Hopfield neural networks....Pages 298-312
A space-bounded learning algorithm for axis-parallel rectangles....Pages 313-321
Learning decision lists and trees with equivalence-queries....Pages 322-336
Bounding VC-dimension for neural networks: Progress and prospects....Pages 337-341
Average case analysis of a learning algorithm for μ -DNF expressions....Pages 342-356
Learning by extended statistical queries and its relation to PAC learning....Pages 357-366
Typed pattern languages and their learnability....Pages 367-379
Learning behaviors of automata from shortest counterexamples....Pages 380-391
Learning of regular expressions by pattern matching....Pages 392-403
The query complexity of learning some subclasses of context-free grammars....Pages 404-414
