Very interesting idea.
The FFT Strikes Back: An Efficient Alternative to Self-Attention
151–160 of 175 posts
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#152Earlier quoted context omitted.
A cartoon: To form a coherent idea you need to coordinate a lot of tokens. In other words, ideas are long-distance correlations between tokens. Ideas are the long-wavelength features of streams of tokens. Is it exactly right? No. But as a cartoon it can motivate exploring an idea like this.
Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.
This way you end up with time dilated convolutional networks [1].
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#153hm. nothing that happens in the fourier domain can touch the phases, which seems like a constraint that would change the behavior of other layers.
the default bias of -0.1 with relus and what i would expect to be a flattish spectrum also seems like it would make for a sparse representation in the fourier domain.
i assume this is learning the text embeddings at training time, if so, i'd be curious how the constraints of going through the fft and filtering magnitudes would/could change how the embeddings look.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#154Earlier quoted context omitted.
Yeah basic math space transformation sandwich : 1) turn data into another space 2) operate in that space 3) transform back into original space. To optimize this, optimize each step and work as much as possible in the most efficient space
Remains to be seen how lossy the transformations are. We lose a lot of data in DSP (aka “media”) doing too much.
ReLU throws away half of data. Yet it works.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#155How does this compare with Mamba? Intuitively it feels like this should have similar performance to Mamba, but the math is a lot simpler and easier to understand.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#156Earlier quoted context omitted.
FFT is only O(N log N) for a vector of length N WRT to matrices for an N by N matrix it would be like O(N^2 log N) you would perform FFT for each row or column
Thank you for that catch. I still think we are comparing ASIC matmul hardware to non ASIC FFT hardware. The given TPU hardware is doing 256x256 matrix multiplication in linear time by using 256x256 multiplier grids. FFT ASIC could like do the same thing but be able to handle a much higher N size before memory becomes the bottleneck.
anything is "constant" time if you build big enough hardware and if it's fixed size.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#157Basically leverages convolution theorem[0]: expensive convolutions in direct space becomes simple multiplications in reciprocal space, and vice versa. Whereever you have a convolution operation on your data, transform them to the conjugate domain to turn it into multiplication. In other words, work in the domain that is natural to your data. [0] https://en.wikipedia.org/wiki/Convolution_theorem
Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…
It is true it isn't numerically stable and a FFT isn't entirely reversible. I think to get an idea about how frequency data relates to attention is to look at JPEG. Images tend to make understanding the concept easier. For JPEG a cosine transformation is used instead of a Fourier transformation, but the principle is the same.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#158What I don't get about attention is why it would be necessary when a fully connected layer can also "attend" to all of the input. With very small datasets (think 0 - 500 tokens), I found that attention makes training longer and results worse. I guess the benefits show up with much larger datasets. Note that I'm an AI noob just doing some personal AI projects, so I'm not exactly a reference.
[deleted]
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#159Earlier quoted context omitted.
Mamba is O(n). But I guess it has other drawbacks.
Yes, in Mamba accuracy seems to goes down and has trouble in exact token recall. But, I would say it might be good for very power efficient edge deployment, and ultra long contexts.
Mamba is solving a different problem than transformers.
What Mamba does is take an initial state s_0 and an input u_0, to produce a new state s_1 and an output o_1. It's basically modeling a very complicated state machine. I can easily think of half a dozen applications where this is exactly what you want and it is better than transformers, but LLMs are not among them. Essentially most control problems boil down to what Mamba does. In fact, I would say that Mamba as an architecture is probably the non-plus ultra for modeling mechanical system dynamics.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#160Earlier quoted context omitted.
> Why not, for example, a wavelet transform. That is a great idea for a paper. Work on it, write it up and please be sure to put my name down as a co-author ;-)
Or for that matter, a transform that's learned from the data :) A neural net for the transform itself!
That would be super cool if it works! I’ve also wondered the same thing about activation functions. Why not let the algorithm learn the activation function?