Improving Generalization with Active Learning

David CohnLes AtlasRichard Ladner

article1994Machine-mediated learning1,783 citations

Presents a selective sampling framework implemented via SG-networks that queries an oracle only on regions of uncertainty, substantially improving neural network generalization over standard random training.

Listen

Most traditional machine learning models learn passively from randomly supplied examples. However, random sampling becomes increasingly inefficient as training progresses because most new data points fall into areas where the model is already confident, providing little new information. This creates significant practical bottlenecks in domains where unlabeled data is plentiful but obtaining accurate classifications or labels requires expensive human expertise or computationally intensive analysis.

The article sets out to formalize an active learning approach called selective sampling and demonstrate its practical implementation in neural networks to improve generalization performance with fewer labeled training examples.

The approach introduces a framework where a learning algorithm identifies a region of uncertainty—the segment of the input space where plausible consistent hypotheses disagree—and exclusively selects and queries new examples from that region. To implement this in feedforward neural networks without exponential computational overhead, the article developed an SG-network. This architecture simultaneously trains two boundary models: a most specific network and a most general network, achieved by biasing the training with background data points. Selective sampling is then performed wherever these two networks disagree on classification. The authors evaluated this framework across three experimental domains: a two-dimensional non-connected geometric shape, a 25-dimensional threshold function, and a four-dimensional electrical power system security analysis.

The experiments demonstrated several key findings. First, selective sampling consistently outperformed both passive random sampling and naive network querying, successfully mapping complex, non-connected concept boundaries where naive querying failed entirely. Second, on the 25-dimensional task, selective sampling produced an exponential decrease in generalization error relative to training set size, compared to the standard polynomial error reduction observed under random sampling. Third, in the power system security problem evaluated against 14,979 test cases, adding a single selective sampling iteration reduced generalization error by 10.7% to 12.6% compared to baseline random sampling of identical sample sizes, with greater than 90% statistical confidence. Finally, breaking the sampling process into smaller, more frequent iterative batches systematically improved learning efficiency, though at the expense of additional computation during model retraining.

These findings indicate that active selective sampling substantially cuts the volume of labeled training data required to achieve high model accuracy. For organizations deploying machine learning, this translates directly to lower labeling costs, faster data collection timelines, and reduced operational risks in high-stakes domains such as infrastructure monitoring or automated diagnostics where classification mistakes are costly.

Organizations operating in data-rich but label-expensive environments should consider implementing selective sampling pipelines, particularly in batched iterations to balance computational retraining overhead against data acquisition costs. For future development, technical teams should explore combining selective sampling with transfer learning to accelerate model retraining between batches, as well as incorporating Bayesian methods or multi-model committees to better quantify uncertainty across high-dimensional spaces.

Confidence in these findings is high for low- to moderate-dimensional concept learning in noise-free environments. However, decision-makers should exercise caution when applying this specific method to highly complex architectures or very high-dimensional input spaces, where the region of uncertainty can encompass nearly the entire domain until training is nearly complete, diminishing the efficiency gains of selective sampling toward those of random sampling.

Massachusetts Institute of Technology University of Washington active learning active learning neural network generalization generalization error

Cohn et al (1994).pdf

Paper: Query by committee, H. Seung et al. (1992). Introduces the Query by Committee algorithm and the theoretical basis for reducing query complexity by sampling points of maximal model disagreement.
Paper: A Theory of the Learnable, Leslie G. Valiant (1984). Establishes the foundational PAC learning framework and oracle-query protocol that formalized active concept learning.

Paper: Active Learning with Statistical Models, D. Cohn et al. (1996). Extends active learning from selective neural network heuristics to closed-form statistical criteria that minimize expected variance.
Paper: A sequential algorithm for training text classifiers, David D. Lewis et al. (1994). Applies selective querying principles directly to text classification via uncertainty sampling.
Paper: Support Vector Machine Active Learning with Applications to Text Classification, Simon Tong et al. (2001). Develops practical pool-based active learning heuristics for support vector machines based on version space reduction.
Paper: Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions, Xiaojin Zhu et al. (2003). Unifies selective query acquisition with graph-based semi-supervised learning to minimize expected classification risk.
Paper: Deep Bayesian Active Learning with Image Data, Yarin Gal et al. (2017). Scales active learning to modern deep neural networks and high-dimensional image data using Bayesian uncertainty estimates.
Paper: Active Learning for Convolutional Neural Networks: A Core-Set Approach, Ozan Sener et al. (2018). Formulates batch active learning for convolutional networks through a geometric core-set approach rather than single-point querying.

