Vorlesung 9 Statistische Lerntheorie III

M. Giese: Lernmethoden in Computergrafik und Multimedia5 December 2003

Vorlesung 9

Statistische Lerntheorie III

Martin Giese

[email protected]


Übersicht

Quadratische ProgrammierungHilberträume mit reproduzierendem KernSupportvektor-Klassifikation: ErweiterungenSupportvektor-RegressionAnwendungen


I. Quadratische Programmierung


Konvexe Mengen / Funktionen Nicht konvexKonvex

Def: Die Menge X ist konvex, falls

Def: Die Funktion f ist konvex,falls

“stark konvex” falls man

“≤” durch “<“ ersetztKonvex Nicht konvex


Konvexe OptimierungsproblemeDef: Das Optimierungsproblem:

minimiere: f(x)

für x ∈ X

heisst konvex falls X und f konvex sind.

Satz: Konvexe Optimierungsprobleme haben eindeutige

Lösung (lokale = globale Optima).


SVM: Primäre Form (primal form)

2||21)( ww =EMinimiere:

unter den NB:

Kompakter:

unter der NB:

Konvex !

liby iT

i ≤≤+≥+ 1 1)( xw

2||21)( ww =E

0cAw ≥+

w2

w1

0cAw ≥+

Halbraum: Konvex !

Quadratische Programmierung


Lagrange Methode für Ungleichungs-NB

Lagrange-Funktion:

Optimierungstheorie ⇒ Notwendige und hinreichende

Bedingungen für Lösung aus Satz v. Kuhn-Tucker:

Minimiere L(w, b, α) über w und b; maximiere L(w, b, α)

über α mit der Einschränkung αi ≥ 0.

Lagrange-Multiplikator

∑=

−+−=l

ii

Tii bybL

1

2 )1)((||21),,( xwwαw α

Fehler Nebenbedingung


Karush-Kuhn-Tucker (KTT) Bedingungen

Differenzieren:

Optimale Gewichte gegeben durch

Linearkombination der Datenpunkte !

Gleichungs-NB für die Lagrangemultiplikatoren

⇒=∂

∂=

∂∂ 0),,(0),,( !!

bbLbL αw

wαw

0mit *1

* ≥=∑=

i

l

iiii y αα xw

li1 0 1

* ≤≤=∑=

l

iii yα

Optimalwert


Karush-Kuhn-Tucker (KTT) BedingungenZusatzbedingung für Ungleichungsnebenbedingungen

(Theorem von Karush-Kuhn-Tucker):

d.h. entweder ist die NB exakt erfüllt (“inaktiv”)

oder der zughörige Lagrange-Multiplikator ist Null.

(KTT-Komplementaritätsbedingung)

liby iT

ii ≤≤=−+ 1 0)1*)*((* xwα


Konsequenz: Viele Terme in der Entwicklung

können verschwinden !!! (“Spärlichkeit”, sparseness)

Die xi der Terme, die nicht verschwinden heissen

Supportvektoren

Die Supportvektoren “komprimieren” die Information über

die optimale Hyperebene

Für die Supportvektoren xs gilt (wegen Komplementaritätsbed.)

Supportvektoren∑

=

=l

iiii y

1

** xw α

∑=

−=⇒=+l

is

Tiiiss

Ts yybby

1

** 1*)*( xxxw α

w*T


Duales Optimierungsproblem

Idee: Lagrangefunktion ausdrücken alleine als Funktion

der Lagrange-Multiplikatoren αi

Vorteil: Oft wird Optimierungsproblem einfacher.

Man kann beweisen, dass unter geeigneten

Bedingungen (starke Dualität) die Lösungen des

primären und des dualen Optimierungsproblems

identisch sind.



Einsetzen:

Resultierende Lagrange-Funktion:

Maximierung unter den NB:

∑=

−=l

is

Tiiis yyb

1

** xxα∑=

=l

iiii y

1

** xw α

α1Kααxxα TTl

ii

l

jij

Tijiji yyL +−=+−= ∑∑

== 21

21)(

11,

ααα

0

li1 0

*1

*

≥

≤≤=∑=

i

l

iii y

α

α

jTiijK xx=



Vorteile:

Oft viel weniger freie Parameter

Abhängigkeit nur von den Skalarprodukten der Daten xi

⇒ x kann sehr hoch- oder sogar unendlichdimensional

sein !

α1Kααxxα TTl

ii

l

jij

Tijiji yyL +−=+−= ∑∑

== 21

21)(

11,

ααα

Skalarprodukt


II. Hilberträume mit reproduziernedem Kern (reproducing kernel Hilbert spaces)


Funktionenräume

Funktion ↔ Punkt des RaumesBeispiele:• C[a,b]: stetige Funktionen auf [a,b]• L1[a,b]: | f | integrierbar auf [a,b]• L2[a,b]: | f |2 integrierbar auf [a,b]


Normierter RaumLinearer Vektorraum mit NormAbbildung || f ||: f → IR is eine Norm falls:

Seminorm, falls || f || = 0 ⇒ f =0 nicht erfüllt ist.

fallsund


Euklidscher RaumLinearer Vektorraum mit SkalarproduktAbbildung (f, g): f → IR ist ein Skalarprodukt falls:

ist eine Norm.

und

falls


Dichte Teilmengen

A heisst dicht in B, falls jedes Element van B beliebig genau durch ein Element von A approximiert werden kann.Beispiel: Rationale Zahlen sind dicht in den reellen Zahlen.Für Lernen hilfreich: Funktionenmenge H, die dicht ist in L2


Hilbert Raum

Euklidscher Raum mit folgenden Eigenschaften:– Vollständig (jede Cauchy Folge konvergiert)– Separabel (approximierbar mit dichter Teilmenge

mit abzählbar vielen Elementen)Abzählbare Basis (ggf. unendlichdimensional)Beispiele: L2, IRn


Kompakter Raum

Normierter Raum N ist kompakt falls er

1. total beschränkt ist, d.h. || f || < R < ∞ für alle f ∈ N2. und vollständig ist.

In Funktionenräumen (im Gegensatz zu IRn) ist nicht jedes beschränkte Intervall kompakt.


Auswertungsfunktional

Lineares Funktional das die Funktion f(x) am festen Punkt t auswertet:

Definition: Funktional beschränkt, falls:

wobei ||.|| die Norm im Hilbertraum ist.(Wert des Auswertfunktionals abschätzbar durch die Norm von f.)

M: pos. Konstante


Auswertungsfunktional

nicht beschränkt im normalen Hilbertraum L2[a, b]

“Ausreisser” an einzelnen Punkten oder auf Mengenmit Mass Null ändern die Norm von f nicht, aber

f1(x)

f2(x)Mukherjee & Poggio (2002)

Beide Funktionen sind in L2[a, b]


Positiv definite Kernfunktionen

Definition: Sei X eine Teilmenge von IRd. Eine Kernfunktion ist symmetrische Funktion:

Kernfunktion positiv definit falls (Vorlesung 4):

für alle n, und


Hilberträume mit reproduzierendem Kern(reproducing kernel Hilbert spaces, RHKS)

RKHS: Hilbertraum über kompaktem Gebiet X mit der Eigenschaft, dass das Auswertungsfunktionalbeschränkt ist.

Satz:Für jeden RKHS existiert eindeutig eine positiv definite Kernfunktion, der sog. reproduzierende KernFür jede positiv definite Kernfunktion existiert RKHS, so dass sie die reproduzierende Kernfunktion ist.


Hilberträume mit reproduzierendem Kern

Wenn H ein RKHS ist folgt aus dem Satz von Rieszdie Existenz einer Funktion Kt aus H mit:

Die Funktion Kt hat die gleiche Eigenschaft wie die δ-Funktion in L2:

Im Gegensatz zur Funktion δ(x) gehört sie zu H !


Hilberträume mit reproduzierendem Kern

Folgerung: Kt definiert reproduzierenden Kern mit

Dies impliziert auch, dass K positiv definit ist, wegen))(),((),(),()),(),(( ⋅⋅===⋅⋅ xKKxtKtxKxKK tt

über

j

Argumente über die Skalarprodukt berechnet wird


Hilberträume mit reproduzierendem KernWenn Kx gegeben ist, kann ein RKHS konstruiert werden durch Vervollständigung des Raumes der durch die Basis der Funktionen = K(x, xi)aufgespannt wird, wobei abzählbar viele xi aus demkompakten Gebiet X gewählt werden.

Ein Skalarprodukt in diesem Raum ist definiert durch:


Satz von Mercer

Jeder positiv definite Kern K: X x X → IR, hat eine Entwicklung der Form:

wobei die Reihe gleichmassig konvergiert.Die Funktionen φq(x) sind die EigenfunktionenIntegraloperators TK:

d.h.: mit

tttxx d)(),(:)( fKfTX

K ∫=o

)(d)(),( xtttx qqqX

K φλφ =∫ 0≥qλ (Eigenwerte)


Approximationseigenschaften von RKHS

Für eine Reihe von Kernen existieren abzählbar unendlich viele positive Eigenwerte µq

Die zugehörigen RKHS sind dicht L2 !Die so definierten Hypothesenräume sind somit sehr mächtig und erlauben die Approximation einer grossen Klasse von FunktionenEine einfache Steuerung der Grösse des Hypothesenraumes is möglich durch die Bedingung:

=Kff ),(


Interpretation als MerkmalsraumFunktionenraum aufgespannt durch die Eigenfunk-tionen Φ(x) =[φ1(x), …, φN(x)]:

Normierter Basisfunktionensatz:

Interpretation von Φ(x) als hochdimensionaler Merkmalsvektor

xx x x xo xo oo x

x xx

o

x

oo

oφ2(x)

Φ(x)linear separierbar

nicht separierbar

(vgl. Vorlesung 8)

φ1(x)


Interpretation als Merkmalsraum

Skalarprodukt:

Kern ≡ Skalarprodukt der Merkmalsvektoren Φ(x):

1 x y

(Mercer)


Konstruktion von Kernfunktionen

Einige hilfreiche Zusammenhänge für die Praxis:Falls ci > 0 und Ki(s, t) Kernfunktionen, so ist auch

Kernfunktion.

Falls Ki(s, t) Kernfunktionen, so auch K1(s, t) • K2(s, t).Falls f(s) eine relle Funktion ist, so ist K(s, t) = f(s) • f(t) Kernfunktion.Falls A eine positive definite symmetrische Matrix ist, ist K(s, t) = sT A t Kernfunktion.

∑=i

iiKcK ),(),( tsts


III. Supportvektor-Klassifikation:Erweiterungen


Nichtseparable Trainingsdaten (soft margin)

Falls Trainingsdatensatz Punkte enthält, die nicht

separierbar sind oder in den Bereich des Randes fallen,

hat vorgestelltes Optimierungsproblem keine Lösung

⇒ Algorithmus nicht robust gegen Outlier!

Abhilfe: NB “weicher” machen

durch Einführen von Schlupf-

variablen (slack variable):

0mit - 1)( ii ≥≥+ ξξby iT

i xw

x1

x2

Klasse 1

Klasse 2

ξi

Outlier


Nichtseparable Trainingsdaten (soft margin)

Modifizierte Fehlerfunktion (C > 1):

Analoge Behandlung liefert folgendendes duales

Optimierungsproblem (“Box-NB” !):

∑=

+=l

iiCE

1

2||21)( ξww

Bestrafungsterm für Outlier

∑∑==

+−=l

ii

l

jij

Tijiji yyL

11,21)( ααα xxα

C

y

i

l

iii

≤≤

≤≤=∑=

*1

*

0

li1 0

α

α

Maximiere:

unter der NB:

“Box-Constraint”


Nichtlineare KlassifikatorenDuales Problem hängt nur von den Skalarprodukten

xiT xj = (xi, xj ) ab.

Idee: Ersetzen der Vektor-Skalarprodukte durch

Skalarprodukt im RKHS:

),()()())(),((,

1

max

jijqiq

q

qqji k xxxxxΦxΦ == ∑

∞

=

φφλ

Kernfunktion

Eigenfunktionen des Integraloperators

tttxx dfkfTX

k )(),()( ∫=o

(Satz von Mercer, s.o.)


Nichtlineare KlassifikatorenDuales Problem bleibt im Wesentlichen unverändert:

Zugehörige Funktion f(x):

∑∑==

+−=l

ii

l

jijijiji kyyL

11,

),(21)( ααα xxα

C

y

i

l

iii

≤≤

≤≤=∑=

*1

*

0

li1 0

α

α

Maximiere:

unter der NB:

q ∞,max

Merkmalsraum kann unendlich-dimensional sein !

bky

bwbf

l

iiii

qqq

T

+=

+=+=

∑

∑

=

=

1

1

),(

)()()(

xx

xxΦwx

α

φ

Lineare Superposition von l Kernfunktionen


VI. Supportvektor-Regression


Idee

Übertragung des entwickelten Supportvektor-Algorithmus

für Klassifikation auf Regression

Minimierung eines Kapazitätsmasses (z.B. VC-Dimension)

bei vorgegebener Approximationsqualität der

Trainingsdaten

Kapazitätskontrolle für die Funktionenklasse H

möglich durch Bedingung |w|2 < M2 (Generalisierungs-

schranken siehe z.B. Christianini, 2000)

bwbfq

qqq

T +=+= ∑∞

=

,

1

max

)()()( xxΦwx φ


ε-unempfindliche FehlerfunktionKontrolle der Approximationsgüte mittels

ε-unempfindlicher Fehlerfunktion:

Approxiumationsfehler im Interval

[-ε, ε] werden nicht bestraft.

”ε –Schlauch” um f(x)

Messung der signifikanten Approxi-

mationsfehler durch Schlupf-

variablen ξi , ξi’ mit ξi , ξi’ ≥ 0.

V(y,f(x))

y-f(x)

ε-unempfindliche FF

-ε ε

( )0|,)(|max))(,( xx fyfyV −=

y

xKlasse 2

ξi

f(x)

2ε

ξi’


Primäres Optimierungsproblem (Lineare SV Regression)

Minimiere die Fehlerfunktion (mit Konstante C > 0):

unter der NB:

0', ')(

1 )(

≥+≤++−

≤≤+≤+−

ii

iiT

i

iiT

i

by

liby

ξξξε

ξε

xwxw

∑=

++=l

iiiCE

1

2 )'(||21)',,( ξξwξξw

Kapazität Approximationsfehler

Misst Abstände vom ε-Schlauch


Duales Optimierungsproblem (Lineare SV Regression)

)'()'(

)')('(21)',(

11

1,

ii

l

iiii

l

ii

l

jij

Tijjii

yy

L

ααεαα

αααα

+−−+

−−−=

∑∑

∑

==

=

xxαα

Maximiere:

unter der NB:

li1 ,0 '**1

'*

1

*

≤≤≤≤

= ∑∑==

Cii

l

ii

l

ii

αα

αα


Nichtlineare Regression

)'()'(

),()')('(21)',(

