Hypothesis Classes
Finite classes contain a limited number of hypotheses, often because their representations are bounded.
A Limited Set of Predictors
A hypothesis class is finite when it contains a limited number of available predictors. The important question is not how complicated one predictor looks, but how many different predictors the class makes available to the learning procedure. When that number is limited, the class can be analyzed using its size, written as |H|.
Finite classes often arise because their representations are bounded. Once the allowed representation choices are restricted, only a limited collection of hypotheses remains available. The finite-class analysis then connects three ingredients: the class size |H|, the desired accuracy parameter ε, and the desired confidence parameter δ. It also depends on whether the learning problem is realizable or nonrealizable.
Reading the Finite-Class Bound
For a finite class, the analysis follows a fixed sequence. First identify H and determine |H|. Next identify the desired accuracy ε and confidence δ. Then determine whether the setting is realizable or nonrealizable. Finally use the finite-class sample-complexity bound with c set to 1 for realizable learning or 2 for nonrealizable learning. The resulting bound describes how many examples are sufficient under those parameters.
Finite-class sample-complexity bound: use |H|, ε, δ, and c, with c = 1 in the realizable case and c = 2 in the nonrealizable case.
Choosing the Case Before the Bound
Suppose a finite class H has a known size, and the learning task specifies ε and δ. How should the bound be selected?
Identify the class: Write down H and its size |H|.
Identify the setting: Decide whether the learning problem is realizable or nonrealizable.
Select c: Use c = 1 in the realizable case and c = 2 in the nonrealizable case.
Apply the bound: Use |H|, ε, δ, and the selected value of c in the finite-class sample-complexity bound.
The same class can receive different bound calculations because the realizable and nonrealizable cases use different values of c.
Why Class Size Has Mild Impact
The key structural feature of the finite-class result is the logarithm around the class size. Because the class-size contribution is logarithmic, increasing the number of hypotheses does not increase the sample requirement in direct proportion to the number of hypotheses. This is why a very large finite class can still have a comparatively mild contribution to sample complexity.
Consider a displayed bound in which a class contains 2^10,000 hypotheses. The relevant class-size contribution is represented by 10,000 rather than by 2^10,000 itself. The class is enormous in terms of the number of predictors, but the logarithmic dependence keeps the class-size term comparatively manageable.
Architecture as a Graph
A neural network can be viewed as a function that maps inputs to outputs. Its architecture is specified by the tuple (V, E, σ). Here, the graph describes the network structure, E identifies its edges, and σ is the activation function. These structural choices describe how the computation is organized before particular numerical weights are selected.
Weights Select a Hypothesis
Weights are assigned to the network edges and act as the parameters of an individual hypothesis. Once the graph, edges, activation function, and weights are specified, the tuple (V, E, σ, w) defines one function, written h_V,E,σ,w. Thus, the weights do not add new structural choices to the fixed architecture; they select the particular function computed by that architecture.
From Architecture to Individual Hypothesis
What does it mean to specify one neural-network hypothesis?
Fix the architecture: Choose the graph V, its edges E, and the activation function σ.
Assign weights: Place a numerical weight assignment w on the network edges.
Form the tuple: Combine the fixed architecture and the selected weights as (V, E, σ, w).
Interpret the result: The tuple defines one function h_V,E,σ,w, which is one individual hypothesis.
A fixed architecture together with one weight assignment specifies one predictor.
Varying Weights Creates the Class
To create a neural-network hypothesis class, keep the architecture (V, E, σ) fixed and allow the edge weights to vary. Every allowable choice of weights gives one predictor. The collection of all predictors obtained this way is written H_V,E,σ. The subscript records the fixed architecture and activation function, while the class consists of the functions generated by the permitted weight assignments.
| Object | Role | Changes across the class? |
|---|---|---|
| V | Graph nodes and network structure | No |
| E | Network edges | No |
| σ | Activation function | No |
| w | Weights assigned to edges | Yes |
| hV,E,σ,w | Individual predictor | Yes, when w changes |
Interpreting Network-Class Notation
The notation H_V,E,σ identifies a class of neural-network hypotheses associated with a fixed graph, fixed edge structure, and fixed activation function. A member of that class has the more detailed form h_V,E,σ,w, where w identifies the particular weights used. Reading the notation this way prevents a common confusion: H_V,E,σ names the collection, while h_V,E,σ,w names one function inside that collection.
Common Interpretation Errors
Treating the number of hypotheses as the direct sample requirement.
The finite-class result uses a logarithmic contribution from the class size.
Fix:
Identify the logarithmic class-size term rather than using the raw number of hypotheses as the sample requirement.Using the same c value in both learning cases.
The stated bound uses c = 1 for realizable learning and c = 2 for nonrealizable learning.
Fix:
Classify the learning setting before applying the bound.Confusing one hypothesis with the hypothesis class.
The tuple including w defines one function, while varying w produces the collection.
Fix:
Use hV,E,σ,w for one predictor and H_V,E,σ for the class generated by varying weights.Treating weights as changes to the fixed architecture.
Weights are parameters assigned to edges; the graph and activation function remain fixed in the class.
Fix:
Separate structural choices (V, E, σ) from the parameter choice w.
Apply the Procedure
A neural-network class keeps (V, E, σ) fixed while allowing several possible weight assignments. Explain what one weight assignment represents, what the full collection represents, and which value of c you would use for a realizable learning analysis.
Hints
- A single assignment w is combined with the fixed architecture.
- The collection is formed by allowing w to vary.
- The realizable case uses c = 1.
Suppose a finite class contains an extremely large number of hypotheses. Without calculating a numerical sample size, explain why the class-size contribution can still be comparatively mild in the finite-class bound.
Hints
- Look at how the class size enters the bound.
- Compare logarithmic growth with direct proportional growth.
Key Takeaways
- A finite hypothesis class contains a limited number of predictors, often because its representations are bounded.
- The finite-class analysis uses |H|, ε, δ, and c; c equals 1 for realizable learning and 2 for nonrealizable learning.
- Dependence on |H| is logarithmic, so even a very large finite class can make only a comparatively mild contribution to sample complexity.
- A neural-network architecture is specified by (V, E, σ), while (V, E, σ, w) specifies one individual hypothesis.
- Fixing the architecture and varying the edge weights produces the class H_V,E,σ.
Key Takeaways
- Finite classes are collections with a limited number of available hypotheses.
- To use the finite-class bound, identify |H|, ε, δ, and whether the setting is realizable or nonrealizable.
- The class-size contribution is logarithmic, which explains its mild dependence on the number of hypotheses.
- In a neural-network class, the architecture stays fixed while edge weights vary.
- The notation H_V,E,σ names the class, whereas h_V,E,σ,w names one hypothesis.