Praxiseinstieg Machine Learning mit Scikit-Learn, Keras und TensorFlow. Aurélien Géron
wie das primale Problem haben. Glücklicherweise ist dies beim Optimierungsproblem einer SVM der Fall,6 sodass Sie sich aussuchen können, ob Sie das primale Problem oder das duale Problem lösen möchten; beide haben die gleiche Lösung. Formel 5-6 zeigt die duale Form der Zielfunktion für eine lineare SVM (wenn Sie an der Herleitung des dualen Problems aus dem primalen Problem interessiert sind, sehen Sie sich Anhang C an).
Formel 5-6: Duale Form der Zielfunktion einer linearen SVM
unter der Bedingungα(i) ≥ 0für i = 1, 2, …, m
Wenn Sie erst einmal den Vektor
Formel 5-7: Von der dualen Lösung zur primalen Lösung
Das duale Problem lässt sich schneller als das primale lösen, wenn die Anzahl Trainingsdatenpunkte kleiner als die Anzahl der Merkmale ist. Bedeutender ist aber, dass es den Kerneltrick ermöglicht, was mit dem primalen nicht funktioniert. Was also ist dieser Kerneltrick überhaupt?
Kernel-SVM
Nehmen wir an, Sie möchten mit zweidimensionalen Trainingsdaten (wie dem Datensatz moons) eine polynomielle Transformation 2. Ordnung durchführen und anschließend einen linearen SVM-Klassifikator auf den transformierten Daten trainieren. Formel 5-8 zeigt die zu verwendende polynomielle Zuordnungsfunktion 2. Grades ϕ.
Formel 5-8: Polynomielle Zuordnung 2. Grades
Beachten Sie, dass der transformierte Vektor drei statt der ursprünglichen zwei Dimensionen besitzt. Betrachten wir nun, was bei einer Anzahl zweidimensionaler Vektoren a und b passiert, wenn wir diese polynomielle Zuordnung 2. Grades anwenden und anschließend das Skalarprodukt7 der transformierten Vektoren berechnen (siehe Formel 5-9).
Formel 5-9: Kerneltrick bei einer polynomiellen Zuordnung 2. Grades
Was halten Sie davon? Das Skalarprodukt der transformierten Vektoren entspricht dem Quadrat des Skalarprodukts der ursprünglichen Vektoren: ϕ(a)T ϕ(b) = (aT b)2.
An dieser Stelle stellt sich die entscheidende Erkenntnis ein: Wenn Sie die Transformation ϕ auf alle Trainingsdatenpunkte anwenden, enthält das duale Problem (siehe Formel 5-6) das Skalarprodukt ϕ(x(i))T ϕ(x(j)). Wenn aber ϕ die in Formel 5-8 definierte polynomielle Transformation 2. Ordnung ist, dann können Sie dieses Skalarprodukt der transformierten Vektoren einfach durch
Die Funktion K(a, b) = (aT b)2 nennt man einen polynomiellen Kernel 2. Grades. Im Machine Learning versteht man unter einem Kernel eine Funktion, mit der sich das Skalarprodukt ϕ(a)T ϕ(b) lediglich aus den ursprünglichen Vektoren a und b berechnen lässt, ohne dass die Transformation ϕ berechnet werden (oder überhaupt bekannt sein) muss. In Formel 5-10 sind einige der gebräuchlichsten Kernels aufgelistet.
Formel 5-10: Gebräuchliche Kernels
| Linear: | K(a, b) = aTb |
| Polynomiell: | K(a, b) = (γaTb + r)d |
| Gaußsche RBF: | K(a, b) = exp(–γ || a – b ||2) |
| Sigmoid: | K(a, b) = tanh(γaTb + r) |
Mercers Theorem
Laut Mercers Theorem muss, wenn eine Funktion K(a, b) einige mathematische Bedingungen, die Mercer-Bedingungen (K muss stetig sein, seine Parameter symmetrisch, sodass gilt K(a, b) = K(b, a) und so weiter), erfüllt, auch eine Funktion ϕ existieren, die a und b in einen anderen Raum abbildet (der möglicherweise sehr viel mehr Dimensionen aufweist), sodass gilt: K(a, b) = ϕ(a)T ϕ(b). Damit können Sie K als Kernel einsetzen, da Sie ja wissen, dass ϕ existiert, selbst wenn Sie ϕ nicht genau kennen. Im Fall des gaußschen RBF-Kernels lässt sich nachweisen, dass ϕ jeden Trainingsdatenpunkt in einen Raum mit unendlich vielen Dimensionen transformiert, es ist also gut, dass Sie die Zuordnung nicht vornehmen müssen!
Einige häufig eingesetzte Kernels (wie der sigmoide Kernel) erfüllen nicht alle Mercer-Bedingungen. In der Praxis funktionieren sie dennoch gut.
Um ein loses Ende müssen wir uns noch kümmern. Formel 5-7 zeigt, wie wir im Fall eines linearen SVM-Klassifikators von einer dualen Lösung zur primalen Lösung gelangen. Wenn Sie aber den Kerneltrick anwenden, erhalten Sie Gleichungen mit ϕ(x(i)).