Gzip e KNN superam Transformers em classificação de texto

 (twitter.com/LukeGessler)
2 pontos por GN⁺ 2023-07-15 | 1 comentários | Compartilhar no WhatsApp
  • Proposto um método não paramétrico de classificação de texto que combina um compressor simples como gzip com um classificador k-vizinhos mais próximos (kNN)
  • Sem nenhum parâmetro de treinamento, ele ainda é leve e genérico, com menor custo computacional que DNNs
  • Em comparação com métodos de deep learning sem pré-treinamento, obteve resultados competitivos em 6 datasets in-distribution
  • Superou o BERT em todos os 5 datasets OOD (out-of-distribution), incluindo 4 idiomas de poucos recursos
  • Também apresentou ótimo desempenho em cenários few-shot, nos quais é difícil treinar DNNs por falta de dados rotulados

Contexto e problema

  • DNNs são amplamente usadas em classificação de texto devido à alta precisão
  • Porém, exigem milhões de parâmetros e grande volume de dados rotulados, o que eleva o custo computacional
  • Por isso, seu uso, otimização e a transferência para cenários OOD (out-of-distribution) acabam sendo tarefas caras na prática

Método proposto

  • Como alternativa às DNNs, é apresentado um método não paramétrico simples, leve e genérico
  • A estrutura combina um compressor simples como gzip com um classificador k-vizinhos mais próximos
  • A principal característica é ter zero parâmetros de treinamento

