One-versus-All Multiclass Classification
The multiclass hypothesis is not counted as one binary hypothesis. It is counted as k coordinated selections from H bin, one selection for every label.
From One Classifier to Several
A multiclass problem has multiple possible labels, but One-versus-All builds its multiclass hypothesis from binary hypotheses. Instead of treating the multiclass hypothesis as one indivisible object, the construction assigns one binary hypothesis to each label. The result is a collection of label-specific binary choices.
What do you think happens?
Suppose there are k labels. How many binary components must a One-versus-All hypothesis specify?
Reveal answer
k binary components
The construction uses one binary hypothesis for each label. Therefore, a One-versus-All hypothesis contains k binary components.
The One-versus-All Decomposition
Let the multiclass problem have k labels. One-versus-All represents a multiclass hypothesis by selecting one member of the binary hypothesis class H bin for each of those labels. The full hypothesis is therefore a tuple of k binary hypotheses. The important counting unit is this complete tuple: one selected binary hypothesis for label 1, one for label 2, and so on through label k.
The multiclass hypothesis is not counted as one binary hypothesis. It is counted as k coordinated selections from H bin, one selection for every label.
What H bin Contributes
H bin is the binary hypothesis class used repeatedly in the construction. Each label receives one selected member of H bin. If H bin has VC dimension d, then d describes the capacity of the binary class used for one label-specific component. One-versus-All does not replace this binary VC dimension with a different binary value; it uses the same binary complexity once for each of the k components.
Counting Multiclass Complexity
The binary class H bin has VC dimension d. A One-versus-All class with k labels contains k binary components. The corresponding Natarajan dimension is therefore obtained by using the binary capacity d once for every component: Ndim(H OvA,k bin) = kd.
Three Labels and Binary Dimension Two
Suppose H bin has VC dimension d = 2 and the One-versus-All construction has k = 3 labels. What is the Natarajan dimension of the resulting class?
- 1Identify the binary capacity
The binary hypothesis class contributes d = 2.
- 2Identify the number of components
The construction has k = 3 labels, so it contains three binary components.
- 3Apply the relationship
Use
Ndim(H OvA,k bin)= kd, giving 3 times 2.
The Natarajan dimension is 6.
VC Dimension Versus Natarajan Dimension
| Measure | Class it describes | Role in One-versus-All |
|---|---|---|
| VC dimension | The binary hypothesis class H bin | Provides the value d for one binary component |
| Natarajan dimension | The One-versus-All multiclass class | Combines the binary capacity across k components as kd |
VC dimension supplies the per-component capacity; Natarajan dimension describes the resulting multiclass construction.
These dimensions answer related but different questions. VC dimension is the complexity measure given for the binary class H bin. Natarajan dimension is the multiclass complexity measure for the assembled One-versus-All class. The relationship between them is not a change in the meaning of d; it is a calculation that accounts for the k binary choices in the multiclass representation.
Common Counting Mistakes
Common mistake Using d as the Natarajan dimension of the full One-versus-All class.
What it looks likeIf H bin has VC dimension d and there are k labels, reporting d instead of kd ignores the additional binary components.
Why it failsThe One-versus-All class contains k binary components, not just one.
Do this insteadMultiply the VC dimension d by the number of labels k.
Common mistake Using k as the complexity of the binary hypothesis class.
What it looks likeTreating the number of labels as though it were the VC dimension of H bin.
Why it failsk counts components, while d is the VC dimension of H bin.
Do this insteadKeep the roles separate and use Ndim(H OvA,k bin) = kd.
Common mistake Replacing the binary VC dimension with the multiclass Natarajan dimension.
What it looks likeCalling d the Natarajan dimension before accounting for the k label-specific components.
Why it failsVC dimension measures the binary class H bin; Natarajan dimension measures the assembled multiclass class.
Do this insteadFirst identify d for H bin, then calculate the multiclass value kd.
Practice the Construction
A binary hypothesis class H bin has VC dimension d = 4. A One-versus-All class uses k = 5 labels. Calculate the Natarajan dimension and state what each factor represents.
Hints
- Use the relationship
Ndim(H OvA,k bin)= kd. - The factor d comes from H bin.
- The factor k counts the label-specific binary components.
Checking the Practice Result
For d = 4 and k = 5, calculate the Natarajan dimension of the One-versus-All class.
- 1Substitute the values
The relationship is
Ndim(H OvA,k bin)= kd, with k = 5 and d = 4. - 2Multiply
Compute 5 times 4.
The Natarajan dimension is 20. The 4 comes from the VC dimension of H bin, and the 5 counts the binary components, one for each label.
Key Takeaways
- 1One-versus-All represents a multiclass hypothesis with one binary hypothesis for each of the k labels.
- 2H bin is the binary hypothesis class from which each label-specific component is selected.
- 3If H bin has VC dimension d, the One-versus-All class has k binary components.
- 4The Natarajan dimension of the One-versus-All class is
Ndim(H OvA,k bin)= kd. - 5VC dimension describes the binary class, while Natarajan dimension describes the assembled multiclass class.
At a glance
- One-versus-All decomposes a multiclass hypothesis into k binary components.
- Each component is selected from the binary hypothesis class H bin.
- The VC dimension d measures the capacity of one binary class, while the Natarajan dimension measures the resulting multiclass class.
- For k labels, the relationship is
Ndim(H OvA,k bin)= kd.