AI Tutorials

2011-09-27 06:15:41 by Homer in AI Tutorials
Our second machine learning algorithm is far more interesting than the first one (backpropagation of error terms derived from training sets - see previous posts).

Remember that neural networks are an attempt to simulate the processes that occur in a biological brain, and that we've just created a population of nnet-powered 'critters' - artificial lifeforms? We'll be extending on this concept of 'living machines' by pretending that the 'brain weights' inside the neural network actually represent 'Chromosomes' - the building blocks of life.
We're going to take the analogy of living biological systems to the extreme by simulating biological evolution itself (!) This post will describe the implementation of  an 'Applied Genetic Algorithm'. It all begins by assigning each of our critters a 'fitness score' which we will use to determine how 'successful' they are, both individually, and as a group / population.

Assume that we have given our critters random 'brain weights' and positions in worldspace, and have also created a randomly-positioned list of 'food items'.
We'll basically let our critters run wild and free for some amount of Time, known as an 'Epoch', which represents one generation of life.
At the beginning of each Epoch, we will set all the Fitness scores to zero, then let them go nuts.
Some of them, by pure chance, will accidentally run into food items - when they do so, we'll increment their fitness score. Others will wander about aimlessly, or worse, sit in one place spinning around, starving to death lol.
At the end of the Epoch, we will apply the genetic algorithm, which has several steps.
The aim is to produce a new population of neural nets which converges toward more successful behavior in the next generation.

ELITISM (aka Natural Selection):
Step One is to copy the existing nnet weight arrays into one big flat array (ie our 'gene pool'), then choose a small number of the 'Fittest' members of the population, and create a few extra copies of those, so we are 'poisoning the gene pool' to increase the likelihood of 'successful genetics' being selected in the next step.
The rich get richer, and the poor get poorer - success breeds success.

CROSSOVER:
Step Two involves selecting 'pseudorandom' pairs of nnets from the gene pool, and 'crossing' them - for each 'mum and dad', we will choose a random point midway through their nnet weights, and cut the weight array in two, rearranging the weights from the 'parents' to create two new 'children' (who will replace their parents). The selection of parents is not purely random, there is a heuristic which considers the Fitness of the parents, and is sometimes called 'Chromosome Roulette'. This process continues until the number of new Child nnets matches the number of critters in our population.

GENETIC MUTATION:
The 'new child critters' will have their 'brain weights' slightly perturbed (small random fudge factor), regardless of how successful their parents were. This ensures that the population does not rapidly converge on the SAME set of neural weights and will always have the opportunity to derive new, unpredictable yet successful behaviors that differ from the crowd - this is known as 'Emergent Behavior'.

Having finished screwing around with the nnet weights, we are ready to begin another Epoch.
That is absolutely all there is to it! Over a series of generations, our population of critters will get better at running over food - EVEN THOUGH WE NEVER TOLD THEM TO - the evolutionary system is rewarding critters who do that - we have a reward mechanism!
They will actually begin to AIM for the food, appearing to intelligently CHOOSE to do so.
In fact if you watch the average fitness score of the population over many generations you can see that it clearly improves, and rarely goes backwards - these guys are getting smarter at doing their job, and they don't know what their job is, there is no code that tells them that 'FOOD IS GOOD', they have figured it out all on their own!

In fact we can go a lot further with this, why not make the food items a population (of prey) so that our critters (predators) have to chase them - and the prey have to learn to evade capture .. add a couple more neural inputs and you'll see your predators evolve PACK HUNTING behavior!
ZOMFG

Hey, why stop at predator/prey behaviors? What about driving NPC's directly (little mages shooting fireballs?) or using the nnet outputs to drive the FSM (or alter the BehaviorTree logic) of a conventional game AI system? Hehe !!!

I sincerely hope this post helps someone understand applied genetic algorithms better.
For anyone who is interested, I can happily provide code for neural networks in asm, ObjAsm,  and C++ formats (apon request).

Have a nice day

2011-09-17 20:38:06 by Homer in AI Tutorials

Today we'll be learning how to hook up a neural network to solve an arbitrary problem.
This is the point where most people get stuck with neural networks - they have struggled to understand and implement them, and now they don't know how to APPLY them - because none of the whitepapers on the subject tell them how!

We have created a population of 'critters' who each have a small neural network.
Now we need to know what the neural network looks like in terms of its topology... so let's dive in headfirst, by talking about what kind of inputs we'll need. In order to keep things relatively simple, we will be implementing our creature simulation in 2D.

