En clasificación de texto, Gzip y KNN superan a los Transformers.

 (twitter.com/LukeGessler)
2 puntos por GN⁺ 2023-07-15 | 1 comentarios | Compartir por WhatsApp
  • Se propone un método no paramétrico de clasificación de texto que combina un compresor simple como gzip con un clasificador k-vecinos más cercanos (kNN)
  • No tiene ningún parámetro de entrenamiento y, aun así, es ligero y de propósito general, con una menor carga de costo computacional que las DNN
  • Frente a métodos de aprendizaje profundo sin preentrenamiento, logra resultados competitivos en 6 datasets in-distribution
  • Supera a BERT en los 5 datasets OOD (out-of-distribution), incluidos 4 de idiomas de bajos recursos
  • También muestra un gran desempeño en entornos few-shot, donde la escasez de datos etiquetados dificulta entrenar DNN

Contexto y planteamiento del problema

  • Las DNN se usan ampliamente en clasificación de texto por su alta precisión
  • Sin embargo, requieren millones de parámetros y grandes volúmenes de datos etiquetados, por lo que su costo computacional es alto
  • Esto hace que su uso, optimización y la transferencia a escenarios OOD (out-of-distribution) sean tareas costosas en la práctica

Método propuesto

  • Se presenta un método no paramétrico simple, ligero y de propósito general como alternativa a las DNN
  • La estructura combina un compresor simple como gzip con un clasificador k-vecinos más cercanos
  • Su característica clave es que no tiene ningún parámetro de entrenamiento

