Click here to load reader

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

  • View
    1

  • Download
    0

Embed Size (px)

Text of Kapitel 8: Kernel-Methoden - Medizinischen Universität Wien Kapitel 8: Kernel-Methoden SS 2009...

  • SS 2009 Maschinelles Lernen und Neural Computation

    150

    Kapitel 8: Kernel-Methoden

  • SS 2009 Maschinelles Lernen und 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 Lernen und 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

    T ii wyxf 0xx

    Inneres Produkt (dot product)

  • SS 2009 Maschinelles Lernen und 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 Lernen und Neural Computation

    154

    Vergleiche Diskriminanzanalyse

    • Allgemein linear:

    beliebige Vorverarbeitungsfunktionen, lineare Verknüpfung

    • Neuronales Netz:

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

    ( ) ( ) 0 1

    wywg p

    i iii +=∑

    =

    xx

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

    Sigmoide ... ffy

    ffy

    ii

    ii

    xwx xwx T

    −= = MLP

    RBFN

  • SS 2009 Maschinelles Lernen und 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 Lernen und 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

    21 2 2

    2 121

    2 2

    2 1

    2121 2 2

    2 2

    2 1

    2 1

    2 2211

    2

    2,,2,,

    2

  • SS 2009 Maschinelles Lernen und Neural Computation

    157

    Beispiel

    • Durch Transformation wird Problem linear trennbar

    Ф

    Ф-1

    x1

    x2

    x12

    x22

  • SS 2009 Maschinelles Lernen und 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

    T ii

    i ii wywKyf 0

    5 0, xxxxx

  • SS 2009 Maschinelles Lernen und 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

    mKKK mKKK

    K

    ,2,1,

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

    K

    MLMM

    K

    K

    ( ) ( ) ( )zxzx i i

    iiK ΦΦ=∑λ,

  • SS 2009 Maschinelles Lernen und 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

    w 2

    =d

    • Optimierung:

    Minimiere

    (Maximiere )

    Randbedingung:

    w 2

    =d

    2w

    ( ) 01≥−+ by Tii wx

  • SS 2009 Maschinelles Lernen und Neural Computation

    161

    Optimierung 1

    • Quadratisches Optimierungsproblem • Lösungsansatz: Lagrange-Multiplikanten

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

    ( )( ) min1 2 1

    1

    2 →−+−= ∑ =

    n

    i

    T iiiP byL wxw α

    0≥iα

    ∑ =

    =

    i ii

    i iii

    y

    y

    α xw

  • SS 2009 Maschinelles Lernen und 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

    min 2 1

    ,

    →−=∑ ∑ i ji

    T jijijiiD yyL xxααα

    ( ) min, 2 1

    ,

    →−=∑ ∑ i ji

    jijijiiD KyyL xxααα

  • SS 2009 Maschinelles Lernen und Neural Computation

    163

    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)

  • SS 2009 Maschinelles Lernen und 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ückprojektion Support Vectors

  • SS 2009 Maschinelles Lernen und 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

    min 2 1 2 →+ ∑

    i iC ξw

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

    w

    Lernparameter

    min 2 1

    , →−=∑ ∑

    i ji

    T jijijiiD yyL xxααα

    • Duales Problem (Lagrange) bleibt gleich (bis auf Randbedingung)

    Ci ≤≤α0

    w iξ−

  • SS 2009 Maschinelles Lernen und Neural Computation

    166

    Beispiel

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

  • SS 2009 Maschinelles Lernen und 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+K2 K1*K2 Kernel

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

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

    ( ) i ji

    jiji axxKaa ∀∑ , ,

    für beliebige Trainingspunkte xi

  • SS 2009 Maschinelles Lernen und 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 Lernen und 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=∞

    n h nh

    RR ⎟ ⎠ ⎞

    ⎜ ⎝ ⎛−⎟

    ⎠ ⎞

    ⎜ ⎝ ⎛ +

    +≤ 4 ln12ln

    emp

    δ

    Mit Wahrscheinlichkeit 1-δAnzahl Trainingspunkte

    Empirischer Fehler am Trainingsset

    Minimal möglicher Fehler

  • SS 2009 Maschinelles Lernen und 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 Zusammenhang vgl. Boosting: Punkte an der Entscheidungsgrenze bekommen gr