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

摘要: We describe a polynomial-time algorithm for learning axis-aligned rectangles in Q^d with respect to product distributions from multiple-instance examples the PAC model. Here, each example consists of n elements together label indicating whether any points is rectangle be learned. assume that there an unknown distribution D over such all instances are independently drawn according D. The accuracy hypothesis measured by probability it would incorrectly predict one more was Our achieves e 1-δ O\left(\frac{d^5n^{12}}{\epsilon^{20}} \log^2 \frac{nd}{\epsilon\delta}\right) time.