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 ∈ with probability 1- δ in O (d 5 n 12 /∈ 20 log 2 nd/∈δ time.
Cite
Text
Long and Tan. "PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples." Machine Learning, 1998. doi:10.1023/A:1007450326753Markdown
[Long and Tan. "PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples." Machine Learning, 1998.](https://mlanthology.org/mlj/1998/long1998mlj-pac/) doi:10.1023/A:1007450326753BibTeX
@article{long1998mlj-pac,
title = {{PAC Learning Axis-Aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples}},
author = {Long, Philip M. and Tan, Lei},
journal = {Machine Learning},
year = {1998},
pages = {7-21},
doi = {10.1023/A:1007450326753},
volume = {30},
url = {https://mlanthology.org/mlj/1998/long1998mlj-pac/}
}