COLT '91 - 1st Edition - ISBN: 9781558602137, 9781483299143

COLT '91

1st Edition

Proceedings of the Fourth Annual Workshop, UC Santa Cruz, California, August 5-7, 1991

Editors: COLT
eBook ISBN: 9781483299143
Imprint: Morgan Kaufmann
Published Date: 1st July 1991
Page Count: 371
Tax/VAT will be calculated at check-out Price includes VAT (GST)
Price includes VAT (GST)
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


COLT '91: Proceedings of the Fourth Annual Workshop on Computational Learning Theory covers the papers presented at the Fourth Workshop on Computational Learning Theory, held at the University of California at Santa Cruz on August 5-7, 1991. The book focuses on quantitative theories of machine learning.

The selection first offers information on the role of learning in autonomous robots; tracking drifting concepts using random examples; investigating the distribution assumptions in the PAC learning model; and simultaneous learning of concepts and simultaneous estimation of probabilities.The text then examines the calculation of the learning curve of Bayes optimal classification algorithm for learning a perceptron with noise and a geometric approach to threshold circuit complexity.

The manuscript takes a look at learning curves in large neural networks, learnability of infinitary regular sets, and learning monotone DNF with an incomplete membership oracle. Topics include monotone DNF learning algorithm, difficulties in learning infinitary regular sets, learning of a perception rule, and annealed approximation. The book also examines the fast identification of geometric objects with membership queries and a loss bound model for on-line stochastic prediction strategies.

The selection is a valuable source of information for researchers interested in the computational learning theory.

Table of Contents


Invited Talks

Learning and Generalization

The Role of Learning in Autonomous Robots

Session 1: Morning, Aug 5

Tracking Drifting Concepts Using Random Examples

Investigating the Distribution Assumptions in the Pac Learning Model

Simultaneous Learning of Concepts and Simultaneous Estimation of Probabilities

Learning by Smoothing: A Morphological Approach

Session 2:

Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension

Calculation of the Learning Curve of Bayes Optimal Classification Algorithm for Learning a Perceptron with Noise

Probably Almost Bayes Decisions

Session 3: Afternoon, Aug 5

Invited Talk

Learning and Generalization

Session 4:

A Geometric Approach to Threshold Circuit Complexity

Learning Curves in Large Neural Networks

On the Learnability of Infinitary Regular Sets

Session 5: Morning, Aug 6

Learning Monotone DNF with an Incomplete Membership Oracle

Redundant Noisy Attributes, Attribute Errors, and Linear-Threshold Learning Using Winnow

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes

On-Line Learning with an Oblivious Environment and the Power of Randomization

Session 6:

Learning Monotone kμ-DNF Formulas on Product Distributions

Learning Probabilistic Read-Once Formulas on Product Distributions

Learning 2μ-DNF Formulas and kμ Decision Trees

Session 7: Afternoon, Aug 6

Invited Talk

The Role of Learning in Autonomous Robots

Session 8:

Polynomial-Time Learning of Very Simple Grammars from Positive Data

Relations Between Probabilistic and Team One-Shot Learners

When Oracles Do Not Help

Session 9: Morning, Aug 7

Approximation and Estimation Bounds for Artificial Neural Networks

The VC-Dimension Vs. the Statistical Capacity for Two Layer Networks with Binary Weights

On Learning Binary Weights for Majority Functions

Evaluating the Performance of a Simple Inductive Procedure in the Presence of Overfitting Error

Session 10:

Polynomial Learnability of Probabilistic Concepts with Respect to the Kullback-Leibler Divergence

A Loss Bound Model for On-Line Stochastic Prediction Strategies

On the Complexity of Teaching

Session 11: Afternoon, Aug 7

Improved Learning of AC0 Functions

Learning Read-Once Formulas Over Fields and Extended Bases

Fast Identification of Geometric Objects with Membership Queries

Bounded Degree Graph Inference from Walks

On the Complexity of Learning Strings and Sequences

The Correct Definition of Finite Elasticity: Corrigendum to Identification of Unions

Author Index


No. of pages:
© Morgan Kaufmann 1991
Morgan Kaufmann
eBook ISBN:

About the Editor