16 ms·

The Fourier transform is a neural network

267 points by montebicyclelo 5y ago

threatripper 5y ago
The Fourier transformation is a special case of a linear transformation. Linear neural networks can represent any linear transformation. Both can also be expressed as matrix multiplication. It's not really all that surprising if you know some of the math behind neural networks, matrix algebra, linear transformations or the Fourier transformation.
- amelius 5y ago
  Yes but this article shows that the matrix coefficients of the Fourier transform can be learned.
  - threatripper 5y ago
    This is also not really surprising for a single layer neural network.
    - visarga 5y ago
      It might not be surprising when they implemented it by supervised learning, but when they also solved it by reconstructing the input it was like a rediscovery.
  - madhadron 5y ago
    That's because "learning" in neural networks is a fancy way of saying "curve fitting."
- amcoastal 5y ago
  I dont think its surprising but its definitely a cool little exercise. Somewhat aside of the content of the post, I could see some use cases where specifically implementing DFT layers in your architectures could lead to improved performance over using just the raw inputs or activations. Noisy datasets, or synthetic data based transfer learning come to mind as potential uses for the DFT as a step in your ML pipeline.
  - threatripper 5y ago
    There is the FFT in TensorFlow already: https://www.tensorflow.org/api_docs/python/tf/signal/fft https://www.tensorflow.org/api_docs/python/tf/signal/fft
    - amelius 5y ago
      And FFT (Fast Fourier Transform) is more efficient than matrix multiplication (EDIT: by a matrix with Fourier elements).
      - mochomocha 5y ago
        This is analogous to saying "an umbrella is better than a toaster". They are two different things.
        ok123456 5y ago
        You can implement a DFT with matrix multiplication using the vandermonde matrix with roots of the unitary polynomial as the basis.
        amelius 5y ago
        Not if you perform these operations in order to obtain a Fourier transform.
        cdavid 5y ago
        Fourier transform, more exactly DFT, is a special case of matrix multiplication, when seen as a linear operator. The fact that you can do operations faster than the usual N*2 matrix / vector operation is due to the specific form of the underlying matrix (Van Der Mont matrix). So they are not that different: the specific structure of the Fourier basis allows for more efficient matrix * vector operation.
        deleted 5y ago
        [deleted]
- thearn4 5y ago
  I've come to internalize the Fourier transform as a type of sparse matrix algorithm. I.e. something that implements a particular matrix-vector product without requiring explicit construction of said matrix.
  - srean 5y ago
    And pushing the parantheses to factor out common subexpressions. Essentially exploiting the distributive law
  - enchiridion 5y ago
    Do you mean the FFT? I've been trying to wrap my head around the Fourier transform lately, and I can see the matrix connection to an FFT, but not the Fourier transform in general.
    - bonoboTP 5y ago
      The Fourier transform performs a change of basis into the eigenbasis of convolution. It's linear and so in the discrete case can be expressed as matrix multiplication (every discrete linear operation is expressible as matmul).
- amatic 5y ago
  On the other hand, if you don't yet know a lot of NN math, like me, it is super surprising. Definitely a cool way to connect FFT and NNs.
omarhaneef 5y ago
Here is the special sauce: “We can consider the the discrete Fourier transform (DFT) to be an artificial neural network: it is a single layer network, with no bias, no activation function, and particular values for the weights. The number of output nodes is equal to the number of frequencies we evaluate.” A single layer neural network is a sum of products, the basic Fourier equation is a sum of products. In this view there are lots of single layer neural networks out there. For me, it’s the training algorithm (backprop) that sets apart the neural net.
- 29athrowaway 5y ago
  Biological neural networks do not use backpropagation, or at least, there's no evidence of that yet. Backpropagation is a placeholder for stuff we don't understand.
  - deleted 5y ago
    [deleted]
  - cl3misch 5y ago
    Isn't "backpropagation" just a synonym for the partial derivative of the scalar cost function with respect to the weights? And in the mathematical formulation of biological neural networks these derivatives can't be computed analytically. Your comment sounds like "backpropagation" is some kind of natural phenomenon.
    - 29athrowaway 5y ago
      > Your comment sounds like "backpropagation" is some kind of natural phenomenon. No it's not, read again.
  - ta988 5y ago
    Not exactly the same kind of backpropagation but signals fly the other way in neurons as well https://en.wikipedia.org/wiki/Neural_backpropagation https://en.wikipedia.org/wiki/Neural_backpropagation
  - 5y ago
ellisv 5y ago
Neural networks can learn many things but I can't imagine a practical use-case of this.
- killerstorm 5y ago
  I guess it is mostly an illustration that time-domain => frequency-domain transformation is trivial for ANNs. And e.g. it won't make any sense to pre-process your signal with FFT before training ANN since it will do it itself if needed.
  - raphaelj 5y ago
    Well, you can still probably reduce the training computational cost by feeding the additional FFT features to your NN.
    - ellisv 5y ago
      The Fourier transform layer might not be the immediate hidden layer.
  - ellisv 5y ago
    That's a fair point. My assumption was that the neural network isn't going to be as efficient at the FFT but the article doesn't include that type of assessment.
    - killerstorm 5y ago
      NN is doing matrix multiplications anyway. That's what it does, basically. The property of matrix multiplications is that they are composable, i.e. `X * (Y * z) = (X * Y) * z` that is, in the end you only need one matrix. So what this means in practice is that you have FFT for free. NN is doing a matrix multiplication anyway. Discrete time Fourier Transform is a matrix multiplication. Thus it can simply fold DTFT together with whatever other transform it is doing - it doesn't cost anything.
- SuchAnonMuchWow 5y ago
jhidding 5y ago
Next exercise: implement the fast Fourier transform as a multi-layered network.
- threatripper 5y ago
  This could be highly interesting. Especially when starting with the FFT butterfly structure for connections and the corresponding weights as network initialization and then adapting that to real data via training.
- mensetmanusman 5y ago
  This is a great idea, I bet one could find a bit-faster fftw that would be close enough for many applications, but it would apply a statistical approach to each weight.
- wiggle_woof 5y ago
  Nice idea. Turns out, doing this works well and has some nice properties https://dawn.cs.stanford.edu/2019/06/13/butterfly/ https://dawn.cs.stanford.edu/2019/06/13/butterfly/
