Resolvendo ARC-AGI sem pré-treinamento
(iliao2345.github.io)- Em problemas como o ARC-AGI, nos quais é preciso descobrir regras a partir de poucos exemplos, o CompressARC encontra soluções usando apenas aprendizado no momento da inferência para cada quebra-cabeça, sem pré-treinamento, datasets externos ou busca em larga escala
- A ideia central é um experimento sobre a possibilidade de comportamento inteligente emergir ao otimizar o objetivo de compressão de informação sem perdas, de modo que a representação do quebra-cabeça, incluindo a resposta correta, fique mais curta
- Usando cerca de 20 minutos por quebra-cabeça em uma RTX 4070, o método registrou 34,75% no conjunto de treino e 20% no conjunto de avaliação, destacando-se por ser uma abordagem com rede neural que usa apenas o quebra-cabeça-alvo como dado de treino
- A arquitetura foi projetada com foco em equivariância à ordem dos exemplos, permutação de cores e rotações/reflexões, e usa uma representação de multitensor que agrupa tensores de vários ranks
- Mostra pontos fortes em mapeamento cor-procedimento, preenchimento, recorte, conexão de pontos e movimentos curtos, mas contagem, expansão de padrões de longa distância, rotação/cópia/redimensionamento e planejamento de agente ainda seguem como gargalos
Experimento: dá para resolver ARC-AGI só com compressão?
- A pergunta central é se apenas a compressão de informação sem perdas pode gerar comportamento inteligente
- O CompressARC é um método voltado para os quebra-cabeças do ARC-AGI que opera apenas com uma função-objetivo baseada em compressão
- Ele impõe três restrições
- Sem pré-treinamento: o modelo começa com inicialização aleatória e é treinado no momento da inferência
- Sem dataset: cada modelo aprende apenas um único quebra-cabeça ARC-AGI alvo e produz uma única resposta
- Sem busca: em quase todos os sentidos, usa apenas descida de gradiente, sem busca
- Os resultados foram de 34,75% no conjunto de treino e 20% no conjunto de avaliação, com cada quebra-cabeça levando cerca de 20 minutos em uma RTX 4070
- O texto afirma que este é o primeiro método com rede neural para ARC-AGI que usa apenas o quebra-cabeça-alvo como dado de treino
Configuração do problema ARC-AGI
- O ARC-AGI é um benchmark de IA apresentado em 2019 para testar a capacidade de inferir e generalizar regras abstratas a partir de poucos exemplos
- Cada quebra-cabeça fornece vários exemplos de entrada-saída e uma entrada de teste; o sistema precisa acertar a grade de saída de teste
- Há duas tentativas por quebra-cabeça, e acertar qualquer uma delas vale 1 ponto
- É possível alterar o tamanho da grade de saída e escolher a cor de todos os pixels
- Os quebra-cabeças são projetados para que humanos razoavelmente consigam resolvê-los, mas sejam mais difíceis para máquinas
- Humanos em média resolvem 76,2% do conjunto de treino
- Especialistas humanos resolvem 98,5%
- Os 400 quebra-cabeças de treino são mais fáceis do que os demais e servem para fazer aprender os seguintes padrões
- Objetualidade: objetos não aparecem nem desaparecem sem motivo
- Orientação a objetivos: alguns objetos agem como agentes com intenção
- Números e contagem: usa quantidade de objetos, ordenação, comparação e matemática básica como soma e subtração
- Geometria e topologia: inclui reflexões, rotações, translações, transformações, combinações, repetição e diferenças de distância
- A competição recente no Kaggle do ARC Prize ofereceu prêmios de mais de US$ 1 milhão, e o principal foi destinado a métodos que alcancem 85% em 100 problemas ocultos com 12 horas de computação em ambiente restrito
Como o CompressARC funciona
- No CompressARC, representações que podem ser comprimidas com menos bits tendem a estar ligadas a soluções mais corretas dos quebra-cabeças
- O sistema busca uma representação comprimida que transforme um quebra-cabeça incompleto em um quebra-cabeça completo, de modo que a descompressão reconstrua o problema e a resposta
- A rede neural assume o papel de decodificador
- Não existe uma rede neural codificadora separada
- A codificação é implementada, no momento da inferência, treinando o decodificador via descida de gradiente
- Os pesos otimizados e a configuração da distribuição de entrada funcionam como a representação comprimida em bits contendo o quebra-cabeça e a resposta
- Em termos de representação padrão de machine learning, o procedimento é o seguinte
- Receber um quebra-cabeça ARC-AGI
- Construir a rede neural
fde acordo com o número de exemplos do quebra-cabeça e o número de cores observadas - Receber uma entrada aleatória normal
z ~ N(μ, Σ)e produzir logits de cor por pixel para todas as grades - Minimizar a soma da entropia cruzada nas grades conhecidas e ignorar a grade-resposta
- Aplicar uma penalidade de divergência KL para manter
N(μ, Σ)próximo deN(0,1) - Armazenar as grades-resposta geradas durante o treino e escolher como previsão final a resposta que apareceu com mais frequência
fθfoi projetada para ser equivariante a aumentos comuns, como mudança na ordem dos pares de entrada-saída, permutação de cores e rotações/reflexões espaciais
Derivação sob a perspectiva de compressão
- Compressão sem perdas é o problema de representar informação com o menor número possível de bits e ainda assim reconstruir exatamente o original a partir dessa representação
- No ARC-AGI, idealmente seria preciso comprimir o par completo de quebra-cabeça e resposta como um símbolo, mas na prática o codificador não recebe a resposta como entrada e a distribuição que gera os quebra-cabeças também é desconhecida
- Assume-se a existência de um sistema de compressão eficiente em bits e viável na prática para o dataset ARC-AGI
- Mesmo sem conhecer a distribuição
p, pode-se imaginar um compressor universal que minimizelen(f)+len(s), ondefé o programa esé sua entrada- O decodificador executa
f(s)para reconstruir o original - Em teoria da informação algorítmica, ele pode ser apenas ineficiente em relação ao compressor original pelo comprimento adicional de
f - Na prática, porém, um codificador que busca no espaço de programas não é viável
- O decodificador executa
- O CompressARC substitui a busca no espaço de programas por um forward pass de rede neural como programa fixo
sé composto por pesosθ, entradaze correção de saídaε- O comprimento de código de
θezé calculado na perspectiva de Relative Entropy Coding (REC), enquantoεé tratado pela perspectiva de arithmetic coding - O comprimento do código de correção de saída torna-se igual à entropia cruzada total das grades conhecidas
- O comprimento do código de
ztorna-seKL(pz || qz), comqz = N(0,I)
- O comprimento total do código assume a mesma forma da perda de um VAE
- erro de reconstrução
- KL sobre
z - regularização do decodificador
- A implementação do CompressARC inclui, a partir dessa derivação, modificações ligadas a parte da regularização, à equivariância e à independência entre quebra-cabeças
Arquitetura: multitensor e equivariância
- A característica mais importante da arquitetura é a equivariância
- Se a entrada
zfor transformada, o quebra-cabeça ARC-AGI de saída também deve ser transformado da mesma forma - Exemplos disso incluem reordenação dos pares entrada-saída, embaralhamento de cores e espelhamento/rotação/reflexão da grade
- Se a entrada
- O projeto começa criando uma arquitetura-base totalmente simétrica e depois adiciona camadas assimétricas para fornecer as capacidades não equivariantes necessárias, quebrando uma a uma as simetrias desnecessárias
- Os dados internos fluem em um formato chamado multitensor
- É um conjunto de tensores com vários ranks e shapes
- As dimensões são subconjuntos de até
[n_examples, n_colors, n_directions, height, width, n_channels] - A dimensão
channelé sempre mantida - Aplicando regras, o número de tensores legais dentro do multitensor é reduzido para 18
- O quebra-cabeça pode ser representado como um tensor
[examples, colors, height, width, channel]channelé usado para selecionar a grade de entrada ou saídawidtheheightrepresentam a posição dos pixels- A dimensão
colorcontém a representação one-hot das cores dos pixels
- A arquitetura completa segue o fluxo abaixo
- Começa nos parâmetros da distribuição de
z - Decoding Layer
- Repetição 4 vezes de Multitensor Communication, Softmax, Directional Cummax, Directional Shift, Directional Communication, Nonlinear e Normalization
- Linear Heads para produzir a distribuição do quebra-cabeça ARC-AGI
- Começa nos parâmetros da distribuição de
Resultados de desempenho
- O treinamento foi feito com Adam por 2000 iterations
- taxa de aprendizado
0.01 β1 = 0.5,β2 = 0.9
- taxa de aprendizado
- Resultados no conjunto de treino
- 100 iteration: Pass@2 2,25%
- 500 iteration: Pass@2 27,5%
- 1000 iteration: Pass@2 31,75%
- 2000 iteration: Pass@2 34,75%
- Pass@1000 em 2000 iteration: 52,75%
- Resultados no conjunto de avaliação
- 100 iteration: Pass@2 1,25%
- 500 iteration: Pass@2 15%
- 1000 iteration: Pass@2 19,25%
- 2000 iteration: Pass@2 20%
- Pass@1000 em 2000 iteration: 33,75%
- Como a avaliação do ARC-AGI permite duas tentativas, o principal resultado destacado no texto é o Pass@2
Quebra-cabeças que resolve e quebra-cabeças difíceis
- O CompressARC identifica regras até onde suas capacidades permitem, mas esbarra em gargalos quando a arquitetura não dispõe da habilidade necessária
- Exemplos de tarefas que ele consegue realizar
- atribuir cores individuais a procedimentos individuais
- preenchimento
- recorte
- conexão de pontos, inclusive em diagonais de 45 graus
- detecção da mesma cor
- identificação de adjacência entre pixels
- atribuição de cores por exemplo
- identificação de partes de formas
- movimentos de curta distância
- Também há tarefas claramente difíceis
- fazer correspondência entre duas cores
- repetir a mesma operação várias vezes em sequência
- mover, rotacionar, refletir, redimensionar e duplicar imagens
- detectar propriedades topológicas como conectividade
- planejar e simular o comportamento de agentes
- expandir padrões a longa distância
- No quebra-cabeça de treino 28e73c20, é preciso expandir um padrão das bordas até o centro; o CompressARC faz expansões curtas, mas perto do centro passa a depender de chute
Exemplo: Color the Boxes
- Na solução humana, percebe-se que a entrada é dividida em caixas e que, na saída, essas caixas são coloridas
- Os cantos são sempre pretos
- O centro é sempre magenta
- As caixas nas bordas recebem cor conforme a direção: vermelho em cima, azul embaixo, verde à direita e amarelo à esquerda
- A evolução do treino do CompressARC muda por etapas
- 50 step: reflete que as linhas e colunas em azul-claro da entrada correspondem à saída
- 150 step: mostra uma forma de saída em que pixels próximos tendem a ter cores parecidas
- 200 step: imita blocos de cor maiores cortados por bordas em azul-claro e blocos pretos nos cantos
- 350 step: acerta em grande parte as cores das caixas conforme a direção em relação ao centro
- 1500 step: a saída já está quase refinada, mas ainda restam erros ocasionais em algumas amostras
- A análise da distribuição
zaprendida mostra que ela codifica uma tabela de correspondência entre cor e direção e as posições das divisórias de linha e coluna - Apenas quatro tensores mantêm conteúdo informacional
(examples, height, channel): guarda a posição das linhas em azul-claro de cada exemplo(examples, width, channel): guarda a posição das colunas em azul-claro de cada exemplo(direction, color, channel): guarda a correspondência entre direção e cor(color, channel): distingue o papel especial de magenta e azul-claro
Casos adicionais e análise da representação
-
Quebra-cabeça Bounding Box 6d75e8bb
- A solução humana consiste em desenhar a menor caixa azul-claro que envolve a forma vermelha
- O CompressARC mostra sinais de ter identificado a bounding box comum no passo 100 e, no passo 150, encontra a resposta antes de refiná-la com mais treinamento
- Os principais tensores que permanecem são
(examples, height, channel),(examples, width, channel)e(color, channel) - Os tensores de linha e coluna indicam linhas e colunas com muitos pixels azul-claro, mas não está claro como o modelo sabe a posição exata das bordas
-
Quebra-cabeça Center Cross 41e4d17e
- A partir do centro da bolha azul na entrada, deve-se desenhar raios magenta para cima, baixo, esquerda e direita, e a cor da bolha precisa sobrepor os raios
- O CompressARC copia a entrada, depois surgem linha e coluna magenta, e elas gradualmente se estabilizam na posição correta
- Não aparecem erros do tipo humano, como desenhar os raios incorretamente por cima da bolha
- Os tensores que permanecem são
(examples, height, width, channel)e(color, channel) (examples, height, width, channel)codifica o centro da bolha
Ideias de melhoria
- Em vez de comprimir cada quebra-cabeça separadamente, comprimir todo o dataset ARC-AGI junto poderia compartilhar computação entre quebra-cabeças e produzir um viés indutivo melhor
- Uma possibilidade é usar os mesmos pesos de rede para todos os quebra-cabeças, com perturbações limitadas específicas por quebra-cabeça
- Também é proposta uma abordagem com hypernetwork, aprendendo embeddings de alta dimensão por quebra-cabeça e um mapeamento linear desses embeddings para os pesos da rede
- Essa direção não foi tentada porque poderia desacelerar o ritmo de iteração da pesquisa
- Para tarefas de cópia de formas, camadas do tipo convolution podem ser úteis
- Se uma grade armazenar a forma e outra indicar a posição de cópia, uma convolution poderia produzir o resultado da cópia
- Convolutions comuns tinham o problema de amplificar o ruído mais do que o sinal
- Tropical convolution funcionou bem em quebra-cabeças de brinquedo, mas não foi suficiente para os quebra-cabeças de treino do ARC-AGI
- Também foi considerada a aplicação de um KL floor para aliviar posterior collapse
- Observou-se que, quando o KL de tensores importantes cai para 0, ele não se recupera depois
- Manter o KL acima de 0 por algum tempo pode fazer a rede aprender a usar essa informação
- A implementação foi feita, mas não houve casos em que os tensores se recuperaram, indicando que talvez seja necessário desenhar outro agendamento para o KL floor
- A implementação não usa regularização
- Na formulação do problema, ela mede a complexidade de
fe faz parte da derivação do CompressARC - O texto avalia que tê-la removido na implementação foi algo um tanto temerário
- Na formulação do problema, ela mede a complexidade de
Trabalhos relacionados e posição na pesquisa
- A ideia de equivalência entre compressão e inteligência foi inspirada no Hutter Prize
- O Hutter Prize premia o sistema que melhor comprime um arquivo de texto da Wikipedia, associando capacidade de compressão de informação à inteligência
- A base teórica inclui Solomonoff Induction, Kolmogorov Complexity e Minimum Description Length
- Do ponto de vista da teoria da informação, o Relative Entropy Coding é central
- A proposta considera que, se for possível limitar a divergência KL, então um algoritmo de compressão pode ser construído, abstraindo o problema de implementar o código binário real
- Na perspectiva de VAE, o decodificador faz o papel do algoritmo de descompressão
- Também seria possível considerar uma neural Turing machine com capacidades mais gerais, mas ela não se adapta tão bem à otimização por descida de gradiente, por isso foi usada a abordagem de VAE
- O reweighting da perda de reconstrução no estilo beta-VAE funciona bem neste caso
- Métodos anteriores para ARC-AGI usam principalmente LLMs, aumento de dados, datasets alternativos, aprendizado em tempo de teste e busca de programas baseada em linguagens específicas de domínio
- O CompressARC enfatiza que é uma abordagem de deep learning sem pré-treinamento externo nem busca em larga escala
- O código do projeto está disponível no GitHub
1 comentários
Opiniões no Hacker News
Pré-treinamento em larga escala parece ir contra a ideia de generalidade
Se você criou uma máquina geral capaz de sintetizar um programa que vê apenas 3 exemplos e prevê o 4º, então, na prática, resolveu a síntese de oráculos
Por outro lado, se você treinou uma rede com todo o conhecimento humano, incluindo até a criação de puzzles, fez ajuste fino com 99% do dataset e depois a deixou tentar várias vezes no 1% restante, isso está mais para construir um compressor caro que comprime a psicologia de quem elaborou a prova
Pressupõe que exista um domínio platônico de lógica e razão ao qual uma AGI só precisa se conectar, mas sem contexto não pode haver significado, inferência nem lógica
Para acertar padrões de formas, é preciso ter o conceito de forma; isso pressupõe o conceito de relações espaciais, que por sua vez pressupõe o conceito de espaço bidimensional ou tridimensional
Essas coisas parecem óbvias e implícitas porque estão profundamente entranhadas no ambiente que a mente humana evoluiu por centenas de milhões de anos para interpretar, e no ambiente que consumiu e processou por décadas
O verdadeiro teste de uma AGI é a capacidade de assimilar informações diferentes em uma visão de mundo coerente, e o pré-treinamento, na prática, está fazendo isso
Mesmo uma inteligência com essa capacidade provavelmente precisa ter “pré-carregadas” suposições estruturais sobre o mundo em que será colocada. Algo parecido com áreas do cérebro especializadas em relações espaciais, linguagem e interpretação sensorial
Humanos também descobrem como praticar uma tarefa quando querem ficar melhores em algo, e aprendem de um jeito que de fato os faz melhorar
Por isso há quem ache que AGI não vai aparecer tão cedo: https://www.lycee.ai/blog/why-no-agi-openai
Não vejo por que deveríamos esperar que uma máquina generalize bem sem conhecimento de base
Isso me lembra o podcast do Lex Fridman com Marcus Hutter
Joshua Bach também definiu inteligência como a capacidade de modelar a realidade com precisão, e fico me perguntando se a compressão sem perdas em si é inteligência, ou se é o modelo de melhor ajuste. Existe diferença entre os dois?
https://www.youtube.com/watch?v=E1AxVXt2Gv4
Portanto, é preciso olhar para quatro eixos: simplicidade, precisão, latência e complexidade da realidade; e a inteligência artificial será alguma região dentro desse espaço
Na verdade, há um teste simples para distinguir inteligência: a pessoa consegue ler o código de uma função em C e dizer como mudanças na entrada afetam a saída?
Em algoritmos complexos, é preciso criar um modelo interno. Caso contrário, como você executaria mentalmente o qsort em um milhão de itens?
Dá para distinguir do mesmo modo se um aluno está fingindo que entendeu ou se realmente entendeu
Um teste mais difícil é o inverso: criar um algoritmo a partir de apenas alguns exemplos de entrada e saída
[1] http://prize.hutter1.net/
Estou tentando destilar a essência desta abordagem, mas ela parece estar escondida atrás de detalhes não essenciais, como a escolha de um método específico de compressão ou uma distribuição a priori.
A inovação central parece estar em construir um “modelo” que possa ser otimizado por descida de gradiente e fazer com que seu ponto ótimo seja o modelo mais “simples” que memoriza a relação entrada-saída.
Aqui, “simplicidade” significa especificamente “ser eficientemente compressível”, mas, de forma mais geral, provavelmente está mais próxima de dizer que a complexidade do modelo é a menor possível.
Isso contrasta claramente com o aprendizado de máquina padrão. Normalmente, primeiro escolhemos a estrutura do modelo e vários parâmetros de complexidade, definimos um orçamento de complexidade e, depois, treinamos com dados para encontrar uma solução que memorize bem a relação entrada-saída.
Esse novo método inverte o aprendizado de máquina. Ele continua memorizando os pares entrada-saída, mas otimiza para reduzir ao máximo a complexidade do modelo.
O fato de conseguir generalizar com apenas 2 exemplos de treinamento é realmente surpreendente, e me parece sugerir fortemente uma direção correta para lidar com generalização.
O caminho pelo qual os autores chegaram a essa estrutura foi a teoria da informação, mas não sei bem se isso é o essencial.
O ponto central parece mais próximo da percepção de que, em vez de procurar o melhor modelo dentro de um orçamento fixo de complexidade, é possível procurar o modelo de complexidade mínima.
É comum adicionar um termo de regularização à função objetivo de perda na otimização, e essa regularização muitas vezes pode ser interpretada como uma penalidade sobre a complexidade.
Graças à dualidade, a mesma função objetivo pode ser vista de várias formas: minimizar uma soma ponderada do erro nos dados e da complexidade, minimizar a complexidade mantendo o erro nos dados abaixo de um limite, ou minimizar o erro nos dados mantendo a complexidade abaixo de um limite.
Essa regularização clássica parece ter saído de moda recentemente.
Não acho que ela tenha um papel grande na maioria das arquiteturas Transformer, mas seria interessante se voltasse de alguma forma.
Fora isso, há tantos elementos novos nessa abordagem que é difícil separar o que de fato está gerando o desempenho.
Por exemplo, a própria arquitetura da rede neural também parece ter sido ajustada com bastante cuidado para maximizar o desempenho em tarefas do tipo ARC-AGI, e não está claro como ela generalizaria além disso.
Cada quebra-cabeça tem um formato parecido, e os dados que variam dentro do quebra-cabeça correspondem quase exatamente às informações necessárias para inferir a regra.
Ao reduzir a quantidade de informação necessária para descrever a regra, o codec praticamente não tem escolha senão se reduzir a algo que faz quase o mesmo que a própria regra.
Se houvesse mais ruído ou dados arbitrários em cada quebra-cabeça, acho que essa técnica não teria funcionado.
Claro que, a partir de certo ponto, o quebra-cabeça não deveria virar “descobrir onde está o quebra-cabeça”, mas aqui ela funciona porque cada exemplo contém informação pura sobre o próprio quebra-cabeça.
Interessante. Cada vez mais penso que o futuro do aprendizado de máquina pode envolver menos “aprendizado de máquina” no sentido a que nos acostumamos.
Menos pré-treinamento, dados e busca; mais representação direta, processamento simbólico, satisfação de restrições e meta-aprendizado.
As coisas que se tornarão menos necessárias — pré-treinamento, dados etc. — são bagunçadas, indiscriminadas e acidentais.
Depender delas sempre deixa você subordinado à qualidade dos dados; isso é aceitável se o objetivo for mineração de dados, mas não combina com o objetivo de modelar as causas fundamentais dos dados.
Pelo que entendi, eles estão mais próximos de tentar revelar a representação mínima do espaço de soluções/problemas.
Por meio da equivariância, eles rastreiam a estrutura real do problema e derivam algo próximo da representação subjacente real do quebra-cabeça e do método de solução, em vez de esperar capturá-los por acaso a partir de muitos exemplos resolvidos.
Documentação e explicação excelentes. Também bate com minha própria introspecção, então fico feliz.
Vejo que “inteligência é comprimir informação em uma representação irredutível”.
https://en.wikipedia.org/wiki/Kolmogorov_complexity
https://en.wikipedia.org/wiki/Solomonoff%27s_theory_of_induc...
https://en.wikipedia.org/wiki/Minimum_description_length
Parece estar relacionado a esses conceitos, então pretendo investigar mais.
https://en.wikipedia.org/wiki/Wigner%27s_classification
Se o ARC-AGI é um benchmark que testa a capacidade de inferir regras abstratas a partir de exemplos mínimos e generalizar, então, no fim, ele define inteligência como a capacidade de comprimir informação em um conjunto de regras.
Sendo assim, faz sentido dizer que compressão faz esse trabalho.
Fico me perguntando se você já tentou resolver problemas do ARC-AGI diretamente.
Os problemas são bem sutis e testam uma ampla gama de conceitos abstratos.
Para referência, o o1-preview marcou 21% na avaliação pública, enquanto a abordagem do texto original marcou 34%.
Um artigo do Schmidhuber um tanto relacionado: https://arxiv.org/abs/0812.4360
A expressão “processar cada quebra-cabeça por cerca de 20 minutos em uma RTX 4070” parece significar que o desafio de 100 problemas levaria 33,3 horas.
Isso excede a meta de 12 horas do desafio, mas a abordagem em si é bem legal.
Isso parece quase uma abordagem padrão de deep learning bayesiano, exceto pelo fato de que a estrutura foi projetada com bastante cuidado.