Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

Childhood Habituation in Evolution of Augmenting Topologies (CHEAT)

Moberg, Anton LU (2020) FYTM04 20201
Computational Biology and Biological Physics - Undergoing reorganization
Abstract
Neuroevolution is a field within machine learning that applies genetic algorithms to train artificial neural networks. Neuroevolution of Augmenting Topologies (NEAT) is a method that evolves both the topology of the network and trains the weights of the network at the same time, and has been found to successfully solve reinforcement learning problems efficiently and the XOR problem with a minimal topology. However, NEAT has not been shown to solve more complex labelling problems and has a vaguely motivated heuristic concept of speciation needed to keep a diverse population and protect new structural innovations from instant elimination. In this thesis a new algorithm was developed, the Childhood Habituation in Evolution of Augmenting... (More)
Neuroevolution is a field within machine learning that applies genetic algorithms to train artificial neural networks. Neuroevolution of Augmenting Topologies (NEAT) is a method that evolves both the topology of the network and trains the weights of the network at the same time, and has been found to successfully solve reinforcement learning problems efficiently and the XOR problem with a minimal topology. However, NEAT has not been shown to solve more complex labelling problems and has a vaguely motivated heuristic concept of speciation needed to keep a diverse population and protect new structural innovations from instant elimination. In this thesis a new algorithm was developed, the Childhood Habituation in Evolution of Augmenting Topologies (CHEAT) algorithm, which removes the need for the heuristic speciation concept and its associated hyper-parameters by splitting topology evolution and weight training into two distinct phases. CHEAT also allows for structured topology evolution by having the option of forcing fully connected layers. The algorithm was tested on the XOR problem and the spiral problem with two turns, with a result showing performances on par with NEAT for the XOR problem, and better results on the spiral problem where CHEAT is able to solve the problem while NEAT is not. It was found that without an early stopping criterion for gradient descent training, new structural innovations were quickly eliminated from the population before being optimally tuned, and thus the stopping criterion is vital to be able to remove the NEAT speciation heuristics. It was also found that restricting the algorithm to evolve in a structured manner by forcing fully connected layers was vital to solving any problems more complex than the XOR problem, likely due to the feature selection behaviour fully connected layers exhibit. The work done in this thesis opens further areas of research into evolving Artificial Neural Networks, where the most interesting leads lie in other weight training methods, different stopping criterion for gradient descent training, and finally letting the algorithm take control of evolution of its own hyper-parameters for automatic model construction. (Less)
Popular Abstract
Artificial Neural Networks are the computer equivalent to the human nervous system. Just like the nervous system is a network of neurons connected to other neurons by axons, the artificial neural network is a network of nodes connected to other nodes by links. The artificial neural network takes an input signal, transmits the signal through the network during which the nodes perform mathematical operations to alter the received signal in some way. Once transmitted all the way through the network a result can be extracted. These networks are used in basically all modern technology and has during the past decade completely changed the way technology is working in society.

The theory behind artificial neural networks is rather simple, but... (More)
Artificial Neural Networks are the computer equivalent to the human nervous system. Just like the nervous system is a network of neurons connected to other neurons by axons, the artificial neural network is a network of nodes connected to other nodes by links. The artificial neural network takes an input signal, transmits the signal through the network during which the nodes perform mathematical operations to alter the received signal in some way. Once transmitted all the way through the network a result can be extracted. These networks are used in basically all modern technology and has during the past decade completely changed the way technology is working in society.

The theory behind artificial neural networks is rather simple, but the problem lies in how these networks are created efficiently. It involves a lot of fiddling with the size of the network, the so called topology, since a network that is too big will be computationally inefficient while a network that is too small will not be able to solve the problem it has been tasked with. Furthermore the strength at which the links transmit the signal needs to be individually tuned to a very precise unknown value. This tuning is called training of the network and is one of the foundations to machine learning, and there are many methods used for this process.

One such training method is called Neuroevolution which uses Darwin's theory of evolution to essentially artificially simulate natural selection. It works by having a bunch of networks (a population), all with different link strengths and then mutating these strengths at random. The mutated networks are evaluated on how well the perform a given task, and based on this evaluation they are ranked from best to worst, where the worst ones are eliminated from the population while the best ones are allowed to reproduce and produce offspring to replace the eliminated ones. The reproduction works by combining information on the strength of the links from two parent networks, and thus producing an offspring that, ideally, will perform better. This process is the repeated until a solution is found. This method solves the tuning problem, but there is the second piece to the puzzle of finding a suitable network size. This is where Neuroevolution of Augmenting Topologies, or simply NEAT, comes into the picture.

