SRM, Maximum Margin

Gegeben Menge von Maschinen F1 subclassOf F2 … subclassOf Fn … mit h1≤h2≤…≤hn≤…, dann gilt

Ez(fz1) ≥ Ez(fz2) ≥ … ≥Ez(fzn) ≥ …

=> Training Error sinkt mit steigender VC-Dimension

Problem: gleichzeitig wächst das Konfidenzintervall => nur anhand des empirical risk können wir keine Wahl treffen, weil bei kleinem Ez wahrscheinlich auch die Abweichung zu true loss größer ist

• falls zwei Maschinen denselben training error haben, sollte man die mit der kleineren VC-Dimension bevorzugen

  • wähle an einem gewissen Training Error die Maschine mit kleinstem h

• trade-off zwischen Güte der Approximation an die Daten und Komplexität der Funktion

• findet keinen optimalen Klassifikator f, aber eine geeignete Suchmenge F (Maschine)

• Konfidenzintervall (anhand VCdim) ist i.Allg. sehr konservativ

  • kann sehr viel größer sein als wahre Abweichung

  • führt zu Bias -> Bevorzugung zu einfacherer Klassifikatoren (niedrige VCdim)

• es gibt weitere Kriterien, einen Klassifikator auszuwählen, z.B. Cross Validation

• VCdim eines linearen Klassifikators in D-dim-Raum: D+1

• betrachte jetzt linearen Classifier mit Margin Δ

  • Abstand zwischen nächstem Datenpunkt zur trennenden Hyperebene

• Beobachtung: je größer Margin, desto kleiner die VC-dim

• => SRM: bei gleichem Training error sollte man Lösung mit größtem Margin wählen

• falls Daten linear separierbar:

  • unendlich viele lin.Class. mit Training Error 0

  • wähle unter optimalen Classifier den mit größtem Margin

• Annahme: alle Datenpunkte liegen in Hyperkugel mit Radius R

• h≤min (ceil(R^2 / Δ^2), D) +1

  • proportional zu R^2 -> Daten sollten kompakt repräsentiert werden (z.B. durch PCA zu erreichen)

  • invers proportional zu Δ^2 -> maximiere den Margin