VC Dimension of Binary Hypothesis Classes
One-versus-All represents a multiclass hypothesis using one binary hypothesis for each label.
From One Multiclass Task to Many Binary Tasks
One-versus-All, abbreviated OvA, represents a multiclass hypothesis using one binary hypothesis for each label. Instead of treating the multiclass hypothesis as one indivisible object, we examine the binary component associated with every possible label. This creates a counting question: if each binary component has VC dimension d and there are k labels, how should we describe the complexity of the full OvA class?
The Binary Building Block
The binary hypothesis class H bin is the source of the individual binary components in the OvA construction. The assumption is that H bin has VC dimension d. For each label, the OvA hypothesis selects one binary hypothesis from this binary class. Therefore, the full multiclass hypothesis is not described by one selected binary hypothesis; it contains k selected binary hypotheses arranged as a tuple, one for each label.
The important counting unit is one selected member of H bin for each label. The label itself is not the complexity contribution being counted; the contribution comes from the binary hypothesis chosen for that label.
Counting the Overall Complexity
Suppose H bin has VC dimension d. An OvA class with k labels contains k binary components. The stated relationship is that the Natarajan dimension of the OvA class is obtained by multiplying the number of labels by the VC dimension of the binary class.
Ndim(H OvA,k bin) = kd
Three Labels and Binary Dimension Two
An OvA class has k = 3 labels, and its binary hypothesis class H bin has VC dimension d = 2. What is the Natarajan dimension of the OvA class?
Identify the components: There are three labels, so the OvA class contains three binary components.
Use the relationship: The Natarajan dimension is calculated as k times d.
Substitute the values: Substitute k = 3 and d = 2 into the relationship, giving 3 times 2.
The Natarajan dimension is 6.
Two Dimensions, Two Roles
| Quantity | What it describes | Where it appears |
|---|---|---|
| VC dimension | The dimension d of the binary hypothesis class H bin | Each binary component |
| Natarajan dimension | The dimension kd of the One-versus-All class | The full multiclass construction |
Common Counting Mistakes
Using d as the final complexity of the OvA class.
The OvA class contains k binary components, not just one.
Fix:
Multiply the binary VC dimension by the number of labels: Ndim(H OvA,k bin) = kd.Counting labels without using the complexity of H bin.
The construction has k components, but each component comes from a binary class with VC dimension d.
Fix:
Use both quantities: k counts the binary components and d gives the complexity contributed by each binary class.Calling kd the VC dimension of H bin.
The binary VC dimension remains d; kd is the stated Natarajan dimension of the full OvA class.
Fix:
Keep d attached to H bin and kd attached to the One-versus-All class.
Check the Construction
An OvA class has k = 5 labels. Its binary hypothesis class H bin has VC dimension d = 4. Calculate the Natarajan dimension of the OvA class, then state which quantity remains the VC dimension of H bin.
Hints
- There are k binary components.
- Use Ndim(H OvA,k bin) = kd.
- The VC dimension of H bin is given directly as d.
What do you think happens?
For k = 5 and d = 4, what is the Natarajan dimension of the One-versus-All class?
Reveal answer
Answer: 20
The relationship is Natarajan dimension = k times d, so 5 times 4 equals 20. The VC dimension of H bin is still 4.
Key Takeaways
- One-versus-All represents a multiclass hypothesis with one binary hypothesis for each label.
- The binary hypothesis class H bin has VC dimension d, which supplies the complexity of each binary component.
- An OvA class with k labels contains k binary components arranged as a tuple.
- The Natarajan dimension of the OvA class is Ndim(H OvA,k bin) = kd.
- VC dimension describes the binary class, while Natarajan dimension describes the resulting multiclass One-versus-All class.
Key Takeaways
- One-versus-All converts a multiclass problem into several label-specific binary classification problems.
- H bin is the binary hypothesis class from which one component is selected for each label.
- If H bin has VC dimension d and there are k labels, the OvA class has Natarajan dimension kd.
- The value d remains the VC dimension of the binary class; kd is the Natarajan dimension of the full multiclass construction.