Natarajan Dimension

The Natarajan dimension is defined through a relationship between a set C and a hypothesis class H.

Programming

From Inputs to Classes

A multiclass categorization problem asks us to learn a predictor h : X → [k]. The predictor receives an input from X and produces one class label from [k]. This is the prediction task: construct a function that turns inputs into class predictions.

How does an input x from X move through the predictor h to become one class label in [k]?

The two sides of h : X → [k] describe different parts of the task. X is the input space: it contains the possible inputs that the predictor can receive. The set [k] is the output set: it contains the possible class labels that the predictor can return. The notation therefore describes both what enters the prediction process and the kind of result it must produce.

Prediction and Evaluation

Producing a class prediction and judging that prediction are different tasks. The predictor h maps an input to one output in [k]. That output alone does not say whether the prediction is good. To discuss learning quality, an evaluation rule is needed.

What is the difference between producing a class prediction h(x) and comparing that prediction with the true label?

In the real world

Generated example: Suppose h receives one input and returns a class in [k]. The act of returning that class is prediction. Comparing the returned class with the true class under the 0-1 loss is evaluation. These are two stages of reasoning about the same predictor, not two different predictors.

The Shattering Relationship

The Natarajan dimension is defined through a relationship between a set C and a hypothesis class H. The set C is contained in the input space X. Two functions, f0 and f1, map C to [k]. For every point x in C, these functions provide the two label choices that participate in the shattering definition.

Definition

A set C is multiclass-shattered by H when the two functions f0 and f1 from C to [k] allow every binary labeling pattern on C to be realized by hypotheses in H: for each choice of which points use f0 and which use f1, a hypothesis in H realizes those choices on C.

How do C, H, f0, and f1 show that every binary labeling pattern can be realized by hypotheses in H?

The word binary refers to the choice between the two functions at each point of C. It does not mean that the predictor's full output set [k] has only two labels. The functions f0 and f1 select the two label values used in the shattering test, while [k] remains the output set of multiclass labels.

Roles of the Symbols

What does each symbol contain or represent, and how are f0(x) and f1(x) selected from [k] for each x in C?

Symbol	Role
C	A set contained in the input space X
H	The hypothesis class whose hypotheses are tested for realizing patterns
f0	A function from C to [k]
f1	A function from C to [k]
[k]	The output set of multiclass labels

Roles in the multiclass shattering definition

Dimension from Shattered Sets

Once shattered sets have been identified, the Natarajan dimension records the maximal size of a shattered set. Therefore, determining the dimension means comparing the sizes of the shattered sets that are known to be shattered and selecting the largest size. The definition asks for the maximum, not the average and not the first size encountered.

How do the sizes of known shattered sets determine the largest size, and therefore the Natarajan dimension?

Worked example

Finding the Dimension

Suppose a collection of known shattered sets has sizes 2, 4, and 3. What is the Natarajan dimension?

1
List the candidate sizes
The known shattered-set sizes are 2, 4, and 3.
2
Compare the sizes
Among these values, 4 is the largest.
3
Apply the definition
The Natarajan dimension is the maximal size of a shattered set.

Result

The Natarajan dimension is 4.

Common Reasoning Errors

Common mistake
Treating h(x) as a performance score
What it looks like
The predictor returns one class in [k].
Why it fails
The returned class is a prediction, not an evaluation of whether the prediction is good.
Do this instead
Use the 0-1 loss as the evaluation perspective when discussing performance and PAC learnability.
Common mistake
Confusing binary choices with a binary classification problem
What it looks like
The shattering definition chooses between f0(x) and f1(x) at each point of C.
Why it fails
The full predictor still produces outputs from the multiclass set [k].
Do this instead
Interpret binary as the two available function choices in the shattering test.
Common mistake
Using the first or average shattered-set size
What it looks like
Known sizes are 2, 4, and 3, but the answer uses 2 or 3.
Why it fails
The dimension is defined by the maximal size.
Do this instead
Compare all supplied sizes and select the largest.
Common mistake
Leaving the functions f0 and f1 outside the definition
What it looks like
Describing shattering only as a relationship between H and C.
Why it fails
The definition involves two functions from C to [k] that provide the two label choices.
Do this instead
Include C, H, f0, f1, and [k] when explaining the multiclass shattering relationship.

Practice Check

MEDIUM

A predictor h maps inputs from X to labels in [k]. A set C is contained in X, and f0 and f1 both map C to [k]. Explain what must be true for H to shatter C, and then determine the Natarajan dimension if the known shattered-set sizes are 1, 3, 2, and 5.

Hints

Separate the prediction task from the shattering definition.
For shattering, focus on every binary choice between f0 and f1 across C.
For the dimension, select the largest known shattered-set size.

Your attempt (not saved)

What do you think happens?

What is the Natarajan dimension when the known shattered-set sizes are 1, 3, 2, and 5?

Reveal answer

Answer:

The Natarajan dimension is the maximal size of a shattered set, so the largest listed size is selected.

Key Takeaways

1
Multiclass categorization learns a predictor h: X → [k], mapping each input to one class label.
2
X is the input space, while [k] is the output set of possible class labels.
3
The 0-1 loss evaluates predictions for PAC learnability; it is conceptually separate from producing h(x).
4
Multiclass shattering uses a set C, a hypothesis class H, and two functions f0 and f1 from C to [k] so that every binary choice pattern can be realized by hypotheses in H.
5
The Natarajan dimension is the maximal size of a shattered set.

At a glance

A multiclass predictor maps an input from X to one label in [k].
Prediction and evaluation are distinct: h produces a class, while the 0-1 loss evaluates it.
Multiclass shattering concerns whether H can realize every binary pattern formed by choosing between f0 and f1 on C.
The Natarajan dimension is the largest size of a set that can be shattered.

Related concepts

More concepts starting with N