liveBook · Manning

Expressive power

As explained in Timeless Algorithms, The Foundational Ideas

The range and complexity of relationships that a model can represent.

A model may fit its training observations perfectly yet fail on new data. Expressive power, or capacity, is the range and complexity of relationships a model can represent. More capacity makes richer patterns available, but also makes it possible to fit irregularities specific to the training sample. section 8.7.1 section 9.1.2

Capacity depends on the model family and its configuration. A deeper decision tree can represent nonlinear relationships and conditional effects by combining successive splits. In a neural network, width accommodates a variety of patterns, while depth allows patterns to be recombined. Increasing depth or width generally increases the number of adjustable parameters and the range of relationships the network can represent. section 9.1.2 section 11.5.1 section 13.2.1

For binary classification, VC dimension formalizes one aspect of capacity. A hypothesis class shatters a set of n observations if it contains a classifier for every one of the 2^n possible assignments of two labels. Its VC dimension is the largest number of observations that can be positioned so that they are shattered. This tests the variety of label patterns the class can reproduce, not the total number of observations it can classify. section 8.7.2

Lines and labelings

Three points at the corners of a triangle can be shattered by straight-line classifiers: every assignment of two labels can be separated by some line. Four points at the corners of a square illustrate a limitation: alternating labels cannot be separated by a single line. The VC dimension of straight-line classifiers in two dimensions is three. section 8.7.2

The practical aim is to use enough flexibility to capture predictive structure without relying excessively on training-specific details. Structural risk minimization considers empirical risk alongside capacity. A soft-margin support vector machine balances margin violations against a wider margin; its penalty parameter C controls the relative importance of violations. For neural networks, architecture selection and regularization similarly influence the capacity available and how it is used. section 8.7.1 section 11.6.2

Capacity alone does not determine what is learned or whether it generalizes. Data must contain relevant information, and training requires sufficient computation. In studied language models, held-out loss continued to decline as parameter counts increased when enough data and compute were available. That result does not guarantee reliability on unfamiliar distributions or tasks. Candidate configurations can be compared on validation data, then evaluated on reserved test data; changing deployment conditions still require attention. section 13.2.1 section 13.3.2 section 11.6.1 section 11.6.3

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines capacity through VC dimension and shattering, then relates architectural flexibility to model behavior.
Examples
Illustrates capacity with linearly separated points, deep decision trees, pedestrian detection, and neural language models.
What you can do after
Evaluate model flexibility against validation performance, data coverage, and the risk of fitting training-specific patterns.
How it connects
Connects expressive power to structural risk minimization, regularization, overfitting, and generalization.

Also explained in

Compare how 13 books explain expressive power →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.