Vorlesung 2 Maschinenlernen: Klassische Ansätze I€¦ · M. Giese: Lernmethoden in Computergrafik...

transcript

M. Giese: Lernmethoden in Computergrafik and Multimedia16 October 2003

Vorlesung 2

Maschinenlernen:Klassische Ansätze I

Martin Giese

Martin.giese@uni-tuebingen.de

Übersicht

Statistische Formulierung desüberwachten LernproblemsEinfache KlassifikatorenAnwendung

I. Statistiche Formulierung des überwachten Lernenproblems

Überwachtes Lernen aus Beispielen

LernerInputs Outputs

Beispiele: Datenpaare

Input 1Input 2Input 3

Output 1Output 2Output 3

Überwachtes Lernen aus BeispielenBeispiel: Funktionenapproximation

Beispiele (Trainingsdaten)

Gesucht: Funktion f mit

Ziel: gute Vorhersage zukünftiger Testdaten

{ }),(...,,),(),,( 2211 LL yxyxyxT =

yyxf ≈= ˆ)(ˆ

{ }),(...,,),(),,( 2211 MM yxyxyxG =

Trainingsdaten

“wahre Funktion” )(xf

Trainingsdaten

“wahre Funktion”

Approximation der Funktion )(ˆ xf

Neue Testdaten

Generalisierung:

Vorhersage der Funktion an Stellen ohne Trainingsdaten

Neue Testdaten

)(xfGute

Generalisierung

Generalisierung:

Neue Testdaten

)(xfSchlechte

Generalisierung

Generalisierung:

Regression: Ausgangsvariable y kontinuierlich

Univariate Regression: x eindimensional

Multiple Regression: x mehrdimensional

Klassifikation: Ausgangsvariable y diskret

Einklassen (binary)

Multiklassen (multiclass)

Überwachtes Lernen aus Beispielen

Statistische Formulierung

Raum)geeigneter ,( . und YXYyXx ∈∈

Gemeinsame Verteilungsdichte über X x Y:

)()|(),( xpxypyxp = konstant aber unbekannt !

Trainingsdatenpaare: (aus dieser Verteilung)

{ }),(...,,),(),,( 2211 LL yxyxyxT =

Rifkin (2002)p(y|x) definiert Verteilung im

Raum Y für festes x.

Regression: x und y kontinuierlich

Viele wichtige Lernprobleme können als Funktionenapproximationaufgefasst werden.

Klassifikation: x kontinuierlich, y diskret x

“gehört zur Klasse”: 1

“gehört nicht zur Klasse”: -1

)(ˆˆ xfy =

Statistische FormulierungKostenfunktion (loss function)

*)),(ˆ(*),ˆ( yxfVyyV =wahrer Wert von y

Definiert die Kosten, wenn vorhergesagt wird und der wahre Wert y* ist.

Sinvoll: L minimal für *)(ˆˆ yxfy ==

Statistische FormulierungPopuläre Kostenfunktionen (Regression):L2-Fehler (L2 loss )

L1-Fehler (L1 loss )

ε-unempfindliche Fehlerfunktion

(ε-insensitive error)

2*)ˆ(*),ˆ( yyyyV −=*ˆ yy −

*ˆ yy −

V|*ˆ|*),ˆ( yyyyV −=

)0,|*ˆmax(|*),ˆ( ε−−= yyyyV*ˆ yy −

ε−ε

Statistische FormulierungPopuläre Kostenfunktionen (Klassifikation):

0-1-Fehler (0-1 loss )

“Scharnier”-Fehler (L1 hinge loss )

*)ˆ(*),ˆ( yyyyV −=θ

)0*,ˆ1max(*),ˆ( yyyyV −=*ˆyy

=sonst.

0 falls 1)(

* und ˆ von Vorzeichen gleiches

Wahres Risiko (true risk)Entspricht dem Erwartungswert der Kostenfunktion

für gegebene Approximationsfunktion f(x):

Prädiziert erwartete Kosten für neue Datenpunkte

Problem: p(x,y) unbekannt

Dichteschätzung im allgemeinen Fall sehr aufwendig

∫= ),(),()),((][ yxdyxpyxfVfR Funktional !

Klassische parametrische StatistikAnnahme, dass die prinzipielle Form der Verteilung

p(x,y) bekannt ist

Schätzung der freien Parameter aus den Daten

Klassische nichtparametrische Statistik

Verwendung von Kenngrössen, die unabhängig von

der Verteilungsform der Daten sind, und deren

Verteilung berechnet werden kann

Empirisches Risiko (empirical risk)Gegeben: L Datenpaare (xl, yl)

Approximation des wahren Risikos:

Idee: Minimierung des empirischen Risiko

lll yxfV

1emp )),((1][

Statistische LerntheorieMinimierung des empirischen Risiko

Herleitung von Schranken für die Abweichung:

Schranken nichtparametrisch, d.h. unabängig von

der Form der Verteilung p(x,y)

][][ emp fRfR −

II. Einfache Klassifikatoren

Aufbau eines typischen Klassifikationssystems

Bild Merkmalsextraktion

•Pixel•Kanten•Frequenzkom-ponenten

•…

Klassifikatorf(x)

x: Merkmalsvektor

y: Klassen-label

“fröhlich”

“böse”

MerkmalsraumKlasse 2

Merkmalsvektor Merkmalsraum

Klasse 1x2

Klasse 3 x1

Merkmale

stark korreliertschlechtgut

Nächster-Nachbar-Klassifikator (nearest neighbor classifier)

Klasse 2

Klasse 3

Klassen definiert durch TrainingsbeispieleZuordnung zu nächstliegendem Klassenzentrum

Trainingsbeispiele

Klasse 1x2

Problem

Klassen nicht immer um Lernbeispiele zentriert

Trainingsbeispielex1

Klasse 1 Klasse 2

Entscheidungsregionen

Klassifizieren entspricht Zuordung zu bestimmter Region im MerkmalsraumEntscheidungsgrenzen(decision boundaries)

Entscheidungsgenze

Diskriminantenfunktionen

Jede Klasse assoziiert mit einer Diskriminan-tenfunktion fk(x)Zuordnung des Mekmalsvekotors x zu der Klasse K mit

)(maxarg xfK kk=x1

Typische DiskriminantenfunktionenLinear: f(x) = wTx + b (linearer Klassifikator)

Polynominal (polynominaler Klassifikator)

Linearkombination von Basisfunktionen /

Kernfunktionen (Supportvektormaschine)

Statistische EntscheidungstheorieZiel: Konstruktion einer Enscheidungsregel f(x), die Datenpunkt x abbildet auf Klassenlabel, z.B. y∈{0, 1}.

Einfaches Beispiel: Indikatorfunktion

Kostenfunktion: Erwartung des Fehlers

= ist ungsregion Entscheidin falls 1

ist ungsregion Entscheidinnicht falls 0)(

))5.0*()5.0)(((*)),(( −⋅−−= yxfyxfV θ1

.1sonst 1* und 5.0 ˆ fallsoder 0* und 5.0 ˆ falls null

=>==<=

yf(x)yyf(x)y

Statistische EntscheidungstheorieGenerelles Schema (aus Signaldetektionstheorie):

Treffer(hit, positive)

Falscher Alarm(false alarm, false positive)

Korrekte Ablehnung

(correct rejection, negative)

Aussetzer(miss,

false negative)

Statistische EntscheidungstheorieBeispiel: Detektion von Massenvernichtungswaffen

Korrekte Ablehnung(correct rejection,

negative)

Aussetzer(miss,

false negative)

y*: Realität

0: nicht vorhanden 1: vorhanden

1:gefun-denf(x):

Such-ergebnis 0:

nichtgefun-

1:gefun-den

1: vorhanden0: nicht vorhanden

f(x): Such-

ergebnis

y*: Realität

Korrekte Ablehnung

Aussetzer(miss,

false negative)

Keine MVW!

0:nicht

gefun-den

Beispiel: Detektion von Massenvernichtungswaffen

Statistische Entscheidungstheorie

0: nicht vorhanden

Korrekte Ablehnung(correct rejection,

negative)

Aussetzer(miss,

false negative)

y*: Realität

1: vorhanden

1:gefun-denf(x):

Such-ergebnis 0:

nichtgefun-

Beispiel: Detektion von Massenvernichtungswaffen

1:gefun-den

1: vorhanden0: nicht vorhanden

0:nicht

gefun-den

f(x): Such-

ergebnis

y*: Realität

Korrekte Ablehnung

Aussetzer(miss,

false negative)

KeineMVW!

1: vorhanden

Korrekte Ablehnung

Aussetzer(miss,

false negative)

y*: Realität

0: nicht vorhanden

1:gefun-denf(x):

Such-ergebnis 0:

nichtgefun-

Risikofunktion (true risk):

Annahme des klassischen Ansatzes:Wahrscheinlichkeitsdichte p(x|y) bekannt, bzw. aus den Daten schätzbar.

)10)(()01)(()1()0(

),(),()),((][

=∧=+=∧===∧∉+=∧∈=

yxfPyxfPyRxPyRxP

yxdyxpyxfVfR

Hypothetisch: Optimale Entscheidungsfunktion ohne Daten x:

Nach Erhebung von Daten x:

== sonst 1

10 falls 0const)(

)P(y)P(yxf

= sonst 1

|1|0 falls 0)(

x)P(yx)P(yxf

“A-priori-Wahrscheinlichkeiten”der Klassenzugehörigkeit

Bayes-Theorem:

)()()|(

)(),()|(

xpypyxp

xpyxpxyp ==

)()1()1|()|1(

)()0()0|()|0(

xpyPyxpxyP

Bayes Klassifikator

Optimale Entscheidungsregel:

Wahrscheinlichkeitsverhältnis (likelihood ratio):

= sonst 1

)1(1|)0(0| falls 0)(

y)Pyp(xy)Pyp(xxf

= sonst 1

)0()1(

1|0| falls 0)( yP

yP)yp(x)yp(x

Bayes Klassifikator

Oft Diskriminantenfunktionen geschrieben alslog:

)0(ln0|ln())0(0|ln()(0 =+===== yP)yp(xy)Pyp(xxg

)1(ln1|ln())1(1|ln()(1 =+===== yP)yp(xy)Pyp(xxg

= sonst. 1

)(g )(g falls 0)( 10 xx

Bayes Klassifikator

Erweiterung für allgemeinere Kostenfunktion:

)11)(()01)(()10)(()00)((][

=∧=+=∧=+=∧=+=∧==yxfPCyxfPC

yxfPCyxfPCfR

−−

= sonst 1

)0()1(

1|0| falls 0)( 0010

)yp(x)yp(x

(Zuvor war: C00 = C11 = 0; C01 = C10 = 1.) (vgl. Duda & Hart & Stork, 2001)

Bayes KlassifikatorErweiterung für Multiklassenfall: L Klassen; y = l ; l ∈ {1…L}.

Kostenfunktion:

Diskriminantenfunktionen:

Entscheidungsregel:

= sonst 1

gew.) Klasserichtige (d.h. )( falls 0)),((

lxflxfV

)(|)( lyl)Pyp(xxgl ===

)(max arg xgy ll=

(oder log…)

(vgl. Duda & Hart & Stork, 2001)

Bayes KlassifikatorSpezialfall: Gauss-Verteilungen

Diskriminantenfunktionen: (falls Verteilungen charakterisiert durch Mittelwerte µl und Varianz σ)

Quadratischer Term derselbe für alle l:

⇒ g(x) = wTx + b

Linearer Klassifikator !

)(ln)2(2

1)(|ln)(

lyl)Pyp(

=++−=

µµxµxx

Realisierung von Multi-klassenklassifikation durch Kaskadieren von binären KlassifikatorenVerschiedene HeuristikenProblem: Aussagen über Generalisierungsfehler schwierig

Hierarchische Klassifikatoren

(Nakajima et al., 2003)

Sehr ähnliche Ergebnisse für alle 3 Varianten.

III. Anwendung

Bayes Klassifikatoren für Objektdetektion(Schneiderman & Kanade, 2000)

Ziel: Detektion von Bildern in DatenbankenProbleme:– Variation der Ansichten– Variation der Beleuchtung– Formvariationen (z.B. Autos)2D bildbasiertHistogramme für verschiedene visuelle Attribute“Experten” für verschiedene AnsichtenScannen verschiedener Positionen

Separate Detektoren für 15 AnsichtenModellierung der Verteilungen falls Objekt präsent und nicht präsent durch HistogrammeLikelihood-Ratio-Entscheidungsregel (Bayes Klass.):

Vorteil: Normalisierung der Variation der Merkmale (feature)

Histogramme “lernen” p(feature|object)Problem: Hochdimensionale Vertei-lungen erfordern zu viele “Bins”Zerlegung in Einzelattribute:– Frequenz (Wavelet Pyramide)– Orientierung (hor. / vert.)– Position (Abtasten mit Überlappung;

Merkmalspos. relative zu Objekt)17 kombinierte Attribute aus je 8 Filterantworten; quantisiert in je 3 Level ~6500 bins

Position

Probabilistische Integration der Merkmale unterAnnahme der Unabhängigkeit:

Trainingsbilder normalisiert:– Grösse– Position– Beleuchtung (Wavelet-Pyramide)Zusätzliche synthetische Trainigsbilder(gewonnen durch Transformationen)

Systematische Suche über verschiedene Positionen und Skalen oder “coarse-to-fine”-Strategie

Ergebnisse:Gesichter+Autos: > 92 % korrekte DetektionEines der besten z.Zt. bekannten Systeme

Wichtige Punkte (bitte behalten !)

Definition des LernproblemsNächster-Nachbar-KlassifikatorBayes-KlassifikatorHierarchische KlassifikatorenMerkmals-Histogramme

LiteraturCherkassky, V., Mulier, F. (1998). Learning From Data. John-Wiley &

Sons Inc, New York.

Duda, R.O., Hart, P.E., Stork, D.G. (2001). Pattern Classification. John-Wiley & Sons Inc, New York.

Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical Learning Theory. Springer, Berlin.

Nakajima, C., Pontil, M., Heisele, B. Poggio, T. (2003). Full-body person recognition system. Pattern Recognition 36, 1997-2006.

Schneiderman, H., Kanade, T. (2000) A Statistical Method for 3D Object Detection Applied to Faces and Cars. IEEE Conference on Computer Vision and Pattern Recognition (CVPR).

http://fpn.mit.edu/9.520Spring2002/ MIT Course 9.520: Statistical Learning Theory and Applications (T. Poggio, S. Mukherjee, R.Rifkin)

Vorlesung 2 Maschinenlernen: Klassische Ansätze I€¦ · M. Giese: Lernmethoden in Computergrafik...

Documents