3 ms·

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

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.
- Jensson 5y ago
  > 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? The huge difference is that humans has a rational part of the brain which determines if examples are important to train on or not, doing extremely efficient problem space pruning. And then it trains the neural network in real time using that rational part as guidance. We can't program without the rational part, so computers likely wont able to program without it either. We can read sentences and detect objects in images without the rational parts so ML AI can do that. We have no idea at all how to build that rational part, without something replacing its role the current methods will just give us extremely primitive parts of human thinking such as image recognition. AlphaGO actually got a rational part, the code they used to play through the game and see if moves leads to a win. That means that AlphaGO has the full human capability, but for a very limited domain, just GO, the rational part of GO doesn't generalize well to more interesting problems.

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.

Jensson 5y ago
> 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? The huge difference is that humans has a rational part of the brain which determines if examples are important to train on or not, doing extremely efficient problem space pruning. And then it trains the neural network in real time using that rational part as guidance. We can't program without the rational part, so computers likely wont able to program without it either. We can read sentences and detect objects in images without the rational parts so ML AI can do that. We have no idea at all how to build that rational part, without something replacing its role the current methods will just give us extremely primitive parts of human thinking such as image recognition. AlphaGO actually got a rational part, the code they used to play through the game and see if moves leads to a win. That means that AlphaGO has the full human capability, but for a very limited domain, just GO, the rational part of GO doesn't generalize well to more interesting problems.