8. COLT 1995: Santa Cruz, California, USA

Proceedings of the Eigth Annual Conference on Computational Learning Theory (COLT 1995), Santa Cruz, California, USA. ACM, 1995, ISBN 0-89791-723-5

Invited Talks

Leslie G. Valiant:
Rationality. 3-14
Electronic Edition (ACM DL) BibTeX
Terrence J. Sejnowski, Peter Dayan, P. Read Montague:
Predictive Hebbian Learning. 15-18
Electronic Edition (ACM DL) BibTeX

Session 1

Michael J. Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron:
An Experimental and Theoretical Comparison of Model Selection Methods. 21-30
Electronic Edition (ACM DL) BibTeX
Dana Ron, Yoram Singer, Naftali Tishby:
On the Learnability and Usage of Acyclic Probabilistic Finite Automata. 31-40
Electronic Edition (ACM DL) BibTeX
Yoav Freund, Dana Ron:
Learning to Model Sequences Generated by Switching Distributions. 41-50
Electronic Edition (ACM DL) BibTeX

Session 2

V. G. Vovk:
A Game of Prediction with Expert Advice. 51-60
Electronic Edition (ACM DL) BibTeX
David P. Helmbold, Robert E. Schapire:
Predicting Nearly as Well as the Best Pruning of a Decision Tree. 61-68
Electronic Edition (ACM DL) BibTeX
David P. Helmbold, Yoram Singer, Robert E. Schapire, Manfred K. Warmuth:
A Comparison of New and Old Algorithms for a Mixture Estimation Problem. 69-78
Electronic Edition (ACM DL) BibTeX
Nader H. Bshouty:
A Note on Learning Multivariate Polynomials Under the Uniform Distribution (Extended Abstract). 79-82
Electronic Edition (ACM DL) BibTeX
Kenji Yamanishi:
Randomized Approximate Aggregating Strategies and Their Applications to Prediction and Discrimination. 83-90
Electronic Edition (ACM DL) BibTeX
Olga Mitina, Nikolai K. Vereshchagin:
How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown. 91-97
Electronic Edition (ACM DL) BibTeX

Session 3

Avrim Blum, Prasad Chalasani, Sally A. Goldman, Donna K. Slonim:
Learning with Unreliable Boundary Queries. 98-107
Electronic Edition (ACM DL) BibTeX
Tibor Hegedüs:
Generalized Teaching Dimensions and the Query Complexity of Learning. 108-117
Electronic Edition (ACM DL) BibTeX
Nader H. Bshouty, Jeffrey C. Jackson:
Learning DNF over the Uniform Distribution using a Quantum Example Oracle. 118-127
Electronic Edition (ACM DL) BibTeX
Yiqun Lisa Yin:
Reducing the Number of Queries in Self-Directed Learning. 128-135
Electronic Edition (ACM DL) BibTeX
Shai Ben-David, Nadav Eiron, Eyal Kushilevitz:
On Self-Directed Learning. 136-143
Electronic Edition (ACM DL) BibTeX
Ronald L. Rivest, Yiqun Lisa Yin:
Being Taught can be Faster than Asking Questions. 144-151
Electronic Edition (ACM DL) BibTeX

Session 4

William I. Gasarch, Geoffrey R. Hird:
Reductions for Learning via Queries. 152-161
Electronic Edition (ACM DL) BibTeX
Frank Stephan:
Learning via Queries and Oracles. 162-169
Electronic Edition (ACM DL) BibTeX
Kalvis Apsitis, Rusins Freivalds, Carl H. Smith:
On the Inductive Inference of Real Valued Functions. 170-177
Electronic Edition (ACM DL) BibTeX
Douglas A. Cenzer, William R. Moser:
Inductive Inference of Functions on the Rationals. 178-181
Electronic Edition (ACM DL) BibTeX
Efim B. Kinber, Frank Stephan:
Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity (Extended Abstract). 182-189
Electronic Edition (ACM DL) BibTeX
Nader H. Bshouty, Christino Tamon, David K. Wilson:
On Learning Decision Trees with Large Output Domains (Extended Abstract). 190-197
Electronic Edition (ACM DL) BibTeX
Nader H. Bshouty, Zhixiang Chen, Scott E. Decatur, Steven Homer:
On the Learnability of Z_n-DNF Formulas (Extended Abstract). 198-205
Electronic Edition (ACM DL) BibTeX
Yoshifumi Sakai, Eiji Takimoto, Akira Maruoka:
Proper Learning Algorithm for Functions of k Terms Under Smooth Distributions. 206-213
Electronic Edition (ACM DL) BibTeX
Atsuyoshi Nakamura, Naoki Abe:
On-line Learning of Binary and n-ary Relations over Multi-dimensional Clusters. 214-221
Electronic Edition (ACM DL) BibTeX
H. David Mathias:
DNF - If You Can't Learn'em, Teach'em: An Interactive Model of Teaching. 222-229
Electronic Edition (ACM DL) BibTeX

