4 ms·

You're not wrong, but the numbers are quite different if you have a strong search heuristic. And that is where neural nets excel. See AlphaGo and derivatives. S

You're not wrong, but the numbers are quite different if you have a strong search heuristic. And that is where neural nets excel. See AlphaGo and derivatives. So this isn't just some random gradient descent exploring the full space; a properly designed and trained neural net will effectively cordon off vast swaths of the search space, and suddenly the problem is probably many orders of magnitude more tractable. That's really why deep learning shines in technical applications. Solution search heuristics were until recently solely within the domain of biological neural networks; now we have created technology which is capable of extracting superior heuristics over the course of learning. And it's already paying off in industrial science, despite the cries of naysayers, though the applications are still in infancy.

bmc7505 5y ago
There is a vast chasm of computational complexity between Chess, Go, and protein folding, to program induction. Unlike problems where the configuration space grows exponentially, the space of valid programs is at least super-exponential and depending on the language family, (e.g. context free, context sensitive, recursively enumerable), can often be undecidable. Furthermore, many language induction problems do not have optimal substructure or overlapping subproblems, two important prerequisites for reinforcement learning to work. In these settings, gradient-based heuristics will only get you so far. If you are interested in learning more about the limits of gradient descent, you should look into the TerpreT problem [1]. There are surprisingly tiny Boolean circuits which can be found using constraint solving, but we have not yet been able to learn despite the success of reinforcement learning in other domains. I'm not saying that program induction is impossible, but it is extremely hard even for relative "simple" languages like source code. [1]: https://arxiv.org/pdf/1608.04428.pdf https://arxiv.org/pdf/1608.04428.pdf
- bhntr3 5y ago
  Thank you. I just finished my master's thesis in program synthesis/induction. You're explaining this better than I could.
- twofornone 5y ago
  So what do you think is different about human learning that allows us to learn to find solutions in such large spaces?
  - bmc7505 5y ago
    There are two answers to your question. One is, humans have simply not found very good solutions in these spaces. We have designed algorithms which barely work on denumerable sets, but are unsuitable in more general spaces. There are many decision problems which are known to be undecidable, i.e., there exists no algorithm that decides first order logic propositions. There are fragments which are decidable, and essentially all useful algorithms in CS fall into this category. The second answer is that we are exploiting statistical regularities in the data which make these problems effectively regular or context-free in practice. When someone asks you to solve a new programming problem, you are applying some heuristics that have worked on similar problems in the past. Given a truly novel problem, you can either make some assumptions to reduce it into a more tractable form (e.g. 3-SAT), or design some clever search heuristic, but without any prior examples of programs or a distribution over probable inputs, you can do no better than naïve search.
    - twofornone 5y ago
      >The second answer is that we are exploiting statistical regularities in the data which make these problems effectively regular or context-free in practice. When someone asks you to solve a new programming problem, you are applying some heuristics that have worked on similar problems in the past. Given a truly novel problem, you can either make some assumptions to reduce it into a more tractable form (e.g. 3-SAT), or design some clever search heuristic, but without any prior examples of programs or a distribution over probable inputs, you can do no better than naïve search. How is this different from training a neural network on a data set and relying on interpolation for inference? Isn't that exactly what neural nets learn, statistical relationships between inputs? After all, isn't that effectively the mathematical definition for a heuristic? You don't know exactly what the solution is, but there are similarities between past examples you've encountered, and these form priors for your shortcut through the solution space. I'm not sure if neural nets can extrapolate (which would imply searching outside of the training space, i.e. innovating) but if they are truly universal function approximators, I don't see why not. Especially if the solution space is smooth and continuous in the extrapolation range...whatever that means in high D space. To your first point, it seems you are saying that neither humans or neural networks can solve these intractable problems. It would not surprise me if a massive, well tuned neural net, possibly with yet to be developed components, could discover better heuristics than even an intelligent and experienced human for problems in this class. But that might be optimistic.
supperburg 5y ago
And don’t forget that we haven’t even really begun to search the areas that resemble aspects of human neural anatomy. The ultimate heuristic.

bmc7505 5y ago

There is a vast chasm of computational complexity between Chess, Go, and protein folding, to program induction. Unlike problems where the configuration space grows exponentially, the space of valid programs is at least super-exponential and depending on the language family, (e.g. context free, context sensitive, recursively enumerable), can often be undecidable. Furthermore, many language induction problems do not have optimal substructure or overlapping subproblems, two important prerequisites for reinforcement learning to work. In these settings, gradient-based heuristics will only get you so far. If you are interested in learning more about the limits of gradient descent, you should look into the TerpreT problem [1]. There are surprisingly tiny Boolean circuits which can be found using constraint solving, but we have not yet been able to learn despite the success of reinforcement learning in other domains. I'm not saying that program induction is impossible, but it is extremely hard even for relative "simple" languages like source code. [1]: https://arxiv.org/pdf/1608.04428.pdf https://arxiv.org/pdf/1608.04428.pdf

bhntr3 5y ago
Thank you. I just finished my master's thesis in program synthesis/induction. You're explaining this better than I could.
twofornone 5y ago
So what do you think is different about human learning that allows us to learn to find solutions in such large spaces?
- bmc7505 5y ago
  There are two answers to your question. One is, humans have simply not found very good solutions in these spaces. We have designed algorithms which barely work on denumerable sets, but are unsuitable in more general spaces. There are many decision problems which are known to be undecidable, i.e., there exists no algorithm that decides first order logic propositions. There are fragments which are decidable, and essentially all useful algorithms in CS fall into this category. The second answer is that we are exploiting statistical regularities in the data which make these problems effectively regular or context-free in practice. When someone asks you to solve a new programming problem, you are applying some heuristics that have worked on similar problems in the past. Given a truly novel problem, you can either make some assumptions to reduce it into a more tractable form (e.g. 3-SAT), or design some clever search heuristic, but without any prior examples of programs or a distribution over probable inputs, you can do no better than naïve search.
  - twofornone 5y ago
    >The second answer is that we are exploiting statistical regularities in the data which make these problems effectively regular or context-free in practice. When someone asks you to solve a new programming problem, you are applying some heuristics that have worked on similar problems in the past. Given a truly novel problem, you can either make some assumptions to reduce it into a more tractable form (e.g. 3-SAT), or design some clever search heuristic, but without any prior examples of programs or a distribution over probable inputs, you can do no better than naïve search. How is this different from training a neural network on a data set and relying on interpolation for inference? Isn't that exactly what neural nets learn, statistical relationships between inputs? After all, isn't that effectively the mathematical definition for a heuristic? You don't know exactly what the solution is, but there are similarities between past examples you've encountered, and these form priors for your shortcut through the solution space. I'm not sure if neural nets can extrapolate (which would imply searching outside of the training space, i.e. innovating) but if they are truly universal function approximators, I don't see why not. Especially if the solution space is smooth and continuous in the extrapolation range...whatever that means in high D space. To your first point, it seems you are saying that neither humans or neural networks can solve these intractable problems. It would not surprise me if a massive, well tuned neural net, possibly with yet to be developed components, could discover better heuristics than even an intelligent and experienced human for problems in this class. But that might be optimistic.

supperburg 5y ago

And don’t forget that we haven’t even really begun to search the areas that resemble aspects of human neural anatomy. The ultimate heuristic.