Learning in Parallel
View/ Open
Issue Date
1992Author
Vitter, Jeffrey Scott
Lin, Jyh-Han
Publisher
Elsevier
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
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.
Collections
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
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.