Does adding more features guarantee better accuracy?

No. It can increase fitting capacity while also increasing opportunities to fit noise or accidental relationships.

Must the final classifier be nonlinear in feature space?

No. A linear classifier there can produce a nonlinear boundary in the original input space.

Is this only a deep-learning result?

No. It is a foundational pattern-recognition result relevant to feature maps and linear separation more broadly.

Cover's theorem

Definition

Cover's theorem, in pattern recognition, concerns the capacity of linear decision surfaces to separate labeled points and how nonlinear feature representations can increase that capacity. A practical lesson is that a nonlinear mapping into a higher-dimensional representation can make a classification problem linearly separable. This is a statement with geometric assumptions and statistical qualifications, not a guarantee that adding arbitrary features will improve predictions on unseen data.

What it means

A linear classifier separates classes with a line in two dimensions, a plane in three, or a hyperplane in higher dimensions. Some label arrangements cannot be separated in the original representation. A nonlinear transformation can change their geometry so that a linear separator becomes possible in the transformed space.

The important word is nonlinear. Merely repeating existing features or applying an invertible linear re-expression does not create every missing separation. Cover's analysis helps explain the appeal of richer feature spaces, while also distinguishing the ability to fit labels from the ability to generalize beyond the observed points.

How it works

Represent each example through a set of measurement functions. A linear combination of those measurements defines a decision surface. If the measurements are nonlinear functions of the original input, a hyperplane in feature space corresponds to a nonlinear boundary in the original space.

Cover's function-counting result counts separable binary label assignments for points in general position. For homogeneous separators through the origin in d dimensions, the count for N points is 2 times the sum of binomial coefficients “N−1 choose k” for k from 0 to d−1.

The assumptions and separator convention matter. A boundary with a freely chosen intercept differs from a homogeneous boundary; adding a constant feature can express that intercept, but dimensional accounting must remain consistent.

Three practical examples

1. Feature-engineering study: an analyst adds an interaction term when two measurements jointly determine a category, then tests whether the new representation helps a simple classifier.

2. Kernel-method lesson: students connect nonlinear feature maps with the idea that a linear separator in an expanded representation can correspond to a curved boundary in the original input space.

3. Capacity review: a team examines why a model fits a small training collection perfectly after adding many features, while checking whether the apparent success persists on separate data.

Think of it this way

Think of colored beads that overlap in a flat projection but can be separated after their positions are described using an additional meaningful coordinate. The analogy is limited: the new coordinate must come from a specified mapping, and extra room alone does not supply a useful rule for future beads. A representation can separate the observed collection while capturing noise rather than a stable pattern.

Worked example

Consider four points with coordinates x1 and x2, each taking values −1 or +1. Give the same-sign points (−1, −1) and (+1, +1) label positive. Give the opposite-sign points (−1, +1) and (+1, −1) label negative.

No single straight line in the original two-dimensional plane separates these opposite-corner groups. Now add the nonlinear feature z = x1 × x2. The positive examples have z = +1; the negative examples have z = −1. In the expanded representation (x1, x2, z), the plane z = 0 separates them.

This explicit mapping demonstrates the geometric idea, not a universal recipe. The interaction was selected because it matches the example's known structure. Adding an unrelated random feature might not solve the problem, and using the labels to search many transformations without independent evaluation could overfit.

This toy arrangement illustrates nonlinear separation rather than every general-position assumption in the counting theorem.

Illustrative case study

Fictional case: Feature Pier predicts whether pairs of machine settings belong to an acceptable operating category. A linear baseline misses a systematic interaction. An analyst proposes interaction features and finds a training separator, then adds many more terms until every recorded label is fitted.

A reviewer separates the initial structural hypothesis from the later unrestricted search. The team evaluates selected features on held-out operating combinations and examines whether measurement noise affects the decision. No predictive gain is claimed. The case illustrates the difference between using richer representations to express a plausible relationship and treating perfect training separation as sufficient evidence.

Common misconceptions and mistakes

Cover's theorem does not say that every higher-dimensional mapping makes every problem easier. The mapping, point configuration, sample size, and meaning of “easier” matter.

Linear separability is not the same as a large margin or robustness to noisy measurements. A separator may exist while being fragile.

The theorem also does not establish that a deeper neural network always generalizes better. Model training, regularization, data quality, and task structure remain relevant.

Finally, adding duplicate features does not create independent geometric freedom. Many columns can occupy a smaller effective subspace.

Business use

For business teams, the practical lesson is to consider whether the current representation hides relationships that a simple predictor cannot express. An interaction or other meaningful transformation may be worth testing before assuming the data require an opaque or very large model.

Keep evaluation independent of feature selection. Report the feature-generation process and compare performance on new examples, including conditions not densely represented in training. The ability to separate existing records is useful diagnostic information, but deployment decisions require evidence about future cases and the costs of errors.

Check your understanding

In the worked example, what happens if the new feature is x1 + x2 instead of x1 × x2?

Answer: The sum is a linear combination of existing coordinates and does not supply the nonlinear interaction used to separate the opposite-corner labels. Adding it alone does not create the demonstrated solution.

Related terms

Learn next

draw the four worked-example points and list their product features. Then distinguish a separator through the origin from one with an intercept. Study why increasing the number of separable label assignments does not by itself establish reliable prediction on new data.

Sources

Thomas M. Cover, Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition: https://isl.stanford.edu/~cover/papers/paper2.pdf — primary full text consulted for feature-space separation, general position, and the homogeneous function-counting theorem. The original interaction example and fictional case illustrate implications without claiming the theorem guarantees generalization. The input's Deep learning category is retained, although the theorem is broader.

Previous: Covariant derivative (healing brush) Next: Coverage bias