Kerne¶

In this section, we will cover fundamental concepts of non-linear classification by introducing the concept of kernels. First, let us recall what we have seen so far in our section about Lineare Klassifizierung. In linear classification, our task consisted of classifying data points through a hyperplane that could linearly separate the dataset in the features coordinate space. For instance, in a 3d feature space, thus a feature vector such as $(x_1, x_2, x_3) \in \mathbb{R}^3$ , recall that our data is considered linearly separable if there is at least one plane (not line) who can split the points. Unlike linear classification, which assumes a linear relationship between input features and class labels, non-linear classification algorithms use various techniques to capture complex patterns and decision boundaries in the data. In particular, we will look at how we can transform our data into a new coordinate space of higher dimension through kernels, which help us turning the non-linear problem into a linear one.

Kernel ermöglichen es uns, Daten in einen höherdimensionalen Merkmalsraum zu transformieren, in dem eine lineare Trennung möglich wird. Ein Beispiel für einen ML-Algorithmus, der auf Kernel angewiesen ist, um komplexe Muster und Entscheidungsgrenzen in den Daten zu finden, ist Support Vector Machine (SVM).

Merkmalstransformation¶

We will now see how feature transformation works through a 1d example, that is, we have one feature $x \in \mathbb{R}$ . The figure below illustrates the training points ( $n=3$ ).

Beachten Sie aus der Abbildung, dass der Datensatz nicht linear trennbar ist, zumindest nicht im angegebenen Merkmalsraum in 1 Dimension. Um dieses Problem in ein lineares Problem zu verwandeln, können wir eine Merkmalstransformation ( $\phi (x)$ ) durchführen, um nach einer Entscheidungsgrenze in einem höherdimensionalen Raum zu suchen. Beachten Sie in diesem Beispiel, dass wir das 1D-Feature in einen neuen 2D-Feature-Vektor umwandeln können, wobei die zusätzliche Dimension als eine Art neues Feature angesehen werden kann.

x \to \Phi(x) = [\Phi_1 \; \; \; \Phi_2] = [x \; \; \; x^2]

(1)

Original feature space

New feature space

Decision boundary in the new feature space

initial problem before feature transformation — Figure 1:1: Trainingsdaten im ersten Feature Space.

By performing feature transformation as illustrated in the step 2: training dataset in the new feature space $\Phi(x)$ (see figure above), we can find a classifier $h(x, \theta, \theta_o)$ with a decision boundary defined by $\theta$ and the offset parameter $\theta_0$ :

h (x, \theta, \theta_0) = sign(\theta \cdot \Phi(x) + \theta_0)\\ \therefore h (x, \theta, \theta_0) = sign(\theta_1 x + \theta_2 x^2 + \theta_0)

(2)

Exercise 1: Feature transformation with kernels

The figure below shows a dataset that is not linearly separable in the original feature space $x = [x_1, x_2]$ . Can you think of a kernel function to create a higher-dimensional feature space where there is a decision boundary solvable through linear classification?

Figure 4:Übung 1 zu Kernel

Solution

Wir fangen an, dieses Problem zu lösen, indem wir uns an die Gleichung eines Umfangs erinnern, der nicht im Ursprung zentriert ist:

(x_1+a)^2+(x_2+b)^2 = c

(3)

Erweiterung der obigen Gleichung erhalten wir:

x_1^2 + 2 a x_1 + a^2 + x_2^2 + 2 b x_2 + b^2 -c = 0 \\

(4)

Die Begriffe $a$ , $b$ und $c$ sind Konstanten, so dass wir die Gleichung vereinfachen können:

2 a x_1 + 2 b x_2 + x_1^2 + x_2^2 + C = 0 \\

(5)

Wobei $C = (a^2 + b^2 - c)$ .

Note that the above equation denotes our non-linear decision boundary in the original feature space $x \in \mathbb{R}^2$ and thus should equal the expression $\theta \cdot \Phi(x) +\theta_0$ :

\theta \cdot \Phi(x) + \theta_0 = x_1^2 + 2 a x_1 + x_2^2 + 2 b x_2 + C

(6)

which means that $\theta_0 = C$ , $\Phi(x) = [x_1 \;\; x_2 \;\; x_1^2 \;\; x_2^2]$ , and thus we can also find $\theta$ in terms of the circumference parameters:

\theta = [2a \;\; 2b \;\; 1 \;\; 1]

(7)

Kerne

Kerne¶

Merkmalstransformation¶

Mehr kommt bald...¶