Concepts / Minimum Description Length and Hypothesis Hierarchies

Minimum Description Length and Hypothesis Hierarchies

PAC-Bayes bounds define a hierarchy over a hypothesis class H.

  • Programming

From One Hypothesis to a Distribution

A learning algorithm does not necessarily have to return one hypothesis. In the PAC-Bayes view, it can work with a distribution over a hypothesis class H. This changes the central question: instead of asking only which single hypothesis was selected, we also ask how probability is distributed across the available hypotheses before and after learning.

PAC-Bayes bounds connect two distributional views of the same hypothesis class: a prior hierarchy before learning and a posterior distribution produced by learning.

containscontainscontainsHhypothesis classh1hypothesish3hypothesish2hypothesis
How does a PAC-Bayes view organize hypotheses into levels within the hypothesis class H?

The Hypothesis Class H

The hypothesis class H is the collection over which the distributional view operates. Individual hypotheses are members of H. The prior assigns probability or density to these members before learning, and the posterior is another distribution over H that is produced by the learning process.

containscontainsassigns probabilityassigns probabilityassigns probabilityassigns probabilityHhypothesis classh1hypothesish2hypothesisPprior distributionQposterior distribution
What does the hypothesis class H contain, and how do distributions relate to its individual hypotheses?

Before Learning: The Prior P

The prior distribution P assigns a probability or density P(h) to each hypothesis h before learning. Its role is to describe the initial hierarchy over the hypotheses in H.

DistributionWhen it appliesWhat it describes
PBefore learningThe prior hierarchy over hypotheses
QAfter the learning process produces itThe distribution used by the learned randomized rule
assignsassignsPbefore learningP(h)probability or densityQafter learningQ(h)posterior probability
What is the difference between the prior distribution before seeing data and the posterior probability after the learning process?

Learning Changes the Distribution

Learning changes which distribution is used to select hypotheses. The prior P is the distribution available before learning. The learning algorithm produces a posterior Q over H. The posterior does not have to be understood as one final hypothesis; it can describe how the algorithm distributes probability across the hypothesis class after learning.

learning usesproducesPprior distributionObserved datalearning inputQposterior distribution
How does learning change the distribution used to select hypotheses?

Tracking a Distributional Update

Suppose a hypothesis class H contains h1, h2, and h3. Describe the roles of P and Q without treating the learner's result as a single hypothesis.

Initial organization: Before learning, P assigns a probability or density to each of h1, h2, and h3. This is the prior organization of the class.

Learning step: The learning algorithm uses the learning situation to produce a posterior distribution Q over the same class H.

Final interpretation: The result is Q, a distribution over hypotheses, rather than necessarily one selected member of H.

The class H stays as the space of available hypotheses, while the distribution used to select among them changes from P to Q.

Randomized Prediction from Q

A posterior probability Q defines a randomized prediction rule. For an input x, the rule selects a hypothesis h according to Q and then predicts h(x). The prediction process therefore has two conceptual stages: select a hypothesis using Q, then apply that hypothesis to x.

samplesapplies hprovides xQposterior distributionSelect haccording to Qxinputh(x)prediction
How does a posterior probability distribution select or weight hypotheses to produce a randomized prediction?

Generated example: imagine H contains three candidate rules for classifying an input. Q gives each rule a probability. For a particular input x, the randomized rule selects one candidate according to Q and returns that candidate's prediction h(x). The important point is that Q governs the selection process; the learner need not output only one permanent rule.

What the PAC-Bayes Connection Adds

PAC-Bayes bounds connect the prior and posterior views rather than focusing only on a single selected hypothesis. The prior describes the hierarchy before learning, while the posterior describes the distribution produced by learning. This connection lets the analysis discuss both the initial organization of H and the algorithm's distributional result.

organized bydistributed overprovides priorprovides posteriordescribes learned behaviorconnects to analysisHhypothesis classPprior hierarchyEmpirical performanceobserved behaviorQlearned distributionP versus Qdistributional connection
How are the prior, posterior, empirical behavior, and complexity-related comparison connected in a PAC-Bayes view?

Common Interpretation Errors

  • Treating the learner's result as necessarily one hypothesis.

    The PAC-Bayes view allows the learning algorithm to return a posterior distribution Q over H.

    Fix: Describe Q as the learned distribution, and explain prediction as selecting h according to Q before computing h(x).

  • Using P and Q as interchangeable names.

    P and Q have different roles and timing.

    Fix: Use P for the prior distribution before learning and Q for the posterior distribution produced by learning.

  • Saying that Q directly predicts without mentioning hypothesis selection.

    The randomized prediction rule selects h according to Q and then predicts h(x).

    Fix: State both stages: select h according to Q, then apply h to x.

  • Describing the PAC-Bayes view only as a ranking of individual hypotheses.

    PAC-Bayes bounds connect the prior and posterior distributional views.

    Fix: Explain how P organizes H before learning and how Q describes the result after learning.

Practice: Trace P to Q

MEDIUM

A hypothesis class H contains h1, h2, and h3. Write a short explanation that traces the system from the prior stage to a prediction for an input x. Your explanation must identify what P does, what learning produces, what Q does, and why the final prediction is written as h(x).

Hints
  • Start by stating when P assigns probability or density.
  • Name Q as the posterior distribution produced by learning.
  • Describe selection of h according to Q before applying h to x.

What do you think happens?

If a learning algorithm returns a posterior distribution Q over H, must it also return one single hypothesis as its only result?

  • Yes, always
  • No, not necessarily
  • Only before learning
Reveal answer

Answer: No, not necessarily

In the PAC-Bayes view, the algorithm can work with and return a distribution over the hypothesis class. A randomized prediction rule can select h according to Q and then predict h(x).

Summary

  1. PAC-Bayes bounds define a hierarchy over a hypothesis class H.
  2. The prior P assigns probability or density to hypotheses before learning.
  3. The learning algorithm produces a posterior distribution Q over H rather than necessarily one hypothesis.
  4. Q defines a randomized prediction rule: select h according to Q and predict h(x).
  5. PAC-Bayes bounds connect the prior hierarchy with the posterior distribution produced by learning.

Key Takeaways

  • PAC-Bayes bounds organize hypotheses in H through a distributional hierarchy.
  • P is the prior distribution assigned before learning; Q is the posterior distribution produced by learning.
  • A posterior distribution can define a randomized rule that selects h according to Q and predicts h(x).
  • The central learning change is a shift from the prior distribution P to the learned posterior distribution Q.
  • The PAC-Bayes perspective connects these two distributions instead of requiring analysis of only one selected hypothesis.

Related Topics

  • Hypothesis Classes
  • Randomized Prediction Rules
  • Prior and Posterior Distributions
  • PAC-Bayes Learning Theory