O contra-ataque da FFT: uma alternativa eficiente ao Self-Attention

• O mecanismo tradicional de Self-Attention tem complexidade O(n²), o que limita sua escalabilidade para sequências longas
• Este artigo propõe o FFTNet, que utiliza a Fast Fourier Transform (FFT)
• O FFTNet realiza a mistura global de tokens com complexidade de tempo O(n log n)
• Introduz filtros espectrais aprendíveis e a função de ativação modReLU no domínio da frequência para destacar componentes de frequência importantes
• Em experimentos de benchmark no Long Range Arena (LRA) e no ImageNet, mostrou desempenho superior ao Self-Attention tradicional e a modelos com transformação de Fourier fixa

Pesquisas relacionadas

• Complexidade do Self-Attention: modelos Transformer exigem O(n²) de computação, tornando o processamento de sequências longas ineficiente
• Abordagens baseadas em Fourier: modelos como FNet utilizam transformações de Fourier fixas para reduzir a carga computacional, mas têm pouca adaptabilidade à entrada
• Técnicas lineares, esparsas e de aproximação de baixa dimensão: trabalhos como Performer, Linformer e BigBird propõem formas de aproximar o cálculo do Self-Attention
• Técnicas de decomposição com matrizes ortogonais: o uso de transformações ortogonais (incluindo DFT) melhora a estabilidade do treinamento do modelo
• Filtragem espectral adaptativa: ao adicionar filtros aprendíveis a transformações baseadas em FFT, o método se torna mais flexível e expressivo do que abordagens anteriores

FFTNet: técnica de filtragem espectral adaptativa

Motivação

• O Self-Attention tem complexidade O(n²) e é ineficiente em sequências longas
• A FFT opera em O(n log n) e consegue codificar interações globais com eficiência

Metodologia

• Transformação de Fourier (aplicação de FFT)
  • Converte a sequência de entrada para o domínio da frequência para capturar dependências globais com eficiência
• Aplicação de filtro espectral adaptativo
  • Usa um vetor de contexto global para gerar filtros aprendíveis e destacar dinamicamente bandas de frequência importantes
• Ativação não linear modReLU
  • Aplica uma ativação baseada em ReLU no domínio de frequência complexo para aumentar a expressividade
• Transformação inversa de Fourier (IFFT)
  • Após aplicar filtragem e ativação aos dados transformados, converte-os novamente para o domínio do tempo

Fundamentação teórica do FFTNet

• Possibilita mistura global de tokens com custo computacional de O(n log n)
• Attention adaptativo: filtros aprendíveis no domínio da frequência ajustam as frequências de acordo com a entrada fornecida
• Maior expressividade com ativação não linear: a aplicação de modReLU permite aprender padrões de alta dimensão além de simples transformações lineares
• Estabilidade garantida com base no teorema de Parseval: preserva a energia do sinal e minimiza a perda de informação

Resultados experimentais

Benchmark Long Range Arena (LRA)

• O FFTNet registrou, no geral, maior precisão do que Transformer e FNet
• Em especial, apresentou melhor desempenho nas tarefas ListOps, Text, Retrieval, Image e Pathfinder, alcançando a maior pontuação média
• O Transformer mostrou alto desempenho em algumas tarefas, mas teve limitações para lidar com dependências de longo prazo
• O FNet também utiliza FFT, mas sua transformação fixa tem pouca adaptabilidade, resultando em desempenho geral inferior
• Em particular, na tarefa Path-X, o Transformer falhou por estouro de memória (OOM), enquanto o FFTNet apresentou desempenho estável

Experimento de classificação no ImageNet

• O Vision Transformer baseado em FFTNet (FFTNetViT) conseguiu manter precisão semelhante à do ViT tradicional, reduzindo bastante a carga computacional (FLOPs)
• No modelo Base, o FFTNetViT usou cerca de 38% menos FLOPs que o ViT e ainda apresentou um leve aumento de precisão
• Nos modelos Large e Huge, o FFTNetViT também manteve desempenho semelhante ao ViT com menor custo computacional
• Isso confirma que o FFTNetViT oferece alta eficiência computacional

Estudo de ablação (análise da importância de cada componente)

