I just have read an article "Training Feedforward Neural Networks Using Genetic Algorithms" written by David J Montana. Experiment 5 compares BP and GA to train ANN, the results show that GA is faster and gives smaller error margin than BP. If those results can be generalized why does BP dominate ANN training?
the link to the paper: http://ijcai.org/Past%20Proceedings/IJCAI-89-VOL1/PDF/122.pdf
Ahmed,
First of all, that article that you cite is from 1989. Much has changed in the last quarter century of research relative to neural networks, and conclusions drawn from applying one non-optimal implementation of classic batch-based back-prop to a single ill-described program cannot be trusted to make decisions about current problems. In particular, advances like Stochastic Gradient Descent, AdaGrad, the use of rectified linear units (ReLU), drop-out regularization, L1 regularization, k-sparse and deep learning have all made massive improvements in the applicability of neural networks to hard problems.
To put it another way, the performance on the MNIST written digit problem has improved from the original 5-12% error rate in 1998 to a standard of ~0.3% more recently. (see http://yann.lecun.com/exdb/mnist/ ). Note also that almost all of the leading systems are neural networks trained using some variant of gradient descent. The only exceptions are SVM's which are commonly also trained using a variant of gradient descent. None of the recent competitive systems have used GA's for optimization.
The points that Nizar made relative to gradient descent versus GA's are somewhat misleading. Here are specific comments which quoted comments from Nizar:
> 1- The objective function might be discontinuous.
Many approaches are available to deal with this. Relaxation methods are commonly used. Hybrid gradient and stochastic methods can be used. See my work on recorded step EA's. http://arxiv.org/abs/0803.3838
In practice, many important problems actually have continuous objectives with gradients defined except for a set of measure 0. These problems can be handled nicely using gradient descent. See for instance the Lasso work from Stanford. http://statweb.stanford.edu/~tibs/lasso.html
> 2- Gradient-based method are very efficient when the search for an optimum happens
> in an elliptical domain, in other words the algorithm searches around a stationary
> point.
This is not exactly a criticism of gradient methods. The unstated criticism that gradient methods are not efficient outside of such problems is simply incorrect. Modern gradient systems handle much more than simple Gaussian bowls.
> 3- Gradient-based method are inefficient when the search space solution is large, i.e.
> in the case of Neural Network. The convergence of the algorithms is often hard to
> achieve;
This is simply incorrect with modern techniques. See the Android speech recognition system which is based on neural networks trained using gradient methods.
> 4- therefore, the choice of a starting point conditions the search and the efficiency of
> a gradient-based method. Converge towards a local minimum is much likely to occur.
This is also pretty much incorrect relative to modern practice. It is common to start with small random weights, but most systems are relatively insensitive to starting conditions.
> Genetic algorithms are stochastic and do not rely on the topology of the objective
> function, they do not compute gradients. Their advantages can be resumed by the
> following
This is simply incorrect. GA convergence strongly depends on the fitness landscape and the population can be seen as encoding some gradient information. Furthermore, systems like recorded-step meta-mutation explicitly incorporates history into the mutation with very good effect.
> 1- Regardless of the continuity or discontinuity of the objective function, they will
> always approximate a solution. Hence, they offer a reduced sensibility to noise.
This does not follow. Gradient based systems also always approximate a solution. Noise sensitivity and robustness to discontinuous objectives are two completely separate questions.
> 2- Instead of a starting point, they use a starting population of points (individuals)
> which follows a random and uniform distributions.
This is essentially irrelevant. You can start many gradient methods with many starting points and get essentially the same effect.
> 3- The search space is swept uniformly. As a consequence, large domains are pre-
> explored by evaluating the performance (the evaluation of the objective function) of
> each starting individual of the population.
Actually, GA's don't do this. If they did, they would be hopeless inefficient for large problems. Instead, they focus efforts on areas with initial good solutions.
> 4- High performance individuals are promoted (selected to become parents) and are
> combined following crossover operators to create a better (in the means of
> performance) new population (offspring). The mutation operator, which is referred in
> the cited article, allows a random search of possible high-performance individuals. In
> this way, the search space solution is swept at each iterations and GA are likely to
> converge to a global optimum.
Again, this is pretty much non-sequitur. Cross-over may help or hurt, depending on the problem. Probability of convergence within any time bound does not follow and is often much worse with GA's precisely because they try to sample so much of the problem space.
In fact, the best is to combine both backpropagation + GA in what is today called a memetic algorithm. We did it a loong time ago http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.5912
Dear Ahmad.
As I looked at the paper It says combining BP with GA is better than using BP alone. In a standard BP training, weights are not selected in an optimal way.
A way to find a globally optimal set of weights would be to use some optimization techniques such as PSO, GA, etc. This paper try to show that this is true (See Experiment 5 results in Fig. 8).
The paper and experiment, anyways, is not exactly state of the art, being 25 years old... much has been done (and written) since then.
The main reason might be that BP is more or less an exact method, while EAs are probabilistic, and people tend to trust the former more. As you indicated, the question also is, if these comparisons can be generalized. I doubt it, as there are many variants of BP and EAs. A big issue is scalability, as EAs certainly face enormous search spaces with increasing complexity of the networks. So in fact, a combination of methods might be the best choice.
BP may result in the local minimum. I am not sure that BP is still used extensively. At least in the research community, one can find many applications of EAs (or memetic algorithms) in training and designing EA.
I believe use of any algorithm depends on how easy/ simple it is and how fast/ cheap (computational cost) it is. BP is usually run as a form of error correction learning. So the network is adaptive to the error, and faster (than GA/EC). This algorithm just tries to minimize error.
In EC based approach, although the end aim is to find parameters to generalize the network efficiently, it is very time and resource consuming (more particles/ chromosomes are required for complete coverage of search space). As the samples increase, this becomes cumbersome.
Again, it also depends on others' mindset (people still dont trust neural networks very much).
Hello,
The article discusses training Neural Network. The drawback of gradient-based methods (BackPropagation) is
1- The objective function might be discontinuous. Therefore optimality conditions cannot be met using gradient-based methods which require differentiability. The algorithm fails.
2- Gradient-based method are very efficient when the search for an optimum happens in an elliptical domain, in other words the algorithm searches around a stationary point.
3- Gradient-based method are inefficient when the search space solution is large, i.e. in the case of Neural Network. The convergence of the algorithms is often hard to achieve;
4- therefore, the choice of a starting point conditions the search and the efficiency of a gradient-based method. Converge towards a local minimum is much likely to occur.
Genetic algorithms are stochastic and do not rely on the topology of the objective function, they do not compute gradients. Their advantages can be resumed by the following
1- Regardless of the continuity or discontinuity of the objective function, they will always approximate a solution. Hence, they offer a reduced sensibility to noise.
2- Instead of a starting point, they use a starting population of points (individuals) which follows a random and uniform distributions.
3- The search space is swept uniformly. As a consequence, large domains are pre-explored by evaluating the performance (the evaluation of the objective function) of each starting individual of the population.
4- High performance individuals are promoted (selected to become parents) and are combined following crossover operators to create a better (in the means of performance) new population (offspring). The mutation operator, which is referred in the cited article, allows a random search of possible high-performance individuals. In this way, the search space solution is swept at each iterations and GA are likely to converge to a global optimum.
For these reasons mainly, genetic algorithms are efficient when dealing with large domains.
As it has been underlined by the researchers who answered, hybrid methods (GA and gradient-based) are efficient also. The global optimum found using GA can be used as a starting point for gradient-based methods that are able to ameliorate the solution.
have a nice day
This is the same as the question "Why do people still use the simplex method given that interior point methods are so much faster?" The answer to that question is that in many linear programming problems, interior point methods are overkill, and yet, people use canned active set based convex programming approaches -- interior point methods -- even for the smallest problems. Yet they write papers talking about the simplex method.
Most "real world" applications of neural networks -- even those with significant "Wow" factor -- are just a notch or two above logistic regression, and BP (with interventions) is manageable and effective. The actuality, though, is that even when people talk about using BP, then they likely are using Conjugate Gradient or other convex programming approach and handling local minima with annealing or relaxation or similar. Also, BP and BP like approaches allow us to address the most common drawback of ANN's in applications, which is overfitting.
However, as the paper above points out, the research world lives at the extremes and not in the commonplace. Thus, even for those who use BP, there is great interest and utilization of GA's and similar methods when the problem at hand (e.g., large domain searches) goes beyond what the BP algorithm can handle. New methods always welcomed -- and often utilized -- even though the BP remains the "simplex" method of artificial neural networks.
I have never used GA/evolutionary algorithms to training neural networks for one reason: they are slow. Gradient based algorithms such as Levenberg-Marquardt or conjugate gradient are faster. Maybe for small NN (ten, twenty weights) using GA/EA gives reasonable training time.
GA/EA allows us to get global optimum (theoretically). But is it really good idea (to get training error minimum) in neural network training? I am not sure.
@Nizar Harb, nice detailed answer,
thanks to all of you guys, your experiences saved a lot of my time and taught me a lot.
Using evolutionary algorithms to design and optimise ANNs has become increasingly popular in recent years. See NEAT for instance (http://www.cs.ucf.edu/~kstanley/neat.html). Beyond the issues that have already been discussed, another advantage of EAs is their ability to optimise the topology of the network in addition to the weights. This is particularly useful when a suitable topology can not be estimated a priori. Grammatical and cellular models can also be used with EAs, allowing large network topologies to be patterned using processes akin to biological development. EAs can also be used to explore a wider space of connectionist models, such as neural networks with non-differentiable nodal functions (see my work on biochemical connectionism, for instance - https://www.researchgate.net/publication/257423690_Biochemical_Connectionism).
Article Biochemical Connectionism
Since many years support vector machines (SVMs) outperform back propagation for function approximation in terms of error rate and in terms of computing time. And they are also much better than GAs to my knowledge. Does anybody know an empirical comparison of SVMs to GAs and maybe backlprop?
BTW: Backprop is no longer used in practice because it has been replaced by RPROP (Riedmiller et. al.)
For real-time applications one often needs online algorithms; most GA's are only effective offline and then for relatively small data sets. As far as I am aware, for online algorithms one needs deterministic recursion relations that are Markov; gradient methods are incredible useful in this regard. So it really depends on the application and the data-set in question.
Ahmed,
First of all, that article that you cite is from 1989. Much has changed in the last quarter century of research relative to neural networks, and conclusions drawn from applying one non-optimal implementation of classic batch-based back-prop to a single ill-described program cannot be trusted to make decisions about current problems. In particular, advances like Stochastic Gradient Descent, AdaGrad, the use of rectified linear units (ReLU), drop-out regularization, L1 regularization, k-sparse and deep learning have all made massive improvements in the applicability of neural networks to hard problems.
To put it another way, the performance on the MNIST written digit problem has improved from the original 5-12% error rate in 1998 to a standard of ~0.3% more recently. (see http://yann.lecun.com/exdb/mnist/ ). Note also that almost all of the leading systems are neural networks trained using some variant of gradient descent. The only exceptions are SVM's which are commonly also trained using a variant of gradient descent. None of the recent competitive systems have used GA's for optimization.
The points that Nizar made relative to gradient descent versus GA's are somewhat misleading. Here are specific comments which quoted comments from Nizar:
> 1- The objective function might be discontinuous.
Many approaches are available to deal with this. Relaxation methods are commonly used. Hybrid gradient and stochastic methods can be used. See my work on recorded step EA's. http://arxiv.org/abs/0803.3838
In practice, many important problems actually have continuous objectives with gradients defined except for a set of measure 0. These problems can be handled nicely using gradient descent. See for instance the Lasso work from Stanford. http://statweb.stanford.edu/~tibs/lasso.html
> 2- Gradient-based method are very efficient when the search for an optimum happens
> in an elliptical domain, in other words the algorithm searches around a stationary
> point.
This is not exactly a criticism of gradient methods. The unstated criticism that gradient methods are not efficient outside of such problems is simply incorrect. Modern gradient systems handle much more than simple Gaussian bowls.
> 3- Gradient-based method are inefficient when the search space solution is large, i.e.
> in the case of Neural Network. The convergence of the algorithms is often hard to
> achieve;
This is simply incorrect with modern techniques. See the Android speech recognition system which is based on neural networks trained using gradient methods.
> 4- therefore, the choice of a starting point conditions the search and the efficiency of
> a gradient-based method. Converge towards a local minimum is much likely to occur.
This is also pretty much incorrect relative to modern practice. It is common to start with small random weights, but most systems are relatively insensitive to starting conditions.
> Genetic algorithms are stochastic and do not rely on the topology of the objective
> function, they do not compute gradients. Their advantages can be resumed by the
> following
This is simply incorrect. GA convergence strongly depends on the fitness landscape and the population can be seen as encoding some gradient information. Furthermore, systems like recorded-step meta-mutation explicitly incorporates history into the mutation with very good effect.
> 1- Regardless of the continuity or discontinuity of the objective function, they will
> always approximate a solution. Hence, they offer a reduced sensibility to noise.
This does not follow. Gradient based systems also always approximate a solution. Noise sensitivity and robustness to discontinuous objectives are two completely separate questions.
> 2- Instead of a starting point, they use a starting population of points (individuals)
> which follows a random and uniform distributions.
This is essentially irrelevant. You can start many gradient methods with many starting points and get essentially the same effect.
> 3- The search space is swept uniformly. As a consequence, large domains are pre-
> explored by evaluating the performance (the evaluation of the objective function) of
> each starting individual of the population.
Actually, GA's don't do this. If they did, they would be hopeless inefficient for large problems. Instead, they focus efforts on areas with initial good solutions.
> 4- High performance individuals are promoted (selected to become parents) and are
> combined following crossover operators to create a better (in the means of
> performance) new population (offspring). The mutation operator, which is referred in
> the cited article, allows a random search of possible high-performance individuals. In
> this way, the search space solution is swept at each iterations and GA are likely to
> converge to a global optimum.
Again, this is pretty much non-sequitur. Cross-over may help or hurt, depending on the problem. Probability of convergence within any time bound does not follow and is often much worse with GA's precisely because they try to sample so much of the problem space.
Brilliant answer Ted!
Just to support what Ted said look at this paper: http://link.springer.com/article/10.1007/s10898-012-9951-y
In this paper, the authors compared several derivative-free optimization techniques (genetic algorithms is one of them). In figure 9 of the paper, authors compared the performance of different algorithms for nonconvex smooth problems (the objective function of neural networks is also smooth and nonconvex). You can see that there are many other derivative-free algorithms that outperform genetic algorithm. Many of derivative-free algorithms used in this paper are also global optimizers like genetic algorithms.
If one can compute the derivative efficiently, then usually derivative-based methods outperform derivative-free techniques. The nice thing about neural networks is that you actually can compute the derivative of the objective function efficiently. So one should exploit this fact! To solve the problem of local minima a bit, one can start the optimization using different starting points.
Back-propagation Neural Network (BPNN) algorithm is one of the most widely used and a popular technique to optimize the feed forward neural network training. Traditional BP algorithm has some drawbacks, such as getting stuck easily in local minima and slow speed of convergence. Nature inspired meta-heuristic algorithms provide derivative-free solution to optimize complex problems in achieving fast convergence rate and to avoid local minima problem. Computational efficiency of BP training process is highly enhanced when coupled with the proposed hybrid method using nature inspired meta-heuristic algorithms.
I feel recently developed Cuckoo Search and Modified Cuckoo Search may be of help to Train Back Propagation and to show a high convergence rate to the true global minimum even at high numbers of dimensions.
1. A New Back-Propagation Neural Network Optimized with Cuckoo Search Algorithm
Nazri Mohd. Nawi , Abdullah Khan , M. Z. Rehman
Link:
https://www.academia.edu/6850696/A_New_Back-Propagation_Neural_Network_Optimized_with_Cuckoo_Search_Algorithm
Abstract.
Back-propagation Neural Network (BPNN) algorithm is one of the most widely used and a popular technique to optimize the feed forward neural network training. Traditional BP algorithm has some drawbacks, such as getting stuck easily in local minima and slow speed of convergence. Nature inspired meta-heuristic algorithms provide derivative-free solution to optimize complex problems. This paper proposed a new meta-heuristic search algorithm, called cuckoo search (CS), based on cuckoo bird’s behavior to train BP in achieving fast convergence rate and to avoid local minima problem. The performance of the proposed Cuckoo Search Back-Propagation (CSBP) is compared with artificial bee colony using BP algorithm, and other hybrid variants. Specifically OR and XOR datasets are used. The simulation results show that the computational efficiency of BP training process is highly enhanced when coupled with the proposed hybrid method.
2. Modified cuckoo search: A new gradient free optimisation algorithm
S. Walton, O. Hassan, K. Morgan, M. R. Brown
Link:
https://www.researchgate.net/publication/233415496_Modified_cuckoo_search_A_new_gradient_free_optimisation_algorithm
ABSTRACT A new robust optimisation algorithm, which can be regarded as a modification of the recently developed cuckoo search, is presented. The modification involves the addition of information exchange between the top eggs, or the best solutions. Standard optimisation benchmarking functions are used to test the effects of these modifications and it is demonstrated that, in most cases, the modified cuckoo search performs as well as, or better than, the standard cuckoo search, a particle swarm optimiser, and a differential evolution strategy. In particular the modified cuckoo search shows a high convergence rate to the true global minimum even at high numbers of dimensions.
3. A New Back-Propagation Neural Network Optimized with Cuckoo Search Algorithm
Nazri Mohd Nawi, Abdullah Khan, Mohammad Zubair Rehman
Link:
https://www.researchgate.net/publication/244478637_A_New_Back-Propagation_Neural_Network_Optimized_with_Cuckoo_Search_Algorithm?ev=pub_cit_inc
ABSTRACT Back-propagation Neural Network (BPNN) algorithm is one of the most widely used and a popular technique to optimize the feed forward neural network training. Traditional BP algorithm has some drawbacks, such as getting stuck easily in local minima and slow speed of convergence. Nature inspired meta-heuristic algorithms provide derivative-free solution to optimize complex problems. This paper proposed a new meta-heuristic search algorithm, called cuckoo search (CS), based on cuckoo bird’s behavior to train BP in achieving fast convergence rate and to avoid local minima problem. The performance of the proposed Cuckoo Search Back-Propagation (CSBP) is compared with artificial bee colony using BP algorithm, and other hybrid variants. Specifically OR and XOR datasets are used. The simulation results show that the computational efficiency of BP training process is highly enhanced when coupled with the proposed hybrid method.
4. Conference Paper: CSBPRNN: A New Hybridization Technique Using Cuckoo Search to Train Back Propagation Recurrent Neural Network
Nazri Mohd Nawi, Abdullah Khan, M. Z. Rehman
[Show abstract]
Link:
https://www.researchgate.net/publicationhttps://www.researchgate.net/publication/259982596_CSBPRNN_A_New_Hybridization_Technique_Using_Cuckoo_Search_to_Train_Back_Propagation_Recurrent_Neural_Network?ev=pub_cit_inc
P.S.
Article Modified cuckoo search: a new gradient free optimisation alg...
Conference Paper A New Back-Propagation Neural Network Optimized with Cuckoo ...
Conference Paper CSBPRNN: A New Hybridization Technique Using Cuckoo Search t...
ANN is simple to use and works well enough at the first analysis approach.
Dear Ahmad, probably the simplest answer could be the right one. If you use a GA for training an ANN, then you have to solve two problems instead of one: you need to find a good set of parameters for the GA (mutation rate, population size, number of epochs, kind of recombination, elitism, and etc.) plus a good fitness function that could evaluate on the ANN the performance of the found weights set encoded in every one of the individuals of the GA population, at each GA iteration (often this fitness is found by evaluating the mean squared error of a test-set fed to the ANN that is precisely what BP does). In those cases, the time consumed for the GA could be much greater than the one required for the BP.
In my experience, the advantage of using GA resides in the ability of suggesting changes in the ANN Architecture. If in the genotype the ANN architecture is also coded, then not only the weights of the network can be optimized, but THE WHOLE ANN ARCHITECTURE. This cannot be done with BP, because it 'dilutes' (propagates) the error in a more softer way that in a GA, where no relationships between the errors at the different layers must be met. Therefore, in BP would be very rare to have some weights equal to zero, that would imply removing connections. Also, the main problem with GAs is mainly the inability of prevent it from over-fitting, something that at least we know that have direct relationship with the number of training epochs in BP.
Finally, if we would see the problem under a pure mathematical (or object-oriented programming) point of view, the operation (or method) BP would be defined within the scope of the class Artificial Neural Networks. This imply that no other thing (or class) would be necessary to solve (train) an ANN but the ANN class itself. As in the case of the dot product for vectors, by using Neural Algebras (an extended set of Linear Algebra) it is possible to define the BP as an operation (or mathematical operator) over ANNs. By introducing a GA as a general method for solving (training) ANNs, the students and researchers would need to go out beyond the scope of ANNs, in order to solve such systems, adding much more complexity that mainly computing simple partial derivatives as BP does.
In general, we could say that for those cases where a relatively low mean square error is enough, then BP would be adequate. For those cases where reaching the true minimum as well as the minimum architecture that optimizes the solution is fundamental, then GAs are quite better, but he problem would be of course not to get lost in the attempt.
I hope this help.
Regards,
I do not believe that GA are faster than BP. With respect to convergence to the global minimum, it may happen that GA is better that simple BP. However there are many improvements in BP that increased its capability. Moreover, other meta heuristics, such as simulated annealing, may also show better performance with respect to convergence. We must be careful about many things written about GA. My experience says that for a sufficiently big initial population, GA take long time to find good solutions. There is still a long road to obtain an algorithm that guarantees convergence to the global optimum on ANN training.
Even though Back propagation has slow convergence time but it will converge to the solution. That's why back propagation still extensively used especially in classifications and forecasting problems.
Back propagation isn't even that slow. The question was a silly one that presumed an answer that is contrary to experience.
@Ted Dunning, there is no silly question and intelligent question Ted, we all are learning here, in a friendly platform! trying to get experience such as yours.
Ahmad,
A good question is one that doesn't presume an answer. The question that started this discussion presumed that,
1) GA's work better than BP
2) a paper that is 25 years old will not have been superseded in an active area of research
A better version of this question would be more along the lines of:
"I found this old paper that claims that genetic algorithms are as good or better for training NN's than backprop. Is there a more recent consensus on this? Did this result hold up? Have other developments made this old result irrelevant?"
This is better because it doesn't turn off possible answers by taking a relatively uninformed but still quite dogmatic position.
Here are some link on how to ask a good question. Not all apply directly to RG, but they are still good advice:
http://stackoverflow.com/help/how-to-ask
http://www.catb.org/esr/faqs/smart-questions.html
Ted, off the topic
you keep annoying me by schooling me how to ask a question, I wrote a Msc thesis, PhD thesis and more than 15 research papers using your own language, I dare you if you can say hello in my language.
I chose the old paper to show that researchers used to use GA for ANN long time ago, so BP should be extinct now a days, the new trends now is to use GA not only for optimizing the weights but also to choose the topology of ANN (the number of hidden layers and the number of nodes in each). retaining much better performance.
I asked the question because I wanted to use ANN in one of my projects, the first thing came to my mind is BP, but with little research I became confused in how to train ANN, what is the best way to do it? GA or BP
If the problem with GA stems from the convergence time, you proposed a method to accelarate convergence time for GA algorithms I quote "This work clearly shows that meta-evolutionary strategies can be effective in accelerating the convergence of evolutionary programming algorithms under certain conditions." https://www.researchgate.net/publication/1916718_Recorded_Step_Directional_Mutation_for_Faster_Convergence
Article Recorded Step Directional Mutation for Faster Convergence
Take your pick. GAs are global optimisers or at least can be, but are slow in terms of
"learning" time. Are we talking about supervised learning? If so back- prop and more recent methods will easily outperform a GA. Are we talking MLP NNs? Radial basis function (RBF) NNs which use more "local" learning can be better approximators but not so good at generalisation. In my limited experiences, using a GA to learn is slow. The best way forward I have found is to use a GA to optimise the architecture of the NN in conjunction with back-prop or more recent algorithms.
Hello Ahmad and all others
.
One powerful reason is simplicity. In average the C language code for a GA solution requires about 7 to 10 times more code lines than a ANN-Backpro equivalent. Being development cost directly related to software complexity ANN-Backpro is a winner. It should be said that GAs have a much more powerful “climbing capacity” toward an ideal solution than Backpro does.
From my experience of dealing with NNs, which have 10^4 - 10^6 weights (and it is the dimensionality of the training space) and with training sets containing 10^5 - 10^6 records, nothing except slightly improved (ennobled) backprop works. Other more sophisticated algorithms simply suffocate and give no results.
I commonly use a GA and BPNN in my work. Typically, I use BPNN to further investigate a feature set that was selected by the GA. BPNN runs exponentially faster than the GA in my experience, even if it hits the maximum number of epochs without converging (I typically run 200 generations on the GA and 10,000 epochs on BPNN). Based on this, I believe that even if I were giving BPNN the "All Features" problem, it would still be consistently faster than the GA. The first paragraph in Ted Dunning's answer from May 14th sums it up: BPNN is far more advanced than it was in 1989.
I've been experimenting with NN and CMA-ES, up to 4e5 dimensions. My first main observation is that convergence is very slow, though it eventually yields the expected results on a classical dataset I did experiment with.
At this stage, and if this can help in the conversation, my view is that if there's room for GA outside the fitting of the network architecture itself, it might lie in the optimization of the network once gradient-based method that rely on BP have converged.
Code is available if some of you believe it can be inspiring.
One possible advantage of GAs over gradient descent methods is that, in the former, the metric is arbitrary, whereas in the latter L2 is usually applied. This does not mean that L2 is inferior. But GAs applied to training NNs are apt to be more flexible. At least in this aspect.
Comments regarding the length (in terms of lines of code) of one approach vs. any other tend to be secondary if the "larger" implementation leads to better answers.
Hello all,
If we look deeply to the concept of back propagation, we can realise that it works like a " Guided Genetic Algorithm " approach for every node in the network. If we assume that the next generation of weight is intentionally modified.
Thanks,
A simple comment. In order to be able to generalize as to the size of the codes we have to specify the type of GA we are dealing with. From the comments above it would seem that only one such GA does exist. This is not so. There are at least 5 structuraly different GAs. Some are definitely faster than others. Also I would like to clarify that GAs do not learn in the sense that NNs do. These are optimization and not learning methods.
Regards,
A true genetic algorithm model, with the three basic operations of selection, mutation and crossover is much more complicated, in terms of programming, that a pure backpro algorithm.
Backpropagation is well known for get trapped in local minima. On the other hand, GA avoids this difficulty by using several search agents.
Erik Cuevas is correct (and full disclosure: I am also an EA fan :-D), but there is an interesting semi-theoretical result mentioned in the "Deep Learning Book" (Goodfellow et al.): in practice, researchers in NNs observed that - as the number of dimensions/weights in a NN increases - the local optima in the fitness landscape become vanishingly few, while saddle points increase (this might be true for their specific kind of problem, only). And backpropagation (stochastic gradient descent and the like) is able to escape saddles. So, NN practitioners are not using EAs/GAs because *they don't need to*.
https://stats.stackexchange.com/questions/55887/backpropagation-vs-genetic-algorithm-for-neural-network-training
Please go through my Presentation on
"Voronoi Diagrams & Delaunay Triangulations - Their Applications in Computer Science"
Link : Data Voronoi Diagrams & Delaunay Triangulations - Their Applicati...
Abstract :
Voronoi Diagrams and Delaunay Tringulations(Power Diagrams) are the latest trend in not only Computer Science,but in many other Areas. Delaunay Triangulations is Dual of Voronoi Diagrams. Delaunay implies Optimization. Locally Delaunay everywhere ⇐⇒ Globally Delaunay. These Diagrams get the Optimal Solutions in one Stretch. The Presentation had been given by the Author to the Faculty of C.S.E. and I.T. Departments of V.B.I.T.,Hyderabad and was well Received. It is only a Compilation done by the Author from different Resources and not a Original Work. It will help a Peep into this New Area of Research.
P.S.
- Badges
- Science topic