LEARNING SEPARATIONS BY BOOLEAN COMBINATIONS OF HALF-SPACES

Given two subsets S1 and S2 (not necessarily finite) of R(d) separable by a Boolean combination of learning halfspaces, we consider the prob lem of (in the sense of Valiant) the separation function from a finite set of examples, i.e., we produce with a high probability a function close to the actual separating function. Our solution consists of a sy stem of N perceptrons and a single consolidator which combines the out puts of the individual perceptrons. We show that an off-line version o f 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-l ine learning algorithm that incrementally solves the problem by suitab ly training a system of N perceptrons much in the spirit of the classi cal perceptron learning algorithm.