AI Glossary / Statistics and probability / Advanced

Natarajan dimension

Definition

Natarajan dimension measures the capacity of a multiclass hypothesis class. It is the largest number of input points on which the class can realize every combination of two fixed, distinct label choices per point. Those two choices may differ from point to point. If such sets exist at arbitrarily large sizes, the dimension is infinite.

What it means

The dimension concerns a family of possible prediction rules, not the accuracy of one fitted rule. It asks how freely predictions can vary across selected inputs. For binary labels it agrees with VC dimension. For multiple labels, it does not require every possible assignment from the entire label vocabulary.

How it works

Choose a set of points and two witness labelings that disagree at every point. For each subset of the points, a hypothesis must match the first witness there and the second witness everywhere else in the set. Passing this test gives a lower bound. An exact dimension also requires ruling out all larger sets.

Three practical examples

• A researcher compares two restricted ticket-routing families. A family that can independently switch labels on more selected ticket types has a larger witnessed capacity, although that does not by itself establish better routing performance.
• An instructor represents a finite hypothesis class as a table. Rows are allowed prediction rules and columns are inputs. Searching for all combinations of two labels in selected columns makes the abstract definition visible.
• A reviewer checks a learning guarantee. Before applying a statement about finite label sets, the reviewer determines whether the proposed task has a fixed finite vocabulary or an unrestricted output space. That distinction can change which theoretical conclusion is justified.

Think of it this way

Picture several switches, with two labeled positions assigned to each switch. The labels need not be identical across switches. A class passes the test on those switches only if it contains a rule for every combined switch setting. Merely showing that each switch can move separately is insufficient if some joint settings are forbidden.

Worked example

Consider an original input domain containing exactly three objects, a, b, and c. The output labels are red, blue, and green. A hypothesis is a complete triple of predictions in that input order. Define a class H containing exactly four hypotheses:

h1 = (red, blue, green).
h2 = (red, green, green).
h3 = (blue, blue, green).
h4 = (blue, green, green).

On the set {a,b}, choose witness labels red versus blue for a, and blue versus green for b. The four required joint patterns are (red,blue), (red,green), (blue,blue), and (blue,green). Hypotheses h1 through h4 supply all four. Therefore H Natarajan-shatters two points, so its dimension is at least two.

It cannot shatter all three inputs: every hypothesis predicts green at c, leaving no pair of distinct label choices there. Since the entire input domain has only three points, no larger set exists either. The dimension is therefore exactly two. Notice that this does not require all nine possible three-label patterns on {a,b}; four carefully specified patterns suffice.

Now remove h4, leaving a class H-minus with three hypotheses. Input a alone still has both red and blue predictions, so the dimension is at least one. Shattering two points would require four distinct restrictions, one for each of the four switch patterns. Three hypotheses can supply at most three restrictions. Consequently, no two-point set can be shattered, and the dimension is exactly one.

For a second comparison, define K as the three constant rules (red,red,red), (blue,blue,blue), and (green,green,green). Each input can receive three labels across K, yet two different inputs cannot change independently: every rule gives them the same label. K has dimension one. Counting available labels at individual inputs would miss this constraint.

Finally, let U contain all 27 triples over the three labels. Choose red and blue at every input. U includes all eight combinations formed from those pairs, so it shatters {a,b,c}. Its dimension is exactly three because the domain has only three points. The example separates label count, hypothesis count, and shattering capacity: three labels can accompany dimensions one, two, or three.

Illustrative case study

This fictional case concerns Birch Categorization, an imaginary research team evaluating routing-rule families. A presentation claims that allowing three category names makes every candidate family equally expressive. The analyst constructs the H, K, and U tables above and demonstrates their different dimensions.

The team also catches an incomplete proof: showing four patterns on {a,b} establishes a lower bound, but an exact value requires the argument about c and the finite domain. The revised report distinguishes mathematical capacity from validation accuracy and training cost. It uses the toy table to explain the reasoning rather than claiming that the production model has the same dimension. No measured business improvement is asserted.

Common misconceptions and mistakes

A feature vector with 100 coordinates does not automatically imply Natarajan dimension 100. The permitted hypothesis family matters. Finding one unshatterable set of size three also does not prove a dimension below three; another three-point set might work.

For a fixed finite label set, finite Natarajan dimension characterizes PAC learnability under the standard learning framework. This cannot be extended without qualification to arbitrary label spaces. Brukhim and colleagues constructed a nonlearnable class with Natarajan dimension one and established a characterization using DS dimension.

Business use

The practical value is in assessing theoretical claims and comparing explicitly defined model families. It is not a formula for a project's exact training-data budget. A purchasing team should ask whether a cited bound matches the proposed label space, sampling assumptions, error tolerance, confidence level, and learning procedure. Empirical evaluation still addresses the actual deployment population.

People also ask

Does adding hypotheses reduce the dimension?

No. Every shattering witness available before remains available afterward.

Does a large hypothesis count prove a large dimension?

No. The constant-rule example shows that labels can vary while joint choices remain constrained.

Check your understanding

Why does H-minus have dimension one?

Answer: One input can vary, but three rules cannot supply the four distinct patterns needed for two-point shattering.

Why is H's dimension two rather than three?

Answer: Its prediction at c is fixed across the entire class.

Related terms

• VC dimension
• PAC learning
• Sample complexity
• Empirical risk minimization
• hypothesis class
• shattering
• graph dimension
• DS dimension

Learn next

Enumerate the restrictions of H and K on every two-input subset. Then distinguish an explicit lower-bound witness from an argument excluding every larger candidate set.

More in Statistics and probability

• n-gram model - An n-gram model estimates the probability of the next token using only the preceding n-1 tokens.
• N-of-1 trial - An N-of-1 trial compares interventions within one individual across repeated periods.
• Naive Bayes classifier - A naive Bayes classifier predicts a class by combining its prior probability with feature evidence under a simplifying assumption: features are mutually...
• Nearest Neighbors Regression - Nearest neighbors regression predicts a numerical outcome by combining outcomes from similar training observations.
• Negative relationship - A negative relationship is an association in which larger values of one variable tend to accompany smaller values of another.
• Negatively skewed - A negatively skewed distribution is asymmetric with a tail extending farther toward lower values than toward higher values. It is also called left-skewed.

Sources

Daniely et al., Multiclass Learnability and the ERM Principle, definition 3 and finite-label bounds: https://proceedings.mlr.press/v19/daniely11a/daniely11a.pdf . Brukhim et al., A Characterization of Multiclass Learnability, author abstract reporting the general-label limitation: https://arxiv.org/abs/2203.01550 . All finite tables and the Birch Categorization case are original illustrations.

Previous: Nasal sound Next: Native cloud application