Natarajan Dimension for Multiclass Classification

The Counting Question

One-versus-All turns a multiclass problem into several binary classification problems. This creates a natural complexity question: if one binary classifier has a known capacity, how should we describe the capacity of the complete multiclass construction? The answer comes from counting the binary hypotheses that must be selected.

From One Classifier to a Tuple

Let H bin denote the binary hypothesis class. In a One-versus-All construction with k labels, the multiclass hypothesis is formed by selecting k binary hypotheses from H bin: one component for each label. These components are arranged as a tuple. The resulting object is therefore not one isolated binary hypothesis; it is a collection of k label-specific binary choices.

The Role of H bin

H bin is the source class from which the label-specific binary hypotheses are selected. Every component in the One-versus-All tuple comes from this binary hypothesis class. If H bin has VC dimension d, then d supplies the capacity value for each binary component in the construction.

Multiplying the Capacity

Ndim(H OvA,k bin) = kd

A Numerical Calculation

Two Dimensions, Two Roles

VC dimension describes the capacity value supplied by the binary hypothesis class H bin. Natarajan dimension describes the capacity of the resulting multiclass One-versus-All class. In this construction, the Natarajan dimension is obtained by using the binary VC dimension for each of the k components.

Common Counting Mistakes

• Using d as the final complexity of the One-versus-All class.

  The One-versus-All class contains k binary components, so the binary value must be used once for each component.

  Fix: Calculate kd for the Natarajan dimension.

• Multiplying by the wrong quantity.

  The number of components is determined by k, the number of labels.

  Fix: Identify k first, then apply Ndim(H OvA,k bin) = kd.

• Treating H bin as the complete multiclass class.

  H bin supplies one binary hypothesis at a time; the multiclass construction selects one such hypothesis for each label.

  Fix: Distinguish the binary source class H bin from the resulting class of k-component tuples.

Check Your Calculation

1. The expected calculation is 4 times 5, giving a Natarajan dimension of 20. The factor 5 comes from the VC dimension of H bin, while the factor 4 counts the label-specific binary components.

Key Takeaways

1. One-versus-All represents a multiclass hypothesis with one binary hypothesis for each label.
2. H bin is the binary hypothesis class from which the label-specific components are selected.
3. If H bin has VC dimension d and there are k labels, the One-versus-All class has Natarajan dimension kd.
4. VC dimension supplies the capacity of one binary class, while Natarajan dimension describes the resulting multiclass construction.
5. The multiplication by k counts the k binary choices contained in the multiclass hypothesis.