SS 2009Maschinelles Lernen und Neural Computation 150 Kapitel 8: Kernel-Methoden

SS 2009 Maschinelles Lernen und Neural Computation

1

Kapitel 8: Kernel-Methoden


2

Ausgangsbasis: Perceptron Learning Rule

• Rosenblatt (1962)

• Input wird dazugezählt (abgezogen), wenn Output falsch(„mismatch-based“)

• Verwendung: Klassifikation

target""

sonst0

if

if

j

jji

jjiij

y

yxx

yxxw

Target:

Nach dem Lernschritt:


3

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)


4

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


5

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

xwx

xwx T

MLP

RBFN


6

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


7

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


8

Beispiel

• Durch Transformation wird Problem linear trennbar

Ф

Ф-1

x1

x2

x12

x22


9

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

5

0, xxxxx


10

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

mKKK

mKKK

K

,2,1,

,22,21,2

,12,11,1

zxzx ii

iiK ,


11

Large Margin Classifier• Hochdimensionaler Raum:

Overfitting leicht möglich

• Lösung: Suche Entscheidungslinie (Hyperebene) mit größtem Abstand von den Punkten

0bTwx

Abstand maximal

w

1bTwx

1bTwx

w

2d

• Optimierung:

Minimiere

(Maximiere )

Randbedingung:

w

2d

2w

01by Tii wx


12

Optimierung 1

• Quadratisches Optimierungsproblem

• Lösungsansatz: Lagrange-Multiplikanten

• Randbedingung:

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

min12

1

1

2

n

i

TiiiP byL wxw

0i

iii

iiii

y

y

0

xw


13

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

min2

1

,

i ji

TjijijiiD yyL xx

min,2

1

,

i ji

jijijiiD KyyL xx


14

Optimierung 3

• Minimierung ist quadratisches Programmierungsproblem

• Globales Minimum garantiert• Methoden

– Chunking nutzt 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)


15

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


16

Daten mit Rauschen

• Bisherige Annahme: Problem ist exakt trennbar

• Bei Rauschen: Einführung von „Slack variables“:weicht den strengen Margin etwas auf

min2

1 2 i

iC w

0 1 iiTii by wx

w

Lernparameter

min2

1

,

i ji

TjijijiiD yyL xx

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

Ci 0

wi


17

Beispiel

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


18

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+K2

K1*K2

Kernel• Wahl des richtigen Kernels (Vorverarbeitung) ist entscheidend!

Modellselektion notwendig

fddffK 0, zxzxzx

iji

jiji axxKaa ,,

für beliebige Trainingspunkte xi


19

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


20

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

nhn

hRR

4ln1

2ln

emp

Mit Wahrscheinlichkeit 1-δAnzahl Trainingspunkte

Empirischer FehleramTrainingsset

Minimal möglicher Fehler


21

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,


22

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


23

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!

Documents

SS 2009Maschinelles Lernen und Neural Computation 150 Kapitel 8: Kernel-Methoden