11

1,

ii

l

iiii

l

ii

l

jijijjii

yy

k

ααεαα

αααα

+−−+

−−−=

∑∑

∑

==

=

xxαα

li1 ,0 '**1

'*

1

*

≤≤≤≤

= ∑∑==

Cii

l

ii

l

ii

αα

αα

∑∑=

∞

=

=+=+=l

iiii

q

qqq

T kybwbf1

,

1

),()()()(max

xxxxΦwx αφ

Funktionenklasse H :

Duales Optimierungsproblem: Kernfunktion

LMaximiere:

unter der NB:


V. Anwendungen


Fussgängerdetektion Papageorgiou & Poggio, 1999)

Detektion von Personen in

Strassenszenen

Projekt mit Daimler-Chrysler

Integration über die Zeit

(Dynamik)


Papageorgiou & Poggio, 1999)Fussgängerdetektion

Haar wavelets

Bilder 64 x 128 Pixel (RGB)

Haar-Wavelets als “Merkmalslexikon”

1326 Filterantworten als Merkmalsvektor

Skalenhierarchie (16 x 16, 32 x 32 Pixel)

Scannen mit Fenster

Supportvektor-Klassifikation

Verschiedene (Polynom)-Kerne getestet


Fussgängerdetektion Papageorgiou & Poggio, 1999)

