Mustererkennung - fbmn.h-da.deneubecker/uploads/Lehre/ME.4.SVM.2018_11_27.pdf · Der Weight-Vektor (Normale der Hyperebene) ist eine Linearkombination (bestimmter) Merkmalsvektoren

Mustererkennung

Support Vector Machines

R. Neubecker, WS 2018 / 2019

2Support Vector Machines

Support Vector Machines (SVM)

kommen aus der statistischen Lerntheorie

gehören zu den „optimalen Klassifikatoren“ = SVMs minimieren nicht nur den Trainingsfehler, sondern auch den (voraussichtlichen) Klassifikationsfehler bei neuen Datensätzen

bestehen aus 2 Kernkomponenten

a) Large Margin

b) Abbildung mit Kernelfunktionen für nicht linear-separierbare Daten

(Diese Konzepte sind nicht auf SVM beschränkt)


Maximum Margin: eine Optimierungsaufgabe

Kerneltrick: Problemlösung in höheren Dimensionen

Varianten: Weiche Abstände

4Support Vector Machines: Maximum margin

Maximum Margin Optimierungsziel: Hyperebene mit

größtmöglichem Abstand zu den Trainingsvektoren


Maximum Margin

Optimierungsziel: Hyperebene mit dem größtmöglichem Abstand zu den Trainingsvektoren

Hyperebene wird durch die am nächsten liegenden Merkmalsvektoren fixiert = Support Vectors (Stützvektoren)

Anzahl Support Vectors ≥ 𝑁+1 (=Dim. Merkmalsraum +1) ≪ 𝑀 (= Stichprobengröße).Alle anderen Mitglieder der Klasse werden dann unwichtig.

Sinnvolle Vorgabe: Abstand zu den Support Vectors (Margin) auf beiden Seiten soll gleich groß sein


Maximum Margin als mathematisches Kriterium

𝑤x1

x2

|w0|



𝑤x1

x2

Margin 2b

|w0|

Ԧ𝑥𝑠



Erinnerung: Hyperebene wird durch Normalenvektor 𝑤 und Abstand 𝑤0 definiert:

𝑔 Ԧ𝑥 = 𝑤𝑡 Ԧ𝑥 + 𝑤0 > 0 ↔ 𝜔1

𝑔 Ԧ𝑥 = 𝑤𝑡 Ԧ𝑥 + 𝑤0 < 0 ↔ 𝜔2

mit Vorzeichen 𝑠1 = 1, 𝑠2 = −1 (Klassenzugehörigkeit)

Einführung Margin: 𝑠𝑖 𝑔 Ԧ𝑥 = 𝑠𝑖 𝑤𝑡 Ԧ𝑥 + 𝑤0 ≥ 𝑏

Supportvektoren Ԧ𝑥𝑠 liegen genau im Abstand 𝑏: 𝑠𝑖 𝑔 Ԧ𝑥𝑠 = 𝑏

⇒ 𝑠𝑖𝑤𝑡

𝑤Ԧ𝑥𝑠 +

𝑤0

𝑤=

𝑏

𝑤→ Max!

Länge des Normalenvektors ist noch frei

→ Umskalierung 𝑏 = 1 kanonische Hyperebene 𝑠𝑖 𝑔 Ԧ𝑥 ≥ 1

→ Margin-Forderung ↷ |𝑤| :

1

𝑤→ Max!

𝑠𝑖 𝑔 Ԧ𝑥 > 0


Maximum Margin mathematisch realisieren

Fragestellung: 1

𝑤→ Max ⟺ 𝑤 2 → Min

unter den Nebenbedingungen ℎ𝑘 = 𝑠𝑘 𝑤𝑡 Ԧ𝑥𝑘 + 𝑤0 − 1 ≥ 0

für alle Ԧ𝑥𝑘 aus dem Trainingsdatensatz (𝑘= Index des Stichprobenmitglieds)

Lösungsansatz: Erweiterte Lagrange-Multiplikatoren (Karush-Kuhn-Tucker: KKT)

ℒ𝑃 𝑤,𝑤0, 𝛼𝑘 =1

2𝑤 2 −

𝑘𝛼𝑘 𝑠𝑘 𝑤𝑡 Ԧ𝑥𝑘 + 𝑤0 − 1 → Min

Lösung: Partielle Ableitungen der Lagrange-Funktion = 0 setzen

i) 𝛿

𝛿𝑤𝑛ℒ = 0 → 𝛻𝑤 ℒ = 𝑤 − σ𝑘 𝛼𝑘𝑠𝑘 Ԧ𝑥𝑘 = 0

ii) 𝛿

𝛿𝑤0ℒ = − σ𝑘 𝛼𝑘𝑠𝑘 = 0

