Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The FFT Strikes Back: An Efficient Alternative to Self-Attention

arxiv.org

Post reply on HN
Print view View original

11–20 of 175 posts

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#11

Post by iNic »

pointlessone wrote: post #5

OK, I admit that the math flies way over my head and I barely understand the text around the math. Can someone please explain (in basic English) how this is equivalent to attention mechanism? What friquencies does it talk about? How does it encode positional relations between tokens?

- The Fourier Transform is an invertable operator (i.e. it acts on functions, in the case of matrices both functions and operators are themselves matrices). It transforms into what we call frequency space.

- This is most intuitive for signal analysis or images [1].

- Frequency space is inherently "complex", i.e. represented by complex numbers.

- Frequencies have the advantage that they take a "global" view of the problem.

- This mechanism is not equivalent to the attention mechanism. There is definitely a trade-off.

- But it is possible that it captures many of the important relationships that attention capture.

- I do not have good intuition for modReLU right away, but it seems important because it modifies the frequencies but preserves the inverse Fourier transform.

[1]: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#12

Post by cs702 »

TL;DR:

1. Take FNet (https://arxiv.org/abs/2105.03824).

2. Replace the fixed (frequency-domain) convolution filter with one that is dynamically computed from the data.

3. Apply non-linear functions to both real and imaginary components, before mapping the convolved data back to the time domain.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#14

Post by pointlessone »

jampekka wrote: post #6
pointlessone wrote: post #5

OK, I admit that the math flies way over my head and I barely understand the text around the math. Can someone please explain (in basic English) how this is equivalent to attention mechanism? What friquencies does it talk about? How does it encode positional relations between tokens?

The actual mechanism at least is quite simple. Essentially it takes the FFT of the input embeddings, multiplies it elementwise with weights that are gotten from the input embeddings using an MLP (plus a constant (but learnable) bias) and then runs it through an activation function and finally takes the inverse FFT. The "frequencies" are probably something quite abstract. FFT is often used in ways where there aren't r…

I’m still confused. Does it treat the input tokens as a sampled waveform?

I mean, say I have some text file in ASCII. Do I then just pretend it’s raw wav and do FFT on it? I guess it can give me some useful information (like does it look like any particular natural language or is it just random; sometimes used in encrytion analysis of simple substitution cyphers). It feels surprising that revers FFT can get a coherent output after fiddling with the distribution.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#15

Post by jampekka »

pointlessone wrote: post #14
jampekka wrote: post #6

Earlier quoted context omitted.

The actual mechanism at least is quite simple. Essentially it takes the FFT of the input embeddings, multiplies it elementwise with weights that are gotten from the input embeddings using an MLP (plus a constant (but learnable) bias) and then runs it through an activation function and finally takes the inverse FFT. The "frequencies" are probably something quite abstract. FFT is often used in ways where there aren't r…

I’m still confused. Does it treat the input tokens as a sampled waveform? I mean, say I have some text file in ASCII. Do I then just pretend it’s raw wav and do FFT on it? I guess it can give me some useful information (like does it look like any particular natural language or is it just random; sometimes used in encrytion analysis of simple substitution cyphers). It feels surprising that revers FFT can get a coheren…

It embeds them first into vectors. The input is a real matrix with (context length)x(embedding size) dimensions.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#16

Post by xeonmc »

pointlessone wrote: post #14
jampekka wrote: post #6

Earlier quoted context omitted.

The actual mechanism at least is quite simple. Essentially it takes the FFT of the input embeddings, multiplies it elementwise with weights that are gotten from the input embeddings using an MLP (plus a constant (but learnable) bias) and then runs it through an activation function and finally takes the inverse FFT. The "frequencies" are probably something quite abstract. FFT is often used in ways where there aren't r…

I’m still confused. Does it treat the input tokens as a sampled waveform? I mean, say I have some text file in ASCII. Do I then just pretend it’s raw wav and do FFT on it? I guess it can give me some useful information (like does it look like any particular natural language or is it just random; sometimes used in encrytion analysis of simple substitution cyphers). It feels surprising that revers FFT can get a coheren…

Do keep in mind that FFT is a lossless, equivalent representation of the original data.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#17

Post by jampekka »

iNic wrote: post #11
pointlessone wrote: post #5

OK, I admit that the math flies way over my head and I barely understand the text around the math. Can someone please explain (in basic English) how this is equivalent to attention mechanism? What friquencies does it talk about? How does it encode positional relations between tokens?

- The Fourier Transform is an invertable operator (i.e. it acts on functions, in the case of matrices both functions and operators are themselves matrices). It transforms into what we call frequency space. - This is most intuitive for signal analysis or images [1]. - Frequency space is inherently "complex", i.e. represented by complex numbers. - Frequencies have the advantage that they take a "global" view of the pro…

modReLU seems to just increase the magnitude of the input value, and rotate it to the original polar angle. With clipping off negative magnitudes.

Or equivalently rotates a (real) bias term with the input angle and adds that into the original.

  (abs(z) + c)*exp(i*arg(z)) = abs(z)*exp(i*arg(z)) + c*exp(i*arg(z)) = z + c*exp(i*arg(z))

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#18

Post by frodo8sam »

yagizdegirmenci wrote: post #10

Google introduced this idea in 2022 with "FNet: Mixing Tokens with Fourier Transforms" [0]. Later they found out that, performance of their TPU(s) for matrix multiplication was faster than FFT in the most scenarios. [0]: https://arxiv.org/abs/2105.03824

I would guess that the FFT scales better as you increase the number of tokens in the context window. Interesting Google's models outperform their competitors on context size.
Post reply on HN