Algorithmic Learning Theory

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithmic Learning Theory, ALT '96, held in Sydney, Australia, in October 1996.
The 16 revised full papers presented were selected from 41 submissions; also included are eight short papers as well as four full length invited contributions by Ross Quinlan, Takeshi Shinohara, Leslie Valiant, and Paul Vitanyi, and an introduction by the volume editors. The book covers all areas related to algorithmic learning theory, ranging from theoretical foundations of machine learning to applications in several areas.

Managing complexity in neuroidal circuits.- Learnability of exclusive-or expansion based on monotone DNF formulas.- Improved bounds about on-line learning of smooth functions of a single variable.- Query learning of bounded-width OBDDs.- Learning a representation for optimizable formulas.- Limits of exact algorithms for inference of minimum size finite state machines.- Genetic fitness optimization using rapidly mixing Markov chains.- The kindest cut: Minimum message length segmentation.- Reducing complexity of decision trees with two variable tests.- The complexity of exactly learning algebraic concepts.- Efficient learning of real time two-counter automata.- Cost-sensitive feature reduction applied to a hybrid genetic algorithm.- Effects of Feature Selection with 'Blurring' on neurofuzzy systems.- Boosting first-order learning.- Incorporating hypothetical knowledge into the process of inductive synthesis.- Induction of Constraint Logic Programs.- Constructive learning of translations based on dictionaries.- Inductive logic programming beyond logical implication.- Noise elimination in inductive concept learning: A case study in medical diagnosis.- MML estimation of the parameters of the spherical fisher distribution.- Learning by erasing.- On learning and co-learning of minimal programs.- Inductive inference of unbounded unions of pattern languages from positive data.- A class of prolog programs inferable from positive data.- Vacillatory and BC learning on noisy data.- Transformations that preserve learnability.- Probabilistic limit identification up to "small" sets.- Reflecting inductive inference machines and its improvement by therapy.