iii) sowie KKT-Bedingungen 𝛼𝑘ℎ𝑘 = 0 und 𝛼𝑘 ≥ 0


Maximum Margin und Hyperebene festgelegt

Interpretation

iii) 𝛼𝑘ℎ𝑘 = 0 ⇒ 𝛼𝑘 ∙ 𝑠𝑘 𝑤𝑡 Ԧ𝑥𝑘 + 𝑤0 − 1 = 0

Entweder ist 𝛼𝑘 = 0 : Nebenbedingung ist inaktiv, betrachteter Punkt Ԧ𝑥𝑘 wird richtig klassifiziert, liegt außerhalb der Margin-Grenzen

oder die Nebenbedingung ℎ𝑘 ist „aktiv“, d.h. der betrachtete Merkmalsvektor Ԧ𝑥𝑘liegt genau auf dem Margin = Support Vektor

i) 𝑤 = σ𝑘 𝛼𝑘𝑠𝑘 Ԧ𝑥𝑘

Der Weight-Vektor (Normale der Hyperebene) ist eine Linearkombination (bestimmter) Merkmalsvektoren aus dem Trainingsdatensatz – nämlich der Support Vektoren


Maximum Margin – Duale Formulierung

Duale FormulierungEinsetzen von i) … iii) in ℒ und Umformen ergibt eine alternative Lagrange-Funktion

ℒ𝐷 𝛼𝑖 , Ԧ𝑥𝑗 =𝑘𝛼𝑘 −

1

2

𝑘

𝑙𝛼𝑘𝛼𝑙 𝑠𝑘𝑠𝑙 Ԧ𝑥𝑘 Ԧ𝑥𝑙 → Min

mit den Bedingungen σ𝛼𝑘s𝑘 = 0 und 𝛼i ≥ 0

d.h. gesucht sind jetzt (nur noch) die 𝛼𝑖

Unterschiede zur Primalen Version

• Suche im 𝑀-dimensionalen Raum (𝑀 = Größe Trainingsdatensatz),statt in 𝑁 Dimensionen des Merkmalsraums (= Dimensionalität von 𝑤)

• Nur wenige 𝛼𝑖 ≠ 0 (wenige Supportvektoren)

• Merkmalsvektoren des Trainingsdatensatzes kommen nur als Skalarprodukt vor!


Maximum Margin zusammengefasst

Training

• Gegeben: Trainingsdatensatz Ԧ𝑥𝑘 und Klassenzugehörigkeit über 𝑠𝑘

• Aufgabe: Suche (numerisch) die 𝛼𝑖 , welche

den Ausdruck min𝛼𝑖

σ𝑘 𝛼𝑘 −1

2σ𝑘σ𝑙 𝛼𝑘𝛼𝑙𝑠𝑘𝑠𝑙 Ԧ𝑥𝑘 Ԧ𝑥𝑙 minimieren

und die Bedingungen 𝛼𝑖 ≥ 0 und σ𝑖 𝛼𝑖𝑠𝑖 = 0 erfüllen.

→ Supportvektoren, die Hyperebene (mit maximalem Margin) festlegen

𝑔 Ԧ𝑥𝑢 = 𝑤𝑡 Ԧ𝑥𝑢 + 𝑤0

mit 𝑤 = σ𝑘 𝛼𝑘𝑠𝑘 Ԧ𝑥𝑘

und 𝑤0 = −max𝑖:𝑠𝑖=−1

𝑤𝑡 Ԧ𝑥𝑖 − min𝑖:𝑠𝑖=+1

[𝑤𝑡 Ԧ𝑥𝑖]

2

→ Klassifikator gefunden


Aber …

… was tun, wenn die Klassen gar nicht linear separierbar sind?

Option: Nicht-linear separieren! → Kerneltrick

Option: Fünfe gerade sein lassen und nicht perfekt separieren Soft Margin


Large Margin: eine Optimierungsaufgabe



16Support Vector Machines: Kerneltrick

Linear nicht separierbar? Höhere Dimensionen!

Linear nicht separierbare Merkmale können durch Abbildung in einen höher-dimensionalen Raum linear trennbar werden (vgl. Abschnitt in „Perzeptron“)

Ԧ𝑥 ↦ 𝜙( Ԧ𝑥) : ℝ𝑁 → ℝ𝐷 mit 𝐷 > 𝑁

Zielraum ℝ𝐷 wird auch als Feature Space bezeichnet

Hyperebene im Zielraum = komplexere, u.U. nicht-zusammenhängende Hyperfläche im urspr. Merkmalsraum

Aufgabe: Suche nach trennender Hyperebene in ℝ𝐷 für die 𝜙( Ԧ𝑥i) ,

