### Efficient distribution-free population learning of simple concepts

**Authors: Atsuyoshi Nakamura, Jun-ichi Takeuchi and Naoki Abe**.

Email: atsu@ccm.cl.nec.co.jp

**Source: ***Annals of Mathematics and Artificial Intelligence*
Vol. 23, No. 1-2, 1998, 53-82.

**Abstract.**
We consider a variant of the `population learning model' proposed by Kearns and Seung [8], in
which the learner is required to be `distribution-free' as well as computationally efficient. A
population learner receives as input hypotheses from a large population of agents and produces as
output its final hypothesis. Each agent is assumed to independently obtain labeled sample for the
target concept and output a hypothesis. A polynomial time population learner is said to PAC-learn
a concept class, if its hypothesis is probably approximately correct whenever the population size
exceeds a certain bound which is polynomial, even if the sample size for each agent is fixed at
some constant. We exhibit some general population learning strategies, and some simple concept
classes that can be learned by them. These strategies include the `supremum hypothesis finder', the
`minimum superset finder' (a special case of the `supremum hypothesis finder'), and various voting
schemes. When coupled with appropriate agent algorithms, these strategies can learn a variety of
simple concept classes, such as the `high-low game', conjunctions, axis-parallel rectangles and
others. We give upper bounds on the required population size for each of these cases, and show that
these systems can be used to obtain a speed up from the ordinary PAC-learning model [11], with
appropriate choices of sample and population sizes. With the population learner restricted to be a
voting scheme, what we have is effectively a model of `population prediction', in which the
learner is to predict the value of the target concept at an arbitrarily drawn point, as a threshold
function of the predictions made by its agents on the same point. We show that the population
learning model is strictly more powerful than the population prediction model. Finally, we
consider a variant of this model with classification noise, and exhibit a population learner for the
class of conjunctions in this model.

©Copyright 1998 Baltzer Science Publishers