One-versus-All Multiclass Classification
One-versus-All represents a multiclass hypothesis using one binary hypothesis for each 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
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?
Identify the binary capacity: The binary hypothesis class contributes d = 2.
Identify the number of components: The construction has k = 3 labels, so it contains three binary components.
Apply 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 |
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
Using d as the Natarajan dimension of the full One-versus-All class.
The One-versus-All class contains k binary components, not just one.
Fix:
Multiply the VC dimension d by the number of labels k.Using k as the complexity of the binary hypothesis class.
k counts components, while d is the VC dimension of H bin.
Fix:
Keep the roles separate and use Ndim(H OvA,k bin) = kd.Replacing the binary VC dimension with the multiclass Natarajan dimension.
VC dimension measures the binary class H bin; Natarajan dimension measures the assembled multiclass class.
Fix:
First 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.
Substitute the values: The relationship is Ndim(H OvA,k bin) = kd, with k = 5 and d = 4.
Multiply: 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
- One-versus-All represents a multiclass hypothesis with one binary hypothesis for each of the k labels.
- H bin is the binary hypothesis class from which each label-specific component is selected.
- If H bin has VC dimension d, the One-versus-All class has k binary components.
- The Natarajan dimension of the One-versus-All class is Ndim(H OvA,k bin) = kd.
- VC dimension describes the binary class, while Natarajan dimension describes the assembled multiclass class.
Key Takeaways
- 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.