Ziel dieser 5 Minuten Präsentation zum Kernel-Trick ist es einen kurzen, verständlichen Einblick in die Funktionsweise eines Radial Basis Funktion (rbf) Kernels mittels einer 3D Visualisierung zu bekommen. Hierzu wird zuerst das Einsatzgebiet des Kernels und seine Arbeitsweise kurz dargelegt, sowie die Berechnungsformel erläutert. Anschließend wird zum Programm GeoGebra gewechselt, da dort eine anschauliche Visualisierung der Berechnung erfolgen kann. Nach diesem Ausflug, wird anhand des Beispiels von GeoGebra die Berechnung eines Support Vector Machine Modells mit dem rbf-Kernel vorgenommen und grafisch das Ergebnis 2 und 3 dimensional dargestellt.

Das R Dokument “SVM” sowie die GeoGebra Datei “RBF_Kernel 4 Punkte.ggb” sind unter folgendem GitHub Projekt zu finden: https://gitlab.web.fh-kufstein.ac.at/2010837035/svm-rbf-kernel

Support Vector Maschinen

Der Kernel-Trick kommt bei Support Vector Maschinen zum Einsatz, deren Algorithmus versucht, eine Grenze mit dem größtmöglichen Abstand zwischen unterschiedlichen Klassen von Daten zu ziehen. Diese Grenze wird über die ihr nächstliegenden Objekte definiert, die auch Stützvektoren genannt werden.

Häufig spricht man von dieser Grenze auch als Hyperebene. Dabei handelt es sich um einen Unterraum, dessen Dimension um 1 kleiner ist als seine Umgebung. Im dreidimensionalen Raum, wäre eine Hyperebene eine zweidimensionale Ebene, während sie im zweidimensionalen Raum einfach eine gerade Linie wäre.

Kernel-Trick

Hieraus folgt, dass die Daten linear trennbar sein müssen, was in den meisten reellen Fälle nicht zutreffend ist. An dieser Stelle kommt der Kernel-Trick zum Einsatz, der den Vektorraum in einen höherdimensionalen Raum überführt, in dem dann die Objekte linear trennbar sind und so eine Hyperebene zur Trennung der Daten definiert werden kann. Bei der anschließenden Rücktransformation, ist diese Hyperebene dann allerdings nicht mehr linear.

Um einem erhöhten Rechenaufwand entgegenzuwirken, der durch künstlich aufgeblähte Dimensionen entstehen könnte, verwendet der Kernel-Trick zwar das Skalarprodukt eines höherdimensionalen Raumes, überführt aber nicht die Merkmale in diesen Raum.

Dieses Skalarprodukt kann durch verschiedene Berechnungen erfolgen (linear, polynomial, radial, etc.). Im folgenden wird näher auf die radiale Berechnung des sogenannten RBF-Kernels eingegangen.

RBF-Kernel

Der sogenannte Radial Basis Funktions Kernel (kurz RBF-Kernel) benutzt die quadrierte Euklidsche Distanz zwischen 2 Stützvektoren sowie einen freien Parameter Sigma zur Berechnung der Skalierung:

