Symbolic Regression is NP-hard
openreview.net
openreview.net
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
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!
I suspect you mean "the value of parameters" here.
Most Neural networks have other hyper-paramters, but the ones in SR are probably quite interpretable and intuitive.
This might be difficult, especially if you can't visualize the data (many dimensions etc).
For example, a numeric regression for a1 * x1 + a2 * x2 + a3 = y can not fit a relationship like y = x1/x2.
In symbolic regression, the system can automatically discover equations also, not just coefficients.
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.
Now the people routinely use a different meaning, our language is unnecessarily muddier.
(From Wikipedia) To "beg the question" (also called petitio principii) is to attempt to support a claim with a premise that itself restates or presupposes the claim.[6] It is an attempt to prove a proposition while simultaneously taking the proposition for granted.
When the fallacy involves only a single variable, it is sometimes called a hysteron proteron[7][8][9] (Greek for "later earlier"), a rhetorical device, as in the statement:
"Opium induces sleep because it has a soporific quality."[10]This seems wrong: The Oxford dictionary lists a) the original meaning and b) "invites the question", and b) is not marked as vernacular.
Based on the context, you know exactly which meaning of the phrase is intended here, and it's disengenuous to pretend otherwise. The differences in context between the two meanings make this a non-problem.
Personally speaking, it's not always easy to tell which "begging the question" someone means from context. I often have to stop and ask "hold on, do they mean the premise assumes the conclusion?" (And all the worse for me if they just mean "brings up the question", because I'll spend a minute making sure I'm not just missing the fallacy).
In that sense, it's not quite the same as "slippery slope," which doesn't get used literally much anyway.
I'd imagine that we come to know the meaning of >99% of words and expressions through usage, so it feels like a fairly expected -- and reasonable, yet wrong -- outcome.
https://erikdemaine.org/papers/ArithmeticGames_ISAAC2020/pap...
If arithmetic search is NP-complete so is every superset of it: this was just a cursory google search.
The computationally difficulty of something like SR is also deeply connected to its applicability. If you have data where it's easy to apply SR and trust it, it tends to be easy; to trust your ability more you probably want to add regularization based on the complexity of the final formula, and probably you'd have strong priors on a small set of functions that are applicable. Once you don't have this, and get to where the problem can be plausibly NP-hard, you're going to overfit and the technique is worthless.
There's a family of ML theoretical questions that are just very low value as they make very little progress in helping to understand important problems. This is one of them.
https://dl.acm.org/doi/pdf/10.5555/2955491.2955678
Using SR to find an invertible function which can effectively linearise its input. I don't think it is too difficult to think of applications where discovering relationships in terms of a limited set of operators is useful.
SR is equivalent to blind feature engineering. If I put it like that, probably most people who've done a bit of data science would know how bad of an idea it is unless we can regularize it well and bound the search space based on prior knowledge.
Deep learning has the same theoretical problem and it's only overcome by its unreasonable empircal effectiveness on certain problems. And even then, nobody cares about its NP-hardness.
Does this mean that minds don't ever naturally build symbolic models of the world, or rather just that they try to minimize the computationally intensive (and now NP-hard) task of uncovering a symbolic model? I'd definitely lean toward the latter (ironically due to my intuition).
It also aligns quite well with Kahneman's System 1 - System 2 distinction, where the symbolic System 2 is reserved for situations that most strongly require such computation.
I think you need to pin down what you mean by "mind" there. The raw neurons of (say) the human vision system seem to work by learning useful features, combining them in later layers etc. - analogous to how an ANN might be trained. i.e. it's not symbolic at its core.
In contrast, the creation of a new scientific insight (e.g. Newton's law of gravity), seems to use a more symbolic search method, which is thought to be built on top of the raw neural processes. An analogy might be the use of GPT-3 to "solve" various language problems.
Of course, these are just guesses based on our current research - no-one really has any idea exactly how the brain works.
> It also aligns quite well with Kahneman's System 1 - System 2 distinction, where the symbolic System 2 is reserved for situations that most strongly require such computation.
It would be very, very remarkable if that were the case. Our brains don't work like Turing Machines. We're finite. Our symbolic reasoning is different. What Kahneman dubs System 2 decisions also is not necessarily related to symbolic reasoning, certainly not of the type mentioned in the paper.
However it could still be true that this result was known beforehand (and judging by the length of the proof, it doesnt seem too difficult). So their main result would still be the NP-hardness, which justifies the name of the paper.
>Then, an SR algorithm would ideally re-discover the well-known expression (or an equivalent formulation thereof) F = G × m1 m2 r2 , with G = 6.6743 × 10−11, by opportunely combining the mathematical operations (here, of multiplication and division) with the variables and constant at play
F in this case is the second derivative of the curve of motion of mass, _either_ mass. Yet given a sampling of data the best you could do would be one equation for the motion of mass one and another for m2. The fact they are equal is not an NP-hard problem but equivalent to the halting problem. Similarly for deciding that the equation is a differential equation.