A conjunction describes one region: every literal in the rule must hold. A disjunctive normal form (DNF) describes a union of such regions: an input is positive if at least one term holds. Can we still learn efficiently without knowing which term generated each positive example? When each term uses at most a fixed number of variables, we can list all possible short terms and delete those contradicted by negative data. The same construction would be much larger if the width were allowed to grow.
We work in the realizable, noiseless PAC model. The proof separates two questions: an algorithm must actually find a consistent rule, and then a sample bound must control the rule selected after seeing the sample. A finite-class guarantee answers the second question but, by itself, does not provide an efficient algorithm.
Terms, width and the learning model
Fix integers and . The input domain is .
Definition 1.5.1
(Terms and width-k DNF)
A literal is or . A term is a conjunction of literals involving distinct variables, with at most literals; the empty conjunction has value 1. A width- DNF is the disjunction of any subset of these terms. The empty disjunction has value 0.
There are exactly
distinct syntactic terms in this list: choose variables and one sign for each. A DNF may use arbitrarily many of the terms.
Common mistake
(Width is not the number of terms)
Width bounds the number of literals in each term, not the number of terms. A DNF with at most terms but arbitrarily long terms is a different class; the algorithm below does not prove that class efficiently learnable.
An unknown fixed width- target labels independent samples , where are i.i.d. from an arbitrary distribution on and . For a hypothesis its population risk is
The target and distribution are fixed before the sample. The learner does not know either. Prediction error under is the goal; recovering the target's exact written formula is not required.
Delete terms contradicted by negative examples
Let be the fixed list of all terms. Start with all terms retained. For every sample point with label 0, delete every retained term that evaluates to 1 on that point. Ignore positive examples during deletion. Output the disjunction of the remaining terms; if none remains, output 0.
Theorem 1.5.2
(Consistency and one-sided prediction)
For every sample labeled by a width- target, the algorithm outputs a width- DNF consistent with the sample. Moreover, for every ,
Thus possible errors are false positives, not false negatives.
Proof
(Target terms are never deleted)
Every term appearing in the target is false on every negative example: if one were true, their disjunction would be 1 there. None of the target terms is deleted. Therefore, whenever , at least one retained target term is true at , so . This includes every positive training point. On the other hand, a negative training point deletes every term that is true on it, so none of the retained terms fires there and predicts 0. Hence is consistent on both labels. The reasoning also covers a constant-zero target, a constant-one target represented by the empty term, and samples containing no negative examples.
Proof X-ray
Which direction does the inclusion go?
Deleting terms makes a disjunction harder to satisfy. Since every target term survives, however, the output still contains all target terms and may contain extra ones. Its positive region therefore contains the target's positive region. This reverses the inclusion obtained when extra literals are retained inside a conjunction. Realizability is used exactly once, to guarantee that every target term is false on every negative example; positive examples are never inspected, yet they are fitted automatically.
Worked example 1.5.3
(Consistent but not equal to the target)
Take , and target . Observe labeled 1 and labeled 0. Initially the terms are . The negative example deletes , leaving . It fits both observations but predicts 1 at , where the target predicts 0. If assigns positive mass to , this sample can leave positive population error. Consistency is not the same as equality everywhere.
Worked example 1.5.4
(Constant targets)
Let , . If (the empty term) and the sample has only positive examples, nothing is deleted, so is the disjunction of all five terms, which contains the term and equals everywhere: it matches . If (the empty disjunction) and the sample contains the negatives and , then deletes and deletes . No term remains, so the output is the empty disjunction , again equal to . With only the single negative the output would be , a false positive at .
From finite hypotheses to a PAC bound
Theorem 1.5.5
(Distribution-free realizable guarantee)
Let . If
then, for every distribution and every width- target, the deletion learner has with probability at least over the independent examples. Logarithms are natural.
Proof
(Counting the syntactic hypotheses)
The hypothesis class is fixed before sampling. Each hypothesis corresponds to a subset of , so there are at most syntactic hypotheses; different subsets may define the same function, which only makes this upper bound looser. Fix any hypothesis with . Independence gives
A union bound over the fixed class shows that the chance that any hypothesis of risk at least is consistent is at most . On the complementary event, every consistent hypothesis has risk below . The deletion algorithm's sample-dependent output is consistent by the preceding theorem, and hence belongs to that event's conclusion.
Proof X-ray
Why a sample-dependent output is covered
Three ingredients appear in sequence. The class of at most syntactic hypotheses is fixed before sampling, which makes a union bound over it legitimate. For each fixed with , independence of the draws gives the factor . The union bound then produces one event, of probability at least , on which every consistent member of the class has small risk. The learner's output is some consistent member chosen after seeing the sample, so it lies in that event's conclusion; no independence between the output and the sample is ever assumed.
One cannot treat the selected output as if it had been fixed independently of the sample. The theorem gives a sufficient sample size, not an optimal one.
Worked example 1.5.6
(Sample size for and )
Here . Take and . The theorem requires , so examples suffice. The bound grows linearly in , which is why it stays polynomial in only when is fixed.
What “efficient” depends on
For each negative example, evaluating every term takes at most literal operations. Thus listing the terms and processing examples takes operations, including a full scan of the input bits, and space for an explicit list, excluding input storage. For fixed , , so both the algorithm and the displayed sample bound are polynomial in and .
If , then . Our explicit expansion is exponential. This observation is a limitation of this algorithm; it does not prove a computational lower bound for all possible DNF learners.
Common mistake
(A sample guarantee is not an algorithm)
A finite-class bound says that any consistent member of the class generalizes; it does not say how to find one. Brute-force search over the syntactic hypotheses is not efficient even for fixed . The deletion rule is what supplies a consistent output in time polynomial in and .
The guarantee relies on noiseless realizability, as the following example shows.
Counterexample mode
One flipped label deletes a target term
Take , , target , and uniform on . Suppose the label at is incorrectly recorded as , while is correctly labeled . The negative record at deletes every term true there: , and . The survivors are and , so . It is consistent with the recorded sample, since and . But while : a false negative, so and the one-sided conclusion fails. The survival invariant, that no target term is deleted, was exactly what the proof needed. This single example does not analyze a particular stochastic noise model.
Practice with solutions
Quick check
(Compute for and . Does this count formulas or candidate terms?)
Sum for .
Solution · Answer
candidate terms. There are at most syntactic disjunctions of these terms.
Quick check
(For , , and a negative example , which candidate terms survive that example?)
Evaluate each of at .
Solution · Answer
The terms false at survive: and . The terms are true there and are deleted.
Quick check
(Why can the learner ignore positive examples and still fit them in the realizable model?)
Where does a positive example's label come from?
Solution · Answer
Any positive example has a true target term, and no true target term can have been deleted by a correctly labeled negative example, so that term survives and makes predict 1.
Quick check
(Does the theorem show that width- DNF has at most terms? Does it give a polynomial-time algorithm when ?)
What exactly does limit?
Solution · Answer
No: limits literals per term, and the formula can have many terms. Nor does this explicit algorithm run in polynomial time for , because its list has entries.
Quick check
(Why is it invalid to apply a fixed-hypothesis consistency probability directly to the final data-dependent output?)
Which object is fixed before the sample, and which is not?
Solution · Answer
The output changes with the sample. A union bound over the fixed class provides a single high-probability event valid for every consistent candidate, including the output.