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

M. Giese: Lernmethoden in Computergrafik and Multimedia16 October 2003

Vorlesung 2

Maschinenlernen:Klassische Ansätze I

Martin Giese

[email protected]


Ü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 =



x

Trainingsdaten

“wahre Funktion” )(xf

y



x

Trainingsdaten

“wahre Funktion”

Approximation der Funktion )(ˆ xf

)(xf

y



x

Neue Testdaten



)(xf

y

Generalisierung:

Vorhersage der Funktion an Stellen ohne Trainingsdaten



x

Neue Testdaten



)(xfGute

Generalisierung

y

Generalisierung:




x

Neue Testdaten



)(xfSchlechte

Generalisierung

y

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

y

y

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 ==

y

*y y

V


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

L1-Fehler (L1 loss )

ε-unempfindliche Fehlerfunktion

(ε-insensitive error)

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

V

*ˆ yy −

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

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

V

ε−ε


Statistische FormulierungPopuläre Kostenfunktionen (Klassifikation):

0-1-Fehler (0-1 loss )

“Scharnier”-Fehler (L1 hinge loss )

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

*ˆyy

V

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

V

1

>

=sonst.

0 falls 1)(

yyθ

* und ˆ von Vorzeichen gleiches

yy

1*±y



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

∑=

=L

lll yxfV

LfR

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

x1


Problem

Klassen nicht immer um Lernbeispiele zentriert

Trainingsbeispielex1

x2

Klasse 1 Klasse 2


Entscheidungsregionen

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

x1 x1

x2

Entscheidungsgenze


Diskriminantenfunktionen

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

)(maxarg xfK kk=x1

x2

fk



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)(

0

0

RR

fxx

x

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

10

0

1

1

0

0f(x)

y*

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

=>==<=

yf(x)yyf(x)y


Statistische EntscheidungstheorieGenerelles Schema (aus Signaldetektionstheorie):

1

10

0

Treffer(hit, positive)

f(x)

y*

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-

den



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-

den


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-

den



Risikofunktion (true risk):

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

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

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

00

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

= ∫

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

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

xf


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

xf


110

0

C10

C01

C11

C00

f(x)

y*

Bayes Klassifikator

Erweiterung für allgemeinere Kostenfunktion:

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

1110

0100

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

yxfPCyxfPCfR

==

−−

>==

= sonst 1

)0()1(

1|0| falls 0)( 0010

1101

yPyP

CCCC

)yp(x)yp(x

xf

(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 !

g

)(ln)2(2

1)(|ln)(

2 lyP

lyl)Pyp(

lTl

Tl

T

l

=++−=

===

µµxµxx

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)

Date post:	02-Oct-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

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

Documents