Choosing both a model and a classifier
A larger hypothesis class can fit a sample better, but that extra flexibility can make the fitted error optimistic. For nested classes, the minimum training error cannot increase with the class, even when the selected classifier has worse population error. Structural risk minimization addresses the choice by adding a complexity allowance to each class's empirical error, then selecting a class and classifier together.
The difficulty is that the selected class depends on the same sample used to assess it. A bound that holds for one class fixed in advance cannot simply be applied to whichever class wins. We allocate confidence across the classes first, so that all the needed comparisons hold simultaneously. The result below applies to arbitrary labels, including distributions not realizable by any class.
Classes, risks and weights
Definition 3.1.1
(Weighted finite classes and class radius)
Let be i.i.d. from a fixed distribution on a measurable instance space and binary labels. Let be a fixed countable list of finite, nonempty classes of measurable classifiers . The classes may overlap and need not be nested. Fix weights before seeing the sample, with .
For define
For , assign class the radius
All logarithms are natural. Small weights allocate less failure probability to a class and therefore give it a larger penalty. The weights are not probabilities that the classes are true. The radius can exceed one; it remains a valid, though uninformative, deviation bound.
Concept lensAlgorithmic
The radius as a description length
Split the logarithm: . The first term is the cost of naming class in a code with lengths , the second the cost of naming a member of it, so is the total description length divided by . For in the example below, and .
A simultaneous event and an oracle inequality
Theorem 3.1.2
(Class-weighted uniform bound and structural risk selection)
With probability at least , simultaneously for every and every ,
Fix an ordering of each finite class. For each , select the first empirical risk minimizer in that order. Select the smallest index minimizing , and output . The empirical losses are measurable, so these countable, fixed tie rules make the selected index and classifier measurable. The simultaneous event below is a countable intersection of measurable events. Then on the same event,
This is an oracle inequality: the data-driven output is compared with the best risk in every class plus that class's allowance. The right side is an analysis benchmark, not a quantity assumed known to the algorithm.
A minimizer over the countable list actually exists here. Since the positive weights have finite sum, . For fixed , the radii tend to infinity while empirical risks lie in , so only finitely many class scores can be below any fixed finite level. This justifies the stated selection instead of assuming an infimum is attained. For a finite list the issue is simpler.
Proof
(Union bounds, then a chain of four inequalities)
For fixed and , the loss indicators are independent, lie in , and have mean . Two-sided Hoeffding gives
A union bound over the finite class gives failure probability at most for that class. A second, countable union bound gives total failure probability at most . Overlapping classes can be counted more than once; that does not invalidate the bound.
On the simultaneous event, for any fixed choose ; finiteness guarantees existence. The selection and the two deviation inequalities give
This is true for every on the same event, so taking the infimum proves the oracle inequality.
Proof X-ray
Why the selected class needs no second test sample here
The selected index is data-dependent. The proof does not condition on it being fixed; it first constructs a simultaneous event for every class using the preassigned weights. Once that event holds, the inequalities may be applied to the winning index. This avoids an additional selection penalty beyond the one already paid in the class weights. It does not remove the need for independent observations or make training error itself an unbiased estimate after selection.
A comparison of two scores
Worked example 3.1.3
(A comparison of two penalized scores)
Suppose , , and weights are . Consider two classes with , , whose empirical minimizers have errors and . Their radii and scores are approximately
The second class fits the observed sample better, but the first has the lower penalized score among these two. A third class could still win the full countable comparison. The scores are upper bounds on the simultaneous event, not exact population risks, so the example does not establish that the first class really has lower risk in this particular sample.
Worked example 3.1.4
(The price of a small weight)
Keep , and , but compare the weights and . The radius is . For it is ; for it is . Making the weight times smaller increases the radius by only about , because the weight enters through . A class far down the list is penalized, but not prohibitively.
Worked example 3.1.5
(A radius larger than one)
Take , , a class with and weight . Then , so . Since risks lie in , the event holds trivially. The bound is valid but says nothing; the penalized score of this class is at least , so it can only be selected if every other class scores worse. Small samples and tiny weights make the guarantee vacuous, which the theorem does not hide.
Why the prior allocation must precede the data
Counterexample mode
A data-chosen singleton can hide a large class
Let be uniform, with label zero everywhere. After observing the sample, define to be zero on observed points and one on unobserved points. It has empirical risk zero, while at least points are unobserved and . If we now call a preassigned singleton class and assign it weight one, the purported fixed-class radius is . For , , it is about , so the claimed bound fails on every sample. This singleton depends on the observed inputs and is not specified as one of the theorem’s pre-fixed classes. Treating it as preassigned is the invalid step.
A data-dependent choice is allowed after a genuinely fixed, countable family and weights have been assigned, because the theorem controls every candidate simultaneously. Data-dependent classes or weights require a different argument, such as an independent sample for their construction or an additional accounting of the selection mechanism.
Common mistake
(Selecting by empirical risk alone)
For nested classes the minimum training error cannot increase with the class, so ranking classes by alone never prefers a class strictly over a larger class that contains it, however large the larger class's allowance is. The theorem controls the penalized score . Dropping from the selection rule removes the guarantee.
Common mistake
(Dropping the factor two in the oracle inequality)
The benchmark is , not . The radius is paid twice: once to turn the empirical risk of the selected classifier into a population risk, and once more to turn the population risk of the benchmark classifier into an empirical one. With best risk and radius the guaranteed bound is , not .
Approximation and estimation
The oracle expression separates two effects. The quantity is the approximation error available in class ; is an estimation allowance. Enlarging the class may reduce the first while increasing the second. Neither is generally known from a single training sample.
Let . If the same i.i.d. sequence supplies the first examples for each , choose in the selection rule. The first Borel–Cantelli lemma, which does not require independence of the failure events, says that the simultaneous event fails only finitely often almost surely because . For each fixed , . Thus the oracle inequality gives for every , and hence . Since every selected classifier belongs to the union, its risk is at least . Therefore
This is consistency relative to the fixed union of classes. It is not automatically Bayes consistency: that would also require the union to approximate the best measurable classifier for the distribution under study. The result is statistical; enumerating all classes or finding empirical minimizers may be computationally impractical.
Practice with solutions
Quick check
(Let , , and . Write the class radius exactly.)
Substitute into .
Solution · Answer
, so .
Quick check
(On the simultaneous event, a class has best true risk and radius . What upper bound does the oracle inequality give for the selected classifier?)
Remember that the radius is counted twice.
Solution · Answer
The selected risk is at most on the simultaneous event.
Quick check
(Why is it invalid to set a class equal to a sample-dependent singleton and then apply the fixed-class radius without further analysis?)
Compare the training risk of such a singleton with its true risk.
Solution · Answer
The one-class Hoeffding calculation assumes the hypotheses are fixed before the sample; the proposed singleton can encode the sample and make its training error artificially small. The counterexample above gives true risk at least despite zero training risk.
Quick check
(For fixed and , explain why .)
Look at the numerator and the denominator under the square root.
Solution · Answer
Its numerator is for fixed , while the denominator is . Their ratio tends to zero, as does its square root.