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]

## Definition

[edit]

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

* For every  x ∈ C , f 0 ( x ) ≠ f 1 ( x ) {\displaystyle x\in C,f_{0}(x)\neq f_{1}(x)} .
* For every  B ⊂ C {\displaystyle B\subset C} , there exists a function  h ∈ H {\displaystyle h\in H} such that

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

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

It is easy to see that if  | Y | = 2 {\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.

## References

[edit]

1. ^ Natarajan, Balas Kausik (1989). "On Learning sets and functions". Machine Learning. 4: 67–97\. doi:10.1007/BF00114804.67-97&rft.date=1989&rft_id=info:doi/10.1007/BF00114804&rft.aulast=Natarajan&rft.aufirst=Balas+Kausik&rft_id=https://doi.org/10.1007%2FBF00114804&rfr_id=info:sid/en.wikipedia.org:Natarajan+dimension" class="Z3988">
2. ^ Haussler, David; Long, Philip (1995). "A Generalization of Sauer's Lemma". Journal of Combinatorial Theory. 71: 219–240.219-240&rft.date=1995&rft.aulast=Haussler&rft.aufirst=David&rft.au=Long,+Philip&rfr_id=info:sid/en.wikipedia.org:Natarajan+dimension" class="Z3988">
3. ^ Shalev-Shwartz, Shai; Ben-David, Shai (2013). Understanding machine learning. From theory to algorithms. Cambridge University Press.