Artificial Neural Net - Backpropagation (C++)

[BlindSide]

I wrote this a while back, I figured someone could use it to take over the world, do facial recognition, analyze heartbeats, game ai, whatever. Have fun, comments will be appreciated. (Yeah I know I forgot to constify some things, feel free to tweak that.)

Features:
- Simple backpropagation style neural network.
- Adjustable size hidden layers.
- Adjustable hidden node count.
- Adjustable size input/outputs.
- Input outputs should be normalized to 0-1.
- Binary file save/load. (Dimensions must match the current neural net though.)

Code: Select all

#ifndef ANN_INCLUDE_H
#define ANN_INCLUDE_H

#include <vector>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <string.h>

using namespace std;

const float learningRate = 0.05f;

class Ann
{
public:
	class Link;
	class BackLink;
	class INode;
	class ITrainer
	{
	public:
		virtual void train(std::vector<float>& inputs,
			std::vector<float>& outputs, Ann* ann) = 0;
	};

	Ann(size_t numberOfWorkLayers = 2, size_t numberOfWorkers = 8, size_t numberOfInputs = 3,
		size_t numberOfOutputs = 3);
	~Ann();

	void setTrainer(Ann::ITrainer* trainerIn)
	{
		trainer = trainerIn;
	}

	void backPropagate(size_t iterations);

	void randomizeInputs();

	void setInput(const std::vector<float>& input);

	std::vector<float> getOutput();

	std::vector<float> getInput();

	void saveNeuralMap(const char* filename);

	bool loadNeuralMap(const char* filename);
private:
	Ann::ITrainer* trainer;
	
	std::vector<Ann::INode*> inputLayer;
	std::vector<std::vector<Ann::INode*> > workLayers;
	std::vector<Ann::INode*> outputLayer;

	// Sizes
	size_t inputLayerSize;
	size_t workLayersSize;
	size_t workLayerSize;
	size_t outputLayerSize;

	// Used while training.
	std::vector<float> inputValues;
	std::vector<float> outputValues;
};

class Ann::Link
{
public:
	Ann::Link(Ann::INode* nodeLink) : pointer(nodeLink)
	{
		// Initialise weight to a random value between [-2.0, 2.0]
		weight = (rand()%400) * 0.01f - 2.0f;
	}

	float weight;
	Ann::INode* pointer;	
};

class Ann::BackLink
{
public:
	Ann::BackLink(Ann::INode* nodeLink, float* weightIn) 
		: pointer(nodeLink), weight(weightIn) {}

	float* weight;
	Ann::INode* pointer;	
};

class Ann::INode
{
public:
	virtual float getOutput() = 0;
	virtual void calculateDelta() {};
	virtual void updateFreeValues() {};

	std::vector<Ann::Link>& getLinks()
	{
		return links;
	}	

	float delta;
	float bias;
	std::vector<Ann::BackLink> backLinks;

protected:
	std::vector<Ann::Link> links;
};

class BasicNode : public Ann::INode
{
public:
	BasicNode(std::vector<Ann::INode*>& inputs)
	{
		bias = (rand()%100) * 0.01f;

		size_t inputsSize = inputs.size();
		links.reserve(inputsSize);

		for(size_t i = 0;i < inputsSize;++i)
		{
			Ann::Link currentLink(inputs[i]);
			links.push_back(currentLink);

			inputs[i]->backLinks.push_back(Ann::BackLink(this, &links[i].weight)); 
		}
	}

	virtual float getOutput()
	{
		float netValue = bias;

		// Summing function.
		size_t linksSize = links.size();
		for(size_t i = 0;i < linksSize;++i)
			netValue += links[i].pointer->getOutput() * links[i].weight;

		// Transfer function.
		netValue = 1.0f / (1.0f + exp(-netValue));

		return netValue;
	}

	virtual void calculateDelta()
	{
		float errorFactor = 0.0f;
		size_t backLinksSize = backLinks.size();
		for(size_t i = 0;i < backLinksSize;++i)
			errorFactor += (*backLinks[i].weight) * backLinks[i].pointer->delta;

		float currentOutput = getOutput();
		delta = currentOutput * (1.0f - currentOutput) * errorFactor;
	}

	virtual void updateFreeValues()
	{
		bias = bias + learningRate * delta;

		size_t currentLinksSize = links.size();
		for(size_t g = 0;g < currentLinksSize;++g)
			links[g].weight = links[g].weight + learningRate
				* links[g].pointer->getOutput() * delta;
	}
};

class InputNode : public Ann::INode
{
public:
	InputNode(float inputValue) : value(inputValue)	{}

	virtual float getOutput()
	{
		return value;
	}

	float value;
};

Ann::Ann(size_t numberOfWorkLayers, size_t numberOfWorkers, size_t numberOfInputs, size_t numberOfOutputs)
: trainer(0) 
{
	// Seed rand.
	srand(clock());

	for(size_t i = 0;i < numberOfInputs;++i)
		inputLayer.push_back(new InputNode(0));

	inputLayerSize = inputLayer.size();
	
	// Push back the input layer.
	workLayers.push_back(inputLayer);

	for(size_t g = 0;g < numberOfWorkLayers;++g)
	{
		std::vector<Ann::INode*> workLayer;

		for(size_t i = 0;i < numberOfWorkers;++i)
			workLayer.push_back(new BasicNode(workLayers[g]));

		workLayers.push_back(workLayer);
	}

	workLayerSize = numberOfWorkers;
	workLayersSize = workLayers.size();
	
	for(size_t i = 0;i < numberOfOutputs;++i)
		outputLayer.push_back(new BasicNode(workLayers[workLayersSize - 1]));

	outputLayerSize = outputLayer.size();
}

void Ann::randomizeInputs()
{
	for(size_t i = 0;i < inputLayerSize;++i)
		((InputNode*)inputLayer[i])->value = inputValues[i] = (rand()%100) * 0.01f;
}

void Ann::backPropagate(size_t iterations)
{
	for(size_t l = 0;l < iterations;++l)
	{
		// Reset output and input values.
		inputValues.resize(inputLayerSize);
		outputValues.resize(outputLayerSize);

		// Training is performed here.
		if(trainer)	
			trainer->train(inputValues, outputValues, this);

		// Update input values.
		for(size_t i = 0;i < inputLayerSize;++i)
			((InputNode*)inputLayer[i])->value = inputValues[i];

		// Here we backpropagate and calculate the error values:
		for(size_t i = 0;i < outputLayerSize;++i)
		{
			float outputValue = outputLayer[i]->getOutput();
			float outputEFactor = outputValues[i] - outputValue;
			outputLayer[i]->delta = outputValue * (1.0f - outputValue) * outputEFactor;
		}

		// We only go down to level 1 as we don't need to calculate
		// the input node's deltas/weights/biases.
		for(size_t i = workLayersSize - 1;i >= 1;--i)
		{
			for(size_t g = 0;g < workLayerSize;++g)
			{
				workLayers[i][g]->calculateDelta();
				workLayers[i][g]->updateFreeValues();
			}
		}

		for(size_t i = 0;i < outputLayerSize;++i)
			outputLayer[i]->updateFreeValues();
	}
}

void Ann::setInput(const std::vector<float>& input)
{
	size_t inputSize = input.size();

	// Update input values.
	for(size_t i = 0;i < inputLayerSize && i < inputSize;++i)
		((InputNode*)inputLayer[i])->value = input[i];
}

std::vector<float> Ann::getOutput()
{
	std::vector<float> output;

	for(size_t i = 0;i < outputLayerSize;++i)
		output.push_back(outputLayer[i]->getOutput());

	return output;
}

std::vector<float> Ann::getInput()
{
	std::vector<float> input;

	for(size_t i = 0;i < inputLayerSize;++i)
		input.push_back(inputLayer[i]->getOutput());

	return input;
}

Ann::~Ann()
{
	for(size_t i = 0;i < inputLayerSize;++i)
		delete inputLayer[i];
	
	for(size_t g = 1;g < workLayersSize;++g)
		for(size_t i = 0;i < workLayerSize;++i)
			delete (workLayers[g])[i];

	for(size_t i = 0;i < outputLayerSize;++i)
		delete outputLayer[i];
}

void Ann::saveNeuralMap(const char* filename)
{
	FILE* file = fopen(filename, "wb");

	fwrite(&workLayersSize, sizeof(size_t), 1, file);
	fwrite(&workLayerSize, sizeof(size_t), 1, file);
	fwrite(&inputLayerSize, sizeof(size_t), 1, file);
	fwrite(&outputLayerSize, sizeof(size_t), 1, file);

	for(size_t g = 1;g < workLayersSize;++g)
	{
		for(size_t i = 0;i < workLayerSize;++i)
		{
			fwrite(&workLayers[g][i]->bias, sizeof(float), 1, file);

			size_t linksSize = workLayers[g][i]->getLinks().size();
			for(size_t j = 0;j < linksSize;++j)
				fwrite(&workLayers[g][i]->getLinks()[j].weight, sizeof(float), 1, file);
		}
	}
	
	for(size_t i = 0;i < outputLayerSize;++i)
	{
		fwrite(&outputLayer[i]->bias, sizeof(float), 1, file);

		size_t linksSize = outputLayer[i]->getLinks().size();
		for(size_t j = 0;j < linksSize;++j)
			fwrite(&outputLayer[i]->getLinks()[j].weight, sizeof(float), 1, file);
	}
	
	fclose(file);
}

bool Ann::loadNeuralMap(const char* filename)
{
	FILE* file = fopen(filename, "rb");

	size_t fWorkLayersSize = 0;
	size_t fWorkLayerSize = 0;
	size_t fInputLayersSize = 0;
	size_t fOutputLayersSize = 0;

	if(!file)
	{
		printf("\nAnn: Error loading Neural Map, IO error.");
		return false;
	}

	fread(&fWorkLayersSize, sizeof(size_t), 1, file);
	fread(&fWorkLayerSize, sizeof(size_t), 1, file);
	fread(&fInputLayersSize, sizeof(size_t), 1, file);
	fread(&fOutputLayersSize, sizeof(size_t), 1, file);

	if(	fWorkLayersSize != workLayersSize ||
		fWorkLayerSize != workLayerSize ||
		fInputLayersSize != inputLayerSize ||
		fOutputLayersSize != outputLayerSize)
	{
		printf("\nAnn: Error loading Neural Map, dimensions do not match.");
		fclose(file);
		return false;
	}

	for(size_t g = 1;g < workLayersSize;++g)
	{
		for(size_t i = 0;i < workLayerSize;++i)
		{
			fread(&workLayers[g][i]->bias, sizeof(float), 1, file);

			size_t linksSize = workLayers[g][i]->getLinks().size();
			for(size_t j = 0;j < linksSize;++j)
				fread(&workLayers[g][i]->getLinks()[j].weight, sizeof(float), 1, file);
		}
	}
	
	for(size_t i = 0;i < outputLayerSize;++i)
	{
		fread(&outputLayer[i]->bias, sizeof(float), 1, file);

		size_t linksSize = outputLayer[i]->getLinks().size();
		for(size_t j = 0;j < linksSize;++j)
			fread(&outputLayer[i]->getLinks()[j].weight, sizeof(float), 1, file);
	}
	
	fclose(file);

	return true;
}

#endif

// Copyright Ahmed Hilali 2008 (C)

I'll post some examples of usage later when I have time.

[Nadro]

Looks very interesting, I wait for example, good job BlindSide:)

[fmx]

I remember I made a little ANN demo a long time ago too; its really cool how such a simple mechanism of adjusting outputs from inputs per node can lead to such insanely complex results and behaviour.

I'll have a go at using your implementation in a small test demo, see what it can do, how it could be improved, etc, etc

BTW:

// Copyright Ahmed Hilali 2008 (C)

licence?

[dlangdev]

Found the Wiki: http://en.wikipedia.org/wiki/Artificial_neural_network

Though I really am not an expert in that field. So I'll have to buckle-down again and study it.

[sudi]

ok this is really cool. but since i never did something about neural nets i don't really know how to use this.....but since u made this i guess i will go and investigate in ANN.
thanks really great snippet

[Acki]

Yes, looks realy interesting !!!

I'll post some examples of usage later when I have time.

So hurry up, I can't wait !!!

[sudi]

ok i don't get how ur system evolves.
this is just one neural net but u need several using a geneticAlg to evolve ur networks and make them work on ur problem even better.

[asphodeli]

any references we can read up on?

[sudi]

I found this Link and already wrote my own ANN. But now I#m strugling on the geneticAlgo with the fitness count for learning. i guess thats always tied to a certain problem.

[Dorth]

Also, one of the first good example could be a simple board game. Those are a fun field for neural network ^^

[BlindSide]

Sorry guys I didn't fully explain myself when I posted this up. Lets have a look at how to train it.

I'm not sure if this is the best way to do it, but it was the easiest that worked for me. I really wanted to try experimenting with genetic algs and populations, gene splicing etc, but I didn't have time.

Ok, for now don't worry about workLayersSize, numberOfWorkers, the default is an ok number. (Note I refer to hidden layers as work layers.).

Basically, when you create it all the weights will be randomized. The weights are the key to your "artificial brain", they govern how it reacts to different inputs. (So are the biases, they also play a part.). Basically the equation connecting everything is val * weight + bias.

Anyway, this means you get a random brain everytime you create a neural net, it could be really smart, or really dumb for that particular task. This is where Sudi's method can come in, you can create a whole lot of random ones, kill off the ones that suck, make some more, mix the ones that are good together a bit, etc, etc for a few hundred/thousand runs and you get a nice neural net, basically just utilizing Darwin's theory of evolution.

Backpropagation however, is how I've been using it, basically this is much simpler. Let me go through the specific usage details:

- Create neural net.
- Derive from the class Ann::ITrainer, and override the train method. Set it using the "setTrainer()" method.
- When you call "backpropagate", Ann will pass the current input and output values to your train method. Here you have to basically set the inputs, and set what the outputs should be for those inputs. So lets start with something simple:

Code: Select all

class XORTrainer : public Ann::ITrainer
{
	void Ann::ITrainer::train(std::vector<float> &inputs, std::vector<float> &outputs, Ann* ann)
	{
		ann->randomizeInputs();

		if(inputs[0] > 0.5f && inputs[1] < 0.5f
		|| inputs[0] < 0.5f && inputs[1] > 0.5f)
		{
			outputs[0] = 1.0f;
		}
		else
		{
			outputs[0] = 0.0f;
		}
	}
};

This is a very simple XOR trainer. It tells our neural net to output a value of 0.0f when the values match, and 1.0f when the values are different. Note we are using floats normalised to 0-1 here so we just test if it's < or > to 0.5f. Now if you run this train method 10000 times, your neural net will learn to do just that. This is of course a very simple example, and there are much more sophisticated ways of using with, I just wanted to show you something simple. Please note that the number of outputs don't have to be the same as the inputs, a singe output value can depend on a number of inputs as shown here (Or vice versa).

It is important to note here that for convenience I just randomize the inputs, and then test against an if statement for training, there are much more sophisticated ways to do this, I will explain them further on below.

- Now to use the neural net we just pass it in a vector of floating point values using setInput(), and retrieve the output using getOutput() hopefully it is what we are looking for.

- Training can be CPU intensive because alot of outputs, weights, biases, errors are evaluated/modified many times for one iteration. But just retrieving the values after successful training is ok, it only requires to evaluate one output for each output node.

Now instead of just having a silly if statement and randomising the inputs, to train a robot car not to avoid obstacles, what I did is make it observe human driving. I have 3 inputs, distance to nearest obstacle on the near left, front and right, and 2 outputs, speed normalised to 0-1 (Below 0.5 goes backwards.), and turning velocity, also normalised to 0-1 (Below 0.5 turns more and more left, else it turns increasingly to the right). Now basically I just drive around with this using the keyboard, and pass the current inputs which are the distances etc, and the current outputs which are my velocity, turning rate, etc every frame, and in theory it should learn to drive a little like me. Now when I let it drive I just pass it the inputs and set the velocity, turning rate, etc based on it's outputs. Of course in theory this *should* work but it hasn't done very well for me, I mean sometimes I can teach it to drive ok, but it always turns too slow or something, thats where genetic algorithms, and/or a physics environment would be interesting, trialing them on who gets closest to some kind of goal in a maze, and base their fitness to avoid obstacles on the distance to the goal, etc.

Please note the very important const value "learningRate", it is set at 0.05f, which is probably a little low for the simple example, but for more complicated things it needs careful adjustment. Too high a learning rate can make it learn bad things very quickly (And quickly unlearn good things), and too low can make it take forever to learn anything, although it is safer and more precise. Careful tweaking of this is very necessary, try playing around with it, it can be a time consuming process and is specific to each task. Try values between 0.01f - 0.2f for most things.

The "iteration" param for backpropagation is good when you are setting the inputs and outputs inside the train function itself, but in other cases you should just do one iteration, and call the backpropagation method many times.

Ok... I talked very very much there. I might post some more interesting usage examples in the Faq forums, I am thinking of making a funny topic like "A 101 uses for a neural network". Yes it will be useless in everything it does but it can still do them using the same piece of code.

Cheers

[BlindSide]

licence?

No license I guess, as long as the original creator is not misrepresented ala zlib. Oh, and I can't be held liable if it develops self awareness and tries to destroy mankind.

ok i don't get how ur system evolves.
this is just one neural net but u need several using a geneticAlg to evolve ur networks and make them work on ur problem even better.

Theres a googolplex of nn training methods out there, this particular one uses the back propagation method. Outputs are calculated, and then they are compared to something similar to the desired output, errors are calculated and used to adjust the weights/biases for more desirable results. It works by forward-propagating the output values, and then back-propagating the error values.

I learnt alot from this CodeProject article: http://www.codeproject.com/KB/recipes/brainnet.aspx

[Dorth]

Ok, nice, but please, back propagation. Thanks
That irks me about as much as "rouge" instead of "rogue"

[BlindSide]

Haha yeah I started correcting my spelling mistakes towards the end. *Fixed*

[Frank Dodd]

Every programmer loves a bit of Neural Networking I think probably because we are all Mad Boffins at heart.

I've played about with genetic NN from the excellent ai-junkie site, this looks like a nice simple example of a back propagation NN which I believe should allow a single network solution instead of having to store multiple neworks, solve multiple solutions and cull poor performers? Actually defining what the solution is to the network might be tricky in the context of a machine game player though.

Although I think state machines are the best way to go for AI its always tempting to put a low consumption machine brain overlord in the background to plot against you. Thanks for the sample code BlindSide.