Bounds on Loss Function

unter welchen Bedingungen kann wahrer Fehler E(f) gut durch den empirical loss Ez(f) auf F approximiert werden?

Ausgangspunkt: P{<u>-mean(u) ≥ ε} ≤ exp(-2ε^2p)

• <u>: wahrer Erwartungswert

• mean(u): Mittelwert über Stichprobe der Größe p

P{E(f)-Ez(f) ≥ ε} ≤ exp(-2ε^2p)

Wahrscheinlichkeit, dass Ez(f) um höchstens ε von E(f) abweicht

Ziel: finde obere Grenze für Schätzfehler für jedes f aus F -> die gilt dann auch für fz und f

verwende P(a or b) ≤ P(a) + P(b)

Umformung: Prob{E(f) - Ez(f) ≥ ε für irgendein f aus F}≤ |F|*exp(-2ε^2p) <=> Prob{E(f) - Ez(f) ≤ ε für alle f aus F}≥ 1-|F|*exp(-2ε^2p)

generell: je größer |F|, desto wahrscheinlicher gibt es ein f in F, für das der empirische Loss klein ist

• kleineres erwartetes structural risk E(fF)

• Problem: je größer |F|, desto mehr Trainingsdaten werden benötigt, dass die Abweichung klein ist -> Wahrscheinlichkeit für Bound sinkt linear mit |F|

Sample Error EF(fz) ist beschränkt (mit gewisser Wahrscheinlichkeit <2ε)

• für guten Sample Error EF(fz) werden aber mehr Datenpunkte benötigt

Maß für Komplexität (Mächtigkeit) von F

• F besteht aus unendlicher Anzahl von f

ΠF(p): maximale Anzahl von Abbildungen X->{0,1}, die F für ein X mit |X|=p realisieren kann -> Klassen trennen

monoton steigend mit p

es gilt immer ΠF(p)≤2^p

• Gleichheit gilt generell für kleine p (alle Zuordnungen können abgebildet werden) -> Maschine lernt nicht

• mit wachsendem p gilt irgendwann ΠF(p)<2^p

maximaler Wert p, für den ΠF(p)=2^p noch immer gilt:

• VC-Dimension von F

Vapnik-Chervonenkis-Dimension

beschreibt Growth Function und damit Komplexität von F

maximaler Wert p, für den eine Menge von p Datenpunkten von F geshattert werden kann

• d.h. für alle möglichen Klassenzuordnungen gibt es ein f aus F, das keine Klassifikationsfehler macht

für Beweis, dass VC-dim ≥ h: finde geshatterte Menge der Größe h

für Beweis, dass VC-dim ≤ h: zeige, dass keine Menge der Größe h+1 geshattert werden kann

• schwieriger, obere Schranken festzulegen

linearer Klassifikator: VCdim(F) = D+1

• D: Dimension des Input Space

• VCdim ist Anzahl der Parameter (Gewichte, Schwellenwerte)

Funktionen mit linearen Parametern: VCdim = #free params

zwei-Layer Neural Network mit Schwellenwert und W Parametern: VCdim = O(W logW)

• VC dim eines ANN ist endlich

VC-dim ist nicht immer durch Anzahl der Parameter definiert:

• y = sin(αx+φ) hat zwei Parameter, aber VCdim = inf

Prob{E(f) - Ez(f) ≤ ε für alle f aus F}≥ 1-2ΠF(2p)*exp(-ε^2/8 p)

für p<h: 2ΠF(2p)*exp(-ε^2/8 p) ≥ 2ΠF(p)*exp(-ε^2/8 p) = 2^p exp(-ε^2/8 p) = 2 exp((ln2 - ε^2/8)p) > 1

• keine Schranke, Maschine lernt nicht

man kann zeigen, dass für p≥h = VCdim(F) gilt

• ΠF(p)≤(ep/h)^h

• ΠF(p) wöchst nur polynomiell mit p

d.h. für p≥h konvergiert Prob{E(f) - Ez(f) ≤ ε für alle f aus F} gegen 0

• mit ausreichenden Daten und endlichem h lernt die Maschine

Voraussetzung: p≥h

E(f) ≤ Ez(f) + ε mit Wahrscheinlichkeit 1-α

α = 2*(2ep/h)^h*exp(-ε^2/8 p)

=> ε^2 = (8h log(2ep/h) - 8 log(α/2)) / p