Mit GZIP in weniger als 10 Zeilen Code 78 % Genauigkeit auf MNIST erreicht

 (jakobs.dev)
1 Punkte von GN⁺ 2023-09-21 | 1 Kommentare | Auf WhatsApp teilen
  • Ein Experiment zur Klassifikation handgeschriebener Ziffern aus MNIST erreicht mit GZIP-Komprimierung und k-Nearest Neighbors (k-NN) rund 78 % Genauigkeit und zeigt, dass sich Komprimierung als modellfreies Klassifikationswerkzeug nutzen lässt
  • Die normalisierte Kompressionsdistanz (NCD) wird daraus berechnet, wie stark sich die Länge verändert, wenn zwei Bildbeispiele gemeinsam komprimiert werden, und als Ähnlichkeitsmaß zwischen Bildern verwendet
  • Jedes Testbeispiel wird mit 100 Trainingsbeispielen verglichen; das Mehrheitslabel der k=5 nächsten Nachbarn wird zur Vorhersage
  • Wegen der Rechenkosten wurde die Genauigkeit nicht auf dem gesamten Testset, sondern nur auf einem Teil der Testbilder gemessen; mit dem vollständigen Set könnte die Auswertung genauer werden
  • Im veröffentlichten Beispiel bleibt ein Refactoring-Fehler bestehen: Obwohl ein Cache für Kompressionslängen angelegt wird, wird er in der eigentlichen NCD-Berechnung nicht verwendet; nötig wäre das Entfernen des Caches oder eine Anpassung von compute_ncd

MNIST mit GZIP + k-NN klassifizieren

  • Das Experiment klassifiziert den Datensatz handgeschriebener Ziffern MNIST mit der Kombination GZIP + k-NN
  • Das kurze Codebeispiel verwendet die Länge von gzip.compress(z.tobytes()) als Kompressionslänge, berechnet daraus die NCD und wählt anschließend das häufigste Label unter den fünf nächsten Nachbarn
  • Ein ausführbares Beispiel gibt es im Jupyter Notebook
  • Das Ziel ist nicht die bestmögliche Genauigkeit, sondern eine einfache Überprüfung der Idee, Komprimierung als modellfreies Klassifikationswerkzeug einzusetzen
  • Der Code mit weniger als 10 Zeilen ist weniger der Kern des Experiments als vielmehr ein Code-Golf-Element zum Spaß

