Natarajan Dimension
The multiclass categorization goal is to learn h : X → [k].
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.
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.
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.
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.
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
| 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.
Finding the Dimension
Suppose a collection of known shattered sets has sizes 2, 4, and 3. What is the Natarajan dimension?
List the candidate sizes: The known shattered-set sizes are 2, 4, and 3.
Compare the sizes: Among these values, 4 is the largest.
Apply the definition: The Natarajan dimension is the maximal size of a shattered set.
The Natarajan dimension is 4.
Common Reasoning Errors
Treating h(x) as a performance score
The returned class is a prediction, not an evaluation of whether the prediction is good.
Fix:
Use the 0-1 loss as the evaluation perspective when discussing performance and PAC learnability.Confusing binary choices with a binary classification problem
The full predictor still produces outputs from the multiclass set [k].
Fix:
Interpret binary as the two available function choices in the shattering test.Using the first or average shattered-set size
The dimension is defined by the maximal size.
Fix:
Compare all supplied sizes and select the largest.Leaving the functions f0 and f1 outside the definition
The definition involves two functions from C to [k] that provide the two label choices.
Fix:
Include C, H, f0, f1, and [k] when explaining the multiclass shattering relationship.
Practice Check
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.
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: 5
The Natarajan dimension is the maximal size of a shattered set, so the largest listed size is selected.
Key Takeaways
- Multiclass categorization learns a predictor h : X → [k], mapping each input to one class label.
- X is the input space, while [k] is the output set of possible class labels.
- The 0-1 loss evaluates predictions for PAC learnability; it is conceptually separate from producing h(x).
- 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.
- The Natarajan dimension is the maximal size of a shattered set.
Key Takeaways
- 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.