Aardwolf 5y ago
So is the identity transform...
- srean 5y ago
  I wish your comment is voted up. Where do we go next ? -- look addition is a neural network, look weighted average is a neural network, look linear regression, logistic regression, Poisson regression are neural networks ...
  - Certhas 5y ago
    I have definitely seen regressions referred to as linear machine learning. Not even kidding.
    - nikk1 5y ago
      Regression is an approach to machine learning https://en.wikipedia.org/wiki/Machine_learning#Regression_analysis https://en.wikipedia.org/wiki/Machine_learning#Regression_an...
    - bonoboTP 5y ago
      So? Machine learning is not some buzzword fad. Regression is part of ML for sure. Some people seem to think ML means fancy deep learning GPT-3 transformer running on a TPU farm. Actually ML is a discipline that has existed for several decades and has various theoretical results too, including VC theory etc. It is also not the same as statistics. They are adjacent but different fields.
      - Certhas 5y ago
        Yeah, but no. It definitely is a buzzword that randomly gets attached to every method of data analysis these days. If you disagree, then please give me a definition that is both distinct from statistics but also means that Regression is an ML technique. BTW, that doesn't mean there isn't also very substantial work done under the umbrella term. Regression analysis was first introduced by Legendre in the early 19th century. I never would have dreamed to pretend it is Machine Learning 10 years ago when the term ML was still used somewhat more sparingly, and carried a bit more meaning... But "I will use ML to analyse the data" gets more funding than "I will run a regression on the data".
cl3misch 5y ago
> We can consider the the discrete Fourier transform (DFT) to be an artificial neural network: it is a single layer network, with no bias, no activation function, and particular values for the weights. So this post essentially shows that the Fourier transform is a linear combination.
- mhh__ 5y ago
  Hammer meet "nail"
cblconfederate 5y ago
If the fourier transform is written as two real parts, the universal approximation theorem says it can be used to approximate any function, the same way NNs do
cantagi 5y ago
Great post! I once had to port a siamese neural network from Tensorflow to Apple's CoreML to make it run on an iPhone. Siamese neural networks have a cross convolution step which wasn't something CoreML could handle. But CoreML could multiply two layer outputs element-wise. I implemented it using a fourier transform (not a fast fourier transform), with separate re and im parts, since a fourier transform is just a matrix multiplication, and convolution is element-wise multiplication in the fourier domain. Unsurprisingly it was very slow.
photonemitter 5y ago
I'll leave these here: https://en.wikipedia.org/wiki/Multiresolution_analysis https://en.wikipedia.org/wiki/Multiresolution_analysis https://en.wikipedia.org/wiki/Discrete_wavelet_transform https://en.wikipedia.org/wiki/Discrete_wavelet_transform And as a lot of people have mentioned in here, DFT is pretty much implicated in neural networks already because of the mathematics (especially in convolutional/correlational neural networks, which often make use of the convolution theorem (which is "just" fourier coefficient multiplication) to do the convolution) Extending this post it seems more interesting to look more generally at the correspondence with wavelet-transforms.
- dplavery92 5y ago
  >especially in convolutional/correlation neural networks, which often make use of the convolution theorem to do the convolution Is this true? With the learned filters being so much smaller than the input imagery/signals, and with "striding" operations and different boundary conditions being wrapped into these algorithms, it doesn't seem like a natural fit.
phonebucket 5y ago
That was a fun read. While it might be unsurprising to some, it's a testament to breadth of applications of modern machine learning frameworks. I enjoyed this sentence in particular. > This should look familiar, because it is a neural network layer with no activation function and no bias. I thought it should look familiar because it's matrix multiplication. That it looks like a neural network layer first and foremost to some is maybe a sign of the times.
- 6gvONxR4sf7o 5y ago
  > it's a testament to breadth of applications of modern machine learning frameworks. More like a testament to the the breadth of applications of linear algebra. It is absolutely remarkable what we're able to compute and analyze in the form of y = A x (hilbert spaces are a wild invention). But it really isn't a testament to modern ML frameworks in any way. The fourier transform has been easy to compute/fit in this exact way (fourier = linear problem + solving linear problems by optimization) by modern-at-the-time frameworks for over two centuries.
enriquto 5y ago
of course (it's a single fully-connected layer, aka a linear map), but more interestingly, the FFT algorithm can be implemented as a very sparse network of logarithmic depth.
mabbo 5y ago
I love this kind of post. While it's all very posh to scoff while saying "well, obviously!", the author has explained it, demonstrated it, documented it. It's not about proving something new, it's about sharing something neat with the world. It's also well written and emotes a bit of a fun in the telling. I'm reminded of xkcd's "Ten Thousand" principle[0]: (Paraphrased) "For each thing that 'Everybody knows', every day there are, on average, 10,000 people in the US learning it for the first time". Good writing makes the experience better for those learning it for the first time today. [0]https://xkcd.com/1053/ https://xkcd.com/1053/
- Certhas 5y ago
  But it explains the wrong thing. It's a fundamentally ridiculous framing. A basic neural network layer is a linear transformation + constant offset + activation function. Linear transformations are the elementary building block. And Fourier Transform is a quintessential example of a linear transform. But the article doesn't actually discuss that at all. If you don't understand this how will you ever deal with more complicated NN architectures?
- 6gvONxR4sf7o 5y ago
  The problem isn't an "everybody knows" kind of problem. People (myself included) are rolling our eyes because it's the most rube goldbergian way to say it. It's analogous to saying that subtraction is a neural network. Addition and negation are core elements of modern state of the art neural networks, and you can express subtraction as a combination of those two modern neural network techniques. Therefore subtraction is a neural network. The line in the article about the formula y = A x is illustrative: > This [y = A x] should look familiar, because it is a neural network layer with no activation function and no bias. Imagine that as: > This [y = a + b] should look familiar, because it is a neural network layer with no activation function and no bias and no multiplication. Meanwhile, this [y = -x] should also look familiar, because it is a neural network layer with no activation function, no bias, no addition, and only negation. You'd expect that kind of explanation of subtraction if someone had never learned about addition and negation outside of neural networks, but you'd roll your eyes and say it's just such a bizarre way to talk about addition, negation, subtraction, and neural networks.
leecarraher 5y ago
Alt title, can a neural network learn the fast fourier transform?
- SuchAnonMuchWow 5y ago
  the discrete Fourier transform, not the fast fourrier transform: the learned algorithm runs in O(n²) and not O(n*log n)
  - leecarraher 5y ago
    oh then this is just approximating the values of the linear transform. I figured at least they'd use mlp to learn each layer of the FFT butterfly network, and the corresponding weights. What would be of interest would be if you could extend this for n length fft using an RNN network
jl2718 5y ago
A ‘neural’ network is tautologically nonlinear.
cochne 5y ago
This is kind of silly. Neural networks are universal function approximators, meaning any function "is" (more accurately, "can be represented by") a neural network. In the DFT case, it is a linear function so we could get an exact representation. Though there is also nothing stopping you from just saying, f(x) is a neural network, because I can choose my activation function to be f.
- TheRealPomax 5y ago
  If silly but interesting things weren't allowed, there would be no point to having a website like this. The article is a neat exploration of two things that many, many people don't realise are related because they simply don't know the maths involved in either of the two subjects.
  - vletal 5y ago
    Maybe, if the title wan not so overblown the pushback againt the articles premise would not be so hard.
    - TheRealPomax 5y ago
      Sorry, have you seen on the internet? There is no requirement of professionalism: write a catchy title, get people to read what you had to say. HN isn't an academic publishing track, it's a reflection of what the world actually posts on the internet. You're free to not like the titles some people use to get eyeballs on their content, but this was clearly not clickbait warranting removal, and it's certainly not HN's job to police page titles on the wider web: we just upvote the cool content, and if enough people like it, it hits the front page. So really, you're complaining that not enough people on HN mind catchy titles enough to downvote a post based on its cover, rather than the book it links to =)
