- Transformers e LLMs são fortes em conversação, compreensão de imagens e conclusão de código, mas têm dificuldade em entregar desempenho estável em planejamento de múltiplas etapas e raciocínio de ordem superior
- Este artigo transforma tarefas de planejamento e soluções ótimas em sequências de tokens, e inclui nos dados de treinamento até o rastreamento de execução de como o A* resolve o problema
- O Searchformer primeiro imita o processo de busca do A* e depois é ajustado por fine-tuning para criar sequências de busca mais curtas, mantendo o plano ótimo
- Em experimentos com Sokoban, os modelos da família Searchformer resolveram 93,7% das tarefas de teste e usaram, em média, 26,8% menos etapas de busca do que a implementação de referência do A*
- O rastreamento de execução impõe o custo de aumentar as sequências geradas em 10×~100×, mas, mesmo com menos sequências de treinamento do que modelos maiores solution-only, gera planos ótimos com mais frequência em tarefas desconhecidas
Em que Transformers se destacam e em quais tarefas de planejamento são fracos
- Arquiteturas baseadas em Transformer apresentam alto desempenho em várias tarefas
- Conversação em nível humano
- Compreensão de imagens de alta qualidade
- Geração de vídeo
- Geração multimodal
- Conclusão de código
- Modelos como LLMs treinados com dados em escala de internet conseguem generalizar bem em casos de uso reais
- Mas ainda há limitações em tarefas de planejamento e raciocínio
- LLMs mostram deficiências em tarefas de planejamento de múltiplas etapas
- Também surgem dificuldades ao executar raciocínio de ordem superior
Limitações dos prompts de pensamento passo a passo
- Abordagens recentes tentam elevar o desempenho induzindo Transformers a gerar “pensamentos” intermediários antes de responder
- O prompting Chain-of-Thought(CoT) e Tree-of-thoughts(ToT) incentiva o modelo a “pensar” passo a passo
- Essas técnicas costumam ser eficazes, mas também podem reduzir o desempenho por motivos como self-enforcing
- Uma abordagem que funciona bem em um dataset pode falhar em outro
- Exemplos incluem casos em que o tipo de raciocínio necessário muda, como raciocínio espacial e raciocínio matemático
- Como fazer Transformers e LLMs executarem de forma estável planejamento, tomada de decisão em múltiplas etapas e raciocínio continua sendo um tema ativo de pesquisa
Incluir a dinâmica de busca do A* nos dados de treinamento
- Esta abordagem foca em treinar Transformers para resolver tarefas complexas de planejamento de forma mais robusta
- O modelo é treinado, como um LLM, para prever a próxima palavra dada uma sequência de palavras
- Os experimentos são realizados em um dataset sintético gerado, que usa linguagem sintética e vocabulário sintético
- Tarefas de planejamento e planos de solução ótima são representados como sequências de palavras chamadas tokens
- O processo computacional executado pelo A* é registrado como uma sequência de tokens de rastreamento de execução
- O rastreamento de execução compõe um dataset sequencial que contém a dinâmica de busca do A*
- O Transformer é treinado, por meio de sequências reforçadas com busca, para gerar sequências de tokens que codificam conjuntamente a dinâmica de busca do A* e o plano ótimo
Procedimento de treinamento do Searchformer
- O modelo final, Searchformer, é criado em duas etapas
- Primeiro, o Transformer é treinado para imitar o processo de busca do A*
- Depois, passa por fine-tuning para encontrar o plano em menos etapas de busca, ainda emitindo o plano ótimo
- Esse processo é chamado de search dynamics bootstrapping
- O objetivo é obter um Transformer que resolva tarefas complexas de planejamento com menos etapas de busca do que a implementação de referência do A*
Experimentos com Sokoban e desempenho de generalização
- Em quebra-cabeças Sokoban, os modelos da família Searchformer resolveram 93,7% de todas as tarefas de teste
- O número médio de etapas de busca é 26,8% menor do que o da implementação de referência do A*
- Em experimentos que controlaram a complexidade das tarefas, o tamanho do dataset e o tamanho do modelo, foi confirmado o efeito de incluir o rastreamento de execução
- Incluir o rastreamento de execução nos dados de treinamento aumenta o comprimento das sequências geradas em 10×~100×
- Mesmo assim, o desempenho aumenta em um conjunto independente de tarefas de teste
- O modelo search-augmented gera planos ótimos em tarefas desconhecidas com mais frequência do que um modelo solution-only maior, mesmo tendo 10 vezes menos sequências de treinamento
- O modelo search-augmented é treinado com dados que incluem a descrição da tarefa, a solução e o rastreamento de execução
- O modelo solution-only é treinado com sequências que incluem apenas a descrição da tarefa e a solução da tarefa
- Esse resultado mostra que incluir a dinâmica de busca do A* no processo de treinamento do Transformer pode melhorar o desempenho em tarefas de planejamento
1 comentários
Opiniões do Hacker News
Também houve uma pesquisa mais interessante usando Transformers para planejamento de movimento robótico 0
O problema de mover um braço robótico do ponto A ao ponto B evitando colisões é muito difícil por ser de alta dimensionalidade e contínuo, e os métodos tradicionais de planejamento tendem a exigir muito cálculo e ainda assim ter desempenho ruim.
Por isso, esse é um dos motivos pelos quais os movimentos de robôs parecem “antinaturais” e eles não conseguem fazer bem várias tarefas que queremos; essa abordagem parece bastante competitiva com outros métodos, planejando trajetórias quase ótimas mais rapidamente.
Antes de seguir nessa direção de pesquisa, fico curioso se tentaram o algoritmo J modificado*, uma otimização do A* para grafos de jogos/busca de caminhos.
Para quem tiver curiosidade, está no Game AI Pro 2 0
O artigo testa quão bem Transformers conseguem prever rastros de execução, como no caso de um compilador JIT, por exemplo, e se isso pode ajudar a melhorar heurísticas em áreas como busca de caminhos.
Ainda assim, Transformers são lentos, então olho para isso com cautela.
Problemas de planejamento já são bem tratados por técnicas consolidadas como busca em grafos, solucionadores SAT, pesquisa operacional e Prolog.
Em geral, o ponto central é otimizar entre várias alternativas possíveis, e não tenho certeza se Transformers são adequados para isso.
O papel das técnicas da família dos LLMs parece estar mais em traduzir descrições em linguagem natural para programas executáveis, mas o Prolog também já é bem próximo disso, já que originalmente foi projetado para processamento clássico de linguagem natural.
Tradução automática antes exigia uma decodificação gramatical complexa usando busca, mas hoje usamos Transformers com uma decodificação muito mais simples e praticamente sem necessidade de busca.
Agora talvez dê para chegar até estruturas totalmente recursivas.
A ideia seria aprender heurísticas de busca de arquitetura neural (NAS) com os melhores modelos preditivos atuais e encontrar novos blocos de redes neurais melhores que transformer ou mamba.
A singularidade está chegando…
Se você se interessa por jogos do tipo Sokoban, vale olhar https://thinky.gg
Há uma variante de Sokoban interessante chamada Sokopath e outra variante NP-difícil chamada Pathology, cujo objetivo é ir do ponto A ao ponto B no menor número de passos.
A comunidade tentou criar vários solucionadores, mas fica muito difícil quando a grade passa de 5x5, e a comunidade do thinky também encontrou, por simulated annealing, níveis interessantes com número máximo de passos muito alto.
“Redução de 26,8% nas etapas de busca em relação à busca A* padrão”
Ou seja, em Sokoban é só um pouco melhor que A*, que está longe do estado da arte (https://festival-solver.site/)
Não sei o que há de impressionante neste artigo nem por que ele foi parar no Hacker News.
Mas, se houver outras restrições aproveitáveis no domínio em que se busca, é possível superar o A*.
Por exemplo, o Jump Point Search explora propriedades de buscas em grades nas quais só se pode mover de certas maneiras.
Seria útil ter um algoritmo geral de busca que consiga explorar “automaticamente” e de forma eficaz características especiais do domínio subjacente, sem que uma pessoa precise analisá-las manualmente.
O A* é mais próximo de uma solução básica “ingênua”, e eles não ficaram pensando diretamente no projeto do algoritmo.
É bastante impressionante que um Transformer encoder-decoder simples consiga fazer isso.
“Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
Este artigo é interessante como exemplo de uso de Transformers para tomada de decisão; não me importo muito se ele está no nível do A* neste momento.
Claro que há versões fortes e fracas dessa hipótese, e a versão forte provavelmente não é verdadeira, mas, na medida em que parecemos estar nos aproximando de “uma verdadeira maneira” pela qual a natureza aprende as coisas, isso me parece uma notícia importante.
Se Transformers conseguem planejar, isso talvez signifique que, para a inteligência artificial geral, só precisamos de um treinamento melhor.
Também é necessário aprendizado online, além de várias outras camadas.
Para aprendizes auditivos, há uma versão deste artigo em formato de audiolivro resumido.
https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f
Sou bastante otimista quanto ao uso de heurísticas aprendidas em algoritmos discretos como A*, Focal search e várias famílias de programação linear inteira.
Na maioria das bibliotecas modernas de otimização discreta, como CPLEX, a diferença de desempenho é explicada por heurísticas e ajustes.
Substituir rotinas de busca ótima bem compreendidas por uma abordagem de aprendizado ponta a ponta me convence menos, mas talvez isso seja uma preocupação à toa.
Ainda assim, parece que os autores perderam essa oportunidade.
Acho que também vou resolver jogo da velha com Transformers e pedir dinheiro a VCs.
Talvez daqui a alguns anos todo mundo esteja escrevendo sobre o quanto código de verdade é mais eficiente que IA ;)
Se aprendermos uma heurística admissível, dá para manter o desempenho no pior caso, e esse sempre foi o critério desses algoritmos.
Não é nada raro encontrar soluções que sejam mais rápidas nos casos médios ou p99, mas que não ofereçam garantias no pior caso.
Fico curioso se alguém está compilando uma lista de algoritmos clássicos ou problemas NP-completos que passaram a ser executados melhor com deep learning.