PAC LEARNING AXIS-ALIGNED RECTANGLES WITH RESPECT TO PRODUCT DISTRIBUTIONS FROM MULTIPLE-INSTANCE EXAMPLES

We describe a polynomial-time algorithm for learning axis-aligned rect angles in Q(d) with respect to product distributions from multiple-ins tance examples in the PAC model. Here, each example consists of n elem ents of Q(d) together with a label indicating whether any of the n poi nts is in the rectangle to be learned. We assume that there is an unkn own product distribution D over Q(d) such that all instances are indep endently drawn according to D. The accuracy of a hypothesis is measure d by the probability that it would incorrectly predict whether one of n more points drawn from D was in the rectangle to be learned. Our alg orithm achieves accuracy epsilon with probability 1 - delta in O(d(5)n (12)/epsilon(20)log(2)nd/epsilon delta) time.