Resultados experimentais

  • Em 6 datasets in-distribution, alcançou desempenho competitivo em relação a métodos de deep learning sem pré-treinamento
  • Superou o BERT em todos os 5 datasets OOD, incluindo 4 idiomas de poucos recursos
  • Também se destacou em cenários few-shot, nos quais há dados rotulados insuficientes para treinar DNNs de forma eficaz

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-15
Comentários do Hacker News

  • Link direto para o artigo: https://aclanthology.org/2023.findings-acl.426.pdf
    Intuitivamente, a ideia central é que, se temos os documentos x1, x2 e um novo documento x, então, se a regularidade estatística de x estiver mais próxima de x1 do que de x2, teremos len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)). Aqui, cat significa concatenação e compress é um compressor como o gzip.
    Em termos literais, len(compress(cat(x1,x))) - len(compress(x)) é o número adicional de bytes necessário para comprimir a regularidade estatística de x1 dado o padrão estatístico de x. Quanto mais parecidos forem x1 e x, menor será o número de bytes extras necessários para comprimir cat(x1,x) em comparação com comprimir apenas x.
    Os autores usam uma função de distância chamada distância de compressão normalizada (NCD), baseada nessa ideia, e aplicam k-vizinhos mais próximos (kNN) aos documentos comprimidos. Também discutem a relação entre NCD, informação, entropia de Shannon e complexidade de Kolmogorov.
    Surpreendentemente, esse método simples e intuitivo supera o BERT em várias tarefas de classificação zero-shot. Mas isso não significa necessariamente que ele vença Transformers maiores e mais modernos.

    • Esse método só se sai melhor em dados fora da distribuição e quando há sobreposição de tokens. Ele não tem capacidade de entendimento semântico; o resultado pode estar certo, mas o título induz ao erro.
    • Fico curioso se daria para obter resultados um pouco melhores usando o suporte a dicionário de compressão do zstd em vez de simplesmente concatenar documentos.
      A ideia seria comparar o tamanho comprimido do documento com e sem usar o outro documento como dicionário de compressão. O zstd, pelo menos em níveis 20+, alcança taxas de compressão muito maiores que o gzip, então, se o motivo de funcionar bem com gzip for a aproximação da complexidade de Kolmogorov, talvez funcione ainda melhor.
    • Se o problema a ser resolvido é, no fim das contas, “x é mais parecido com x1 ou com x2?”, isso parece diferente do problema que um LLM resolve, então não seria surpreendente que se saísse melhor.
      Se x1 estivesse em inglês e x fosse a tradução em hebraico do mesmo documento, imagino que um LLM se sairia melhor.
    • Tecnicamente, isso não é zero-shot, e sim few-shot. Ainda é necessário um conjunto de protótipos de treinamento que sirva como referência.
    • Fico pensando se a mesma abordagem funcionaria para imagens.
      Recentemente estive lidando com imagens e gerando JPEGs, e é interessante como imagens muito diferentes podem surgir a partir dos mesmos pixels básicos. Quanto mais ruidosa e aleatória a imagem, maior tende a ser o tamanho do arquivo JPG; por outro lado, quanto mais ela parece uma fotografia, menor tende a ser o tamanho do JPG.

  • Se você tem interesse na equivalência entre IA e compressão, vale a pena ver o Hutter Prize :) http://prize.hutter1.net/
    O Large Text Compression Benchmark também vale a visita http://mattmahoney.net/dc/text.html - atualmente, o melhor compressor do mundo é uma rede neural do famoso Fabrice Bellard, criador do ffmpeg e do QEMU.
    Também gosto muito do estilo somente texto apropriado dessas páginas.

    • Em especial, algoritmos de compressão baseados em codificação aritmética, que ajustam os pesos dos intervalos prevendo o que vem a seguir, são muito parecidos.
      Eles ajustam a codificação aritmética (https://en.wikipedia.org/wiki/Arithmetic_coding) de acordo com o contexto do byte/bit a ser previsto, então, quanto mais precisamente se prevê o que vem na sequência, mais eficiente a codificação se torna. A tarefa em si é muito parecida com a de um Transformer como o GPT.
      Uma previsão perfeita faz com que o intervalo aritmético não encolha, então quase não há custo adicional de armazenamento e, portanto, nenhum bit precisa ser armazenado. Mas, para fazer um benchmark justo, é preciso contabilizar também o tamanho do descompressor.
    • Quando se aprofunda na matemática, muita coisa acaba sendo fundamentalmente a mesma. Super-resolução é deconvolução com uma boa embalagem, um perceptron de camada única é um SVM de kernel linear e também uma regressão logística, e FFT é apenas fatoração.
    • É importante que os autores usem a distância de compressão normalizada (NCD). A NCD é uma forma de aproximar a complexidade de Kolmogorov.
      É uma ideia bem antiga; veja [1,2]. Antiga, mas ainda muito útil, como o perceptron.
      [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
      [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
    • Fabrice Bellard é realmente uma lenda viva. Dá para acrescentar QuickJS, jslinux, tcc e TinyGL à lista também.
    • Esse tipo de “compressão” é, em essência, mais próximo de compreensão por meio de teoria, como em teorias da física.
      Uma teoria se parece com uma história que explica muita coisa com os mesmos “personagens”. Aqui, os personagens são mais próximos de conceitos; um exemplo disso seriam os átomos.

  • Quero destacar que essa abordagem mais forte é limitada a notícias.
    No Yahoo Questions ela não é a melhor. Não parece absurdo pensar que notícias são escritas de maneira semelhante e às vezes até têm trechos copiados, então existe muita sobreposição de palavras.
    O Yahoo Questions é um fórum, então provavelmente há mais variação de palavras, mas ainda existe similaridade semântica entre elas.
    Ou seja, o gzip é forte quando há muita sobreposição lexical (o aumento de tamanho durante a compressão com gzip é pequeno), e, quando a similaridade semântica importa, DNNs sempre vencem.
    Os resultados são interessantes, mas talvez não tão interessantes quanto parecem à primeira vista.

    • Se a similaridade semântica é diferente, como isso funcionaria? Parece que, durante o treinamento, trata-se apenas de agrupar expressões semanticamente parecidas.

  • É muito importante notar que esse resultado veio de dados fora de distribuição. Por exemplo, são notícias em idiomas como “Kinyarwanda, Kirundi, Pinyin”
    Em cenários mais gerais, o BERT ainda vence com folga
    É legal ver que um método tão simples pode ser muito eficaz, mas não dá para vender isso de forma exagerada

    • Esse ponto realmente deveria ser mais enfatizado. Quando li só o título, pareceu surpreendente, como se alguém tivesse encontrado por acaso evidências de uma lei física antes desconhecida e ainda não explicada, neste caso uma lei da linguística
      Mas, olhando as condições citadas, na verdade isso é bem intuitivo. O que significa classificar texto em um idioma totalmente desconhecido? Se te pedirem para classificar um texto em Kirundi, você não entende absolutamente nada do significado, e o melhor que pode fazer é procurar frequências de palavras ou sequências de caracteres e agrupar textos com impressões digitais de frequência parecidas
      Você continua sem saber o significado real, mas ainda pode ir melhor que o aleatório, e de fato vai. A boa notícia é que é exatamente isso que o gzip+kNN faz, é a especialidade deles e a razão de existirem
      Tentar ler e entender esse texto ou prever o próximo caractere não traz muito benefício. Uma pessoa normal nem tentaria isso, porque não conhece o idioma. Infelizmente, é exatamente isso que o BERT faz. É a única coisa que o BERT sabe fazer. Ainda assim, parabéns por ter conseguido extrair mais utilidade dele do que um humano comum, talvez até do que um humano incomum

  • Na prática, isso é muito inteligente e intuitivo
    Se você juntar dois trechos de texto parecidos, eles vão comprimir melhor do que dois trechos diferentes colados um no outro

    • É uma técnica conhecida, embora não muito conhecida. A principal contribuição aqui é a formalização e medição

  • Isso me parece menos uma vitória desse método e mais um sinal negativo sobre similaridade baseada em deep learning
    Em meio à febre das LLMs, é verdade que as LLMs são impressionantes, mas muita gente parece assumir que houve avanços parecidos também na camada de embeddings para similaridade textual pura
    Daí surgiu todo tipo de boom de bancos de dados de embeddings, mas, pelo que vejo, há pouquíssimas evidências que sustentem isso

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

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      Fato curioso: a similaridade entre consulta e documento foi tratada não com vetores, mas com TF-IDF simples. Quando o número de documentos recuperados passava de 45, isso funcionava melhor do que busca vetorial, e na prática usaram 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.

    • Alguém pode responder só uma pergunta? Ao criar embeddings de texto com uma LLM para usar em medição de similaridade, qual camada se usa? A camada de entrada? A camada de entrada + codificação posicional? Uma camada oculta? A camada de saída?

  • O link deveria apontar para o PDF do artigo: https://aclanthology.org/2023.findings-acl.426.pdf

  • Algoritmos de compressão são sobre economia/compressão de espaço, isto é, de bits e bytes. Modelos de aprendizado de máquina, especialmente modelos generativos, são sobre economizar/comprimir expressão e pensamento humanos
    Classificação de texto é um tipo de compressão sobre a expressão humana. Será que existe alguma propriedade fundamental da linguagem humana e dos dados que explique qual dos dois tende a se sair melhor em tarefas de aprendizado de máquina?
    Se um dia uma teoria assim tomar forma, talvez não seja surpreendente que a codificação de bits/bytes comprimidos e a expressão humana comprimida sejam intimamente relacionadas em algum espaço, de modo que as duas estejam conectadas de alguma maneira. Na verdade, esse tipo de teoria, por exemplo uma teoria baseada em entropia ou em física, poderia ajudar a decidir se, em certos tipos de compressão da expressão humana, vale mais usar algoritmos de compressão ou modelos de aprendizado de máquina
    Olhando do ponto de vista dos dados, quais seriam os exemplos negativos difíceis que tornam esses algoritmos ruins? Por enquanto, talvez só dê para aproximar essa teoria em termos dos tipos de dados textuais humanos. Por exemplo, prever mistura com modelos estatísticos de tópicos funciona bem em texto acadêmico, mas tem dificuldades com texto da internet
    Será que há alguém estudando esse tipo de teoria além do Wolfram Physics?

  • Faz total sentido. Compressão é sobre “entendimento”, isto é, representar a entrada de uma forma que possa ser reconhecida e rotulada
    Se os bits reconhecidos passam a ser maiores que o rótulo, pronto, houve compressão. Não me surpreende que o gzip possa ser melhor nisso do que uma DNN

    • Nesse caso, fico curioso se outros algoritmos de compressão poderiam se sair ainda melhor
    • Eu veria compressão como um subconjunto de entendimento. Quando uma criança começa a falar de forma gramaticalmente correta, ela comprimiu todos os padrões linguísticos aos quais foi exposta em regras gramaticais
      Eu digo subconjunto porque entendimento é mais geral. Um algoritmo de compressão específico pode funcionar bem com números de ponto flutuante. Já o cérebro e as redes neurais artificiais, mesmo com desempenho pior, talvez consigam comprimir qualquer tipo de padrão de entrada

  • Não entendo como o gzip conseguiria lidar com palavras como “not”, que invertem o significado de uma frase inteira
    Alguém entende?

    • Como também aparece em alguns comentários no Twitter, isso é para modelagem de tópicos. Palavras de negação podem ser menos importantes aqui do que em tarefas como análise de sentimento