Trainingssequenzen: 5 Frames je Person

Merkmalsvektoren über Zeit aneinander-

gereiht (⇒ 6630 Merkmale)

Training mit 1379 positiven und 3822

negativen Beispielen

Trainingsdaten



ROC

Ca. 1000 Supportvektoren

Dynamische (Multiframe-)version

besser als Klassifikator, der auf

Einzelframes basiert

Erhebliche Verbesserung durch

Verwendung von RGB-Merkmalen



Geschwindikeitsoptimierung

Echtzeitfähigkeit für Autoanwendung

Auswahl der besten Merkmale (29 statt 1326)

Arbeiten auf Grauwertbildern

Modellierung der Entscheidungsfunktion mit

weniger Supportvektoren

System läuft mit > 10 Hz; 15 ms / Fussgänger


Analyse von Gesichtsausdrücken (Kumar& Poggio, 2001)

1 7 13 19 25 31 37 43 49 55 61 67 73 79 85

0

2

4

6

8

10

12

Analyse von Gesichtsausdrücken, z.B. zur

Extraktion von Mundöffnung, aus Videobildern

Anwendung: Video-Sprache-Fusionierung,

Verbesserung der Spracherkennung


Analyse von Gesichtsausdrücken (Kumar& Poggio, 2001)

SystemarchitekturSV-Regression

