PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples

P. M. Long and L. Tan. PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Machine Learning, 30(1):7-22, 1998.

(Available in Postscript and PDF formats.)

Abstract
We describe a polynomial-time algorithm for learning axis-aligned rectangles with respect to product distributions from multiple-instance examples in the PAC model. Here, each example consists of n domain elements together with a label indicating whether any of the points is in the rectangle to be learned.