Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/114368
Title: PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples
Authors: Long, Philip M. 
Tan, Lei
Issue Date: 1996
Citation: Long, Philip M.,Tan, Lei (1996). PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Proceedings of the Annual ACM Conference on Computational Learning Theory : 228-234. ScholarBank@NUS Repository.
Abstract: We describe a polynomial-time algorithm for learning axis-aligned rectangles in Qd with respect to product distributions from multiple-instance examples in the PAC model. Here, each example consists of n elements of Qd 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 Qd 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(d5n12/ε20 log2 nd/εδ) time.
Source Title: Proceedings of the Annual ACM Conference on Computational Learning Theory
URI: http://scholarbank.nus.edu.sg/handle/10635/114368
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

73
checked on Nov 16, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.