Alcançando 78% de acurácia no MNIST com menos de 10 linhas de código usando GZIP

• Um experimento elevou a classificação de dígitos manuscritos do MNIST a cerca de 78% de acurácia usando apenas compressão GZIP e k-vizinhos mais próximos (k-NN), mostrando que a compressão pode ser usada como uma ferramenta de classificação sem modelo
• A distância de compressão normalizada (NCD) é calculada com base em quanto o tamanho muda ao comprimir duas amostras de imagem juntas, e isso é usado como métrica de similaridade entre imagens
• Cada amostra de teste é comparada com 100 amostras de treino, e o rótulo previsto é definido pela maioria entre os vizinhos com k=5 mais próximos
• Devido ao custo computacional, a acurácia foi medida com apenas parte das imagens de teste, e usar o conjunto completo pode tornar a avaliação mais precisa
• O exemplo público ainda contém um erro de refatoração: ele cria um cache dos comprimentos comprimidos, mas não o usa no cálculo real da NCD, então é necessário remover o cache ou refletir isso em compute_ncd

---

Classificando o MNIST com GZIP + k-NN

• O experimento classifica o conjunto de dados de dígitos manuscritos MNIST com a combinação GZIP + k-NN
• O exemplo curto de código usa o tamanho do resultado de gzip.compress(z.tobytes()) como comprimento comprimido, calcula a NCD e depois escolhe o rótulo mais frequente entre os 5 vizinhos mais próximos
• Há um exemplo executável em Jupyter Notebook
• O objetivo não é obter a melhor acurácia possível, mas validar de forma simples a ideia de usar a compressão como uma ferramenta de classificação sem modelo
• O código com menos de 10 linhas está mais para um elemento divertido de code golf do que para o núcleo do experimento

Cálculo de similaridade e procedimento de classificação

• A NCD mede a similaridade normalizando o quanto o custo de comprimir dois pontos de dados juntos difere de comprimi-los separadamente
• O comprimento comprimido é calculado da seguinte forma
  • Cx1 = len(gzip.compress(x1.tobytes()))
  • Cx2 = len(gzip.compress(x2.tobytes()))
  • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
