A conjunction has one common requirement: every retained literal must be true. A decision list can instead make a sequence of exceptions: if a particular literal is true, give one label; otherwise try the next rule. The first matching rule wins. We will find a consistent list efficiently from realizable data and then prove that its population error is small with high probability.
Rules, order and the learning task
Fix and domain . The available literals are and for .
Definition 1.4.1
(Signed-literal decision list)
A signed-literal decision list has rules
followed by a default label . On input , return for the first literal that is true; if none is true, return . The empty list is a constant classifier.
Repeating a literal later never changes the function, because inputs satisfying it already stopped at its first appearance; we may therefore restrict attention to lists with distinct literals and .
Concept lensStructural
A decision list is a lopsided decision tree
Draw each rule as a node testing : if true, go to a leaf labeled ; if false, go to the next node. The last false branch ends in a leaf labeled . A list with rules is exactly such a tree with tests, one leaf hanging off each test, and its path to the default has length .
Assume a fixed target list labels the data noiselessly: are i.i.d. from an arbitrary distribution on and almost surely. The sample contains labeled examples. Risk means on an independent input .
A learner that peels off homogeneous rules
Keep a set of active sample indices, initially all indices, and an initially empty output list. Repeat:
- If no indices remain, append default label 0 and stop. If all remaining labels equal the same , append default and stop.
- Otherwise, search the literals in a fixed order for one that is true on at least one active example and for which all active examples satisfying it have the same label .
- Append , remove all active examples satisfying , and repeat. If no such literal exists, report failure.
The nonempty-coverage condition prevents a rule from making no progress. A previously chosen literal is false on every remaining example and cannot be chosen again. Since the active set only shrinks and every selected literal has nonempty coverage, there are at most non-default rules. With unit-cost bit access, one scan per literal checks nonempty coverage and homogeneity, giving time. Active-index storage takes and the output takes words, excluding the sample.
Theorem 1.4.2
(Realizable decision lists are learned consistently)
If a single target list labels every sample correctly, the procedure never reports failure, terminates, and outputs a list consistent with the entire sample.
Proof
(An invariant and an eligible literal)
After each round the active examples are exactly those satisfying none of the emitted literals, every removed example is correctly labeled by the emitted prefix, and the target still labels every active example. This invariant holds initially and is preserved by removing a homogeneous covered set. Step 2 is reached only when both labels occur among the active examples. At least one active example must fire a rule of the target: otherwise every active example would receive the same target default label. Choose the earliest target rule whose literal fires on any active example. No earlier target rule fires on any active example, so every active example satisfying this literal reaches that rule and has its label. The literal therefore covers a nonempty homogeneous set, and the search succeeds. This witness argument does not depend on the search order; a fixed order makes the procedure deterministic.
A chosen rule labels exactly the examples removed at that round; all previously emitted rules are false on every then-active example, so later rules cannot change those predictions. The default labels all examples left when the procedure stops. Each non-default step removes at least one example and cannot reuse a literal, so the algorithm terminates and its output is consistent.
Proof X-ray
The earliest target rule is only a witness
The proof uses the unknown target to show that some eligible literal exists. The algorithm may choose a different eligible literal earlier in its fixed search order. It need not recover the target's syntax; it needs only to classify the observed examples correctly.
Worked example 1.4.3
(Two consistent lists from one sample)
On two bits, suppose the active sample is , , , . It is labeled by “if then 1; else if then 0; else 1.” If the search selects first, it removes the first two examples with label 1; on the two remaining examples it can choose with label 0 and then use default 1. Alternatively, is eligible first with label 1; it removes and . The remaining examples and can be handled by “if then 1; else 0,” yielding a different consistent list.
Common mistake
(Using the majority label instead of requiring a homogeneous cover)
In the same sample, the literal is true on and , so its covered set contains both labels. Appending for either would misclassify one of these two examples, and removing both would lock that error in, since removed examples are never revisited. The consistency invariant requires every covered active example to have the same label.
From consistency to a PAC guarantee
Let be the sample-independent set of syntactic lists with distinct literals, at most rules, and either default. The learner outputs a member of because it never reuses a literal. There are at most positions in a list. For a crude fixed class count, at each rule position there are at most literal choices and two output choices. Allowing repetitions in this count can only increase it. Including two defaults and summing over lengths,
Theorem 1.4.4
(A distribution-free realizable bound)
Assume and almost surely. For , if
then with probability at least the output has . Logarithms are natural.
Proof
(A union bound over the fixed class)
For any fixed list with , the probability it makes no mistake on the i.i.d. sample is . The probability that any bad list in the fixed class is consistent is at most by a union bound. On the probability-one realizability event the learner is consistent, so outside that bad event its risk is at most . The union is over the fixed finite set of syntactic lists; it is not an assumption that the sample-dependent output is fixed.
Worked example 1.4.5
(A concrete sample size)
For the count is . With and the theorem requires , so examples suffice. The crude bound is larger than by a factor of about , which adds only about to the logarithm in the theorem.
Worked example 1.4.6
(A sample with a single label)
Let and let the target be “if then 1; else 0.” Suppose the sample is and . In the first round all remaining labels equal , so the learner appends the default and stops with the empty list: the constant classifier . It is consistent but differs from the target on every input with , so its risk is . The PAC bound says that with as above such a misleading sample is unlikely unless that probability is small.
The displayed count is deliberately simple rather than exact. It gives a sufficient sample size of order and combines with the polynomial-time consistency algorithm. It does not say the learned list equals the target on inputs outside the sample or that this sample bound is optimal.
When the assumptions fail
Counterexample mode
Conflicting labels can stop the search
Take two copies of the same input with opposite labels. The active labels are not all equal, and every literal that covers either copy covers both, so no covering literal has homogeneous labels. The algorithm reports failure. No deterministic decision list can fit that sample, so the realizability hypothesis has genuinely failed. This example does not characterize the behavior under every noise model.
Common mistake
(A decision list is not a set of rules)
Order matters even without noise. “If then 1; else if then 0; else 1” predicts 1 at . Reversing the two rules predicts 0 there. A list is not an unordered set of independently valid rules.
Practice with solutions
Quick check
(For the two-bit example, what does the target list predict on and on ?)
Find the first true literal in the order .
Solution · Answer
At the first rule fires and returns 1; at the first rule is false, so the second fires and returns 0.
Quick check
(If all active labels are 0, what must the algorithm output next, and why is it consistent on the active examples?)
Look at step 1 of the procedure.
Solution · Answer
It must stop with default 0. The active examples satisfy no earlier emitted literal, so all receive 0 from the default, while the prefix correctly handled the removed examples.
Quick check
(Why can a literal selected earlier never be selected in a later round?)
What happened to every example satisfying it?
Solution · Answer
Every active example satisfying it was removed, and the active set only shrinks; it therefore has empty coverage and cannot meet the nonempty-coverage rule later.
Quick check
(If a fixed candidate list has population risk , what is the probability that it is consistent with independent samples?)
Each sample must be classified correctly.
Solution · Answer
, since each independent example is classified correctly with probability .
Quick check
(Why is the union bound needed when the output list depends on the sample?)
Which probability bound is valid only for a list fixed in advance?
Solution · Answer
A fixed-list probability bound cannot be applied directly to a list selected after seeing the sample. The union bound gives one event that controls every list in the fixed class, including the selected one.