Statistical Learning Theory

x: Zufallsvektoren werden unabhängig voneinander basierend auf Verteilung P(x) generiert

Supervisor ordnet jedem x einen gewpnschten Ausgabewert y mit der Wahrscheinlichkeit P(y|x) zu -> ground truth

Input-Output-Machine generiert Menge F von Input-Output-Fuktionen f aus F

Error (Loss): L(y, f(x))

• Unterschied zwischen tatsächlichem und gewünschten Ausgabewert

finde (anhand von beschränkter Anzahl p von Datenpaaren (xi,yi)) die Fuktion f aus F, die den erwarteten Fehler für alle möglichen x minimiert => risk minimization

• Fehler: E(f) = ∫L(y,yf(x)) P(x,y) dxdy

Problem: Wahrscheinlichkeit P(x, y) ist unbekannt (nur Datenpaare (xi,yi))

zwei wichtigste Instanzen:

• binäre Klassifikation: y aus {0,1}, f(x) aus {0,1} -> L(y, f(x)) = (y-f(x))^2

• Regression: y aus R (kontinuierlich)

minimiere Training Error Ez(f) (da wahrer Fehler E(f) nicht bestimmt werden kann)

Empirical Error / Loss: Ez(f) = 1/p ΣL(yi, f(xi))

• Schätzung / Annäherung an E(f)

• zi :=(xi, yi) -> z = (z1, …, zp) alle verfügbaren Datenpaare

Wen Ez(f) gute Schätzung für E(f) für alle Funktionen f aus F ist: schätze Minimierer fF von E(f) durch fz aus F (Minimierer für Ez(f))

• empirical risk minimization

generalisiere von bekannten Beispielen auf den allgemeinen Fall => Induktion / induktives Prinzip

ERM liefert nur dann gute Lösung, wenn Ez(f) gute Annäherug von E(f) über die ganze Menge F

• funktioniert z.B. nicht, wenn F groß im Vergleich zur Menge der Datenpunkte ist -> sind nicht ausreichend für gute Annäherung

Unterschied zwischen E(f) und kleinstmöglichem Error E(fF) (Minimum von E über alle f aus F)

• EF(f) = E(f) - E(fF) <=> E(f) = E(fF) + EF(f)

fz: mit ERM gefundene Funktion

E(fz) = E(fF) + EF(fz)

E(fF): structural risk (Approximationsfehler)

• hängt nur von F (Struktur der Maschine) ab -> vom Bias!

EF(fz): sample error (Schätzfehler)

• können nicht das wahre Optimum finden (nur begrenzte Trainingsdaten)

EF(fz) = E(fz) - E(fF)

• -> sample error ist klein, wenn E(f) über gesamte Menge F gut durch E(fz) approximiert werden kann

Bias: Vorannahmen durch den Lernalgorithmus, bestimmte Menge F wird bevorzugt

• hier: Bias ausgedrückt durch Wahl von F und Fehlerfunktion E

Variance: Mächtigkeit von F, damit gleichzeitig Sensitivität bzgl kleineren Schwankungen in Trainingsdaten

• i.d.R. sind Modelle mit höherer Variance komplexer

• hohe Variance -> Trainingsdaten genau darstellbar

Problem: eig wäre kleineres Set F gewünscht, damit Trainingsdaten ausreichen -> damit aber automatisch höherer Bias

klassisches Bias-Beispiel

Prinzip:

• bevorzuge einfache Beschreibung

• wen alle anderen Faktoren gleich sind, wähle einfachste Lösung

hier: unter allen Modellen mit gleichem Training error, wähle das mit geringster Varianz