N-learners problem: Learning Boolean combinations of halfspaces
TN (United States) Oak Ridge National Lab., N Rao, DOE, DOD, NSF, USDOE, Washington, DC (United States), E Oblow, C Glover · 1992
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.