Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/114367
Title: PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples
Authors: Long, P.M. 
Tan, L.
Keywords: Axis-aligned hyperrectangles
Multiple-instance examples
PAC learning
Issue Date: 1998
Source: Long, P.M.,Tan, L. (1998). PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Machine Learning 30 (1) : 7-21. 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. © 1998 Kluwer Academic Publishers.
Source Title: Machine Learning
URI: http://scholarbank.nus.edu.sg/handle/10635/114367
ISSN: 08856125
Appears in Collections:Staff Publications

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

Page view(s)

59
checked on Feb 24, 2018

Google ScholarTM

Check


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