Minimum Description Length and Hypothesis Hierarchies
PAC-Bayes bounds connect two distributional views of the same hypothesis class: a prior hierarchy before learning and a posterior distribution produced by learning.
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.
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.
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.
| Distribution | When it applies | What it describes |
|---|---|---|
| P | Before learning | The prior hierarchy over hypotheses |
| Q | After the learning process produces it | The distribution used by the learned randomized rule |
The essential distinction is the role and timing of P and Q.
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.
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.
- 1Initial organization
Before learning, P assigns a probability or density to each of h1, h2, and h3. This is the prior organization of the class.
- 2Learning step
The learning algorithm uses the learning situation to produce a posterior distribution Q over the same class H.
- 3Final 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.
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.
Common Interpretation Errors
Common mistake Treating the learner's result as necessarily one hypothesis.
What it looks likeAssuming that learning must return h1 and discard every other member of H.
Why it failsThe PAC-Bayes view allows the learning algorithm to return a posterior distribution Q over H.
Do this insteadDescribe Q as the learned distribution, and explain prediction as selecting h according to Q before computing h(x).
Common mistake Using P and Q as interchangeable names.
What it looks likeCalling the distribution used after learning the prior.
Why it failsP and Q have different roles and timing.
Do this insteadUse P for the prior distribution before learning and Q for the posterior distribution produced by learning.
Common mistake Saying that Q directly predicts without mentioning hypothesis selection.
What it looks likeWriting that Q predicts x, with no reference to a selected h.
Why it failsThe randomized prediction rule selects h according to Q and then predicts h(x).
Do this insteadState both stages: select h according to Q, then apply h to x.
Common mistake Describing the PAC-Bayes view only as a ranking of individual hypotheses.
What it looks likeDiscussing which single hypothesis wins while ignoring the distributions.
Why it failsPAC-Bayes bounds connect the prior and posterior distributional views.
Do this insteadExplain how P organizes H before learning and how Q describes the result after learning.
Practice: Trace P to Q
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?
Reveal 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
- 1PAC-Bayes bounds define a hierarchy over a hypothesis class H.
- 2The prior P assigns probability or density to hypotheses before learning.
- 3The learning algorithm produces a posterior distribution Q over H rather than necessarily one hypothesis.
- 4Q defines a randomized prediction rule: select h according to Q and predict h(x).
- 5PAC-Bayes bounds connect the prior hierarchy with the posterior distribution produced by learning.
At a glance
- 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.