• O impacto de diferentes componentes do FFTNet no desempenho do modelo foi analisado removendo cada um deles
• Quanto mais componentes principais do FFTNet eram removidos, maior era a tendência de queda na precisão
  • Remoção do spectral gating: a precisão caiu levemente ao perder a capacidade de destacar frequências específicas
  • Remoção do módulo adaptativo: a precisão caiu ainda mais ao perder a capacidade de ajustar dinamicamente os filtros de acordo com a entrada
  • Uso de convolução no lugar de FFT: a maior queda de desempenho ocorreu com a perda da capacidade de misturar informação global de forma eficiente
• Isso mostra que cada componente do FFTNet desempenha papel importante na melhora de desempenho

Conclusão

• O FFTNet é uma alternativa com melhor eficiência computacional que o Self-Attention
• Ao combinar filtros espectrais adaptativos e modReLU no domínio da frequência, oferece forte poder de representação
• Os resultados experimentais mostram desempenho e eficiência superiores aos modelos tradicionais de Self-Attention no LRA e no ImageNet
• Mantém complexidade O(n log n) e ainda entrega desempenho no nível do Self-Attention, o que o favorece no processamento de sequências longas
• O Vision Transformer baseado em FFTNet (FFTNetViT) também alcança desempenho semelhante ao ViT com menos FLOPs

• Repositório de código: Link do GitHub

[GN⁺]

Comentários do Hacker News

• Basicamente usa o teorema da convolução: convoluções caras no espaço direto viram multiplicações simples no espaço dual

  • Quando há uma operação de convolução nos dados, eles são transformados para o domínio conjugado para convertê-la em multiplicação
  • Ou seja, trabalha-se nos dados em um domínio natural para eles

• O Google apresentou em 2022 a ideia "FNet: Mixing Tokens with Fourier Transforms"

  • Depois descobriram que as TPUs deles eram mais rápidas em multiplicação de matrizes do que em FFT na maioria dos cenários

• A transformada de Fourier é aplicada na dimensão dos "tokens". Mas em muitas aplicações essa dimensão não tem significado

  • Por isso, os transformers são uma ótima opção para lidar com dados invariantes a permutação
  • Gostaria de ver mais experimentos com transformadas de Fourier sobre grupos finitos menos conhecidos
  • Se isso virar a próxima grande tendência dos LLMs, fico curioso sobre como seria fácil integrar isso em motores de inferência como vLLM, llama.cpp etc.

• A matemática é difícil demais para entender. Queria saber se alguém consegue explicar em inglês simples como isso é equivalente ao mecanismo de atenção, de que frequências está falando e como codifica relações posicionais entre tokens

• Não vejo como encaixar mascaramento causal nesse framework. Também não há menção a embeddings posicionais, então a implementação de autoatenção com a qual estão comparando parece ser NoPE não causal

  • Se os resultados estivessem perto do estado da arte, o autor provavelmente teria mencionado isso

• Não há nenhuma menção ao Hyena Operator, que já demonstrou mistura de contexto completo em O(n log n) alguns anos atrás

• Na era da telemetria, acho um grande erro não aplicar FFT à telemetria em nuvem para encontrar epiciclos e sistemas quase estáveis antes de causarem drama

  • "Os SLAs têm maior probabilidade de serem violados 23–25 minutos após o deploy do serviço. Será que dá para descobrir por quê?... ah, não."

• Fico me perguntando se alguém tem uma intuição de por que ver as coisas no domínio da frequência ajuda

  • Entendo o termo DC, mas não esperaria que os dados de entrada fossem periódicos a ponto de outras frequências terem significado

• Entendo mais ou menos a notação Big O, mas, como a maioria das coisas ligadas a computação ou engenharia elétrica, isso também é difícil de entender

  • Como alguém muito fraco em matemática, invejo as pessoas que conseguem entender ou aprender essas coisas
  • O que sei sobre FFT é que ela transforma sinais, é usada em algum processamento de sinais e teve papel importante na detecção de explosões nucleares no passado

• Não entendo por que a atenção é necessária. Uma camada totalmente conectada também pode "prestar atenção" a todas as entradas

  • Em datasets muito pequenos (0 - 500 tokens), a atenção faz o treino demorar mais e piora os resultados
  • Parece que as vantagens aparecem em datasets maiores
  • Sou iniciante em IA e estou fazendo um projeto pessoal de IA, então não é uma referência muito precisa