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

Kapitel 8: Kernel-Methoden - Medizinischen Universität WienKapitel 8: Kernel-Methoden SS 2009 Maschinelles Lernen und Neural Computation 151 Ausgangsbasis: Perceptron Learning Rule

  • Upload
    others

  • View
    8

  • Download
    0

Embed Size (px)

Citation preview

  • 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

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