„Ridge Regression“ und „Kernalized Support Vector Machines“:...

10. Mai 2017 1

Dr. Dominik Grimm

„Ridge Regression“ und „Kernalized Support VectorMachines“: Einführung und Vergleich an einem

Anwendungsbeispiel

ProbelehrveranstaltungFakultät für Informatik und MathematikHochschule München

München, 10. Mai 2017

Ridge Regression & Support Vector Machine

10. Mai 2017 Ridge Regression & Support Vector Machine 2

Inhalte & Lernziele dieser Vorlesung

Was ist Ridge Regression?

Einführung ins Thema

Vergleich von Ridge Regression & SVM an einem Beispiel

Was ist eine Kernalized Support Vector Machine?

Zusammenfassung der Vorlesungsinhalte und Ausblick

10. Mai 2017 Ridge Regression & Support Vector Machine 3

Motivation & EinführungRückblick: Lineare Regression

Prei

s in

€

Fläche Wohnung in m2

10. Mai 2017 Ridge Regression & Support Vector Machine 4

Motivation & EinführungRückblick: Lineare Regression

𝒚 = 𝑏 + 𝑤&𝒙Lineare Regression:

𝒙 ∈ ℝ+:Einflussgröße(Feature)𝒚 ∈ ℝ+:Zielvariable(Target)

𝑛:AnzahlTrainingsinstanzen𝑏, 𝑤& ∈ ℝ:Gewichte(Parameter)

10. Mai 2017 Ridge Regression & Support Vector Machine 5

Motivation & EinführungRückblick: Lineare Regression

𝒚 = 𝑏 + 𝑤&𝒙Lineare Regression:

𝒙 ∈ ℝ+:Einflussgröße(Feature)𝒚 ∈ ℝ+:Zielvariable(Target)

𝑛:AnzahlTrainingsinstanzen𝑏, 𝑤& ∈ ℝ:Gewichte(Parameter)

Parameter 𝑏,𝑤& sind unbekannt. Diese müssen gelernt werden.

10. Mai 2017 Ridge Regression & Support Vector Machine 6

Motivation & EinführungRückblick: Lineare Regression

𝒚 = 𝑏 + 𝑤&𝒙

ℒ 𝒘 =0 𝑦2 − 𝑏 + 𝑤&𝑥2 5𝒏

27&

Lineare Regression:

Straffunktion (Loss):

𝒙 ∈ ℝ+:Einflussgröße(Feature)𝒚 ∈ ℝ+:Zielvariable(Target)

𝑛:AnzahlTrainingsinstanzen𝑏, 𝑤& ∈ ℝ:Gewichte(Parameter)

10. Mai 2017 Ridge Regression & Support Vector Machine 7

Motivation & EinführungRückblick: Lineare Regression

𝒚 = 𝑏 + 𝑤&𝒙

ℒ 𝒘 =0 𝑦2 − 𝑏 + 𝑤&𝑥2 5𝒏

27&

Lineare Regression:

Straffunktion (Loss):

𝒙 ∈ ℝ+:Einflussgröße(Feature)𝒚 ∈ ℝ+:Zielvariable(Target)

𝑛:AnzahlTrainingsinstanzen𝑏, 𝑤& ∈ ℝ:Gewichte(Parameter)

Lernen der unbekannten Parameter durch Minimierung der Straffunktion

10. Mai 2017 Ridge Regression & Support Vector Machine 8

Motivation & EinführungRückblick: Lineare Regression

10. Mai 2017 Ridge Regression & Support Vector Machine 9

Motivation & EinführungRückblick: Lineare Regression

Unteranpassung (Underfitting)Das Modell beschreibt die Trainingsdaten nicht ausreichend

10. Mai 2017 Ridge Regression & Support Vector Machine 10

Motivation & EinführungRückblick: Lineare Regression

𝒚 = 𝑏 + 𝑤&𝒙𝟏 + 𝑤5𝒙𝟏𝟐 + 𝑤:𝒙𝟏𝟑 + ⋯+𝑤&==𝒙𝟏𝟏𝟎𝟎

Polynomiale Regression durch Hinzufügen von Features höherer

Ordnung:

10. Mai 2017 Ridge Regression & Support Vector Machine 11

Motivation & EinführungRückblick: Lineare Regression

𝒚 = 𝑏 + 𝑤&𝒙𝟏 + 𝑤5𝒙𝟏𝟐 + 𝑤:𝒙𝟏𝟑 + ⋯+𝑤&==𝒙𝟏𝟏𝟎𝟎

Polynomiale Regression durch Hinzufügen von Features höherer

Ordnung:

100 Features (Einflussgrößen)

120

Trai

ning

sins

tanz

en

120

Trai

ning

sins

tanz

en

Zielvariable y

10. Mai 2017 Ridge Regression & Support Vector Machine 12

Motivation & EinführungRückblick: Polynomiale Regression (m=100; Grad des Polynoms)

10. Mai 2017 Ridge Regression & Support Vector Machine 13

Motivation & EinführungRückblick: Polynomiale Regression (m=100)

Überanpassung (Overfitting)Das Modell generalisiert schlecht auf unbekannten Daten

10. Mai 2017 Ridge Regression & Support Vector Machine 14

Einführung in Ridge Regression

ℒ 𝒘 =1𝑛0 𝑦2 − 𝑏 + 𝒘@𝒙2 5 + 𝛼 𝒘 5

5

BCDEFGH2I2CHE+DIJCHK

𝒏

27&

Ridge Regression Loss:

Ridge Regression

10. Mai 2017 Ridge Regression & Support Vector Machine 15

Einführung in Ridge Regression

Ridge Regression Loss:

Ridge Regression

𝒘 55 =0𝑤L5 = 𝒘@𝒘

�

LQuadrierte L2-Norm

Lernen der unbekannten Parameter durch Minimierung der Straffunktion

ℒ 𝒘 =1𝑛0 𝑦2 − 𝑏 + 𝒘@𝒙2 5 + 𝛼 𝒘 5

5

BCDEFGH2I2CHE+DIJCHK

𝒏

27&

10. Mai 2017 Ridge Regression & Support Vector Machine 16

Einführung in Ridge RegressionIntuition Ridge Regression

w1

w2LQ ℒ 𝒘 =

1𝑛0 𝑦2 − 𝑏 + 𝒘@𝒙2 5

𝒏

27&

10. Mai 2017 Ridge Regression & Support Vector Machine 17

Einführung in Ridge RegressionIntuition Ridge Regression

w1

w2LQ

w*

ℒ 𝒘 =1𝑛0 𝑦2 − 𝑏 + 𝒘@𝒙2 5 + 𝛼 𝒘 5

5𝒏

27&

10. Mai 2017 Ridge Regression & Support Vector Machine 18

Einführung in Ridge RegressionIntuition Ridge Regression

ℒ 𝒘 =1𝑛0 𝑦2 − 𝑏 + 𝒘@𝒙2 5 + 𝛼 𝒘 5

5𝒏

27&

w1

w2LQ

w*

Effekt eines kleinen α

Regularisierung hat einen schwachen Effekt auf Parameter

(Gefahr von Overfitting)

10. Mai 2017 Ridge Regression & Support Vector Machine 19

Einführung in Ridge RegressionIntuition Ridge Regression

ℒ 𝒘 =1𝑛0 𝑦2 − 𝑏 + 𝒘@𝒙2 5 + 𝛼 𝒘 5

5𝒏

27&

w1

w2LQ

w* Effekt eines großen α

Regularisierung hat einen starken Effekt auf die Parameter

(Gefahr von Underfitting)

10. Mai 2017 Ridge Regression & Support Vector Machine 20

Einführung in Ridge RegressionEffekt der L2-Regularisierung auf die Gewichte/Parameter

UnteranpassungÜberanpassung

10. Mai 2017 Ridge Regression & Support Vector Machine 21

Einführung in Ridge RegressionWie findet man den optimalen Parameter α?

Test FoldTraining Folds

Subtraining Subtest

Trainiere mit kleinem alpha Teste

Trainiere mit hohem alpha Teste

Erhöhe alpha TesteTrainiere mit bestem alpha

10. Mai 2017 Ridge Regression & Support Vector Machine 22

Einführung in Ridge RegressionWie findet man den optimalen Parameter α?

Verschachtelte k-fache Kreuzvalidierung mit interner Liniensuche

10. Mai 2017 Ridge Regression & Support Vector Machine 23

Einführung in Ridge RegressionBeispiel: Ridge Regression (m=100)

10. Mai 2017 Ridge Regression & Support Vector Machine 24

Einführung in Ridge RegressionBeispiel: Ridge Regression (m=100)

Optimale Abwägung zwischen zu einfachem und zu komplexem Model durch L2-Regularisierung

10. Mai 2017 Ridge Regression & Support Vector Machine 25

Zusammenfassung Ridge RegressionWas haben wir gelernt?

• Ridge Regression wird bei Regressionsproblemen verwendet, welcheviele (korrelierten) Features besitzt (und/oder wenige Trainings-Instanzen), um eine Unter- oder Überanpassung des Models zuvermeiden.

• Ridge Regression ist eine überwachte (supervised) Lernmethode, welcheeinen Strafterm besitzt, um die Gewichte (Parameter) derRegressionsmethode zu regularisieren.

• Der Strafterm entspricht der L2-Norm.

• Den optimalen Hyperparameter α findet man mittels verschachtelter k-fachen Kreuzvalidierung.

10. Mai 2017 Ridge Regression & Support Vector Machine 26

Einführung in Support Vector MachinesRegression vs. Klassifikation

Regression Klassifikation

𝒚 ∈ ℝ+:Zielvariable(Target) 𝒚 ∈ {−1,1}+:Zielvariable(Label)

10. Mai 2017 Ridge Regression & Support Vector Machine 27

Einführung in Support Vector MachinesKlassifizieren mit einer Entscheidungsfunktion

𝒘𝑻𝒙 + 𝑏 = 0

𝒘𝑻𝒙 + 𝑏 < 0

𝒘𝑻𝒙 + 𝑏 > 0

10. Mai 2017 Ridge Regression & Support Vector Machine 28

Einführung in Support Vector MachinesKlassifizieren mit einer Entscheidungsfunktion

𝑓 𝒙 = 𝑠𝑔𝑛(𝒘@𝒙 + 𝑏)

Entscheidungsfunktion (Decision Function):

Vorzeichenfunktion (Sign Function):

𝑠𝑔𝑛 𝑧 = Z+1 falls 𝑧 > 00 falls 𝑧 = 0−1 falls 𝑧 < 0

10. Mai 2017 Ridge Regression & Support Vector Machine 29

Einführung in Support Vector MachinesKlassifizieren mit einer Entscheidungsfunktion

𝒘𝑻𝒙 + 𝑏 = 0

10. Mai 2017 Ridge Regression & Support Vector Machine 30

Einführung in Support Vector MachinesKlassifizieren mit einer Entscheidungsfunktion

𝒘𝑻𝒙 + 𝑏 = 0?

10. Mai 2017 Ridge Regression & Support Vector Machine 31

Einführung in Support Vector MachinesKlassifizieren mit einer Entscheidungsfunktion

𝒘𝑻𝒙 + 𝑏 = 0?

10. Mai 2017 Ridge Regression & Support Vector Machine 32

Einführung in Support Vector MachinesKlassifizieren mit einer Entscheidungsfunktion

Falls zwei Klassen mit einer linearen Funktion trennbar sind, gibt es unendlich viele Entscheidungsfunktionen

10. Mai 2017 Ridge Regression & Support Vector Machine 33

Einführung in Support Vector MachinesHard-Margin SVM (Vapnik und Chervonenkis, 1974)

10. Mai 2017 Ridge Regression & Support Vector Machine 34

Einführung in Support Vector MachinesHard-Margin SVM (Vapnik und Chervonenkis, 1974)

Margin= 𝟐𝒘 `

`

𝒘𝑻𝒙 + 𝑏 = 0

𝒘𝑻𝒙 + 𝑏 = −1

𝒘𝑻𝒙 + 𝑏 = 1

SupportVectors

𝒘

10. Mai 2017 Ridge Regression & Support Vector Machine 35

Einführung in Support Vector MachinesHard-Margin SVM (Vapnik und Chervonenkis, 1974)

subject to 𝑦2 𝒘@𝒙2 + 𝑏 ≥ 1, ∀𝑖 ∈ {1,… , 𝑛}

min𝒘,h

12 𝒘 5

5

Optimierungsproblem mit Nebenbedingung um 𝒘 zu lernen

Je kleiner 𝒘 desto größer die Margin: 𝟐𝒘

Die Nebenbedingung stellt sicher, dass alle Trainingsinstanzen der selben Klasse außerhalb oder auf dem Margin liegen

10. Mai 2017 Ridge Regression & Support Vector Machine 36

Einführung in Support Vector MachinesHard-Margin SVM (Vapnik und Chervonenkis, 1974)

10. Mai 2017 Ridge Regression & Support Vector Machine 37

Einführung in Support Vector MachinesHard-Margin SVM (Vapnik und Chervonenkis, 1974)

SupportVectorsEs gibt keine Lösung für nicht vollständig linear

trennbare Probleme

10. Mai 2017 Ridge Regression & Support Vector Machine 38

Einführung in Support Vector MachinesHard-Margin SVM (Vapnik und Chervonenkis, 1974)

SupportVectorsEs gibt keine Lösung für nicht vollständig linear

trennbare Probleme

Erlaube die Fehlklassifikation von Trainingsinstanzen

10. Mai 2017 Ridge Regression & Support Vector Machine 39

Einführung in Support Vector MachinesSoft-Margin SVM: C-SVM (Cortes und Vapnik, 1995)

10. Mai 2017 Ridge Regression & Support Vector Machine 40

Einführung in Support Vector MachinesSoft-Margin SVM: C-SVM (Cortes und Vapnik, 1995)

subject to 𝑦2 𝒘@𝒙2 + 𝑏 ≥ 1 − 𝜉2, ∀𝑖 ∈ 1,… , 𝑛 , 𝜉2 ≥ 0

min𝒘,h,k

12 𝒘 5

5 + 𝐶0𝜉2

+

2

Erlaube die Fehlklassifikation von Trainingsinstanzen

𝝃 ist ein Schlupfvariable (Slackvariable): Misst den Grad derFehlklassifikation für jede Trainingsinstanz

𝑪 ∈ ℝ ist ein Regularisierungsparameter: Tradeoff zwischen Maximierungder Margin und Minimierung des Trainingsfehlers

10. Mai 2017 Ridge Regression & Support Vector Machine 41

Einführung in Support Vector MachinesSoft-Margin SVM: C-SVM (Cortes und Vapnik, 1995)

subject to 𝑦2 𝒘@𝒙2 + 𝑏 ≥ 1 − 𝜉2, ∀𝑖 ∈ 1,… , 𝑛 , 𝜉2 ≥ 0

min𝒘,h,k

12 𝒘 5

5 + 𝐶0𝜉2

+

2

Erlaube die Fehlklassifikation von Trainingsinstanzen

= min𝒘,h

1𝑛0max(0,1 − 𝑦2(𝒘@𝒙2 + 𝑏))

+

27&p2+DCqrII

+𝜆2 𝒘 5

5

+1𝒘@𝒙2 + 𝑏 →

0

𝜆 =2𝑛𝐶

10. Mai 2017 Ridge Regression & Support Vector Machine 42

Einführung in Support Vector MachinesSoft-Margin SVM: C-SVM (Cortes und Vapnik, 1995)

Kleines 𝑪 führt zu einer großen Margin (à Gefahr von Underfitting)

10. Mai 2017 Ridge Regression & Support Vector Machine 43

Einführung in Support Vector MachinesSoft-Margin SVM: C-SVM (Cortes und Vapnik, 1995)

Großes 𝑪 führt zu einer kleinen Margin (à Gefahr von Overfitting)

10. Mai 2017 Ridge Regression & Support Vector Machine 44

Einführung in Support Vector MachinesNicht-Linear-Trennbare Daten

10. Mai 2017 Ridge Regression & Support Vector Machine 45

Einführung in Support Vector MachinesNicht-Linear-Trennbare Daten

Nicht trennbar mit einer linearen Entscheidungsfunktion

10. Mai 2017 Ridge Regression & Support Vector Machine 46

Einführung in Support Vector MachinesTransformation der Daten in einen höherdimensionalen Raum

ℝ5 → ℝ:Transformation in 3-dimensionalen Raum

𝑥&, 𝑥5 → 𝑧&, 𝑧5, 𝑧: ≔ (𝑥&, 𝑥5, 𝑥&5 + 𝑥55)

10. Mai 2017 Ridge Regression & Support Vector Machine 47

Einführung in Support Vector MachinesTransformation der Daten in einen höherdimensionalen Raum

𝑧&𝑧5

𝑧:

10. Mai 2017 Ridge Regression & Support Vector Machine 48

Einführung in Support Vector MachinesTransformation der Daten in einen höherdimensionalen Raum

𝑧&𝑧5

𝑧:

10. Mai 2017 Ridge Regression & Support Vector Machine 49

Einführung in Support Vector MachinesTransformation der Daten in einen höherdimensionalen Raum

Feature Transformation muss explizit berechnet werden à Unmöglich für unendlich-dimensionale Daten

10. Mai 2017 Ridge Regression & Support Vector Machine 50

Einführung in Support Vector MachinesKerntrick

𝑓 𝒙 = 𝑠𝑔𝑛 0𝛼2𝑦2𝒙@𝒙2 + 𝑏+

27&

10. Mai 2017 Ridge Regression & Support Vector Machine 51

Einführung in Support Vector MachinesKerntrick

𝑓 𝒙 = 𝑠𝑔𝑛 0𝛼2𝑦2𝒙@𝒙2 + 𝑏+

27&

= 𝑠𝑔𝑛 0𝛼2𝑦2𝜙 𝒙 @𝜙(𝒙2) + 𝑏+

27&

Entscheidungsfunktion hängt von Trainingsinstanzen 𝒙nur über Skalarprodukt 𝜙 𝒙 @𝜙(𝒙2) ab

10. Mai 2017 Ridge Regression & Support Vector Machine 52

Einführung in Support Vector MachinesKerntrick

𝑓 𝒙 = 𝑠𝑔𝑛 0𝛼2𝑦2𝜙 𝒙 @𝜙(𝒙2) + 𝑏+

27&

= 𝑠𝑔𝑛 0𝛼2𝑦2𝑘(𝒙, 𝒙2) + 𝑏+

27&

𝑘(𝒙, 𝒙2) = 𝜙 𝒙 @𝜙(𝒙2)

Ersetzt Skalarprodukt und Transformation durch einen Kern (Kernel)

Entscheidungsfunktion hängt von Trainingsinstanzen 𝒙nur über Skalarprodukt 𝜙 𝒙 @𝜙(𝒙2) ab

10. Mai 2017 Ridge Regression & Support Vector Machine 53

Einführung in Support Vector MachinesWarum handelt es sich dabei um einen Trick?

• Wenn man Kernfunktionen verwendet, muss man nichts überden genauen Feature Space wissen. Man benötigt nur eineFunktion, welche ein Ähnlichkeitsmaß zwischen den Featuresberechnet.

• Ein optimaler Kern weist Trainingsinstanzen• einen höheren Ähnlichkeitswert zu, wenn diese zur

gleichen Klasse gehören• einen niedrigeren Ähnlichkeitswert, wenn diese zu

unterschiedlichen Klassen gehören.

10. Mai 2017 Ridge Regression & Support Vector Machine 54

Einführung in Support Vector MachinesBeispiele von Kernen

𝑘 𝒙, 𝒙′ = 𝒙@𝒙′

𝑘 𝒙, 𝒙′ = 𝒙@𝒙y + 𝑐 {

𝑘 𝒙, 𝒙′ = exp −12𝜎5 𝒙 − 𝒙y 5

Linearer Kern

Polynomialer Kern

Gaußsche Radiale Basisfunktion (RBF) Kern

10. Mai 2017 Ridge Regression & Support Vector Machine 55

Zusammenfassung Kernalized Support Vector MachineWas haben wir gelernt?

• Die Support Vector Machine wird im (klassischen Sinne) beiKlassifikationsproblemen verwendet.

• Die Hard-Margin SVM ist eine überwachte (supervised) Lernmethode,welche sich nur auf vollständig linear-trennbare Probleme anwenden lässt.

• Die Soft-Margin SVM (C-SVM) besitzt einen zusätzlichen Strafterm, umeinen optimalen Tradeoff zwischen der Maximierung der Margin und derMinimierung des Trainingsfehler zu finden.

• Der Kerntrick besteht darin, mittels Kernfunktionen nicht-lineare Problemein einem höherdimensionalen Raum zu lösen, ohne die Punkte explizit indiesen Raum projizieren zu müssen.

10. Mai 2017 Ridge Regression & Support Vector Machine 56

AnwendungsbeispielVergleich von Ridge Regression und SVM an einem Anwendungsbeispiel

Neues Medikament für die Therapie eines speziellen

Tumors

10. Mai 2017 Ridge Regression & Support Vector Machine 57

AnwendungsbeispielVergleich von Ridge Regression und SVM an einem Anwendungsbeispiel

Neues Medikament für die Therapie eines speziellen

Tumors

Medikament zeigt eine Wirkung innerhalb von 50 Tagen

Medikament zeigt Wirkung erst nach 50 Tagen, aber mit

erheblichen Nebenwirkungen

10. Mai 2017 Ridge Regression & Support Vector Machine 58

AnwendungsbeispielVergleich von Ridge Regression und SVM an einem Anwendungsbeispiel

Können wir anhand der genetischen Unterschiede (z. B. der Mutationen) zwischen den Patienten die Anzahl der Tage

vorhersagen, ab wann das Medikament eine Wirkung zeigt?

10. Mai 2017 Ridge Regression & Support Vector Machine 59

AnwendungsbeispielVergleich von Ridge Regression und SVM an einem Anwendungsbeispiel

• Anzahl Patienten (Trainingsinstanzen): 400• Anzahl Mutationen (Features): 600

• Zielvariable y: Anzahl der Tage bis Medikament Wirkung zeigt

Können wir anhand der genetischen Unterschiede (z. B. der Mutationen) zwischen den Patienten die Anzahl der Tage

vorhersagen, ab wann das Medikament eine Wirkung zeigt?

10. Mai 2017 Ridge Regression & Support Vector Machine 60

AnwendungsbeispielVergleich von Ridge Regression und SVM an einem Anwendungsbeispiel

Ergebnis Ridge Regression auf Testdaten:

Mittlerer Quadratische Fehler (MSE): 699.56

Ergebnis SVM mit linearen Kern auf Testdaten:

Genauigkeit (Accuracy): 82%

Ergebnis SVM mit RBF Kern auf Testdaten:

Genauigkeit (Accuracy): 93%

10. Mai 2017 Ridge Regression & Support Vector Machine 61

Ausblick auf die nächste VorlesungWas kommt als nächstes?

Ridge Regression

• Herleitung der Lösung für das Optimierungsproblem, um dieParameter w zu lernen

• Implementierung des Algorithmus in Python

Support Vector Machine

• Detaillierte Betrachtung des Optimierungsproblems für Hard-MarginSVM

• Detaillierte Betrachtung des Optimierungsproblems für Soft-MarginSVM

• Praktische Evaluierung unterschiedlicher Kerne

Danksagung

10. Mai 2017 Ridge Regression & Support Vector Machine 62

Berufungsausschuss Allen Zuhörern und Zuhörerinnen

Iconsmade by Freepik from www.flaticon.com is licensed under CCBY3.0

http://grimmdominik.eu/teaching/

Folien und Code zur Vorlesung

Zusätzliche Referenzen• Friedman, J., Hastie, T., & Tibshirani, R. (2001). The elements of statistical learning (Vol. 1).

Springer, Berlin: Springer series in statistics. • Murphy, K. P. (2012). Machine learning: a probabilistic perspective. MIT press. • Schölkopf, B., & Smola, A. J. (2002). Learning with kernels: support vector machines,

regularization, optimization, and beyond. MIT press.

https://github.com/dominikgrimm/ridge_and_svm/