The Library
When can two unsupervised learners achieve PAC separation?
Tools
Tools
Tools
Goldberg, Paul W. (2001) When can two unsupervised learners achieve PAC separation? In: Helmbold, D. and Williamson, B., (eds.) Computational Learning Theory. Lecture Notes in Computer Science, Volume 2111 . Springer Berlin Heidelberg, pp. 303-319. ISBN 9783540423430
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/3-540-44581-1_20
Abstract
In this paper we study a new restriction of the PAC learning framework, in which each label class is handled by an unsupervised learner that aims to fit an appropriate probability distribution to its own data. A hypothesis is derived by choosing, for any unlabeled instance, the label whose distribution assigns it the higher likelihood.
The motivation for the new learning setting is that the general approach of fitting separate distributions to each label class, is often used in practice for classification problems. The set of probability distributions that is obtained is more useful than a collection of decision boundaries. A question that arises, however, is whether it is ever more tractable (in terms of computational complexity or sample-size required) to find a simple decision boundary than to divide the problem up into separate unsupervised learning problems and find appropriate distributions.
Within the framework, we give algorithms for learning various simple geometric concept classes. In the boolean domain we show how to learn parity functions, and functions having a constant upper bound on the number of relevant attributes. These results distinguish the new setting from various other well-known restrictions of PAC-learning. We give an algorithm for learning monomials over input vectors generated by an unknown product distribution. The main open problem is whether monomials (or any other concept class) distinguish learnability in this framework from standard PAC-learnability.
| Item Type: | Book Item | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer Berlin Heidelberg | ||||
| ISBN: | 9783540423430 | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Computational Learning Theory | ||||
| Editor: | Helmbold, D. and Williamson, B. | ||||
| Official Date: | 13 September 2001 | ||||
| Dates: |
|
||||
| Volume: | Volume 2111 | ||||
| Number of Pages: | 17 | ||||
| Page Range: | pp. 303-319 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 14th Annual Conference on Computational Learning Theory (COLT 2001)/5th European Conference on Computational Learning Theory (EuroCOLT 2001) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Amsterdam, The Netherlands, | ||||
| Date(s) of Event: | 16-19 Jul 2001 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
