8
$\begingroup$

VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ordered domains: i.e. $f:X\rightarrow \mathbb{R}$. Is there a standard generalization of VC-dimension suited to functions with discrete, unordered domains? i.e. $f:X\rightarrow K$ where $K$ is a finite set with no ordering on it.

$\endgroup$
10
$\begingroup$

Yes - I think you are looking for "multiclass VC dimension," and there are a couple different generalizations of VC dimension to multiclass classification. A good paper on this is by Ben-David et al. ('95). In addition to proving learnability results, they give a nice history and references to previous extensions of VC dimension to the multiclass case. Another perhaps relevant work by Haussler and Long ('95) generalizes Sauer's lemma to more general versions of VC dimension.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.