• A fórmula da NCD tem a forma (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
• A classificação calcula a distância entre cada imagem de teste e as imagens de treino, ordena da menor para a maior e usa votação majoritária dos 5 mais próximos
• No experimento, a comparação foi feita com base em 100 amostras de treino e, por causa do custo computacional, também foi usada apenas parte do conjunto de teste

Ideias de referência e pontos de atenção no código

• Essa abordagem foi inspirada no texto text generation from data compression e no artigo parameter free text classification
• Depois de escrever o texto, o autor também encontrou a postagem MNIST by ZIP de Andreas Kirsch, que usava um método parecido em 2019
• O código de exemplo cria um cache dos comprimentos comprimidos das amostras de treino, mas não usa esses valores no loop real
  • Tanto a versão normal quanto a ofuscada criam compressed_lengths ou cls, mas não usam os comprimentos em cache no cálculo da NCD
  • Remover o cache e usar diretamente training_set, ou alterar compute_ncd para aproveitar os valores em cache, faz a intenção do código voltar a bater com a implementação

[GN⁺]

Opiniões no Hacker News

• Ao trocar a função de distância do código por métricas mais simples, a distância GZIP teve precisão menor e custo computacional muito maior na classificação do MNIST
  Distância Gzip: cerca de 3 minutos, 78% de precisão / distância euclidiana: cerca de 0,5 s, 93% / distância de Jaccard: cerca de 0,7 s, 94% / dissimilaridade de Dice: cerca de 0,8 s, 94%
  Jaccard e Dice foram medidos após binarizar as imagens
  Não conheço muito bem o algoritmo GZIP, mas é interessante que o resultado seja tão baixo, e fico curioso se um algoritmo de compressão mais voltado a imagens seria melhor
  O texto em si é criativo, e o código e a explicação também são bons, mas acho que esses baselines acima acrescentam contexto à pontuação do gzip

  • O melhor resultado que encontrei foi com informação mútua normalizada, chegando a 95%; é um pouco mais complexa, mas pode ser calculada bem rapidamente em imagens binarizadas
    NMI skimage: cerca de 30 s, 95% de precisão / NMI numba: cerca de 0,6 s, 95% de precisão
    Usei um código numba fornecido pelo ChatGPT para calcular contagens conjuntas 2x2, entropia e informação mútua normalizada
  • Eu sabia que o MNIST era simples, mas não imaginava que fosse tanto; se você puder compartilhar o trecho de código usado, seria ótimo para servir de baseline
    Pessoalmente, tenho interesse em treinamento rápido no CIFAR10, então esse tipo de abordagem parece poder ser bastante útil em outros domínios também
  • A implementação de métodos de kernel do ben recht chega a 98% em 10 linhas
    https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
  • Também testei compressão PNG e, na prática, foi um pouco melhor: PNG ficou com cerca de 15,1 s e 83% de precisão
    Também incluí zstandard, e Zstd(level=3) ficou com cerca de 3,5 s e 88% de precisão, muito mais rápido que gzip
    Ao calcular Cx1x2, se usar (x1-x2)*2 em vez de x1+x2, o zstd sobe para 93% de precisão
    Se, em vez de somar os dois arrays, você os empilhar um acima do outro, o desempenho desmorona totalmente e fica abaixo de 20%; é interessante porque, em classificação de strings, esse método parece funcionar bem
  • O método com gzip é legal, mas no fim parece produzir resultado pior com mais etapas

• Comparando com outras técnicas, Linear SVC fica em 92%, SVC com kernel RBF em 96,4%, SVC com kernel polinomial em 94,5%, regressão logística em 89% e Naive Bayes em torno de 81%
  Fonte: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
  Pelos textos online, parece que só com K-NN já dá para obter resultados muito melhores, então talvez o autor tenha dificultado as coisas ao usar gzip

  • Muita gente não sabe que regressão logística consegue cerca de 90% de precisão no MNIST
    Gosto de começar com modelos simples e adicionar complexidade depois, mas ouvi muitas vezes que “regressão logística não funciona” mesmo em problemas nos quais ela de fato funciona bem
    Quando pergunto qual acham que seria o desempenho de referência no MNIST, muita gente chuta 20~30%
    Mesmo pessoas que trabalham com machine learning frequentemente subestimam a rapidez com que aparecem retornos decrescentes ao aumentar bastante a complexidade do modelo
    Em muitos casos, quando um modelo simples não tinha bom desempenho, também era difícil obter desempenho excelente com um modelo mais complexo
  • Aquele blog não mostra o melhor desempenho de ponta atual; está mais para uma comparação de implementações de SVM relativamente simples
    O artigo original que apresentou o dataset MNIST também chegou a cerca de 98% de precisão, e redes neurais atuais chegam a 99,87%
    https://paperswithcode.com/sota/image-classification-on-mnis...
  • O ponto central não é fazer melhor, mas mostrar que, mesmo depois da compressão, ainda sobra informação suficiente para obter um sinal forte
    A compressão serve justamente para tornar o problema mais difícil e, na prática, continua fazendo isso
  • É legal que isso funcione, mas, como o MNIST ficou fácil demais, eu gostaria que parassem de usá-lo como benchmark
  • Há, portanto, um algoritmo de compressão mais ideal para a relação entre as entradas e as saídas do MNIST
    Como outros modelos tendem a adicionar ruído em algum ponto, fico pensando em colocar engenharia de atributos antes do gzip
    Por exemplo, parece possível aplicar primeiro Gaussian blur e convoluções e depois usar deep learning para seleção de atributos

• O código pode ser elegante e curto, mas 78% de precisão no MNIST é muito ruim
  Até um modelo dummy feito em TensorFlow chega facilmente a 90% de precisão, e o melhor modelo chega a 99,87%
  Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

  • Acho que o texto enfatiza o ponto errado
    A parte interessante é que dá para usar compressão em classificação mesmo sem treinar um modelo
    Isso leva à pergunta de se outras métricas informacionais mais baratas e com perdas também poderiam ser usadas
    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\)*
  • O objetivo não é criar um código “elegante e curto”, mas mostrar uma curiosidade interessante; fazer em 10 linhas é só um desafio extra
    O interessante não é saber se GZip alcança o estado da arte, e sim o fato de que ele consegue classificar de forma razoável
    É como um urso tocando piano: o surpreendente não é ele reproduzir Mozart perfeitamente, mas conseguir tocar piano
  • Não é uma tentativa de quebrar recordes, e sim um exemplo que mostra um aspecto interessante da compressão
    Ainda assim, é 8 vezes melhor que o baseline e mostra que a compressão pode aprender representações

• Se você trocar compute_ncd por distância euclidiana, a acurácia de teste sobe 15 pontos percentuais e o volume de cálculo também cai bastante
  Basta mudar para algo como distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths]

• O melhor livro que vi sobre as conexões profundas entre teoria da informação, compressão e algoritmos de aprendizado foi o MacKay
  Para quem teve uma formação adequada, talvez isso seja conhecimento básico, mas, do ponto de vista de alguém que aprendeu machine learning prático de forma autodidata, ver esse tema se conectar a áreas como física de partículas e cosmologia foi um daqueles momentos intensos de “aha!”
  Deixo aqui na esperança de que pelo menos uma pessoa tenha a mesma percepção

  • Coloquei MacKay na minha lista de tarefas
    Achei bem impressionante quando descobri que a compressão Lempel-Ziv original, uma das bases do gzip, surgiu não apenas como uma tentativa de reduzir tamanho, mas a partir do estudo da “complexidade de sequências finitas”
    https://ieeexplore.ieee.org/document/1055501

