Nsv. Rao et al., LEARNING SEPARATIONS BY BOOLEAN COMBINATIONS OF HALF-SPACES, IEEE transactions on pattern analysis and machine intelligence, 16(7), 1994, pp. 765-768
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.