Approximating hyper-rectangles: learning and pseudo-random sets

By Peter Auer, Philip M. Long, Aravind Srinivasan. 1997

The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for severaf applied learning problems. Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subpmb-lem common to the derandomization of depth-2 (DIW) circuits and derandotnizing Randomized Logspace, and (ii) they approximate the distribution of n independent multivalued random variables. We present improved upper bounds for a class of such problems of " approximating " highdlmensional rectangles that arise in PAC learning and pseudorandomness. A basic common theme of a large part of PAC learning and deran-domination/computational pseudorandomness is to " approximate " a structure using a " smafl " number of representative random examples. A commonly studied such type of structure in both lemn-ing and derandomization are then-dimensional combinatorial rect

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

Distribution Kernel Methods for Multiple-Instance Learning (2013, background): “Other existing work describes when instance or bag concepts are learnable in the probably approximately correct (PAC) framework from MI data using instance classifiers (Auer, Long, and Srinivasan 1997; Blum and Kalai 1998; Sabato and Tishby 2012).”
PAC Learning Axis-aligned Rectangles with Respect to Product Distributions from Multiple-Instance Examples (1996, methodology): “The algorithm of this paper and that of (Auer, Long & Srinivasan, 1997) used only the first instance of each multiple-instance example for estimating probabilities; Blum and Kalai found an elegant way to use all n instances, resulting in an improvement in time and sample complexity over the results ”
Multi-Instance Learning : A Survey (2004, background): “Reinforcement learning attempts to learn a mapping from states to actions, where the instances are with no labels but with delayed rewards that could be viewed as delayed labels, therefore the ambiguity is between that of supervised learning and unsupervised learning.”
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).”
Multi-instance clustering with applications to multi-instance prediction (2009, background): “Dietterich et al. [1] studied the standard multi-instance prediction (STDMIP) problem where a bag is positively labeled if it contains at least one positive instance; otherwise, it is labeled as a negative bag.”
A brief introduction to weakly supervised learning (2018, background): “Early theoretical results [5, 9, 54] show that multiinstance learning is hard for heterogeneous case where each instance in the bag is classified by a different rule, while it is learnable for homogeneous case where all instances are classified by the same rule.”
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 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 inn-dimensional space (Long and Tan, 1998; Auer et al., 1997; Blum and Kalai, 1998).”
A Note on Learning from Multiple-Instance Examples (2004, methodology): “Auer et al. 1997 give a n algorithm that does not require D to be a product distribution and has a much improved sample complexity ~ Od 2 r 2 == 2 and running time ~ Od 3 r 2 ==”
Multi-instance multi-label learning (2008, background): “[5] showed that if the instances in the bags are not independent then Apr learning under the multi-instance learning framework is NP-hard.”