29 ms·

I encourage everyone to read this paper. It's well written and easy to follow along. To the uninitiated, SR is the problem of finding a mathematical (symbolic)

by aseg 4y ago

I encourage everyone to read this paper. It's well written and easy to follow along. To the uninitiated, SR is the problem of finding a mathematical (symbolic) expression that most accurately describes a dataset of input-output examples (regression). The most naive implementation of SR is basically a breath first search starting from the simplest program tree: x -> sin(x) -> cos(x) ... sin(cos(tan(x))) until timeout. However, we can prune out equivalent expressions and, in general, the problem is embarrassingly parallel which alludes to some hope that we can solve this pretty fast (check out PySR[1] for a modern implementation). I find SR fascinating because it can be used for model distillation: learn a DNN approximation and "distill" it to a symbolic program. Note that the paper talks about the decision version of the SR problem. ie: can we discover the global optimum expression. I think this proof is important for the SR community but not particularly surprising (to me). However, I'm excited by the potential future work for this paper! A couple of discussion points: * First, SR is technically a bottom up program synthesis problem where the DSL (math) has an equivalence operator. Can we use this proof to impose stronger guarantees on the "hyperparameters" for bottom up synthesis. Conversely, does the theoretical foundation of the inductive synthesis literature [2] help us define tighter bounds? (EDIT: I was thinking a bit more about this and [2] is a bad reference for this... Jha et al give proofs for synthesis w/ CEGIS where the synthesizer queries a SMT solver for counterexamples until there are none... kinda like a GAN. Apologies.) * Second, while SR itself is NP hard, can we say anything about the approximate algorithms (eg: distilling a deep neural network to find a solution[3])? Specifically, what proof tell us about the PAC learnability of SR? Anyhow, pretty cool seeing such work get more attention! [1] https://github.com/MilesCranmer/PySR https://github.com/MilesCranmer/PySR [2] https://susmitjha.github.io/papers/togis17.pdf https://susmitjha.github.io/papers/togis17.pdf [3] https://astroautomata.com/paper/symbolic-neural-nets/ https://astroautomata.com/paper/symbolic-neural-nets/

noobermin 4y ago
Random question, if you don't mind. What does symbolic fitting give you that normal regression doesn't? Usually in physics, an analytic solution (our term) yields physical insight, although not everyone is a physicist and cares about that, hence why machine learning in general is popular.
- usgroup 4y ago
  Non linear forms most importantly.
- thrown_22 4y ago
  A Fourier expansion is a symbolic fitting of data to a curve, yet it provides no information about the systems sampled as shown by the fact that it fits a geocentric model just as well as a heliocentric one. The idea that an arbitrarily large expression is somehow more understandable than the fourier coefficients of a the first few large terms could only have been done by someone who hasn't looked the the vast array of semi-empirical formulas out there which are as clear as mud.
  - usgroup 4y ago
    Well, I think the hope is that formulae reveal relationships. Notable applications of SR have mostly been to physics and other science phenomena. So, you do some SR to understand the mathematical form of the relationship, and then carry on by trying to understand it causally.
- aseg 4y ago
  You might find (Cramer, 1985) interesting! IIRC they go into exactly this problem. However, I can't find an open pdf to link to unfortunately. I'll edit this list tomorrow morning in case I misjudged (Cramer, 1985) or if I find a link.. Here are two hand-wavy arguments that may not be 100% correct: * Structured Bias: A symbolic regression term allows you -- the scientist -- to control exactly what sort of expressions you expect to see. If I'm looking at data coming from a spring, I expect to see a lot of dampened sinusoids and little quantum physics. SR gives you control over the "programming language" while parametric regression will only allow you to change the number of parameters (not useful in this context). * Generality: A regression term guarantees the best fit parametric equation as long as you have a comprehensive sample of your data range. A symbolic expression (most of the time) extrapolates beyond the provided data range. In fact, this is one of the constraints in the main proof in the paper (f* should generalize)! Basically: If I only have data for sin(x) from 0 to \pi, PR will find the best fit but there is no guarantee that the best fit will also work in the range \pi to 2\pi. I want to stress that these aren't established facts and each of these pros actually introduces a lot of cons in the process (what if you introduce incorrect structured bias / what if the "general/simple" solution is actually a little imprecise... Like Newton's laws vs Einstein's theory)! This just means that there is plenty of exciting work to be done!

by aseg 4y ago

noobermin 4y ago

Random question, if you don't mind. What does symbolic fitting give you that normal regression doesn't? Usually in physics, an analytic solution (our term) yields physical insight, although not everyone is a physicist and cares about that, hence why machine learning in general is popular.

usgroup 4y ago
Non linear forms most importantly.
thrown_22 4y ago
A Fourier expansion is a symbolic fitting of data to a curve, yet it provides no information about the systems sampled as shown by the fact that it fits a geocentric model just as well as a heliocentric one. The idea that an arbitrarily large expression is somehow more understandable than the fourier coefficients of a the first few large terms could only have been done by someone who hasn't looked the the vast array of semi-empirical formulas out there which are as clear as mud.
- usgroup 4y ago
  Well, I think the hope is that formulae reveal relationships. Notable applications of SR have mostly been to physics and other science phenomena. So, you do some SR to understand the mathematical form of the relationship, and then carry on by trying to understand it causally.
aseg 4y ago
You might find (Cramer, 1985) interesting! IIRC they go into exactly this problem. However, I can't find an open pdf to link to unfortunately. I'll edit this list tomorrow morning in case I misjudged (Cramer, 1985) or if I find a link.. Here are two hand-wavy arguments that may not be 100% correct: * Structured Bias: A symbolic regression term allows you -- the scientist -- to control exactly what sort of expressions you expect to see. If I'm looking at data coming from a spring, I expect to see a lot of dampened sinusoids and little quantum physics. SR gives you control over the "programming language" while parametric regression will only allow you to change the number of parameters (not useful in this context). * Generality: A regression term guarantees the best fit parametric equation as long as you have a comprehensive sample of your data range. A symbolic expression (most of the time) extrapolates beyond the provided data range. In fact, this is one of the constraints in the main proof in the paper (f* should generalize)! Basically: If I only have data for sin(x) from 0 to \pi, PR will find the best fit but there is no guarantee that the best fit will also work in the range \pi to 2\pi. I want to stress that these aren't established facts and each of these pros actually introduces a lot of cons in the process (what if you introduce incorrect structured bias / what if the "general/simple" solution is actually a little imprecise... Like Newton's laws vs Einstein's theory)! This just means that there is plenty of exciting work to be done!