Ähnlichkeitsberechnung und Klassifikationsablauf

  • Die NCD misst Ähnlichkeit, indem sie normiert, wie stark sich die Kosten der gemeinsamen Komprimierung zweier Datenpunkte von der getrennten Komprimierung unterscheiden
  • Die Kompressionslängen werden in folgender Form berechnet
    • Cx1 = len(gzip.compress(x1.tobytes()))
    • Cx2 = len(gzip.compress(x2.tobytes()))
    • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
  • Die NCD-Formel hat die Form (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
  • Für die Klassifikation werden die Distanzen zwischen jedem Testbild und den Trainingsbildern berechnet, nach Nähe sortiert und anschließend die Labels der fünf nächsten per Mehrheitsentscheid ausgewertet
  • Im Experiment wurden 100 Trainingsbeispiele als Vergleichsbasis verwendet, und wegen der Rechenkosten kam auch beim Testset nur ein Teil zum Einsatz

Verwandte Ideen und Hinweise zum Code

  • Dieser Ansatz ist inspiriert vom Artikel text generation from data compression und dem Paper parameter free text classification
  • Nach Veröffentlichung wurde außerdem der Beitrag MNIST by ZIP von Andreas Kirsch aus dem Jahr 2019 entdeckt, der einen ähnlichen Ansatz verwendet
  • Der Beispielcode legt zwar einen Cache für Kompressionslängen der Trainingsbeispiele an, verwendet diese Werte in der eigentlichen Schleife aber nicht
    • Sowohl die normale als auch die obfuskierte Version erzeugen compressed_lengths bzw. cls, nutzen die zwischengespeicherten Längen jedoch nicht in der NCD-Berechnung
    • Wenn der Cache entfernt und direkt training_set verwendet wird oder compute_ncd so angepasst wird, dass die Cache-Werte genutzt werden, stimmen Absicht und Implementierung des Codes wieder überein

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-09-21
Meinungen auf Hacker News

  • Als ich die Distanzfunktion im Code durch einfachere Maße ersetzt habe, zeigte sich: Die GZIP-Distanz hat bei der MNIST-Klassifikation eine niedrigere Genauigkeit und einen deutlich höheren Rechenaufwand.
    Gzip-Distanz: ca. 3 Minuten, 78 % Genauigkeit / euklidische Distanz: ca. 0,5 Sekunden, 93 % / Jaccard-Distanz: ca. 0,7 Sekunden, 94 % / Dice-Dissimilarität: ca. 0,8 Sekunden, 94 %
    Jaccard und Dice wurden nach Binarisierung der Bilder gemessen.
    Ich bin mit dem GZIP-Algorithmus nicht besonders vertraut, aber dass die Ergebnisse so niedrig ausfallen, ist interessant; ich frage mich auch, ob ein bildzentrierter Kompressionsalgorithmus besser wäre.
    Der Beitrag selbst ist kreativ, und Code sowie Erklärung waren gut, aber ich denke, die obigen Baselines geben dem gzip-Score mehr Kontext.

    • Das beste Ergebnis, das ich gefunden habe, lag bei normalisierter gegenseitiger Information mit 95 %; das ist etwas komplexer, lässt sich auf binarisierten Bildern aber recht schnell berechnen.
      NMI skimage: ca. 30 Sekunden, 95 % Genauigkeit / NMI numba: ca. 0,6 Sekunden, 95 % Genauigkeit
      Mit dem von ChatGPT gelieferten numba-Code habe ich 2x2-Joint-Counts, Entropie und normalisierte gegenseitige Information berechnet.
    • Mir war klar, dass MNIST einfach ist, aber nicht, dass es so weit geht; wenn du die verwendeten Code-Schnipsel teilen könntest, wären sie wirklich gut als Baseline.
      Persönlich interessiere ich mich für schnelles Training auf CIFAR10, und solche Ansätze scheinen auch in anderen Bereichen recht nützlich sein zu können.
    • Ben Rechts Implementierung von Kernel-Methoden erreicht in 10 Zeilen 98 %.
      https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
    • Ich habe auch PNG-Kompression ausprobiert, und sie war tatsächlich etwas besser: PNG kam in etwa 15,1 Sekunden auf 83 % Genauigkeit.
      Ich habe auch zstandard hinzugefügt; Zstd(level=3) war mit ca. 3,5 Sekunden und 88 % Genauigkeit deutlich schneller als gzip.
      Wenn man bei der Berechnung von Cx1x2 statt x1+x2 den Ausdruck (x1-x2)*2 verwendet, steigt zstd auf 93 % Genauigkeit.
      Wenn man die beiden Arrays nicht addiert, sondern vertikal stapelt, bricht die Leistung völlig ein und fällt unter 20 %; interessant ist, dass diese Methode bei der String-Klassifikation offenbar gut funktioniert.
    • Der gzip-Ansatz ist zwar cool, aber am Ende wirkt es so, als liefere er mit mehr Schritten schlechtere Ergebnisse.

  • Im Vergleich zu anderen Verfahren liegt Linear SVC bei 92 %, SVC mit RBF-Kernel bei 96,4 %, SVC mit polynomialem Kernel bei 94,5 %, logistische Regression bei 89 % und Naive Bayes bei etwa 81 %.
    Quelle: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
    Wenn man sich Online-Beiträge ansieht, scheint allein mit K-NN ein deutlich besseres Ergebnis möglich zu sein; vielleicht hat der Autor es sich mit gzip unnötig schwer gemacht.

    • Viele wissen nicht, dass logistische Regression auf MNIST etwa 90 % Genauigkeit erreichen kann.
      Ich beginne gern mit einfachen Modellen und erhöhe später die Komplexität, aber ich habe oft gehört: „logistische Regression geht nicht“, selbst bei Problemen, bei denen sie tatsächlich gut funktioniert hätte.
      Wenn man fragt, welche Basisleistung sie bei MNIST erwarten würden, schätzen viele 20 bis 30 %.
      Auch Leute aus dem Machine Learning unterschätzen oft, wie schnell bei stark steigender Modellkomplexität abnehmende Erträge einsetzen.
      Wenn ein einfaches Modell keine gute Leistung bringt, war es in vielen Fällen auch schwierig, mit einem komplexeren Modell hervorragende Ergebnisse zu erzielen.
    • Dieser Blog zeigt nicht die aktuelle Bestleistung, sondern vergleicht eher relativ einfache SVM-Implementierungen.
      Schon das ursprüngliche Paper, das den MNIST-Datensatz eingeführt hat, erreichte etwa 98 % Genauigkeit, und heutige neuronale Netze kommen auf bis zu 99,87 %.
      https://paperswithcode.com/sota/image-classification-on-mnis...
    • Der Kernpunkt ist nicht, besser zu sein, sondern zu zeigen, dass nach der Kompression noch genug Information übrig bleibt, um ein starkes Signal zu erhalten.
      Kompression ist ursprünglich dazu da, das Problem schwieriger zu machen, und tatsächlich funktioniert sie weiterhin so.
    • Dass das funktioniert, ist cool, aber da MNIST inzwischen so einfach geworden ist, würde ich mir wünschen, dass man es nicht mehr als Benchmark verwendet.
    • Für die Beziehung zwischen MNIST-Eingaben und -Ausgaben gibt es gewissermaßen einen optimaleren Kompressionsalgorithmus.
      Andere Modelle neigen dazu, irgendwo Rauschen hinzuzufügen; daher frage ich mich, wie es wäre, vor gzip Feature Engineering einzubauen.
      Zum Beispiel könnte man zuerst Gaussian Blur und Faltungen anwenden und danach Deep Learning für die Feature-Auswahl nutzen.

  • Der Code mag elegant und kurz sein, aber 78 % Genauigkeit auf MNIST ist sehr schlecht.
    Selbst ein Dummy-Modell mit TensorFlow erreicht leicht 90 % Genauigkeit, und das beste Modell liegt bei 99,87 %.
    Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

    • Ich denke, der Beitrag setzt den Schwerpunkt falsch.
      Interessant ist, dass man Kompression zur Klassifikation nutzen kann, ohne ein Modell zu trainieren.
      Das wirft die Frage auf, ob sich auch andere, günstigere und verlustbehaftete informationstheoretische Maße verwenden lassen.
      To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review
      [https://arxiv.org/abs/2304.09355\)" class="ud link">https://arxiv.org/abs/2304.09355\](https://arxiv.org/abs/2304.09355\)*
    • Das Ziel ist nicht, „eleganten und kurzen“ Code zu schreiben, sondern eine interessante Kuriosität zu zeigen; die Umsetzung in 10 Zeilen ist eher eine zusätzliche Herausforderung.
      Interessant ist nicht, ob GZip die aktuelle Bestleistung erreicht, sondern dass es halbwegs klassifizieren kann.
      Es ist ein bisschen so, als wäre nicht entscheidend, ob ein Bär Mozart perfekt wiedergibt, sondern dass er überhaupt Klavier spielen kann.
    • Es geht nicht darum, einen Rekord zu brechen, sondern ein interessantes Beispiel für Kompression zu zeigen.
      Trotzdem ist es achtmal besser als die Baseline und zeigt, dass Kompression Repräsentationen lernen kann.

  • Wenn man compute_ncd durch die euklidische Distanz ersetzt, steigt die Testgenauigkeit um 15 Prozentpunkte und der Rechenaufwand sinkt deutlich.
    Man kann es etwa so ändern: distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths]

  • Als Buch über die tiefen Zusammenhänge zwischen Informationstheorie, Kompression und Lernalgorithmen fand ich MacKay am besten.
    Für ordentlich ausgebildete Leute mag das Allgemeinwissen sein, aber aus der Perspektive von jemandem, der sich praxisorientiertes Machine Learning autodidaktisch beigebracht hat, war es ein intensiver „Aha!“-Moment zu sehen, wie dieses Thema bis in Bereiche wie Teilchenphysik und Kosmologie hineinreicht.
    Ich lasse das hier stehen, in der Hoffnung, dass wenigstens eine Person zu derselben Erkenntnis kommt.

    • Ich habe MacKay auf meine To-do-Liste gesetzt.
      Ziemlich beeindruckend fand ich die Erkenntnis, dass die ursprüngliche Lempel-Ziv-Kompression, eine der Grundlagen von gzip, nicht einfach aus dem Versuch entstand, Dinge kleiner zu machen, sondern aus der Forschung zur „Komplexität endlicher Folgen“.
      https://ieeexplore.ieee.org/document/1055501

  • Fairerweise muss man sagen: MNIST wird schon fast perfekt getrennt, wenn man es nur durch UMAP schickt.
    Ich denke, heutzutage muss man sich bei MNIST schon ziemlich anstrengen, um schlechte Ergebnisse zu bekommen.
    https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
    Es wäre wohl besser, diesen Datensatz endlich in den Ruhestand zu schicken; Datensätze wie QuickDraw ergeben deutlich mehr Sinn.

    • Als Autor stimme ich dem völlig zu.
      An sich ist das schwerlich eine große Leistung, aber es ist trotzdem interessant zu sehen, dass es funktioniert.
      Wenn ich zu Hause bin, werde ich im Artikel ergänzen, dass MNIST vergleichsweise leicht zu lösen ist.
    • Aus Forschungssicht ist MNIST im Grunde ein gelöstes Problem, und die aktuelle Leistung dürfte besser sein als die von Menschen.
      Trotzdem erreichen die meisten einfachen und vernünftigen Algorithmen 97 % Genauigkeit, daher hat es als Lehrmittel oder als Hello-World-Datensatz weiterhin Wert.
      Selbst wenn man die Werkzeuge von Grund auf selbst baut, passt es vom Umfang her zu einer Hausaufgabe, und es ist eine nützliche Aufgabe, die jeder versteht, etwa „Ziffernerkennung auf Postsendungen“.
    • gzip ist nichts „Modernes“, sondern deutlich älter als UMAP und sogar älter als MNIST selbst.
      Wenn man Kompression versteht, ist auch dieser Ansatz eine sehr einfache Idee; man hätte ihn schon am ersten Tag der Veröffentlichung von MNIST schreiben können und wäre trotzdem auf 78 % Genauigkeit gekommen.
      Das finde ich ziemlich erstaunlich.
    • Das lässt sogar die unhöfliche Person, die sich über Abkürzungen beschwert hat, plausibel wirken.
      Auch das Repository definiert UMAP nicht, aber wenn man ChatGPT glaubt, steht UMAP für Uniform Manifold Approximation and Projection, eine Technik zur Dimensionsreduktion und Visualisierung, die in Machine Learning und Datenanalyse verwendet wird.

  • Ich beschäftige mich mit diesem Gebiet nur hobbymäßig, aber stark komprimierte Daten haben doch, ähnlich wie verschlüsselte Daten, eine hohe Entropie, oder?
    Wenn man in komprimierten Daten Muster findet, um die ursprüngliche Ziffer zu erkennen, müsste man diese Muster dann nicht für eine bessere Kompression nutzen können?

    • Diese Demo klassifiziert nicht, indem sie die komprimierten Daten anschaut, sondern danach, wie gut sich die Daten komprimieren lassen.
      Die Idee ist: „7 7“ sollte sich besser komprimieren lassen als „7 3“, und auch bei Rasterbildern sollte sich „7 7“ besser komprimieren lassen als „7 3“.
    • Ideale verschlüsselte Daten sollten nicht komprimierbar sein.
      Nichtkomprimierbarkeit ist ein Merkmal effizienter kryptografischer Operationen.
      Siehe den Abschnitt zur Kompression im Artikel zur Kolmogorow-Komplexität: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
      Eines meiner Lieblingskonzepte bei Kompression ist das Schubfachprinzip: Für jeden Kompressionsalgorithmus gibt es zwangsläufig Ausgaben, die größer sind als die Eingaben.
      Auch bei gut entworfenen verschlüsselten Payloads kann man versuchen, sie zu komprimieren, aber im Durchschnitt wird die Ausgabe größer als die Eingabe, wodurch Kompression nutzlos wird; deshalb nennt man sie „nicht komprimierbar“.
      https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

  • Ich glaube, vor ein paar Jahren gab es einen Fall, in dem die Größe von MNIST-Bildern als „Meta-Feature“ verwendet wurde, aber ich kann ihn auf die Schnelle nicht finden.
    Soweit ich mich erinnere, kam man allein mit diesem einen Feature, ohne die Bilder überhaupt anzusehen, ungefähr auf eine Genauigkeit von um die 90 %.

    • Vor ein paar Jahren habe ich an einem Projekt zur Fingerabdruckbildung von Webseiten-Screenshots gearbeitet, und allein die Größe der komprimierten Bilder funktionierte zur Ähnlichkeitsmessung zwischen Screenshots ungefähr so gut wie eine bestimmte Fingerprinting-Methode.
    • Ich frage mich, was hier mit „Größe“ gemeint ist.
      Die mit gzip komprimierte Größe? Wenn man nur betrachtet, wie dunkel ein MNIST-Bild ist, also den Anteil dunkler Pixel, kommt man auf etwa 20 % Genauigkeit – doppelt so gut wie Zufall, aber weit entfernt von 90 %.

  • Ich vermute, die Autoren des Papers haben einen Fehler gemacht, wodurch die Ergebnisse in den oberen Bereich des Benchmarks geschossen sind.
    Seit diesem Vorfall hielt ich die Theorie für inkonsistent, aber 78 % Genauigkeit nur mit GZIP sind trotzdem beeindruckend.

    • Vermutlich ist dieser Artikel gemeint: https://kenschutte.com/gzip-knn-paper/
    • Das hier sind 78 % Genauigkeit mit Gzip-basierter Kompressionsdistanz und KNN; es wirkt also schlechter als fast jede andere Distanzmetrik, die einem mit KNN einfallen könnte.

  • Unabhängig davon, ob dieses Problem ein guter Anwendungsfall für Kompressionstricks ist: Wer damit experimentiert, sollte aufhören, gzip zu verwenden, und stattdessen zlib nutzen.
    Wenn man in der ersten Zeile gzip.compress durch zlib.compress ersetzt, bekommt man bei gleicher Klassifikationsleistung eine dreimal höhere Geschwindigkeit.