¿Por qué no cuadraban las cifras del paper "gzip beats BERT"?

 (kenschutte.com)
1 puntos por GN⁺ 2023-07-18 | 1 comentarios | Compartir por WhatsApp
  • Es posible que el rendimiento del clasificador kNN basado en gzip que llamó la atención en el paper de clasificación de texto “Low-Resource” de Jiang et al. no se haya calculado como una precisión kNN convencional, sino de una forma cercana a top-2 con k=2
  • En calc_acc dentro del repositorio oficial, si entre los candidatos empatados hay хотя бы una etiqueta correcta, se cuenta como acierto, por lo que se considera éxito incluso si solo una de las dos muestras de entrenamiento más cercanas coincide
  • Al recalcular la columna “Full” de los primeros 4 datasets, cambian varias cifras, y en KirundiNews el método gzip pasa del mejor rendimiento al peor
  • En una reimplementación aparte, la salida del código oficial siempre coincidió con top2, y si el empate con k=2 se resuelve priorizando la muestra más cercana, el resultado termina siendo en la práctica igual a k=1
  • La opción rand==True rompe empates con random.choice, pero parece no haberse usado en los resultados del paper; SogouNews todavía no se ha ejecutado por el tamaño de los datos

Problema en el cálculo de precisión detectado al reproducir los resultados del paper

  • El objetivo es “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors de Jiang et al., cuyo cuadro mostrando que el método basado en gzip superaba a varios métodos basados en redes neuronales llamó la atención en Twitter
  • Durante el proceso de reproducir el código fuente oficial, se confirmó que el método de cálculo de precisión del clasificador kNN funciona de forma distinta a la habitual
  • En particular, con k=2 se parece más a una precisión top-2 que a una precisión kNN normal (k=2), lo que puede inflar el rendimiento del método del paper

Por qué el empate es un problema en kNN con k=2

  • El método del paper usa un clasificador kNN y, según el Appendix C, en todos los experimentos se usa k=2
  • La clasificación con k=2 busca las 2 muestras de entrenamiento más cercanas para cada muestra de prueba, así que la situación de etiquetas es simple
    • Si las dos etiquetas son iguales, se predice esa etiqueta y, en la práctica, se obtiene la misma respuesta que con k=1
    • Si las dos etiquetas son distintas, aparece un empate 1:1, por lo que hace falta una regla adicional para desempatar, como priorizar la muestra más cercana
  • Si el empate se rompe al azar, en la mitad de los empates 1:1 se elegirá la muestra más lejana, así que difícilmente mejorará frente a k=1

Cómo calc_acc maneja los empates

  • El punto problemático es el método calc_acc de experiments.py
  • El flujo del código reúne en sorted_pred_lab las etiquetas y conteos de las muestras top-k, luego las agrupa por etiqueta y las ordena según el conteo
  • Recorre las etiquetas empatadas con el conteo más alto y, si al menos una coincide con la etiqueta de prueba, establece if_right = 1, por lo que se cuenta como correcta
  • Cuando k=2 y dos etiquetas distintas reciben 1 voto cada una, en la práctica solo se comprueba si una de las dos candidatas es la correcta
  • El resultado se parece a la precisión top-k de ImageNet, pero aquí la diferencia es que el criterio no son k etiquetas seleccionadas sino k muestras de entrenamiento
  • El método acepta cualquier k, pero no calcula top-k en todos los casos; con k=2 aparece una situación especial donde todos los candidatos quedan agrupados con conteo máximo 1
  • calc_acc tiene un flag rand, y cuando rand==True rompe empates con random.choice, pero parece que no se usó en los resultados del paper

Cambios en la precisión recalculada

  • En la columna “Full” de los primeros 4 datasets, las cifras del paper y las cifras corregidas de knn2d quedan así
Categoría KinyarwandaNews KirundiNews DengueFilipino SwahiliNews
Paper 0.891 0.905 0.998 0.927
Corregido knn2d 0.835 0.858 0.999 0.850
  • El quinto dataset, SogouNews, todavía no se ha ejecutado porque es grande
  • Esta diferencia cambia bastante la interpretación del experimento y, en KirundiNews, el método gzip pasa del mejor rendimiento al peor

Resultados confirmados con una implementación aparte

  • La implementación separada usa dos estrategias de desempate
    • r: selección aleatoria
    • d: reducir k hasta que desaparezca el empate
  • Los resultados de la reimplementación son los siguientes
Método kinnews kirnews filipino swahili Descripción
table5 0.891 0.905 0.998 0.927 cifras de la tabla del paper
code 0.891 0.906 1.000 0.927 usando el repositorio npc_gzip
top2 0.891 0.906 1.000 0.927 top-2
knn1r 0.835 0.858 0.999 0.850 kNN, k=1, empate aleatorio
knn1d 0.835 0.858 0.999 0.850 kNN, k=1, reducir k si hay empate
knn2r 0.828 0.807 0.851 0.842 kNN, k=2, empate aleatorio
knn3r 0.838 0.791 0.851 0.881 kNN, k=3, empate aleatorio
knn2d 0.835 0.858 0.999 0.850 kNN, k=2, reducir k si hay empate
knn3d 0.843 0.794 0.904 0.883 kNN, k=3, reducir k si hay empate
  • La verificación cruzada muestra qué calculó realmente el código oficial
    • table5 está muy cerca de code, con diferencias de apenas 0.001 o 0.002, así que las cifras del paper pueden reproducirse
    • code siempre coincide con top2, así que el resultado del código oficial coincide con el resultado top-2 de la implementación aparte
    • knn1r == knn1d, y con k=1 no aparecen empates
    • knn2d == knn1d, y al resolver el empate de k=2 con la primera muestra, termina siendo igual a k=1
    • knn2r < knn2d, y en el empate 1:1 de k=2 la selección aleatoria elige la muestra más lejana en la mitad de los casos