- volta83 5y ago
  > Neural networks are universal function approximators, Do we have tight error bounds proofs for neural networks as approximators ?
albertzeyer 5y ago
Also interesting/related: In speech recognition, we usually use log Mel features, or MFCC features, which do a Fourier transformation on the raw audio frames. You can also train neural networks directly on the raw audio features. When you do so, you can inspect the weights of the first layer (convolutional layer), and you see that it pretty much learned the short Fourier transformation. https://www-i6.informatik.rwth-aachen.de/publications/download/1097/Tueske-ICASSP-2018.pdf https://www-i6.informatik.rwth-aachen.de/publications/downlo...
pontus 5y ago
Is there anything deep here? There's a parametrized representation of a function and it's being interpreted as a neural network, why is this surprising? It's like saying that Newton's second law is a neural network: F=ma can be written log(F) = log(m) + log(a). Aha, this is a neural network! The inputs are m and a, the first layer is sparsely connected with log activation functions, the second layer is fully connected with an exponential activation function: F = exp(c1 * o1 + c2 * o2) o1 = log(c3 * a + c4 * m) o2 = log(c5 * a + c6 * m) If you feed it enough data you'll find c1=c2=c3=c6=1 and c4=c5=0. But saying that Newton's second law is a Neural Network, while correct, seems a bit deceptive in that it's not a deep idea at all.
- volta83 5y ago
  > But saying that Newton's second law is a Neural Network, while correct, seems a bit deceptive in that it's not a deep idea at all. I guess the point is that neither is the idea of a Neural Network.
  - Nasrudith 5y ago
    A neural network can also be set to learn unconditionally return a fixed value with no learning feedback. I don't think lower bounds on capabilities are very informative. So could many arbitrarily complex arrangements that do massive amounts of work only to discard it and return a constant. An upper bound of what an approach is capable of is more useful. Say no matter how vast a look up table is it will never return a different value for the same input regardless of prior sequence.
- candiodari 5y ago
  Well the point is that it does not make sense to DFT data before feeding it into a multilayered neural network (or calculating the force generated by mass and acceleration as you point out). Those formulas make no sense: the network can just learn them on the fly. In fact you'll find that this does not just work for the Fourier transform, but for any FIR filter (and some other classes), and therefore neural networks can deal with signals and construct low-pass filters, high-pass filters, bandgap filters, ... as required for the task at hand without the network (or it's designer) having any idea at all what is happening. I mean there's some basic assumptions these reasonings make (main one is that you need to feed many discretized values from a time window). Of course, a problem remains: local optima. Just because a neural network can construct a filterbank or do a DFT, doesn't mean that it will actually do it when the situation warrants it. If there's a local optimum without filters ... well, you may get unlucky. It there's many local optima without filters ... sucks to be you.
bigbillheck 5y ago
You can't just point at things and call them 'a neural network'. Linear regression's just learning an affine transform but I think it's misleading and unhelpful to call that a neural network either.
ondrysak 5y ago
Given the fact that fourier basis, can be seen as polynomials on unit circle, this may be intresting for some of you. https://arxiv.org/abs/2008.07669 https://arxiv.org/abs/2008.07669
swiley 5y ago
Anything can be expressed by a neural network to some arbitrary degree of precision. That's the whole point. The hard part isn't expressing the thing but getting the machine to figure out how to express it correctly on it's own. There's also no way to prove your learning algorithm actually works outside of toy problems like this which is why ML is really only good for data mining rather than steering a car.
- eigenket 5y ago
  *anything continuous
