Multiclass Learnability
Shattering is a relationship between H and a set C contained in X.
Two Questions Behind Learnability
Multiclass learnability studies learning problems in which hypotheses assign multiple possible classes or labels. The topic asks more than whether a learner can produce a prediction. It asks which multiclass hypothesis classes are learnable in the multiclass PAC model and how many samples are needed to learn those classes to a specified level of accuracy.
The Shattering Relationship
Shattering is a relationship between a hypothesis class H and a set C contained in the input space X. The set C supplies the points being examined, while H supplies the hypotheses that may realize label assignments on those points. In the multiclass definition, two functions f0 and f1 map C to [k]. The notation [k] represents the available collection of k labels used by those functions.
A set C is shattered by H when, for the two label functions f0 and f1 from C to [k], every choice between f0(x) and f1(x) at each point x in C can be realized by some hypothesis in H. Thus, the definition checks whether H can realize all binary choices formed from the two available labels at every point of C.
| Symbol | Role |
|---|---|
| C | A set contained in X whose shattering is being tested |
| H | The hypothesis class that may realize the choices |
| f0 | A function from C to [k] supplying one label at each point |
| f1 | A function from C to [k] supplying the alternative label at each point |
| [k] | The collection of k possible labels used as the functions' codomain |
The roles of the symbols in the multiclass shattering definition
Tracing a Shattered Set
Suppose C contains two points. At the first point, the two functions provide f0(x1) and f1(x1). At the second point, they provide f0(x2) and f1(x2). The definition examines every combination of these two choices: choose the first function's label at both points, switch only at the first point, switch only at the second point, or choose the second function's label at both points. C is shattered only when each such combination is realized by some hypothesis in H.
Testing a Two-Point Set
A set C has points x1 and x2. The functions f0 and f1 provide two candidate labels at each point. What must H realize for C to be shattered?
List the choices: At x1, select either f0(x1) or f1(x1). At x2, select either f0(x2) or f1(x2).
Combine the choices: Consider every combination formed by independently choosing one of the two labels at x1 and one of the two labels at x2.
Check H: For each combination, check whether some hypothesis in H realizes the selected labels on the points of C.
Conclude: If every combination is realized by a hypothesis in H, then H shatters C. If even one combination cannot be realized, the definition's shattering requirement is not met.
The test concerns the complete collection of two-way choices across C, not just one labeling or one hypothesis.
From Shattering to Dimension
The Natarajan dimension records the maximal size of a set that is shattered by H under this multiclass shattering relationship. First identify which sets are shattered. Then compare their sizes. The dimension is the largest size found, not an average, a total, or the size of the first set examined.
Finding the Dimension from Known Sizes
Assume that three sets known to be shattered have sizes 2, 5, and 3. What is the Natarajan dimension based on these known shattered-set sizes?
Collect the sizes: The known shattered-set sizes are 2, 5, and 3.
Compare them: The largest listed size is 5.
Apply the definition: Because the Natarajan dimension is the maximal size of a shattered set, the relevant size is 5.
The Natarajan dimension is 5 for the collection of known shattered sets described.
The PAC Learning Frame
The multiclass PAC model provides the framework for characterizing learnability. It gives the study a specific setting: instead of asking vaguely whether a multiclass class is learnable, we ask which multiclass hypothesis classes are learnable in the multiclass PAC model.
The PAC model supplies the context for the first major question: whether a multiclass hypothesis class is learnable. The source material does not provide a particular learning algorithm or a criterion for deciding a particular class. Therefore, the correct use of the model here is to identify the setting in which learnability is characterized, not to claim that an unspecified class is automatically learnable.
Learnability and Sample Complexity
| Goal | Question | What it produces |
|---|---|---|
| Characterize learnable classes | Which multiclass hypothesis classes are learnable in the multiclass PAC model? | A classification of classes by learnability |
| Quantify sample complexity | How many samples are required for a specified accuracy? | A sample requirement associated with the target accuracy |
The two goals in a full study of multiclass learnability
Analyzing a Hypothetical Class
Organizing a Hypothetical Study
Suppose a researcher proposes a multiclass hypothesis class H and wants to study its learnability.
Set the framework: State the question in the multiclass PAC model rather than discussing learnability without a specified framework.
Characterize the class: Ask whether the proposed multiclass hypothesis class is learnable in that PAC setting. The source material does not justify declaring the answer for an unspecified class.
Set the accuracy target: Specify the level of accuracy for which learning is being considered.
Quantify samples: Study how many samples are required for the selected class to be learned to that specified accuracy.
The analysis has two stages: characterize learnability in the multiclass PAC model, then quantify the sample requirement for the chosen accuracy. No numerical sample count follows unless additional information is supplied.
A study reports that a multiclass hypothesis class is being analyzed in the multiclass PAC model, but it gives no numerical sample count. Which question has the study framed, and which question remains unanswered?
Hints
- Look for the distinction between class characterization and sample complexity.
- A PAC framing identifies the learnability setting, while sample complexity concerns the number of samples for a specified accuracy.
Common Reasoning Errors
Treating shattering as a property of H alone
Shattering is a relationship between H and a set C contained in X.
Fix:
State which set C is being tested and whether H realizes the required choices on that set.Checking only one labeling choice
The definition requires every choice between the two labels at each point in C to be realizable.
Fix:
Check the full collection of choices generated by f0 and f1 across C.Confusing f0 and f1 with hypotheses in H
f0 and f1 are functions from C to [k] that provide the two labels being compared. Hypotheses in H must realize the choices.
Fix:
Keep the functions that define the label alternatives separate from the hypothesis class that realizes them.Using an average shattered-set size
The Natarajan dimension is the maximal size of a shattered set.
Fix:
Select the largest known shattered-set size.Treating PAC characterization as a sample count
Characterizing learnable classes and quantifying sample complexity are separate goals.
Fix:
First frame or determine learnability in the multiclass PAC model, then study the number of samples needed for a specified accuracy.
Practice Check
A collection contains known shattered sets of sizes 4, 1, 6, and 3. What Natarajan dimension follows from these known sizes? Then state the two separate questions a complete multiclass learnability study would ask about a hypothesis class.
Hints
- The dimension is determined by the largest shattered-set size.
- The two study questions concern learnability in the multiclass PAC model and the number of samples needed for a specified accuracy.
What do you think happens?
Known shattered-set sizes are 4, 1, 6, and 3. Which size determines the Natarajan dimension?
Reveal answer
Answer: 6
The Natarajan dimension is the maximal size of a shattered set, so the largest listed size determines it.
Key Takeaways
- Shattering describes a relationship between a hypothesis class H and a set C contained in X.
- The multiclass definition uses two functions f0 and f1 from C to [k], and every choice between their labels at the points of C must be realizable by a hypothesis in H.
- The Natarajan dimension is the maximal size of a shattered set, so known shattered-set sizes must be compared and the largest selected.
- The multiclass PAC model provides the framework for characterizing which multiclass hypothesis classes are learnable.
- A complete study separates characterizing learnable classes from quantifying how many samples are required for a specified accuracy.
Key Takeaways
- Multiclass shattering tests whether H can realize every selection between f0 and f1 across a set C.
- C is the tested set, H is the hypothesis class, f0 and f1 map C to [k], and [k] is the available label collection.
- The Natarajan dimension is the largest size among the shattered sets.
- The multiclass PAC model frames the question of which hypothesis classes are learnable.
- Sample complexity is a separate question about the number of samples needed for a specified accuracy.