34
$\begingroup$

I've read a few papers discussing pros and cons of each method, some arguing that GA doesn't give any improvement in finding the optimal solution while others show that it is more effective. It seems GA is generally preferred in literature (although mostly people modify it in some way to achieve results they need), then why majority of software solutions seem to use backpropagation only?

Is there some general rule of thumb when to use one or another? Maybe it depends on type of NN or there exists some state of the art solution which generally outperforms others?

If possible I'm looking for general answers: i.e., "if the NN is huge, GA is better", or "GA is always better but has computational performance issues" etc...

$\endgroup$
23
$\begingroup$

If you look carefully at the scientific literature you'll find contrasting results. Obviously, in some cases GA (and more in general, Evolutionary Algorithms) may help you to find an optimal NN design but normally they have so many drawbacks (algorithm parameters' tuning, computational complexity etc) and their use is not feasible for real-world applications. Of course you can find a set of problems where GA/EAs is always better than backpropagation. Given that finding an optimal NN design is a complex multimodal optimization problem GA/EAs may help (as metaheuristics) to improve the results obtained with "traditional" algorithms, e.g. using GA/EAs to find only the initial weights configuration or helping traditional algorithms to escape from local minima (if you are interested I wrote a paper about this topic).

I worked a lot on this field and I can tell you that there are many scientific works on GA/EAs applied to NNs because they are (or better, they used to be) an emerging research field.

$\endgroup$
  • 2
    $\begingroup$ This is something I also came up with recently - first find 'good' solution and then improve it further with GA. Not only applicable to NNs, but optimization in general... $\endgroup$ – sashkello Apr 21 '13 at 4:35
  • 1
    $\begingroup$ I'm confused why they are mutually exclusive. I thought GA is supposed to learn the structure; Backpropagation can only learn the weights $\endgroup$ – pete Apr 27 '15 at 19:22
8
$\begingroup$

One of the key problems with neural networks is over-fitting, which means that algorithms that try very hard to find a network that minimises some criterion based on a finite sample of data will end up with a network that works very well for that particular sample of data, but which will have poor generalisation. I am rather wary of using GAs to design neural networks for this reason, especially if they do architecture optimisation at the same time as optimising the weights. I have generally found that training networks (with regularisation) from a number (say 20) of random initial weight vectors and then forming an ensemble of all the resulting networks is generally as good an approach as any.

Essentially optimisation is the root of all evil in machine learning, the more of it you do, the more likely you are to end up over-fitting the data.

$\endgroup$
  • $\begingroup$ Dikran, though GA make natural selection but does not ignore the information as you mentioned, it only ensure if the selected solution solve its problem if not, it find out to know why and upgrade the agorithm which form the basis of it dynamism till the network converge at one or two best solution. hope you get that rignt? $\endgroup$ – user55737 Sep 13 '14 at 17:53
  • $\begingroup$ converging to the best solution evaluated over a finite sample of data is exactly what causes over-fitting. To avoid overfitting you want to converge on a solution that is not the best (e.g. early stopping in training neural networks). GAs are no better than any other form of optimisation in fitting neural networks, you need to avoid over-optimising the training criterion. $\endgroup$ – Dikran Marsupial Sep 15 '14 at 7:59
5
$\begingroup$

Whenever you deal with huge amounts of data and you want to solve a supervised learning task with a feed-forward neural network, solutions based on backpropagation are much more feasible. The reason for this is, that for a complex neural network, the number of free parameters is very high. One industry project I am currently working on involves a feed-forward neural network with about 1000 inputs, two hidden layers @ 384 neurons each and 60 outputs. This leads to 1000*384 + 384*384 + 384*60 = 554496 weight parameters which are to be optimized. Using a GA approach here would be terribly slow.

$\endgroup$
  • $\begingroup$ My understanding is that GA is designed to tackle problems which are harder to solve with standard approaches. Shouldn't it perform better exactly in a situation you described? $\endgroup$ – sashkello Apr 13 '13 at 1:50
  • 2
    $\begingroup$ I thought GA is supposed to be used to figure out what structure it is e.g. how many hidden layers and how they are connected. Backpropagation can only figure out the weights $\endgroup$ – pete Apr 27 '15 at 19:23
2
$\begingroup$

Second answer is wrong. Overfitting isn't caused by optimization. Overfitting happens when your model is over-complicated and can fit all the datapoints without learning the actual rule that created them (i.e. just memorizing them, in the extreme case.) There are many ways to prevent overfitting such as choosing simpler models, dropout, dropconnect, weight decay, and just using more data. The goal should be to optimize your network and make it as accurate as possible, taking those constraints into account.

To answer the question, backprop is supposedly much faster than stochastic optimization (genetic algorithms and the like.) My guess is this is because it takes advantage of what the actual output was supposed to be, adjusts the weights in the right direction based on that, where stochastic optimization tries completely random changes and ignores that information.

However by exploring a larger area, GAs will probably do better in the long run by avoiding local optimas, it will just take longer to train.

I am curious how much slower GAs are than backprop, and if anyone knows of hybrid algorithms (scatter search seems like it would be ideal for this.)

$\endgroup$
  • 1
    $\begingroup$ Disagree with your first paragraph. Overfitting is prevented mainly via regularization approaches in the training problem. If you start doing meta-optimization --- that is solving lots of training problems (for example tuning kernel parameters, network architectures, ...) -- taking care of overfitting becomes much more difficult and is certainly not implicitly guaranteed anymore. $\endgroup$ – Marc Claesen Sep 14 '14 at 7:51
  • $\begingroup$ If overfitting were not caused by optimisation, early stopping wouldn't be an effective remedy for overfitting. $\endgroup$ – Dikran Marsupial Jan 10 at 16:49
1
$\begingroup$

imho the difference between GA and backpropagation is that GA is based on random numbers and that backpropagation is based on a static algorithm such as stochastic gradient descent. GA being based on random numbers and add to that mutation means that it would likely avoid being caught in a local minima. But then GA being based on random numbers means that it is fairly likely for 2 different times you run the learning on the same network, it may reach a different conclusion i.e. a different set of weights

$\endgroup$
  • $\begingroup$ Just commenting, we also use random init. for the weights in back-prop. If we use the same seed while initializing, it will lead to the same solution, but if you don't, probably it won't. So, back-prop, too, depends on a random input. When you fix the seed, you'll also have the same result in genetic algorithm since it'll use the same seq. of numbers again. $\endgroup$ – gunes Dec 24 '18 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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