PAC Learning Axis-aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples

By Philip M. Long, Lei Tan. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Solving the Multiple-Instance Problem: A Lazy Learning Approach (2000, background): “Following Dietterich's original work, Long & Tan (1996) showed from theoretical aspect that it is possible to PAC-learn an axis-parallel concept from multiple-instance examples.”
On learning to localize objects with minimal supervision (2014, unknown): “In nearly all cases, the task is formulated as a multiple instance learning (MIL) problem (Long & Tan, 1996).”
Multiple-Instance Learning of Real-Valued Data (2001, background): “There has also been some nice theoretical work on learning the multiple-instance concept class of axis-aligned boxes in n-dimensional space ( Long and Tan, 1998; Auer et al., 1997; Blum and Kalai, 1998).”
Multiple Instance Learning: Algorithms and Applications (2008, background): “Early work on MIL focused on simple algorithms, such as axis aligned rectangles, for which theoretical results can be derived more readily [12, 13].”
Multiple instance learning with generalized support vector machines (2002, methodology): “Algorithms for the MIL problem have first been presented in [5, 1, 7].”
SMILE: A Similarity-Based Approach for Multiple Instance Learning (2010, methodology): “The initial MIL algorithms are presented in [1], [11], [12], which are based on hypothesis classes consisting of axis-aligned rectangles.”
Multi-instance learning with any hypothesis class (2011, methodology): “Diverse Density (Maron and Lozano-P´erez, 1998) and EM-DD (Zhang and Goldman, 2001) employ assumptions on the structure of the bags of instances.”
MILES: Multiple-Instance Learning via Embedded Instance Selection (2006, methodology): “Anumber of theoretical results have been obtained following the APR framework [4], [10], [33].”
Multiple Instance Learning with Manifold Bags (2011, methodology): “Theoretical PAC-style analysis of MIL problems has also seen progress in the last decade (Auer et al., 1997; Blum & Kalai, 1998; Long & Tan, 1998; Sabato & Tishby, 2009; Sabato et al., 2010).”
A Framework for Multiple-Instance Learning (1997, methodology): “This work was followed by [Long and Tan, 1996], where a high-degree polynomial PAC bound was given for the number of examples needed to learn in the multiple-instance learning model.”
Support Vector Machines for Multiple-Instance Learning (2002, methodology): “Algorithms for the MIL problem were first presented in [4, 1, 7].”
A Note on Learning from Multiple-Instance Examples (2004, background): “Long and Tan 1996 describe an algorithm that learns axis-parallel rectangles in the above P AC setting, under the condition that D is a product distribution i.e., the coordinates of each single-instance are chosen independently, with sample complexity ~ Od 2 r 6 ==”
Multi-instance multi-label learning (2008, methodology): “Long and Tan [44] studied the Pac-learnability of multi-instance learning and showed that if the instances in the bags are independently drawn from product distribution, the Apr (Axis-Parallel Rectangle) proposed by Dietterich et al.”
Multi-Instance Learning : A Survey (2004, background): “Work Sample complexity Running time Main assumptions independent instances, product distribution, Long & Tan [15] O( 2n6 ε10 log nd εδ ) O( d5n12 ε20 log(2) nd εδ ) n is constant”