Concepts / Sample Complexity of Finite Hypothesis Classes

Sample Complexity of Finite Hypothesis Classes

Three conjunctions connected by OR define a 3-term DNF.

  • 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.

Conjunction 1AND of literalsORalternativeConjunction 2AND of literalsORalternativeConjunction 3AND of literals
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.

checktruefalsetruefalsetruefalseInput assignmentConjunction 1true or false1at least one trueConjunction 2true or false0all three falseConjunction 3true or false
How does an input assignment move through the three conjunctions, and when does the overall formula evaluate to true?

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?

Check conjunction 1: The first conjunction is false, so it does not make the whole formula true.

Check conjunction 2: The second conjunction is true. This supplies the one true conjunction required by the OR structure.

Check conjunction 3: The third conjunction is false, but that does not change the result because another conjunction is already true.

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.

useassesssuccessful ERMcomputational barrierLabeled sampleHₙ³DNFcandidate formulasEmpirical performanceevaluate candidatesERM hypothesisrequired performanceIntractable taskeven for realizable data
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.

formulas onbounded bysupports{0,1}ⁿinstance spaceHₙ³DNFfinite hypothesis class3³ⁿsize upper bound3n log(3/δ) dividedby εERM sample upper bound
How does the finite size of the hypothesis class connect to the stated ERM sample-complexity upper bound?
QuestionGiven 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

Common Reasoning Errors

  • Treating the three conjunctions as conditions that must all be true.

    The conjunctions are connected by OR, so one true conjunction is sufficient.

    Fix: Check whether at least one of the three conjunctions is true. The formula is false only when all three are false.

  • Assuming realizable data makes ERM computationally easy.

    The stated result is that ERM is intractable even when the sample is realizable by a hypothesis in the class.

    Fix: Separate existence of a consistent hypothesis from the computational difficulty of obtaining the ERM hypothesis.

  • Reading the sample-complexity bound as an efficiency guarantee.

    The bound is statistical; it describes the number of examples required, not the computational cost of finding the hypothesis.

    Fix: 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.
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.

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.

Key Takeaways

  • 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 Topics

  • Empirical Risk Minimization
  • Finite Hypothesis Classes
  • Realizable Learning