Por que os números do artigo "gzip beats BERT" não batiam?

 (kenschutte.com)
1 pontos por GN⁺ 2023-07-18 | 1 comentários | Compartilhar no WhatsApp
  • O desempenho do classificador kNN baseado em gzip destacado no artigo “Low-Resource” Text Classification, de Jiang et al., pode ter sido calculado não como a acurácia comum de kNN, mas de uma forma próxima de top-2 com k=2
  • No calc_acc de experiments.py do repositório oficial, entre candidatos empatados, se ao menos um rótulo correto estiver presente, conta como acerto, então basta que um dos dois exemplos de treino mais próximos esteja certo para ser considerado sucesso
  • Recalculando a coluna “Full” dos quatro primeiros datasets, vários números mudam, e em KirundiNews o método gzip cai do melhor desempenho para o pior
  • Em uma reimplementação separada, a saída do código oficial foi sempre igual a top2, e resolver o empate de k=2 priorizando a amostra mais próxima acaba produzindo, na prática, o mesmo resultado de k=1
  • A opção rand==True desfaz empates com random.choice, mas aparentemente não foi usada nos resultados do artigo, e o SogouNews ainda não foi executado por causa do tamanho do dataset

Problema no cálculo de acurácia revelado ao reproduzir os resultados do artigo

  • O alvo é “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors, de Jiang et al., cujo método baseado em gzip chamou atenção no Twitter por aparecer com desempenho superior ao de vários métodos baseados em redes neurais
  • No processo de reproduzir o código-fonte oficial, foi identificado um ponto em que o cálculo de acurácia do classificador kNN funciona de forma diferente da abordagem usual
  • Em especial, com k=2, o resultado fica mais próximo de uma acurácia top-2 do que da acurácia normal de kNN (k=2), o que pode inflar o desempenho do método do artigo

Por que o empate em k=2 no kNN é um problema

  • O método do artigo usa um classificador kNN e, segundo o Apêndice C, todos os experimentos usam k=2
  • A classificação com k=2 encontra os 2 exemplos de treino mais próximos para cada amostra de teste, então a situação dos rótulos é simples
    • Se os dois rótulos forem iguais, esse rótulo é previsto, e o resultado acaba sendo igual ao de k=1
    • Se os dois rótulos forem diferentes, surge um empate de 1:1, exigindo uma regra extra de desempate, como priorizar a amostra mais próxima
  • Se o empate for resolvido aleatoriamente, em metade dos empates 1:1 será escolhido o exemplo mais distante, o que dificulta superar k=1

Como calc_acc trata empates

  • O ponto do problema está no método calc_acc em experiments.py
  • O fluxo do código reúne em sorted_pred_lab os rótulos e contagens dos top-k exemplos, agrupa por rótulo e depois ordena pelas contagens
  • Ao percorrer os rótulos empatados com a maior contagem, se qualquer um deles coincidir com o rótulo de teste, if_right = 1 é definido e o caso é contado como acerto
  • Quando k=2 e os dois rótulos diferentes recebem 1 voto cada, isso equivale a verificar apenas se um dos dois candidatos é o rótulo correto
  • O resultado lembra a acurácia top-k usada em ImageNet, mas com a diferença de que aqui o critério se baseia não em k rótulos escolhidos, e sim em k exemplos de treino
  • O método aceita um k arbitrário, mas não calcula top-k para todos os valores; com k=2 surge a situação especial em que todos os candidatos ficam empatados com contagem máxima 1
  • calc_acc tem uma flag rand, e com rand==True o empate é resolvido com random.choice, mas isso aparentemente não foi usado nos resultados do artigo

Mudanças nas acurácias recalculadas

  • Na coluna “Full” dos quatro primeiros datasets, os números do artigo e os valores corrigidos de knn2d ficam assim
Categoria KinyarwandaNews KirundiNews DengueFilipino SwahiliNews
Artigo 0.891 0.905 0.998 0.927
Corrigido knn2d 0.835 0.858 0.999 0.850
  • O quinto dataset, SogouNews, ainda não foi executado por ser grande demais
  • Essa diferença muda bastante a interpretação do experimento, e em KirundiNews o método gzip passa do melhor desempenho para o pior

Resultado confirmado com implementação separada

  • A implementação separada usa duas estratégias de desempate
    • r: escolha aleatória
    • d: reduzir k até que o empate desapareça
  • Os resultados da reimplementação são os seguintes
Método kinnews kirnews filipino swahili Descrição
table5 0.891 0.905 0.998 0.927 valores da tabela do artigo
code 0.891 0.906 1.000 0.927 usando o repositório 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 aleatório
knn1d 0.835 0.858 0.999 0.850 kNN, k=1, reduzir k em caso de empate
knn2r 0.828 0.807 0.851 0.842 kNN, k=2, empate aleatório
knn3r 0.838 0.791 0.851 0.881 kNN, k=3, empate aleatório
knn2d 0.835 0.858 0.999 0.850 kNN, k=2, reduzir k em caso de empate
knn3d 0.843 0.794 0.904 0.883 kNN, k=3, reduzir k em caso de empate
  • A conferência mostra o que o código oficial realmente calculou
    • table5 fica próximo de code, com diferença de até 0.001 ou 0.002, então os números do artigo podem ser reproduzidos
    • code é sempre igual a top2, mostrando que o resultado do código oficial coincide com o resultado top-2 da implementação separada
    • knn1r == knn1d, e com k=1 não há empates
    • knn2d == knn1d, e com k=2 resolver o empate escolhendo a primeira amostra equivale a k=1
    • knn2r < knn2d, e no empate 1:1 de k=2 a escolha aleatória leva, em metade dos casos, à seleção da amostra mais distante

Pontos que ainda precisam ser verificados

  • Uma nova reimplementação com mais valores de k está em gzip-knn
  • O motivo de o DengueFilipino chegar a valores muito altos, como 1.0 em alguns casos, será tratado na Parte 2 de um texto posterior
  • A razão de table5 e code diferirem ligeiramente em dois casos ainda permanece em aberto

Leituras relacionadas

