Concepts / Natarajan Dimension for Multiclass Classification

Natarajan Dimension for Multiclass Classification

One-versus-All represents a multiclass hypothesis using one binary hypothesis for each label.

  • Programming

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.

Key point

The central idea is that a One-versus-All hypothesis contains one binary hypothesis for each label.

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.

MulticlasshypothesisBinary hypothesis 1H binCombined outputsMulticlass predictionBinary hypothesis 2H binBinary hypothesis kH bincomponent for label 1component for label 2component for label koutputoutputoutput
How does one multiclass hypothesis become one binary hypothesis for each label, and how are their outputs combined into a multiclass prediction?

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.

H binVC dimension dh1label 1One-versus-All classk-component tupleh2label 2hklabel kselectselectselectcomponentcomponentcomponent
What does each binary hypothesis in H bin represent, and how do k selections from H bin form a One-versus-All hypothesis?

Multiplying the Capacity

Formula, step by step
  1. 1
    The binary hypothesis class H bin has VC dimension d.
  2. 2
    The One-versus-All class has k binary components.
  3. 3
    The binary capacity value d is used once for each of the k label-specific components.
  4. 4
    Multiplying the number of components by the binary VC dimension gives the Natarajan dimension kd.
VC dimensiond for H binNatarajan dimensionkdBinary componentskmultiply by knumber of uses
How does the VC dimension of H bin get multiplied by k to produce the Natarajan dimension of the One-versus-All class?
Best practice

When applying the relationship, identify both quantities before calculating: d is the VC dimension of H bin, and k is the number of labels or binary components. Then use kd for the Natarajan dimension of the One-versus-All class.

A Numerical Calculation

Worked example

Finding the Natarajan Dimension

Suppose H bin has VC dimension d = 4 and the One-versus-All construction uses k = 3 labels. What is the Natarajan dimension of the resulting class?

  1. 1
    Identify d

    The binary class has VC dimension 4, so d = 4.

  2. 2
    Identify k

    There are 3 labels, so the One-versus-All class contains 3 binary components.

  3. 3
    Apply the relationship

    Use Ndim(H OvA,k bin) = kd and substitute k = 3 and d = 4.

  4. 4
    Calculate

    The product is 3 times 4.

Result

The Natarajan dimension is 12.

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.

H binbinary hypothesis classdVC dimensionOne-versus-Allclassk binary componentskdNatarajan dimensionhashasused k times
What does the VC dimension measure for the binary class, and what does the Natarajan dimension measure for the resulting multiclass class?
QuantityClass it describesRole in One-versus-All
VC dimension dH binProvides the capacity value for one binary component
Natarajan dimension kdOne-versus-All multiclass classAccounts for all k binary components

The binary measure is the input to the multiclass calculation; the Natarajan dimension is the resulting multiclass measure.

Common Counting Mistakes

  • Common mistake

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

    What it looks like

    A learner sees that H bin has VC dimension d and reports d for the full multiclass class.

    Why it fails

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

    Do this instead

    Calculate kd for the Natarajan dimension.

  • Common mistake

    Multiplying by the wrong quantity.

    What it looks like

    A learner multiplies by the binary dimension but forgets to count the labels.

    Why it fails

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

    Do this instead
    Identify k first, then apply Ndim(H OvA,k bin) = kd.
  • Common mistake

    Treating H bin as the complete multiclass class.

    What it looks like

    A learner describes H bin as though it already contains the entire One-versus-All tuple.

    Why it fails

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

    Do this instead

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

Check Your Calculation

EASY

A binary hypothesis class H bin has VC dimension d = 5. A One-versus-All construction uses k = 4 labels. Calculate the Natarajan dimension of the resulting class and explain what each factor represents.

Hints
  • Use Ndim(H OvA,k bin) = kd.
  • The value 5 is the VC dimension of one binary component.
  • The value 4 is the number of binary components.
  1. 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. 1
    One-versus-All represents a multiclass hypothesis with one binary hypothesis for each label.
  2. 2
    H bin is the binary hypothesis class from which the label-specific components are selected.
  3. 3
    If H bin has VC dimension d and there are k labels, the One-versus-All class has Natarajan dimension kd.
  4. 4
    VC dimension supplies the capacity of one binary class, while Natarajan dimension describes the resulting multiclass construction.
  5. 5
    The multiplication by k counts the k binary choices contained in the multiclass hypothesis.

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.
  • If H bin has VC dimension d, then the Natarajan dimension of the One-versus-All class is kd.
  • VC dimension describes the binary class, whereas Natarajan dimension describes the resulting multiclass class.

Related Topics

Related concepts

More concepts starting with N