Motivation
In ordinary supervised learning, a learner receives labeled examples drawn from a distribution. In an active-learning model, it may have some choice about which labels to request. This can be valuable when obtaining an input is cheap but obtaining its correct label requires a costly experiment or expert. An informative question can eliminate many possible hypotheses at once; a randomly labeled example may land where every remaining hypothesis already agrees.
The phrase “the learner chooses an example” conceals several different models. Can it choose any point of the instance space, or only from a finite pool? Does it know the input distribution? Is the oracle always correct? Do unlabeled examples and computation have a cost? A label bound without these answers can be misleading. We first prove a sharp and transparent result for one particularly favorable setting, and then examine the assumptions responsible for it.
Definitions
Definition 8.1.1
(Realizable membership-query model)
Let and let the unknown target be a threshold
The learner may adaptively choose any and ask an oracle for the exact label . Each request costs one label. A later query may depend on earlier queries, labels and the learner's internal randomness. The input distribution used to evaluate error is uniform on , and is known to the learner. The output is a threshold .
The population error is . A label-complexity guarantee states how many label requests suffice to achieve a specified error and confidence, uniformly over all allowed targets. This model counts labels, not the numerical precision of a query, oracle computation, or any unlabeled sampling.
For two thresholds, the disagreement region is the interval between their parameters, apart from endpoints. Thus
The convention at equality affects only one point and has zero uniform probability. Under a different distribution, parameter distance and error probability need not agree. The learner also cannot use the target's numerical parameter directly: it must infer a sufficiently small interval containing it from the oracle responses.
Definition 8.1.2
(Version space and pool-based queries)
After a finite labeled history, the version space is the set of hypotheses in the chosen class consistent with every requested label. Its disagreement region consists of inputs on which at least two surviving hypotheses give different labels. In a pool-based model the learner receives or samples an unlabeled pool and may request labels only for points in that pool. A membership query, by contrast, may request any permitted point in . These two access models need not have the same label complexity or unlabeled-data cost.
Theorem/Proposition
Theorem 8.1.3
(Bisection learns a uniform threshold)
In the noiseless membership-query model above, there is a deterministic algorithm which, after labels, returns a threshold with population error at most for every . Thus, for , at most labels suffice for error at most , with confidence one.
Theorem 8.1.4
(A passive comparison for the same targets)
Let and , and write for the natural logarithm. Suppose a passive algorithm receives independent uniform inputs together with their threshold labels and, for every threshold in the class, outputs a classifier with error at most with probability at least . Then necessarily
This lower bound permits randomized algorithms and does not require their outputs to be thresholds. It counts labeled i.i.d. examples. It is a comparison for this particular uniform, noiseless problem, not a universal separation between all active and passive models.
Theorem 8.1.5
(A matching passive upper bound)
For the same uniform noiseless threshold class, a passive learner that returns a threshold consistent with i.i.d. labeled samples has error at most with probability at least whenever
Thus the lower bound has the correct dependence on and up to constants when .
Proof sketch or proof idea
Proof
(Bisection preserves an interval containing the target)
Initially the learner knows . At round , query . If the answer is one, the definition of the target gives , so keep . If the answer is zero, then , so keep . The second interval includes an impossible endpoint, but it still safely contains the target. In either case the interval is closed, contains and has half its previous length.
Induction gives . Output . Both parameters are in the retained interval, so their distance, and therefore uniform-distribution error, is at most . No probability calculation is needed: each possible target and each possible response sequence consistent with it satisfies the invariant. If , the bound is one and no labels are requested. The midpoint is at distance at most half the interval length from every point in the interval; outputting it gives the sharper bound , but the stated bound is enough to show logarithmic dependence on .
Concept lensCombinatorial
Bisection reads off binary digits
Each answer of bisection is one binary digit of the target. Answer one means lies in the left half, digit ; answer zero means the right half, digit . After queries the learner holds the first digits of (for , in the expansion not ending in zeros), so error is the price of digits. For the answers one, zero, one, zero spell .
Proof
(Why passive samples can miss the decisive interval)
Take and . Their labels disagree on an interval of uniform mass . Let be the event that none of the inputs falls there. Then , and conditional on the distribution of the entire labeled dataset is the same under both targets. The same is true after including any independent algorithmic randomness.
The two target classifiers disagree on mass . For any output classifier , the inclusion gives
Consequently one output cannot have error at most for both targets. On the common conditional distribution given , the sum of the two target-specific failure probabilities is therefore at least one. Multiplying by shows that at least one unconditional failure probability is at least . A uniform failure guarantee requires ; taking logarithms yields the first inequality.
For , . With , we have , yielding the second inequality. The lower bound is on labeled observations; it does not say that the active model obtains physical labels without cost or that every distribution permits bisection.
For the passive upper bound, choose any threshold consistent with the sample. If its error exceeds , it lies more than to the left or right of the true parameter. In the first case the sample contains no input in ; in the second it contains no input in . A direction is impossible when the corresponding interval would leave . Every relevant interval has uniform mass , so the probability of a bad consistent threshold is at most . The displayed sample size makes this at most . This argument holds for any consistent selection, including one chosen after seeing the data.
Proof X-ray
What creates the label saving?
A query at the midpoint is chosen after the current uncertainty interval is known, so either answer discards half of that interval. A passive sample can repeatedly miss the small interval on which two plausible targets disagree. The two proofs compare different information-access rules: arbitrary noiseless membership queries against i.i.d. labeled examples. The conclusion should travel with those assumptions.
Worked examples
Worked example 8.1.6
(Bisection with an unknown threshold)
Suppose the true threshold is , unknown to the learner. The first query at returns one, leaving . The next at returns zero, leaving . Querying returns one, leaving ; querying returns zero, leaving .
After four labels the interval length is . Returning its left endpoint gives error . The algorithm does not need to know that this is the actual error; the length of the interval is its certificate. The midpoint would give error , at most .
Worked example 8.1.7
(A concrete accuracy request)
To guarantee uniform error at most using the stated left-endpoint algorithm, choose . The final interval has length , no matter where the threshold lies. The passive lower bound at confidence says that any uniformly successful passive algorithm needs at least
labeled samples, hence at least . These are sufficient and necessary bounds for different procedures, not exact optima. The passive count depends on a failure allowance, while the bisection guarantee holds for every target and response history.
Worked example 8.1.8
(A pool can hide the useful query)
Suppose an unlabeled pool contains only , and the target threshold is either or . Every pool label is the same under the two targets: the first two points are labeled zero and the last two one. No choice of labels from this fixed pool can distinguish the targets, even if all four are requested. A membership query at separates them immediately. The two targets disagree on uniform mass , so no one classifier can have error below for both. More unlabeled points may help, but their acquisition and the assumptions on how they are drawn must be counted separately.
Counterexample mode
A query does not always halve the version space
Let and let for , where . A query at asks whether the target is the single hypothesis . If the answer is zero, only that one candidate is eliminated. A deterministic exact-identification algorithm can be forced to receive zero answers until candidates have been eliminated; the remaining candidate is then known. Thus queries may be required, although bisection among ordered thresholds takes at most suitably chosen membership queries. This example establishes a worst-case cost for exact identification; it does not itself establish a lower bound for approximate learning. Active choice does not itself guarantee a balanced split.
Common mistakes
Common mistake
(An uncertainty interval is not automatically a probability bound)
The bisection proof uses a uniform input distribution to turn interval length into error probability. If all probability mass is concentrated at a point inside a short interval, two thresholds on opposite sides of that point can disagree on the entire mass. Under an arbitrary unknown distribution, a short parameter interval alone need not imply small population error.
Common mistake
(A perfect oracle is an assumption, not a consequence)
One wrong answer can discard the true threshold, after which the interval invariant fails. Repeating queries and taking a majority can be useful under an explicitly specified independent noise model, but arbitrary or correlated errors do not automatically disappear by repetition. Likewise, querying the midpoint requires membership-query access; a fixed pool may not contain it.
Label complexity also omits other resources unless the model includes them. Identifying a narrow interval may require high-precision query locations. A pool-based procedure may inspect many unlabeled inputs before finding a useful one. A generalization result must say whether its probability is over sample generation, oracle noise, algorithm randomness, or some combination. Confidence one in the theorem follows specifically from noiseless answers and the deterministic geometric invariant.
Summary
An active learner selects labels using previous answers. Under noiseless arbitrary membership queries and a uniform input distribution, threshold bisection gives a logarithmic label bound. A passive sample can miss the region separating two targets, producing the stated lower bound in this example. For , that bound is at least . A different hypothesis class, a restricted pool, a different distribution or noisy labels may remove the advantage.
Exercises
Quick check
(Run three bisection queries for a threshold , starting from . Give the interval after each query and the error of the final left-endpoint hypothesis under the uniform distribution.)
Remember that label one means .
Solution · Answer
Queries at , and produce labels zero, one and zero. The intervals are , and . The left-endpoint hypothesis has error .
Quick check
(For , how many labels does the stated left-endpoint theorem guarantee? What bound on error follows if the midpoint of the final interval is returned instead?)
Use .
Solution · Answer
Five labels suffice because . The final interval has length , so its midpoint is at distance at most from the target and has uniform error at most .
Quick check
(For thresholds and , calculate the probability that independent uniform inputs all receive identical labels under the two targets. Explain why the same observed labeled data cannot establish which target generated it on this event.)
Find the interval on which the two thresholds disagree.
Solution · Answer
The targets disagree on , of mass . The probability all inputs avoid it is . On that event both targets assign the same label to every observed input, so the data are compatible with both; the data alone cannot determine which target is correct. A prior assigning positive probability to both targets does not turn this common transcript into certainty.
Quick check
(In the singleton class of the counterexample, suppose . Give a deterministic strategy requiring at most four exact labels to identify the target, and explain why three do not suffice in the worst case.)
Think about what an adversary answers when a query returns zero.
Solution · Answer
Query four distinct points. If a query returns one, its point identifies the target; if all return zero, the fifth hypothesis remains. Against any deterministic strategy making at most three queries, an adversary can answer zero and leave at least two targets consistent with the transcript. The same output cannot identify both, so three queries cannot guarantee exact identification.