Logran 78% de precisión en MNIST con GZIP en menos de 10 líneas de código

• Un experimento llevó la clasificación de dígitos manuscritos de MNIST hasta cerca de 78% de precisión usando solo compresión GZIP y k-vecinos más cercanos (k-NN), mostrando que la compresión puede usarse como una herramienta de clasificación sin modelo
• Calcula la distancia de compresión normalizada (NCD) según cuánto cambia la longitud al comprimir dos muestras de imagen juntas, y la usa como métrica de similitud entre imágenes
• Cada muestra de prueba se compara con 100 muestras de entrenamiento, y la etiqueta mayoritaria de los vecinos con k=5 más cercanos se toma como predicción
• Debido al costo computacional, la precisión se midió con solo una parte de las imágenes de prueba en lugar de todo el test set; usar el conjunto completo podría dar una evaluación más precisa
• El ejemplo público todavía contiene un error de refactorización: crea una caché de longitudes comprimidas pero no la usa en el cálculo real de NCD, por lo que haría falta eliminar la caché o reflejarla en compute_ncd

---

Clasificar MNIST con GZIP + k-NN

• El experimento clasifica el dataset de dígitos manuscritos MNIST con la combinación GZIP + k-NN
• El ejemplo corto de código usa la longitud del resultado de gzip.compress(z.tobytes()) como longitud comprimida, calcula la NCD y luego elige la etiqueta más frecuente entre los 5 vecinos más cercanos
• Hay un ejemplo ejecutable en Jupyter Notebook
• El objetivo no es lograr la máxima precisión, sino validar de forma simple la idea de usar la compresión como una herramienta de clasificación sin modelo
• El código de menos de 10 líneas es más un elemento divertido de code golf que el núcleo del experimento

Cálculo de similitud y procedimiento de clasificación

• La NCD mide la similitud normalizando cuánto difiere el costo de comprimir dos puntos de datos juntos frente a comprimirlos por separado
• La longitud comprimida se calcula así
  • Cx1 = len(gzip.compress(x1.tobytes()))
  • Cx2 = len(gzip.compress(x2.tobytes()))
  • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
• La fórmula de NCD tiene la forma (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
• Para clasificar, se calcula la distancia entre cada imagen de prueba y las imágenes de entrenamiento, se ordenan de menor a mayor y se usa votación mayoritaria de las 5 más cercanas
• En el experimento, la comparación se hizo tomando 100 muestras de entrenamiento como referencia y, por el costo computacional, también se usó solo una parte del test set

Ideas de referencia y detalles a cuidar en el código

• Este enfoque se inspira en el artículo text generation from data compression y en el paper parameter free text classification
• Después de publicar el texto, también se encontró el post MNIST by ZIP de Andreas Kirsch, que en 2019 usó un método similar
• El código de ejemplo crea una caché de longitudes comprimidas para las muestras de entrenamiento, pero en el bucle real no usa esos valores
  • Tanto la versión normal como la ofuscada crean compressed_lengths o cls, pero no usan las longitudes cacheadas en el cálculo de NCD
  • Si se elimina la caché y se usa training_set directamente, o si compute_ncd se modifica para aprovechar esos valores, la intención del código y su implementación quedarían alineadas

[GN⁺]

Opiniones de Hacker News

• Al cambiar la función de distancia del código por una métrica más simple, en la clasificación de MNIST la distancia GZIP tiene menor precisión y requiere mucho más cómputo.
  Distancia Gzip: aprox. 3 min, 78% de precisión / distancia euclidiana: aprox. 0.5 s, 93% / distancia de Jaccard: aprox. 0.7 s, 94% / disimilitud Dice: aprox. 0.8 s, 94%
  Jaccard y Dice se miden después de binarizar las imágenes.
  No conozco mucho el algoritmo GZIP, pero me parece interesante que el resultado sea tan bajo, y me pregunto si un algoritmo de compresión centrado en imágenes podría funcionar mejor.
  El artículo en sí es creativo, y el código y la explicación también son buenos, pero creo que esas líneas base aportan contexto a la puntuación de gzip.

  • El mejor resultado que encontré fue con información mutua normalizada, con 95%; es un poco más complejo, pero puede calcularse bastante rápido en imágenes binarizadas.
    NMI skimage: aprox. 30 s, 95% de precisión / NMI numba: aprox. 0.6 s, 95% de precisión
    Calculé los conteos conjuntos 2x2, la entropía y la información mutua normalizada con código numba que me dio ChatGPT.
  • Sabía que MNIST era simple, pero no imaginaba que tanto; si compartieras el fragmento de código que usaste, sería realmente útil como línea base.
    En lo personal me interesa el entrenamiento rápido en CIFAR10, así que este enfoque parece poder ser bastante útil también en otros dominios.
  • La implementación de métodos de kernel de ben recht llega a 98% en 10 líneas.
    https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
  • También probé compresión PNG y en la práctica fue un poco mejor: PNG logró cerca de 83% de precisión en aprox. 15.1 s.
    También probé zstandard, y Zstd(level=3) fue mucho más rápido que gzip, con aprox. 88% de precisión en 3.5 s.
    Al calcular Cx1x2, si se usa (x1-x2)*2 en vez de x1+x2, zstd sube hasta 93% de precisión.
    Si en vez de sumar los dos arreglos se apilan uno encima del otro, el rendimiento se destruye por completo y cae por debajo de 20%, pero es interesante porque en clasificación de cadenas parece que ese método funciona bien.
  • El enfoque con gzip es genial, pero al final parece producir menor rendimiento con más pasos.

• Comparado con otras técnicas, Linear SVC ronda el 92%, SVC con kernel RBF el 96.4%, SVC con kernel polinómico el 94.5%, regresión logística el 89% y Naive Bayes alrededor del 81%.
  Fuente: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
  Por lo que se ve en artículos en línea, solo con K-NN parecen posibles resultados mucho mejores, así que quizás el autor se complicó más el trabajo al usar gzip.

  • Mucha gente no sabe que la regresión logística puede lograr alrededor de 90% de precisión en MNIST.
    Me gusta empezar con modelos simples y agregar complejidad después, pero muchas veces escuché “la regresión logística no sirve” incluso en problemas donde en realidad funcionaría bien.
    Cuando se pregunta qué rendimiento base esperarían en MNIST, muchos estiman 20~30%.
    Incluso quienes hacen machine learning suelen subestimar lo rápido que aparece el rendimiento decreciente al aumentar mucho la complejidad del modelo.
    En muchos casos, si el rendimiento no era bueno con un modelo simple, también era difícil obtener un rendimiento excelente con un modelo más complejo.
  • Ese blog no muestra el mejor rendimiento de vanguardia, sino que más bien compara implementaciones de SVM relativamente simples.
    El paper original que presentó el dataset MNIST también logró alrededor de 98% de precisión, y las redes neuronales actuales llegan hasta 99.87%.
    https://paperswithcode.com/sota/image-classification-on-mnis...
  • El punto no es hacerlo mejor, sino mostrar que incluso después de la compresión queda información suficiente para obtener una señal fuerte.
    La compresión está pensada justamente para hacer más difícil el problema original, y de hecho sigue funcionando así.
  • Es genial que esto funcione, pero como MNIST se volvió demasiado fácil, ojalá ya dejen de usarlo como benchmark.
  • En cierto sentido, hay un algoritmo de compresión más óptimo para la relación entre las entradas y salidas de MNIST.
    Otros modelos tienden a agregar ruido en algún punto, así que me pregunto qué pasaría si se incorporara ingeniería de características antes de gzip.
    Por ejemplo, parece posible aplicar primero desenfoque gaussiano y convoluciones, y luego usar deep learning para la selección de características.

• El código puede ser elegante y breve, pero 78% de precisión en MNIST es bastante malo.
  Incluso un modelo dummy hecho con TensorFlow llega fácilmente a 90% de precisión, y el mejor modelo alcanza 99.87%.
  Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

  • Creo que el artículo enfatiza el punto equivocado.
    Lo interesante es que se puede usar compresión para clasificar incluso sin entrenar un modelo.
    Eso lleva a preguntarse si también pueden usarse otras métricas de teoría de la información más baratas y con pérdida.
    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\)*
  • El objetivo no es escribir código “elegante y breve”, sino mostrar una curiosidad interesante; hacerlo en 10 líneas es más bien un desafío adicional.
    Lo interesante no es si GZip alcanza el mejor rendimiento de vanguardia, sino el hecho de que clasifique medianamente bien.
    Es parecido a que lo sorprendente no sea que un oso reproduzca perfectamente a Mozart, sino que pueda tocar el piano.
  • No es un intento de romper récords, sino un ejemplo que muestra un aspecto interesante de la compresión.
    Aun así, es 8 veces mejor que la línea base y muestra que la compresión puede aprender representaciones.

• Si se cambia compute_ncd por distancia euclidiana, la precisión en pruebas sube 15 puntos porcentuales y también se reduce mucho el cómputo.
  Basta con cambiarlo a algo como distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths]

• De los libros que tratan la conexión profunda entre teoría de la información, compresión y algoritmos de aprendizaje, MacKay fue el mejor.
  Para gente con formación formal quizá sea conocimiento común, pero como alguien que aprendió machine learning práctico de forma autodidacta, ver cómo este tema se conectaba incluso con campos como la física de partículas y la cosmología me produjo un intenso momento de “¡ajá!”.
  Lo dejo con la esperanza de que al menos una persona llegue a la misma revelación.

  • Puse a MacKay en mi lista de pendientes.
    Me impresionó bastante enterarme de que la compresión Lempel-Ziv original, una de las bases de gzip, no surgió simplemente como un intento de reducir tamaño, sino del estudio de la “complejidad de secuencias finitas”.
    https://ieeexplore.ieee.org/document/1055501

• Para ser justos, MNIST queda casi perfectamente separado con solo pasarlo por UMAP.
  Hoy en día creo que hay que esforzarse bastante para tener mal desempeño en MNIST.
  https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
  Creo que ya sería mejor retirar este dataset, y que datasets como QuickDraw tienen mucho más sentido.

  • Como autor, estoy totalmente de acuerdo.
    No creo que sea un gran logro por sí mismo, pero igual es interesante ver que funciona.
    Cuando llegue a casa agregaré al artículo que resolver MNIST es relativamente fácil.
  • Desde el punto de vista de investigación, MNIST es básicamente un problema resuelto, y creo que el desempeño actual ya es mejor que el humano.
    Aun así, como la mayoría de los algoritmos simples y razonables llegan a 97% de precisión, sigue teniendo valor como herramienta educativa o como dataset Hello world.
    Incluso si construyes las herramientas desde cero, tiene el tamaño adecuado para una tarea, y es un problema útil que cualquiera puede entender, como “reconocer dígitos del correo”.
  • gzip no es “algo moderno”; es una tecnología mucho más antigua que UMAP e incluso que el propio MNIST.
    Si entiendes la compresión, este enfoque también es una idea muy simple, así que podría haberse escrito el primer día en que se publicó MNIST y aun así habría obtenido 78% de precisión.
    Eso me parece bastante sorprendente.
  • Casi hace quedar bien a la persona grosera que se quejaba de las siglas.
    El repositorio tampoco define UMAP, pero si le creemos a ChatGPT, UMAP significa Uniform Manifold Approximation and Projection, y es una técnica de reducción de dimensionalidad y visualización usada en machine learning y análisis de datos.

• Este campo lo manejo solo a nivel de hobby, pero supongo que los datos fuertemente comprimidos tienen alta entropía, como los datos cifrados.
  Si se encuentran patrones en los datos comprimidos para identificar el dígito original, ¿no se deberían poder usar esos patrones para lograr una mejor compresión?

  • Esta demostración no clasifica mirando los datos comprimidos, sino según qué tan bien se comprimen los datos.
    La idea es que “7 7” debería comprimirse mejor que “7 3”, y que una imagen raster de “7 7” también se comprimirá mejor que una de “7 3”.
  • Los datos cifrados ideales deberían ser incompresibles.
    La incompresibilidad es una característica de las operaciones criptográficas eficientes.
    Ver la sección de compresión del artículo sobre complejidad de Kolmogorov: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
    Uno de los conceptos que me gustan de la compresión es el principio del palomar, que dice que para todo algoritmo de compresión necesariamente existen salidas más grandes que sus entradas.
    También se puede intentar comprimir una carga útil cifrada bien diseñada, pero en promedio la salida será más grande que la entrada y la compresión se volverá inútil; por eso se la llama “incompresible”.
    https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

• Creo que hace unos años hubo un caso en el que se usaba el tamaño de las imágenes de MNIST como una “metacaracterística”, pero no logro encontrarlo enseguida.
  Recuerdo que, sin siquiera mirar la imagen, solo con esa característica se obtenía una precisión de alrededor del 90%.

  • Hace unos años hice un proyecto para generar huellas digitales de capturas de pantalla de páginas web, y solo con el tamaño de la imagen comprimida funcionaba tan bien como cierto método de huella digital para comparar similitud entre capturas.
  • Me da curiosidad qué significa “tamaño” aquí.
    ¿El tamaño comprimido con gzip? Si solo miras qué tan oscura es una imagen de MNIST, es decir, la proporción de píxeles oscuros, se obtiene alrededor de 20% de precisión, que es el doble de adivinar al azar, pero está muy lejos de 90%.

• Sospecho que los autores de ese paper cometieron un error y por eso los resultados saltaron a los primeros puestos del benchmark.
  Después de ese episodio pensé que la teoría no era consistente, pero aun así 78% de precisión solo con GZIP es impresionante.

  • Probablemente estás pensando en este artículo: https://kenschutte.com/gzip-knn-paper/
  • Esto es 78% de precisión usando distancia de compresión basada en Gzip y KNN, así que parece peor que casi cualquier otra métrica de distancia que se te pueda ocurrir combinada con KNN.

• Más allá de si este problema es una buena aplicación para trucos de compresión, quienes experimentan deberían dejar de usar gzip y usar zlib.
  Si cambian la primera línea de gzip.compress a zlib.compress, obtendrán el mismo desempeño de clasificación con una velocidad 3 veces mayor.