4 ms·

In this case wouldn't a Fourier-type approach work better? At least there's no risk the function blows up and it possibly needs fewer parameters?

bsder 2y ago
Yeah, I thought the whole point of a polynomial approximation was that it is really only useful for the first couple of powers (quick and cheap) or because you have a particular process that you know a priori has a particular form (non-convergent, non-conservative, higher powered, etc.). The "particular form" is important--if you don't know that then there is no reason for choosing x^10000 over x^5 (other than computational complexity). But there is also no reason for choosing x^5 over x^10000! Maybe that function really is flat and maybe it isn't. You really just don't know. If you don't have anything too weird, Fourier is pretty much optimal in the limit--if a bit expensive to calculate. In addition, since you can "bandwidth limit" it, you can very easily control overfitting and oscillation. Even more, Fourier often reflects something about the underlying process (epicycles, for example, were correct--they were pointing at the fact that orbits were ellipses).
- constantcrying 2y ago
  >If you don't have anything too weird, Fourier is pretty much optimal "Optimal" by what metric? Why is projecting on the Fourier basis "better" than projecting on a polynomial basis?
  - bsder 2y ago
    Pick a metric. Fourier is probably better in general. With respect to machine learning, probably the fact that Fourier is bounded and gives coherent (if completely random) results even very far from the interval of interest. However, this is like saying that an O(n log n) algorithm is better than O(n^2). Sure, it's true in the limit, by the constant terms can be quite large and O(n^2) can remain better up to remarkably useful values of n. As I pointed out, the advantage that polynomial basis generally has is that you can be accurate enough with lower powers that are much, much faster to calculate (we use matrices of linear equations precisely for that reason). Or, you can match a particular process because you know specifically that it follows some particular function (we know that road damage follows the fourth power of load--it would be counterproductive to model that with Fourier). Using high powers for polynomial basis is almost always worse than any other choice.
    - constantcrying 2y ago
      I don't disagree, but I do not think it's meaningful to call something optimal if it is clearly unusable under certain circumstances. If you know that some relationship is close to polynomial, obviously a polynomial basis is more suitable. E.g. a line performs terribly for a Fourier transformation. >Using high powers for polynomial basis is almost always worse than any other choice. For some value of "high", yes.
constantcrying 2y ago
The problem with Fourier approximation is that it works terribly for relatively "simple" functions. E.g. fitting a linear relationship is extremely hard.
- ziofill 2y ago
  Ah good point. There ought to be a way to get the best of both worlds.
  - hoseja 2y ago
    https://en.wikipedia.org/wiki/Pad%C3%A9_approximant https://en.wikipedia.org/wiki/Pad%C3%A9_approximant
    - constantcrying 2y ago
      The "normal" Pade Approximation is irrelevant. Could you point out why exactly this is superior or actually solves the issue? Any paper comparing these methods would also be interesting.
      - srean 1y ago
        One way I handle the 'simple case that Fourier has trouble with' is I add the 'simple' bases to the catalogue of Fourier basis functions and then orthogonalise the resulting basis system. Depending on specific 'simple' cases this can be messy but effective. The same deal happens for decision trees. (Axis parallel) Trees have a hard time fitting linear functions, requiring many modes. One can use essentially the same solution. BTW very informative commentary. The things that you bring up really needed to be brought out.
        ziofill 1y ago
        I’ll keep asking my ignorant questions since I found informed people: what about a basis of wavelets or some heterogeneous bag of functions (which could include linear, polynomial times Gaussian, and why not some harmonic functions too)? At the end of the day a functional basis might not need to be “well formed” like Fourier or some polynomial family. It just needs to do the job.

bsder 2y ago

Yeah, I thought the whole point of a polynomial approximation was that it is really only useful for the first couple of powers (quick and cheap) or because you have a particular process that you know a priori has a particular form (non-convergent, non-conservative, higher powered, etc.). The "particular form" is important--if you don't know that then there is no reason for choosing x^10000 over x^5 (other than computational complexity). But there is also no reason for choosing x^5 over x^10000! Maybe that function really is flat and maybe it isn't. You really just don't know. If you don't have anything too weird, Fourier is pretty much optimal in the limit--if a bit expensive to calculate. In addition, since you can "bandwidth limit" it, you can very easily control overfitting and oscillation. Even more, Fourier often reflects something about the underlying process (epicycles, for example, were correct--they were pointing at the fact that orbits were ellipses).

constantcrying 2y ago
>If you don't have anything too weird, Fourier is pretty much optimal "Optimal" by what metric? Why is projecting on the Fourier basis "better" than projecting on a polynomial basis?
- bsder 2y ago
  Pick a metric. Fourier is probably better in general. With respect to machine learning, probably the fact that Fourier is bounded and gives coherent (if completely random) results even very far from the interval of interest. However, this is like saying that an O(n log n) algorithm is better than O(n^2). Sure, it's true in the limit, by the constant terms can be quite large and O(n^2) can remain better up to remarkably useful values of n. As I pointed out, the advantage that polynomial basis generally has is that you can be accurate enough with lower powers that are much, much faster to calculate (we use matrices of linear equations precisely for that reason). Or, you can match a particular process because you know specifically that it follows some particular function (we know that road damage follows the fourth power of load--it would be counterproductive to model that with Fourier). Using high powers for polynomial basis is almost always worse than any other choice.
  - constantcrying 2y ago
    I don't disagree, but I do not think it's meaningful to call something optimal if it is clearly unusable under certain circumstances. If you know that some relationship is close to polynomial, obviously a polynomial basis is more suitable. E.g. a line performs terribly for a Fourier transformation. >Using high powers for polynomial basis is almost always worse than any other choice. For some value of "high", yes.

constantcrying 2y ago

The problem with Fourier approximation is that it works terribly for relatively "simple" functions. E.g. fitting a linear relationship is extremely hard.

ziofill 2y ago
Ah good point. There ought to be a way to get the best of both worlds.
- hoseja 2y ago
  https://en.wikipedia.org/wiki/Pad%C3%A9_approximant https://en.wikipedia.org/wiki/Pad%C3%A9_approximant
  - constantcrying 2y ago
    The "normal" Pade Approximation is irrelevant. Could you point out why exactly this is superior or actually solves the issue? Any paper comparing these methods would also be interesting.
    - srean 1y ago
      One way I handle the 'simple case that Fourier has trouble with' is I add the 'simple' bases to the catalogue of Fourier basis functions and then orthogonalise the resulting basis system. Depending on specific 'simple' cases this can be messy but effective. The same deal happens for decision trees. (Axis parallel) Trees have a hard time fitting linear functions, requiring many modes. One can use essentially the same solution. BTW very informative commentary. The things that you bring up really needed to be brought out.
      - ziofill 1y ago
        I’ll keep asking my ignorant questions since I found informed people: what about a basis of wavelets or some heterogeneous bag of functions (which could include linear, polynomial times Gaussian, and why not some harmonic functions too)? At the end of the day a functional basis might not need to be “well formed” like Fourier or some polynomial family. It just needs to do the job.