ajross 5y ago
Not to be too glib, but as a non-ML person with decent numerics ability: ... did this post just spend a ton of boring math explaining that a neural network has the ability to detect whether an image is bumpy or smooth? I mean, Fourier analysis has a very straightforward "intuitive" interpretation. That's the point of its value in applied domains, after all. Straightforward intuitive things are "neural" by their nature, no?
zeroxfe 5y ago
Taking this one more step forward, generating spectrograms with neural networks: https://0xfe.blogspot.com/2020/03/generating-spectrograms-with-neural.html https://0xfe.blogspot.com/2020/03/generating-spectrograms-wi...
Gravityloss 5y ago
Of course. What about the Haar transform? Or digital filters? It's very much all about the same thing. You compare the original signal with some reference signals, look at how much it correlates. Then you save those correlations only. With the correlations and the reference signals, you can roughly reproduce the original signal. (Extremely paraphrased.)
ktln2 5y ago
Just another example of https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore...
RocketSyntax 5y ago
I think the author's point is that every data transformation can be represented as a neural network. Neural nets are just many degree polynomials.
AndrewGYork 5y ago
One of the questions raised at the end of the article: "Do we ever benefit from explicitly putting Fourier layers into our models?" Has a simple, partial answer here: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.dft.html https://docs.scipy.org/doc/scipy/reference/generated/scipy.l... "...multiplying a vector by the matrix returned by dft is mathematically equivalent to (but much less efficient than) the calculation performed by scipy.fft.fft." fft-as-a-matrix-multiply is much slower to compute than a standard fft, especially on large input.
- modeless 5y ago
  You can do the linear parts of neural nets in the frequency domain, but AFAIK you can't do the nonlinearity, so you have to inverse transform back to the spatial domain for that. The nonlinearity is an absolutely essential part of pretty much every neural net layer, so there is no big win to be had unfortunately. For convolutional nets in particular there are other ways of going faster than a naive matrix multiply, e.g. winograd convolution.
  - aesthesia 5y ago
    But if your network contains a layer whose linear part performs an (approximate) DFT, you will get an efficiency gain by replacing it with an exact FFT. You wouldn't want to use an FFT for most CNNs anyway because the kernels have very small support. Convolution with them is O(n) in the spatial domain as long as you recognize the sparsity.
  - evancox100 5y ago
    Why can't you apply the nonlinear activation functions in the frequency domain? What's stopping this or making it not work?
akrymski 5y ago
I'm really interested in training NNs in the frequency domain: - a ton of data (JPEGs, MPEGs, MFCCs) exists in the compressed form of FFT-ed features - FFTs are hardware encoded/decoded & optimised - FFTs are great at separating signal from noise, leading to a huge reduction in input features (eg JPEG encoded) as compared to raw pixel values - convolutions in the time domain are just multiplications in the frequency domain - converting to log polar coordinates turns them into additions - distance between two log polar coordinates could be the loss function However, I've not had much luck getting a frequency domain network like this to converge. Anyone tried something similar with success?
- mochomocha 5y ago
  I have trained GANs on raw JPEG coefficients with moderate success as a pet project. Read the raw DCT coefficients without decompressing and train in this space. JPEG-decompress the output of the net to reconstruct an image in the pixel space. There are few papers doing similar things for supervised learning tasks iirc
  - akrymski 5y ago
    Using a standard loss function like MSE? Yeah it kinda works when you feed JPEG coefficients into a typical time-domain CNN, but mathematically it seems that if you're using frequencies as inputs, your convolutions should become simple multiplications. Am I wrong?
    - mochomocha 5y ago
      Yep, you can successfully do it without convolutions. Here is a pointer if you want to dig deeper: https://eng.uber.com/neural-networks-jpeg/ https://eng.uber.com/neural-networks-jpeg/ (there's prior art to that, but this one is well written)
- akrymski 5y ago
  I don't see why processing JPEG coefficients directly as input features shouldn't have similar accuracy to a much larger NN using raw pixel data. In particular I'm interested in the efficiency gains from avoiding convolutions and the possibility of running a compressed frequency-domain NN on CPUs.
layoutIfNeeded 5y ago
Ummmm... sure. A layer of a neural network is a linear operator followed by an arbitrary (nonlinear in practice) mapping. Which means that neural networks can trivially implement linear operators (like the Fourier transform) by making the second mapping to be identity. QED
deleted 5y ago
[deleted]
throwawayffffas 5y ago
I have always thought of it the other way around, neural networks are a kind of transform similar to the Fourier transform. But you know, instead of a sum of sinusoid components you get a sum of weighted <insert your activation function>.
TaupeRanger 5y ago
"Multiplication of matrices is a neural network"
peter_retief 5y ago
https://math.stackexchange.com/questions/2569814/fourier-transform-of-sigmoid-function https://math.stackexchange.com/questions/2569814/fourier-tra...
mikewarot 5y ago
I have zero doubt that given sufficient resources ANY function can be learned by a neural network. Why not just initialize part of the layers in a network to do the FFT, or DFT when you're setting up a system to learn, that it doesn't have to waste megawatt hours of power? Consider it a form of discretized / explicit transfer learning. Why not use the fact that you could just set the coefficients in a neural network to do DFTs or FFTs to utilize neural network chips as ersatz DSP chips, without learning? Just like when GPUs turned out to be useful for neural networks, the TPUs will turn out to be useful for DSP and other things. These neural network chips showing up can do a lot of cool things unrelated to AI, if we use them properly.
6gvONxR4sf7o 5y ago
> [with regards to y = A x:] This should look familiar, because it is a neural network layer with no activation function and no bias. This line makes me think this might be satire. Are there really people who see y = A x and think neural networks? Otherwise, a better title would be "The Fourier transform is a linear operation. (neural networks can do linear operations too)" ... which makes it pretty boring.
slver 5y ago
Technically physical reality is also a neural network.
master_yoda_1 5y ago
My fart molecule also have non linear interaction with other atom. So my farting is a neural network too. #bullshitArticle
meiji163 5y ago
> What is the explanation for the flexibility in the weights? How much flexibility is there? most of the terms are on the order of 1/N so on these would be negligible
n_kr 5y ago
People may find this interesting too: https://ocw.mit.edu/courses/mechanical-engineering/2-71-optics-spring-2009/video-lectures/lecture-19-the-4f-system-binary-amplitude-pupil-masks/MIT2_71S09_lec19.pdf https://ocw.mit.edu/courses/mechanical-engineering/2-71-opti...
turtletontine 5y ago
I don't see anything here beyond "neural networks generalize linear operators." (But of course they're more interesting for nonlinear applications) I think neutral nets are such a generalized thing that tons of stuff can be shown to map to them. I saw a talk once about evolution being equivalent to neural networks: consider a genome as a set of neuron weights, and your iterative refinement as new generations in evolution. Maybe there's something deep there, but maybe if you make your model arbitrarily complicated enough you can make it look like any system you want. Which is the whole idea with neural nets.
deleted 5y ago
[deleted]
Vhano 5y ago
this is why linear dynamics should be a basic course before ML/DL. Next week OP discovers Kalman filter... and surprise, surprise!
chobytes 5y ago
...This could be a brilliant technique for collecting funding.
- srean 5y ago
  Mono layer DNNs with a block-chained backpropagated backend

