4. COLT 1991: Santa Cruz, California, USA

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

Invited Talks

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

Session 1

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

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
Manfred Opper, David Haussler:
Calculation of the Learning Curve of Bayes Optimal Classification Algorithm for Learning a Perceptron With Noise. 75-87
Paul Fischer, Stefan Pölt, Hans-Ulrich Simon:
Probably Almost Bayes Decisions. 88-94

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Session 9

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

Session 10

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

Session 11

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

Errata

Tatsuya Motoki, Takeshi Shinohara, Keith Wright:
The Correct Definition of Finite Elasticity: Corrigendum to Identification of Unions. 375

Addendum

Theodore A. Slaman, Robert Solovay:
When Oracles Do Not Help. 379-383

Last update Mon May 20 22:39:25 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page