Our neural network's inputs are used to inform the critter about its environment, so we'll begin by assigning the first two inputs of the network, we'll be feeding in the WORLD TRANSLATION, or the position in worldspace, of this critter.

Input 0 = Position.x
Input 1 = Position.y

Good start.. need more inputs! The next two inputs will be for the Direction from this critter to the closest food item (or enemy, or whatever).

Input 2 = vFoodDirection.x
Input 3 = vFoodDirection.y

Although simple, this is enough information for our first attempt at an artificial lifeform.
So, our network will have just 4 inputs. Now we'll discuss the outputs.

We want our creature to react to its world, so we'll hook up outputs to two 'motors' which we will use to make the creature turn and move (imagine the tracks of a military tank, although we could be applying this to a bunny rabbit or a turtle or anything we want).

Output 0 = fLeftMotor
Output 1 = fRightMotor

As mentioned, outputs are always Normal floats (0.0 thru 1.0), so we'll have to come up with some simple function that converts these outputs into rotational and translational motion... not too difficult.

Our network will have just two outputs, and four inputs.
We will add to this, several Hidden Layers of neurons (at least two), which must have at least four neurons, and preferable, a little more.
  H H
I H H
I H H O
I H H O
I H H
  H H

We can now construct our neural network per critter and initialize its weights to randomness.
In the next post, I'll be talking about Genetic Algorithms and Applied Evolutionary Theory, and how we implement a neural net Training mechanism based on those.

2011-09-16 10:00:13 by Homer in AI Tutorials
We're ready to learn about our second training technique, which is based apon the Game Of Life / Genetic Algorithms.

We will implement a 'population of critters' who each contain a small neural network, and learn from their environment!

Further, we will implement a Training mechanism which is based apon Biological Evolution !!!

This kind of training can evolve truly emergent behaviors, which are unpredictable and yet successful. Overtraining will (again) lead to conformist behavior, where all the critters have similar brain weights / behaviors, however, we have some new mechanisms at our disposal to ensure that they cannot and will not conform utterly, and can yet evolve further new behaviors !!

So, we begin with the premise that we have some kind of array of neural networks, or, we have an array of 'critters' that each contain a small network. Let's create one, and fill it's brain weights with randomness. In order to do that, we will need to know what our neural network topology will look like, ie, how many inputs, outputs, how many layers, how many in each hidden layer... We need to talk about our requirements, and so the next post will discuss our requirements, and we will in fact be learning how to hook up neural networks to solve arbitrary problems !!!

2011-09-13 03:43:38 by Homer in AI Tutorials

Now we're able to apply inputs and generate outputs, it's time to talk about how to TRAIN our neural network, ie, how the 'machine learning' mechanism works.
I'll be discussing two different kinds of learning mechanism, but they both have the same goal - to 'improve' the network's weights such that the outputs more closely approximate our notion of "ideal" outputs... that needs a little explaining.

We know what we are using the neural network for - we can describe the problem space elegantly, but all the neural network ever knows about is the inputs that we show it.
Since we, the God-like creators of this brain-like thing, know so much about the problem we are trying to solve, we can "know" what the outputs should look like for any given set of inputs.

Our first learning mechanism is called "Back-Propagation" (of error terms).
We will 'run' our network as usual (show it some inputs, and produce some outputs).
Now we'll compare the outputs to our 'Desired Outputs' based on our expert knowledge of the problem space (ie, we'll determine what the outputs SHOULD be, and then determine the difference). We will now have an error value for each output, and we can calculate the mean error by summing them etc... usually referred to as Mean Square Error (MSE), the total error term for the entire network. We'll come back to the MSE.

For each output, we have an error term, and further, we know this error was produced by all the neurons in the next layer, whose outputs were connected as inputs of this neuron... we will assume that they all contributed to the error term, and we can calculate their contribution by simply applying their respective Weights to the error term.
So we are able to calculate the amount of error that each input contributed to the error term.
Please note that these error terms are SIGNED !!
These are the error terms for the next layer of neurons Further, now we know the contributing error term of each input neuron, we can determine how much and in which direction the weight needs to be adjusted to make the error term smaller (simple substitution).
Now we can adjust those weights, so next time the network runs, the error terms should be smaller, and the overall MSE smaller as well.

We can now repeat this process for each subsequent layer, moving in 'waves' across the network, from the outputs, back to the inputs, kinda like the FF algo (previous post), but in reverse.