Cover for Improving Generalization with Active Learning

Abstract

Active learning differs from "learning from examples" in that the learning algorithm assumes at least some control over what part of the input domain it receives information about. In some situations, active learning is provably more powerful than learning from examples alone, giving better generalization for a fixed number of training examples. In this article, we consider the problem of learning a binary concept in the absence of noise. We describe a formalism for active concept learning called selective sampling and show how it may be approximately implemented by a neural network. In selective sampling, a learner receives distribution information from the environment and queries an oracle on parts of the domain it considers "useful." We test our implementation, called an SG-network, on three domains and observe significant improvement in generalization.

Topics

active learning

Keywords

active learning neural network generalization generalization error selective sampling random sampling inductive bias target concept computational learning backpropagation algorithm

Improving Generalization with Active Learning*
1. Introduction: Random sampling vs. active learning
2. Concept learning and selective sampling
2.1. Generalization
2.2. The region of uncertainty
2.3. Selective sampling is active learning
2.4. Approximations to selective sampling
3. Neural networks for selective sampling
3.1. A naive neural network querying algorithm
3.2. Version space
3.3. Implementing an active version-space search
3.4. The SG-net: a neural network version-space search algorithm
3.4.1. Implementing a "most specific/general" network
3.4.2. Implementing active learning with an SG-net
4. Experimental results
4.1. The triangle learner
4.2. Real-valued threshold function
4.3. Power system security analysis
5. Limitations of the selective sampling approach
5.1. Practical limitations
5.2. Theoretical limitations
6. Related work
7. Conclusion
Acknowledgments
Notes
References

Knowls

Knowl 1 — Region of Uncertainty in Concept Learning
definition
Let $X$ be an input domain and let $c: X o \{0, 1\}$ denote a binary concept defined on $X$ . A concept class $C$ is a set of candidate concepts $c \in C$ . Given a target concept $t \in C$ and a training set $S^m = \{(x_i, t(x_i))\}_{i=1}^m$ of $m$ classified instances, a concept $c \in C$ is consistent with $S^m$ if $c(x_i) = t(x_i)$ for all $i \in \{1, \dots, m\}$ .

The region of uncertainty $\mathcal{R}(S^m)$ is the subset of the domain $X$ on which at least two consistent concepts in $C$ disagree:

$\mathcal{R}(S^m) = \{x \in X : \exists c_1, c_2 \in C \text{ consistent with } S^m \text{ such that } c_1(x) \neq c_2(x)\}$

For an underlying probability distribution $\mathcal{P}$ over $X$ , the size of the region of uncertainty is defined as $\alpha = \Pr_{x \sim \mathcal{P}}[x \in \mathcal{R}(S^m)]$ . The generalization error $\epsilon(c, t, \mathcal{P}) = \Pr_{x \sim \mathcal{P}}[c(x) \neq t(x)]$ of any consistent hypothesis $c \in C$ is strictly bounded by $\alpha$ , such that $\epsilon \le \alpha$ .
Knowl 2 — Selective Sampling via Unlabeled Instance Filtering
model/method
Selective sampling is an active concept learning framework in which training examples are drawn exclusively from the region of uncertainty $\mathcal{R}(S^m)$ rather than at random over the entire domain $X$ . Under passive random sampling, the probability that a newly drawn instance falls in $\mathcal{R}(S^m)$ is $\alpha = \Pr_{x \sim \mathcal{P}}[x \in \mathcal{R}(S^m)]$ , which monotonically decreases toward zero as the sample size $m$ grows, diminishing the sample efficiency of each additional example.

