4. COLT 1991: Santa Cruz, California, USA

Leslie G. Valiant, Manfred K. Warmuth (Eds.): Proceedings of the Fourth Annual Workshop on Computational Learning Theory (COLT 1991), Santa Cruz, California, USA. Morgan Kaufmann, 1991, ISBN 1-55860-213-5

Invited Talks

Thomas M. Cover:
Learning and Generalization.(Abstract). 3
Electronic Edition (link) BibTeX
Rodney A. Brooks:
The Role of Learning in Autonomous Robots. 5-10
Electronic Edition (link) BibTeX

Session 1

David P. Helmbold, Philip M. Long:
Tracking Drifting Concepts Using Random Examples. 13-23
Electronic Edition (link) BibTeX
Peter L. Bartlett, Robert C. Williamson:
Investigating the Distribution Assumptions in the Pac Learning Model. 24-32
Electronic Edition (link) BibTeX
Kevin Buescher, P. R. Kumar:
Simultaneous Learning of Concepts and Simultaneous Estimation of Probabilities. 33-42
Electronic Edition (link) BibTeX
Woonkyung Michael Kim:
Learning by Smoothing: A Morphological Approach. 43-57
Electronic Edition (link) BibTeX

Session 2

David Haussler, Michael J. Kearns, Robert E. Schapire:
Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension. 61-74
Electronic Edition (link) BibTeX
Manfred Opper, David Haussler:
Calculation of the Learning Curve of Bayes Optimal Classification Algorithm for Learning a Perceptron With Noise. 75-87
Electronic Edition (link) BibTeX
Paul Fischer, Stefan Pölt, Hans-Ulrich Simon:
Probably Almost Bayes Decisions. 88-94
Electronic Edition (link) BibTeX

Session 4

Vwani P. Roychowdhury, Kai-Yeung Siu, Alon Orlitsky, Thomas Kailath:
A Geometric Approach to Threshold Circuit Complexity. 97-111
Electronic Edition (link) BibTeX
H. Sebastian Seung, Haim Sompolinsky, Naftali Tishby:
Learning Curves in Large Neural Networks. 112-127
Electronic Edition (link) BibTeX
Oded Maler, Amir Pnueli:
On the Learnability of Infinitary Regular Sets. 128-136
Electronic Edition (link) BibTeX

Session 5

Dana Angluin, Donna K. Slonim:
Learning Monotone DNF with an Incomplete Membership Oracle. 139-146
Electronic Edition (link) BibTeX
Nick Littlestone:
Redundant Noisy Attributes, Attribute Errors, and Linear-Threshold Learning Using Winnow. 147-156
Electronic Edition (link) BibTeX
Avrim Blum, Lisa Hellerstein, Nick Littlestone:
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. 157-166
Electronic Edition (link) BibTeX
Wolfgang Maass:
On-Line Learning with an Oblivious Environment and the Power of Randomization. 167-175
Electronic Edition (link) BibTeX

Session 6

Thomas R. Hancock, Yishay Mansour:
Learning Monotone kµ DNF Formulas on Product Distributions. 179-183
Electronic Edition (link) BibTeX
Robert E. Schapire:
Learning Probabilistic Read-Once Formulas on Product Distributions. 184-198
Electronic Edition (link) BibTeX
Thomas R. Hancock:
Learning 2µ DNF Formulas and kµ Decision Trees. 199-209
Electronic Edition (link) BibTeX

Session 7

Takashi Yokomori:
Polynomial-Time Learning of Very Simple Grammars from Positive Data. 213-227
Electronic Edition (link) BibTeX
Robert P. Daley, Leonard Pitt, Mahendran Velauthapillai, Todd Will:
Relations Between Probabilistic and Team One-Shot Learners (Extended Abstract). 228-239
Electronic Edition (link) BibTeX

Session 9

Andrew R. Barron:
Approximation and Estimation Bounds for Artificial Neural Networks. 243-249
Electronic Edition (link) BibTeX
Chuanyi Ji, Demetri Psaltis:
The VC-Dimension vs. the Statistical Capacity for Two Layer Networks with Binary Weights. 250-256
Electronic Edition (link) BibTeX
Santosh S. Venkatesh:
On Learning Binary Weights for Majority Functions. 257-266
Electronic Edition (link) BibTeX
Andrew B. Nobel:
Evaluating the Performance of a Simple Inductive Procedure in the Presence of Overfitting Error. 267-274
Electronic Edition (link) BibTeX

Session 10

Naoki Abe, Manfred K. Warmuth, Jun-ichi Takeuchi:
Polynomial Learnability of Probabilistic Concepts with Respect to the Kullback-Leibler Divergence. 277-289
Electronic Edition (link) BibTeX
Kenji Yamanishi:
A Loss Bound Model for On-Line Stochastic Prediction Strategies. 290-302
Electronic Edition (link) BibTeX
Sally A. Goldman, Michael J. Kearns:
On the Complexity of Teaching. 303-314
Electronic Edition (link) BibTeX

Session 11

Merrick L. Furst, Jeffrey C. Jackson, Sean W. Smith:
Improved Learning of AC⁰ Functions. 317-325
Electronic Edition (link) BibTeX
Thomas R. Hancock, Lisa Hellerstein:
Learning Read-Once Formulas over Fields and Extended Bases. 326-336
Electronic Edition (link) BibTeX
William J. Bultman, Wolfgang Maass:
Fast Identification of Geometric Objects with Membership Queries. 337-353
Electronic Edition (link) BibTeX
Vijay Raghavan:
Bounded Degree Graph Inference from Walks. 354-366
Electronic Edition (link) BibTeX
Tao Jiang, Ming Li:
On the Complexity of Learning Strings and Sequences. 367-371
Electronic Edition (link) BibTeX

Errata

Tatsuya Motoki, Takeshi Shinohara, Keith Wright:
The Correct Definition of Finite Elasticity: Corrigendum to Identification of Unions. 375
Electronic Edition (link) BibTeX

Addendum

Theodore A. Slaman, Robert Solovay:
When Oracles Do Not Help. 379-383
Electronic Edition (link) BibTeX