PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples
Abstract
We describe a polynomial-time algorithm for learning axis-aligned rectangles in Q^d with respect to product distributions from multiple-instance examples in the PAC model. Here, each example consists of n elements of Q^d together with a label indicating whether any of the n points is in the rectangle to be learned. We assume that there is an unknown product distribution D over Q^d such that all instances are independently drawn according to D. The accuracy of a hypothesis is measured 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 algorithm achieves accuracy e with probability 1-δ in O\left(\frac{d^5n^12}{\epsilon^20} \log^2 \frac{nd}{\epsilon\delta}\right) time.
Cite
Text
Long and Tan. "PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples." Annual Conference on Computational Learning Theory, 1996. doi:10.1145/238061.238105Markdown
[Long and Tan. "PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples." Annual Conference on Computational Learning Theory, 1996.](https://mlanthology.org/colt/1996/long1996colt-pac/) doi:10.1145/238061.238105BibTeX
@inproceedings{long1996colt-pac,
title = {{PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples}},
author = {Long, Philip M. and Tan, Lei},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1996},
pages = {228-234},
doi = {10.1145/238061.238105},
url = {https://mlanthology.org/colt/1996/long1996colt-pac/}
}