In scenarios where obtaining unlabeled domain points from distribution $\mathcal{P}$ is computationally inexpensive relative to the cost of querying an oracle for true classifications, selective sampling operates by filtering:
1. An unclassified instance $x$ is drawn at random according to $\mathcal{P}$ .
2. The learner evaluates whether $x \in \mathcal{R}(S^m)$ .
3. If $x \in \mathcal{R}(S^m)$ , the learner queries the oracle for label $t(x)$ and adds $(x, t(x))$ to the training set; otherwise, $x$ is discarded at zero labeling cost.
To manage computational overhead, selective sampling can be executed in batches: an initial sample $S_0$ is drawn from $\mathcal{P}$ to estimate $\mathcal{R}(S_0)$ , after which successive batches of candidate instances are drawn from the restricted distribution $\mathcal{P}'$ (where $\mathcal{P}'(x) > 0$ only for $x \in \mathcal{R}(S^m)$ ) to incrementally shrink the uncertainty region.
Knowl 3 — SG-Network Architecture for Version Space Approximation
model/method
Exact maintenance of Mitchell's version space boundaries $S$ (most specific consistent hypotheses) and $G$ (most general consistent hypotheses) is intractable for general continuous classifiers because the size of $S$ and $G$ can grow exponentially with sample size. The SG-network approximates this boundary traversal with a fixed representational capacity by defining a total ordering on concept generality: concept $c_1$ is more general than $c_2$ with respect to distribution $\mathcal{P}$ if and only if $\Pr_{x \sim \mathcal{P}}[x \in c_1] > \Pr_{x \sim \mathcal{P}}[x \in c_2]$ .

The SG-network architecture consists of two neural networks possessing identical topologies and sharing the same input layer:
- A most specific network $s$ , trained with an inductive bias that minimizes $\Pr_{x \sim \mathcal{P}}[x \in s]$ subject to consistency with training sample $S^m$ .
- A most general network $g$ , trained with an inductive bias that maximizes $\Pr_{x \sim \mathcal{P}}[x \in g]$ subject to consistency with training sample $S^m$ .
The estimated region of uncertainty $\mathcal{R}^*(S^m)$ is the symmetric difference between their thresholded outputs:

$\mathcal{R}^*(S^m) = s \Delta g = \{x \in X : s(x) \neq g(x)\}$

If candidate point $x \sim \mathcal{P}$ satisfies $s(x) \neq g(x)$ , the oracle is queried for $t(x)$ and the instance is added to $S^m$ . If either network fails to reach zero error on a training instance, that instance remains inside $s \Delta g$ , guaranteeing additional sampling in that locale on subsequent iterations to overcome local minima.
Knowl 4 — Training Most Specific and Most General Networks with Dynamic Background Bias
algorithm
To constrain a feedforward neural network trained via backpropagation to converge to either the most specific concept $s$ or the most general concept $g$ consistent with training set $S^m$ , artificial background instances drawn from distribution $\mathcal{P}$ are interleaved during training. Background instances are labeled as 0 (for the specific network $s$ ) or 1 (for the general network $g$ ).

To prevent background patterns from overpowering actual training data as training error approaches zero, the learning rate for background examples $\eta'$ is dynamically scaled by the network error $\delta(x) = (c(x) - t(x))^2$ on the current training point:

$\eta' = \gamma \delta(x) \eta$

where $\eta$ is the standard learning rate and $\gamma \in (0, 1]$ is an attenuation constant (empirically set to $\gamma = 0.75$ ).
Input: Training set $S^m = \{(x_k, t(x_k))\}_{k=1}^m$ , distribution $\mathcal{P}$ , learning rate $\eta$ , attenuation factor $\gamma \in (0, 1]$ , tolerance threshold $\theta$ , background label $\tau \in \{0, 1\}$ ( $\\tau = 0$ for most specific network, $\\tau = 1$ for most general network)
Output: Trained network configuration $c$
Initialize network configuration $c$ with random weights
while $\exists (x, t(x)) \in S^m$ such that $(c(x) - t(x))^2 \ge \theta$ :
    for each training example $(x, t(x)) \in S^m$ :
        Compute output error $\delta(x) = (c(x) - t(x))^2$
        Backpropagate $\delta(x)$ and compute weight update $\Delta w_{ji} = \eta \delta_j(x) o_i(x)$
        Update weights $w_{ji} \leftarrow w_{ji} + \Delta w_{ji}$
        Compute background learning rate $\eta' = \gamma \delta(x) \eta$
        Sample unclassified point $y \sim \mathcal{P}$ and create background pair $(y, \tau)$
        Compute background output error $\delta(y) = (c(y) - \tau)^2$
        Backpropagate $\delta(y)$ and compute weight update $\Delta w_{ji} = \eta' \delta_j(y) o_i(y)$
        Update weights $w_{ji} \leftarrow w_{ji} + \Delta w_{ji}$
