Natarajan dimension

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The Natarajan dimension measures how complex a family of multi-class functions is. Let H be a set of functions from an input set X to a label set Y. A subset C of X is said to be shattered by H if there exist two functions f0 and f1 in H such that f0(x) ≠ f1(x) for every x in C, and for every way of mixing f0 and f1 on C (splitting C into two parts B and C minus B), there is a function h in H with h(x) = f0(x) for x in B and h(x) = f1(x) for x in C minus B. The Natarajan dimension of H is the largest size of a shattered set. If Y has only two labels, this dimension becomes the VC dimension. This concept helps understand learning and generalization in multi-class settings.