Face Detection Localization of Facial FeaturesLocalization of Facial Features

Analysis of Facial partsAnalysis of Facial parts

1 7 13 19 25 31 37 43 49 55 61 67 73 79 85

0

2

4

6

8

10

12


(Kumar& Poggio, 2001)Analyse von Gesichtsausdrücken

Merkmale: Ausgewählte Haar-Wavelets (max. Varianz)

Supportvektor-Regression

Klassifizierungung von Visemen (analog Phonem)

Schätzung von generativem Modell (Morphable Model)

Optischer Fluss(Deformationsfeld):

Textur:


Schätzung von Morphable-Model-Koeffizienten bi und ci

Vergleich mit optimalem Fit der Koeffizienten mit stochastischem Gradientenverfahren (sehr langsam)Gute Approximation durch SVM; echtzeitfähig!

Kumar& Poggio, 2001)

Analyse von GesichtsausdrückenTextur Optischer Fluss


Analyse von Gesichtsausdrücken Kumar& Poggio, 2001)

Rekonstruktion der Bilder mittels eines

“Morphable Models” (Vorlesung 12)

Gausskerne besser als Polynomkerne

Klassifikation von 15 Visemen

Erkennung aus Filterantworten (Wavelets)

etwa genausogut wie Erkennung aus

