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,⁶ 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α⁽ⁱ⁾ ≥ 0für i = 1, 2, …, m

      Wenn Sie erst einmal den Vektor gefunden haben, der diese Gleichung minimiert (mit einem QP-Solver), können Sie und berechnen, die das primale Problem über Formel 5-7 minimieren.

       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 Skalarprodukt⁷ 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) = (a^T b)².

      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⁽ⁱ⁾)^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 ersetzen. Also brauchen Sie die Trainingsdaten überhaupt nicht zu transformieren: Ersetzen Sie einfach das Skalarprodukt in Formel 5-6 durch sein Quadrat. Das Ergebnis ist exakt das gleiche, als hätten Sie sich die Mühe gemacht, die Trainingsdaten tatsächlich zu transformieren und anschließend einen linearen SVM-Algorithmus auszuführen. Mit diesem Trick wird der gesamte Prozess rechnerisch wesentlich effizienter.

      Die Funktion K(a, b) = (a^T b)² 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) = a^Tb
Polynomiell:	K(a, b) = (γa^Tb + r)^d
Gaußsche RBF:	K(a, b) = exp(–γ || a – b ||^2)
Sigmoid:	K(a, b) = tanh(γa^Tb + 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⁽ⁱ⁾).