Vorlesungsaufzeichnung Kernel-Trick (VL 21, erste 32 Minuten)
Motivation: radiale Basisfunktion¶
import numpy as np
import scipy.stats as st
np.random.seed(1234) # scipys .rvs zieht aus dem globalen Generator
# craft synthetic data:
def ringe(n, radius=(8, 9)):
rs = st.multivariate_normal(mean=radius[0]+np.ptp(radius),
cov=np.ptp(radius)/2
).rvs(size=n)
phis = st.uniform.rvs(size=n) * 2 * np.pi
x, y = np.cos(phis), np.sin(phis)
return (rs * np.stack([x, y])).T
n = 2000
sample = ringe(n)
secondsample = st.multivariate_normal.rvs(mean=[0,0], cov=np.eye(2), size=n)
sample = np.concatenate([sample, secondsample])import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(7,7))
ax.scatter(sample[:,0], sample[:,1], alpha=0.2)
plt.show()
Eine geometrische Transformation¶
# this produces the same as meshgrid, but is more explicit:
ticks = 20
frames = 70
x = np.outer(np.linspace(-12, 12, ticks), np.ones(ticks))
y = x.copy().T # transpose
rbf_surface_in_time = np.linspace(0, 1, frames).reshape(1, 1, -1) \
* ((x**2 + y**2).reshape(ticks, ticks, 1))import matplotlib.animation as animation
from IPython import display as ipydisplay
import io, base64
def init(ax):
ax.clear()
ax.set_xlim(-12, 12)
ax.set_ylim(-12, 12)
ax.set_zlim( -1, 350)
ax.set_zticklabels([])
def update_surface(i, ax):
init(ax)
ax.view_init(10, 15+i)
ax.plot_surface(x, y, rbf_surface_in_time[:,:,i])
def update_data(i, ax):
init(ax)
ax.view_init(10, 15+i)
ax.scatter(sample[:,0], sample[:,1],
2*i/frames * (sample[:,0]**2 + sample[:,1]**2),
marker='.', s=50)
def plot_ani(func=update_surface):
fig = plt.figure(figsize=(7, 7))
fig.set_size_inches(9, 9)
ax = plt.axes(projection='3d')
ani = animation.FuncAnimation(fig, func, fargs=(ax,), interval=100,
frames=np.hstack([np.arange(frames),np.arange(frames)[::-1]]))
video = ani.to_html5_video()
# Zusätzlich das letzte Bild als PNG ausgeben: der Web-Export zeigt das Video,
# der PDF-Export (der kein HTML kann) verwendet das Standbild.
png = io.BytesIO()
fig.savefig(png, format='png')
ipydisplay.display({'text/html': video,
'image/png': base64.b64encode(png.getvalue()).decode('ascii')},
raw=True)
plt.close()plot_ani(update_surface)plot_ani(update_data)Diese so transformierten Daten lassen sich nun mit 2-Means clustern!
k-Means im transformierten Raum¶
def radial(x, y):
"""Quadrierter Abstand von (x,y) zum Ursprung: eine einzelne Koordinate
der Feature-Abbildung φ, die wir weiter unten allgemein einführen."""
return x**2 + y**2
xs, ys = sample[:,0], sample[:,1]
zs = radial(xs, ys)
from sklearn.cluster import KMeans
kmeans_fit = KMeans(n_clusters=2, n_init=1, random_state=0).fit(np.stack([xs,ys,zs]).T)from mpl_toolkits.mplot3d import Axes3D
fig = plt.figure(figsize=(10,10))
ax = fig.add_subplot(331, projection='3d')
ax2 = fig.add_subplot(332, projection='3d')
ax3 = fig.add_subplot(333, projection='3d')
for axis in (ax, ax2, ax3):
axis.scatter(xs, ys, zs,
alpha=0.2, c=kmeans_fit.labels_,
cmap='brg')
ax.view_init(elev=10., azim=-50)
ax2.view_init(elev=25., azim=-60)
ax3.view_init(elev=75., azim=-70)
plt.show()
Wir können auch nur die k-Means-Berechnung in diesem größeren Raum (mit dem radialen Feature ) stattfinden lassen, die Labels dann mitnehmen und in unseren ‘alten’ zweidimensionalen Plot darstellen:
fig, ax = plt.subplots(figsize=(7,7))
ax.scatter(sample[:,0], sample[:,1], alpha=0.2,
c=kmeans_fit.labels_,
cmap='brg')
plt.show()
Was wir wirklich brauchten¶
Im k-Means-Verfahren werden die ganze Zeit Abstände gemessen. Es ist daher translations- und rotationsinvariant. Wenn wir außerdem nicht unsere Daten transformieren, sondern lediglich beim Messen der Abstände den Abstandsbegriff aus dem transformierten Raum verwenden, könnte das, je nach Transformation, weniger rechenintensiv sein.
Auch andere Verfahren, wie z.B. k-Nearest Neighbours und Support Vector Machines (was wir beides nicht besprochen haben) beruhen nur auf Abstandsmessungen.
Daten durch Abstände beschreiben¶
Der Kernel-Trick besteht nun darin, die Daten nicht durch die symmetrische Matrix zu beschreiben, sondern durch eine andere Funktion , die die gleiche Rolle spielt wie eine Abstandsmessung in einem transformierten Koordinatensystem.
Der euklidische Abstand ist
Wenn man eine lineare Transformation anwendet auf die Daten, so berechnet man danach
sodass wir für eine Abstandsmessung im transformierten Raum eigentlich gar nicht und ausrechnen müssen, sondern ‘nur’ ziemlich oft anwenden. Wenn wir Glück haben, ist das einfacher.
Oftmals ist ein guter Abstandsbegriff auch das Skalarprodukt selbst bzw. .
Nebenbemerkung, um das zu erläutern: Wir können auch ausrechnen, dass
was für normierte Vektoren (also und ) zeigt, dass es einen engen Zusammenhang zwischen und gibt.
Von der linearen Situation abstrahiert man nun, und lässt eine beliebige Abbildung in einen Vektorraum mit Skalarprodukt zu.
Kernel¶
Man muss bei einem Kernel den Raum und die Abbildung gar nicht kennen, weil für symmetrische positiv definite Funktionen stets eine Konstruktion existiert, sodass damit als Kernel dargestellt werden kann (Satz von Mercer).
Man spricht auch von einem Mercer-Kernel und nennt allgemeiner Funktionen , die nicht notwendig positiv definit oder symmetrisch sind, ebenfalls Kernel-Funktionen.
Man spricht allgemein von der Kernel-Methode, wenn man einen Algorithmus so umformuliert, dass er nur mit den Skalarprodukten der Feature-Vektoren arbeitet, und ersetzt diese dann durch eine Kernelfunktion.
Gausssche Kernel¶
Man beachte, dass wir hier nicht mit vergleichen müssen, weil diese die gleiche Differenz haben. Die sonst übliche Normierung entfällt ebenfalls, weil wir es nicht mit Wahrscheinlichkeiten zu tun haben, sondern mit einem Abstandsbegriff.
from sklearn.metrics.pairwise import rbf_kernel
k = rbf_kernel(sample, gamma=None)
# from the scikit-learn documentation:
# gamma: If None, defaults to 1.0 / n_features.
karray([[1.00000000e+00, 5.99739246e-33, 8.16001067e-14, ...,
6.54905753e-16, 6.68458610e-26, 4.77998504e-22],
[5.99739246e-33, 1.00000000e+00, 6.21026247e-61, ...,
1.97600107e-19, 4.23471174e-21, 1.23356941e-10],
[8.16001067e-14, 6.21026247e-61, 1.00000000e+00, ...,
1.22257133e-15, 7.75803174e-22, 5.76000560e-28],
...,
[6.54905753e-16, 1.97600107e-19, 1.22257133e-15, ...,
1.00000000e+00, 5.54264452e-02, 1.27386311e-02],
[6.68458610e-26, 4.23471174e-21, 7.75803174e-22, ...,
5.54264452e-02, 1.00000000e+00, 1.22581743e-02],
[4.77998504e-22, 1.23356941e-10, 5.76000560e-28, ...,
1.27386311e-02, 1.22581743e-02, 1.00000000e+00]],
shape=(4000, 4000))Nur, was fängt man jetzt mit dem Kernel an?
Zum Beispiel lineare Regression mit Ridge Regularisierung:
from sklearn.kernel_ridge import KernelRidge
# target variable is #cluster,
# given how we created the sample, it simply is:
y = np.hstack([np.zeros(len(sample)//2),np.ones(len(sample)//2)])clf = KernelRidge(kernel="precomputed")
clf.fit(k, y)
y_pred = clf.predict(k)
fig, ax = plt.subplots(figsize=(7,7))
ax.scatter(sample[:,0], sample[:,1], c=y_pred)
plt.show()
Kernel PCA¶
Bei der Hauptachsentransformation werden die Eigenvektoren der Kovarianzmatrix berechnet. Man kann die Daten auch zuerst nichtlinear transformieren, bevor man das tut - oder aber die entsprechend transformierte Kovarianzmatrix verwenden.
from sklearn.decomposition import PCA, KernelPCA
pca = PCA(n_components=2)
kernel_pca = KernelPCA(
n_components=None, kernel="rbf", gamma=0.2, alpha=2.5
)
# these parameters gamma, alpha needed some manual tweaking!sample_pca = pca.fit_transform(sample)# The following may need more than 16 GB of RAM,
# if the sample is large, so we're not going there:
#sample_kernel_pca = kernel_pca.fit_transform(sample)
# Keep it calm, train_size=2000 suffices:
from sklearn.model_selection import train_test_split
smaller_sample, remainder_sample, smaller_y, remainder_y \
= train_test_split(sample, y_pred, train_size=2000, random_state=0)
sample_kernel_pca = kernel_pca.fit_transform(smaller_sample)fig, axs = plt.subplots(ncols = 2, figsize=(8,4))
axs[0].scatter(sample_pca[:,0], sample_pca[:,1],
c=y_pred, alpha=0.2)
axs[1].scatter(sample_kernel_pca[:,0], sample_kernel_pca[:,1],
c=smaller_y, alpha=0.2)
plt.show()
Genau genommen vergrößert Kernel-PCA zunächst die Anzahl an Dimensionen (mit der nichtlinearen Feature-Abbildung), um sie daraufhin linear auf Hauptkomponenten zu transformieren, sodass man wiederum unwichtige Dimensionen wegschmeißen kann. Die erste Hauptkomponente im Feature-Raum entspricht im ursprünglichen Beobachtungsraum keiner Geraden mehr, sondern einer nichtlinearen Kurve.