Lokale Dualität für spärliche Support Vector Machines

Durch die zunehmende Bedeutung der Kardinalitätsminimierung in der Optimierung gewinnt die Klasse der spärlichen Support Vector Machines (SSVM) immer mehr an Aufmerksamkeit. Im Vergleich zu klassischen konvexen SVMs zeigen SSVMs empirisch signifikante Vorteile, insbesondere wenn die Anzahl der aktiven Trainingsbeispiele reduziert werden soll.

Ein verbreiteter Ansatz zur Konstruktion von SSVMs besteht darin, eine Kardinalitätsfunktion – etwa die \(\ell_0\)-Norm – zum Dualproblem einer konvexen SVM hinzuzufügen. Dieser Schritt fehlt jedoch bislang an einer soliden theoretischen Fundierung.

Die vorliegende Arbeit schließt diese Lücke, indem sie eine lokale Dualitätstheorie für SSVMs entwickelt und deren Beziehung zu den hinge‑Loss‑SVM (hSVM) und ramp‑Loss‑SVM (rSVM) untersucht. Dabei wird gezeigt, dass die abgeleitete SSVM exakt dem Dualproblem der 0/1‑Loss‑SVM entspricht und dass das lineare Repräsenter‑Theorem für lokale Lösungen gilt.

Darüber hinaus liefert die Theorie praktische Leitlinien zur Auswahl der Hyperparameter von hSVM und rSVM. Unter bestimmten Voraussetzungen konvergiert eine Folge globaler hSVM‑Lösungen gegen eine lokale Lösung der 0/1‑Loss‑SVM, und ein lokaler Minimierer der 0/1‑Loss‑SVM ist zugleich ein lokaler Minimierer der rSVM. Diese Resultate erklären, warum lokale Lösungen, die durch SSVM erzeugt werden, in früheren Experimenten die hSVM und rSVM übertreffen.

Schließlich werden numerische Tests an realen Datensätzen durchgeführt, die die potenziellen Vorteile von SSVMs anhand der hier vorgestellten lokalen Lösungen deutlich machen.