Relations Between Probabilistic and Team One-Shot Learners (Extended Abstract)

Abstract

A typical way to increase the power of a learning paradigm is to allow randomization and require successful learning only with some probability p. Another standard approach is to allow a team of s learners working in parallel and to demand only that at least r of them correctly learn. These two variants are compared for the model of learning of total recursive functions where the learning algorithm is allowed an unbounded but finite amount of computation, and must halt with a correct program after receiving only a finite number of values of the function to be learned. For any p, the minimum number n is determined such that any function that can be learned with probability p can be learned by at least one member of a team of n learning algorithms. This result is a special case of more general theorems that exactly determine the relationships between probabilistic learning with probability p > 1/2, and learning by a team of r out of s when r/s > 1/2 For the case when r/s < 1/2, many new interesting consequences are given. The power of redundancy for team learning is investigated, and new techniques are developed for comparing the relative power of r out of s learners with kr out of ks learners.