Improving TensorSketch Using Complex Random Variables

Stellen Sie sich vor, Sie versuchen, ein riesiges Jigsaw-Puzzle zu lösen, aber anstelle von Puzzleteilen haben Sie Millionen von Zahlen, die Datenpunkte repräsentieren. In der Welt des maschinellen Lernens müssen Computer oft Muster finden, indem sie diese Zahlen vergleichen. Manchmal sind die Muster einfach, wie eine gerade Linie. Aber oft ist die Welt unordentlich und gekrümmt, daher verwenden Computer „Kernel“ – mathematische Zaubertricks, die es ihnen ermöglichen, komplexe, gekrümmte Beziehungen zwischen Datenpunkten zu erkennen. Einer dieser populären Tricks ist der „Polynomial-Kernel“, der betrachtet, wie diese Merkmale interagieren, wenn man sie viele Male miteinander multipliziert.

Das Problem ist, dass die Anzahl der Puzzlestücke explodiert, wenn man diese Merkmale immer öfter miteinander multipliziert (sie also zu einem höheren „Grad“ potenziert). Das Wachstum ist so schnell, dass selbst die schnellsten Supercomputer stecken bleiben würden, wenn sie versuchen würden, jedes einzelne Teil zu berechnen. Um dies zu beheben, erfanden Wissenschaftler das „Sketching“. Stellen Sie sich Sketching wie das Erstellen einer Skizze vor, bei der man ein hochauflösendes Foto in ein winziges Vorschaubild komprimiert. Man verliert zwar etwas Detail, behält aber die wichtigsten Formen und Farben bei und kann das Vorschaubild sofort verarbeiten. Jahrelang war die beste Methode für diese Polynomial-Puzzles eine Methode namens TensorSketch. Sie war schnell, hatte aber einen Makel: Je komplexer das Puzzle wurde, desto „verschwommener“ wurde das Vorschaubild, und die Schätzung des Computers begann stärker zu schwanken, was zu mehr Fehlern führte.

Kürzlich stellte ein Team von Forschern eine neugierige Frage: Was wäre, wenn wir nicht nur gewöhnliche Zahlen verwenden würden, sondern „komplexe“ Zahlen – Zahlen, die einen imaginären Teil enthalten, wie die Quadratwurzel aus minus eins? Sie fragten sich, ob dieser imaginäre Twist das Vorschaubild schärfer machen könnte. Eine vorangegangene Studie hatte gezeigt, dass die Verwendung komplexer Zahlen bei einer bestimmten Art des Sketchings das Bild tatsächlich klarer machte (die Verschwommenheit reduzierte). Diese Methode war jedoch langsam und schwerfällig, als würde man versuchen, mit einem schweren Rucksack zu rennen. Die Forscher in dieser Arbeit wollten wissen: Können wir diese super-scharfe Klarheit komplexer Zahlen erreichen, ohne den schweren Rucksack? Können wir die schnelle, leichte TensorSketch-Methode genauso gut machen wie die langsame, schwere?

Die Arbeit mit dem Titel „Improving TensorSketch Using Complex Random Variables“ sagt: Ja. Die Autoren, Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap und Keegan Kang, haben eine neue Version von TensorSketch entwickelt, die diese komplexen Zahlen verwendet, aber die Geschwindigkeit des Originals beibehält. Sie haben nicht nur geraten, sondern es mit Mathematik bewiesen und mit realen Daten getestet.

So haben sie es gemacht. Das ursprüngliche TensorSketch funktioniert dadurch, dass es Ihre Daten nimmt, sie mit zufälligen Vorzeichen vermischt (wie ein Münzwurf, um zu entscheiden, ob eine Zahl positiv oder negativ ist) und sie dann zusammendrückt. Die neue Methode, die sie „Complex-to-Real TensorSketch“ (oder CtR TensorSketch) nennen, verändert den Münzwurf. Anstatt nur Kopf oder Zahl (1 oder -1) zu verwenden, nutzt sie einen vierseitigen Würfel, der auf 1, -1 oder zwei imaginäre Zahlen (i und -i) landet. Das mag so klingen, als würde das Ergebnis ein seltsames, imaginäres Chaos werden, aber sie haben einen cleveren Trick. Sie nehmen das Ergebnis, das eine komplexe Zahl ist, und teilen es in zwei Teile auf: den „reellen“ Teil und den „imaginären“ Teil. Dann fügen sie diese beiden Teile nebeneinander ein, um einen neuen, reellen Vektor zu bilden.

Die Magie geschieht durch die Art und Weise, wie diese imaginären Zahlen interagieren. Als die Forscher die Zahlen berechneten, fanden sie heraus, dass die „Verschwommenheit“ (oder Varianz) ihrer neuen Methode viel langsamer wächst als die der alten Methode. In der alten Methode wuchs der Fehler wie $3^p$ (wobei $p$ die Komplexität des Puzzles ist). In ihrer neuen Methode wächst der Fehler nur wie $2^p$. Das mag nach einem kleinen Unterschied klingen, aber in der Welt des exponentiellen Wachstums ist das eine massive Verbesserung. Es bedeutet, dass ihr neuer Sketch für komplexe Puzzles signifikant genauer ist.

Entscheidend ist, dass sie bewiesen haben, dass diese neue Methode immer noch genauso schnell ist wie die alte. Während andere Methoden, die komplexe Zahlen verwenden, vom Computer aufwendige, langsame Berechnungen erfordern (mit einer Zeit, die proportional zur vollen Größe der Daten ist), bleibt ihre Methode „input-sparse“. Das bedeutet, sie verbringt Zeit nur mit den Teilen der Daten, die tatsächlich existieren, und ignoriert die Nullen. Sie zeigten, dass die Zeit, die es dauert, ihren Algorithmus auszuführen, $O(p(nnz(x) + D \log D))$ beträgt, was dieselbe Geschwindigkeit wie das ursprüngliche TensorSketch ist.

Um sicherzustellen, dass dies nicht nur ein mathematischer Trick war, der auf dem Papier funktionierte, führten sie Experimente durch. Sie testeten ihre Methode an synthetischen Daten (künstlich erzeugten Zahlen) und realen Datensätzen wie den MAGIC Gamma Telescope Daten und COD-RNA. Sie verglichen ihren CtR TensorSketch mit dem Standard-TensorSketch und anderen komplexen Methoden. Die Ergebnisse waren eindeutig: Ihre neue Methode lieferte viel genauere Approximationen (gemessen an etwas namens KL-Divergenz, das prüft, wie ähnlich der Sketch dem Original ist), während sie die gleiche Zeit für die Berechnung benötigte. In einigen Tests war ihre Methode sogar schneller als die anderen komplexen Methoden, weil sie nicht die schwere Arbeit leisten musste.

Die Arbeit geht auch auf eine potenzielle Verwirrung ein. Sie zeigten, dass die bloße Verwendung komplexer Zahlen in einer anderen Art von Sketch (genannt CountSketch) nicht automatisch eine Verbesserung bewirkt. Die Verbesserung ergibt sich erst aus der spezifischen Art und Weise, wie sie die komplexen Zahlen mit der TensorSketch-Struktur kombiniert haben. Dies beweist, dass ihr Ergebnis kein Zufall ist; es ist eine spezifische, nicht-triviale Verbesserung, die daraus resultiert, wie die Mathematik bestimmte Fehlerterme ausgleicht.

Kurz gesagt: Diese Arbeit nimmt ein schnelles, aber leicht verschwommenes Werkzeug (TensorSketch), verbessert es mit ein wenig imaginärer Mathematik, um es schärfer zu machen, und stellt sicher, dass es schnell bleibt. Es ist, als würde man einem schnellen Skizzierkünstler ein spezielles Set farbiger Bleistifte geben, mit denen er mehr Details erfassen kann, ohne dabei langsamer zu werden. Für jeden, der Machine-Learning-Modelle baut, die komplexe Beziehungen in riesigen Datensätzen verstehen müssen, bietet diese neue Methode einen Weg, bessere Antworten zu erhalten, ohne länger darauf warten zu müssen, dass der Computer seine Arbeit beendet.