Proceedings of the second annual Workshop on Computational Learning Theory : University of California, Santa Cruz, July 31- August 2, 1989

Computational Learning Theory presents the theoretical issues in machine learning and computational models of learning. This book covers a wide range of problems in concept learning, inductive inference, and pattern recognition. Organized into three parts encompassing 32 chapters, this book begins with an overview of the inductive principle based on weak convergence of probability measures. This text then examines the framework for constructing learning algorithms. Other chapters consider the formal theory of learning, which is learning in the sense of improving computational efficiency as opposed to concept learning. This book discusses as well the informed parsimonious (IP) inference that generalizes the compatibility and weighted parsimony techniques, which are most commonly applied in biology. The final chapter deals with the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be given in each and the goal of the learner is to make some mistakes. This book is a valuable resource for students and teachers. Content: Front Matter, Page i Copyright, Page ii Foreword, Pages v-vi, Ron Rivest, David Haussler, Manfred Warmuth Inductive Principles of the Search for Empirical Dependences (Methods Based on Weak Convergence of Probability Measures), Pages 3-21, V.N. Vapnik Polynomial Learnability of Semilinear Sets, Pages 25-40, Naoki Abe LEARNING NESTED DIFFERENCES OF INTERSECTION-CLOSED CONCEPT CLASSES, Pages 41-56, David Helmbold, Robert Sloan, Manfred K. Warmuth A Polynomial-time Algorithm for Learning k-variable Pattern Languages from Examples, Pages 57-71, Michael Kearns, Leonard Pitt ON LEARNING FROM EXERCISES, Pages 72-87, B.K. Natarajan On Approximate Truth, Pages 88-101, Daniel N. Osherson, Michael Stob, Scott Weinstein Informed parsimonious inference of prototypical genetic sequences, Pages 102-117, Aleksandar Milosavljević, David Haussler, Jerzy Jurka COMPLEXITY ISSUES IN LEARNING BY NEURAL NETS, Pages 118-133, Jyh-Han Lin, Jeffrey Scott Vitter Equivalence Queries and Approximate Fingerprints, Pages 134-145, Dana Angluin LEARNING READ-ONCE FORMULAS USING MEMBERSHIP QUERIES, Pages 146-161, Lisa Hellerstein, Marek Karpinski LEARNING SIMPLE DETERMINISTIC LANGUAGES, Pages 162-174, Hiroki Ishizaka Learning in the Presence of Inaccurate Information, Pages 175-188, Mark Fulk, Sanjay Jain Convergence to Nearly Minimal Size Grammars by Vacillating Learning Machines, Pages 189-199, Sanjay Jain, Arun Sharma, John Case Inductive Inference with Bounded Number of Mind Changes, Pages 200-213, Mahendran Velauthapillai LEARNING VIA QUERIES TO AN ORACLE, Pages 214-229, William I. Gasarch, Mark B. Pleszkoch LEARNING STRUCTURE FROM DATA: A SURVEY, Pages 230-244, Judea Pearl, Rina Dechter A Statistical Approach to Learning and Generalization in Layered Neural Networks, Pages 245-260, Esther Levin, Naftali Tishby, Sara A. Solla THE LIGHT BULB PROBLEM, Pages 261-268, Ramamohan Paturi, Sanguthevar Rajasekaran, John Reif From On-line to Batch Learning, Pages 269-284, Nick Littlestone A PARAMETRIZATION SCHEME FOR CLASSIFYING MODELS OF LEARNABILITY, Pages 285-302, Shai Ben-David, Gyora M. Benedek, Yishay Mansour On the Role of Search for Learning, Pages 303-311, Stuart A. Kurtz, Carl H. Smith ELEMENTARY FORMAL SYSTEM AS A UNIFYING FRAMEWORK FOR LANGUAGE LEARNING, Pages 312-327, Setsuo Arikawa, Takeshi Shinohara, Akihiro Yamamoto IDENTIFICATION OF UNIONS OF LANGUAGES DRAWN FROM AN IDENTIFIABLE CLASS, Pages 328-333, Keith Wright INDUCTION FROM THE GENERAL TO THE MORE GENERAL, Pages 334-348, Kevin T. Kelly SPACE-BOUNDED LEARNING AND THE VAPNIK-CHERVONENKIS DIMENSION, Pages 349-364, Sally Floyd Reliable and Useful Learning, Pages 365-380, Jyrki Kivinen The Strength of Weak Learnability, Page 383, Robert E. Schapire ON THE COMPLEXITY OF LEARNING FROM COUNTEREXAMPLES, Page 384, WOLFGANG MAASS, GYÖRGY TURÁN Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results, Page 385, David Haussler A Theory of Learning Simple Concepts Under Simple Distributions, Page 386, Ming Li, Paul M.B. Vitanyi Learning Binary Relations and Total Orders, Page 387, Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire The Weighted Majority Algorithm, Page 388, Nick Littlestone, Manfred K. Warmuth Author Index, Page 389