Paul Goldberg, When Can Two Unsupervised Learners Achieve PAC Separation? (November 1, 2000).
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.