NEAT evolves both the strength of the links and the actual network structure at the same time. The evolution of the network structure works in the same way as for the link strength, but instead of the link strength at random the actual networks structure is mutated. This happens by either adding a new node on an existing link, or adding a new link between two previously not linked nodes. NEAT is a very powerful algorithm as it removes the need for a human to specify the network structure, but it also has some trouble being able to evolve a network that is able to solve some more complex problem. NEAT also has a heuristic principle called speciation which introduce new parameters that a human needs to tune by hand, which of course is not ideal. Speciation splits the population into different groups in which each network resembles the other networks in that species. This is done to ensure that there is some diversity in the population so that evolution does not stagnate.

Enter the new algorithm Childhood habituation in Evolution of Augmenting Topologies, or CHEAT. CHEAT works on the same base principle as NEAT but it splits the training of the link strengths and the evolution of the structure into two separate phases. The phase for structural innovation can be seen as an analogy to two parents mixing their genes to produce an offspring, however when the offspring is born it cannot care for itself and needs its parents help to learn to survive. The training phase can be seen as the time where the parents protect their offspring and teach it necessary skills to survive on its own. Once trained it will go out and face the world on its own and if it has inherited good genes and been trained well, it will be able to find a mate and keep the cycle going.

The results of studying this algorithm has been bigger networks must be allowed to train for longer than smaller networks, which can be seen as an analogy to how bigger animals usually stay with their parents for longer while smaller animals stay shorter. Second, to solve more complex problems there is a need to structure how the mutations of the network occur. This is done by forcing the network to have a layered structure in which all nodes of that a layer have links to all the nodes of the previous layer and the following layer. With these modifications CHEAT solves the problems that NEAT has, as well as removes the speciation heuristic and the associated difficult to tune parameters. This opens up for exciting further research into the matter, where the ultimate goal would be to let the algorithm take control of all of the remaining parameters currently needing human input and tuning. (Less)
Popular Abstract (Swedish)
Artificiella Neuronnät är datorvärldens ekvivalens till det mänskliga nervsystemet. Precis som nervsystemet är ett nätverk av neuroner som är kopplade till andra neuroner med nerver så är det artificiella neuronnätet ett näverk av noder som är kopplade till andra noder med länkar. Det artificiella neuronnätet tar en inputsignal som skickas igenom nätverket och där noderna signalen stöter på på vägen modifierar den matematiskt innan den skickas vidare. När signalen nått hela vägen till slutet av nätverket så kan ett resultat extraheras. Dessa nätverk används i princip i all modern teknologi och har under det senaste decenniet totalt förändrat teknikens plats i samhället.

Teorin bakom artificiella neuronnät är relativt simpel, men... (More)
Artificiella Neuronnät är datorvärldens ekvivalens till det mänskliga nervsystemet. Precis som nervsystemet är ett nätverk av neuroner som är kopplade till andra neuroner med nerver så är det artificiella neuronnätet ett näverk av noder som är kopplade till andra noder med länkar. Det artificiella neuronnätet tar en inputsignal som skickas igenom nätverket och där noderna signalen stöter på på vägen modifierar den matematiskt innan den skickas vidare. När signalen nått hela vägen till slutet av nätverket så kan ett resultat extraheras. Dessa nätverk används i princip i all modern teknologi och har under det senaste decenniet totalt förändrat teknikens plats i samhället.

Teorin bakom artificiella neuronnät är relativt simpel, men problematiken ligger i hur dessa nätverk skapas på ett effektivt vis. Det involverar mycket pysslande med storleken av nätverket i sig, den så kallade topologin, då ett nätverk som är för stort är beräkningsmässigt ineffektivt, medan ett nätverk som är för litet inte kommer lyckas lösa det givna problemet. Dessutom, som om det inte vore nog så behöver styrkan på länkarna som skickar vidare signalen i nätverket individuellt ställas in till ett okänt optimalt värde. Denna process kallas för träning av nätverket och är ett av fundamenten för maskininlärning. Det finns många olika metoder för träning av ett nätverk.

En metod är Neuroevolution, som bygger på Darwins evolutionsteorier för att simulera naturligt urval. Det fungerar genom att ha en mängd olika nätverk (en population), alla med olika styrka på länkarna, och sen mutera denna styrka slumpvis. De muterade nätverken testas sen på ett givet problem och baserat på detta test rankas nätverken i populationen från bäst till sämst. De sämsta nätverken elimineras medan de bästa får lov att föröka sig och producera avkommor som ersätter de eliminerade nätverken. Förökningen sker genom att kombinera information om styrkan på länkarna mellan två föräldranätverk, och på så sätt skapa en avkomma som förhoppningsvis kommer prestera bättre. Denna process återupprepas till dess att en lösning på det givna problemet hittats. Detta löser problemet med att finjustera styrkan på länkarna, men det andra problemet om att hitta en optimal nätverksstruktur återstår. Det är här Neuroevolution of Augmenting Topologies, förkortat NEAT, kommer in i spelet.

