Embed Size (px)
Citation preview
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/