d.h. alles wie vorher, nur für 𝜙( Ԧ𝑥) statt für Ԧ𝑥 :

vorher min𝛼𝑖


2σ𝑘σ𝑙 𝛼𝑘𝛼𝑙𝑠𝑘𝑠𝑙 ⋅ Ԧ𝑥𝑘

𝑡 Ԧ𝑥𝑙

→ jetzt min𝛼𝑖


2σ𝑘σ𝑙 𝛼𝑘𝛼𝑙𝑠𝑘𝑠𝑙 ⋅ 𝜙

𝑡 Ԧ𝑥𝑘 𝜙( Ԧ𝑥𝑙)

In Dualer Formulierung des SVM-Problems kommt Ԧ𝑥 nur als Skalarprodukt vor,

Ԧ𝑥𝑘𝑡 Ԧ𝑥𝑙 ↦ 𝜙𝑡 Ԧ𝑥𝑘 𝜙 Ԧ𝑥𝑙 . Die Funktion 𝜙 selbst muss nicht mal bekannt sein.


Kernel

Definition Kernel-Funktion: 𝑘 Ԧ𝑥𝑖 , Ԧ𝑥𝑗 = 𝜙𝑡 Ԧ𝑥𝑖 𝜙 Ԧ𝑥𝑗

Kernel Trick: SVM kann trainiert und genutzt werden, ohne dass die Transformation

Ԧ𝑥 ↦ 𝜙 Ԧ𝑥 explizit berechnet werden muss. Nötig ist nur der einfachere Kernel 𝑘( Ԧ𝑦, Ԧ𝑧).

Der Kernel-Trick an einem Beispiel

Ԧ𝑥 =𝑥1𝑥2

↦ 𝜙 Ԧ𝑥 =

𝑥12

𝑥22

2 𝑥1𝑥2

ℝ2 ↦ ℝ3

𝜙𝑡 Ԧ𝑥𝑖 𝜙 Ԧ𝑥𝑗 = 𝑥𝑖12 𝑥𝑖2

2 2 𝑥𝑖1𝑥𝑖2

𝑥𝑗12

𝑥𝑗22

2 𝑥𝑗1𝑥𝑗2

= ⋯

= Ԧ𝑥𝑖𝑡Ԧ𝑥𝑗

2= 𝑘( Ԧ𝑥𝑖 , Ԧ𝑥𝑗)

d.h. die Funktion 𝜙() muss gar nicht explizit berechnet werden.


Beispiele für Kernel-Funktionen

Linearer Kernel 𝑘 Ԧ𝑥𝑖 , Ԧ𝑥𝑗 = Ԧ𝑥𝑖𝑡 ⋅ Ԧ𝑥𝑗

Polynomielle Kernel 𝑘 Ԧ𝑥𝑖 , Ԧ𝑥𝑗 = 𝑎 ∙ Ԧ𝑥𝑖𝑡 Ԧ𝑥𝑗 + 𝑏

𝑑mit 𝑑 > 0

enthält Polynome bis zur Ordnung 𝑑

Gaußscher Kernel 𝑘 Ԧ𝑥𝑖 , Ԧ𝑥𝑗 = exp(− Ԧ𝑥𝑖 − Ԧ𝑥𝑗2/2𝜎2)

• Für jeden Satz von Merkmalsvektoren Ԧ𝑥1, Ԧ𝑥2, … Ԧ𝑥𝑛 gilt: die transformierten

Merkmalsvektoren 𝜙( Ԧ𝑥1), 𝜙( Ԧ𝑥2), …𝜙( Ԧ𝑥𝑛) sind linear unabhängig

→ Dimensionalität des Feature Space = Anzahl Trainingsvektoren

• Gehört zur Klasse der Radialen Basisfunktionen: 𝑓 Ԧ𝑥𝑖 , Ԧ𝑥𝑗 = 𝑓 | Ԧ𝑥𝑖 − Ԧ𝑥𝑗|

Hyperbolischer Tangens Kernel 𝑘 Ԧ𝑥𝑖 , Ԧ𝑥𝑗 = tanh 𝛾 Ԧ𝑥𝑡 Ԧ𝑥𝑗 + 𝛿


Welche Funktionen 𝒌(𝒙 , 𝒙 ′) sind Kernel-Funktionen?

Kann ich irgendeine Funktion von 2 Merkmalsvektoren als Kernelfunktion nehmen? (Natürlich nicht)

Hinreichend: Mercer-Bedingungen:

• Symmetrisch 𝑘 Ԧ𝑥, Ԧ𝑥′ = 𝑘 Ԧ𝑥′, Ԧ𝑥

