Goldberg, Paul W. (2000) When can two unsupervised learners achieve PAC separation? University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-377.pdf - Other - Requires a PDF viewer. Download (341Kb) | Preview

Request Changes to record.

Abstract

In this paper we introduce a new framework for studying PAC learning problems, that has practical as well as theoretical motivations. In our framework the training examples are divided into the two sets associated with the two possible output labels, and each set is sent to a separate (unsupervised) learner. The two learners must independently fit probability distributions to their examples, and afterwards these distributions are combined to form a hypothesis by labeling test data according to maximum likelihood. That is, the output label for any input would be the one associated with the unsupervised learner that gave that input the higher probability. This approach is motived by the observation that PAC learning algorithms of this kind are extendable in a natural way to multi-class classification. It also turns out to introduce new algorithmic challenges, even for very simple concept classes. Learning may be viewed as a cooperative game between two players, for which we must design a strategy that they will both use. 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 for which there is a constant upper bound on the number of relevant attributes. We give an algorithm for learning monomials subject to the assumption that the input distribution is a 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:	Report
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Computer-assisted instruction
Series Name:	Department of Computer Science Research Report
Publisher:	University of Warwick. Department of Computer Science
Official Date:	1 November 2000
Dates:	Date Event 1 November 2000 Published
Number:	Number 377
Number of Pages:	17
DOI:	CS-RR-377
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads