Gzip und KNN übertreffen Transformers bei der Textklassifikation

 (twitter.com/LukeGessler)
2 Punkte von GN⁺ 2023-07-15 | 1 Kommentare | Auf WhatsApp teilen
  • Vorschlag einer nichtparametrischen Methode zur Textklassifikation, die einen einfachen Kompressor wie gzip mit einem k-Nearest-Neighbor-(kNN)-Klassifikator kombiniert
  • Kommt ganz ohne Trainingsparameter aus, ist dennoch leichtgewichtig und universell einsetzbar und verursacht im Vergleich zu DNNs geringere Rechenkosten
  • Erzielt im Vergleich zu nicht vortrainierten Deep-Learning-Methoden auf sechs In-Distribution-Datensätzen konkurrenzfähige Ergebnisse
  • Übertrifft BERT auf allen fünf OOD-(Out-of-Distribution)-Datensätzen, darunter vier ressourcenarme Sprachen
  • Zeigt auch in Few-Shot-Szenarien, in denen zu wenige gelabelte Daten für ein effektives DNN-Training vorhanden sind, starke Leistung

Hintergrund und Problemstellung

  • DNNs werden wegen ihrer hohen Genauigkeit breit für Textklassifikation eingesetzt
  • Sie erfordern jedoch Millionen von Parametern und große Mengen gelabelter Daten, was hohe Rechenkosten verursacht
  • Dadurch werden Nutzung, Optimierung und die Übertragung auf OOD-(Out-of-Distribution)-Situationen in der Praxis zu kostspieligen Aufgaben

Vorgeschlagene Methode

  • Als Alternative zu DNNs wird eine einfache, leichtgewichtige und universelle nichtparametrische Methode vorgestellt
  • Die Architektur kombiniert einen einfachen Kompressor wie gzip mit einem k-Nearest-Neighbor-Klassifikator
  • Das zentrale Merkmal ist, dass sie vollständig ohne Trainingsparameter auskommt

Experimentelle Ergebnisse

  • Auf sechs In-Distribution-Datensätzen erreicht sie eine Leistung, die mit nicht vortrainierten Deep-Learning-Methoden konkurrieren kann
  • Übertrifft BERT auf allen fünf OOD-Datensätzen, darunter vier ressourcenarme Sprachen
  • Hat auch Stärken in Few-Shot-Szenarien, in denen zu wenige gelabelte Daten vorhanden sind, um ein DNN effektiv zu trainieren

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-15
Hacker-News-Kommentare

  • Direkter Link zum Paper: https://aclanthology.org/2023.findings-acl.426.pdf
    Intuitiv ist der Kern, dass bei den Dokumenten x1, x2 und einem neuen Dokument x gilt: Wenn die statistische Regelmäßigkeit von x näher an x1 als an x2 liegt, dann ist len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)). Dabei ist cat das Aneinanderhängen und compress ein Kompressor wie gzip.
    Wörtlich ist len(compress(cat(x1,x))) - len(compress(x)) die zusätzlich benötigte Byte-Zahl, um die statistische Regelmäßigkeit von x1 zu komprimieren, gegeben die statistische Regelmäßigkeit von x. Je ähnlicher sich x1 und x sind, desto weniger zusätzliche Bytes werden benötigt, um cat(x1,x) zu komprimieren, verglichen mit der Komprimierung von x allein.
    Die Autoren verwenden auf Basis dieser Idee eine Distanzfunktion namens Normalized Compression Distance (NCD) und wenden k-Nearest Neighbors (kNN) auf komprimierte Dokumente an. Außerdem behandeln sie den Zusammenhang zwischen NCD, Information, Shannon-Entropie und Kolmogorov-Komplexität.
    Überraschenderweise schlägt diese einfache und intuitive Methode BERT bei mehreren Zero-Shot-Klassifikationsaufgaben. Das heißt allerdings nicht zwangsläufig, dass sie auch größere und neuere Transformer schlägt.

    • Diese Methode ist nur bei Out-of-Distribution-Daten und überlappenden Tokens besser. Sie hat kein semantisches Verständnis; das Ergebnis mag stimmen, aber der Titel ist irreführend.
    • Ich frage mich, ob etwas bessere Ergebnisse herauskämen, wenn man statt die Dokumente einfach aneinanderzuhängen die Unterstützung von zstd-Kompressionswörterbüchern nutzen würde.
      Man würde also die Kompressionsgröße mit und ohne Verwendung des Dokuments als Wörterbuch vergleichen. Da zstd zumindest auf Level 20+ eine deutlich höhere Kompressionsrate als gzip erreicht, könnte es noch besser funktionieren, wenn der Erfolg bei gzip tatsächlich auf einer Approximation der Kolmogorov-Komplexität beruht.
    • Wenn das zu lösende Problem letztlich „Ist x eher x1 oder x2 ähnlich?“ lautet, dann wirkt das anders als das Problem, das ein LLM löst, daher wäre es nicht überraschend, wenn es besser abschneidet.
      Wenn x1 Englisch ist und x die hebräische Übersetzung desselben Dokuments, würde ich erwarten, dass ein LLM besser ist.
    • Streng genommen ist das kein Zero-Shot, sondern Few-Shot. Man braucht weiterhin eine Referenzmenge von Prototypen als Trainingsbasis.
    • Ich frage mich, ob sich derselbe Ansatz auch auf Bilder anwenden lässt.
      Ich habe kürzlich mit Bildern gearbeitet und dabei JPEG ausgegeben; selbst bei denselben Grundpixeln können sehr unterschiedliche Bilder entstehen. Interessant ist, dass die JPG-Dateigröße größer wird, je verrauschter und zufälliger ein Bild ist, und kleiner, je mehr es wie ein Foto aussieht.

  • Wenn dich die Äquivalenz von KI und Kompression interessiert, lohnt sich ein Blick auf den Hutter Prize :) http://prize.hutter1.net/
    Sehenswert ist auch das Large Text Compression Benchmark http://mattmahoney.net/dc/text.html - der derzeit weltbeste Kompressor ist ein neuronales Netz von Fabrice Bellard, dem bekannten Schöpfer von ffmpeg und QEMU.
    Ich mag auch sehr den passenden rein textbasierten Stil solcher Seiten.

    • Besonders kompressionsalgorithmen auf Basis arithmetischer Kodierung, die durch Vorhersage des nächsten Inhalts die Intervallgewichtung anpassen, sind sehr ähnlich.
      Dabei wird die arithmetische Kodierung(https://en.wikipedia.org/wiki/Arithmetic_coding) abhängig vom Kontext des vorherzusagenden Bytes/Bits angepasst; je genauer das Kommende vorhergesagt wird, desto effizienter wird die Kodierung. Die Aufgabe selbst ist der von GPT-ähnlichen Transformern sehr ähnlich.
      Bei perfekter Vorhersage schrumpft das arithmetische Intervall nicht, daher entstehen fast keine zusätzlichen Speicherkosten und somit werden auch keine Bits gespeichert. Für einen fairen Benchmark müsste man allerdings auch die Größe des Dekompressors einrechnen.
    • Wenn man tief genug in die Mathematik eintaucht, wird vieles im Kern dasselbe. Super-Resolution ist nur Dekonvolution mit gutem Marketing, ein Single-Layer-Perzeptron ist ein SVM mit linearem Kernel und logistische Regression, und die FFT ist letztlich nur Faktorisierung.
    • Wichtig ist, dass die Autoren Normalized Compression Distance (NCD) verwenden. NCD ist eine Methode zur Approximation der Kolmogorov-Komplexität.
      Das ist eine ziemlich alte Idee; siehe [1,2]. Alt, aber wie das Perzeptron immer noch sehr nützlich.
      [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
      [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
    • Fabrice Bellard ist wirklich eine lebende Legende. Auf diese Liste gehören auch QuickJS, jslinux, tcc und TinyGL.
    • Diese Art von „Kompression“ ist im Wesentlichen eher Verstehen durch Theorie, ähnlich wie eine Theorie in der Physik.
      Eine Theorie ist wie eine Geschichte, die mit denselben „Figuren“ sehr viel erklärt. Diese Figuren sind hier eher Konzepte; ein Beispiel dafür wären Atome.

  • Ich möchte darauf hinweisen, dass diese Methode nur bei Nachrichtenartikeln stärker ist.
    Bei Yahoo Questions ist sie nicht die beste. Es ist nicht unplausibel anzunehmen, dass Nachrichten in ähnlicher Weise geschrieben werden und manchmal sogar teilweise kopiert sind, sodass viele Wörter gemeinsam vorkommen.
    Yahoo Questions ist ein Forum, daher ist die Wortvariation größer, aber zwischen den Wörtern bestehen semantische Ähnlichkeiten.
    Mit anderen Worten: gzip ist stark, wenn es viele Wortüberlappungen gibt (der Größenanstieg bei der gzip-Komprimierung ist klein), und wenn semantische Ähnlichkeit wichtig ist, gewinnt ein DNN immer.
    Die Ergebnisse sind interessant, aber meiner Meinung nach nicht so interessant, wie sie klingen.

    • Wenn sich semantische Ähnlichkeit unterscheidet, wie funktioniert das dann eigentlich? Ist das beim Training nicht letztlich nur das Clustering semantisch ähnlicher Repräsentationen?

  • Es ist sehr wichtig zu beachten, dass dieses Ergebnis aus Out-of-Distribution-Daten stammt. Zum Beispiel handelt es sich um Nachrichten in Sprachen wie „Kinyarwanda, Kirundi, Pinyin“.
    In allgemeineren Settings gewinnt BERT weiterhin mit großem Abstand.
    Es ist zwar cool, dass eine so einfache Methode sehr effektiv sein kann, aber man sollte das nicht überverkaufen.

    • Dieser Punkt sollte wirklich stärker betont werden. Als ich nur die Überschrift gelesen hatte, wirkte es erstaunlich, als hätte man zufällig Belege für ein zuvor unbekanntes und noch unerklärtes physikalisches Gesetz gefunden, in diesem Fall ein linguistisches Gesetz.
      Betrachtet man aber die zitierten Bedingungen, ist es eher ziemlich intuitiv. Was bedeutet es, Text in einer völlig unbekannten Sprache zu klassifizieren? Wenn man Kirundi-Text klassifizieren soll, versteht man die Bedeutung überhaupt nicht, und das Beste, was man tun kann, ist, die Häufigkeit von Wörtern oder Zeichenfolgen zu betrachten und Texte mit ähnlichen Häufigkeits-Fingerabdrücken zu gruppieren.
      Die eigentliche Bedeutung versteht man zwar immer noch nicht, aber man kann besser sein als Zufall, und genau das passiert auch. Die gute Nachricht ist, dass genau das gzip+kNN tut; das ist ihre Kernaufgabe und der Grund ihrer Existenz.
      Wenn man versucht, diesen Text zu lesen und zu verstehen oder das nächste Zeichen vorherzusagen, gewinnt man dabei nicht viel. Ein normaler Mensch würde das gar nicht erst versuchen, weil er die Sprache nicht kennt. Leider macht BERT genau das. Es ist eben das Einzige, was BERT kann. Trotzdem kann man BERT dazu beglückwünschen, dass es daraus noch mehr Nutzen gezogen hat als ein gewöhnlicher Mensch, vielleicht sogar mehr als ein ungewöhnlicher Mensch.

  • Tatsächlich sehr clever und intuitiv nachvollziehbar.
    Wenn man zwei ähnliche Textstücke aneinanderhängt, lassen sie sich besser komprimieren als zwei unterschiedliche Textstücke.

    • Das ist zwar bekannt, aber eher eine etwas weniger bekannte Technik. Der Hauptbeitrag hier ist die Formalisierung und Messung.

  • Das wirkt weniger wie ein Sieg dieser Methode als eher wie ein negatives Signal für Deep-Learning-basierte Ähnlichkeit.
    Im Hype um LLMs ist zwar klar, dass LLMs großartig sind, aber viele scheinen anzunehmen, dass es auch bei Embedding-Layern für reine Textähnlichkeit ähnliche Fortschritte gegeben hat.
    Deshalb gibt es diesen Boom an Embedding-Datenbanken aller Art, aber ich sehe kaum Belege, die das stützen.

    • https://twitter.com/eugeneyan/status/1678060204943097863

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      Interessante Tatsache: Die Query-Dokument-Ähnlichkeit wurde nicht mit Vektoren, sondern schlicht mit TF-IDF behandelt. Sobald die Zahl der Suchdokumente 45 überschritt, war das besser als Vektorsuche; tatsächlich wurden 50 verwendet.
      https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa...
      This case illustrates that in-domain effectiveness does not necessarily transfer to an out-of-domain zero-shot application of the model. Generally, as observed on the BEIR dense leaderboard, dense embeddings models trained on NQ labels underperform the BM25 baseline across almost all BEIR datasets.

    • Könnte mir jemand nur eine Frage beantworten? Wenn man Text-Embeddings aus einem LLM für Ähnlichkeitsmessung erzeugt, welche Schicht verwendet man dann? Die Eingabeschicht? Eingabeschicht plus Positionskodierung? Eine verborgene Schicht? Die Ausgabeschicht?

  • Der Link sollte auf das Paper-PDF https://aclanthology.org/2023.findings-acl.426.pdf verweisen.

  • Kompressionsalgorithmen sind das Einsparen bzw. Komprimieren von Raum, also von Bits und Bytes. Machine-Learning-Modelle, insbesondere generative Modelle, sparen bzw. komprimieren menschlichen Ausdruck und menschliches Denken.
    Textklassifikation ist eine Form der Kompression über menschlichem Ausdruck. Könnte es grundlegende Eigenschaften menschlicher Sprache und Daten geben, die erklären, welches von beiden bei einer Machine-Learning-Aufgabe besser sein wird?
    Wenn sich so eine Theorie eines Tages herausbildet, wäre es vielleicht gar nicht überraschend, dass die Kodierung komprimierter Bits/Bytes und komprimierter menschlicher Ausdruck in irgendeinem Raum eng miteinander verwandt sind und auf irgendeine Weise verbunden sein könnten. Tatsächlich könnten solche Theorien, etwa entropiebasierte oder physikbasierte Theorien, dabei helfen zu entscheiden, ob man für bestimmte Arten der Kompression menschlichen Ausdrucks einen Kompressionsalgorithmus oder ein Machine-Learning-Modell verwenden sollte.
    Datenzentriert betrachtet: Was wären schwierige negative Beispiele, die solche Algorithmen schlecht aussehen lassen? Im Moment kann man sich dieser Theorie vielleicht nur aus der Perspektive verschiedener Arten menschlicher Textdaten annähern. Zum Beispiel funktioniert das Vorhersagen von Mischungen mit statistischen Themenmodellen bei wissenschaftlichen Texten gut, stößt aber bei Internettexten auf Schwierigkeiten.
    Gibt es außer Wolfram Physics noch jemanden, der so eine Theorie erforscht?

  • Ergibt völlig Sinn. Kompression hat mit „Verstehen“ zu tun, also damit, die Eingabe auf eine Weise darzustellen, in der man sie erkennen und labeln kann.
    Wenn die erkannten Bits größer sind als das Label, voilà, dann hat man Kompression. Dass gzip bei dieser Aufgabe besser sein kann als ein DNN, ist nicht überraschend.

    • Dann frage ich mich, ob andere Kompressionsalgorithmen noch besser sein könnten.
    • Ich würde sagen, Kompression ist eine Teilmenge von Verstehen. Wenn ein Kind beginnt, grammatikalisch korrekt zu sprechen, hat es alle Sprachmuster, denen es ausgesetzt war, in grammatische Regeln komprimiert.
      Ich nenne es eine Teilmenge, weil Verstehen allgemeiner ist. Ein bestimmter Kompressionsalgorithmus kann bei Gleitkommazahlen gut funktionieren. Das Gehirn und künstliche neuronale Netze könnten dagegen vielleicht jedes beliebige Eingabemuster komprimieren, auch wenn ihre Leistung dabei schlechter ist.

  • Ich verstehe nicht, wie gzip mit Wörtern wie „not“ umgehen kann, die die Bedeutung eines ganzen Satzes umkehren.
    Versteht das jemand?

    • Wie auch in einigen Kommentaren auf Twitter erwähnt wurde: Das hier ist für Topic Modeling. Negationen sind hier möglicherweise weniger wichtig als bei Aufgaben wie Sentimentanalyse.