The Fourier transform is a neural network
sidsite.com
sidsite.com
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.
I guess the point is that neither is the idea of a Neural Network.
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.
> Just because [...] can construct a filterbank or do a DFT, doesn't mean that it will actually do it when the situation warrants it.
These statements seem in conflict, no?
is false.
"It would be nice if we didn't have to DFT data before feeding it into a multilayered neural network" is true, but a completely different statement.
You can see this most clearly in the auditory system where the incoming signal is transformed into the frequency domain by the cochlea before the signal is received by the epithelial cells.
Neurons absolutely love working in the frequency domain, but they seem to prefer to not be the ones to do the binning in the first place.
Peak neuron firing rates basically only touch the lower bounds of frequencies that need to be processed.
Without the "hardware acceleration" of the cochlea that preprocesses the time domain signals to frequency domain first, basically our whole audio sensorium is out of processing range.
Normal nervous signal transmission speeds are in the order of the speed of sound, switching rates are in Hz range. Voltages are in the 10s of millivolt range.
Additionally there's large variations in neuron spiking rates.
It's encoded in an elegant way.
It has to be, due to the signalling constraints.
It's not like a microphone-based electronic system that's fast enough to directly transmit an analog sample of air pressure changes.
Maybe not a rate.
It can't be "amplitude modulated" because in general signals are pulses.
So it's kind-of digital.
It sometimes can't be a pulse rate encoded signal due to frequency cutoffs.
As far as I understand they've identified several different encoding schemes and will probably find several more.
You can see this clearly if you do an extreme slowdown of a human movement. Then, suddenly, what looks like a smooth movement, like raising an arm (and because of inertia it is smoothed of course), isn't really smooth. A pulse arrives in the muscle, and there is 20ms where the muscle is tensioned, and then it's back to neutral for 100ms. Then another spike arrives, another 20ms where a lot of tension is put on the muscle, the movement accelerates, and the muscle goes back to neutral. It's not a continuous movement at all.
https://en.wikipedia.org/wiki/Biological_neuron_model
But odds are good that it's not just the value that's encoded. Many experiments have shown that it matters a lot if the signals are in phase (ie. they encode the same or some multiple of a value, but that the signals started at the exact same time matters, maybe more than the value itself. Or in the encoding: while for the value only the distance between 2 spikes matters, if 2 spikes on 2 different neurons occur at the exact same time, this will be interpreted as very relevant, even those both spikes may have very different firing rates)
The actual signal isn't "direct".
IIRC from reading up on haptics - different tactile sensors are sensitive to different ranges of stimulus. Different cell bodies sense different effects and frequency ranges and send an encoded signal.
We tend to forget that the underlying technology is very different and needs different encoding, signalling and computation approaches.
The main sentiment is that our nervous system is quite slow compared to our electronics and needs to use different design approaches and novel encodings, to get things done.
In much the same way our electronics can't engage with visible optic phenomena "directly". I mean visible light frequencies are too high to directly sample and transmit electronically the sensor used has to deal with that.
As I understand it, the touch sensing structures are more like a zero, first, and second derivatives (deformation/tension, velocity, acceleration) and these coincidentally have different frequency sensitivity curves. My reading is that in some ways this might be more similar to how our visual system integrates different photon detection signals to interpret color. Rather than the clear frequency domain transform of the cochlea, there are broadly overlapping sensitivity curves with only 2-3 peaks.
Admittedly, I should have mentioned that any linear transform can be considered to be a single layer neural network (if you want to see the world through a neural network lens), and will add this to the post at some point.
In fact, I have a series of posts planned, which will reveal that well known algorithms/models are actually neural networks...
[1] https://sidsite.com/posts/fourier-nets/#learning-the-fourier...
Training straight from DCT coefficients to avoid spending time learning a similar representation in the bottom layers of the net. I've personally toyed with something similar on GANs to gauge the computational benefits of not doing convolutions in the bottom layers of a net but learning directly in a FFT-like compressed space instead.
I think this should be turned around. A single layer neural network can be considered a linear mapping (but not necessarily an orthogonal transform or change of basis, like the DFT).
A more clear example of this are adaptive filters, which are trained in real time using gradient descent.
This is an important distinction because thinking of "X is a Neural Net" doesn't provide meaningful insight, whereas "Neural Nets with X properties are a case of linear dynamic systems, here's an example of how we can equate one linear transformation to a neural net" leads you to deeper conclusions on the analysis and synthesis of ANNs in the context of dynamics - which encompasses a much larger surface area than the DFT.
Could it discover an interpolation filter like upfirdn? An IIR Butterworth filter (it would have to be recurrent)? A frequency transfer function derived from two signals?
I imagined that the solutions it found wouldn't be "clean" but have other non-essential operators bloating them. Could it find new architectures that haven't been created from first principles?
For some tasks, like system identification (used in echo cancellation), the NN is the filter - aformentioned adaptive filters are used for this case right now. It can also be used for black box modeling, which has numerous application in real time or otherwise.
For others like Butterworth (and other classic designs) there's not really a good reason to use a NN. Butterworth (and Chebychev I/II, elliptical, optimum-L, and others) are filter design formulae with a closed form (for a given filter order) that yield roots of transfer functions that have desirable properties - I'm not sure how a learning approach can beat a formulae that are derived from the properties of the filter they design.
There are iterative design algorithms that do not have a closed form, like Parks-McClellan. It is however quite good at what it does - it would be interesting to compare these methods against some design tricks to reduce filter order.
There are some applications of filter design that NNs can do that we don't have good solutions for with traditional algorithms, like system identification, another is in optimization (in terms of filter order) and iteratively designing stable IIR filters to fit arbitrary frequency curves (for FIR it's a solved problem, at significant extra cost compared to IIR).
As for topologies of the filter itself that is an interesting angle. Topologies affect quantization effects (if you wanted an FPGA to realize the filter with the fewest number of bits, topologies matter) and for time variant filters (like an adaptive IIR) there are drastic differences between the behavior of various topologies. I'm not sure how it would manifest with a NN designing the filter.
[1] https://en.m.wikipedia.org/wiki/Neural_architecture_search
[2] https://ai.googleblog.com/2021/04/evolving-reinforcement-lea...
This can be found somewhere in S.M. Kay's Fundamentals of Statistical Signal Processing: Estimation Theory (Vol 1), Detection Theory (Vol 2).
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.
So they are not that different: the specific structure of the Fourier basis allows for more efficient matrix * vector operation.
And what's better, an umbrella or a toaster, depends on the one's goals: if one'd like to fry some bread, toaster is more useful; if one'd like to cover from rain, umbrella is far superior, although toaster could used be too; if one'd like to drive a nail into the wall, toaster again is better; etc.
It's linear and so in the discrete case can be expressed as matrix multiplication (every discrete linear operation is expressible as matmul).
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 =)
Do we have tight error bounds proofs for neural networks as approximators ?
It doesn't tell you whether for a particular function f:
- a particular network structure is suitable,
- a trained network with particular weight value is suitable,
and it obviously doesn't answer the most useful question:
- given this network with this weights, what's the largest approximation error for this function f?
There are many approximation methods in approximation theory that can answer this last question.
Do we have these answers for neural networks?
Not in general that I'm aware of.
I agree the result is not practical, but you asked what is known. There have been some refinements (the citations on that page give a reasonable flavor, fwiw).
What about discontinuous functions?
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.
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.
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.
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.
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.
https://en.wikipedia.org/wiki/Machine_learning#Regression_an...
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.
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".
Statisticians care more about "modeling", actually estimating parameters that stand in for something real, to check assumptions and hypotheses. The cultures are very different. What makes total sense to one may baffle the other as lunacy (there's more convergence now though, by realizing the complementary nature of the two approaches). The terminology is different too: in stats, they call logistic regression regression, while in ML it would have been called classification (but the name is now stuck). ML also tends to be more Bayesian than frequentist, as opposed to classical stats.
I could write more but having taken ML courses before the big hype times, I can assure you ML doesn't just mean hyped up startup fluff vaporware.
Open up Kevin Murphy's ML book and compare the TOC with a Statistics textbook. There is overlap but it's certainly different in its goals and mentality.
It seems like some bitter bickering from the side of stats people that they didn't manage to hype up their field as much. Yeah they did have many of the same tools at their disposal but didn't use them in this way.
The only real useful definition these days is that stats is learning from data that happens in the stats department and ML is learning from data that happens in the CS department.
I wrote a bit more here: https://news.ycombinator.com/item?id=26984234
I think it's good if people are aware of the origins of the methods they use. Regression wasn't invented under the umbrella of ML, but is analyzed from a particular angle in ML more than in stats.
My conceptualization of the field is simply that ML is the design of universal function approximators to be used as part of statistical modeling/analysis. The key insight seems to be that a complex set of adapted network architectures, together with stochastic gradient descent are unreasonably effective. Further the effectiveness is a very non-linear function of size. As far as I can tell there is not much known about why this is the case. But as far as I can tell there really isn't anything done with these models that isn't statistical inference.
Machine learning is the study of computer algorithms that improve automatically through experience and by the use of data.
This definition would include something as simple as linear regression.
Linear regression attempts to model the relationship between two variables by fitting a linear equation to observed data.
The purpose of a neural network is exactly the same as a line of best fit. That is, you are just approximating an unknown function based on input/output data. The only difference is that a NN can better approximate a nonlinear function.
> A computer program is said to learn from experience E with respect to some task T and performance measure P, if its performance at task T, as measured by P, improves with experience E.
Statistical estimation methods are one way to achieve this, but not the only way, especially when an exact function can be learned, i.e. a typical layer 2 switch is a learning device. You don't program in the mapping from connected device MAC addresses to switch port, the switch itself learns this from receiving a message from a MAC on a port and then records the mapping. That is a very simple form of non-statistical machine learning.
I'm not really sure how you can start here but then say regression is not a form of machine learning. "Regression" is a pretty broad class of techniques that just means using labeled examples to estimate a function with a continuous response, typically contrasted with "classification," where the response is discrete. The method you use to do the function approximation may or may not be statistical. A genetic algorithm is not, for instance. I'm not sure least squares, which is what Legendre invented, should really be considered statistical, either. The original purpose was for approximating the solution to an overdetermined system of equations, before statistics was even formalized. It certainly became a preferred method in mathematical statistics, but mathematical statistics wasn't even formalized until later. It didn't start being called "regression" until Galton published his paper showing children of exceptionally tall or short people tended to regress to the mean, which was 80 years later. But you're performing regression analysis whether you use the normal equations, LU decomposition, QR decomposition, a genetic algorithm, gradient descent, stochastic gradient descent, stochastic gradient descent with dropout. Doesn't matter. As long as you're doing function approximation with a continuous response, it's still regression. Whether or not it can also be considered "machine" learning just depends on whether you're doing it by hand or via machine.
Though sure, typically people tend to imagine the more exotic and newer techniques that scale to very large data sets and reduce overfitting and deal with noise automatically and involve hyperparameters, i.e. not least squares.
> ML is a discipline that has existed for several decades
If you're going to say regression is part of ML, you can't say ML has only existed for decades. If you define it with that expansive scope, it's existed for centuries.
The truth is, these are tools that many communities have used in parallel and these communities are in constant flux regarding what promising directions they find and exploit and when they make a big splash in one place, others take notice and incorporate those ideas etc. There are no rigidly predefined disciplines and fields over long timescales.
When electrical engineers and signal processing communities worked on similar things they called it "pattern recognition".
Machine learning as a field started out with more ambition than mere regression and classification (and indeed covers a lot more ground), but it turns out that supervised learning has had the most practical success. But it's a research program and community that goes beyond that.
Similarly, there are parallels and similar equations between control theory and reinforcement learning. And indeed some controllers can be expressed as reinforcement learning agents. But the aims of the two communities are not the same.
Maybe people would be happier if "statistical learning" (which is also used) was used more instead of "machine learning"? But indeed as another comment points out, ML as a paradigm does not necessarily require learning of a statistical kind.
Labels grow and wane in popularity, it doesn't mean it's the same thing repackaged, rather that the aims and the focus changes depending on what we find most productive and fruitful.
For example many of these things were also called "soft computing" a few years ago, but that term is rarely seen nowadays.
The problem in my mind is not that ML is using a lot of stats (obviously), it's that foundational mathematical concepts get labelled as ML techniques. This is why the title of the post is so annoying. This totally obscures the structure of the field. E.g. I wouldn't call linear algebra a quantum mechanics technique. I would say that QM uses (and spurred the development of) a lot of LinAlg.
The point is, when you listen to an ML person introduce regression in a lecture it will look and feel different from when a stats person does it. ML-type regression is part of ML. Stats type regression doesn't cut it. They care about different aspects, flesh out stuff that's not very relevant for ML and ignore parts that are more important for ML.
Neural nets are all you need[*].
[*] if what you need is non-robust black boxes
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.
Backpropagation is a placeholder for stuff we don't understand.
No it's not, read again.
So this post essentially shows that the Fourier transform is a linear combination.
- 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?
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?
In particular I'm interested in the efficiency gains from avoiding convolutions and the possibility of running a compressed frequency-domain NN on CPUs.
Like you said, there's already a significant connection between convolutional networks and the Fourier domain (the convolution theorem).
Tangentially, I've recently worked on a project that focused on implementing convolution in the Fourier domain, and how that allows one to control useful properties of convolutions (like "smoothness" and orthogonality).
I made a demonstration of convolution in the Fourier domain in PyTorch, which you might find interesting: https://nbviewer.jupyter.org/github/locuslab/orthogonal-conv...
More generally, you could look here for more code and the corresponding paper: https://github.com/locuslab/orthogonal-convolutions
"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.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.
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.
Linear regression's just learning an affine transform but I think it's misleading and unhelpful to call that a neural network either.
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/downlo...
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.
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.
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.
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.
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.
... 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?
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.)
https://en.wikipedia.org/wiki/Universal_approximation_theore...
most of the terms are on the order of 1/N so on these would be negligible
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.
Winograd transform can be seen as a depthwise convolution with fixed weights.
And similarly to DTF, winograd transform can be used to speed up convolutions: a 3x3 convolution can be implemented with a winograd transform + a 1x1 convolution + inverse winograd transform. This basically reduce the number of operations performed by 2.
Now, if a neural network is able to learn the weights of a depthwise convolution to match the coefficients of a winograd transform, that means you should be able to do this transformation when describing the architecture of your network. That way, you don't rely on your deep learning framework to do the transformation for you.
And more importantly you might end up with something more generic: perhaps the weights in the depthwise convolutions will not converge to the weights of a winograd transform, but to weight better suited to what you are trying to learn.
This is the same ideas which lead to the development of CNN: replace the fixed weights of convolutions used in traditional computer vision algorithm with weights that are learned by the network.