VC Dimension verallgemeinert auf diskrete, nicht binäre, ungeordnete Domänen?

Die VC-Dimension ist ein Maß für die Komplexität von Funktionsklassen , die eng mit der Komplexität der Stichprobe verknüpft ist. Fat Shattering Dimension ist eine Verallgemeinerung, die für Domänen mit höherer Ordnung geeignet ist: dh . Gibt es eine Standardverallgemeinerung der VC-Dimension, die für Funktionen mit diskreten, ungeordneten Domänen geeignet ist? dh wobei eine endliche Menge ohne Reihenfolge ist.f : X → R f : X → K $f:X\rightarrow \{0,1\}$$f:X\rightarrow \mathbb{R}$$f:X\rightarrow K$$K$

Ja - ich denke, Sie suchen nach "VC-Dimension für mehrere Klassen", und es gibt verschiedene Verallgemeinerungen der VC-Dimension für die Klassifizierung für mehrere Klassen. Ein gutes Papier dazu ist von Ben-David et al. ('95). Sie beweisen nicht nur die Ergebnisse der Lernfähigkeit, sondern geben auch einen schönen Verlauf und Verweise auf frühere Erweiterungen der VC-Dimension für den Fall mit mehreren Klassen. Eine andere vielleicht relevante Arbeit von Haussler und Long ('95) verallgemeinert Sauers Lemma auf allgemeinere Versionen der VC-Dimension.