Datenabhängige Verallgemeinerungsgrenzen für die Multi-Class-Klassifikation

In diesem Papier untersuchen wir datenabhängige Verallgemeinerungsfehlerschranken, die eine milde Abhängigkeit von der Anzahl der Klassen aufweisen, wodurch sie für das Lernen mit mehreren Klassen geeignet sind, wenn eine große Anzahl von Labelklassen vorliegt. Die Schranken gelten im Allgemeinen für empirische Multi-Class-Risiko-Minimierungsalgorithmen, die eine beliebige Norm als Regularisierer verwenden. Zentral für unsere Analyse sind neue strukturelle Ergebnisse für mehrklassige Gaußsche Komplexitäten und empirische ℓ ∞ -Normüberdeckungszahlen, die die Lipschitz-Kontinuität der Verlustfunktion in Bezug auf die ℓ 2 - und ℓ ∞ -Norm ausnutzen. Wir etablieren datenabhängige Fehlerschranken in Bezug auf die Komplexitäten einer linearen Funktionsklasse, die auf einer endlichen Menge definiert ist, die von Trainingsbeispielen induziert wird, für die wir enge untere und obere Schranken zeigen. Wir wenden die Ergebnisse auf mehrere prominente Multi-Class-Lernmaschinen an und zeigen eine engere Abhängigkeit von der Anzahl der Klassen als der Stand der Technik. Beispielsweise erhalten wir für die Multi-Class-Support-Vektor-Maschine von Crammer und Singer (2002) eine datenabhängige Schranke mit logarithmischer Abhängigkeit, was eine wesentliche Verbesserung zur vorherigen Wurzel-Abhängigkeit darstellt. Die experimentellen Ergebnisse werden veröffentlicht, um die Wirksamkeit unserer theoretischen Ergebnisse zu überprüfen.