• Für einen beliebigen Satz von Merkmalsvektoren muss die Kernel-Matrix 𝐾𝑖𝑗 = 𝑘( Ԧ𝑥𝑖 , Ԧ𝑥𝑗) positiv definit sein.

(aber: andere Funktionen können ggf. auch funktionieren)

Es gibt Regeln, wie man aus bekannten Kernel-Funktionen neue Kernel konstruieren kann

Fertige SVM-Implementationen bieten Auswahl guter Kernel-Funktionen an

Resumé: SVM mit Kernel

Alles wie vorher (Maximum Margin),

nur Skalarprodukt Ԧ𝑥𝑘𝑡 Ԧ𝑥𝑙 ersetzen durch Kernel-Funktion 𝑘( Ԧ𝑥𝑘

𝑡 , Ԧ𝑥𝑙)


Large Margin: eine Optimierungsaufgabe



21Support Vector Machines: Soft Margin

Soft Margin SVM: lockere Bedingungen Lockern der Bedingungen bei nicht linear-separierbaren Trainingsdatensätzen:

Tolerierte Ausreißer müssen nicht außerhalb des Margin liegen, bzw. müssen gar nicht korrekt klassifiziert werden

Fallunterscheidung: Es gilt

• 𝑠𝑖 𝑤𝑡 Ԧ𝑥 + 𝑤0 ≥ 𝑏 für alle korrekt klassifizierten, außerhalb Margin liegenden

• 𝑠𝑘 𝑤𝑡 Ԧ𝑥 + 𝑤0 ≥ 0 für Ausreißer, verletzt gefordertem Margin, aber noch korrekt klassifiziert

• 𝑠𝑘 𝑤𝑡 Ԧ𝑥 + 𝑤0 ≤ 0 für Ausreißer, falsch klassifiziert

22Support Vector Machines: Soft Margin

Soft Margin SVM: Umsetzung

Optimierungsproblem

Vorher 𝑤 2 → Min

Jetzt 𝑤 2 + 𝐶 σ𝑘 𝜉𝑘 → Min

Slack variable 𝜉𝑘 (Slackness: Laschheit, Nachlässigkeit), bewertet Ausreißer𝑘: Indices der Ausreißer,0 < 𝜉𝑘 ≤ 1: zwischen Hyperebene und Margin (noch korrekt klassifiziert), 𝜉𝑘 > 1: falsch klassifiziert.

Bestrafungsgewicht 𝐶 (Penalty Parameter), gilt (in dieser Formulierung) für alle Ausreißer gemeinsam.𝐶 → ∞ Ausreißer werden gar nicht toleriert, 𝐶 → 0 Ausreißer sind egal.

Soft Margin lässt sich also einfach in die Formulierung des Optimierungsproblems einbauen

Je größer 𝐶, desto mehr versucht Optimierungsalgorithmus eine Lösung ohne Ausreißer zu finden

Wirkung von 𝐶 anschaulich: beschränkt den Einfluss jedes einzelnen Mitglieds des Trainingsdatensatzes in der Optimierung Wenn jedes korrekt klassifiziert werden muss → unendliches Gewicht 𝐶 → ∞


Zusammenfassung Support Vector Machines

SVM sind sehr bekannte Klassifikatoren, werden in unterschiedlichsten Gebieten erfolgreich eingesetzt

In den Trainingsdatensatz wird zwischen zwei Klassen eine Hyperfläche mit maximalem Abstand (Margin) zu den Merkmalsvektoren der Stichproben gelegt → Robust gegen Variationen zwischen Trainings- und Testdaten

Die Support-Vektoren definieren („stützen“) diese Fläche von beiden Seiten

Mithilfe des Kernel-Tricks können auch nicht linear-separierbare Klassen getrennt werden (ohne das die Abbildung des Merkmalsraums bekannt sein muss).

Jede nicht linear-separierbare Stichprobe wird bei genügend hoher Einbettungsdimension linear trennbar!

Variante Soft Margin lässt zu, dass einige der Trainingsvektoren (Ausreißer) nicht mit Margin oder ganz falsch klassifiziert werden

Es gibt speziell angepasste numerische Optimierungsverfahren und bewährte Kernel-Funktionen → fertige SVM in SW-Bibliotheken


Literatur Support Vector Machines

Christopher M. Bishop, Pattern recognition and machine learning, Springer VerlagKapitel Sparse kernel machines

Christopher J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, Vol. 2 (2), pp. 121-167 (1998)

Documents

Mustererkennung - fbmn.h-da.deneubecker/uploads/Lehre/ME.4.SVM.2018_11_27.pdf · Der Weight-Vektor (Normale der Hyperebene) ist eine Linearkombination (bestimmter) Merkmalsvektoren