Hypothesis Classes of Neural Networks

Every Boolean Rule

Imagine a task with n inputs. Each input is either -1 or +1, and the task produces one output that is also either -1 or +1. Any rule that assigns one of these two outputs to every allowed input is a Boolean function. The central question is whether a neural network can represent some of these rules or every possible one.

Tracing Universal Representation

The universal claim concerns a whole collection of predictors, not one permanently fixed output rule. The input sign vector enters the network structure, the computation passes through the depth-2 network, and the resulting hypothesis returns one sign. By choosing the network appropriately and selecting suitable weights, the resulting hypothesis class can include every allowable Boolean input-output rule.

Universal Does Not Mean Small

The depth-2 guarantee answers a question about expressive range: no Boolean input-output rule is excluded merely because the network has depth 2, provided the network is sufficiently large. It does not say that every rule has a compact representation.

In the construction associated with the depth-2 result, the hidden layer may be exponentially large. The minimum size s(n) needed for universal Boolean representation is exponential in the number of inputs n. Therefore, increasing the number of inputs can cause the required number of hidden units or weights to grow exponentially.

Architecture and Parameters

The architecture describes the network structure. The graph determines the nodes and edges that make up the network, and the activation function is part of the architectural specification. This structure is separate from the numerical weights assigned to the edges.

Weights are assigned to the edges in E. Once the architecture is fixed, a particular choice of edge weights specifies one individual hypothesis. The tuple (V, E, σ, w) defines one function h_V,E,σ,w.

From One Hypothesis to a Class

A hypothesis class is created by holding the architecture fixed while allowing the edge weights to vary. Each possible weight choice gives one predictor. The collection of all predictors obtained this way is the hypothesis class H_V,E,σ.

Common Interpretation Errors

• Treating the universal representation result as a promise of a small network.

  The guarantee concerns representational power. The hidden layer in the construction may be exponentially large, and the required minimum size s(n) is exponential in the number of inputs.

  Fix: Separate the question of whether a function can be represented from the question of how large the representing network must be.

• Confusing one hypothesis with a hypothesis class.

  The tuple including w defines one function. The class H_V,E,σ is obtained by varying w while the architecture stays fixed.

  Fix: Use h_V,E,σ,w for one weight-specific function and H_V,E,σ for the collection generated by all weight choices.

• Treating weights as part of the fixed architecture.

  Weights are parameters of a hypothesis, while the graph and activation function specify the architecture.

  Fix: Keep (V, E, σ) fixed when describing a class formed by varying weights.

• Interpreting the universal claim as referring to one special Boolean rule.

  The claim applies to every assignment of outputs to the allowed Boolean inputs, not merely to one selected rule.

  Fix: Read universal representation as containment of all functions from {±1}^n to {±1}.

Practice Check

Key Takeaways

1. A Boolean function maps an n-dimensional vector from {±1}^n to one output in {±1}.
2. For every n, a sufficiently large depth-2 network can have a hypothesis class containing every Boolean function on n inputs.
3. Universal representational power does not imply an efficient representation; the required network size can be exponential in n.
4. The architecture is specified by (V, E, σ), while edge weights specify an individual hypothesis.
5. Fixing the architecture and varying the weights produces the class H_V,E,σ.