return $c$
Knowl 5 — Failure Mode of Single-Network Output Uncertainty Heuristics
theoretical result
A naive heuristic for active learning in neural networks defines the region of uncertainty as the transition region where a single trained network's continuous sigmoid output $c(x) \in [0, 1]$ falls between intermediate thresholds (such as $0.1 < c(x) < 0.9$ ).

This approach fails to approximate the true region of uncertainty $\mathcal{R}(S^m)$ because it reflects only the internal ambiguity of one specific configuration $c$ , rather than the envelope of disagreement across all possible configurations in concept class $C$ consistent with $S^m$ .

Because gradient-based backpropagation exhibits an inductive bias toward sharp decision boundaries with minimal units, a single network becomes overly confident ( $c(x) \le 0.1$ or $c(x) \ge 0.9$ ) across regions lacking data. Consequently, if an initial random sample fails to detect an isolated or disconnected positive component of a target concept, the naive transition zone will exclude that entire component from future queries, causing permanent failure to learn the undiscovered region.
Knowl 6 — Exponential Generalization Error Scaling on Real-Valued Threshold Functions
empirical result
In a 25-bit continuous real-valued threshold classification problem evaluated across varying training set sizes $m$ , active learning with the SG-network achieved near-exponential error decay, whereas passive random sampling followed polynomial error decay.

Linear regression on the inverse error $\epsilon^{-1}$ and logarithmic error $\ln(\epsilon)$ demonstrated:
- Random sampling (12 runs): Error scaled polynomially according to $\epsilon = (a \cdot m + b)^{-1}$ with $a = 0.0514$ , $b = -0.076$ , and a coefficient of determination $r^2 = 0.987$ (exponential fit yielded only $r^2 = 0.981$ ). The average standard deviation of error was $0.00265$ .
- SG-network selective sampling (6 runs, batches of 10): Error scaled exponentially according to $\epsilon = e^{a \cdot m + b}$ with $a = -0.0218$ , $b = 0.071$ , and a coefficient of determination $r^2 = 0.995$ down to $\epsilon < 0.015$ (polynomial fit yielded only $r^2 = 0.937$ ). The average standard deviation of error was $0.00116$ .
Partitioning the total query budget into smaller, more frequent sampling iterations consistently lowered generalization error relative to larger batch sizes.
Knowl 7 — Sample Complexity on Non-Connected 2D Triangular Concepts
empirical result
Active learning with the SG-network was evaluated on learning a non-connected concept consisting of two disjoint triangles in a two-dimensional domain with a uniform distribution $\mathcal{P}$ . The classifier architecture was a feedforward network with two inputs, hidden layers of 8 and 3 units, and a single thresholded output unit.

Experimental conditions compared:
1. Random sampling baseline: 12 networks trained on randomly sampled datasets sized from $m = 10$ to $m = 150$ in increments of 10.
2. Naive output-uncertainty querying: 12 runs using the single-network uncertainty band $0.1 < c(x) < 0.9$ .
3. SG-network selective sampling: 4 independent runs performing 15 sequential iterations of 10 queries each (evaluated over 8 network test cases).
The SG-network achieved consistently lower generalization error across all training set sizes relative to random sampling. The naive querying method exhibited erratic generalization performance, failing repeatedly due to its inability to place queries near whichever triangle remained unhit during the initial random sample.
Knowl 8 — Generalization Improvement in Power System Static Security Assessment
empirical result
Selective sampling was applied to power system static security assessment over a 4-dimensional continuous electrical load domain, where evaluating whether a state is secure requires solving non-linear power flow differential equations.

