SS 2009 Maschinelles Lernenund Neural Computation

150

Kapitel 8: Kernel-Methoden

SS 2009 Maschinelles Lernenund Neural Computation

151

Ausgangsbasis: Perceptron Learning Rule

• Rosenblatt (1962)• Input wird dazugezählt

(abgezogen), wenn Output falsch(„mismatch-based“)

• Verwendung: Klassifikation

target"" sonst0

if

if

K

K

K

K

j

jji

jjiij

y

yxx

yxxw

=

>−=

SS 2009 Maschinelles Lernenund Neural Computation

152

Mathematische Formulierung

• Perceptron (1 Output):

• yi = +1/-1:

• Daten kommen als inneres Produkt vor („duale Darstellung“)

( ) 0wxf T += wx

iiyw x=Δ

( ) ∑ +=i

Tii wyxf 0xx

Inneres Produkt(dot product)

SS 2009 Maschinelles Lernenund Neural Computation

153

Vor- und Nachteile des Perceptrons

• Vorteile:– Globale Lösung garantiert (keine lokalen Minima)– Leicht lösbar bzw. otpimierbar

• Nachteil:– Auf lineare Separierbarkeit beschränkt

• Idee:– Transformation der Daten auf einen Raum, in dem das

Problem linear trennbar ist

SS 2009 Maschinelles Lernenund Neural Computation

154

Vergleiche Diskriminanzanalyse

• Allgemein linear:

beliebige Vorverarbeitungsfunktionen, lineare Verknüpfung

• Neuronales Netz:

NN implementiert adaptive Vorverarbeitungnichtlinear in Parametern (w)durch Approximationstheorem: beliebig nichtlineare Diskriminanzfunktion

( ) ( ) 01

wywgp

iiii +=∑

=

xx

( ) ( )( ) ( ) Gauss ...

Sigmoide ... ffy

ffy

ii

ii

xwxxwx T

−== MLP

RBFN

SS 2009 Maschinelles Lernenund Neural Computation

155

Kernels

• Ziel ist eine fix bestimmte Transformation xi→Φ(xi), sodass das Problem linear trennbar ist (ev. hochdimensional)

• Kernel: Funktion, die als inneres Produkt von Φs darstellbar ist:

• Φ muss nicht einmal bekannt sein

( ) ( ) ( )TK 2121, xΦxΦxx =

( ) ( )∑ +=i

ii wKyf 0,xxx

SS 2009 Maschinelles Lernenund Neural Computation

156

Beispiel: Polynomischer Kernel

• 2 Dimensionen:

• Kernel entspricht tatsächlich einem inneren Produkt aus Vektoren mit „Vorverarbeitung“

( ) ( )2, TK xzzx =

( ) ( )

( )( )( ) ( )zΦxΦ

xz

===

=++=

=+=

T

T

zzzzxxxx

zzxxzxzx

zxzx

2122

2121

22

21

212122

22

21

21

22211

2

2,,2,,

2

SS 2009 Maschinelles Lernenund Neural Computation

157

Beispiel

• Durch Transformation wird Problem linear trennbar

Ф

Ф-1

x1

x2

x12

x22

SS 2009 Maschinelles Lernenund Neural Computation

158

Die Wirkung des Kernel-Tricks

• Einsatz des Kernels, z.B:

• 16x16-dimensionale Vektoren (z.B. Pixel-Bilder), Polynom 5. Grades: Dimension = 1010– Inneres Produkt zweier 10000000000-dim. Vektoren

• Berechnung erfolgt im niedrigdimensionalen Raum:– Inneres Produkt zweier 256-dim. Vektoren– 5-te Potenz

( ) ( ) ( )∑∑ +=+=i

Tii

iii wywKyf 0

50, xxxxx

SS 2009 Maschinelles Lernenund Neural Computation

159

Gauss‘scher Kernel

• Ф nicht darstellbar, hat aber unendliche Dimension!(wenn Trainingsset unbegrenzt groß sein kann)

• Folgt aus Mercer‘s Theorem:– Betrachte die Kernel-Matrix

über alle Trainingsbeispiele

– Berechne Eigenwerte und -funktionen, dann gilt:

– Für Gauss‘schen Kernel gilt: Kernel-Matrix hat vollen Rang!Dimension so groß wie das Trainingsset

( ) σ2/2

, zxzx −−= eK

( ) ( ) ( )( ) ( ) ( )

( ) ( ) ( )⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

mmKmKmK

mKKKmKKK

K

,2,1,

,22,21,2,12,11,1

K

MLMM

K

K

( ) ( ) ( )zxzx ii

iiK ΦΦ=∑λ,

SS 2009 Maschinelles Lernenund Neural Computation

160

Large Margin Classifier• Hochdimensionaler Raum:

Overfitting leicht möglich• Lösung: Suche

Entscheidungslinie (Hyperebene) mit größtem Abstand von den Punkten

0=+ bTwx

Abstand maximal

w

1=+ bTwx

1−=+ bTwx

w2

=d

• Optimierung:

Minimiere

(Maximiere )

Randbedingung:

w2

=d

2w

( ) 01≥−+ by Tii wx

SS 2009 Maschinelles Lernenund Neural Computation

161

Optimierung 1

• Quadratisches Optimierungsproblem• Lösungsansatz: Lagrange-Multiplikanten

• Randbedingung:• 1. Ableitung nach w und b muss 0 sein. Das ergibt:

( )( ) min121

1

2 →−+−= ∑=

n

i

TiiiP byL wxw α

0≥iα

∑

∑=

=

iii

iiii

y

y

0α

α xw

SS 2009 Maschinelles Lernenund Neural Computation

162

Optimierung 2

• Einsetzen der zuletzt ergebenen Terme:

• „Duale“ Formulierung• Wichtig: Daten stehen wieder als inneres Produkt (dot

product) im Term!• Kernel-Trick kann wieder angewandt werden

min21

,

→−=∑ ∑i ji

TjijijiiD yyL xxααα

( ) min,21

,

→−=∑ ∑i ji

jijijiiD KyyL xxααα

SS 2009 Maschinelles Lernenund Neural Computation

163

Optimierung 3

• Minimierung ist quadratisches Programmierungsproblem

• Globales Minimum garantiert• Methoden

– Chunkingnutzt die Tatsache dass viele αi=0

– Decomposition Methods– Sequential Minimal Optimization (SMO)

löst eine Sequenz von Problemen der Größe 2(Paare von Variablen)

SS 2009 Maschinelles Lernenund Neural Computation

164

Support Vectors

• Support-Vectors: Punkte am Rand des Margins• Bestimmen alleine die Lösung,

für alle anderen Punkte gilt: αi=0, können weggelassen werden Kernelfunktion

RückprojektionSupport Vectors

SS 2009 Maschinelles Lernenund Neural Computation

165

Daten mit Rauschen• Bisherige Annahme: Problem ist exakt trennbar• Bei Rauschen: Einführung von „Slack variables“:

weicht den strengen Margin etwas auf

min21 2 →+ ∑

iiC ξw

( ) 0 1 ≥−≥−+ iiTii by ξξwx

w

Lernparameter

min21

,→−=∑ ∑

i ji

TjijijiiD yyL xxααα

• Duales Problem (Lagrange) bleibtgleich (bis auf Randbedingung)

Ci ≤≤α0

wiξ−

SS 2009 Maschinelles Lernenund Neural Computation

166

Beispiel

Kernel: Polynom 3. Ordnung Schätzung nur mit Support-Vectors ergibt die selbe Lösung:

SS 2009 Maschinelles Lernenund Neural Computation

167

Bedingungen für Kernels• Jede Funktion K(x,z), für die gilt

• bzw.

ist eine Kernelfunktion („positive definite“ Kernels)• Ist K1 und K2 ein Kernel, so sind auch

aK1 (für a>0)K1+K2K1*K2Kernel

• Wahl des richtigen Kernels (Vorverarbeitung) ist entscheidend!⇒ Modellselektion notwendig

( ) ( ) ( ) fddffK ∀≥∫ 0, zxzxzx

( ) iji

jiji axxKaa ∀∑ ,,

für beliebige Trainingspunkte xi

SS 2009 Maschinelles Lernenund Neural Computation

168

SVM-Theorie: VC-Dimension

• „Shatter“: Wenn unter n Punkten alle 2n Klassifikationen möglich sind

• VC-Dimension h … kleinstes m von Punkten, für die der Lerner weniger als 2m Klassifikationen schafft

• Z.B.: VC-Dim(Perceptron)=k+1 (k … Inputdimension)• Für komplexe Lerner kann oft nur Schranke angegeben

werden

SS 2009 Maschinelles Lernenund Neural Computation

169

SVM-Theorie: Structural risk minimization

• Schranke für das „Risiko“ (Fehler)

• Maximieren des Margins beschränkt VC-Dimension• ||w|| kann als Regularisierungsterm betrachtet werden• Gauss-Kernel: VC-Dim h=∞

nhnh

RR⎟⎠⎞

⎜⎝⎛−⎟

⎠⎞

⎜⎝⎛ +

+≤ 4ln12ln

emp

δ

Mit Wahrscheinlichkeit1-δAnzahl Trainingspunkte

Empirischer FehleramTrainingsset

Minimal möglicher Fehler

SS 2009 Maschinelles Lernenund Neural Computation

170

SVM und Neuronale Netze

• Gauss-Kernel: RBF• Sigmoid-Kernel: MLP

• So viele „Hidden Units“ wie Trainingsmuster• Allerdings andere Berechnung• Raum ist ∞-dimensional

• SVM und Boosting: formaler Zusammenhangvgl. Boosting: Punkte an der Entscheidungsgrenze bekommen größte Bedeutung (wie SV)

( ) σ2/2

, zxzx −−= eK

( ) ( )θκ += TK xzzx tanh,

SS 2009 Maschinelles Lernenund Neural Computation

171

Andere Kernelverfahren

• Kernel-Trick funktioniert bei allen Methoden, in denen Daten als inneres Produkt vorkommen– Kernel-PCA– Kernel-Fisher Diksriminante– Kernel Regression

• Gauss‘sche Prozesse

SS 2009 Maschinelles Lernenund Neural Computation

172

Zusammenfassung

• SVMs sind interessante Alternative zu klassischen neuronalen Netzen• Kernel-Trick: Inneres Produkt von hochdimensionalen „Features“

(Vorverabeitung) kann niedrigdimensional berechnet werden• Beschränken der VC-Dim. (Vermeidung von Overfitting): Large

Margin Classifier• Lineares Modell, Quadratische Programmierung, Minimum garantiert• Support Vectors: Punkte am Margin, sind alleine für Lösung

verantwortlich

• Aber: Overfitting dennoch möglich• Modellselektion notwendig• Wahl des geeigneten Kernels ist sehr wichtig!