The Fourier transformation is a special case of a linear transformation. Linear neural networks can represent any linear transformation. Both can also be expressed as matrix multiplication. It's not really all that surprising if you know some of the math behind neural networks, matrix algebra, linear transformations or the Fourier transformation.

amelius 5y ago
Yes but this article shows that the matrix coefficients of the Fourier transform can be learned.
- threatripper 5y ago
  This is also not really surprising for a single layer neural network.
  - visarga 5y ago
    It might not be surprising when they implemented it by supervised learning, but when they also solved it by reconstructing the input it was like a rediscovery.
- madhadron 5y ago
  That's because "learning" in neural networks is a fancy way of saying "curve fitting."
amcoastal 5y ago
I dont think its surprising but its definitely a cool little exercise. Somewhat aside of the content of the post, I could see some use cases where specifically implementing DFT layers in your architectures could lead to improved performance over using just the raw inputs or activations. Noisy datasets, or synthetic data based transfer learning come to mind as potential uses for the DFT as a step in your ML pipeline.
- threatripper 5y ago
  There is the FFT in TensorFlow already: https://www.tensorflow.org/api_docs/python/tf/signal/fft https://www.tensorflow.org/api_docs/python/tf/signal/fft
  - amelius 5y ago
    And FFT (Fast Fourier Transform) is more efficient than matrix multiplication (EDIT: by a matrix with Fourier elements).
    - mochomocha 5y ago
      This is analogous to saying "an umbrella is better than a toaster". They are two different things.
      - ok123456 5y ago
        You can implement a DFT with matrix multiplication using the vandermonde matrix with roots of the unitary polynomial as the basis.
      - amelius 5y ago
        Not if you perform these operations in order to obtain a Fourier transform.
      - cdavid 5y ago
        Fourier transform, more exactly DFT, is a special case of matrix multiplication, when seen as a linear operator. The fact that you can do operations faster than the usual N*2 matrix / vector operation is due to the specific form of the underlying matrix (Van Der Mont matrix). So they are not that different: the specific structure of the Fourier basis allows for more efficient matrix * vector operation.
        deleted 5y ago
        [deleted]
thearn4 5y ago
I've come to internalize the Fourier transform as a type of sparse matrix algorithm. I.e. something that implements a particular matrix-vector product without requiring explicit construction of said matrix.
- srean 5y ago
  And pushing the parantheses to factor out common subexpressions. Essentially exploiting the distributive law
- enchiridion 5y ago
  Do you mean the FFT? I've been trying to wrap my head around the Fourier transform lately, and I can see the matrix connection to an FFT, but not the Fourier transform in general.
  - bonoboTP 5y ago
    The Fourier transform performs a change of basis into the eigenbasis of convolution. It's linear and so in the discrete case can be expressed as matrix multiplication (every discrete linear operation is expressible as matmul).
amatic 5y ago
On the other hand, if you don't yet know a lot of NN math, like me, it is super surprising. Definitely a cool way to connect FFT and NNs.

omarhaneef 5y ago

Here is the special sauce: “We can consider the the discrete Fourier transform (DFT) to be an artificial neural network: it is a single layer network, with no bias, no activation function, and particular values for the weights. The number of output nodes is equal to the number of frequencies we evaluate.” A single layer neural network is a sum of products, the basic Fourier equation is a sum of products. In this view there are lots of single layer neural networks out there. For me, it’s the training algorithm (backprop) that sets apart the neural net.

29athrowaway 5y ago
Biological neural networks do not use backpropagation, or at least, there's no evidence of that yet. Backpropagation is a placeholder for stuff we don't understand.
- deleted 5y ago
  [deleted]
- cl3misch 5y ago
  Isn't "backpropagation" just a synonym for the partial derivative of the scalar cost function with respect to the weights? And in the mathematical formulation of biological neural networks these derivatives can't be computed analytically. Your comment sounds like "backpropagation" is some kind of natural phenomenon.
  - 29athrowaway 5y ago
    > Your comment sounds like "backpropagation" is some kind of natural phenomenon. No it's not, read again.
- ta988 5y ago
  Not exactly the same kind of backpropagation but signals fly the other way in neurons as well https://en.wikipedia.org/wiki/Neural_backpropagation https://en.wikipedia.org/wiki/Neural_backpropagation
- 5y ago

ellisv 5y ago

Neural networks can learn many things but I can't imagine a practical use-case of this.

killerstorm 5y ago
I guess it is mostly an illustration that time-domain => frequency-domain transformation is trivial for ANNs. And e.g. it won't make any sense to pre-process your signal with FFT before training ANN since it will do it itself if needed.
- raphaelj 5y ago
  Well, you can still probably reduce the training computational cost by feeding the additional FFT features to your NN.
  - ellisv 5y ago
    The Fourier transform layer might not be the immediate hidden layer.
- ellisv 5y ago
  That's a fair point. My assumption was that the neural network isn't going to be as efficient at the FFT but the article doesn't include that type of assessment.
  - killerstorm 5y ago
    NN is doing matrix multiplications anyway. That's what it does, basically. The property of matrix multiplications is that they are composable, i.e. `X * (Y * z) = (X * Y) * z` that is, in the end you only need one matrix. So what this means in practice is that you have FFT for free. NN is doing a matrix multiplication anyway. Discrete time Fourier Transform is a matrix multiplication. Thus it can simply fold DTFT together with whatever other transform it is doing - it doesn't cost anything.
SuchAnonMuchWow 5y ago

jhidding 5y ago

Next exercise: implement the fast Fourier transform as a multi-layered network.

threatripper 5y ago
This could be highly interesting. Especially when starting with the FFT butterfly structure for connections and the corresponding weights as network initialization and then adapting that to real data via training.
mensetmanusman 5y ago
This is a great idea, I bet one could find a bit-faster fftw that would be close enough for many applications, but it would apply a statistical approach to each weight.
wiggle_woof 5y ago
Nice idea. Turns out, doing this works well and has some nice properties https://dawn.cs.stanford.edu/2019/06/13/butterfly/ https://dawn.cs.stanford.edu/2019/06/13/butterfly/