Puntos que siguen pendientes de confirmar

  • Una nueva reimplementación que incluye más valores de k está en gzip-knn
  • La razón por la que DengueFilipino da valores muy altos, como 1.0 en algunos casos, se trata en una publicación posterior, Part 2
  • La razón exacta de la pequeña diferencia entre table5 y code en dos casos todavía queda pendiente

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-18
Opiniones en Hacker News

  • Seguro será decepcionante para los autores, pero me parece una gran refutación
    En machine learning es realmente fácil cometer este tipo de errores, y lo peor es que fallas metodológicas sutiles no suelen manifestarse como fracasos fatales, como en otras ramas de la ingeniería o la ciencia, sino como cambios sutiles en el rendimiento
    Aunque datos malos se mezclen en el conjunto de entrenamiento o se filtre información del objetivo, el sistema más o menos sigue funcionando y el resultado solo queda ligeramente contaminado
    Aplicar algoritmos de compresión existentes al machine learning, a diferencia de lo que uno esperaría, se siente demasiado como un almuerzo gratis. Si hubiera una magia especial en los algoritmos de compresión, se habrían usado como codificadores en vez de usar transformadores como compresores

    • Este punto hay que recordarlo siempre. Como equivocarse es fácil, es común, y la ciencia es un proceso ruidoso, pero dentro de ese ruido también hay señal, y lo que estamos viendo aquí es precisamente la esencia de la revisión por pares
      Por eso suelo decir que la publicación abierta es una mejor forma de revisión por pares que las conferencias o las revistas. La revisión por pares consiste en que colegas revisen mi trabajo; lo central no son los criterios arbitrarios y ruidosos que imponen conferencias o revistas
      Durante la mayor parte de la historia funcionó así, y la revisión por pares en el sentido moderno es una idea bastante reciente, de mediados de los años 70. Las revistas de antes se parecían más a la función de difusión de investigación que hoy cumple arXiv
      https://mitcommlab.mit.edu/broad/commkit/peer-review-a-histo...
      Otra razón para deshacerse de conferencias y revistas es que así se podría fomentar activamente trabajo importante como artículos de replicación y artículos de resultados negativos. No haría falta estar atado al criterio de “novedad”, y en realidad casi toda la investigación es incremental
      “Publicar” consiste en comunicar mi trabajo a mis pares y permitir que ellos validen o refuten los resultados
      Eso sí, me gusta que las conferencias reúnan gente y faciliten la colaboración. Lo que critico aquí es usarlas como medio para juzgar la validez de la investigación
      Si el sistema de conferencias fuera solo un espacio para invitar investigación y comunidad, no habría ningún problema. Las revistas también son valiosas en teoría porque hay diálogo entre autores y revisores, pero creo que eso también se puede lograr fácilmente con arxiv + github u OpenReview
    • Ese enfoque ya se está usando. Basta con buscar el principio de longitud mínima de descripción y clasificadores basados en entropía
      El rendimiento no es bueno, pero claramente existen y además son muy fáciles de desplegar. Como textos similares tienden a comprimirse mejor, he visto usar gzip para detección de plagio
      También se puede usar la tasa de compresión como peso en un modelo de resortes para visualización, y aplicarlo a metadatos de comunicaciones de red
    • En muchos experimentos eso es cierto. El deseo de obtener el resultado que uno quiere fácilmente supera la necesidad de verificar lo que realmente se obtuvo
      Sobre todo cuando el resultado confirma lo que uno ya pensaba
    • Últimamente he estado estudiando mucho machine learning y veo este patrón con frecuencia. Como ingeniero de software, es otro aspecto que se siente como lo opuesto a casi todo lo que he hecho
      Si falta un punto y coma, el error aparece de inmediato
      Pero incluso si calculas mal el gradiente de una de tres capas, a veces igual puede funcionar. Solo que el resultado sale raro
    • El código de investigación académica suele ser código desastroso escrito por amateurs lo más rápido posible, casi sin pruebas, y cuyo principal producto es acumular citas de artículos
      Un mundo con la mitad de papers y el doble de cuidado generaría muchísimo más valor, pero todo el sistema está tristemente gameificado

  • Soy la persona que escribió esta entrada de blog. Tengo bastante confianza en lo que puse aquí, pero si se me escapó algo, quizá los autores tengan que explicarlo directamente
    Acabo de abrir un issue en GitHub: https://github.com/bazingagin/npc_gzip/issues/3

    • Tal vez valdría la pena considerar agregar una nota al principio del texto. Mucha gente parece leer el título por encima y quedarse con “el paper de gzip es una basura y el enfoque con gzip no sirve”, cuando en realidad parece más cercano a “el enfoque con gzip no supera a los modelos de redes neuronales profundas, pero en general es competitivo y cuesta mucho menos ejecutarlo”
      El paper en sí sigue siendo sólido
    • Soy el primer autor del paper y leí la entrada del blog. Elegí k=2 porque se recomendaba usar n^{1/2}, y quería escoger un k que encajara con la configuración de 5-shot
      Pero sí, es cierto que esa elección resulta algo extraña. Como dije en el paper y en Twitter, los resultados cambian según el valor de k, y lo que reportamos fue el mejor resultado que se podía obtener, así que representa una situación ideal en la que la predicción siempre acierta
      Usamos la misma estrategia para W2V y SentBERT. Pero eso no significa que sea exactitud top-2. Hasta donde sé, la exactitud top-2 da el punto si una de las dos clases predichas con mayor puntaje es correcta
      Pero, como señalaste, en kNN con k=2 puede darse el caso de que los dos vecinos más cercanos apunten a la misma clase, y si en ese caso reportas exactitud top-2, estarías perdiendo otro posible candidato de clase
      Cuando tenga tiempo y suba una nueva versión a arxiv, me gustaría agregar resultados para otras estrategias y otros valores de k. La estrategia de decremento que mencionaste en el blog es realmente buena, y si quieres me gustaría añadirla al repositorio
      Perdón por la respuesta breve y tardía. Todavía no he podido revisar el repositorio. Mañana estoy preparando una revisión del paper, así que cuando termine responderé el issue y lo resolveré
    • Gracias por reproducirlo, es un trabajo importante
      Me pregunto si también reprodujiste la otra tabla de resultados, Table 3
      Si lo entendí bien, cuando solo hay dos clases la exactitud top-2 se vuelve 1, pero a medida que aumenta el número de clases, la diferencia promedio con la exactitud “normal” se va reduciendo. Así que, si el dataset tiene muchas clases, los resultados de Table 3 no deberían cambiar tanto
      De todos modos, una exactitud top-2 de 0.685 en el dataset 20-newsgroups es bastante impresionante para un método que ni siquiera ve los caracteres como caracteres[1]. Y ni hablar de buenas herramientas en las que investigadores de procesamiento de lenguaje natural han invertido años, como tokens, n-gramas y embeddings
      [1] Según entiendo, gzip solo trabaja con secuencias de bits, que no necesariamente están alineadas con palabras, es decir, con límites de bytes
    • Me pregunto si contactaste primero a los autores antes de hacerlo público

  • Cuando hacía experimentos de relevancia de búsqueda en Shopify también cometí muchos errores, así que empatizo con los autores. Yo también he tenido varios errores vergonzosos en público
    Hacia el final de mi etapa en Shopify aprendí que la buena ciencia necesita buena ingeniería de software. Porque es muy fácil equivocarse en demasiados puntos del stack
    Por eso dediqué mucho tiempo a crear software experimental estricto, con muchas pruebas y de alta calidad, para poder confiar en los números y reproducir los experimentos de los demás
    Intentaba evitar métodos de evaluación de una sola vez, y cuando creaba un método nuevo lo agregaba al conjunto de herramientas de evaluación y luego lo probaba para entender qué significaba esa métrica
    Suena obvio, pero por mi experiencia haciendo este tipo de experimentos, por desgracia no es tan común como uno quisiera. Las empresas quieren velocidad, y pensar a fondo en estadística o crear herramientas internas casi nunca se alinea bien con los intereses de arriba

    • La frase “la buena ciencia necesita buena ingeniería de software” es un aspecto positivo de la investigación industrial
      Primero, porque se puede aprovechar más expertise en ingeniería de software, y segundo, porque hay menos incentivos para exagerar afirmaciones. Si dices que algo funciona, se espera que lo pongas en un entorno real de producción

  • Me alegra que se haya publicado esta entrada de blog
    Yo también hago muchísimos proyectos pequeños así, y hasta trabajos como este, que muestran problemas en un paper, muchas veces nunca ven la luz. Normalmente haces un poco de ruido y luego termina enterrado en el disco duro
    Así que gracias por sacarlo a la luz

    • Últimamente empecé a usar Twitter como un blog de bajo costo
      Después de dedicar un día a este tipo de trabajo, normalmente ya no me quedan energías para escribir de verdad una entrada de blog, y da pena. Pero por lo general sí me alcanza para escribir un hilo corto en Twitter

  • Me da mucho gusto ver este resultado. kNN + tareas de clasificación + clasificación basada en pura similitud de texto es una combinación donde es fácil que los resultados se inclinen a favor
    Las reacciones de burla hacia este paper malinterpretan el punto de que el componente de lenguaje natural es crucialmente importante en los embeddings. Frases que comparten palabras suelen clasificarse bien y también funcionan bien con GZIP, así que GZIP sí puede servir como clasificador sustituto
    El milagro de BERT o de los embeddings está en que no hace falta compartir palabras. Por ejemplo, “what is my safe passcode?” coincide fuertemente con “my lockbox pin is 1234”, pero no con “my jewelry is stored safely in the safe”
    Esto también es importante en los LLM. Mucha gente usa embeddings para similitud de texto, cuando en realidad debería usar modelos SBERT entrenados para que haya correlación entre una pregunta y el documento que contiene su respuesta
    Todo el agujero del conejo puede verse en https://www.sbert.net/
    Entrada anterior: Should you use OpenAI's embeddings? Probably not, and here's why. https://iamnotarobot.substack.com/p/should-you-use-openais-e...
    Discusión en HN: https://news.ycombinator.com/item?id=35377935

    • Para ser justos, la tarea original fue elegida deliberadamente como un caso donde un enfoque tipo kNN+compresión tenía probabilidades de funcionar bien, es decir, un entorno fuera de dominio + de pocos recursos
      En esas condiciones, las entradas de entrenamiento pueden ser demasiado escasas como para que un modelo con muchos parámetros aprenda buenos embeddings
      En una configuración tradicional de clasificación dentro del dominio y con grandes volúmenes de datos, es muy poco probable que métodos no paramétricos como la compresión superen a representaciones aprendidas

  • No estaba claro por qué los autores eligieron kNN como clasificador. Si ya habían construido una matriz de distancias, podrían haber convertido la matriz en factores mediante escalamiento multidimensional y luego usar un algoritmo de árboles como xgboost; así probablemente habrían aprovechado mucha más información y obtenido resultados mucho mejores que con kNN
    También podrían haber usado el algoritmo de compresión PAQ, que es mucho mejor que los compresores de la familia LZ. Es posible que esas decisiones hubieran mejorado mucho los resultados y los hubieran llevado a la conclusión original
    Lo bueno de este paper fue que abstrajo el algoritmo de compresión, y eso me hizo pensar qué más se puede hacer con compresión a partir de la relación p(x) ~ K^(-|x|). Aquí K es el tamaño del alfabeto, |x| es la longitud de la cadena x, y se asume una codificación óptima
    Por ejemplo, se me ocurrió que también sería posible hacer una clasificación tradicional agrupando por separado en documentos los factores de cada respuesta, y luego, del mismo modo que en el paper, encontrar el documento que mejor comprima la siguiente muestra para decidir la clase. Sería una especie de clasificación supervisada usando un algoritmo de compresión
    Cuanto más cerca esté el compresor del código óptimo para ese dataset, mejor debería funcionar
    Un enfoque de predicción secuencial también sería igual de simple de implementar
    Fue una sorpresa agradable

  • ¿Alguien puede explicar cómo un algoritmo de compresión puede vencer a un LLM? Suena como comparar el habla con el grafiti
    Siento que la respuesta debe estar por algún lado, pero no estoy familiarizado con la IA y de plano no lo entiendo

    • En general, compresión = modelo + codificación entrópica
      El papel del modelo es predecir qué viene después, y el del codificador entrópico es codificar la diferencia entre la predicción y el siguiente valor real, haciendo que los resultados más probables usen la menor cantidad de bits posible
      Cuanto más preciso sea el modelo, menor será la diferencia entre la realidad y la predicción, y menos bits necesitará el codificador entrópico, así que la compresión mejora
      Un algoritmo de compresión simple tiene un modelo sencillo, algo como “si vi el mismo byte 10 veces, es probable que la 11.ª vez también sea el mismo”. Pero un LLM también puede usarse como modelo, porque eso es lo que hace un LLM: completar texto con la palabra más plausible
      Aquí lo hicieron al revés. En vez de usar un modelo para comprimir, usaron un algoritmo de compresión como si fuera un modelo, con algunos trucos. La idea es tratar como el resultado más probable aquel que el algoritmo de compresión puede codificar con menos bits
      Los autores del artículo original mostraron que, en algunas tareas, un modelo simple extraído de gzip supera a LLM mucho más complejos
    • Un modelo de lenguaje estima la probabilidad de una secuencia de palabras P(w_1, ..., w_n), o de forma equivalente P(palabra | contexto)
      En compresión hay una relación directa, porque a las secuencias de palabras más probables se les deben asignar códigos más cortos. Un método muy conocido para construir esos códigos a partir de probabilidades es la codificación de Huffman
      Esto aplica tanto si usas un modelo de lenguaje estadístico basado en frecuencia de palabras como si usas un LLM para estimar probabilidades. Cuanto mejor sea el modelo de lenguaje, es decir, cuanto menor sea la perplejidad, más corto será el resultado de la compresión
      A la inversa, también puede decirse que un algoritmo de compresión define implícitamente un modelo de lenguaje a través de la longitud de sus códigos. Por ejemplo, está asumiendo que una cadena repetida es más probable que ruido aleatorio
    • La intuición detrás de gzip es esta
      Si comprimes ABC, termina ocupando X bytes. Si luego comprimes ABCABC, no ocupa 2X bytes. Cuanto más parecidas sean las dos cadenas concatenadas, menos bytes se necesitan
      ABCABD será más grande que ABCABC, pero más pequeño que ABCXYZ
      BERT, para los estándares actuales, es un LLM muy pequeño, y también sabemos que rinde peor que los modelos de miles de millones de parámetros que hoy vemos por todos lados
    • La compresión es equivalente a la inteligencia
      https://mattmahoney.net/dc/rationale.html
    • Es una tarea muy limitada. Tomas un documento y lo clasificas en una de, por ejemplo, unas 10 categorías
      Un método como detectar ciertas palabras también puede funcionar bastante bien en algunos casos. Las cosas que se comprimen bien suelen tener subcadenas en común con frecuencia

  • Si esto es cierto, quiero ver cómo la gente que habló con tanta grandilocuencia sobre ese artículo ahora borra discretamente sus huellas
    Estoy viendo especialmente a los influencers de LinkedIn y Twitter
    Si no es cierto, yo quedaré como tonto, pero apenas hojeé el artículo por encima

  • Gzip como clasificador es sorprendentemente bueno, y debería usarse como línea base frente a redes neuronales

  • Por cierto, parece que el blog se quedó detenido en 2022
    La fecha del artículo aparece como 17 de julio de 2022

    • Gracias. Lo corregiré pronto. Esto pasa cuando escribes la fecha a mano...