Resultados experimentales

  • En 6 datasets in-distribution, alcanza un nivel de desempeño competitivo frente a métodos de aprendizaje profundo sin preentrenamiento
  • Supera a BERT en los 5 datasets OOD, incluidos 4 de idiomas de bajos recursos
  • También destaca en entornos few-shot, donde hay tan pocos datos etiquetados que resulta difícil entrenar DNN de forma efectiva

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-15
Comentarios de Hacker News

  • Enlace directo al artículo: https://aclanthology.org/2023.findings-acl.426.pdf
    Intuitivamente, la idea central es que, si tenemos los documentos x1, x2 y un documento nuevo x, entonces si la regularidad estadística de x se parece más a x1 que a x2, se cumple que len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)). Aquí, cat significa concatenar y compress es un compresor como gzip.
    Literalmente, len(compress(cat(x1,x))) - len(compress(x)) es la cantidad adicional de bytes necesaria para comprimir la regularidad estadística de x1 dado que ya se conoce la regularidad estadística de x. Cuanto más parecidos sean x1 y x, menos bytes adicionales se necesitan para comprimir cat(x1,x) que para comprimir solo x.
    Los autores usan una función de distancia llamada distancia de compresión normalizada (NCD) basada en esta idea y aplican k-vecinos más cercanos (kNN) a los documentos comprimidos. También tratan la relación entre NCD, la información, la entropía de Shannon y la complejidad de Kolmogorov.
    Sorprendentemente, este método simple e intuitivo supera a BERT en varias tareas de clasificación zero-shot. Pero eso no significa necesariamente que también supere a Transformers más grandes y modernos.

    • Este método solo funciona mejor en datos fuera de distribución y cuando hay superposición de tokens. No tiene capacidad de comprensión semántica; el resultado es correcto, pero el título lleva a confusión.
    • Me pregunto si se podrían obtener resultados un poco mejores usando el soporte de diccionario de compresión de zstd en lugar de simplemente concatenar documentos.
      La idea sería comparar el tamaño comprimido cuando se usa un documento como diccionario de compresión frente a cuando no se usa. Como zstd, al menos en niveles 20+, logra tasas de compresión mucho mejores que gzip, si la razón por la que gzip funciona bien aquí es que aproxima la complejidad de Kolmogorov, podría funcionar aún mejor.
    • Si el problema que se quiere resolver al final es “¿x se parece más a x1 o a x2?”, esto parece distinto del tipo de problema que resuelve un LLM, así que no sería sorprendente que lo haga mejor.
      Si x1 está en inglés y x es la traducción al hebreo del mismo documento, me da la impresión de que un LLM lo haría mejor.
    • Estrictamente hablando, no es zero-shot sino few-shot. Sigue haciendo falta un conjunto de prototipos de entrenamiento que sirva como referencia.
    • Me pregunto si el mismo enfoque podría aplicarse también a imágenes.
      Hace poco estuve trabajando con imágenes e intentando generar JPEG, y vi que incluso con los mismos píxeles base pueden salir imágenes muy distintas. También es interesante que, cuanto más ruidosa y aleatoria es una imagen, más grande se vuelve el archivo JPG, y al revés, cuanto más parece una foto, más pequeño tiende a ser.

  • Si te interesa la equivalencia entre IA y compresión, vale la pena ver el Hutter Prize :) http://prize.hutter1.net/
    También vale la pena revisar el Large Text Compression Benchmark http://mattmahoney.net/dc/text.html - actualmente el mejor compresor del mundo es una red neuronal de Fabrice Bellard, famoso por haber creado ffmpeg y QEMU.
    También me gusta mucho el estilo solo texto apropiado de estas páginas.

    • En particular, los algoritmos de compresión basados en codificación aritmética que ajustan los pesos de intervalo prediciendo lo que viene a continuación son muy parecidos.
      Como ajustan la codificación aritmética (https://en.wikipedia.org/wiki/Arithmetic_coding) según el contexto del byte/bit que se va a predecir, cuanto más exactamente predigan lo que sigue, más eficiente se vuelve la codificación. La tarea en sí es muy parecida a la de un Transformer como GPT.
      Una predicción perfecta no reduce el intervalo aritmético, así que casi no hay costo adicional de almacenamiento y, por lo tanto, no se guardan bits. Pero para hacer un benchmark justo, también habría que contar el tamaño del descompresor.
    • Si uno se mete a fondo en las matemáticas, muchas cosas terminan siendo básicamente lo mismo. La superresolución es una deconvolución con buena presentación, un perceptrón de una sola capa es un SVM de kernel lineal y también una regresión logística, y la FFT no es más que factorización.
    • Es importante que los autores usen la distancia de compresión normalizada (NCD). NCD es una forma de aproximar la complejidad de Kolmogorov.
      Es una idea bastante antigua; se pueden ver [1,2]. Es vieja, pero sigue siendo muy útil, como el perceptrón.
      [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
      [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
    • Fabrice Bellard de verdad es una leyenda viviente. A esa lista también habría que sumarle QuickJS, jslinux, tcc y TinyGL.
    • Este tipo de “compresión” está esencialmente más cerca de una comprensión mediante teorías, como en la física.
      Una teoría se parece a una historia que explica muchas cosas con los mismos “personajes”. Aquí los personajes se parecen más a conceptos; por ejemplo, los átomos encajan en esa idea.

  • Quiero señalar que este método es más fuerte solo en noticias.
    En Yahoo Questions no logra el mejor rendimiento. No parece forzado pensar que las noticias se escriben de forma parecida y que a veces incluso se copian partes, así que comparten muchas palabras.
    Yahoo Questions es un foro, así que probablemente haya más variación en las palabras, pero sigue habiendo similitud semántica entre ellas.
    O sea, gzip es fuerte cuando hay mucha superposición de palabras (porque el aumento de tamaño al comprimir con gzip es pequeño), y cuando importa la similitud semántica, una DNN siempre gana.
    Los resultados son interesantes, pero no creo que sean tan interesantes como suenan.

    • Si la similitud semántica es distinta, ¿entonces cómo funcionaría eso? Me parece que al final no es más que un problema de agrupar expresiones semánticamente parecidas durante el entrenamiento.

  • Es muy importante notar que este resultado proviene de datos fuera de distribución. Por ejemplo, son noticias en idiomas como “Kinyarwanda, Kirundi, pinyin”.
    En configuraciones más generales, BERT sigue ganando de manera aplastante.
    Es genial que un método tan simple pueda ser muy efectivo, pero no habría que venderlo exagerándolo.

    • Este punto de verdad debería enfatizarse más. Al leer solo el título, sonaba sorprendente, como si por accidente hubieran descubierto evidencia de una ley física antes desconocida y todavía sin explicar, en este caso una ley lingüística.
      Pero viendo las condiciones citadas, en realidad resulta bastante intuitivo. ¿Qué significa clasificar texto de un idioma completamente desconocido? Si te piden clasificar texto en kirundi, no entiendes en absoluto el significado, y lo mejor que puedes hacer es buscar la frecuencia de secuencias de palabras o caracteres y agrupar entre sí los textos que tengan huellas de frecuencia parecidas.
      Sigues sin conocer el significado real, pero puedes hacerlo mejor que al azar, y en efecto eso es lo que pasa. La buena noticia es que eso es exactamente lo que hace gzip+kNN, su trabajo principal y su razón de existir.
      Intentar leer y entender ese texto o predecir el siguiente carácter no aporta mucho. Una persona normal ni siquiera lo intentaría, porque no conoce el idioma. Desafortunadamente, BERT hace exactamente eso. Porque es lo único que sabe hacer. Aun así, hay que felicitarlo por sacarle más provecho que un humano promedio, y quizá incluso que un humano no promedio.

  • En realidad es muy ingenioso y se entiende de forma intuitiva.
    Si unes dos fragmentos de texto parecidos, se van a comprimir mejor que si unes dos fragmentos de texto distintos.

    • Es una técnica conocida, aunque no muy conocida. La contribución principal aquí es la formalización y medición.

  • Esto parece menos una victoria de ese método y más una señal negativa sobre la similitud basada en deep learning.
    En medio del furor por los LLM, está claro que los LLM son impresionantes, pero da la impresión de que mucha gente asume que hubo avances similares también en las capas de embedding para pura similitud de texto.
    De ahí salió el boom de toda clase de bases de datos de embeddings, pero yo veo muy poca evidencia que lo respalde.

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

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      Dato curioso: la similitud consulta-documento se resolvió no con vectores sino con simple TF-IDF. A partir de más de 45 documentos para buscar, rindió mejor que la búsqueda vectorial, y de hecho usaron 50.
      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.

    • ¿Me podrían responder una sola pregunta? Cuando se crean text embeddings con un LLM para medir similitud, ¿qué capa se usa? ¿La capa de entrada? ¿La capa de entrada + positional encoding? ¿La capa oculta? ¿La capa de salida?

  • El enlace debería apuntar al PDF del paper: https://aclanthology.org/2023.findings-acl.426.pdf

  • Un algoritmo de compresión consiste en ahorrar/comprimir espacio, es decir, bits y bytes. Un modelo de machine learning, especialmente uno generativo, consiste en ahorrar/comprimir la expresión y el pensamiento humanos.
    La clasificación de texto es un tipo de compresión sobre la expresión humana. ¿Habrá alguna propiedad fundamental del lenguaje humano y de los datos que explique cuál de los dos debería funcionar mejor en tareas de machine learning?
    Si algún día una teoría así toma forma, quizá no sería sorprendente que la codificación de bits/bytes comprimidos y la expresión humana comprimida estén estrechamente relacionadas en algún espacio, de modo que ambas queden conectadas de alguna manera. De hecho, una teoría así —por ejemplo, una basada en entropía o en física— podría ayudar a elegir si conviene usar un algoritmo de compresión o un modelo de machine learning para cierto tipo de compresión de expresión humana.
    Visto desde los datos, ¿cuáles serían los ejemplos negativos difíciles que hacen que este tipo de algoritmo funcione mal? Por ahora quizá solo podamos aproximar esa teoría desde la perspectiva de los distintos tipos de datos textuales humanos. Por ejemplo, predecir mezclas con modelos estadísticos de temas funciona bien en textos académicos, pero tiene dificultades con texto de internet.
    ¿Alguien está investigando una teoría así aparte de Wolfram Physics?

  • Tiene todo el sentido. La compresión trata sobre “entender”, es decir, representar la entrada de una manera que permita reconocerla y etiquetarla.
    Si los bits reconocidos terminan siendo más pequeños que la etiqueta, listo, hay compresión. No me sorprende que gzip pueda ser mejor que una DNN en esta tarea.

    • Entonces me pregunto si otros algoritmos de compresión podrían hacerlo todavía mejor.
    • Yo vería la compresión como un subconjunto del entendimiento. Cuando un niño empieza a hablar de forma gramaticalmente correcta, ha comprimido todos los patrones del lenguaje a los que estuvo expuesto en reglas gramaticales.
      Digo que es un subconjunto porque el entendimiento es más general. Un algoritmo de compresión específico puede funcionar bien con números de punto flotante. En cambio, el cerebro y las redes neuronales artificiales quizá puedan comprimir cualquier patrón de entrada, aunque su desempeño sea peor.

  • No entiendo cómo gzip podría manejar palabras como “not”, que invierten por completo el significado de una oración.
    ¿Alguien lo entiende?

    • Como también se menciona en algunos comentarios de Twitter, esto es para topic modeling. Las palabras de negación pueden ser menos importantes aquí que en tareas como análisis de sentimiento.