VC Dimension of Binary Hypothesis Classes
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.
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.
- 1Start with the VC dimension d of the binary hypothesis class H bin.
- 2Count the k binary components in the One-versus-All class.
- 3Multiply the binary complexity by the number of components: k times d.
- 4The resulting value is the Natarajan dimension of the One-versus-All class.
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?
- 1Identify the components
There are three labels, so the OvA class contains three binary components.
- 2Use the relationship
The Natarajan dimension is calculated as k times d.
- 3Substitute 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 |
The binary VC dimension supplies the per-component value; the Natarajan dimension describes the resulting One-versus-All class.
Common Counting Mistakes
Common mistake Using d as the final complexity of the OvA class.
What it looks likeFor k labels and binary VC dimension d, reporting d as the Natarajan dimension.
Why it failsThe OvA class contains k binary components, not just one.
Do this insteadMultiply the binary VC dimension by the number of labels: Ndim(H OvA,k bin) = kd.
Common mistake Counting labels without using the complexity of H bin.
What it looks likeReporting k as the complexity of the OvA class.
Why it failsThe construction has k components, but each component comes from a binary class with VC dimension d.
Do this insteadUse both quantities: k counts the binary components and d gives the complexity contributed by each binary class.
Common mistake Calling kd the VC dimension of H bin.
What it looks likeSaying that the binary hypothesis class has VC dimension kd after forming the OvA class.
Why it failsThe binary VC dimension remains d; kd is the stated Natarajan dimension of the full OvA class.
Do this insteadKeep 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
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
- 1One-versus-All represents a multiclass hypothesis with one binary hypothesis for each label.
- 2The binary hypothesis class H bin has VC dimension d, which supplies the complexity of each binary component.
- 3An OvA class with k labels contains k binary components arranged as a tuple.
- 4The Natarajan dimension of the OvA class is
Ndim(H OvA,k bin)= kd. - 5VC dimension describes the binary class, while Natarajan dimension describes the resulting multiclass One-versus-All class.
At a glance
- 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.