Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com