Networks trained on 500 initial random samples were augmented with a single batch of selective queries using an SG-network and compared against purely random baselines on an independent test set of 14,979 points:
- Small training set ( $m = 800$ total points): Augmenting 500 initial points with 300 selectively sampled points achieved a test classification error of $5.17\%$ , compared to $5.47\%$ for 800 purely random points (a $10.7\%$ relative error reduction).
- Large training set ( $m = 2500$ total points): Augmenting 500 initial points with 2000 selectively sampled points achieved a test error of $4.21\%$ , compared to $4.82\%$ for 2500 purely random points (a $12.6\%$ relative error reduction).
The observed accuracy improvements over passive random sampling were statistically significant at greater than $90\%$ confidence.
Knowl 9 — Theoretical and Practical Scalability Bottlenecks of Selective Sampling
limitation
The selective sampling paradigm exhibits several theoretical and geometric limitations in high-dimensional or high-capacity settings:
1. Superset approximation explosion: When using an outer bounding approximation $\mathcal{R}^+(S^m) \supseteq \mathcal{R}(S^m)$ , high input dimensionality causes corner irregularities ('nicks') to force $\mathcal{R}^+(S^m)$ to encompass nearly the entire domain volume, degrading sampling efficiency to that of random sampling.
2. Subset starvation: When using an inner approximation $\mathcal{R}^-(S^m) \subseteq \mathcal{R}(S^m)$ , inductive bias can shrink $\mathcal{R}^-(S^m)$ into tiny local sub-regions, causing heavy oversampling in isolated areas while ignoring large unlearned portions of the domain.
3. High capacity dispersion: When the classifier concept class has high representational complexity (e.g., neural networks with large hidden layers), the region of uncertainty $\mathcal{R}(S^m)$ can span the entire domain even when the true generalization error is small, preventing active querying from focusing until the concept is already almost fully learned.

Coverage note — None; all primary contributed theoretical definitions, the SG-network architecture, the dynamic background training algorithm, and empirical evaluations across the 2D triangles, 25-bit threshold function, and power system security benchmarks are fully represented.

References

1.Aggoune, M., Atlas, L., Cohn, D., Damborg, M., El-Sharkawi, M., & Marks, R. II. (1989). Artificial neural networks for power system static security assessment. Proceedings, International Symposium on Circuits and Systems. IEEE.
2.Angluin, D. (1986). Learning regular sets from queries and counter-examples. (Technical Report YALEU/DCS/TR-64). Dept. of Computer Science, Yale University, New Haven, CT.
3.Ash, T. (1989). Dynamic node creation in backpropagation networks. ICS Report 8901. Institute for Cognitive Science, University of California, San Diego, CA.
4.Aum, E., & Haussler, D. (1989). What size net gives valid generalization? In D. Touretzky (Ed.), Advances in neural information processing systems, (Vol. 1). San Francisco, CA: Morgan Kaufmann.
5.Baum, E., & Lang, K. (1991). Constructing hidden units using examples and queries. In R. Lippmann et al. (Eds.), Advances in neural information processing systems (Vol. 3). San Francisco, CA: Morgan Kaufmann.
6.Blum, A., & Rivest, R. (1989). Training a 3-node neural network is NP-complete. In D. Touretzky (Ed.), Advances in neural information processing systems, Volume 1. San Francisco, CA: Morgan Kaufmann.
7.Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1989). Learnability and the Vapnik-Chervonenkis dimension. JACM, 36(4), 929-965.
8.Cohn, D., Atlas, L., & Ladner, R. (1990). Training connectionist networks with queries and selective sampling. In D. Touretzky (Ed.), Advances in neural information processing systems, (Vol. 2). San Francisco, CA: Morgan Kaufmann.
9.Cohn, D., & Tesauro, G. (1992). How tight are the Vapnik-Chervonenkis bounds? Neural Computation 4(2), 249-269.
10.Eisenberg, B., & Rivest, R. (1990). On the sample complexity of pac-learning using random and chosen examples. In M. Fulk & J. Case (Eds.), ACM 3rd Annual Workshop on Computational Learning Theory. San Francisco, CA: Morgan Kaufmann.
11.Fernald, A., & Kuhl, P. (1987). Acoustic determinants of infant preference for Motherese speech. Infant Behavior and Development, 10, 279-293.
12.Freund, Y., Seung, H.S., Shamir, E., & Tishby, N. (1993). Information, prediction, and query by committee. In S. Hanson et al., (Eds.). Advances in Neural Information Processing Systems (Vol. 5). San Francisco, CA: Morgan Kaufmann.
13.Haussler, D. (1987). Learning conjunctive concepts in structural domains. Proceedings, AAAI '87 (pp. 466-470). San Francisco, CA: Morgan Kaufmann.
14.Haussler, D., (1992). Decision-theoretic generalizations of the PAC model for neural net and other applications. Information and Computation, 100(1), 78-150.
15.Hwang, J.-N., Choi, J., Oh, S., & Marks, R. (1990). Query learning based on boundary search and gradient computation of trained multilayer perceptrons. IJCNN 90. San Diego, CA.
16.Judd, S. (1988). On the complexity of loading shallow neural networks. Journal of Complexity, 4, 177-192.
17.Le Cunn, Y., Denker, J., & Solla, S. (1990). Optimal brain damage. In D. Touretzky (Ed.), Advances in neural information processing systems (Vol. 2). San Francisco, CA: Morgan Kaufmann.
18.MacKay, D. (1992). Information-based objective functions for active data selection. Neural Computation, 4(4), 590-604.
19.Mitchell, T. (1982). Generalization as search. Artificial Intelligence, 18, 203-226.
20.Pratt, L.Y. (1993). Discriminability-based transfer between neural networks. In C.L. Giles, et al. (Eds.), Advances in Neural Information Processing Systems, (Vol. 5). San Francisco, CA: Morgan Kaufmann.
21.Rumelhart, D., Hinton, G., & Williams, R. (1986). Learning internal representations by error propagation. In D. Rumelhart & I. McClelland (Eds.), Parallel distributed processing, Cambridge, MA: MIT Press.
22.Seung, H.S., Opper, M., & Sompolinsky, H. (1992). Query by committee. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory (pp. 287-294). New York: ACM.
23.Valiant, L. (1984). A theory of the learnable. Communications of the ACM, 27, 1134-1142.

