A finite-class theorem can promise that a consistent hypothesis generalizes, but it may leave the computational task of finding one unresolved. Monotone conjunctions offer a case where we can see both parts: a simple algorithm finds a consistent rule, and an independent-sample argument bounds its population error. The result is distribution-free but relies on noiseless realizability.
The model and the deletion rule
Definition 1.2.1
(Monotone conjunction, target and risk)
Let , , and for define the monotone conjunction
The empty conjunction is the constant 1. The unknown target is for some fixed , and are i.i.d. from an arbitrary fixed distribution on , with noiseless labels . For a candidate , its risk is .
The learner starts with . For each example labeled 1, it removes every coordinate for which . It ignores negative examples for the update and outputs . The computation inspects at most coordinate values and uses working storage, apart from the sample itself. If there are no positive examples, it outputs the conjunction of all variables.
Worked example 1.2.2
(Deleting coordinates from positive examples)
For , take target . The positive examples and delete coordinates 4 and 2, respectively, leaving . The negative example is not needed for the deletion step; the resulting conjunction labels it zero. A different sample could leave extra coordinates, even if it is also consistent.
Worked example 1.2.3
(No positive example: the all-variables conjunction)
Let and let the target be . Suppose the sample contains only the negatives and . No coordinate is deleted, so and the output is . It labels both negatives 0, because each has a zero among the coordinates, so it is consistent. Its risk is the probability of , that is, of the positives of the target other than . If puts most of its mass there, the risk is large. This is not a contradiction: such a sample is exactly the unlikely event in which the sample size is too small to have seen a positive, and the theorem below makes that event rare once is large enough.
Worked example 1.2.4
(Evaluating the sample-size bound)
Take , and . Then and , so
The smallest integer that the theorem certifies is . The class has members, yet is only a few hundred: the bound grows linearly in , because the dependence on the class is through . Halving to doubles the requirement to , that is , whereas squaring to adds only examples.
Why the output is consistent
Lemma 1.2.5
(Invariant of the deletion learner)
In the noiseless realizable model, the set maintained by the deletion learner satisfies at every stage. Consequently the output is consistent with all examples, and implies for every .
Proof
(Target coordinates are never deleted)
Every true positive has for every . Consequently none of the target coordinates can be deleted, so at every stage. At the end every observed positive has value 1 in every retained coordinate and is labeled 1 by . Every observed negative has at least one target coordinate equal to zero; since all target coordinates remain, labels it 0. Thus the output is consistent with all examples, even if there are no positive examples.
Moreover, implies . The learner can make false-negative errors by retaining unnecessary variables, but under the stated assumptions it cannot make false-positive errors. This one-sided error is an invariant of this algorithm, not a property of an arbitrary consistent learner.
Proof X-ray
Retaining extra variables narrows the positive region
The only non-obvious move is to read the deletion rule as a statement about indices: a coordinate is removed only when some labeled-1 example has a zero there. Two hypotheses are used. Noiseless labels make every labeled-1 example a genuine positive of the target, so all target coordinates equal 1 on it and none is removed. Realizability makes every negative example violate the target, so it has a zero on some target coordinate.
The two inclusions point in opposite directions. On index sets, . On positive regions, , because adding a variable to a conjunction makes it harder to satisfy. The first inclusion gives consistency on the negatives; the second gives the absence of false positives. Confusing the directions reverses the conclusion about false positives and false negatives.
The argument closes because every retained coordinate has never been seen equal to 0 on a positive example, while the target coordinates are never removed. If a single positive label is corrupted, the first step fails, as the end of the section on prediction versus identification shows.
A distribution-free sample guarantee
Theorem 1.2.6
(A concrete realizable PAC guarantee)
Fix and . If
then, with probability at least over the sample, the output satisfies . Logarithms are natural. The bound holds for every and every target conjunction in the class.
Proof
(Union bound over all conjunctions)
There are conjunctions, including the empty one. Fix a candidate with . On each independent labeled example it agrees with the target with probability at most , so the probability that it is consistent with all examples is at most . A union bound over the fixed finite class says that the probability any such bad candidate is consistent is at most . On the complementary event every consistent candidate has risk below . The deletion learner's output is consistent, so it obeys that bound.
The bound is uniform over distributions, not conditional on a particular favorable sample. It uses the finite class only in the proof; the algorithm does not enumerate all candidates. The guarantee concerns predictive error, not exact recovery of the target's set of variables.
A second proof that exposes the missed evidence. For each coordinate let . Fix any coordinate before drawing the sample. If , each independent example has probability at least of presenting evidence that deletes it. The probability that this coordinate survives all examples is at most . If no such coordinate survives, a false negative must have and a retained coordinate equal to 0, so a union bound gives risk strictly below . Hence failure probability is at most . This alternative can be looser than the finite-class bound, but makes the role of rare positives explicit. The events being union-bounded need not be independent; independence is used across the examples.
Prediction versus identifying the target
Counterexample mode
Correlated variables prevent exact identification
Take and a distribution supported on and . Targets and give the same labels on this support, although they differ at and . No amount of i.i.d. labeled data from this distribution distinguishes which target was chosen. Either rule can have zero risk under . Distribution-free PAC accuracy does not promise identification of the target representation or correctness at points outside the distribution's support.
Common mistake
(Deleting coordinates on negative examples)
It is tempting to prune with negatives as well, deleting each coordinate at which a negative example is 0. This fails already on the example above: for the target , the negative is 0 only at coordinate 3, a target coordinate, so the rule would delete a variable that the target needs. A negative example says that some target coordinate is 0, not which one. Only positives are informative for deletion.
Common mistake
(Reading the size of the class as the running time or the sample size)
The proof counts all conjunctions, but the learner never lists them, and the sample size depends on the class only through . The running time is and the sample size is linear in . The size of the finite class enters the analysis, not the algorithm.
Rare evidence can also delay learning without violating the theorem. Let the target be the empty conjunction, and put probability on and on . If all draws are , which occurs with probability , no coordinate is deleted and the output has risk . A draw of is positive and deletes every coordinate, giving the constant-one target. A high-probability bound makes misleading samples sufficiently rare; it does not declare them impossible.
The proof breaks under arbitrary label noise. For with target , a corrupted positive label at input 0 deletes the true variable, after which the output is constant 1 and can make false-positive errors. A noisy model needs its own assumptions and analysis.
Practice with solutions
Quick check
(For , process positive examples and . What is the output, and how does it label ?)
Delete the coordinates at which each positive is 0.
Solution · Answer
The first positive deletes coordinate 3 and the second deletes coordinate 2. The output is , which labels as 0.
Quick check
(With , , and , give the theorem's sufficient integer sample size.)
Evaluate the bound with natural logarithms and round up.
Solution · Answer
Take .
Quick check
(If no positive example is observed, why is the output still consistent in the noiseless realizable model?)
Look at what a negative example forces on the target coordinates.
Solution · Answer
Every negative example has a zero in a target coordinate, and all target coordinates remain in the output, so the output labels each negative 0.
Quick check
(Does zero risk under imply that the selected index set equals ? Give a reason.)
Compare with the two-variable example above.
Solution · Answer
No. Correlated coordinates can produce distinct conjunctions that agree everywhere on the support of , as in the two-variable example.