Return to site

Last Man Standing Neural Network

By Thimo Visser, Coderbunker intern

What is a neural network?
You've probably heard the term machine learning: machine learning is the ability for a computer to learn a task without the task being explicitly programmed.
A neural network is one of the options for implementing machine learning. It calculates the probabilities of all possible actions and chooses which action is the best for the current given situation.
The way a neural network works is loosely based on the way your brain works. A neural network consists of a set of input neurons (your sight, taste,temperature, etc) called the input layer. A set of hidden neurons (your brain) called the hidden layer. And a set of output neurons (for example your muscles) called the output layer.These are all interlinked in a topological order (ordered in a way where all the dependencies from others are previously met).

Image source: www.texample.net

When one of your input neurons senses something it sends an electric pulse to the next neurons in line, the neuron next in line gets this input from multiple neurons, combines them and modifies them and again sends a pulse to the next in line. This continues until the output neurons knows whether it should act or not.

What is the last man standing approach?
To teach the neural network the correct weights it needs to "learn". There are two popular ways to learn a network, backpropagation and genetic algorithms.

My last man standing is another approach on how a neural network can learn. The approach simplified is: Take the best of the best, kill all the other lesser species and keep evolving to reach the perfect species as soon as possible.

Why this project?
I've been interested in artificial intelligence for a while now and neural networks really caught my attention. The network has been making the news on a regular basis with projects such as alphaGo beating Lee Sedol in Go and Microsoft Tay chat bot.
I've had the last man standing idea in my head for a while and I feel that it might be a new invention that might lead to the improvement of the neural network.

Image source: http://www.tomshardware.com/

What makes it special?
The biggest problem with neural networks at this moment in time is that they take a lot of number crunching power to learn how to solve complex problems. The last man standing approach is a way to shorten the learning process which could be a big step in the machine learning technologies and thus enabling neural networks to tackle more complex problems.
Whether this concept works is still to be determined, so this project is a proof of concept.

What is the concept?
Most of the neural networks in use at the moment make use of either back-propagation or a genetic algorithm.
Back-propagation is the act of back-tracking all the neurons and adjusting them according whether the result was good or bad.
A genetic algorithm copies the way nature evolves, removing the less fit species and adjust the fitter species to their environment and keep evolving by cross-breeding and genetic mutation.
The last man standing approach looks the most like a genetic algorithm. What we do is, take one generation containing multiple species. Check which of these species performs the task the best by the use of a fitness function. Afterwards take only the best species, kill of the rest, and copy the best species to repopulate the next generation. We adjust certain genes of all the species but leave one intact to make sure evolutionary progress is never lost. This process keeps going until the best solution is reached and the problem is solved.
The one known downside to this approach is that the species that get killed off could have traits that would have been useful to later generations. These genes are wasted with the expectation that the fittest species should grow these traits as well. So we lose variety in hopes of evolving one fitter species more quickly.

How do I know it works?
The first goal is to get the neural network to beat the simple game of Tic Tac Toe. I've chosen Tic Tac Toe as the game has a clear peak: if played correctly the game will always end in a tie.
So when the network reaches a 100% tie rate I know it has evolved into the perfect species for this problem.
My implementation
As the main goal of this project is a proof of concept and not speed, I decided on Java as the programming language as that is the language I'm the most comfortable with. I wanted to be able to visualize and store all the information the network produces so I elected to store all the information in a Mongo document database.
The combination of the two allowed for me to focus on the actual implementation.
After a while I removed a part of the Mongo database to improve the speed of the network; the reason why is explained below

Problems encountered
After implementing the neural network for the first time it didn't learn. After some investigation I figured out that the root of the problem was that I was changing the neurons too much. Because I did this it was ignoring things it learned in the past and the network just did a random walk into the solution space. The way I fixed this is by instead of changing every weight of the network I only change a predetermined x% of the weights. This allows for good weights to remain and not throw away information it learned in the past.
By writing a converter I get graph files which we can use in Graphwiz to visualize a species.
I decided to remove a big part of the Mongo database to improve efficiency and reduced the processing time by at least 10000 times by removing I/O operations.
With this new improvement I was able to test the network on a bigger scale. This is how I found out the result was a false positive. With this information I fixed more bugs in the system and got the network to work.

Results

With the fitness function that I wrote the perfect species requires the fitness of 0.9; this is where the network reaches a 100% tie rate. After running the network a couple of times I get result like these:

X-axis represents generations, Y-axis is fitness

As you can see the network evolves and reaches the 'perfect' species. In the examples above, it took a variable number 4 to 45 generations to reach this perfect species. The amount of time it takes to reach this species varies highly on whether the mutations are good or bad.
With this I've proven that the last man standing approach does work. Whether it is a good or viable option is still to be determined.

Can I see the source code?
Yes you can! The project is open source and can be found here: https://github.com/thimovss/lastmanstanding
The visualization tool I made can also be found here: https://github.com/thimovss/networkVisualization

Next goals/ideas
Implement the network on Blackjack and/or four-in-a-row to see if it works with more complex tasks.
Implement cross-over between best 2 species instead of taking just the best species to improve performance.
Port the concept to a better programming language to improve time investment to train the network.
Write a standard genetic algorithm or back-propagation to compare the results with.

What have we learned?
The use of a Mongo database for every I/O operation is a big bottleneck.
The last man standing concept might work, whether it works needs further testing.
Whether the network evolves is still based on luck, it can evolve to the solution in 2 generations but it might also take 30 generations.
In order for this approach to work we need an accurate fitness function, if not the network might not learn.

Want to learn more or discuss?

Join Coderbunker as a member or come to our next Coderbunker Machine Learning Meetup

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly