Efficient progressive sampling

By Foster J. Provost, David D. Jensen, Tim Oates. 1999

Having access to massive amounts of data does not necessarily imply that induction algorithms must use them all. Samples often provide the same accuracy with far less computational cost. However, the correct sample size rarely is obvious. We analyze methods for progressive samplingusing progressively larger samples as long as model accuracy improves. We explore several notions of efficient progressive sampling. We analyze efficiency relative to induction with all instances; we show that a simple, geometric sampling schedule is asymptotically optimal, and we describe how best to take into account prior expectations of accuracy convergence. We then describe the issues involved in instantiating an efficient progressive sampler, including how to detect convergence. Finally, we provide empirical results comparing a variety of progressive sampling methods. We conclude that progressive sampling can be remarkably efficient .

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

Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, background): “Curve fitting is an LPA (learning, predicting, assessing) algorithm (Kohavi and John, 1995; Provost et al., 1999).”
Tree Induction vs. Logistic Regression: A Learning-Curve Analysis (2003, unknown): “For example, Oates and Jensen (1997) conclude that classification-tree learning curves level off, and Provost, Jensen, and Oates (1999) replicate this finding and use it as an assumption of their sampling strategy.”
Recent advances and applications of surrogate models for finite element method computations: a review (2022, background): “In general, the approaches that address this exploration /exploitation trade-off have been demonstrated to attain better surrogate accuracy with a lower number of samples (Provost et al. 1999).”
Machine Learning from Imbalanced Data Sets 101 (2008, background): “If this turns out to be so, it may be possible to design a progressive sampling strategy (Provost, Jensen, and Oates, 1999) that decides how next to sample by analyzing the prevalence of small disjuncts in the different classes.”
Fast Algorithm Selection Using Learning Curves (2015, background): “The samples follow a geometric increase, as suggested in [12].”
Predicting sample size required for classification performance (2012, methodology): “Both active learning and progressive sampling start with a very small batch of instances and progressively increase the training data size until a termination criteria is met [31-36].”
Fuzzy c-Means Algorithms for Very Large Data (2012, background): “Provost et al. [36] provide a very readable analysis and summary of progressive sampling schemes.”
A Survey of Methods for Scaling Up Inductive Algorithms (1999, methodology): “In Section 7 we discuss a similar technique for determining the minimum number of training examples sufﬁcient for satisfactory learning, namely, progressively sampling larger subsets until model performance no longer improves (John and Langley, 1996; Frey and Fisher, 1999; Provost et al., 1999).”
The effect of class distribution on classifier learning: an empirical study (2001, background): “However, if in practice it is cost effective to procure data incrementally, we suggest that a progressive, adaptive, sampling strategy (Provost, Jensen & Oates, 1999) be developed that incrementally requests new examples based on the improvement in classifier performance due to the recently added…”
Mining high-speed data streams (2000, methodology): “[14] studied different strategies for mining larger and larger subsamples until accuracy (apparently) asymptotes.”
A review of automatic selection methods for machine learning algorithms and hyper-parameter values (2016, methodology): “…to select either machine learning algorithms (Petrak 2000; Leite et al. 2012; Fürnkranz and Petrak 2001; Soares et al. 2001; Leite and Brazdil 2005; Provost et al. 1999; Leite and Brazdil 2010; John and Langley 1996; Gu et al. 2001) (sometimes each with a pre-determined set of combinations of…”