10
$\begingroup$

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. They use genetic algorithms to "evolve" the weights of the axons.

So basically my idea is the following. If I was supposed to write a program that recognizes numbers I would not know how to start (I could have some vague idea but my point is: It is not trivial, nor easy.) but by using neural network I do not have to. By creating the right context in order for the neural network to evolve, my neural network will "find the correct algorithm". Down below I quoted a really interesting part of the article where they explain how each layer have different role in the process of image recognition.

One of the challenges of neural networks is understanding what exactly goes on at each layer. We know that after training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. For example, the first layer maybe looks for edges or corners. Intermediate layers interpret the basic features to look for overall shapes or components, like a door or a leaf. The final few layers assemble those into complete interpretations—these neurons activate in response to very complex things such as entire buildings or trees.

So basically my question is the following: Couldn't we use genetic algorithms + neural networks in order to solve every NP problem? We just create the right evolutionary context and leave "nature" find a solution.

Inceptionism: Going Deeper into Neural Networks

EDIT: I know we can use Brute-Force or find a not-efficient solution in many cases. That is why I try to highlight Evolving artificial neural networks. As I said in a comment: Given sufficient time and an appropriate mutation rate we could find the optimal solution (Or at least that is what I think).

Concept

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ We don't have to. We can simply use brute-force. What is your goal, exactly? $\endgroup$
    – Pål GD
    Sep 23, 2015 at 15:23
  • 2
    $\begingroup$ I am not an expert on neural networks so I don't know if they can be trained to solve NP problems correctly. But I don't think you are asking the right question. Coming up with an algorithm that solves a problem contained in NP is usually not difficult, just check every possible solution. However, finding an algorithm that solves an NP-hard problem in polynomial time is a different story and its existence is highly unlikely. Since neural networks can be simulated by a truing machine, they still need super polynomial time unless P=NP and won't be of much help. $\endgroup$
    – Dennis Kraft
    Sep 23, 2015 at 15:23
  • $\begingroup$ yes, neural nets have been used against NP complete problems eg Travelling Salesman and many others and there is research/ literature on the subj. they can have some useful properties but they dont get away from time constraints of complexity theory as DK points out. $\endgroup$
    – vzn
    Sep 23, 2015 at 15:54
  • $\begingroup$ My point is: Using an appropiate mutation rate and sufficient time we could (at least theorically) find the optimal solution. (Or at least a local maximum) Image: Concept $\endgroup$
    – NMO
    Sep 23, 2015 at 16:21
  • 3
    $\begingroup$ Genetic algorithms (and the rest of the lot of "AI" techniques) are essentially randomized "try a sample of the solution space" with some smarts (heuristics) thrown in to make it not totally random. No, it is not better than "try all possible solutions", most of the time much worse (as there is no guarantee not to check the same discarded case again). Sure, they find "decent" solutions. But we want to find the best. $\endgroup$
    – vonbrand
    Sep 24, 2015 at 1:13

6 Answers 6

Reset to default
22
$\begingroup$

No. This direction is unlikely to be useful, for two reasons:

  1. Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the neural network will itself be a polynomial-time algorithm. It follows that if P $\ne$ NP, neural networks cannot efficiently solve any NP-complete problem.

  2. Neural networks aren't "magic". They are a way of trying to find patterns. For some problems where there are strong enough patterns to be found, and the patterns can be learned from a reasonable number of examples, they might be effective. But they're not magic fairy dust. Just because you can set up a neural network doesn't mean that backpropagation will necessarily find a good way to solve your problem. It might be that there are no patterns to be found, that the patterns can only be discovered with an unfeasible number of examples, or that patterns exist but the neural network training procedure isn't able to find them.

Neural networks are just another form of machine learning. We could make the same remarks about SVMs or random forests or linear regression any other form of machine learning. Neural networks aren't some kind of magical silver bullet that solve all machine learning problems. They're about as effective as other machine learning methods, or for some kinds of problems, maybe a little bit more effective, but they're not magic.

Sometimes I run across people who have heard only a little bit about neural networks, and they walk away thinking that neural networks are the answer to everything -- maybe because they heard that "your brain uses neural networks too", or they saw some very cool application (voice recognition or something). But don't be fooled. Don't believe the hype. Neural networks are a useful technique, but they're not going to enable computers to solve NP-complete problems, or to beat the Turing test, take away all our jobs and replace humans with computers. Not anytime soon, anyway. That's just science fiction.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Really good answer. Genetic Algorithms + Neural Networks seems very powerful but maybe it is not enough to solve every np problem. I imagine leaving this neural networks + genetic algorithms in the wild looking for this p solutions. Like little scouts haha. $\endgroup$
    – NMO
    Sep 23, 2015 at 17:05
  • 1
    $\begingroup$ May also be worth noting that neural networks typically provide some probability of finding the correct answer, not a guarantee. When you relax your problem requirements to allow sub-optimal solutions, there are very often practical solutions to NP-complete problems, despite their intractability in the worst case. $\endgroup$
    – Dan Bryant
    Sep 23, 2015 at 20:39
