Dimensionality Reduction mit Random Projections

Einführung

Ob ChatGPT (mit dem zugrunde liegenden GPT4) oder Forschungsprojekte zum autonomen Fahren, eines haben diese Projekte gemeinsam: große Datenmengen. Große Datenmengen stellen die Entwickler von “Deep Learning”-Modellen vor verschiedene Herausforderungen, wie z.B. enormer Hardwarebedarf, schwierige oder unmögliche Visualisierung, (extrem) lange Trainingszeiten oder schlechte Trainingsergebnisse aufgrund des Fluchs der Dimensionalität. Um die Dimensionalität eines Datensatzes zu reduzieren und dennoch relevante Informationen zu erhalten, wurde die Dimensionalitätsreduktion mit verschiedenen Algorithmen entwickelt. In diesem Beitrag möchte ich das Prinzip der Random Projections vorstellen.

Mathematische Grundlagen

Um über die mathematischen Grundlagen der Random Projections zu sprechen, nehmen wir an das wir Daten aus einem euklidischen Raum mit hoher Dimension haben, beispielsweise $\mathbb{R}^m$ wobei $m \in \mathbb{N}$.

Die euklidische Eigenschaft des Vektorraums ist notwendig, um Abstände zwischen zwei (oder mehreren) Punkten in unserem Vektorraum berechnen zu können.

Weiter nehmen wir an, dass $m$ groß genug ist und wir Daten aus $\mathbb{R}^m$ in einen Raum kleiner Dimension bringen wollen, also $\mathbb{R}^n$ mit $n < m$ und $n \in \mathbb{N}$. In diesem Fall können wir auf das Johnson–Lindenstrauss-Lemma zurückgreifen.

Das Johnson–Lindenstrauss-Lemma besagt, dass wir den oben beschriebenen Prozess umsetzen können uns ein solches $n \in \mathbb{N}$ existiert, welches die Punkten aus $\mathbb{R}^m$ in $\mathbb{R}^n$ einbetten kann und die Distanzen zwischen den Punkten aus $\mathbb{R}^m$ ungefähr in $\mathbb{R}^n$ beibehält. ^{1 2 3 4}

Die Erhaltung der Distanzen zwischen den einzelnen Punkten ist hierbei von großer Wichtigkeit, da diese die Unterschiedlichkeit der einzelnen Datenpunkt beschreibt. Würden Distanzen nicht (grob) erhalten bleiben, könnten so zwei (potenziell) sehr unterschiedliche Datenpunkte in $\mathbb{R}^n$ sehr ähnlich erscheinen, obwohl diese objektiv sich nicht ähnlich sind.

Der noch fehlende Schritt zum reduzieren des Datensatzes beinhaltet die Auswahl der Datenpunkte. Dies wird bei Random Projections erreicht, indem wir eine Zufallsmatrix $R \in \mathbb{R}^{N \times n}$ generieren, wobei $N \in \mathbb{N}$ die Anzahl der Datenpunkte im Datensatz darstellt.

Eine Zufallsmatrix $R$ ist kurzgesagt eine Matrix, deren Elemente $r_{ij}$ Zufallsvariablen sind.

Zur Generierung der Elemente $r_{ij}$ können nun viele Ansätze verwendet werden. Häufig werden $r_{ij}$ als Elemente einer Gauss’schen Normalverteilung angenommen. Hierzu gibt es effiziente Methoden zur Generierung dieser Elemente. Alternativ wurde gezeigt, dass die Generierung durch eine bedeutend einfachere Verteilung erzeugt werden können: ^{1 5 6 7}

Mit der hier vorgestellten Methode der Zufallszahlenziehung kann eine höhere Effizienz in Bezug auf die benötigte Zeit erreicht werden, auch wenn die Ergebnisse möglicherweise etwas schlechter ausfallen.

Anwendungsbeispiel

Als Anwendungsbeispiel verwenden wir einen Datensatz, der im Idealfall relativ viele Eingabedimensionen aufweisen kann. Bilder eignen sich hierfür ideal, da sie bereits bei kleinen Bildgrößen eine hohe Anzahl an Eingansdimensionen aufweisen. Im Rahmen dieser Arbeit haben wir uns entschieden, mit dem Datensatz colorectal_histology zu arbeiten. Dieser Datensatz enthält Bilder von verschiedenen Gewebearten, wobei der Schwerpunkt des Datensatzes auf Darmkrebs liegt. Ein Algorithmus soll diesen Datensatz in insgesamt acht verschiedene Gewebetypen klassifizieren. ⁸

