Hypothesis Classes

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.

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.

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.

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 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.

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.

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.