Johnson-Lindenstrauss-Transformation
Die Johnson-Lindenstrauss-Transformation ist ein mathematisches Verfahren, das lange Zahlenlisten auf wenige Zahlen verkürzt, ohne die Abstände zwischen ihnen wesentlich zu verfälschen. Sie macht Suchsysteme und KI-Anwendungen schneller und speichersparender, weil sie mit deutlich weniger Daten fast gleich gute Ergebnisse liefert.
Computer beschreiben Dinge oft durch lange Listen von Zahlen. Ein einzelner Satz kann so zu einer Liste aus 1536 Zahlen werden, ein Bild zu einer Liste aus mehreren tausend. Wie ähnlich sich zwei Dinge sind, misst man dann als Abstand zwischen ihren beiden Zahlenlisten: kleiner Abstand bedeutet ähnlich, großer Abstand bedeutet unähnlich. Solche langen Listen kosten aber viel Speicher und viel Rechenzeit. Die Johnson-Lindenstrauss-Transformation verkürzt sie drastisch, zum Beispiel von 1536 Zahlen auf 128. Der Clou: Die Abstände zwischen den verkürzten Listen bleiben fast dieselben wie vorher. Benannt ist das Verfahren nach den Mathematikern William B. Johnson und Joram Lindenstrauss, die den zugrunde liegenden Satz 1984 bewiesen.
Warum kurze Zahlenlisten bares Geld sparen
Moderne KI-Systeme vergleichen ständig solche Zahlenlisten miteinander. Eine Suchmaschine für Firmendokumente hält vielleicht zehn Millionen davon bereit. Bei jeder Suchanfrage muss sie die Anfrage mit sehr vielen gespeicherten Listen vergleichen. Halbiert man die Länge der Listen, halbiert sich grob auch die Rechenarbeit pro Vergleich.
Noch wichtiger ist der Speicher. Zehn Millionen Listen à 1536 Zahlen belegen mehrere Dutzend Gigabyte. Das passt nicht mehr in den schnellen Arbeitsspeicher eines normalen Servers, und Zugriffe auf die langsamere Festplatte bremsen alles aus. Kürzt man auf 128 Zahlen, schrumpft der Bedarf auf einen Bruchteil und alles bleibt im schnellen Speicher.
Der eigentliche Grund für die Bekanntheit des Verfahrens ist aber eine überraschende Aussage. Wie stark man kürzen darf, hängt fast gar nicht davon ab, wie lang die Listen ursprünglich waren. Entscheidend sind nur die Anzahl der Objekte und der Fehler, den man zu akzeptieren bereit ist. Ob man von 1000 oder von 100000 Zahlen startet, ändert am Ziel wenig.
Zufällige Projektion statt kluger Auswahl
Man könnte meinen, das Verfahren wähle sorgfältig die wichtigsten Zahlen aus. Genau das tut es nicht. Stattdessen erzeugt man eine Tabelle mit rein zufälligen Zahlen und multipliziert jede Liste damit. Aus dieser Rechnung fällt für jede Liste eine neue, kürzere Liste heraus. Die Zufallstabelle wird einmal erzeugt und danach für alle Objekte gleich verwendet.
Dass Zufall hier funktioniert, ist der eigentliche mathematische Kern. Der Satz von Johnson und Lindenstrauss garantiert: Mit hoher Wahrscheinlichkeit weicht jeder Abstand nach der Verkürzung nur um einen kleinen Prozentsatz vom ursprünglichen Abstand ab. Typisch sind Schranken wie zehn Prozent. Ein guter Vergleich ist der Schatten eines Drahtmodells an der Wand. Aus den meisten Blickwinkeln erkennt man die Form und die groben Verhältnisse noch gut, auch wenn eine Dimension verloren geht.
Es gibt einen Preis. Wer den erlaubten Fehler halbieren will, braucht ungefähr die vierfache Länge der neuen Listen. Sehr genaue Ergebnisse werden also schnell teuer. Außerdem sind die neuen Zahlen für Menschen bedeutungslos, weil sie Mischungen aus allen alten Zahlen sind. Und die Garantie gilt für Abstände, nicht für jedes beliebige Merkmal der Daten.
Vektordatenbanken, Empfehlungen und Bildsuche
Am häufigsten trifft man das Verfahren heute in sogenannten Vektordatenbanken. Das sind Speichersysteme, die Zahlenlisten verwalten und auf Anfrage die ähnlichsten zurückgeben. Sie stecken hinter Chatbots, die firmeneigene Dokumente durchsuchen, bevor sie antworten. Viele solcher Systeme kürzen die Listen vorab, um Speicher und Antwortzeit zu senken.
Auch Empfehlungssysteme in Onlineshops und Streamingdiensten nutzen ähnliche Kürzungen. Dasselbe gilt für die Bildsuche: Zwei Fotos gelten als ähnlich, wenn ihre Zahlenlisten dicht beieinanderliegen. In Fachtexten und Produktbeschreibungen taucht der Begriff oft als random projection oder als JL-Lemma auf.
Ein verwandter Begriff ist die Hauptkomponentenanalyse, kurz PCA. Auch sie kürzt Zahlenlisten, sucht dafür aber gezielt die aussagekräftigsten Richtungen in den Daten. Das liefert oft bessere Ergebnisse, kostet aber zusätzliche Rechenzeit und muss bei neuen Daten neu gemacht werden. Die Johnson-Lindenstrauss-Transformation braucht die Daten gar nicht anzuschauen und ist deshalb besonders schnell und einfach.