4 ms·

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 functio

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.
- dchftcs 4y ago
  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.

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.

dchftcs 4y ago
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.