4. COLT 1991: Santa Cruz, California, USA

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