NEAT använder neuroevolution för att både utveckla styrkan på länkarna och den faktiska strukturen av nätverket. Utvecklingen av strukturen på nätverket fungerar på samma sätt som för styrkan av länkarna, men istället för att styrkan på länkarna muteras så muteras nätverket i sig. Detta sker genom att antingen lägga till en ny nod på en existerande länk, eller en ny länk mellan två tidigare icke sammankopplade noder. NEAT är en väldigt kraftfull algoritm då den tar bort behovet för en människa att bestämma nätverksstrukturen, men har vissa problem när det kommer till att utveckla ett nätverk som kan lösa lite mer komplexa problem. NEAT introducerar också ett heuristiskt koncept vid namn artuppdelning (\textit{eng. speciation}) vilket introducerar nya svårbestämda parametrar som behöver justeras av en människa. Artuppdelning delar, precis som namnet antyder, upp populationen i olika arter där varje nätverk inom en art liknar alla andra nätverk i samma art. Detta görs för att forcera en mångfald av nätverk i populationen så att utvecklingen inte stagnerar.

Det är här den nya algoritmen Childhood Habituation in Evolution of Augmenting Topologies, eller förkortat CHEAT, gör entré. CHEAT använder samma grundpricniper som NEAT men delar träningen av länkstyrkan och utvecklingen av nätverksstrukturen till två separata faser. Fasen för utvecklingen av nätverket kan ses som en analogi till hur två föräldrar mixar genetiskt material för att skapa en avkomma, men denna avkomma klarar sig inte själv utan behöver sina föräldrars hjälp. Träningsfasen kan ses som en analogi till hur föräldrarna skyddar och uppfostrar avkomman så att den lär sig att klara sig själv. När den är uppfostrad blir den utslängd i världen och om den har fått en bra mix av gener och har tränats väl så kommer den hitta en partner och cykeln återupprepas.

Resultaten av att studera denna algoritm har varit att det är mycket viktigt för större nätverk att tränas längre än små, vilket kan ses som en analogi till hur stora djur oftast stannar med sina föräldrar under än längre period än små. För det andra så är det viktigt att styra nätverkens utveckling för att lösa komplexa problem. Detta görs genom att forcera nätverket till en lagerstruktur där noder i ett visst lager har länkar till alla noder i föregående samt efterföljande lager. Med dessa modifikationer lyckas CHEAT lösa de problem som uppstod för NEAT, samtidigt som CHEAT helt tar bort det heuristiska artuppdelningskonceptet, och de associerade svårbestämda parametrarna. Detta öppnar upp för intressant uppföljande forskning där det ultimata målet hade varit att låta algoritmen ta över kontrollen över alla parametrar som annars behöver hjälpande mänsklig hand. (Less)
Please use this url to cite or link to this publication:
author
Moberg, Anton LU
supervisor
organization
course
FYTM04 20201
year
type
H2 - Master's Degree (Two Years)
subject
keywords
Neuroevolution, genetic algorithm, machine learning, ML, CHEAT, Childhood Habituation in Evolution of Augmenting Topologies, optimization, artificial neural network, self evolving, model selection
language
English
id
9029997
date added to LUP
2020-10-07 16:17:00
date last changed
2020-10-07 16:17:00
@misc{9029997,
  abstract     = {{Neuroevolution is a field within machine learning that applies genetic algorithms to train artificial neural networks. Neuroevolution of Augmenting Topologies (NEAT) is a method that evolves both the topology of the network and trains the weights of the network at the same time, and has been found to successfully solve reinforcement learning problems efficiently and the XOR problem with a minimal topology. However, NEAT has not been shown to solve more complex labelling problems and has a vaguely motivated heuristic concept of speciation needed to keep a diverse population and protect new structural innovations from instant elimination. In this thesis a new algorithm was developed, the Childhood Habituation in Evolution of Augmenting Topologies (CHEAT) algorithm, which removes the need for the heuristic speciation concept and its associated hyper-parameters by splitting topology evolution and weight training into two distinct phases. CHEAT also allows for structured topology evolution by having the option of forcing fully connected layers. The algorithm was tested on the XOR problem and the spiral problem with two turns, with a result showing performances on par with NEAT for the XOR problem, and better results on the spiral problem where CHEAT is able to solve the problem while NEAT is not. It was found that without an early stopping criterion for gradient descent training, new structural innovations were quickly eliminated from the population before being optimally tuned, and thus the stopping criterion is vital to be able to remove the NEAT speciation heuristics. It was also found that restricting the algorithm to evolve in a structured manner by forcing fully connected layers was vital to solving any problems more complex than the XOR problem, likely due to the feature selection behaviour fully connected layers exhibit. The work done in this thesis opens further areas of research into evolving Artificial Neural Networks, where the most interesting leads lie in other weight training methods, different stopping criterion for gradient descent training, and finally letting the algorithm take control of evolution of its own hyper-parameters for automatic model construction.}},
  author       = {{Moberg, Anton}},
  language     = {{eng}},
  note         = {{Student Paper}},
  title        = {{Childhood Habituation in Evolution of Augmenting Topologies (CHEAT)}},
  year         = {{2020}},
}