N-learners problem: Learning Boolean combinations of halfspaces

摘要

Given two subsets S(sub 1) and S(sub 2) (not necessarily finite) of (Re)(sup d) separable by a Boolean combination of N halfspaces, we consider the problem of learning the separation function from a finite set of examples, i.e. we produce with high probability a function close to the actual separating function. Our solution consists of a system of N perceptrons and a single consolidator which combines the outputs of the individual perceptrons. We show that an off-line version of this problem, where the examples are given in a batch, can be solved in time polynomial in the number of examples. We also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of the classical perceptron learning algorithm. This solution constitutes an example of a composite system of N learners capable of accomplishing a task that is not achievable by a single learner, for a single perceptron is incapable of separating sets that are not linearly separable.