Minimum Description Length
SRM divides the overall hypothesis class H into classes H_n and represents H as their union.
Why Organize Hypotheses
Suppose you have chosen a hypothesis class H because you believe it contains a useful predictor. That choice already expresses prior knowledge: hypotheses outside H are not being considered. Structural Risk Minimization, or SRM, adds another layer of preference. Rather than treating every member of H as equally preferred, SRM organizes H into smaller classes and records how strongly each class is preferred.
The central idea is to compare candidate hypotheses through an upper bound on their true risk. SRM therefore balances the observed performance of a hypothesis with the preference assigned to the class containing it. The method is not defined as simply choosing the hypothesis with the smallest observed error.
The Class Structure
SRM divides the overall hypothesis class H into classes H_n and represents H as their union. Each hypothesis considered by SRM belongs to one of the organized classes in this structure.
The notation H_n identifies the individual classes in the organization. The overall class H is not replaced by one selected subclass at the start. Instead, SRM keeps the whole structure and compares hypotheses through the classes to which they belong.
Assigning a Hypothesis to a Class
Consider an SRM organization with the overall class H and classes H_1, H_2, and H_3. A candidate hypothesis has been placed in H_2. What does that tell you about the SRM structure?
Locate the candidate: The candidate is a member of H_2, one of the classes used to organize H.
Retain the overall structure: The candidate's membership in H_2 does not remove H_1 or H_3 from the SRM organization. The classes remain parts of the organization of H.
Apply the class preference: The weight assigned to H_2 is the preference value relevant to this candidate's class.
The hypothesis is evaluated as a member of H_2, so the class-level preference and bound associated with H_2 matter for its SRM evaluation.
Weights as Preferences
SRM uses a weight function written as w : N → [0, 1]. This function assigns a preference value to each class H_n. A larger weight means a stronger preference for that class. The assigned weights must have a total no greater than 1.
| SRM element | Role |
|---|---|
| H_n | One hypothesis class in the organization |
| w | The weight function |
| w(H_n) | The preference value assigned to class H_n |
| Total weights | |
| Must have a total no greater than 1 |
The weight function records class-level preferences in SRM.
Generated illustration: imagine that one class receives a larger weight than another. Within the SRM setup, that larger value expresses a stronger preference for the first class. The weight is therefore not a score for one individual hypothesis; it is a preference attached to the entire class H_n.
Bound Minimization
The central SRM rule is bound minimization. SRM does not simply select a hypothesis because it has the smallest observed error on the available sample. Instead, it seeks a hypothesis that minimizes a specified upper bound on the true risk.
This distinction matters because empirical performance is only the performance observed on the sample. SRM brings the class organization and its preferences into the decision through the bound. A hypothesis with a better observed result is not automatically the SRM choice if the relevant upper bound is larger.
Choosing by the Bound
Generated illustration: suppose two candidate hypotheses have different observed errors. Hypothesis A has the lower observed error, while Hypothesis B has the higher observed error. The specified upper bound for A is larger than the specified upper bound for B. Which candidate follows the SRM rule?
Separate the two criteria: The observed error describes empirical performance, while the specified upper bound is the quantity used by the SRM rule.
Compare the bounds: The SRM rule compares the upper bounds rather than selecting solely by the lower observed error.
Select the minimizing candidate: Because B has the smaller specified upper bound in this illustration, B is the SRM choice.
SRM can choose Hypothesis B even though Hypothesis A has the lower observed error, because SRM minimizes the specified upper bound.
Uniform Convergence
The SRM theorem assumes that every class H_n satisfies the uniform convergence property. The source associates this property with a sample complexity function written as m UC H_n. This condition is supplied separately for each class in the SRM structure.
Uniform convergence is the condition that supports the connection between performance measured on the sample and the expected performance represented by the SRM guarantee. Because the assumption is made for every H_n, the guarantee is tied to the complete class structure rather than to only one selected class.
Common Mistakes
Treating H as one undivided class in SRM.
SRM organizes H into classes H_n and assigns preferences at the class level.
Fix:
First identify the relevant H_n, then consider its assigned weight and bound.Assuming the weight function assigns a value to each individual hypothesis.
The weight function assigns a preference value to each hypothesis class H_n.
Fix:
Treat w(H_n) as the preference attached to the class containing the hypothesis.Selecting the hypothesis with the smallest empirical error automatically.
The central SRM rule is bound minimization, not empirical-performance minimization alone.
Fix:
Compare the specified upper bounds on true risk.Ignoring the uniform convergence assumption.
The theorem assumes that every H_n satisfies the uniform convergence property with an associated sample complexity function.
Fix:
Remember that the condition is supplied separately for each class in the structure.
Practice Check
An SRM setup contains the overall class H, subclasses H_1 and H_2, and a weight function w. A candidate hypothesis belongs to H_2. Explain: 1) what the candidate's class is, 2) what w(H_2) represents, 3) why the candidate should be evaluated through a bound rather than empirical error alone, and 4) which theorem condition must hold for H_2.
Hints
- Start by identifying the subclass containing the candidate.
- The weight is a preference value for the class, not for an isolated hypothesis.
- The SRM rule minimizes a specified upper bound on true risk.
- The theorem assumes uniform convergence for every H_n.
What do you think happens?
Two candidates have different empirical errors. Candidate A has the lower observed error, but Candidate B has the smaller specified upper bound. Which candidate does the SRM rule select?
Reveal answer
Answer: Candidate B, because SRM minimizes the specified upper bound.
The SRM rule is bound minimization. It does not select solely by the smallest observed error.
Key Takeaways
- SRM organizes the overall hypothesis class H into subclasses H_n and represents H as their union.
- The weight function w assigns each class H_n a preference value in [0, 1], with total weights no greater than 1.
- A larger class weight expresses a stronger preference for that class.
- SRM chooses by minimizing a specified upper bound on true risk rather than by considering empirical performance alone.
- The SRM theorem assumes uniform convergence for every H_n, with an associated sample complexity function for each class.
Key Takeaways
- SRM adds structured prior preferences to an overall hypothesis class H.
- The class H is organized into subclasses H_n, and each hypothesis belongs to one of those classes.
- The weight function assigns a preference value to every H_n; larger weights indicate stronger preference, and the total is no greater than 1.
- SRM minimizes an upper bound on true risk instead of selecting solely by observed sample error.
- Uniform convergence for every H_n supports the connection between sample performance and the SRM guarantee.