Back

Query by committee

H. SeungM. OpperH. Sompolinsky

article1992COLT2,167 citations

Introduces the Query by Committee active learning framework, demonstrating that selecting unlabeled examples based on maximal disagreement among an ensemble of models achieves an exponential reduction in generalization error compared to passive random sampling.

Listen

In many machine learning applications, acquiring labeled data is computationally expensive or labor-intensive. Standard training approaches that passively learn from randomly chosen inputs require vast numbers of examples to achieve high accuracy, causing significant delays and resource expenditures. The article addresses the challenge of designing efficient query-based active learning strategies that dramatically reduce the number of queries required to train a model accurately.

The article set out to evaluate the Query by Committee algorithm and demonstrate that selecting queries based on maximal disagreement among an ensemble of models achieves asymptotically finite information gain and exponential reductions in prediction error.

The authors analyzed the algorithm using statistical mechanics techniques and theoretical calculations, supported by Monte Carlo simulations. They evaluated two representative learning scenarios: a simple one-dimensional threshold model (the high-low game) and a multidimensional perceptron learning another perceptron under Gaussian input distributions. In this framework, a committee of models is trained on existing data, and new unlabeled inputs are evaluated; only the input that causes the greatest disagreement among committee members is submitted to the teacher for labeling.

The analysis produced three key findings. First, while learning from randomly selected inputs causes the information gain per sample to decay toward zero as training progresses, the Query by Committee algorithm maintains an asymptotically finite information gain for every query. Second, this sustained information gain causes the generalization error to decrease exponentially with the number of queries, compared to the much slower inverse power-law decline observed with random inputs. Third, as the committee size increases, the information gain approaches the theoretical upper bound of one bit per query, corresponding to an exact bisection of the remaining plausible model space.

These findings indicate that actively selecting data points where a committee disagrees can drastically reduce the amount of labeled training data needed to achieve target performance levels. In high-cost data labeling environments, this approach can substantially reduce operational costs and accelerate development cycles compared to random sampling. For moderate data sizes, even a small committee (such as two members) achieves significant performance gains.

Organizations facing high labeling or querying costs should consider implementing disagreement-based query filtering for incremental model training. However, because filtering random inputs to find disagreements becomes slower as model accuracy improves, teams should also evaluate direct query construction methods where applicable to avoid computational search bottlenecks.

The primary limitation of this work is that the findings are derived from idealized theoretical models with perfectly realizable target rules, spherical weight spaces, and uniform or Gaussian data distributions. While confidence in the analytical and simulation results for these models is high, further research and empirical validation on complex, real-world machine learning architectures and noisy data distributions are necessary before broad production deployment.

Justus Liebig University GiessenThe Hebrew University of Jerusalembackpropagation algorithmQueryCommitteeInformation
Seung et al (1992).pdf
  • Paper: A Theory of the Learnable, Leslie G. Valiant (1984). This foundational paper establishes the PAC-learning framework that underpins the theoretical analysis of sample complexity and generalization error central to query-by-committee.
  • Paper: A Stochastic Approximation Method, Herbert Robbins et al. (1951). Understanding stochastic approximation methods is crucial for following how query-by-committee algorithms asymptotically reduce generalization error over infinite query sequences.
Cover for Query by committee

Abstract

We propose an algorithm called query by committee, in which a committee of students is trained on the same data set. The next query is chosen according to the principle of maximal disagreement. The algorithm is studied for two toy models: the high-low game and perceptron learning of another perceptron. As the number of queries goes to infinity, the committee algorithm yields asymptotically finite information gain. This leads to generalization error that decreases exponentially with the number of examples. This in marked contrast to learning from randomly chosen inputs, for which the information gain approaches zero and the generalization error decreases with a relatively slow inverse power law. We suggest that asymptotically finite information gain may be an important characteristic of good query algorithms.

Topics

backpropagation algorithm

Keywords

QueryCommitteeInformationAlgorithmGainLearningGeneralizationTrainingSpaceRandom

