Einbettungen in maschinelles Lernen: Komplexe Daten einfach machen

Die Arbeit mit nicht numerischen Daten kann selbst für erfahrene Data Scientists schwierig sein. Ein typisches maschinelles Lernmodell erwartet, dass seine Merkmale Zahlen sind, nicht Wörter, E-Mails, Webseiten, Listen, Diagramme oder Wahrscheinlichkeitsverteilungen. Um nützlich zu sein, müssen Daten zuerst in einen Vektorraum transformiert werden. Aber wie?

Ein beliebter Ansatz wäre, ein nicht-numerisches Merkmal als kategorisch zu behandeln . Dies könnte gut funktionieren, wenn die Anzahl der Kategorien gering ist (z. B. wenn die Daten einen Beruf oder ein Land angeben). Wenn wir jedoch versuchen, diese Methode auf E-Mails anzuwenden, werden wir wahrscheinlich so viele Kategorien erhalten, wie es Beispiele gibt. Keine zwei E-Mails sind genau gleich, daher wäre dieser Ansatz nutzlos.

Ein anderer Ansatz wäre , einen Abstand zwischen Datenproben zu definieren , eine Funktion, die uns sagt, wie nahe zwei beliebige Proben sind. Oder wir könnten ein Ähnlichkeitsmaß definieren, das uns dieselben Informationen liefern würde, außer dass der Abstand zwischen zwei nahen Stichproben klein ist, während die Ähnlichkeit groß ist. Die Berechnung des Abstands (Ähnlichkeit) zwischen allen Datenstichproben würde uns eine Abstands- (oder Ähnlichkeits-)Matrix liefern. Dies sind numerische Daten, die wir verwenden könnten.

Diese Daten hätten jedoch so viele Dimensionen, wie es Proben gibt, was normalerweise nicht großartig ist, wenn wir sie als Merkmal verwenden (siehe Fluch der Dimensionalität) oder visualisieren möchten (während ein Diagramm sogar 6D verarbeiten kann, habe ich es noch um einen 100D-Plot zu sehen). Könnten wir die Anzahl der Dimensionen auf ein vernünftiges Maß reduzieren?

Die Antwort ist ja! Dafür haben wir Embeddings .

Was ist eine Einbettung und warum sollte man sie verwenden?

Eine Einbettung ist eine niedrigdimensionale Darstellung von hochdimensionalen Daten. Typischerweise erfasst eine Einbettung nicht alle Informationen, die in den Originaldaten enthalten sind. Eine gute Einbettung wird jedoch genug erfassen, um das vorliegende Problem zu lösen.

Es gibt viele Einbettungen, die auf eine bestimmte Datenstruktur zugeschnitten sind. Beispielsweise haben Sie vielleicht schon von word2vec für Textdaten oder Fourier-Deskriptoren für Formbilddaten gehört. Stattdessen werden wir erörtern, wie Einbettungen auf Daten angewendet werden, bei denen wir ein Distanz- oder Ähnlichkeitsmaß definieren können. Solange wir eine Entfernungsmatrix berechnen können, ist die Art der Daten völlig irrelevant. Es funktioniert genauso, seien es E-Mails, Listen, Bäume oder Webseiten.

In diesem Artikel stellen wir Ihnen verschiedene Arten der Einbettung vor und erörtern, wie einige beliebte Einbettungen funktionieren und wie wir Einbettungen verwenden könnten, um reale Probleme mit komplexen Daten zu lösen. Wir werden auch die Vor- und Nachteile dieser Methode sowie einige Alternativen durchgehen. Ja, manche Probleme lassen sich mit anderen Mitteln besser lösen, aber leider gibt es beim maschinellen Lernen keinen Königsweg.

Lass uns anfangen.

Wie Einbettungen funktionieren

Alle Einbettungen versuchen, die Dimensionalität von Daten zu reduzieren und gleichzeitig „wesentliche“ Informationen in den Daten zu erhalten, aber jede Einbettung tut dies auf ihre eigene Weise. Hier werden wir einige beliebte Einbettungen durchgehen, die auf eine Distanz- oder Ähnlichkeitsmatrix angewendet werden können.

Wir werden nicht einmal versuchen, alle Einbettungen da draußen abzudecken. Es gibt mindestens ein Dutzend bekannte Einbettungen, die das können, und viele weitere weniger bekannte Einbettungen und ihre Variationen. Jeder von ihnen hat seinen eigenen Ansatz, Vor- und Nachteile.

Wenn Sie sehen möchten, welche anderen Einbettungen es gibt, können Sie hier beginnen:

• Scikit-learn-Benutzerhandbuch
• Die Elemente des statistischen Lernens (2. Auflage), Kapitel 14

Entfernungsmatrix

Lassen Sie uns kurz auf Distanzmatrizen eingehen. Das Finden einer angemessenen Entfernung für Daten erfordert ein gutes Verständnis des Problems, einige mathematische Kenntnisse und manchmal auch pures Glück . In dem in diesem Artikel beschriebenen Ansatz könnte dies der wichtigste Faktor sein, der zum Gesamterfolg oder Misserfolg Ihres Projekts beiträgt.

Auch ein paar technische Details sollten Sie beachten. Viele Einbettungsalgorithmen gehen davon aus, dass eine Abstands- (oder Unähnlichkeits- ) Matrix $\textbf{D}$ Nullen auf ihrer Diagonale hat und symmetrisch ist. Wenn es nicht symmetrisch ist, können wir stattdessen $(\textbf{D} + \textbf{D}^T) / 2$ verwenden. Algorithmen, die den Kernel-Trick verwenden, gehen auch davon aus, dass ein Abstand eine Metrik ist, was bedeutet, dass die Dreiecksungleichung gilt:

\[\für alle a, b, c \;\; d(a,c) \leq d(a,b) + d(b,c)\]

Wenn ein Algorithmus stattdessen eine Ähnlichkeitsmatrix erfordert, könnten wir auch jede monoton abnehmende Funktion anwenden, um eine Distanzmatrix in eine Ähnlichkeitsmatrix umzuwandeln: zum Beispiel $\exp -x$.

Hauptkomponentenanalyse (PCA)

Die Hauptkomponentenanalyse oder PCA ist wahrscheinlich die bisher am häufigsten verwendete Einbettung. Die Idee ist einfach: Finden Sie eine lineare Transformation von Merkmalen, die die erfasste Varianz maximiert oder (äquivalent) den quadratischen Rekonstruktionsfehler minimiert .

Seien insbesondere Merkmale eine Stichprobenmatrix $\textbf{X} \in \mathbb{R}^{n \times p}$ mit $n$ Merkmalen und $p$ Dimensionen. Nehmen wir der Einfachheit halber an, dass der Datenstichprobenmittelwert null ist. Wir können die Anzahl der Dimensionen von $p$ auf $q$ reduzieren, indem wir $\textbf{X}$ mit einer orthonormalen Matrix $\textbf{V}_q \in \mathbb{R}^{p \times q}$ multiplizieren :

\[\hat{\textbf{X}} = \textbf{X} \textbf{V}_q\]

Dann wird $\hat{\textbf{X}} \in \mathbb{R}^{n \times q}$ der neue Satz von Merkmalen sein. Um die neuen Merkmale wieder dem ursprünglichen Raum zuzuordnen (diese Operation wird als Rekonstruktion bezeichnet), müssen wir sie einfach erneut mit $\textbf{V}_q^T$ multiplizieren.

Nun soll die Matrix $\textbf{V}_q$ gefunden werden, die den Rekonstruktionsfehler minimiert:

\[\min_{\textbf{V}_q} ||\textbf{X}\textbf{V}_q\textbf{V}_q^T - \textbf{X}||^2\]

Spalten der Matrix $\textbf{V}_q$ heißen Hauptkomponentenrichtungen und Spalten von $\hat{\textbf{X}}$ heißen Hauptkomponenten. Numerisch können wir $\textbf{V}_q$ finden, indem wir die SVD-Zerlegung auf $\textbf{X}$ anwenden, obwohl es andere ebenso gültige Möglichkeiten gibt, dies zu tun.

PCA kann direkt auf numerische Features angewendet werden. Oder, wenn unsere Merkmale nicht numerisch sind, können wir sie auf eine Abstands- oder Ähnlichkeitsmatrix anwenden.

Wenn Sie Python verwenden, ist PCA in scikit-learn implementiert.

Der Vorteil dieser Methode besteht darin, dass sie schnell zu berechnen und ziemlich robust gegenüber Rauschen in Daten ist.

Der Nachteil wäre, dass es nur lineare Strukturen erfassen kann, sodass nichtlineare Informationen, die in den Originaldaten enthalten sind, wahrscheinlich verloren gehen.

Kernel-PCA

Kernel PCA ist eine nichtlineare Version von PCA. Die Idee ist, Kernel Trick zu verwenden, von dem Sie wahrscheinlich schon gehört haben, wenn Sie mit Support Vector Machines SVM vertraut sind.

Insbesondere gibt es einige verschiedene Möglichkeiten, PCA zu berechnen. Eine davon ist die Berechnung der Eigenzerlegung der doppelt zentrierten Version der Grammmatrix $\textbf{X}\textbf{X}^T\in\mathbb{R}^{n\times n}$. Wenn wir nun eine Kernel-Matrix $\textbf{K} \in \mathbb{R}^{n \times n}$ für unsere Daten berechnen, wird Kernel PCA sie als Gramm-Matrix behandeln, um Hauptkomponenten zu finden.

Seien $x_i$, $i \in {1,..,n}$ die Feature-Samples. Die Kernel-Matrix wird durch eine Kernel-Funktion $K(x_i,x_j)=\langle \phi(x_i),\phi(x_j) \rangle$ definiert.

Eine beliebte Wahl ist ein radialer Kernel:

\[K(x_i,x_j)=\exp -\gamma \cdot d(x_i,x_j)\]

wobei $d$ eine Abstandsfunktion ist.

Kernel PCA forderte uns auf, eine Entfernung anzugeben. Für numerische Merkmale könnten wir beispielsweise die euklidische Distanz verwenden: $d(x_i,x_j)=\vert\vert x_i-x_j \vert \vert ^2$.

Bei nicht numerischen Merkmalen müssen wir möglicherweise kreativ werden. Eine Sache, die Sie sich merken sollten, ist, dass dieser Algorithmus davon ausgeht, dass unsere Entfernung eine Metrik ist.

Wenn Sie Python verwenden, ist Kernel PCA in scikit-learn implementiert.

Der Vorteil des Kernel-PCA-Verfahrens besteht darin, dass es nichtlineare Datenstrukturen erfassen kann.

Der Nachteil besteht darin, dass es empfindlich auf Datenrauschen reagiert und dass die Wahl der Entfernungs- und Kernelfunktionen die Ergebnisse stark beeinflusst.

Mehrdimensionale Skalierung (MDS)

Multidimensional Scaling (MDS) versucht, Abstände zwischen Samples global beizubehalten. Die Idee ist ziemlich intuitiv und funktioniert gut mit Distanzmatrizen.

Insbesondere berechnen wir bei gegebenen Merkmalsproben $x_i$, $i \in {1,..,n}$ und einer Abstandsfunktion $d$ neue Merkmalsproben $z_i \in \mathbb{R}^{q}$, $i \in {1,..,n}$ durch Minimierung einer Stressfunktion :

\[\min_{z_1,..,z_n} \sum_{1 \leq i < j \leq n} (d(x_i, x_j) - ||z_i - z_j||)^2\]

Wenn Sie Python verwenden, ist MDS in scikit-learn implementiert. scikit-learn unterstützt jedoch keine Transformation von Out-of-Sample-Punkten, was unpraktisch sein könnte, wenn wir eine Einbettung in Verbindung mit einem Regressions- oder Klassifizierungsmodell verwenden möchten. Grundsätzlich ist es aber möglich.

Der Vorteil von MDS ist, dass seine Idee perfekt mit unserem Framework übereinstimmt und dass es nicht stark von Datenrauschen beeinflusst wird.

Der Nachteil ist, dass die Implementierung in scikit-learn ziemlich langsam ist und keine Out-of-Sample-Transformation unterstützt.

Anwendungsfall: Sendungsverfolgung

Einige Siedlungen auf einer kleinen tropischen Insel haben Paketversanddienste entwickelt, um die lokale Tourismusbranche zu bedienen. Ein Händler in einer dieser Siedlungen beschloss, Maßnahmen zu ergreifen, um sich einen Vorteil gegenüber der Konkurrenz zu verschaffen, und richtete daher ein Satellitenüberwachungssystem ein, das alle Paketsendungen auf der Insel verfolgt. Nachdem die Daten gesammelt waren, rief der Händler einen Datenwissenschaftler (das sind wir!) an, um ihm bei der Beantwortung der folgenden Frage zu helfen: Können wir das Ziel eines Pakets vorhersagen, das gerade unterwegs ist?

Der Datensatz enthält Informationen zu 200 verfolgten Sendungen. Für jede verfolgte Sendung gibt es eine Liste mit (x,y)-Koordinaten aller Orte, an denen das Paket gesichtet wurde, was typischerweise zwischen 20 und 50 Beobachtungen liegt. Das Diagramm unten zeigt, wie diese Daten aussehen.

Diese Daten sehen nach Ärger aus – eigentlich zwei verschiedene Arten von Ärger.

Das erste Problem ist, dass die Daten, mit denen wir es zu tun haben, hochdimensional sind. Wenn beispielsweise jedes Paket an 50 Standorten gesichtet wurde, hätten unsere Daten 100 Dimensionen – das klingt viel, verglichen mit den 200 Mustern, die Ihnen zur Verfügung stehen.

Das zweite Problem: Verschiedene Transportrouten haben tatsächlich eine unterschiedliche Anzahl von Beobachtungen, daher können wir die Listen nicht einfach mit Koordinaten stapeln, um die Daten in tabellarischer Form darzustellen (und selbst wenn, wäre das immer noch nicht wirklich sinnvoll).

Der Kaufmann trommelt ungeduldig mit den Fingern auf den Tisch und der Data Scientist gibt sich alle Mühe, keine Panik zu zeigen.

Hier sind Abstandsmatrizen und Einbettungen hilfreich. Wir müssen nur einen Weg finden, zwei Versandrouten zu vergleichen. Die Frechet-Distanz scheint eine vernünftige Wahl zu sein. Mit einer Entfernung können wir eine Entfernungsmatrix berechnen.

Hinweis: Dieser Schritt kann eine Weile dauern. Wir müssen $O(n^2)$ Distanzen berechnen, wobei jede Distanz $O(k^2)$ Iterationen hat, wobei $n$ die Anzahl der Stichproben und $k$ die Anzahl der Beobachtungen in einer Stichprobe ist. Das effiziente Schreiben einer Abstandsfunktion ist der Schlüssel. Beispielsweise könnten Sie in Python numba verwenden, um diese Berechnung um ein Vielfaches zu beschleunigen.

Einbettungen visualisieren

Jetzt können wir mit einer Einbettung die Anzahl der Dimensionen von 200 auf wenige reduzieren. Wir können deutlich erkennen, dass es nur wenige Handelsrouten gibt, sodass wir hoffen können, eine gute Darstellung der Daten sogar in zwei oder drei Dimensionen zu finden. Wir werden Einbettungen verwenden, die wir bereits besprochen haben: PCA, Kernel PCA und MDS.

Auf den folgenden Diagrammen sehen Sie die beschrifteten Streckendaten (zur Demonstration angegeben) und ihre Darstellung durch eine Einbettung in 2D und 3D (von links nach rechts). Die beschrifteten Daten markieren vier Handelsposten, die durch sechs Handelsrouten verbunden sind. Zwei der sechs Handelsrouten sind bidirektional, was insgesamt acht Sendungsgruppen (6+2) ergibt. Wie Sie sehen können, haben wir mit 3D-Einbettungen eine ziemlich klare Trennung aller acht Sendungsgruppen erreicht.

Das ist ein guter Anfang.

Einbettungen in eine Modellpipeline

Jetzt sind wir bereit, eine Einbettung zu trainieren. Obwohl MDS die besten Ergebnisse zeigte, ist es ziemlich langsam; außerdem unterstützt die Implementierung von scikit-learn keine Out-of-Sample-Transformation. Für die Forschung ist das kein Problem, aber für die Produktion kann es ein Problem sein, also werden wir stattdessen Kernel PCA verwenden. Für Kernel PCA sollten wir nicht vergessen, vorher einen radialen Kernel auf die Distanzmatrix anzuwenden.

Wie wählen Sie die Anzahl der Ausgabedimensionen aus? Die Analyse ergab, dass sogar 3D gut funktioniert. Um auf der sicheren Seite zu sein und keine wichtigen Informationen auszulassen, stellen wir die Embedding-Ausgabe auf 10D. Für die beste Leistung kann die Anzahl der Ausgabedimensionen als Modell-Hyperparameter festgelegt und dann durch Kreuzvalidierung optimiert werden.

Wir haben also 10 numerische Merkmale, die wir als Eingabe für so ziemlich jedes Klassifizierungsmodell verwenden können. Wie wäre es mit einem linearen und einem nichtlinearen Modell: sagen wir, Logistische Regression und Gradient Boosting? Lassen Sie uns zum Vergleich auch diese beiden Modelle mit einer vollständigen Entfernungsmatrix als Eingabe verwenden. Darüber hinaus testen wir auch SVM (SVM ist so konzipiert, dass es direkt mit einer Distanzmatrix arbeitet, sodass keine Einbettung erforderlich wäre).

Die Modellgenauigkeit des Testsets ist unten dargestellt (es wurden 10 Zug- und Testdatensätze generiert, damit wir die Varianz des Modells abschätzen konnten):

• Gradient Boosting gepaart mit einer Einbettung (KernelPCA+GB) belegt den ersten Platz. Es übertraf Gradient Boosting ohne Einbettung (GB). Hier hat sich Kernel PCA bewährt.
• Die logistische Regression war in Ordnung. Interessant ist, dass die logistische Regression ohne Einbettung (LR) besser abschneidet als mit Einbettung (KernelPCA+LR). Dies ist nicht ganz unerwartet. Lineare Modelle sind nicht sehr flexibel, aber relativ schwer zu überpassen. Hier scheint der durch eine Einbettung verursachte Informationsverlust den Vorteil einer kleineren Eingabedimensionalität zu überwiegen.
• Last but not least schneidet auch SVM gut ab, obwohl die Varianz dieses Modells ziemlich groß ist.

Modellgenauigkeit

Der Python-Code für diesen Anwendungsfall ist auf GitHub verfügbar.

Fazit

Wir haben erklärt, was Einbettungen sind, und gezeigt, wie sie in Verbindung mit Distanzmatrizen verwendet werden können, um reale Probleme zu lösen. Zeit für das Urteil:

Sind Einbettungen etwas, das ein Datenwissenschaftler verwenden sollte? Werfen wir einen Blick auf beide Seiten der Geschichte.

Vor- und Nachteile der Verwendung von Einbettungen

Vorteile:

• Dieser Ansatz ermöglicht es uns, mit ungewöhnlichen oder komplexen Datenstrukturen zu arbeiten, solange Sie eine Distanz definieren können, die Sie mit einem gewissen Maß an Wissen, Vorstellungskraft und Glück normalerweise können.
  
• Die Ausgabe sind niedrigdimensionale numerische Daten, die Sie einfach analysieren, gruppieren oder als Modellmerkmale für so ziemlich jedes verfügbare Modell für maschinelles Lernen verwenden können.

Nachteile:

• Bei diesem Ansatz gehen zwangsläufig einige Informationen verloren:

  • Im ersten Schritt, wenn wir die Originaldaten durch die Ähnlichkeitsmatrix ersetzen
  • Im zweiten Schritt, wenn wir die Dimensionalität durch eine Einbettung reduzieren
• Je nach Daten und Abstandsfunktion kann die Berechnung einer Abstandsmatrix zeitaufwändig sein. Dies kann durch eine effizient geschriebene Abstandsfunktion gemildert werden.
• Einige Einbettungen sind sehr empfindlich gegenüber Rauschen in Daten. Dies kann durch zusätzliche Datenbereinigung gemildert werden.
• Einige Einbettungen reagieren empfindlich auf die Wahl ihrer Hyperparameter. Dies kann durch sorgfältige Analyse oder Hyperparameter-Tuning gemildert werden.

Alternativen: Warum nicht verwenden …?

• Warum nicht einfach eine Einbettung direkt auf Daten statt einer Distanzmatrix verwenden?
  Wenn Sie eine Einbettung kennen, die Ihre Daten effizient direkt kodieren kann, verwenden Sie sie auf jeden Fall. Das Problem ist, dass es nicht immer existiert.
  
• Warum nicht einfach die Clusterisierung auf einer Distanzmatrix verwenden?
  Wenn Ihr einziges Ziel darin besteht, Ihren Datensatz zu segmentieren, wäre dies völlig in Ordnung. Einige Clusterisierungsmethoden nutzen auch Einbettungen (z. B. Spectral Clustering). Wenn Sie mehr erfahren möchten, finden Sie hier ein Tutorial zur Clusterisierung.
  
• Warum nicht einfach eine Abstandsmatrix als Merkmale verwenden?
  Die Größe einer Abstandsmatrix ist $(n_{samples}, n_{samples})$. Nicht alle Modelle können damit effizient umgehen – einige passen möglicherweise über, einige passen sich langsam an, einige passen möglicherweise überhaupt nicht. Hier bieten sich Modelle mit geringer Varianz an, etwa lineare und/oder regularisierte Modelle.
  
• Warum nicht einfach SVM mit einer Distanzmatrix verwenden?
  SVM ist ein großartiges Modell, das in unserem Anwendungsfall gut funktioniert hat. Es gibt jedoch einige Vorbehalte. Erstens, wenn wir andere Funktionen hinzufügen möchten (könnten nur einfache numerische Zahlen sein), können wir dies nicht direkt tun. Wir müssten sie in unsere Ähnlichkeitsmatrix aufnehmen und könnten möglicherweise einige wertvolle Informationen verlieren. Zweitens, so gut SVM auch ist, ein anderes Modell funktioniert möglicherweise besser für Ihr spezielles Problem.
  
• Warum nicht einfach Deep Learning nutzen?
  Es stimmt, dass man für jedes Problem ein passendes neuronales Netz finden kann, wenn man lange genug sucht. Denken Sie jedoch daran, dass der Prozess des Findens, Trainierens, Validierens und Bereitstellens dieses neuronalen Netzwerks nicht unbedingt einfach sein wird. Verwenden Sie also wie immer Ihr bestes Urteilsvermögen.

In einem Satz

Einbettungen in Verbindung mit Distanzmatrizen sind ein unglaublich nützliches Werkzeug, wenn Sie zufällig mit komplexen nicht-numerischen Daten arbeiten, insbesondere wenn Sie Ihre Daten nicht direkt in einen Vektorraum umwandeln können und eine niedrigdimensionale Eingabe für Ihr Modell bevorzugen.