Can neural networks be used to devise algorithms?

Question

After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether

Can neural networks be trained to solve classic algorithmic problems?

Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible. Then I guess the neural network would discover and train itself to use Dijkstra or something similar.

On one hand, we know that the computational power of neural networks is $TC^0$. On the other, I don't know if this is necessarily related to my question. Even so, for most problems we don't know whether they can be solved in $TC^0$ or not. Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not. For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$. I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.

Of course, extracting the algorithm is a whole different question. I suspect experts know how to do that, but discussing it is not the topic of this question.

Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know

Why is playing chess easier than Dijkstra or Graphisomorphism?

Answer 1

According to this blog By Reza Zadeh, training a neural network to produce correct output even for just two-thirds of the training examples is computationally hard:

Indeed, in 1988 J. Stephen Judd shows the following problem to be NP-hard:

Given a general neural network and a set of training examples, does there exist a set of edge weights for the network so that the network produces the correct output for all the training examples?

Judd also shows that the problem remains NP-hard even if it only requires a network to produce the correct output for just two-thirds of the training examples, which implies that even approximately training a neural network is intrinsically difficult in the worst case. In 1993, Blum and Rivest make the news worse: even a simple network with just two layers and three nodes is NP-hard to train!

Answer 2

It seems the answer must be positive, because what might a reasonable negative answer to "Can neural networks be used to devise algorithms?" look like? If you accept the premise that human brains are neural networks -- or at least can be modeled by such to a very high degree of accuracy -- doesn't that provide an existence proof? We can devise algorithms and therefore so can some neural net.

Answer 3

This is not a full answer and I am not very experienced in neural nets, but perhaps helpful.

NNs essentially are given an input and produce a response. They are then trained via practice to produce similar responses on "similar" inputs in the domain, for example, the same label to images of the same animal, or high ratings to "good" chess positions where good means high winning chances.

So as I commented, neural nets are a non-uniform model of computation that work in a totally different way than step-by-step algorithms run on Turing Machines. Instead, think of them as "soft" circuits that use continuous math rather than Boolean and can be tweaked or trained, and are allowed to err.

Why is playing chess easier than Dijkstra or Graphisomorphism?

Partially, it is the difference between asking someone to answer a question to the best of their ability, and asking them for the one correct answer along with a proof that it is correct. Partially, it is the difference between solving a fixed-size problem, and simultaneously solving the problem for all possible input sizes.

Each time Dijkstra's is run on an instance, which may be of any size, it implicitly proves that its output is the one true answer and no other. In chess and image recognition, one gives the best answer one can and errors are tolerated. Furthermore, one only trains networks to solve these problems of one size at a time. I don't think we know yet how to generalize such a neural net solution to, say, problem instances of entirely different sizes and shapes.

I don't think we should assume that neural nets can't solve shortest-paths or similar algorithmic problems, but they solve problems in a fundamentally different way than a step-by-step algorithm that is always correct.

Going back to the similarity between neural nets and circuits, note that circuits have been studied for decades, yet judging by the lack of answers to (5) of my previous question, we know almost nothing about how to construct fully correct circuits for a given problem except via transforming a uniform algorithm (Turing Machine) into a circuit.

Answer 4

I am not an expert by any means, but I don't see why not, yet.

Neural networks fundamentally perform optimization according to some sort of "cost/benefit model" that's often already known before-hand. Additionally, the search space is well-defined, with valid and invalid moves that are known, and "variations" that are easy to define. Even for AlphaZero and AlphaGo, the cost functions are probably based on win-rate and the resulting win-rates distribution for all possible moves after making a move, or some sort of heuristic for that.

For devising algorithms, you are essentially asking the program to learn how to output a correct string (with an implicit encoding and cost function already known) that corresponds to a program that "executes an algorithm." However, there are possibly infinitely many algorithms for which you an implement a program with. So perhaps you'll want to define the correct "fitness" metrics.

However, even for certain programs, "fitness" metrics can be somewhat hard to define. Time? Space usage? Quantification of "side effects?" Optimally, you'll generate "the shortest program" that does only what you want it to do.

I suppose that if you find the correct fitness metrics and adjustment algorithms, you'll be able to do this.

Answer 5

"neural networks " transform a vector from one dimensional space to another dimensional space. so they are nothing more than highly , highly non-linear function approximators. even neural networks use approximation algorithms for their loss minimization . however training neural networks for devising new algorithms is out of question. tomas mikolov did some work in this area with stack augmented recurrent neural network , and i have also heard about "neural turing machines" for this domain. however finding optimal strategies has been the fundamental cause of studying reinforcement learning which is somewhat related to your question. but using neural networks for devising new algorithms is not possible , atleast in the near future.

Answer 6

I am a QA Automation engineer so don't claim expertise at neural networks, but, tautologically, yes NN can themselves create algorithms. Humans themselves are NN at some level, and we create algorithms, so it stands to reason that artificial NN systems we create can themselves create algorithms.