All-Pairs Reduction for Multiclass Categorization
One-versus-All represents a multiclass hypothesis using one binary hypothesis for each label.
From One Prediction to Many Decisions
A multiclass problem has k possible labels, but One-versus-All handles it by organizing k binary classification problems. Instead of describing the multiclass hypothesis as one indivisible object, we describe it using one binary hypothesis for each label. The central question is then: how does the complexity of the full multiclass construction relate to the complexity of one binary component?
The Binary Building Block
The class H bin is the source of every label-specific binary component. In a One-versus-All construction with k labels, the multiclass hypothesis contains k binary choices arranged as a tuple. For each label, one member of H bin is selected to serve as that label's binary hypothesis. Thus, the construction does not use H bin only once: it uses one selected member for every label.
The important counting unit is one selected member of H bin for one label. A complete One-versus-All hypothesis requires one such selection for each of the k labels.
Reading the Two Dimensions
The binary hypothesis class H bin has VC dimension d. In this construction, d remains the VC dimension associated with each binary component. The multiclass construction is described using its Natarajan dimension, which accounts for the k binary components together. The relationship supplied for this construction is Natarajan dimension = k times VC dimension.
| Quantity | Role in the construction |
|---|---|
| VC dimension d | Complexity value of the binary hypothesis class H bin |
| Natarajan dimension | Complexity value of the resulting multiclass One-versus-All class |
| k | Number of labels and number of binary components |
Counting the Multiclass Complexity
Ndim(H OvA,k bin) = kd
Four Labels with Binary VC Dimension Three
Suppose a One-versus-All construction has k = 4 labels, and H bin has VC dimension d = 3. What is the Natarajan dimension of the resulting multiclass class?
Identify the inputs: The construction has 4 labels, so it contains 4 binary components. Each component uses the binary class H bin, whose VC dimension is 3.
Apply the relationship: Use Natarajan dimension = k times VC dimension, giving 4 times 3.
Interpret the result: The multiplication accounts for the four label-specific binary choices in the One-versus-All hypothesis.
The Natarajan dimension is 12.
Mistakes in the Calculation
Using d as the final multiclass complexity.
The value 3 is the VC dimension of one binary component, while the One-versus-All class contains one component for each of the 4 labels.
Fix:
Multiply by the number of labels: 4 times 3 gives a Natarajan dimension of 12.Multiplying by the wrong quantity.
The construction has k binary components because it uses one binary hypothesis for each label.
Fix:
Use k as the multiplier in Natarajan dimension = kd.Treating VC dimension and Natarajan dimension as interchangeable names.
The supplied relationship assigns d to H bin and uses Natarajan dimension for the resulting multiclass One-versus-All class.
Fix:
State which class is being measured: H bin has VC dimension d, while the multiclass construction has Natarajan dimension kd.
When solving a problem, write down the three quantities before calculating: k, the number of labels; d, the VC dimension of H bin; and kd, the Natarajan dimension of the One-versus-All class. This makes the level of each quantity explicit.
Apply the Relationship
A One-versus-All class has k = 6 labels. The binary hypothesis class H bin has VC dimension d = 5. Calculate the Natarajan dimension of the resulting multiclass class, and explain what the factors 6 and 5 represent.
Hints
- Use the relationship Natarajan dimension = k times VC dimension.
- The factor k counts the binary components, one for each label.
- The factor d is the VC dimension of H bin.
What do you think happens?
Before calculating, predict the Natarajan dimension when k = 6 and d = 5.
Reveal answer
Answer: 30
The relationship is Natarajan dimension = kd, so 6 times 5 equals 30.
Key Takeaways
- One-versus-All represents a multiclass hypothesis with one binary hypothesis for each label.
- The binary class H bin supplies the label-specific components, and its VC dimension is d.
- With k labels, the One-versus-All class contains k binary components arranged as a tuple.
- The Natarajan dimension of the resulting multiclass class is Ndim(H OvA,k bin) = kd.
- VC dimension describes the binary building block here, while Natarajan dimension describes the resulting multiclass construction.
Key Takeaways
- One-versus-All converts a multiclass hypothesis into k label-specific binary hypotheses.
- Each component is selected from the binary hypothesis class H bin.
- If H bin has VC dimension d, then the One-versus-All class with k labels has Natarajan dimension kd.
- The VC dimension belongs to the binary building block, whereas the Natarajan dimension describes the full multiclass construction.