\[ {\displaystyle K(\mathbf {x} ,\mathbf {x'} )=\exp \left(-{\frac {\|\mathbf {x} -\mathbf {x'} \|^{2}}{2\sigma ^{2}}}\right)} \] (Quelle:https://en.wikipedia.org/wiki/Radial_basis_function_kernel)

Demonstration in GeoGebra

Zur besseren Demonstration der Arbeitsweise der Radial Basis Funktion (RBF) des Kernels wird das Tool GeoGebra Classic (https://www.geogebra.org/classic) verwendet, welches kostenfrei zum Download unter dem angegebenen Link erhältlich ist.

2 Dimensionale Darstellung zweier Klassen

Zur vereinfachten Darstellung der Arbeitsweise werden 4 Punkte zweier unterschiedlichen Kategorien verwendet, die im zweidimensionalen Bereich nicht linear separierbar sind.

png

Berechnung der 3. Dimension

Nun wird mittels der rbf-Formel die dritte Dimension der Punkte errechnet.

png

Entscheidungsgrenze

Im vorgeführten Beispiel wird manuell eine Entscheidungsgrenze festgelegt, die durch das SVM Modell natürlich automatisch gelernt wird.

png

Trennung der Klassen durch eine Ebene in der 3. Dimension

Anschließend wird zur besseren Verdeutlichung die trennende Ebene eingezeichnet.

png

Berechnung in R

In R gibt es verschiedene Pakete, mit denen die Berechnungen mit dem RBF-Kernel durchführt werden kann. Im folgenden wurde mit dem Paket “caret” gearbeitet.

## Loading required package: lattice
## Loading required package: ggplot2
## Loading required package: carData
## Warning: package 'rgl' was built under R version 4.0.4

Erstellung der Datentabelle

Zur einfachen Darstellung werden die vier Punkte manuell in Form einer Datentabelle geschrieben.

dt <- data.table(ID=1:4)
dt[, Point := c("A","B","C","D")]
dt[, X := c(1,0,1,0)]
dt[, Y := c(1,0,0,1)]
dt[, Category := as.factor(c(1,1,0,0))]
dt

Erstellung des Modells

Die Erstellung des SVM Modells in caret mit einem RBF-Kernel erfolgt mit der Methode “svmRadial” und es können die Parameter Cost (C) und Sigma mitgegeben werden (Quelle: https://topepo.github.io/caret/train-models-by-tag.html#Support_Vector_Machines).

Während die Kostenfunktion bestimmt wie hoch die Fehlertoleranz der Stützvektoren sein darf (welche Stützvektoren werden herangezogen),gibt Sigma wider, wie steil die Kegel in der 3. Dimension sind und somit wie spezifisch die Daten abgegrenzt werden können.

Mit einem kleineren C-Wert und einem kleineren Sigma, werden die Grenzen weniger fehlertolerant und spezifisch können aber dafür besser verallgemeinern und so ein Overfitting verhidnern.

Zur Berechnung des Modells ist es möglich über ein tuneGrid mehrere Werte für C und Sigma zu übergeben. Diese Option ist im folgenden Skript zugunsten der Parameterübergabe auskommentiert.

ctrl <- trainControl(method = "cv")

model <- train(Category ~ X + Y, data = dt, method = "svmRadial",
               #tuneGrid = expand.grid(C = c(0.1, 0.25, 0.5, 1), 
               #sigma = c(0.5, 2, 5, 10, 500)),
               tuneGrid = expand.grid(C = c(params$C), 
               sigma = c(params$s)),
               probability = TRUE,
               trControl = ctrl)

print(model)
## Support Vector Machines with Radial Basis Function Kernel 
## 
## 4 samples
## 2 predictors
## 2 classes: '0', '1' 
## 
## No pre-processing
## Resampling: Cross-Validated (10 fold) 
## Summary of sample sizes: 3, 3, 3, 3 
## Resampling results:
## 
##   Accuracy  Kappa
##   0         0    
## 
## Tuning parameter 'sigma' was held constant at a value of 500
## Tuning
##  parameter 'C' was held constant at a value of 1

2D Plot des Modells

Plottet man das fertige Modell wieder in 2D, so ergibt sich (bei einem hohen Sigma) eine klare Abgrenzung der 2 Kategorien.

dt.all <- expand.grid(
  X = seq(min(dt$X), max(dt$X), 0.02),
  Y = seq(min(dt$Y), max(dt$Y), 0.02))
dt.all$Category <- predict(model, newdata = dt.all)

chart <- ggplot(mapping = aes(X, Y)) + 
  geom_raster(mapping = aes(fill = Category), data = dt.all, alpha = 0.7) + 
  geom_point(mapping = aes(color = Category), data = dt, size = 4)+ 
  scale_fill_manual(values=c("grey", "blue"))  + 
  scale_color_manual(values=c("black", "darkblue"))

print(chart)

### 3D Plot der Punkte

Es gibt auch die Möglichkeit in R einen animierten 3D Scatterplot zu visualisieren. Dieser wird in einem separaten Fenster geöffnet und kann interaktiv gedreht werden.

scatter3d(c(Category) ~ X + Y, data = dt)
## Loading required namespace: mgcv

Da der Output jedoch leider nicht mitgeknitted wird, ist hier zur Übersicht ein Bild eingebunden.

png

Fazit

Support Vector Machines (SVMs) sind einer der beliebtesten und präzisesten Klassifikatoren. Der Kernel der Radial Basis Function (RBF) wurde in SVMs verwendet, um Klassen mit beachtlichem Erfolg zu trennen. Es besteht jedoch eine intrinsische Abhängigkeit vom Anfangswert des Kernel-Hyperparameters.

Daher wird vorgeschlagen zur weiteren Vertiefung in das Thema einen Blick in die Arbeit von Karl Thurnhofer-Hemsi zu werfen, in der er den OKSVM Algorithmus untersucht. Dieser erlernt automatisch den RBF-Kernel-Hyperparameter und passt gleichzeitig die SVM-Gewichte an. Die vorgeschlagene Optimierungstechnik basiert auf einem Gradientenabstiegsverfahren.

(Quelle: https://arxiv.org/abs/2007.08233)