Morphable-Model-Koeffizienten

Rekonstruktion des Originalbildes mit Morphable Model

Klassifikationsergebnisse für Visemerkennung


Wichtige Punkte

Supportvektor-KlassifikationRandDuales OptimierungsproblemSoft marginNichtlineare Erweiterung mit KernenSupportvektor-RegressionAnwendungsbeispiele


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

Sons Inc, New York.

Christianini, N., Shawe-Taylor, J. (2000). Support vector Machines. Cambridge University Press, UK.

Evgeniou, T., Pontil, M., Poggio, T. (2000). Regularization networks and Support Vector Machines. Advances in Computational Mathematics, 13, 1-50.

Kumar, V., Poggio, T. (2002). A pattern classification approach to dynamic object detection. Thesis, Massachusetts institute of Technology.

Papageorgiou, C., Poggio, T. (1999). A pattern classification approach to dynamic object detection. International Conference on Computer Vision, Corfu, Greece, 1999.

Vapnik, V.N. (1998). Statistical Learning Theory. John Wiley & Sons, New York.


Web-Seiten

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

http://www.ai.mit.edu/courses/6.867/ MIT Course 6.867: Machine learning. (T. Jaakkola)


Frohe

Weihnachten!!

Erste Vorlesung im neuen Jahr: 12.1.2004

Vorlesung am 15.12.2003 fällt aus !!

Documents

Vorlesung 9 Statistische Lerntheorie III