We have now executed one 'training iteration', and can now check whether the MSE is below a certain threshold. If the overall error is too big, we will continue training, and if not, we will consider our network to be 'smart enough'.

Continued training involves showing the network more inputs and expected outputs, whether they are from a big fat database or calculated at runtime depends on what you're using the network for.

We should now be able to implement a system which will appear to 'get smarter' (more successful) all by itself, provided we have the ability to determine whether the outputs are 'good' or 'bad'.

We can think of this kind of training regime as being 'negative reinforcement', it's kind of like we are spanking our naughty network for misbehaving, while ignoring good behavior.
This will result in a network whose behavior is 'conformist' - rank and file soldiers, highly trained yet unable to think on their own.

With the right kind of training and environment, neural nets are capable of 'emergent behavior' which basically means unexpected (but successful) behaviors, which when applied to game AI, result in far more interesting and less predictable outcomes... in other words, it's more fun, and they seem to take on a life of their own, with their own idiosyncrasies... fascinating.

In the next post we'll tackle our second machine learning mechanism.
We will learn how to apply Genetic Algorithms to evolve a population of neural network-powered AI critters - without using any backpropagation. This can be thought of as 'positive reinforcement', whereby we 'reward' and favor good behavior, and 'neglect' bad behavior.

2011-09-11 09:03:51 by Homer in AI Tutorials
So here is the algorithm for 'feed forward', which is all we need to 'run' our network, once it has some 'basic training' ... If we look at the neural network from the outside as a kind of magical black box, then the FF algorithm applies our inputs, and produces some outputs - that is its function.

OK, so I said the inputs are just floating point values - they can actually be ANY floating point values, from - to + INFINITY !! However, we can speed up the network's learning rate by choosing a floating point range that better describes our actual 'keyspace' - for example, if we are using 3 inputs to describe the ai's position in worldspace then our input keyspace is the size of our world - the world bounds. This range should be used when we INITIALLY set the entire neural network weights to randoms.

Outputs will always be Signed, Normalized float, ie, between 0.0 and 1.0, which means we can directly apply our outputs to things like direction vectors, and scale them for speed and so on.
This should smell handy to anyone who actually wants to make games.

Before I explain the FF algo further, I think we should pick a convention for the purposes of discussion. I am going to place in your mind an image of our network, with the inputs on the left hand side, and the outputs on the right hand side.

The FF algorithm works in 'waves' - the input layer of neurons is kinda dumb, each neuron will accept its input weight (from the outside world, our app) on good faith. We will move on.
The first of the 'hidden' neuron layers.

For each neuron in this layer, we will do the following:
- For each OUTPUT in the layer on our left, multiply it by its input weight, and sum it.
- Pass the Sum through the Sigmoid function, which squashes the result into a normal float, and this float is the output value for the THIS neuron, and will be one of many inputs to each neuron in the NEXT layer.

Repeat this process for each hidden layer.

The output layer neurons are a bit stupid, like the input layer neurons they will accept the output they are handed on good faith.

We are now able to present a set of input values to our network, and see the outputs change to suit - even with random brains, we should see a consistant and repeatable one to one mapping.

This brings me to an important point.
We can consider the neural network as a glorified way of mapping a set of arbitrary inputs, to a set of arbitrary outputs - and even with random brains, we should be able to prove that.
If you've done everything right so far, anyway!

Now if you try writing pseudocode for this, you will have something like this:

Code: [Select]


For each Layer L (except the input layer):
 For each Neuron in this Layer N:
  For each Neuron in the previous Layer O:
   Weight the output O using weight [L][N]
   Sum the weighted values
   Squash em with Sigmoid
   Remember this output

 If you check that out you'll notice you never need to talk about object instance or whatever - your neurons can be completely theoretical, existing only as a set of weights (for its inputs), and a singular output. So your neural net becomes an array of weight arrays.

I started screwing around with computers when I was nine, the same year I was first arrested for breaking into the local high school to play with the musical instruments.

Since then I have learned to program robots the size of houses with up to seven independent axes, as well as design and build the robot itself.

These days I am back at Uni, getting myself qualified in game programming as a formality.

Do you like zombies?

 Messages: 4617
 Topics in blog: 180

    

 Daily Zombie
 AI Tutorials
 Random Code that I think is really cool and deserves a special mention which is a really long name for a blog, would you not agree?

24017