1 comentários

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

  • Deve ser decepcionante para os autores, mas eu vejo isso como uma excelente refutação
    Em machine learning, é muito fácil cometer esse tipo de erro, e o pior é que erros metodológicos sutis normalmente não aparecem como falhas fatais, como em outras áreas de engenharia ou ciência, mas sim como mudanças sutis de desempenho
    Mesmo que dados ruins se misturem ao conjunto de treino ou haja vazamento de informação do alvo, o sistema continua funcionando mais ou menos, e só os resultados ficam levemente contaminados
    Aplicar algoritmos de compressão já existentes ao machine learning parece, ao contrário do esperado, almoço grátis demais. Se houvesse alguma mágica especial nos algoritmos de compressão, teríamos usado algoritmos de compressão como codificadores em vez de usar transformadores como compressores

    • Vale muito a pena lembrar disso. Como erros são fáceis de cometer, eles são comuns, e a ciência é um processo cheio de ruído, mas há sinal no meio disso, e o que estamos vendo aqui é justamente a essência da revisão por pares
      Por isso eu frequentemente argumento que publicação aberta é uma forma melhor de revisão por pares do que conferências e periódicos. Revisão por pares significa que seus pares revisam seu trabalho; o ponto central não são os critérios arbitrários e ruidosos apresentados por conferências ou periódicos
      Durante a maior parte da história foi assim que funcionou, e a revisão por pares no sentido moderno é um conceito bem recente, de meados da década de 1970. Os periódicos antigos eram mais próximos da missão de distribuir pesquisa, como o arxiv faz hoje
      https://mitcommlab.mit.edu/broad/commkit/peer-review-a-histo...
      Outro motivo para defender o fim de conferências e periódicos é que isso permitiria incentivar ativamente trabalhos importantes como artigos de reprodução e artigos sobre fracassos. Não precisaríamos ficar presos ao critério de “novidade”, e na verdade quase toda pesquisa é incremental
      “Publicar” é comunicar seu trabalho aos seus pares e permitir que eles validem ou refutem os resultados
      Dito isso, é bom que conferências reúnam pessoas e promovam colaboração. O que está sendo criticado aqui é o uso de conferências e periódicos como meio de julgar a validade da pesquisa
      Se o sistema de conferências fosse apenas um espaço para convidar pesquisas e a comunidade, não haveria problema algum. Periódicos também, em teoria, são bons por haver diálogo entre autores e revisores, mas eu acho que isso também pode ser feito facilmente com arxiv + github ou OpenReview
    • Isso já é usado dessa forma. Basta procurar pelo princípio do comprimento mínimo de descrição e por classificadores baseados em entropia
      O desempenho é ruim, mas claramente isso existe e a implantação é muito fácil. Textos parecidos tendem a ser melhor comprimidos, então já vi usarem gzip para detecção de plágio
      Também dá para usar a taxa de compressão como peso em modelos de molas para visualização, e isso também pode ser aplicado a metadados de comunicação em rede
    • Isso é verdade em muitos experimentos. O desejo de obter o resultado que você quer facilmente supera a necessidade de verificar o que você realmente obteve
      Especialmente quando o resultado confirma o que você já pensava
    • Tenho estudado bastante machine learning recentemente e vejo esse padrão com frequência. É mais um ponto que parece o oposto de quase tudo que fiz como engenheiro de software
      Se faltar um ponto e vírgula, o erro aparece imediatamente
      Mas, se você errar o cálculo do gradiente em uma das três camadas, às vezes ainda pode funcionar. Só que o resultado fica estranho
    • Código de pesquisa acadêmica em geral é um código bagunçado feito por amadores o mais rápido possível, quase sem testes, e o principal produto desse código é acumular citações de artigos
      Um mundo com metade dos artigos científicos e o dobro de cuidado geraria muito mais valor, mas o sistema inteiro foi gamificado de forma desesperadora

  • Sou a pessoa que escreveu este post no blog. Tenho bastante confiança no que escrevi aqui, mas, se houver algo que eu tenha deixado passar, talvez os autores precisem explicar diretamente
    Acabei de abrir uma issue no GitHub: https://github.com/bazingagin/npc_gzip/issues/3

    • Talvez valha a pena considerar adicionar uma observação no topo do post. Muita gente parece passar os olhos só pelo título e sair com a impressão de que “o artigo do gzip é ruim e a abordagem com gzip não presta”, quando na verdade parece mais algo como “a abordagem com gzip não é melhor que modelos de redes neurais profundas, mas em geral é competitiva e muito mais barata de executar”
      O artigo em si continua sólido
    • Sou o primeiro autor do artigo e li o post do blog. Escolhi k=2 porque foi recomendado usar n^{1/2}, e eu queria escolher um k que combinasse com a configuração 5-shot
      Mas é verdade que essa escolha é um pouco estranha. Como eu disse no artigo e no Twitter, os resultados mudam quando o valor de k muda, e o que reportamos foi o melhor resultado possível, então isso representa uma situação ideal em que a previsão está sempre certa
      Usei a mesma estratégia para W2V e SentBERT. Mas isso não significa acurácia top-2. Até onde eu sei, acurácia top-2 significa dar pontuação quando uma das duas classes previstas no topo está correta
      Porém, como você apontou, no kNN com k=2 pode acontecer de os dois vizinhos mais próximos apontarem para a mesma classe, e nesse caso, se você reportar acurácia top-2, vai deixar de fora uma outra classe candidata
      Quando eu tiver tempo e subir uma nova versão no arxiv, quero adicionar resultados para outras estratégias e outros valores de k. A estratégia de decremento mencionada no blog é realmente boa e, se você quiser, eu gostaria de adicioná-la ao repositório
      Desculpe pela resposta curta e tardia. Ainda não consegui verificar o repositório. Estou me preparando para a revisão do artigo amanhã, então, quando terminar, responderei e resolverei a issue
    • Obrigado por reproduzir isso; é um trabalho importante
      Fico curioso se você também reproduziu a outra tabela de resultados, a Table 3
      Se entendi corretamente, quando há apenas duas classes a acurácia top-2 vira 1, mas, à medida que o número de classes aumenta, a diferença média para a acurácia “normal” vai diminuindo. Então, se o dataset tiver muitas classes, os resultados da Table 3 provavelmente não mudariam tanto assim
      De todo modo, uma acurácia top-2 de 0,685 no dataset 20-newsgroups é bem impressionante para um método que nem sequer trata caracteres como caracteres[1]. Isso sem falar nas boas ferramentas em que pesquisadores de processamento de linguagem natural investiram por anos, como tokens, n-gramas e embeddings
      [1] Pelo que entendo, o gzip lida apenas com sequências de bits, que não estão necessariamente alinhadas a palavras, isto é, a limites de bytes
    • Você tentou entrar em contato com os autores antes de publicar?

  • Quando fazia experimentos de relevância de busca na Shopify, também cometia muitos erros, então tenho empatia pelos autores. Eu também já passei por vários erros constrangedores em público
    Perto do fim da minha passagem pela Shopify, aprendi que boa ciência exige boa engenharia de software. Porque é fácil errar em pontos demais da stack
    Por isso, investi muito tempo em criar software de experimentação rigoroso, bem testado e de alta qualidade, para que fosse possível confiar nos números e reproduzir os experimentos uns dos outros
    Tentei evitar métodos de avaliação de uso único e, quando criava um método novo, eu o adicionava ao conjunto de ferramentas de avaliação e depois o testava para entender o que aquela métrica significava
    Parece óbvio, mas pela minha experiência fazendo esse tipo de experimento, infelizmente isso não é tão comum quanto se gostaria. Empresas querem velocidade, e pensar com profundidade estatística ou construir ferramentas internas na maioria das vezes não se alinha bem com os interesses da chefia

    • A frase “boa ciência exige boa engenharia de software” é um aspecto positivo da pesquisa na indústria
      Primeiro, permite usar mais expertise em engenharia de software e, segundo, cria menos incentivo para exagerar afirmações. Porque, se você diz que funciona, espera-se que coloque em produção de verdade

  • Fico feliz que este post de blog tenha sido publicado
    Eu também faço muitos projetinhos assim e, mesmo trabalhos como este, que mostram problemas em artigos, muitas vezes nunca veem a luz do dia. Normalmente fazem um pouco de barulho por um instante e depois acabam enterrados no disco rígido
    Então, obrigado por colocar isso para fora

    • Hoje em dia comecei a usar o Twitter como um blog de baixo custo
      Depois de passar um dia nisso, normalmente não tenho energia para de fato escrever um post de blog, o que é uma pena. Ainda assim, quase sempre consigo escrever uma thread curta no Twitter

  • Fico realmente muito satisfeito em ver esse resultado. kNN + tarefa de classificação + classificação baseada puramente em similaridade textual é uma combinação em que os resultados tendem facilmente a parecer favoráveis
    A reação de comemoração em torno deste artigo interpreta mal o ponto de que o componente de linguagem natural é crucialmente importante em embeddings. Frases que compartilham palavras tendem a ser bem classificadas e também funcionam bem com GZIP, então GZIP pode ser usado como classificador alternativo
    O milagre do BERT e dos embeddings está em não precisar compartilhar palavras. Por exemplo, “what is my safe passcode?” combina fortemente com “my lockbox pin is 1234”, mas não com “my jewelry is stored safely in the safe”
    Esse ponto também é importante em LLMs. Muita gente usa embeddings para similaridade de texto, quando na verdade deveria usar um modelo SBERT treinado para correlacionar perguntas com documentos que contêm suas respostas
    Dá para explorar toda essa toca do coelho em https://www.sbert.net/
    Post anterior: Should you use OpenAI's embeddings? Probably not, and here's why. https://iamnotarobot.substack.com/p/should-you-use-openais-e...
    Discussão no HN: https://news.ycombinator.com/item?id=35377935

    • Para ser justo, a tarefa original foi escolhida intencionalmente para um contexto em que abordagens como kNN+compressão têm chance de funcionar bem, ou seja, um cenário fora de domínio + com poucos recursos
      Nessas condições, as entradas de treino podem ser esparsas demais para que um modelo com muitos parâmetros aprenda bons embeddings
      Em configurações tradicionais de classificação com grandes volumes de dados dentro do domínio, métodos não paramétricos como compressão não têm chance de superar representações aprendidas

  • Não ficou claro por que os autores escolheram kNN como classificador. Se já tinham construído uma matriz de distâncias, poderiam ter convertido a matriz em fatores com escalonamento multidimensional e depois usado um algoritmo de árvores como xgboost; assim, provavelmente teriam aproveitado muito mais informação e obtido resultados bem melhores do que com kNN
    Também poderiam ter usado o algoritmo de compressão PAQ, muito melhor do que compressores da família LZ. Essas escolhas talvez tivessem melhorado bastante os resultados e levado à conclusão original
    O ponto bom deste artigo foi abstrair o algoritmo de compressão, o que me fez pensar no que mais seria possível fazer com compressão na relação p(x) ~ K^(-|x|). Aqui, K é o tamanho do alfabeto, |x| é o comprimento da string x, assumindo codificação ótima
    Por exemplo, pensei que também seria possível fazer uma classificação tradicional agrupando os fatores de cada resposta em documentos separados e, no estilo do artigo, encontrar o documento que melhor comprime a amostra seguinte para decidir a classe. Seria uma espécie de classificação supervisionada usando algoritmo de compressão
    Quanto mais o compressor se aproximar do código ótimo para aquele conjunto de dados, melhor isso deve funcionar
    Uma abordagem de previsão sequencial também seria igualmente simples de implementar
    Foi uma surpresa agradável

  • Você pode explicar como um algoritmo de compressão pode vencer um LLM? Parece como comparar grafite com algo melhor
    Parece que a resposta deve estar em algum lugar, mas não estou familiarizado com IA e simplesmente não consigo entender

    • Em geral, compressão = modelo + codificação entrópica
      O papel do modelo é prever o que vem a seguir, e o papel do codificador entrópico é codificar a diferença entre a previsão e o próximo valor real, fazendo com que os resultados mais prováveis usem o mínimo possível de bits
      Quanto mais preciso for o modelo, menor será a diferença entre realidade e previsão, e menos bits o codificador entrópico precisará, então a compressão melhora
      Algoritmos de compressão simples têm modelos simples, como “se eu vi o mesmo byte 10 vezes, é provável que o 11º também seja o mesmo”. Mas um LLM também pode ser usado como modelo, porque é isso que ele faz ao completar texto com a palavra mais plausível
      Aqui fizeram o contrário. Em vez de usar um modelo para compressão, usaram um algoritmo de compressão como se fosse um modelo, com alguns truques. Quando o algoritmo de compressão codifica um resultado com menos bits, ele o trata como o resultado mais provável
      Os autores do artigo original mostraram que, em algumas tarefas, um modelo simples extraído do gzip vence um LLM muito mais complexo
    • Um modelo de linguagem estima a probabilidade de uma sequência de palavras P(w_1, ..., w_n), ou de forma equivalente P(palavra | contexto)
      Na compressão, sequências de palavras mais prováveis devem receber códigos mais curtos, então há uma relação direta. Um método bem conhecido para construir esses códigos com base em probabilidades é a codificação de Huffman
      Isso vale tanto para um modelo estatístico de linguagem que usa frequência de palavras quanto para um que usa um LLM para estimar probabilidades. Quanto melhor o modelo de linguagem, isto é, quanto menor a perplexidade, menor será o resultado da compressão
      Por outro lado, também se pode dizer que um algoritmo de compressão define implicitamente um modelo de linguagem por meio do comprimento dos códigos. Por exemplo, ele assume que strings duplicadas são mais prováveis do que ruído aleatório
    • A intuição do método do gzip é a seguinte
      Se você comprimir ABC, isso vira X bytes. Depois, se comprimir ABCABC, isso não vira 2X bytes. Quanto mais parecidas forem as duas strings concatenadas, menos bytes serão necessários
      ABCABD será maior que ABCABC, mas menor que ABCXYZ
      Também sabemos que o BERT, pelos padrões de hoje, é um LLM muito pequeno, e que ele tem desempenho inferior aos modelos com bilhões de parâmetros que vemos com frequência hoje em dia
    • Compressão é equivalente à inteligência
      https://mattmahoney.net/dc/rationale.html
    • É uma tarefa muito limitada. Você recebe um documento e o classifica em uma de, digamos, umas 10 categorias
      Um método como detectar certas palavras também pode funcionar bastante bem em alguns casos. Em coisas que comprimem bem, substrings em comum aparecem com frequência

  • Se isso for verdade, quero ver como as pessoas que fizeram tanto alarde sobre esse artigo agora vão apagar seus rastros em silêncio
    Estou olhando especialmente para os influenciadores do LinkedIn e do Twitter
    Se não for verdade, eu vou parecer um idiota, mas só passei os olhos no artigo

  • Gzip como classificador é surpreendentemente bom e deveria ser usado como baseline para redes neurais

  • Só para constar, o blog parece ter parado em 2022
    A data do post está marcada como 17 de julho de 2022

    • Valeu. Isso vai ser corrigido em breve. É isso que acontece quando você escreve a data manualmente...