Session 5

Eric B. Baum, Dan Boneh, Charles Garrett:
On Genetic Algorithms. 230-239
Electronic Edition (ACM DL) BibTeX
Jeong Han Kim, James R. Roche:
On the Optimal Capacity of Binary Neural Networks: Rigorous Combinatorial Approaches. 240-249
Electronic Edition (ACM DL) BibTeX
Norbert Klasner, Hans-Ulrich Simon:
From Noise-Free to Noise-Tolerant and from On-line to Batch Learning. 250-257
Electronic Edition (ACM DL) BibTeX
John Shawe-Taylor:
Sample Sizes for Sigmoidal Neural Networks. 258-264
Electronic Edition (ACM DL) BibTeX
Kim L. Blackmore, Robert C. Williamson, Iven M. Y. Mareels, William A. Sethares:
Online Learning via Congregational Gradient Descent. 265-272
Electronic Edition (ACM DL) BibTeX
Changfeng Wang, Santosh S. Venkatesh:
Criteria for Specifying Machine Complexity in Learning. 273-280
Electronic Edition (ACM DL) BibTeX
Lawrence K. Saul, Satinder P. Singh:
Markov Decision Processes in Large State Spaces. 281-288
Electronic Edition (ACM DL) BibTeX
Jyrki Kivinen, Manfred K. Warmuth:
The Perceptron Algorithm vs. Winnow: Linear vs. Logarithmic Mistake Bounds when few Input Variables are Relevant. 289-296
Electronic Edition (ACM DL) BibTeX
Kukjin Kang, Jong-Hoon Oh:
Learning by a Population of Perceptrons. 297-300
Electronic Edition (ACM DL) BibTeX

Session 6

Roni Khardon, Dan Roth:
Learning to Reason with a Restricted View. 301-310
Electronic Edition (ACM DL) BibTeX
Jonathan Baxter:
Learning Internal Representations. 311-320
Electronic Edition (ACM DL) BibTeX
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh:
Piecemeal Graph Exploration by a Mobile Robot (Extended Abstract). 321-328
Electronic Edition (ACM DL) BibTeX
David P. Dobkin, Dimitrios Gunopulos:
Concept Learning with Geometric Hypotheses. 329-336
Electronic Edition (ACM DL) BibTeX
Paul Fischer:
More or Less Efficient Agnostic Learning of Convex Polygons. 337-344
Electronic Edition (ACM DL) BibTeX
Nader H. Bshouty, Sally A. Goldman, H. David Mathias:
Noise-Tolerant Parallel Learning of Geometric Concepts. 345-352
Electronic Edition (ACM DL) BibTeX
Scott E. Decatur, Rosario Gennaro:
On Learning from Noisy and Incomplete Examples. 353-360
Electronic Edition (ACM DL) BibTeX
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
On Learning Bounded-Width Branching Programs. 361-368
Electronic Edition (ACM DL) BibTeX
Wee Sun Lee, Peter L. Bartlett, Robert C. Williamson:
On Efficient Agnostic Learning of Linear Combinations of Basis Functions. 369-376
Electronic Edition (ACM DL) BibTeX
Dale Schuurmans, Russell Greiner:
Sequential PAC Learning. 377-384
Electronic Edition (ACM DL) BibTeX
Michael P. Perrone, Brian S. Blais:
Regression NSS: An Alternative to Cross Validation. 385-391
Electronic Edition (ACM DL) BibTeX

Session 7

Peter L. Bartlett, Philip M. Long:
More Theorems about Scale-sensitive Dimensions and Learning. 392-401
Electronic Edition (ACM DL) BibTeX
David Haussler, Manfred Opper:
General Bounds on the Mutual Information Between a Parameter and n Conditionally Independent Observations. 402-411
Electronic Edition (ACM DL) BibTeX
Joel Ratsaby, Santosh S. Venkatesh:
Learning from a Mixture of Labeled and Unlabeled Examples with Parametric Side Information. 412-417
Electronic Edition (ACM DL) BibTeX
Dan Boneh:
Learning Using Group Representations (Extended Abstract). 418-426
Electronic Edition (ACM DL) BibTeX

Session 8

Dana Ron, Ronitt Rubinfeld:
Exactly Learning Automata with Small Cover Time. 427-436
Electronic Edition (ACM DL) BibTeX
Javed A. Aslam, Scott E. Decatur:
Specification and Simulation of Statistical Query Algorithms for Efficiency and Noise Tolerance. 437-446
Electronic Edition (ACM DL) BibTeX
Nader H. Bshouty:
Simple Learning Algorithms Using Divide and Conquer. 447-453
Electronic Edition (ACM DL) BibTeX
Shai Ben-David, Leonid Gurvits:
A Note on VC-Dimension and Measures of Sets of Reals. 454-462
Electronic Edition (ACM DL) BibTeX

Corrigendum

William W. Cohen, Haym Hirsh: Corrigendum for ``Learnability of Description Logics''. 463 BibTeX