Table of Contents

  • 1 Introduction
  • 2 The information content of a query
  • 3 High-Low
  • 4 Perception Learning
  • 4.1 Random inputs
  • 4.2 Query by committee
  • 5 Conclusion
  • Acknowledgements
  • References
  • Appendix: Replica calculations for query by committee

Knowls

  1. Knowl 1 — Query by Committee Algorithm for Incremental Active Learning

    algorithm

    The Query by Committee (QBC) algorithm is an incremental active learning method for parametric models learning a deterministic boolean target function σ0(X)∈{+1,−1}\sigma_0(X) \in \{+1, -1\}. It uses the principle of maximal disagreement among an even committee of Gibbs learners to select queries that maximize information gain.

    Input: Prior input distribution P0(X)P_0(X), committee size 2k2k (where k≥1k \ge 1 is an integer), initial training set D0=∅D_0 = \emptyset
    Output: Student weight vector WW
    for P=0,1,2,…P = 0, 1, 2, \dots do
        Sample 2k2k student weight vectors W1,…,W2kW_1, \dots, W_{2k} independently at random from the version space WP={W:σ(W;Xt)=σt,∀t=1,…,P}W_P = \{W : \sigma(W; X^t) = \sigma^t, \forall t=1,\dots,P\} using zero-temperature Gibbs sampling
        repeat
            Draw candidate input vector XX from P0(X)P_0(X)
            Evaluate committee predictions σ^i=σ(Wi;X)\hat{\sigma}_i = \sigma(W_i; X) for each i∈{1,…,2k}i \in \{1, \dots, 2k\}
            k+←∑i=12kI(σ^i=+1)k_+ \leftarrow \sum_{i=1}^{2k} \mathbb{I}(\hat{\sigma}_i = +1)
        until k+=kk_+ = k
        Query the teacher for label σP+1←σ0(X)\sigma^{P+1} \leftarrow \sigma_0(X)
        DP+1←DP∪{(X,σP+1)}D_{P+1} \leftarrow D_P \cup \{(X, \sigma^{P+1})\}
    end for
    return W1W_1

    As k→∞k \to \infty, the committee's maximal disagreement condition converges to exact bisection of the version space, providing 1 bit of information per query.

  2. Knowl 2 — Bayesian Expected Information Gain of a Query in Version Space Learning

    theoretical result

    Let σ(W;X)∈{+1,−1}\sigma(W; X) \in \{+1, -1\} be a parametric student model with a flat prior distribution P0(W)P_0(W). Given a training set of PP examples {ξt=(Xt,σt)}t=1P\{\xi^t = (X^t, \sigma^t)\}_{t=1}^P, the version space WPW_P is the set of all weight vectors consistent with the training set:

    WP={W:σ(W;Xt)=σt, t=1,…,P}W_P = \{W : \sigma(W; X^t) = \sigma^t, \, t=1, \dots, P\}

    The posterior distribution is uniform on WPW_P with volume VPV_P, giving posterior entropy S=log⁡VPS = \log V_P. When a candidate query XP+1X^{P+1} is proposed, it partitions WPW_P into two subvolumes:

    W+={W∈WP:σ(W;XP+1)=+1},W−={W∈WP:σ(W;XP+1)=−1}W^+ = \{W \in W_P : \sigma(W; X^{P+1}) = +1\}, \quad W^- = \{W \in W_P : \sigma(W; X^{P+1}) = -1\}

    with volumes V+V^+ and V−V^- (V++V−=VPV^+ + V^- = V_P). Averaging the information gain IP+1=−ΔS=−log⁡(VP+1/VP)I_{P+1} = -\Delta S = -\log(V_{P+1}/V_P) over the posterior distribution of the teacher weight vector W0W_0 yields the Bayesian expected information gain:

    ⟨IP+1⟩=−V+VPlog⁡(V+VP)−V−VPlog⁡(V−VP)\langle I_{P+1} \rangle = -\frac{V^+}{V_P} \log\left(\frac{V^+}{V_P}\right) - \frac{V^-}{V_P} \log\left(\frac{V^-}{V_P}\right)

    This expected information gain equals the binary Shannon entropy of the label distribution. It is maximized at exactly 1 bit (atln⁡2 at \ln 2) when the query bisects the version space such that V+=V−=VP/2V^+ = V^- = V_P / 2.

  3. Knowl 3 — Asymptotic Information Gain and Exponential Generalization Curve in Perceptron Learning

    theoretical result

    Consider a spherical perceptron σ(W;X)=sgn(W⋅X)\sigma(W; X) = \text{sgn}(W \cdot X) learning another perceptron σ0(X)=sgn(W0⋅X)\sigma_0(X) = \text{sgn}(W_0 \cdot X) on inputs X∼N(0,IN)X \sim \mathcal{N}(0, I_N), where W,W0∈RNW, W_0 \in \mathbb{R}^N satisfy W⋅W=W0⋅W0=NW \cdot W = W_0 \cdot W_0 = N. In the thermodynamic limit N,P→∞N, P \to \infty with query density α=P/N\alpha = P/N:

    1. Random inputs: The information gain per query scales as I(α)≈1.60 ϵg(α)→0I(\alpha) \approx 1.60 \, \epsilon_g(\alpha) \to 0 as α→∞\alpha \to \infty, resulting in an inverse power-law generalization error:

    ϵg(α)≈0.625α\epsilon_g(\alpha) \approx \frac{0.625}{\alpha}

    1. Query by Committee (2k2k students): The information gain approaches a strictly positive constant I(∞)>0I(\infty) > 0 as α→∞\alpha \to \infty. Because the entropy per weight scales as s(α)≈log⁡ϵg(α)s(\alpha) \approx \log \epsilon_g(\alpha), the generalization error decays exponentially with α\alpha:

    ϵg(α)∼e−αI(∞)\epsilon_g(\alpha) \sim e^{-\alpha I(\infty)}

    where the asymptotic decay rate is governed by the committee's limiting information gain I(∞)I(\infty).

  4. Knowl 4 — Asymptotic Information Gain Equation for Perceptron Query by Committee

    equation

    For a committee of 2k2k spherical perceptron students learning a teacher perceptron on Gaussian inputs, the asymptotic information gain I(∞)=lim⁡α→∞I(α)I(\infty) = \lim_{\alpha \to \infty} I(\alpha) in the thermodynamic limit is given by:

    I(∞)=−2∫−∞∞Dz Hk(z)Hk(−z)H(z)log⁡H(z)∫−∞∞Dz Hk(z)Hk(−z)I(\infty) = -2 \frac{\int_{-\infty}^\infty Dz \, H^k(z) H^k(-z) H(z) \log H(z)}{\int_{-\infty}^\infty Dz \, H^k(z) H^k(-z)}

    where the Gaussian measure is Dz=dz2πe−z2/2Dz = \frac{dz}{\sqrt{2\pi}} e^{-z^2/2} and the tail probability function is defined as:

    H(y)=∫y∞Dz=∫y∞dx2πe−x2/2H(y) = \int_y^\infty Dz = \int_y^\infty \frac{dx}{\sqrt{2\pi}} e^{-x^2/2}

    As committee size parameter k→∞k \to \infty, I(∞)I(\infty) saturates the theoretical upper bound of 1 bit (atln⁡2≈0.693 at \ln 2 \approx 0.693 nats).

  5. Knowl 5 — Asymptotic Information Gain Values Across Committee Sizes for Perceptron Learning

    data/table

    The asymptotic information gain I(∞)I(\infty) obtained by the Query by Committee algorithm for perceptron learning increases monotonically with the committee size 2k2k, rapidly approaching the 1-bit bisection limit:

    Committee Size (2k2k) Information Gain (nats) Information Gain (bits)
    2 0.523 0.754
    4 0.592 0.854
    6 0.621 0.896
    ∞\infty 0.693 1.000

    Even the minimal committee of two members (2k=22k = 2) achieves an asymptotic information gain of 0.7540.754 bits per query, which is sufficient to produce an exponential decrease in generalization error as a function of the number of queries α=P/N\alpha = P/N.

  6. Knowl 6 — Exact Volume Ratio Distribution and Information Gain in the High-Low Game

    theoretical result

    In the high-low game, the input space and weight space are the unit interval [0,1][0, 1] with flat priors, and rules are threshold functions σ(X;W)=sgn(X−W)\sigma(X; W) = \text{sgn}(X - W). After P≥2P \ge 2 examples, the version space is the interval WP=[XL,XR]W_P = [X_L, X_R] of length VP=XR−XLV_P = X_R - X_L.

    1. Random inputs: The volume ratio χP+1=VP+1/VP\chi_{P+1} = V_{P+1}/V_P follows P(χP+1∣VP)=(1−VP)δ(χP+1−1)+2VPχP+1P(\chi_{P+1} | V_P) = (1 - V_P)\delta(\chi_{P+1} - 1) + 2 V_P \chi_{P+1}. Expected information gain is ⟨IP+1⟩=VP/2→0\langle I_{P+1} \rangle = V_P / 2 \to 0, and average generalization error decays as a power law:

    ϵg(P)=23(P+2)\epsilon_g(P) = \frac{2}{3(P+2)}

    1. Query by Committee (2k2k students): The probability density of the volume ratio χ\chi is independent of query history and given by:

    P(χ)∝2χ∫0χdy∫χ1dz yk−1(1−z)k−1z−yP(\chi) \propto 2\chi \int_0^\chi dy \int_\chi^1 dz \, \frac{y^{k-1}(1-z)^{k-1}}{z-y}

    The average information gain per query is constant for all PP:

    I(k)=∫01dxlog⁡x P(x)=ψ(2k+2)−ψ(k+2)−ψ′(k+2)ψ(k+2)−ψ(k)+12I(k) = \int_0^1 dx \log x \, P(x) = \psi(2k+2) - \psi(k+2) - \frac{\psi'(k+2)}{\psi(k+2) - \psi(k)} + \frac{1}{2}

    where ψ(z)=Γ′(z)/Γ(z)\psi(z) = \Gamma'(z)/\Gamma(z) is the Euler digamma function. Because log⁡ϵg=∑t=1Plog⁡χt+const\log \epsilon_g = \sum_{t=1}^P \log \chi_t + \text{const}, the central limit theorem implies that ϵg(P)\epsilon_g(P) is asymptotically log-normal with the most probable value decaying exponentially:

    ϵg(P)∼e−PI(k)\epsilon_g(P) \sim e^{-P I(k)}

  7. Knowl 7 — Continuous-Time Replica Calculation for Query by Committee in Perceptrons

    model/method

    The dynamics of incremental query learning in spherical perceptrons (W⋅W=NW \cdot W = N) on Gaussian inputs in the thermodynamic limit N,P→∞N, P \to \infty is modeled as a continuous-time process with normalized sample density α=t/N\alpha = t/N. Under the replica-symmetric temporal overlap ansatz, the typical overlap between weight vectors at normalized times α\alpha and α′\alpha' is assumed to depend only on the earlier time:

    Wt⋅Wt′N=q(min⁡{α,α′})\frac{W^t \cdot W^{t'}}{N} = q(\min\{\alpha, \alpha'\})

    Treating previous order parameters q(α′)q(\alpha') for α′<α\alpha' < \alpha as external fields, the entropy per weight s=S/Ns = S/N at time α\alpha for a committee of 2k2k students is derived via the replica trick as:

    s=12q+12ln⁡(1−q)+2∫0αdα′∫Dz∫Dy Hk(γ′z)Hk(−γ′z)H(u)ln⁡H(u)∫Dz Hk(γ′z)Hk(−γ′z)s = \frac{1}{2}q + \frac{1}{2}\ln(1-q) + 2\int_0^\alpha d\alpha' \frac{\int Dz \int Dy \, H^k(\gamma' z) H^k(-\gamma' z) H(u) \ln H(u)}{\int Dz \, H^k(\gamma' z) H^k(-\gamma' z)}

    where γ′=q(α′)1−q(α′)\gamma' = \sqrt{\frac{q(\alpha')}{1-q(\alpha')}}, u=zq(α′)1−q+yq−q(α′)1−qu = z \sqrt{\frac{q(\alpha')}{1-q}} + y \sqrt{\frac{q - q(\alpha')}{1-q}}, and Dz,DyDz, Dy are standard Gaussian measures. The order parameter q(α)q(\alpha) is determined variationally by extremizing ss.

  8. Knowl 8 — Generalization Error Scaling Determined by Entropy Derivative and Asymptotic Information Gain

    theoretical result

    In realizable parametric boolean classification models (including the high-low game and spherical perceptrons), the version space entropy per weight scales asymptotically with generalization error as:

    s≈log⁡ϵgs \approx \log \epsilon_g

    The information gain per example I(α)=−dsdαI(\alpha) = -\frac{ds}{d\alpha} dictates the asymptotic rate of decrease of the generalization curve through the differential relation:

    I(α)=−dlog⁡ϵgdα=−1ϵgdϵgdαI(\alpha) = -\frac{d \log \epsilon_g}{d\alpha} = -\frac{1}{\epsilon_g}\frac{d\epsilon_g}{d\alpha}

    1. If I(α)→0I(\alpha) \to 0 proportionally to ϵg\epsilon_g (as in passive learning with random inputs, where I(α)≈c ϵgI(\alpha) \approx c \, \epsilon_g), integrating dϵgdα≈−c ϵg2\frac{d\epsilon_g}{d\alpha} \approx -c \, \epsilon_g^2 yields an inverse power law:

    ϵg(α)∝1α\epsilon_g(\alpha) \propto \frac{1}{\alpha}

    1. If I(α)→I(∞)>0I(\alpha) \to I(\infty) > 0 as α→∞\alpha \to \infty (as in Query by Committee), integrating dlog⁡ϵgdα→−I(∞)\frac{d \log \epsilon_g}{d\alpha} \to -I(\infty) yields an exponential decay:

    ϵg(α)∼e−αI(∞)\epsilon_g(\alpha) \sim e^{-\alpha I(\infty)}

  9. Knowl 9 — Monte Carlo Simulation Validation of Perceptron Learning Curves

    empirical result

    Monte Carlo simulations were performed for spherical perceptron learning with N=25N = 25 dimensions, averaged over 64 independent runs. For each query, Gibbs sampling was implemented by finding a consistent weight vector using the deterministic perceptron algorithm and equilibrating it with zero-temperature Monte Carlo for 1024 steps, scaling the step size downward with increasing α=P/N\alpha = P/N to maintain an acceptance rate of approximately 50%50\%.

    For moderate values of α\alpha (up to α≈1\alpha \approx 1), the generalization error ϵg(α)\epsilon_g(\alpha) of a two-member committee (2k=22k=2) was close to that of random input learning. For α>1\alpha > 1, the committee algorithm demonstrated a clear separation, exhibiting exponential error reduction in quantitative agreement with the analytical predictions of the replica calculation.

  10. Knowl 10 — Divergence of Candidate Search Time in Passive Screening Implementation of Query by Committee

    limitation

    When Query by Committee is implemented by filtering candidate inputs drawn randomly from the prior distribution P0(X)P_0(X) until an input provoking maximal committee disagreement is found, the probability that a random input splits the shrinking version space scales with the generalization error ϵg\epsilon_g. Consequently, the average number of candidate input evaluations required to find a single valid query scales as O(1/ϵg)O(1/\epsilon_g), diverging as learning proceeds and ϵg→0\epsilon_g \to 0.

    While direct query construction algorithms (such as constructing inputs perpendicular to the student weight vector) avoid this computational bottleneck for specific architectures, the committee screening principle retains broader generality across model classes.

Coverage note — None omitted; all core theoretical models (high-low game and perceptron), replica symmetric dynamical derivations, asymptotic information gain equations and table values, Monte Carlo simulations, and algorithmic limitations were extracted.

References

  1. 1.E. Baum. Neural net algorithms that learn in polynomial time from examples and queries. IEEE Trans. in Neural Networks, 2:5–19, 1991.
  2. 2.V. V. Fedorov. Theory of Optimal Experiments. Academic Press, New York, 1972.
  3. 3.E. Gardner and B. Derrida. Three unfinished works on the optimal storage capacity of networks. J. Phys., A22:1983–1994, 1989.
  4. 4.G. Györgyi and N. Tishby. Statistical theory of learning a rule. In W. K. Theumann and R. Köberle, editors, Neural Networks and Spin Glasses, pages 3–36, Singapore, 1990. World Scientific.
  5. 5.D. Haussler, M. Kearns, and R. Schapire. Bounds on the sample complexity of bayesian learning using information theory and the VC dimension. In M. K. Warmuth and L. G. Valiant, editors, Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pages 61–74, San Mateo, CA, 1991. Morgan Kaufmann.
  6. 6.W. Kinzel and P. Ruján. Improving a network generalization ability by selecting examples. Europhys. Lett., 13:473–477, 1990.
  7. 7.M. L. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, expanded edition, 1988.
  8. 8.M. Opper and D. Haussler. Generalization performance of bayes optimal classification algorithm for learning a perceptron. Phys. Rev. Lett., 66:2677–2680, 1991.
  9. 9.H. S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Phys. Rev., A45:6056–6091, 1992.
  10. 10.N. Tishby, E. Levin, and S. Solla. Consistent inference of probabilities in layered networks: Predictions and generalization. In Proc. Int. Joint Conf. on Neural Networks, volume 2, pages 403–409, Washington, DC, 1989. IEEE.
  11. 11.T. L. H. Watkin and A. Rau. Selecting examples for perceptrons. J. Phys., A25:113–121, 1992.

Citation

MLA
Seung, H. S., et al. “Query by Committee”. Proceedings of the Fifth Annual Workshop on Computational Learning Theory, 1992, pp. 287–94, https://doi.org/10.1145/130385.130417.
APA
Seung, H. S., Opper, M., & Sompolinsky, H. (1992). Query by committee. Proceedings of the Fifth Annual Workshop on Computational Learning Theory, 287–294. https://doi.org/10.1145/130385.130417
Chicago
Seung, H. S., M. Opper, and H. Sompolinsky. 1992. “Query by Committee”. Proceedings of the Fifth Annual Workshop on Computational Learning Theory, 287–94. https://doi.org/10.1145/130385.130417.
Harvard
Seung, H.S., Opper, M. and Sompolinsky, H. (1992) “Query by committee”, Proceedings of the fifth annual workshop on Computational learning theory. ACM, pp. 287–294. Available at: https://doi.org/10.1145/130385.130417.
Vancouver
1. Seung HS, Opper M, Sompolinsky H (1992) Query by committee. In: Proceedings of the fifth annual workshop on Computational learning theory. ACM, pp 287–294

BibTeX

@inproceedings{Seung_1992, series={COLT92}, title={Query by committee}, url={http://dx.doi.org/10.1145/130385.130417}, DOI={10.1145/130385.130417}, booktitle={Proceedings of the fifth annual workshop on Computational learning theory}, publisher={ACM}, author={Seung, H. S. and Opper, M. and Sompolinsky, H.}, year={1992}, month=July, pages={287–294}, collection={COLT92} }
Metadata:Crossref

Access the Paper

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

Open PDF