7 ms·

Symbolic Regression is NP-hard

109 points by nabla9 4y ago

CoastalCoder 4y ago
I wish people knew the original meaning of "begging the question". Now the people routinely use a different meaning, our language is unnecessarily muddier.
- deleted 4y ago
  [deleted]
- GolDDranks 4y ago
  To spread awareness of the original meaning: (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]
  - kltrank 4y ago
    Wikipedia marks the popular use "invites the question" as vernacular. This seems wrong: The Oxford dictionary lists a) the original meaning and b) "invites the question", and b) is not marked as vernacular.
- SantalBlush 4y ago
  It's really not muddier with this use of the phrase; some people make a show about being bothered by it so they can demonstrate that they knew the original meaning. 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.
  - smegsicle 4y ago
    rather than this usage being unclear, i think the muddiness is more about the original concept becoming more difficult to reference- it has a name, but that name now refers to a much less subtle concept
    - goolulusaurs 4y ago
      "assuming the conclusion" is a much better way to refer to the original concept, IMO.
    - SantalBlush 4y ago
      I get it, it's like when someone mentions a slippery slope: are they talking about a fallacy, or a surface I can slide down?
      - Cpoll 4y ago
        > Based on the context 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.
- radarsat1 4y ago
  It's just a common mistake. "Raises the question" would have been the appropriate idiom. In any case no harm no foul.
  - partdavid 4y ago
    Not in itself. But when GP wishes that more people knew the meaning of the set phrase "begging the question", there's an underlying desire (which I share) that more people be familiar with elementary parts of logic and debate. In that sense I also wish more people knew what "No true Scotsman" or"non sequitur" mean. Including, I'm sure, myself, in all my areas of ignorance.
- im3w1l 4y ago
  The words "begging" "the" "question" has almost nothing to do with what the full expression means, making it unnecessarily confusing. "circular argument" is much clearer.
  - bruce343434 4y ago
    A circular argument begs the question "oh, does it?"
- usgroup 4y ago
  "Begging the question" to someone with no sense of its etymology just sounds like it should mean "necessitates the asking of a question" or "makes clear a question" as opposed to "attempting to prove something whilst taking its truth for granted". 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.
- thyrsus 4y ago
  I think the form "beggars the question", i.e., left the question in poverty, unanswered, is somewhat less misinterpretable. https://en.m.wikipedia.org/wiki/Begging_the_question https://en.m.wikipedia.org/wiki/Begging_the_question
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.
enricozb 4y ago
Wouldn't it be more accurate to state that it's NP-complete? In the first step of the proof they show that SR-Dec is in NP.
- deleted 4y ago
  [deleted]
- red_trumpet 4y ago
  I would say it's stylistically questionable to include the proof that it's in NP under the proof of NP-hardness. They could have written it in a paragraph before. 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.
KhoomeiK 4y ago
Interesting implications for "neuro-symbolic" computation and the so-called classical-neural synthesis many are looking for in deep learning, and Cognitive Science more broadly. 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.
- tgv 4y ago
  So many symbolic tasks are NP complete, e.g. crossword puzzles. IIRC, Go is even PSPACE hard. > 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.
- taylorius 4y ago
  "Does this mean that minds don't ever naturally build symbolic models of the world" 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.
- sumtechguy 4y ago
  That our minds skip many things is decently well known. The entire field of magic and marketing is basically doing that to people. People wildly make assumptions all the time, and do not necessarily see it all. If you can get someone to assume something or get to a base emotion it is easier to show someone something that is wrong and they will believe it.
usgroup 4y ago
I'm not sure that this wasn't known before. They claim "...while some works have hinted at the possible hardness of SR, no proof has yet been given that SR is, in fact, NP-hard.". Here is a counter example: https://erikdemaine.org/papers/ArithmeticGames_ISAAC2020/paper.pdf 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.
- Gatsky 4y ago
  This is raised by one of the peer reviewers and the authors reply (scroll down).
- dchftcs 4y ago
  That SR is NP-hard seems pretty trivial to me. Especially since the problem is framed to be combinatorial in nature; with a sufficiently weird family of functions, you'll be able to find an NP-hard class of subproblems. 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.
  - usgroup 4y ago
    I'm not really sure this is a low value theoretical question. Here is a fun application: https://dl.acm.org/doi/pdf/10.5555/2955491.2955678 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.
    - 4y ago
thrown_22 4y ago
Interesting paper for finding a function which fits the given data, however they way oversell the ability of any such model: >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.
- mjburgess 4y ago
  Can you say more about how it's equivalent to the halting problem?
  - thrown_22 4y ago
    >In mathematics, Richardson's theorem establishes the undecidability of the equality of real numbers defined by expressions involving integers, π, ln ⁡ 2 , {\displaystyle \ln 2,} and exponential and sine functions. It was proved in 1968 by mathematician and computer scientist Daniel Richardson of the University of Bath. https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem

109 points by nabla9 4y ago

I wish people knew the original meaning of "begging the question". Now the people routinely use a different meaning, our language is unnecessarily muddier.

deleted 4y ago
[deleted]
GolDDranks 4y ago
To spread awareness of the original meaning: (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]
- kltrank 4y ago
  Wikipedia marks the popular use "invites the question" as vernacular. This seems wrong: The Oxford dictionary lists a) the original meaning and b) "invites the question", and b) is not marked as vernacular.
SantalBlush 4y ago
It's really not muddier with this use of the phrase; some people make a show about being bothered by it so they can demonstrate that they knew the original meaning. 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.
- smegsicle 4y ago
  rather than this usage being unclear, i think the muddiness is more about the original concept becoming more difficult to reference- it has a name, but that name now refers to a much less subtle concept
  - goolulusaurs 4y ago
    "assuming the conclusion" is a much better way to refer to the original concept, IMO.
  - SantalBlush 4y ago
    I get it, it's like when someone mentions a slippery slope: are they talking about a fallacy, or a surface I can slide down?
    - Cpoll 4y ago
      > Based on the context 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.
radarsat1 4y ago
It's just a common mistake. "Raises the question" would have been the appropriate idiom. In any case no harm no foul.
- partdavid 4y ago
  Not in itself. But when GP wishes that more people knew the meaning of the set phrase "begging the question", there's an underlying desire (which I share) that more people be familiar with elementary parts of logic and debate. In that sense I also wish more people knew what "No true Scotsman" or"non sequitur" mean. Including, I'm sure, myself, in all my areas of ignorance.
im3w1l 4y ago
The words "begging" "the" "question" has almost nothing to do with what the full expression means, making it unnecessarily confusing. "circular argument" is much clearer.
- bruce343434 4y ago
  A circular argument begs the question "oh, does it?"
usgroup 4y ago
"Begging the question" to someone with no sense of its etymology just sounds like it should mean "necessitates the asking of a question" or "makes clear a question" as opposed to "attempting to prove something whilst taking its truth for granted". 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.
thyrsus 4y ago
I think the form "beggars the question", i.e., left the question in poverty, unanswered, is somewhat less misinterpretable. https://en.m.wikipedia.org/wiki/Begging_the_question https://en.m.wikipedia.org/wiki/Begging_the_question

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.

enricozb 4y ago

Wouldn't it be more accurate to state that it's NP-complete? In the first step of the proof they show that SR-Dec is in NP.

deleted 4y ago
[deleted]
red_trumpet 4y ago
I would say it's stylistically questionable to include the proof that it's in NP under the proof of NP-hardness. They could have written it in a paragraph before. 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.

KhoomeiK 4y ago

Interesting implications for "neuro-symbolic" computation and the so-called classical-neural synthesis many are looking for in deep learning, and Cognitive Science more broadly. 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.

tgv 4y ago
So many symbolic tasks are NP complete, e.g. crossword puzzles. IIRC, Go is even PSPACE hard. > 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.
taylorius 4y ago
"Does this mean that minds don't ever naturally build symbolic models of the world" 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.
sumtechguy 4y ago
That our minds skip many things is decently well known. The entire field of magic and marketing is basically doing that to people. People wildly make assumptions all the time, and do not necessarily see it all. If you can get someone to assume something or get to a base emotion it is easier to show someone something that is wrong and they will believe it.

usgroup 4y ago

I'm not sure that this wasn't known before. They claim "...while some works have hinted at the possible hardness of SR, no proof has yet been given that SR is, in fact, NP-hard.". Here is a counter example: https://erikdemaine.org/papers/ArithmeticGames_ISAAC2020/paper.pdf 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.

Gatsky 4y ago
This is raised by one of the peer reviewers and the authors reply (scroll down).
dchftcs 4y ago
That SR is NP-hard seems pretty trivial to me. Especially since the problem is framed to be combinatorial in nature; with a sufficiently weird family of functions, you'll be able to find an NP-hard class of subproblems. 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.
- usgroup 4y ago
  I'm not really sure this is a low value theoretical question. Here is a fun application: https://dl.acm.org/doi/pdf/10.5555/2955491.2955678 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.
  - 4y ago

thrown_22 4y ago

Interesting paper for finding a function which fits the given data, however they way oversell the ability of any such model: >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.

mjburgess 4y ago
Can you say more about how it's equivalent to the halting problem?
- thrown_22 4y ago
  >In mathematics, Richardson's theorem establishes the undecidability of the equality of real numbers defined by expressions involving integers, π, ln ⁡ 2 , {\displaystyle \ln 2,} and exponential and sine functions. It was proved in 1968 by mathematician and computer scientist Daniel Richardson of the University of Bath. https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem