Modell Komplexität und Generalisierung

Transcrição

Tagetfunktion und Rauschen
Overtting-Undertting
Testdaten
Bias-Varianz Analyse
Modell Komplexität und Generalisierung
Christian Herta
November, 2013
1 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Lernziele
Konzepte des maschinellen Lernens
Targetfunktion
Overtting, Undertting
Generalisierung
Out-of-sample error und Testdaten
Modell-Komplexität (model complexität)
2 von 41
Christian Herta
Bias-Variance
Lern Kurven
Outline
3 von 41
1
2
3
Testdaten
4
5
Lern Kurven
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Lern Kurven
Targetfunktion
Es soll eine unbekannte Funktion, die sogenannte Targetfunktion
t (~x ),
angenähert werden.
Erhält man die Datentargets
so kann man
y
y deterministisch
schreiben:
y = t (~x )
4 von 41
aus den
~x
Werten,
als Funktion, der sogenannten Targetfunktion
Christian Herta
Bias-Variance
t,
Testdaten
Lern Kurven
Verrauschte Targets
Die unbekannte Targetfunktion
~x (i )
nicht (direkt) dem
y (i ) .
t (~x )
entspricht in der Regel für ein
Die Daten sind typischerweise verrauscht. Dies kann man
folgenderweise modellieren:
y (i ) = t (~x (i ) ) + mit einer Zufallsvariable
(= stochastisches Rauschen)
Somit erhält man statt einer Funktion eine Wahrscheinlichkeitsverteilung
p(y |~x )
Die Wahrscheinlichkeitsverteilung des Rauschens kann dabei auch von
5 von 41
Christian Herta
Bias-Variance
~
x
abhängen
p(|~x ).
Testdaten
Lern Kurven
Ziel des Lernens und Trainingsdaten
Ziel des Lernens: Finden einer geeigneten Hypothese
h(~x ) ≈ t (~x )
für alle interessanten
werden soll. p (~x )
~x ,
d.h.
~x
für die eine Vorhersage gemacht
hinreichend groÿ.
Die Traingsdaten sind verrauscht:
y (i ) = t (~x (i ) ) + Welche Muster liegen der Targetfunktion zu Grunde und welche
sampling
kommen zufällig aus der Auswahl der Trainingsdaten (
error).
Die Werte der Hypothese
h(~x (i ) )
sollte nicht perfekt den
Trainingsdaten entsprechen. Aber wie weit soll die
Übereinstimmung sein?
6 von 41
Christian Herta
Bias-Variance
y (i )
der
Lern-Diagramm nur Training
7 von 41
Christian Herta
Bias-Variance
Testdaten
nach [Abu]
Lern Kurven
Outline
8 von 41
1
2
3
Testdaten
4
5
Lern Kurven
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Lern Kurven
Beispiel: Undertting-Overtting: Polynominal Regression
9 von 41
Christian Herta
Bias-Variance
Testdaten
Logistic Regression: Undertting
10 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Logistic Regression: Overtting
Logistische Regression mit hochgradigem Polynom:
hΘ (~x ) = g (Θ0 + Θ1 x1 + Θ2 x1 x2 + Θ3 x22 + Θ4 x13 + Θ5 x12 x2 + . . . )
11 von 41
Christian Herta
Bias-Variance
Lern Kurven
Logistic Regression: Passend
12 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Lern Kurven
Ziel des Lernens - Hypothesenmenge H
Ziel des Lernens: Finden einer geeigneten Hypothese
h(~x ) ≈ t (~x )
h
wird aus einer Menge von Hypothesen
H
durch die
Trainingsprozedur bestimmt.
Univariate Lineare Regression als Beispiel zur Verdeutlichung der Bedeutung von H:
H ist die Menge aller (unendlich vielen) Hypothesen Θ ( ) = Θ0 + Θ1 , die sich durch Variation der
ergeben.
h x
Aus der Menge von möglichen Hypothesen
Trainingsdaten eine bestimmte Hypothese
der Kostenfunktion aus, d.h.
13 von 41
Christian Herta
H
wird durch Lernen der Parameter
hΘnal (x) erhalten.
∀Θ : J (Θnal ) ≤ J (Θ)
Bias-Variance
x
Θ
Θ
mittels den
Diese zeichnet sich durch das Minimum
Testdaten
Undertting
Ziel:
h(~x ) ≈ t (~x )
Was passiert beim Undertting?
14 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Lern Kurven
Undertting
Ziel:
h(~x ) ≈ t (~x )
Was passiert beim Undertting?
Das Ziel kann im
Undertting-Fall
nicht (ausreichend) erreicht
werden, da keine der Hypothesen aus
H
ist.
d.h.:
14 von 41
H
ist zu wenig mächtig (komplex).
Christian Herta
Bias-Variance
ähnlich der Targetfunktion
Testdaten
Overtting
Ziel:
h(~x ) ≈ t (~x )
Was passiert beim Overtting?
15 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Lern Kurven
Overtting
Ziel:
h(~x ) ≈ t (~x )
Was passiert beim Overtting?
Die durch das Lernen gefundene Hypothese
h
aus
H
passt sich zu
sehr an die spezielle Ausprägung der Trainingsdaten an.
Da
15 von 41
H
sehr mächtig (komplex) ist.
Christian Herta
Bias-Variance
Outline
1
2
3
Testdaten
4
5
Lern Kurven
16 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Lern Kurven
Trainingsfehler
Bisher nur Trainingsmenge
(durchschnittlichen)
Loss
D
und Berechung des
der Traingsdaten (bisher genannt
Kostenfunktion):
Trainingsfehler (
train error, in-sample error)
trainingsfehler = Ein (h) =
1
m
m
X
loss (h(~x (i ) ), y (i ) )
i =0
Der Trainingsfehler wurde bisher als Funktion der Parameter J (Θ) für ein
spezisches Modell (Hypothesenmenge) benutzt, um die Parameter
Θ
aus den Daten zu lernen. Jetzt Ein (h) als Funktion der Hypothesen h,
da verschiedene Modelle benutzt werden können.
17 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Trainingsfehler als Kriterium nicht ausreichend
Ein niedriger Trainingsfehler impliziert nicht automatisch ein gutes
Overtting!),
Modell (
d.h.
h(~x ) ≈ t (~x )
ist nicht garantiert.
h(~x )
kann eine schlechte Prognose abgeben für
Trainingsmenge nicht enthalten sind.
18 von 41
Christian Herta
Bias-Variance
~x -Werte,
die in der
Testdaten
Lern Kurven
Out-of-sample error / expected risk
Der
out-of-sample error
ist der durchschnittliche
typischen weiteren Daten (p (x0 , y 0 )
hinreichend groÿ)
Loss,
der sich auf
ergeben würde, die
nicht zum Training verwendet worden sind:
Eout (h) = Ex ,y [loss (h(x), y )] =
Z
X ×Y
19 von 41
Christian Herta
Bias-Variance
loss (h(x), y )dp (x, y )
Testdaten
Lern Kurven
Generaliserungsfehler
Der Generalisierungsfehler einer Hypothese
h
kann folgendermaÿen
deniert werden (nach [Abu]):
|Eout (h) − Ein (h)|
Also der Fehler, die sich durch die Anpassung von
h
mittels
Trainings an die spezielle Ausprägung der Trainingsdaten
Dtrain
ergibt, im Vergleich zu dem zu erwarteten Vorhersage-Fehler.
Zwei Gründe für die Dierenz:
auch ohne Rauschen sind zu wenig Daten in
Lernalgorithmus
A
D,
so dass der
eine wenig generalisierende Hypothese
h
ndet.
zu wenig Trainingsdaten, so dass auch das Rauschen gelernt
wird.
20 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Generaliserungsfehler (cont.)
In der Literatur ndet man unter dem Begri Generalisierungsfehler
verschiedene Denitionen, wie z.B.:
Der Generalisierungsfehler einer Hypothese
ist
Dtrain
h gelernt mit einem Algorithmus A und den Trainingsdaten
R (A, Dtrain ) = Eout (h) −
Also die Abweichung in
Eout
von
inf
h0 ∈H
Eout (h0 )
h vom besten h0 .
oder
manchmal wird auch nur
21 von 41
Eout (h) als Generalisierungsfehler bezeichnet.
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Out-of-sample error Eout
Einführung von
das Modell
ist nicht direkt zugänglich.
mtest gelabelte
h(~x )
Testdaten, um zu überprüfen, ob
auch Werte gut vorhersagt, die nicht beim
Training verwendet wurden:
testdaten = Dtest = {(x~0
22 von 41
Christian Herta
(0)
, y0
Bias-Variance
(0)
(1)
(mtest ) 0 (mtest )
(1)
), (x~0 , y 0 ), . . . , (x~0
,y
)}
Testdaten
Testfehler
Der Testfehler ist der durchschnittlicher
testfehler =
1
m0
m
test
X
Loss
der Testdaten:
(i )
loss (h(x~0 ), y 0 (i ) )
i =0
Testfehler dient als Schätzung des
out-of-sample error Eout (h)
testfehler ≈ EX ,Y [loss (h(x), y )] = Eout (h)
23 von 41
Christian Herta
Bias-Variance
Lern Kurven
Modell Komplexität (model
Informell: Die Komplexität von
Testdaten
complexity, capacity
H
)
(des Modells) beschreibt wieviele
unterschiedlich komplizierte Funktionen durch
H
abgedeckt werden.
Maÿe um die Modell Komplexität zu beschreiben:
VC-Dimension dvc (VapnikChervonenkis Dimension)
Rademacher Komplexität
24 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Lern Kurven
Einuss der Komplexität
Komplexeres Hypothesenset
H⇒
gröÿere Wahrscheinlichkeit
die Targetfunktion darstellen zu können, d.h. die
Targetfunktion ist in
H
oder nahe
Weniger komplexes Hypothesenset
H.
H⇒
gröÿere
Wahrscheinlichkeit, dass der Generaliserungsfehler niedriger ist.
25 von 41
Christian Herta
Bias-Variance
Testdaten
Schranke für Generalisierung
aus der Theorie ergibt sich mit Wahrscheinlichkeit 1
Eout (h) ≤ Ein (h) + Ω(m, H, δ)
mit der VC-Dimension
dVC
als Maÿ für die Komplexität
v
u
u
u
Ω(m, H, δ) ≤ t
8
m

ln 
m)dVC
4((2
+ 1)
δ


d.h. Lernen (Generalisierung) ist möglich, wenn
die Modell-Komplexität nicht zu hoch ist und
genügend Trainingsdaten vorhanden sind.
26 von 41
Christian Herta
Bias-Variance
− δ:
Lern Kurven
Testdaten
Komplexität und erwartete Fehler
Quelle: [Abu]
27 von 41
Christian Herta
Bias-Variance
Lern Kurven
Outline
1
2
3
Testdaten
4
5
Lern Kurven
28 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Lern Kurven
Trainingsmenge, Hypothesenmenge und Hypothese
Für quadratischem
Loss
und Regression ist die Bias-Variance
Dekomposition einfach. Analoges gilt aber auch für Klassikation
und andere
Loss -Funktionen.
Lernen der Hypothesenmenge (Modell)
D
führt zu Hypothese
h(D)
Abhängigkeit von den Traingsdaten
29 von 41
Christian Herta
Bias-Variance
H
mit den Trainingsdaten
(hochgestelltes
D).
D
zeigt die
Erwartungswert des
Testdaten
out-of-sample errors
Ausgangspunkt der Bias-Varianz Analyse ist der Erwartungswert
des
out-of-sample errors:
ED Eout (hD (x))
mit
hD : gelernte Hypothese mit den Traingsdaten D
Eout (hD ): out-of-sample error für die gelernete Hypothese
ED : Erwartungswert bezüglich der Trainingsdaten.
30 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Lern Kurven
ohne Rauschen in den Daten und quadratischem Fehler:
ED
Eout (h
D
h
h
) = ED EX
h
h
= EX ED
h
D
(x) − t (x)
2 ii
h
D
(x) − t (x)
2 ii
mit der durchschnittlichen Hypothese
h̃(x)
= ED
h
D
(x)
ergibt sich:
ED
Eout (h
D
(x)) = EX ED
= variance
h
D
2 2 (x) − h̃(x)
+EX h̃(x) − t (x)
+bias 2
Falls die Daten verrauscht sind kommt ein dritter Term, der irreduzierbare Fehler
(siehe z.B. [Has])
31 von 41
Christian Herta
Bias-Variance
EX [2 ]
, hinzu.
Testdaten
Lern Kurven
Interpretation: Bias2
Ex
h̃(x) − t (x)
2 Quadratische Abweichung der durchschnittlichen Hypothese
der Targetfunktion
32 von 41
Christian Herta
t↔
Undertting
Bias-Variance
h̃
von
Testdaten
Interpretation: Varianz
Ex ED
2 h (x) − h̃(x)
D
Durchschnittliche quadratische Abweichung der gelernten
hD }
Hypothesen {
von der durchschnittlichen Hypothese
Overtting
33 von 41
Christian Herta
Bias-Variance
h̃ ↔
Lern Kurven
Testdaten
Interpretation: Varianz
Veranschaulichung am Beispiel: 2 Datenpunkte und Fitten von
Sinus mit Konstanter und Geraden.
siehe Folien Seite 10 .
Quelle:[Abu]
34 von 41
Christian Herta
Bias-Variance
Lern Kurven
Outline
1
2
3
Testdaten
4
5
Lern Kurven
35 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Ziel
Ziel:
h(~x ) ≈ t (~x )
gegeben wenn
Eout
bzw der
testfehler
klein ist.
Erfüllt, falls folgende beide Bedingungen erfüllt sind:
Ein (Trainingsfehler) klein, d.h. kein Undertting.
|Eout − Ein | klein
bzw. testfehler ≈ trainingsfehler , d.h. kein Overtting.
36 von 41
Christian Herta
Bias-Variance
Lern Kurven
Testdaten
Lern Kurve
Wie kann man erkennen, dass das Model passend ist?
Beachte passend bezieht sich auf die Einussgröÿen:
Anzahl der Datenpunkte
m
der Trainingsdaten
Komplexität der Hypothesenmenge (Modell)
Stärke des stochastischen Rauschen
Targetfunktion
37 von 41
Christian Herta
t,
Dtrain
H
im Vergleich zur
d.h. das Signal-Rausch Verhältnis.
Bias-Variance
Lern Kurven
Lern Kurve: Einfaches Modell
38 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Lern Kurve: Komplexes Modell
39 von 41
Christian Herta
Bias-Variance
Testdaten
Lern Kurven
Testdaten
Lern-Diagramm für überwachtes Lernen
40 von 41
Christian Herta
Bias-Variance
nach [Abu]
Lern Kurven
Testdaten
Lern Kurven
Literaturangabe
Andrew Ng: Machine Learning (Cousera Online Kurs), 2013
[Has] Trevor Hastie,Robert Tibshirani, Jerome Friedman: The
Elements of Statistical Learning, insb.: Kapitel 7, Springer
Verlag 2009
[Abu] Yaser Abu-Mostafa: Learning from Data, Caltech
Machine Learning bzw.
Yaser Abu-Mostafa et all.: Learning from Data, AMLBook
2012
41 von 41
Christian Herta
Bias-Variance

Modell Komplexität und Generalisierung

Transcrição

Documentos relacionados

Berufseinstiegsklasse (BEK)

Literatur-Nobelpreis für Herta Müller

Der Audi Sport quattro S1 Pikes Peak

1 Dr. Ulrike Murmann Predigt am 1. Advent 2010 in St. Katharinen

PASS OVER BLUES®

KN2132v

Pressetext (PDF / Download)

Optimierung von UHF/SHF-Empfängern

PDF - ALL-OVER

Selbstgesteuertes Lernen mit Neuen Medien im Frem

Zeitreihenanalyse