Die Bilder des Datensatzes sind insgesamt $150$ Pixel hoch, $150$ Pixel breit und auf drei verschiedene Farbkanäle verteilt, liegen also als RBG-Bilder vor. Wir erhalten also einen Datensatz, der insgesamt die Eingabedimensionen $67500$ hat.

Unser Ziel wird es nun sein zu zeigen, dass Random Projections die Klassifikation verbessern können. Um ein Beispiel zu schreiben, beginnen wir mit allen notwendigen Imports:

import tensorflow_datasets as tfds
import tensorflow as tf
import numpy as np

import math

from sklearn.random_projection import GaussianRandomProjection

from tensorflow.python.keras.models import Sequential
from tensorflow.python.keras.layers import InputLayer, Dense
from tensorflow.python.keras.optimizer_v2.adam import Adam
from tensorflow.python.keras.losses import sparse_categorical_crossentropy

Hinweis: Dieses Skript läuft auf Tensorflow mit der Version 2.12.0.

Anschließend laden wir den Datensatz aus dem Tensorflow-Datensatz und verarbeiten ihn, so dass wir alle Bilder und alle Labels haben:

hist_data = tfds.load("colorectal_histology")

df_train = tfds.as_dataframe(hist_data["train"])
images = df_train["image"].values

temp = []
for element in images:
    element = np.reshape(element, [-1])
    temp.append(element)

images = np.array(temp)

labels = df_train["label"].values

Um interessante Ergebnisse zu erhalten, wird im nächsten Schritt ein Train-Test-Split mit einem Verhältnis von $80\%:20\%$ erstellt.

train, test = 0.8, 0.2
amount_train = math.ceil(images.shape[0] * train)
amount_test = math.floor(images.shape[0] * test)

# Randomly Sample Elements from the images Array
indices_train = np.random.choice(images.shape[0], amount_train, replace=False)
indices_train = np.sort(indices_train)

indices_test = []
for i in range(images.shape[0]):
    if ((i in indices_train) == False):
      indices_test.append(i)

indices_test = np.array(indices_test)

# Generate all necessary Variables to store Training Information
train_x, train_y, test_x, test_y = [], [], [], []

train_x = images[indices_train]
train_y = labels[indices_train]

train_x, train_y = tf.convert_to_tensor(train_x), tf.convert_to_tensor(train_y)

test_x = images[indices_test]
test_y = labels[indices_test]

test_x, test_y = tf.convert_to_tensor(test_x), tf.convert_to_tensor(test_y)

Wichtig: der Tag replace=False innerhalb von np.random.choice(...) verhindert die Doppelung von Indizes. Ohne diesen Zusatz erhalten wir keinen korrekten Train-Test-Split.

Der nächste Schritt besteht darin, ein Modell zu erstellen, das alle Eingabedaten verwendet, um eine Klassifizierung auf der Grundlage des Datensatzes durchzuführen. Dabei handelt es sich nicht um ein speziell optimiertes Modell, sondern um ein einfaches neuronales Netz zur Veranschaulichung des Prozesses. In der Realität wäre dies ein für die Aufgabe optimiertes Modell.

model = Sequential([
    InputLayer(input_shape=(67500,)),
    Dense(units=128, activation="relu"),
    Dense(units=128, activation="relu"),
    Dense(units=64, activation="relu"),
    Dense(units=8, activation="softmax")
])

optimizer = Adam(learning_rate=10e-4)
model.compile(optimizer=optimizer, 
              loss=sparse_categorical_crossentropy, 
              metrics=["accuracy"])
model.summary()

Dann trainieren wir dieses Modell. Die Auswertung des Modells kann automatisch erfolgen.

history = model.fit(x=train_x, y=train_y, 
                    epochs=20, batch_size=64, 
                    validation_data=(test_x, test_y))

Aus dieser Grafik können wir erkennen, dass unser Training leider nicht sehr stabil ist. Dafür kann es es mehrere Gründe geben:

• Fehlerhafte Einstellung der Trainingsepochen,
• Fehlerhafte Einstellung der Batch Size,
• Fehlerhafte Architektur des neuronalen Netzes,
• Ein zu kleiner Datensatz oder
• Zu hohe Eingangsdimensionen des Datensatzes.

Letztendlich kann dies leider auf viele Faktoren zurückzuführen sein. Wir können jedoch die Eingangsdimensionen des Datensatzes sehr gut beeinflussen. Dazu verwenden wir nun die bereits besprochenen Random Projections.

proj_gauss = GaussianRandomProjection(random_state=0)
reduced_images = proj_gauss.fit_transform(images)

Eine genauere Betrachtung der Daten des reduzierten Datensatzes zeigt, dass die Anzahl der Merkmale von insgesamt $67500$ auf $7300$ Merkmale reduziert werden konnte. Dies entspricht einer Reduktion von $\approx 11\%$ der Daten. Um den Effekt der Dimensionalitätsreduktion zu demonstrieren, verwenden wir ein Neuronales Netz mit identischen Merkmalen und trainieren es vollständig auf dem reduzierten Datensatz:

reduced_train_x = reduced_images[indices_train]
reduced_test_x = reduced_images[indices_test]

model = Sequential([
    InputLayer(input_shape=(7300,)),
    Dense(units=128, activation="relu"),
    Dense(units=128, activation="relu"),
    Dense(units=64, activation="relu"),
    Dense(units=8, activation="softmax")
])

optimizer = Adam(learning_rate=10e-4)
model.compile(optimizer=optimizer, loss=sparse_categorical_crossentropy, metrics=["accuracy"])
model.summary()

history = model.fit(x=reduced_train_x, y=train_y, 
                    epochs=20, batch_size=64, 
                    validation_data=(reduced_test_x, test_y))

Die Trainingsgenauigkeit und Testgenauigkeit haben wir zur Veranschaulichung einmal visualisert:

Anschließend können wir alle hier produzierten Ergebnisse miteinander vergleichen.

Alle Berechnungen wurden mittels der Hardware von Google Colab durchgeführt. Experimente können dort wiederholt werden, obwohl beispielsweise die Ausführungszeit aufgrund der Verfügbarkeit von Hardware bei Google Colab schwanken kann.

Der Parameter Ausführungszeit spezifiziert uns, wieviel Zeit die Dimensionality Reduction unter Verwendung der Random Projections in Anspruch genommen hat.

Alles in allem zeigt sich, dass eine Dimensionality Reduction im Rahmen des Preprocessings sehr gut dabei helfen kann, die Genauigkeit eines Modells zu verbessern. Dies ist grundsätzlich nicht auf neuronale Netze beschränkt, sondern kann auch bei anderen “Machine Learning”-Techniken hilfreich sein. Ebenso wichtig ist die Reduzierung der Trainingszeit, welches Kosten spart.

Die Verbesserung des Trainings- und Testverhaltes beim Training mit dem reduzierten Datensatz kann auf den Fluch der Dimensionalität zurückgeführt werden.

Vor- und Nachteile von Random Projections

Random Projections haben eine Reihe von Vor- und Nachteilen aufgrund der stochastischen Natur des Algorithmus. Als Gegenpart für Vergleiche zu diesem Algorithmus wird häufig vor allem Principal Component Analysis (PCA) genannt.

Vorteile

Das Verfahren zeichnet sich durch eine Reihe positiver Eigenschaften aus: ^{1 7 9}

1. Random Projections sind unheimlich schnell. Die Zeitkomplexität von Random Projections liegt bei $O(Nnm)$, was bedeutend geringer ist als bei der Principal Component Analysis.

2. Random Projections sind nicht so stark durch Ausreißer beeinflusst. Dies ist vermutlich ein Resultat der stochastischen Natur des Verfahrens.

Nachteile

Im Vergleich mit der Principal Component Analysis weisen die Random Projections eine Reihe von Nachteilen auf: ^{9 10}

1. Random Projections sind nicht so effizient wie dies die Principal Component Analysis ist. In der Theorie ist diese das optimale Verfahren zur Reduzierung der Dimension eines Datensatzes.

Anwendungsgebiete

Random Projections werden bereits in einigen Bereichen von Big Data verwendet. Hier sind einige Beispiele: ^{9 11}

1. Sprach- und Stimmverarbeitung: In diesem Bereich kann es durch Tonaufnahmen zur Verrauschung der Eingangsdaten kommen. Die Projektion der Daten auf einen zufälligen niedrigerdimensionalen Unterraum liefert Ergebnisse, die mit herkömmlichen Dimensionsreduktionsmethoden wie der Principal Component Analysis vergleichbar sind.

2. Bild- und Videoverarbeitung: Bei sowohl der Bild- als auch Videobearbeitung sind wir bei sehr großen Datenmengen, bei welcher die Effizienz von Random Projections vorteilhaft sind.

3. Bioinformatik: Bioinformatik: Genexpressionsprofile können als Matrizen mit mehr als zehntausend kontinuierlichen Werten betrachtet werden. Hohe Dimensionalität führt zu belastenden Berechnungen und Problemen mit dem Fluch der Dimensionalität. Daher werden Dimensionsreduktionstechniken oft in maschinellen Lernaufgaben angewendet, um diese Probleme zu mildern.

Quellen