Loading...
Learning in Parallel
Vitter, Jeffrey Scott Lin, Jyh-Han
Vitter, Jeffrey Scott
Lin, Jyh-Han
Citations
Altmetric:
Abstract
In this paper, we extend Valiant's sequential model of concept learning from
examples [Valiant 1984] and introduce models for the e cient learning of concept classes
from examples in parallel. We say that a concept class is NC-learnable if it can be learned
in polylog time with a polynomial number of processors. We show that several concept
classes which are polynomial-time learnable are NC-learnable in constant time. Some other
classes can be shown to be NC-learnable in logarithmic time, but not in constant time.
Our main result shows that other classes, such as s-fold unions of geometrical objects in
Euclidean space, which are polynomial-time learnable by a greedy set cover technique,
are NC-learnable using a non-greedy technique. We also show that (unless P RNC)
several polynomial-time learnable concept classes related to linear programming are not
NC-learnable. Equivalence of various parallel learning models and issues of fault-tolerance
are also discussed.
Description
Date
1992
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Files
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
J. S. Vitter and J.-H. Lin. “Learning in Parallel,” Information and Computation, 92(2), February 1992, 179–202. An extended abstract appears in Proceedings of the 1st Annual ACM Workshop on Computational Learning Theory (COLT ’88), Cambridge, MA, August 1988, published by Morgan Kaufmann, San Mateo, CA, 106–124. http://dx.doi.org/10.1016/0890-5401(92)90047-J