Citation

MLA

Cohn, D., et al. “Improving Generalization with Active Learning”. Machine Learning, vol. 15, no. 2, 1994, pp. 201–21, https://doi.org/10.1023/A:1022673506211.

APA

Cohn, D., Atlas, L., & Ladner, R. (1994). Improving Generalization with Active Learning. Machine Learning, 15(2), 201–221. https://doi.org/10.1023/A:1022673506211

Chicago

Cohn, D., L. Atlas, and R. Ladner. 1994. “Improving Generalization with Active Learning”. Machine Learning 15 (2): 201–21. https://doi.org/10.1023/A:1022673506211.

Harvard

Cohn, D., Atlas, L. and Ladner, R. (1994) “Improving Generalization with Active Learning”, Machine Learning, 15(2), pp. 201–221. Available at: https://doi.org/10.1023/A:1022673506211.

Vancouver

1. Cohn D, Atlas L, Ladner R (1994) Improving Generalization with Active Learning. Machine Learning 15:201–221

BibTeX

@article{Cohn_1994, title={Improving Generalization with Active Learning}, volume={15}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1022673506211}, DOI={10.1023/a:1022673506211}, number={2}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Cohn, David and Atlas, Les and Ladner, Richard}, year={1994}, month=May, pages={201–221} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Improving Generalization with Active Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Region of Uncertainty in Concept Learning

Knowl 2 — Selective Sampling via Unlabeled Instance Filtering

Knowl 3 — SG-Network Architecture for Version Space Approximation

Knowl 4 — Training Most Specific and Most General Networks with Dynamic Background Bias

Knowl 5 — Failure Mode of Single-Network Output Uncertainty Heuristics

Knowl 6 — Exponential Generalization Error Scaling on Real-Valued Threshold Functions

Knowl 7 — Sample Complexity on Non-Connected 2D Triangular Concepts

Knowl 8 — Generalization Improvement in Power System Static Security Assessment

Knowl 9 — Theoretical and Practical Scalability Bottlenecks of Selective Sampling

References

Citation

BibTeX

Access the Paper