Sample Complexity of Finite Hypothesis Classes

Because the class is finite, a corresponding ERM sample-complexity upper bound is available: the sample complexity is at most 3n log(3/δ) divided by ε.

Programming

Three Alternatives in One Hypothesis

A 3-term disjunctive normal form, or 3-term DNF, is built from three conjunctions connected by OR. Each conjunction combines conditions with AND. The formula therefore accepts an input when at least one of its three conjunctions is true.

How are the literals grouped into three conjunctions, and how are those conjunctions connected by OR?

Evaluating the Three Conjunctions

Evaluation follows the logical structure directly. First evaluate the first conjunction. Then evaluate the second and third conjunctions. The overall 3-term DNF outputs 1 if at least one conjunction outputs 1. It outputs 0 only when all three conjunctions output 0. The three conjunctions are alternatives, so one successful conjunction is sufficient.

How does an input assignment move through the three conjunctions, and when does the overall formula evaluate to true?

Worked example

Checking Three Conjunction Results

Suppose a particular input assignment makes the first conjunction false, the second conjunction true, and the third conjunction false. What does the 3-term DNF output?

1
Check conjunction 1
The first conjunction is false, so it does not make the whole formula true.
2
Check conjunction 2
The second conjunction is true. This supplies the one true conjunction required by the OR structure.
3
Check conjunction 3
The third conjunction is false, but that does not change the result because another conjunction is already true.

Result

The 3-term DNF outputs 1 because one of its three conjunctions is true.

ERM Over the DNF Class

For this learning problem, ERM operates over Hₙ³DNF, the class containing all 3-term DNF formulas on the instance space {0,1}ⁿ. The ERM task is to work within this class and obtain a hypothesis with the required empirical performance on the labeled sample.

What steps would ERM need to perform to obtain a consistent 3-term DNF, and where does the computational difficulty arise?

Finite Size and Sample Bound

The class Hₙ³DNF is finite. The given upper bound on its size is 3³ⁿ. Because the class is finite, a corresponding ERM sample-complexity upper bound is available: the sample complexity is at most 3n log(3/δ) divided by ε. In this bound, ε and δ are the stated parameters.

How does the finite size of the hypothesis class connect to the stated ERM sample-complexity upper bound?

Question	Given result
How large is the hypothesis class?	At most 3³ⁿ
What ERM sample-complexity upper bound is stated?	At most 3n log(3/δ) divided by ε
Is ERM computationally efficient?	No; it is intractable even for realizable data

The statistical size and sample bound do not imply an efficient ERM implementation.

Common Reasoning Errors

Common mistake
Treating the three conjunctions as conditions that must all be true.
What it looks like
A learner concludes that the formula is false whenever one conjunction is false.
Why it fails
The conjunctions are connected by OR, so one true conjunction is sufficient.
Do this instead
Check whether at least one of the three conjunctions is true. The formula is false only when all three are false.
Common mistake
Assuming realizable data makes ERM computationally easy.
What it looks like
A learner reasons that because some hypothesis in Hₙ³DNF labels every example correctly, ERM can efficiently find it.
Why it fails
The stated result is that ERM is intractable even when the sample is realizable by a hypothesis in the class.
Do this instead
Separate existence of a consistent hypothesis from the computational difficulty of obtaining the ERM hypothesis.
Common mistake
Reading the sample-complexity bound as an efficiency guarantee.
What it looks like
A learner sees the finite-class bound and concludes that ERM is efficient to run.
Why it fails
The bound is statistical; it describes the number of examples required, not the computational cost of finding the hypothesis.
Do this instead
Report the finite-class sample bound and the ERM intractability result as two distinct conclusions.

Check Your Understanding

EASY

A 3-term DNF has three conjunctions. For one input assignment, the first and third conjunctions are false, while the second is true. What is the formula's output, and why?

Hints

Identify the connective joining the three conjunctions.
Ask whether at least one conjunction is true.

Your attempt (not saved)

MEDIUM

State the two main theoretical results for Hₙ³DNF: the given upper bound on the class size and the given ERM sample-complexity upper bound. Then state the computational result about ERM, including whether the data must be unrealizable for the difficulty to occur.

Hints

The class-size bound is expressed as 3 raised to the power 3n.
The sample bound uses n, ε, and δ.
The computational result applies even in the realizable case.

Your attempt (not saved)

Key Takeaways

1
A 3-term DNF consists of three conjunctions connected by OR.
2
One true conjunction is enough for the whole formula to output 1.
3
ERM over Hₙ³DNF is computationally intractable even when the labeled data is realizable.
4
The hypothesis class has size at most 3³ⁿ.
5
The stated ERM sample-complexity upper bound is 3n log(3/δ) divided by ε, and this statistical guarantee does not imply efficient computation.

At a glance

A 3-term DNF uses three AND-based conjunctions joined by OR.
Evaluation succeeds as soon as any one conjunction is true.
ERM for this class is intractable even for realizable samples.
The class-size upper bound is 3³ⁿ.
The given ERM sample-complexity upper bound is 3n log(3/δ) divided by ε.

Related concepts

More concepts starting with S