Please use this identifier to cite or link to this item:
|Title:||PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples||Authors:||Long, Philip M.
|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.
checked on Sep 6, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.