• Para ser justo, o MNIST fica quase perfeitamente separado só de passar pelo UMAP
  Hoje em dia, acho que é preciso se esforçar bastante para ter desempenho ruim no MNIST
  https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
  Acho que já seria melhor aposentar esse dataset; datasets como o QuickDraw fazem muito mais sentido

  • Como autor, concordo totalmente
    Não acho que seja uma grande conquista por si só, mas ainda é interessante ver que funciona
    Quando eu chegar em casa, vou acrescentar ao texto que resolver MNIST é relativamente fácil
  • Do ponto de vista de pesquisa, MNIST é basicamente um problema resolvido, e imagino que o desempenho atual já seja melhor que o humano
    Ainda assim, como a maioria dos algoritmos simples e razoáveis chega a 97% de acurácia, ele continua tendo valor como ferramenta educacional ou como dataset Hello world
    Mesmo construindo as ferramentas do zero, ele cabe no tamanho de um exercício, e é uma tarefa útil que qualquer pessoa entende, como “reconhecimento de dígitos em correspondências”
  • gzip não é “coisa de hoje”; é uma tecnologia muito mais antiga que UMAP e até que o próprio MNIST
    Se você entende compressão, essa abordagem também é uma ideia bem simples, então poderia ter sido escrita no primeiro dia em que o MNIST foi publicado e ainda assim teria chegado a 78% de acurácia
    É isso que me parece bem surpreendente
  • Chega a fazer parecer plausível aquela pessoa grosseira que reclamava de siglas
    O repositório também não define UMAP, mas, se o ChatGPT estiver certo, UMAP é a sigla de Uniform Manifold Approximation and Projection, uma técnica de redução de dimensionalidade e visualização usada em machine learning e análise de dados

• Essa área é só um hobby para mim, mas dados fortemente comprimidos não deveriam ter alta entropia, como dados criptografados?
  Se você encontra padrões nos dados comprimidos para descobrir o dígito original, não deveria ser possível usar esses padrões para obter uma compressão melhor?

  • Esta demonstração não classifica olhando para os dados comprimidos, e sim por quão bem os dados se comprimem
    A ideia é que “7 7” deve comprimir melhor que “7 3”, e que “7 7” em imagens raster também deve comprimir melhor que “7 3”
  • Dados criptografados ideais devem ser incompressíveis
    A incompressibilidade é uma característica de operações criptográficas eficientes
    Veja a seção sobre compressão no artigo sobre complexidade de Kolmogorov: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
    Um dos conceitos de que gosto em compressão é o princípio das gavetas, segundo o qual todo algoritmo de compressão necessariamente tem alguma saída que fica maior que a entrada
    Você ainda pode tentar comprimir um payload criptografado bem projetado, mas, em média, a saída ficará maior que a entrada, tornando a compressão inútil; por isso o chamamos de “incompressível”
    https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

• Acho que, alguns anos atrás, houve um caso em que usaram o tamanho das imagens do MNIST como uma “meta-característica”, mas não consigo encontrar agora
  Pelo que lembro, só com essa característica, sem nem olhar a imagem, a acurácia ficava por volta de 90%

  • Alguns anos atrás fiz um projeto de fingerprinting de capturas de tela de páginas web, e só o tamanho da imagem comprimida funcionava tão bem quanto um certo método de fingerprint para comparar similaridade entre capturas de tela
  • Fico curioso sobre o que “tamanho” quer dizer aqui
    É o tamanho comprimido com gzip? Se for simplesmente quão escura é a imagem do MNIST, isto é, apenas a proporção de pixels escuros, dá cerca de 20% de acurácia, duas vezes melhor que um palpite aleatório, mas ainda muito longe de 90%

• Suspeito que os autores daquele artigo tenham cometido um erro e que os resultados tenham saltado para o topo do benchmark por causa disso
  Depois daquele caso, passei a achar que a teoria não era consistente, mas ainda assim 78% de acurácia só com GZIP é impressionante

  • Talvez você esteja pensando neste texto: https://kenschutte.com/gzip-knn-paper/
  • Isto é 78% de acurácia usando distância de compressão baseada em Gzip e KNN, então parece pior do que quase qualquer outra métrica de distância que se possa imaginar combinada com KNN

• Independentemente de este problema ser ou não uma boa aplicação para truques de compressão, quem estiver fazendo experimentos deveria parar de usar gzip e usar zlib
  Se você trocar a primeira linha de gzip.compress para zlib.compress, terá a mesma performance de classificação com velocidade 3 vezes maior