Proceedings of the Second Annual Workshop on Computational Learning Theory

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