Aardwolf 5y ago

So is the identity transform...

srean 5y ago
I wish your comment is voted up. Where do we go next ? -- look addition is a neural network, look weighted average is a neural network, look linear regression, logistic regression, Poisson regression are neural networks ...
- Certhas 5y ago
  I have definitely seen regressions referred to as linear machine learning. Not even kidding.
  - nikk1 5y ago
    Regression is an approach to machine learning https://en.wikipedia.org/wiki/Machine_learning#Regression_analysis https://en.wikipedia.org/wiki/Machine_learning#Regression_an...
  - bonoboTP 5y ago
    So? Machine learning is not some buzzword fad. Regression is part of ML for sure. Some people seem to think ML means fancy deep learning GPT-3 transformer running on a TPU farm. Actually ML is a discipline that has existed for several decades and has various theoretical results too, including VC theory etc. It is also not the same as statistics. They are adjacent but different fields.
    - Certhas 5y ago
      Yeah, but no. It definitely is a buzzword that randomly gets attached to every method of data analysis these days. If you disagree, then please give me a definition that is both distinct from statistics but also means that Regression is an ML technique. BTW, that doesn't mean there isn't also very substantial work done under the umbrella term. Regression analysis was first introduced by Legendre in the early 19th century. I never would have dreamed to pretend it is Machine Learning 10 years ago when the term ML was still used somewhat more sparingly, and carried a bit more meaning... But "I will use ML to analyse the data" gets more funding than "I will run a regression on the data".

cl3misch 5y ago

> We can consider the the discrete Fourier transform (DFT) to be an artificial neural network: it is a single layer network, with no bias, no activation function, and particular values for the weights. So this post essentially shows that the Fourier transform is a linear combination.

mhh__ 5y ago
Hammer meet "nail"

cblconfederate 5y ago

If the fourier transform is written as two real parts, the universal approximation theorem says it can be used to approximate any function, the same way NNs do

cantagi 5y ago

Great post! I once had to port a siamese neural network from Tensorflow to Apple's CoreML to make it run on an iPhone. Siamese neural networks have a cross convolution step which wasn't something CoreML could handle. But CoreML could multiply two layer outputs element-wise. I implemented it using a fourier transform (not a fast fourier transform), with separate re and im parts, since a fourier transform is just a matrix multiplication, and convolution is element-wise multiplication in the fourier domain. Unsurprisingly it was very slow.

photonemitter 5y ago

I'll leave these here: https://en.wikipedia.org/wiki/Multiresolution_analysis https://en.wikipedia.org/wiki/Multiresolution_analysis https://en.wikipedia.org/wiki/Discrete_wavelet_transform https://en.wikipedia.org/wiki/Discrete_wavelet_transform And as a lot of people have mentioned in here, DFT is pretty much implicated in neural networks already because of the mathematics (especially in convolutional/correlational neural networks, which often make use of the convolution theorem (which is "just" fourier coefficient multiplication) to do the convolution) Extending this post it seems more interesting to look more generally at the correspondence with wavelet-transforms.

dplavery92 5y ago
>especially in convolutional/correlation neural networks, which often make use of the convolution theorem to do the convolution Is this true? With the learned filters being so much smaller than the input imagery/signals, and with "striding" operations and different boundary conditions being wrapped into these algorithms, it doesn't seem like a natural fit.

phonebucket 5y ago

That was a fun read. While it might be unsurprising to some, it's a testament to breadth of applications of modern machine learning frameworks. I enjoyed this sentence in particular. > This should look familiar, because it is a neural network layer with no activation function and no bias. I thought it should look familiar because it's matrix multiplication. That it looks like a neural network layer first and foremost to some is maybe a sign of the times.

6gvONxR4sf7o 5y ago
> it's a testament to breadth of applications of modern machine learning frameworks. More like a testament to the the breadth of applications of linear algebra. It is absolutely remarkable what we're able to compute and analyze in the form of y = A x (hilbert spaces are a wild invention). But it really isn't a testament to modern ML frameworks in any way. The fourier transform has been easy to compute/fit in this exact way (fourier = linear problem + solving linear problems by optimization) by modern-at-the-time frameworks for over two centuries.

enriquto 5y ago

of course (it's a single fully-connected layer, aka a linear map), but more interestingly, the FFT algorithm can be implemented as a very sparse network of logarithmic depth.

mabbo 5y ago

I love this kind of post. While it's all very posh to scoff while saying "well, obviously!", the author has explained it, demonstrated it, documented it. It's not about proving something new, it's about sharing something neat with the world. It's also well written and emotes a bit of a fun in the telling. I'm reminded of xkcd's "Ten Thousand" principle[0]: (Paraphrased) "For each thing that 'Everybody knows', every day there are, on average, 10,000 people in the US learning it for the first time". Good writing makes the experience better for those learning it for the first time today. [0]https://xkcd.com/1053/ https://xkcd.com/1053/

Certhas 5y ago
But it explains the wrong thing. It's a fundamentally ridiculous framing. A basic neural network layer is a linear transformation + constant offset + activation function. Linear transformations are the elementary building block. And Fourier Transform is a quintessential example of a linear transform. But the article doesn't actually discuss that at all. If you don't understand this how will you ever deal with more complicated NN architectures?
6gvONxR4sf7o 5y ago
The problem isn't an "everybody knows" kind of problem. People (myself included) are rolling our eyes because it's the most rube goldbergian way to say it. It's analogous to saying that subtraction is a neural network. Addition and negation are core elements of modern state of the art neural networks, and you can express subtraction as a combination of those two modern neural network techniques. Therefore subtraction is a neural network. The line in the article about the formula y = A x is illustrative: > This [y = A x] should look familiar, because it is a neural network layer with no activation function and no bias. Imagine that as: > This [y = a + b] should look familiar, because it is a neural network layer with no activation function and no bias and no multiplication. Meanwhile, this [y = -x] should also look familiar, because it is a neural network layer with no activation function, no bias, no addition, and only negation. You'd expect that kind of explanation of subtraction if someone had never learned about addition and negation outside of neural networks, but you'd roll your eyes and say it's just such a bizarre way to talk about addition, negation, subtraction, and neural networks.

leecarraher 5y ago

Alt title, can a neural network learn the fast fourier transform?

SuchAnonMuchWow 5y ago
the discrete Fourier transform, not the fast fourrier transform: the learned algorithm runs in O(n²) and not O(n*log n)
- leecarraher 5y ago
  oh then this is just approximating the values of the linear transform. I figured at least they'd use mlp to learn each layer of the FFT butterfly network, and the corresponding weights. What would be of interest would be if you could extend this for n length fft using an RNN network

jl2718 5y ago

A ‘neural’ network is tautologically nonlinear.

cochne 5y ago

This is kind of silly. Neural networks are universal function approximators, meaning any function "is" (more accurately, "can be represented by") a neural network. In the DFT case, it is a linear function so we could get an exact representation. Though there is also nothing stopping you from just saying, f(x) is a neural network, because I can choose my activation function to be f.

TheRealPomax 5y ago
If silly but interesting things weren't allowed, there would be no point to having a website like this. The article is a neat exploration of two things that many, many people don't realise are related because they simply don't know the maths involved in either of the two subjects.
- vletal 5y ago
  Maybe, if the title wan not so overblown the pushback againt the articles premise would not be so hard.
  - TheRealPomax 5y ago
    Sorry, have you seen on the internet? There is no requirement of professionalism: write a catchy title, get people to read what you had to say. HN isn't an academic publishing track, it's a reflection of what the world actually posts on the internet. You're free to not like the titles some people use to get eyeballs on their content, but this was clearly not clickbait warranting removal, and it's certainly not HN's job to police page titles on the wider web: we just upvote the cool content, and if enough people like it, it hits the front page. So really, you're complaining that not enough people on HN mind catchy titles enough to downvote a post based on its cover, rather than the book it links to =)
