Natarajan dimension

In the theory of Probably Approximately Correct Machine Learning, the Natarajan dimension characterizes the complexity of learning a set of functions, generalizing from the Vapnik–Chervonenkis dimension for boolean functions to multi-class functions. Originally introduced as the Generalized Dimension by Natarajan,^[1] it was subsequently renamed the Natarajan Dimension by Haussler and Long.^[2]

Let ${\displaystyle H}$ be a set of functions from a set ${\displaystyle X}$ to a set ${\displaystyle Y}$. ${\displaystyle H}$ shatters a set ${\displaystyle C\subset X}$ if there exist two functions ${\displaystyle f_{0},f_{1}\in H}$ such that

• For every ${\displaystyle x\in C,f_{0}(x)\neq f_{1}(x)}$.
• For every ${\displaystyle B\subset C}$, there exists a function ${\displaystyle h\in H}$ such that

for all ${\displaystyle x\in B,h(x)=f_{0}(x)}$ and for all ${\displaystyle x\in C-B,h(x)=f_{1}(x)}$.

The Natarajan dimension of H is the maximal cardinality of a set shattered by ${\displaystyle H}$.

It is easy to see that if ${\displaystyle |Y|=2}$, the Natarajan dimension collapses to the Vapnik–Chervonenkis dimension.

Shalev-Shwartz and Ben-David ^[3] present comprehensive material on multi-class learning and the Natarajan dimension, including uniform convergence and learnability. Recently, Cohen et al^[4][5] showed that the Natarajan dimension is the dominant term governing agnostic multi-class PAC learnability.