11
$\begingroup$

It seems other answers while informative/ helpful are not actually understanding your question exactly and are reading a little too much into it. You didn't ask if neural networks would outperform other methods, you only asked if they could be applied to NP complete problems. The answer is yes, with some success and this has been known for decades and there is a wide variety of research on this, and it continues. This has to do with the flexibility of machine learning. Note that even if they dont find exact or optimal solutions, the solutions they have may have other desirable properties. some example papers:

Improve this answer
$\endgroup$
4
$\begingroup$

Neural networks do not actually solve NP-complete problems. What they do do is solve problems which are remarkably close to NP-complete problems.

One big feature of neural networks is that they are not obliged to find the "right" answer every time. They are allowed to be "wrong." For example, you might be solving a bin-packing problem, and come to a solution which is 1% off of the ideal solution and be totally content with that answer.

If you remove the requirement of being 100% right every time, other problem solving approaches work very well. For example, many route planning algorithms (a la Google Maps) have to be NP-complete, but it is quite trivial to find an algorithm which finds a path within 1% of the optimum 99.9% of the time. It's trying to pin down results in that last 0.1% of the cases which drive NP-complete efforts to be so mindnumbingly expensive.

As it happens, when we try to use NP-complete equations in real life, we don't often need the actual answer. We're often very comfortable with a "close" answer, though we often don't have a wording to explain what "close" metric we are using. These are the situations where a neural network can answer the actual question you wanted to ask, rather than having to actually solve the NP-complete problem you asked for instead.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Neural networks are known to be capable of universal function approximation, but this requires training them on the problem (optimization) which is a NP-complete problem in and of itself, which is why you have evolutionary training and SGD with backpropagation and so on.

So while they are not likely to solve NP-complete problems they can be trained to approximate to an arbitrary degree of accuracy a function that models the problem. Also even if you happen to solve an NP-complete problem optimally using a neural network you still have no way to prove that the solution it found is actually the global optimum without brute forcing the solution (this is of course not feasible for almost any practical use case of neural networks).

Your visualization is accurate in the sense that evolutionary algorithms (see how the neat algorithm prevents a single species from taking over the population with an initially highly performant structure by using shared fitness) are less apt than SGD and other machine learning techniques to be trapped in local optimums but they provide no proof that the solution they find is in fact the global optimum solution.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Could you add some references to your answer? Also, try to improve the formatting (for example, use NP, SGD, backpropagation, and so on, and perhaps add some line breaks). $\endgroup$
    – Yuval Filmus
    Oct 31, 2019 at 12:06
  • $\begingroup$ Alright made some edits let me know any if I should go into further depth anywhere $\endgroup$
    – nickw
    Oct 31, 2019 at 14:30
  • $\begingroup$ I think you should provide some justification for your claim that "evolutionary algorithms...are less apt than SGD and other machine learning techniques to be trapped in local optimums". I don't think that's right, especially for the particular task of training neural networks. $\endgroup$
    – D.W. ♦
    Oct 31, 2019 at 21:16
  • 1
    $\begingroup$ This answer has some confusion about the definition of NP-completeness. Contrary to what you claim, if we solve a NP-complete problem, we can check whether we have the correct solution. There is a difference between a NP-complete search problem and a NP-hard optimization problem; for the former, we can indeed efficiently check whether the solution is correct, but for the latter we might not be able to. $\endgroup$
    – D.W. ♦
    Oct 31, 2019 at 21:17
  • $\begingroup$ I did qualify that we couldnt verify it is the optimal solution without brute forcing the truely optimal solution first, is this not correct? I provided justification for my reasoning that neuroevolution is less apt to get stuck in local optimums with the referenced link to the neat algorithm and shared fitness, I think gradient descents susceptibility to being stuck in local optimums is rather self evident, and while a hyperparameter tuning framework can help alleviate this i would not credit that as an aversion sgd possesses to getting stuck. $\endgroup$
    – nickw
    Nov 1, 2019 at 15:59
0
$\begingroup$

Even if P $\neq$ NP, that says nothing about average case complexity. That for any algorithm for solving a NP complete problem must have at least some instances where it takes more than polynomial time. However it is certainly possible that we find an AI that can solve sat in linear time for 80% of instances better then any conventional algorithm. I do not know enough about AI to give the likelihood of that

Improve this answer
$\endgroup$
0
$\begingroup$

Given that neural nets are good at interpolation (but poor at extrapolation), for a given use case it suffices to solve a few billion large problems and feed them to a sufficiently large net. In some cases this would work.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.