17

I'm trying to understand a few things about neural networks. First, after looking around on the web, it seems that there is no way to compute a (discrete) Fourier transform through a neural network. You can hack it by hard-coding the thing to include the Fourier constants for the transform and then get a decent result. Why can the machine not figure these out by itself?

Brannon
  • 5,324
  • 4
  • 35
  • 83
  • I haven't seen this fact before (but I'm not a neural network expert). Could you give a few references? I see one paper that claims this, but doesn't make a strong case. – tom10 May 07 '12 at 05:29
  • 2
    They can learn DFT just fine. Make a single dense layer, linear (with no activation function), same number of outputs as inputs (one half of inputs/outputs holds real part, one half holds imaginary part) and train it on complex white noise, before and after FFT. It will figure out all the coefficients (which look cool when plotted). It won't be as computationally efficient as an FFT, but it demonstrates that neural networks can figure out frequency spectra on their own. – endolith Aug 08 '18 at 16:21
  • 2
    Here's an example: https://gist.github.com/endolith/98863221204541bf017b6cae71cb0a89 – endolith Aug 10 '18 at 01:34

3 Answers3

17

A DFT is a linear operator. Some neural networks have a sigmoid, RLU, or other non-linear element in the computation path, which might make it harder to simulate a linear operator closely enough.

Added: A full DFT is an N by N matrix multiplication. A neural net has to be big enough to represent that many multiplications (at minimum O(NlogN)).

hotpaw2
  • 70,107
  • 14
  • 90
  • 153
  • I can use a linear activation function. You think that's all it takes? Sin/Cos don't take me down a linear path of thinking by default. – Brannon Apr 27 '12 at 03:27
  • 1
    I'm giving the bounty here because I think this response was the closest to an answer of the question. Thanks everyone. – Brannon May 12 '12 at 15:20
  • 1
    Sin/Cos functions can be approximated by a polynomial, and it might be possible to train a (large enough) neural network to approximate those polynomials. But that NN is likely bigger/slower than a hard-coded FFT. – hotpaw2 Jan 15 '16 at 01:22
3

I think I found a research paper on this topic: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.9688&rep=rep1&type=pdf

It says that "in order to achieve a neural network [that] processes a DFT, a strategy has to be applied which maps the mathematical formula of the DFT to the structure of a neural network", and it seems that they got it to work (section 6).

Riking
  • 2,389
  • 1
  • 24
  • 36
2

As I understand it, a neural network is just a classification method that "learns". To solve a problem using neural networks you need:

  1. Define the classifier inputs
  2. Define the classifier outputs
  3. Provide a training set: it is a set of pairs (input, output)
  4. Choose a topology (how many layers, how many neurons per layer..) and the function individual neurons will use to convert inputs into outputs

After the neural network is trained, given a new input, the neural network produces an output. How good the output is depends on how "good" was the training. Typically, how representative of the data is the training dataset. This technique can be very useful when attempting to solve classification problems in which there is an unknown relationship between inputs and outputs.

Fast Fourier Transform is just a function. You can have FFT in one dimesion, which is applied to one dimensional phenomena like a sound wave. In this case you pass a vector of values (samples of the intensity of the sound wave) and get back a vector of frequencies. More specifically, the amplitude of harmonics of different frequencies that when composed produce the original sound wave. In two dimensions, FFT takes as input a matrix. For a picture, for example, it could be color intensity at the points in a grid. FFT transforms this into a matrix of harmonics. The length of the vector, or the order of the matrix are given by the sampling rate of the orignal signal.

To apply neural networks to compute FFT:

  1. The algorithm to calculate FFT in 1 and 2 dimensions is well defined. Its complexity is O(n log n), which makes it very efficient. The neural network implementation would need to be very efficient (parallelism?) to justify using it.
  2. If you change your sampling rate you need to retrain your neural network: let's assume that you have a tained network that calculates FFT for a given sampling rate, if you reduce significantly the sampling rate, the neural network will "overfit" the data, and viceversa.

With all this, I think neural networks can fit very well a specific implementation of FFT as long as the parameters (sampling rate...) do not change.

j0aqu1n
  • 1,013
  • 7
  • 14
  • couple issues here: 1. *More specifically, the amplitude of harmonics of different frequencies that when composed produce the original sound wave.* not quite true. output of fft are complex numbers. each complex number represents amplitude and phase, but in its raw form, isn't quite that. 2. when people say harmonics, they mean integer multiples of a fundamental frequency (http://en.wikipedia.org/wiki/Harmonic). in fact FT gets you sampled frequencies only up to Nyquist, so *FFT transforms this into a matrix of harmonics* is not true. – thang Feb 10 '13 at 02:41