volta83 5y ago
> Neural networks are universal function approximators, Do we have tight error bounds proofs for neural networks as approximators ?

albertzeyer 5y ago

Also interesting/related: In speech recognition, we usually use log Mel features, or MFCC features, which do a Fourier transformation on the raw audio frames. You can also train neural networks directly on the raw audio features. When you do so, you can inspect the weights of the first layer (convolutional layer), and you see that it pretty much learned the short Fourier transformation. https://www-i6.informatik.rwth-aachen.de/publications/download/1097/Tueske-ICASSP-2018.pdf https://www-i6.informatik.rwth-aachen.de/publications/downlo...

pontus 5y ago

Is there anything deep here? There's a parametrized representation of a function and it's being interpreted as a neural network, why is this surprising? It's like saying that Newton's second law is a neural network: F=ma can be written log(F) = log(m) + log(a). Aha, this is a neural network! The inputs are m and a, the first layer is sparsely connected with log activation functions, the second layer is fully connected with an exponential activation function: F = exp(c1 * o1 + c2 * o2) o1 = log(c3 * a + c4 * m) o2 = log(c5 * a + c6 * m) If you feed it enough data you'll find c1=c2=c3=c6=1 and c4=c5=0. But saying that Newton's second law is a Neural Network, while correct, seems a bit deceptive in that it's not a deep idea at all.

volta83 5y ago
> But saying that Newton's second law is a Neural Network, while correct, seems a bit deceptive in that it's not a deep idea at all. I guess the point is that neither is the idea of a Neural Network.
- Nasrudith 5y ago
  A neural network can also be set to learn unconditionally return a fixed value with no learning feedback. I don't think lower bounds on capabilities are very informative. So could many arbitrarily complex arrangements that do massive amounts of work only to discard it and return a constant. An upper bound of what an approach is capable of is more useful. Say no matter how vast a look up table is it will never return a different value for the same input regardless of prior sequence.
candiodari 5y ago
Well the point is that it does not make sense to DFT data before feeding it into a multilayered neural network (or calculating the force generated by mass and acceleration as you point out). Those formulas make no sense: the network can just learn them on the fly. In fact you'll find that this does not just work for the Fourier transform, but for any FIR filter (and some other classes), and therefore neural networks can deal with signals and construct low-pass filters, high-pass filters, bandgap filters, ... as required for the task at hand without the network (or it's designer) having any idea at all what is happening. I mean there's some basic assumptions these reasonings make (main one is that you need to feed many discretized values from a time window). Of course, a problem remains: local optima. Just because a neural network can construct a filterbank or do a DFT, doesn't mean that it will actually do it when the situation warrants it. If there's a local optimum without filters ... well, you may get unlucky. It there's many local optima without filters ... sucks to be you.

bigbillheck 5y ago

You can't just point at things and call them 'a neural network'. Linear regression's just learning an affine transform but I think it's misleading and unhelpful to call that a neural network either.

ondrysak 5y ago

Given the fact that fourier basis, can be seen as polynomials on unit circle, this may be intresting for some of you. https://arxiv.org/abs/2008.07669 https://arxiv.org/abs/2008.07669

swiley 5y ago

Anything can be expressed by a neural network to some arbitrary degree of precision. That's the whole point. The hard part isn't expressing the thing but getting the machine to figure out how to express it correctly on it's own. There's also no way to prove your learning algorithm actually works outside of toy problems like this which is why ML is really only good for data mining rather than steering a car.

eigenket 5y ago
*anything continuous

ajross 5y ago

Not to be too glib, but as a non-ML person with decent numerics ability: ... did this post just spend a ton of boring math explaining that a neural network has the ability to detect whether an image is bumpy or smooth? I mean, Fourier analysis has a very straightforward "intuitive" interpretation. That's the point of its value in applied domains, after all. Straightforward intuitive things are "neural" by their nature, no?

zeroxfe 5y ago

Taking this one more step forward, generating spectrograms with neural networks: https://0xfe.blogspot.com/2020/03/generating-spectrograms-with-neural.html https://0xfe.blogspot.com/2020/03/generating-spectrograms-wi...

Gravityloss 5y ago

Of course. What about the Haar transform? Or digital filters? It's very much all about the same thing. You compare the original signal with some reference signals, look at how much it correlates. Then you save those correlations only. With the correlations and the reference signals, you can roughly reproduce the original signal. (Extremely paraphrased.)

ktln2 5y ago

Just another example of https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore...

RocketSyntax 5y ago

I think the author's point is that every data transformation can be represented as a neural network. Neural nets are just many degree polynomials.

AndrewGYork 5y ago

One of the questions raised at the end of the article: "Do we ever benefit from explicitly putting Fourier layers into our models?" Has a simple, partial answer here: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.dft.html https://docs.scipy.org/doc/scipy/reference/generated/scipy.l... "...multiplying a vector by the matrix returned by dft is mathematically equivalent to (but much less efficient than) the calculation performed by scipy.fft.fft." fft-as-a-matrix-multiply is much slower to compute than a standard fft, especially on large input.

modeless 5y ago
You can do the linear parts of neural nets in the frequency domain, but AFAIK you can't do the nonlinearity, so you have to inverse transform back to the spatial domain for that. The nonlinearity is an absolutely essential part of pretty much every neural net layer, so there is no big win to be had unfortunately. For convolutional nets in particular there are other ways of going faster than a naive matrix multiply, e.g. winograd convolution.
- aesthesia 5y ago
  But if your network contains a layer whose linear part performs an (approximate) DFT, you will get an efficiency gain by replacing it with an exact FFT. You wouldn't want to use an FFT for most CNNs anyway because the kernels have very small support. Convolution with them is O(n) in the spatial domain as long as you recognize the sparsity.
- evancox100 5y ago
  Why can't you apply the nonlinear activation functions in the frequency domain? What's stopping this or making it not work?

akrymski 5y ago

I'm really interested in training NNs in the frequency domain: - a ton of data (JPEGs, MPEGs, MFCCs) exists in the compressed form of FFT-ed features - FFTs are hardware encoded/decoded & optimised - FFTs are great at separating signal from noise, leading to a huge reduction in input features (eg JPEG encoded) as compared to raw pixel values - convolutions in the time domain are just multiplications in the frequency domain - converting to log polar coordinates turns them into additions - distance between two log polar coordinates could be the loss function However, I've not had much luck getting a frequency domain network like this to converge. Anyone tried something similar with success?

mochomocha 5y ago
I have trained GANs on raw JPEG coefficients with moderate success as a pet project. Read the raw DCT coefficients without decompressing and train in this space. JPEG-decompress the output of the net to reconstruct an image in the pixel space. There are few papers doing similar things for supervised learning tasks iirc
- akrymski 5y ago
  Using a standard loss function like MSE? Yeah it kinda works when you feed JPEG coefficients into a typical time-domain CNN, but mathematically it seems that if you're using frequencies as inputs, your convolutions should become simple multiplications. Am I wrong?
  - mochomocha 5y ago
    Yep, you can successfully do it without convolutions. Here is a pointer if you want to dig deeper: https://eng.uber.com/neural-networks-jpeg/ https://eng.uber.com/neural-networks-jpeg/ (there's prior art to that, but this one is well written)
akrymski 5y ago
I don't see why processing JPEG coefficients directly as input features shouldn't have similar accuracy to a much larger NN using raw pixel data. In particular I'm interested in the efficiency gains from avoiding convolutions and the possibility of running a compressed frequency-domain NN on CPUs.

layoutIfNeeded 5y ago

Ummmm... sure. A layer of a neural network is a linear operator followed by an arbitrary (nonlinear in practice) mapping. Which means that neural networks can trivially implement linear operators (like the Fourier transform) by making the second mapping to be identity. QED

deleted 5y ago

[deleted]

throwawayffffas 5y ago

I have always thought of it the other way around, neural networks are a kind of transform similar to the Fourier transform. But you know, instead of a sum of sinusoid components you get a sum of weighted <insert your activation function>.

TaupeRanger 5y ago

"Multiplication of matrices is a neural network"

peter_retief 5y ago

https://math.stackexchange.com/questions/2569814/fourier-transform-of-sigmoid-function https://math.stackexchange.com/questions/2569814/fourier-tra...

mikewarot 5y ago

I have zero doubt that given sufficient resources ANY function can be learned by a neural network. Why not just initialize part of the layers in a network to do the FFT, or DFT when you're setting up a system to learn, that it doesn't have to waste megawatt hours of power? Consider it a form of discretized / explicit transfer learning. Why not use the fact that you could just set the coefficients in a neural network to do DFTs or FFTs to utilize neural network chips as ersatz DSP chips, without learning? Just like when GPUs turned out to be useful for neural networks, the TPUs will turn out to be useful for DSP and other things. These neural network chips showing up can do a lot of cool things unrelated to AI, if we use them properly.

6gvONxR4sf7o 5y ago

> [with regards to y = A x:] This should look familiar, because it is a neural network layer with no activation function and no bias. This line makes me think this might be satire. Are there really people who see y = A x and think neural networks? Otherwise, a better title would be "The Fourier transform is a linear operation. (neural networks can do linear operations too)" ... which makes it pretty boring.

slver 5y ago

Technically physical reality is also a neural network.

master_yoda_1 5y ago

My fart molecule also have non linear interaction with other atom. So my farting is a neural network too. #bullshitArticle

meiji163 5y ago

> What is the explanation for the flexibility in the weights? How much flexibility is there? most of the terms are on the order of 1/N so on these would be negligible

n_kr 5y ago

People may find this interesting too: https://ocw.mit.edu/courses/mechanical-engineering/2-71-optics-spring-2009/video-lectures/lecture-19-the-4f-system-binary-amplitude-pupil-masks/MIT2_71S09_lec19.pdf https://ocw.mit.edu/courses/mechanical-engineering/2-71-opti...

turtletontine 5y ago

I don't see anything here beyond "neural networks generalize linear operators." (But of course they're more interesting for nonlinear applications) I think neutral nets are such a generalized thing that tons of stuff can be shown to map to them. I saw a talk once about evolution being equivalent to neural networks: consider a genome as a set of neuron weights, and your iterative refinement as new generations in evolution. Maybe there's something deep there, but maybe if you make your model arbitrarily complicated enough you can make it look like any system you want. Which is the whole idea with neural nets.

deleted 5y ago

[deleted]

Vhano 5y ago

this is why linear dynamics should be a basic course before ML/DL. Next week OP discovers Kalman filter... and surprise, surprise!

chobytes 5y ago

...This could be a brilliant technique for collecting funding.

srean 5y ago
Mono layer DNNs with a block-chained backpropagated backend