I wish people knew the original meaning of "begging the question".

Now the people routinely use a different meaning, our language is unnecessarily muddier.

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]

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.

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.

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

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?

> 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.

"assuming the conclusion" is a much better way to refer to the original concept, IMO.

It's just a common mistake. "Raises the question" would have been the appropriate idiom. In any case no harm no foul.

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.

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.

A circular argument begs the question "oh, does it?"

"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.

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

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

[2] https://susmitjha.github.io/papers/togis17.pdf

[3] https://astroautomata.com/paper/symbolic-neural-nets/

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.

Non linear forms most importantly.

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.

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.

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!

> while parametric regression will only allow you to change the number of parameters

I suspect you mean "the value of parameters" here.

The regression will 'set the value of the parameters'. OPs point is that when you want to change the regression your main 'hyper-parameter' (i.e. one that you get to choose rather than one that the system determines for you) is the number of parameters.

Most Neural networks have other hyper-paramters, but the ones in SR are probably quite interpretable and intuitive.

In "regular" regression, you have to come up with an input -> output equation. The regression only figures out the best parameters for it.

This might be difficult, especially if you can't visualize the data (many dimensions etc).

In symbolic regression, the system can automatically discover equations also, not just coefficients.

Potentially much better extrapolation from the data, for one thing. The hope with SR is that the equation that is found will in some sense have a deeper connection to the process that generated the data, than a neural network made of lots of RelU units does.

My initial guess is that regression determines how well you fit an existing pattern or group of patterns but doesn't find out if there is an even better fitting pattern not used. Linear regression will determine how well you fit a linear pattern and while you can use it to search for non-linear patterns (like a regression of home prices against area squared instead of area), it only tests the patterns you put in.

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.

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.

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.

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.

"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.

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.

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/pap...

If arithmetic search is NP-complete so is every superset of it: this was just at a cursory google search.

This is raised by one of the peer reviewers and the authors reply (scroll down).

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.

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

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.

The low-value theoretical question is whether it's NP-hard. For something like SR, if the solution space were to be big enough such that potentially NP hardness would be a serious partical hurdle, it's extremely difficult to trust the outcome of solving the optimization problem.

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.

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.

Can you say more about how it's equivalent to the halting problem?

>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