Dynamic Notions

A Profitable Strategy Abandoned

2009-07-11T14:43:00.002+01:00

As NNATS continues to evolve, it is not making money that is the problem; it is being able to make lots of money.

The biggest problem I have now is how to scale up. My bet sizes have increased significantly, however, the number of days and number of markets on which I trade has reduced. For some reason, Saturday and Sunday punters seem to suit NNATS best. On these days, there is a constant stream of money coming into the markets in a nice predictable way. On the contrary, NNATS especially hates Mondays, which is thin and unpredictable.

I have experimented with a number of trading strategies, but for now have settled on pure scalping.

A couple of months ago, however, I experimented with a strategy, which I named “Aggressive NNATS”. The plan was simple; back any selection whose lay price was at least three times the back price. NNATS would always try to place a back bet at the front of the queue, so for instance if the current lay price was 1000, it would place a back bet at 990. You would be surprised how many other bots out there appear to be running similar strategies. Together, NNATS and the other bot would play a game of chicken, and quickly chase the price down to a level where one of them would give up.

I did not really expect to be matched at such outrageous odds but, every now and then, it would happen. At that point, NNATS would lay the selection a pip ahead of the current back price and net a healthy profit. Of course, getting the lay matched could also sometimes be a problem, but NNATS would keep moving it out until somebody bit.

The following three screen shots show some particularly memorable examples from my P&L.

Why would I give this up? The answer is scale. This strategy is great if you want to make a fifty or a hundred pounds a week, but I am now aiming for a hundred pounds a day. The outrageous profits from “Aggressive NNATS” do not happen often enough to be a viable proposition.

Still if anybody wants to make a few quid a week, this is an easy way to do it..!

John

NNATS - It's No Fluke!

2009-06-03T06:06:00.002+01:00

I couldn't sleep, so thought I would make good use of the time by catching up with replies to blog comments - sorry it's taken so long!

Whilst I'm here, another quick update on NNATS. I've continued to increase the bet size and continue to make money. In the last week, I'm £78.66 up, which is representative of recent history.

I've given a copy of NNATS to a friend, so it will be interesting to see whether his bot competes with my bot or, more hopefully, they reinforce each other's trades...

John

Linear Regression in C#

2009-05-16T13:05:00.006+01:00

When looking at time series data, such as a stream of prices, it can often be useful to establish a general trend and represent this with a single number. This can be achieved using a linear regression calculation.

Take this series of prices:
4.8, 4.8, 4.5, 3.9, 4.4, 3.6, 3.6, 2.9, 3.5, 3.0, 2.5, 2.2, 2.6, 2.1, 2.2

If you plot on an Excel graph and add a linear trend line, you should get something like this:

We can do the same thing in code:

using System;

class Regression

{

static void Main(string[] args)

{

double[] values = { 4.8, 4.8, 4.5, 3.9, 4.4, 3.6, 3.6, 2.9, 3.5, 3.0, 2.5, 2.2, 2.6, 2.1, 2.2 };

double xAvg = 0;

double yAvg = 0;

for (int x = 0; x < values.Length; x++)

{

xAvg += x;

yAvg += values[x];

}

xAvg = xAvg / values.Length;

yAvg = yAvg / values.Length;

double v1 = 0;

double v2 = 0;

for (int x = 0; x < values.Length; x++)

{

v1 += (x - xAvg) * (values[x] - yAvg);

v2 += Math.Pow(x - xAvg, 2);

}

double a = v1 / v2;

double b = yAvg - a * xAvg;

Console.WriteLine("y = ax + b");

Console.WriteLine("a = {0}, the slope of the trend line.", Math.Round(a, 2));

Console.WriteLine("b = {0}, the intercept of the trend line.", Math.Round(b, 2));

Console.ReadLine();

}

Now you have the slope of the trend line, this can be used as an input for neural networks analysing time series data. I use something similar in NNATS…

For a complete explanation of linear regression see Wikipedia.

John

Weight of Money

2009-04-30T17:56:00.007+01:00

Many of you have asked what sort of inputs I use for NNATS and how these can be used either independently or to feed a neural network for further analysis. In the next few posts, I will share some of these with you.

To get the ball rolling, let us start with the backbone of any Betfair trading bot, the “weight of money” indicator. This indicator is a very good place to start, as intuitively it is easy to understand, it is easy to calculate and it provides an output in the range of zero to one, which I always like.

Quite simply, the weight of money indicator provides a measure of how much money is available to back compared to how much is available to lay – or to look at it another way, sellers verses buyers. In theory, if there are more sellers than buyers then the price will fall and if there are more buyers than sellers then the price will rise.

Take this set of prices presented to us on the Betfair interface:

On the left we have the money available to back and on the right the money available to lay.

The weight of money is calculated simply by dividing the sum of all available back money by the total of all available money, i.e.

(62 + 420 + 402) / (62 + 420 + 402 + 62 + 36 + 46) = 0.8599 or 85.99%

Generally, the way to use this value is as follows:

0% to 33% means the price will move down.
33% to 66% means the direction is uncertain.
66% to 100% means the price will move up.

A few moments later, the price had moved up a tick, as predicted, and as seen below:

I certainly would not use this indicator by itself, but is does provide a very good feeling about where the market may move to next.

Hope this is useful.

John

NNATS Evolves

2009-04-25T11:02:00.003+01:00

It has been a while since my last post – as always, I am time starved! Any free time I’ve had has been spent, almost obsessively, developing NNATS.

It has taken hundreds of hours of coding and fair few lost pounds, but NNATS now operates completely unattended and is able to make small yet consistent profits. I cannot believe how hard it has been! The screenshot below shows the profit and loss for the last week. Not the stuff retirements are made of, but not bad either.

There are so many scenarios that we humans cope with automatically, but to NNATS is a completely new opportunity to lose money – these all have to be coded around.

My trading strategy has changed enormously since the early days, when I was trying to get NNATS to emulate human behaviour. NNATS has some real limitations compared to its human prey, but some great advantages too.

The main disadvantage is that NNATS cannot watch TV! A horse’s price can move out wildly leading up to a race if it looks jittery or has trouble going into the stalls, and of course, NNATS cannot see this happening. It can react to the price change and close a losing position, but this normally wipes out any profit from a few races, so why take the pain? Therefore, NNATS stops trading a market half an hour before the start, which means that is misses the high liquidity period during those last few minutes, which is a shame.

Now for the advantages. NNATS is an aggressive scalper and has adapted to trade in the lower liquidity portion of a market, before it hits TV. It will start trading as soon the market becomes available and will continue trading up to 30 minutes before the start. There are definitely some parallels here with evolution. NNATS has had to adapt to survive, and rather than evolve into a tiger, NNATS has become a patient predator – more like a crocodile.

Another advantage that NNATS has is that it trades all available markets in parallel, which means it has a pool of several hundred horses from which to choose.

However, the most significant evolutionary change is that NNATS no longer requires its neural network. The network served its purpose. It was fantastic for indentifying the useful indicators and the relationships between them, but this has now been replaced by hard coded logic.

One of the most significant indicators is the “weight of money”, which when used in conjunction with other signals is very powerful. The other thing the network indentified is the relationship between the runners. If something is moving out very strongly, then normally something is also moving in, and vice versa.

My plan going forward is to leave NNATS running for a few weeks, actively trading and capturing data. It is only by making trades, comparing expected outcomes against actuals, that I can gather enough information to feed a second-generation network. This network will make NNATS a stronger trader by learning from its mistakes.

In the meantime, I will post more articles about other areas of neural networks. I have some ideas bubbling away…

Thanks for reading and keep visiting.

John

NNATS Goes on a Diet

2009-02-25T18:23:00.009Z

If you read my last post, you will know that my goal is to build a fully automated trading system, assisted by a neural network, which will trade on the Betfair exchange – I call this system NNATS (Neural Network Assisted Trading System)

Since my last post, NNATS has matured a lot. I have learnt much more about the Betfair exchange, its API and about how to make (and lose) money.

In the beginning, NNATS had in excess of a hundred analogue input neurons. However, thanks to some clever pre-processing and my greater understanding of what is actually important, NNATS now has only one analogue input neuron (inverse of the current price) and twenty-three binary input neurons (on/off technical indicators).

The neural network supporting NNATS consists of four layers, comprising of the twenty-four input neurons mentioned already, six hidden neurons, two hidden neurons and one output neuron. The penultimate layer is deliberately two-dimensional, so that I can visualise what the network is doing – see my previous blog on this subject.

Using the network visualiser, I am quickly able to see how network training is progressing and tune as appropriate. The most significant thing to note is that I am not looking for an exact fit, as market price movements are probabilistic.

In the screenshot of the network visualiser below, the green points represent market conditions that have previously resulted in at least 25% profit. The red points represent market conditions where 25% profit could not be achieved.

The landscape is divided by a single hyper-plane. The hyper-plane defines a region, the “profit zone”, where NNATS believes there is a high probability of achieving at least 25% profit from a single trade. You will notice that there are still a few red points in the “profit zone” – this is because the market is probabilistic and cannot be predicted with 100% certainty. However, the number of green points in the “profit zone” far exceeds the number of red points, which means that profits should outweigh losses.

The other significant change I have made to NNATS is to remove completely the human trading interface - and subsequently me from the trading process. I had originally built myself a trading interface similar to Bet Angel, complete with trading ladders and charts. However, I have since discovered that I am my own worst enemy, and cannot prevent myself from overruling NNATS. The only time I have ever lost significant amounts of money is when I have ignored the advice provided by NNATS – therefore I have made the bold move to remove myself entirely.

Initial testing against trading simulations looks very promising. I just need to do some final plumbing and refinements before I trade for real again – all I lack is time. Work is very busy at the moment, and I’m about to go on yet another skiing holiday – it’s a tough life :-)

Once I have started trading for real, I will start posting P&Ls on this blog.

Neural Network Assisted Trading System - NNATS

2009-02-03T18:19:00.006Z

It has been some time since my last post – I have been distracted!

Over Christmas, I starting reading Adam Heathcote’s blog, Horse Racing Trader. He has set himself a challenge, that in 2009, he will make £150,000 from trading horseracing on the Betfair betting exchange. So far, in his first month, he has made well over £15,000 and is well on target to succeed.

I like three things about this challenge. Firstly, Adam is clearly very good at spotting trends and signals in the market, by analysing a stream of data provided by Betfair. Secondly, Betfair have published a web service API to allow you to interact with their exchange. Finally, any profits you make from Betfair are entirely tax-free!

This got me thinking that it might be worth pointing a neural network at the exchange and see if it could also spot the trends and signals that Adam is working with. Therefore, I opened a Betfair account, deposited £100 and started to hook up a neural network.

It took me a while to work out exactly I should be feeding into the network, and how I would identify the correct trading signals. However, after much trial and error, I seem to have something stable. I will not reveal exactly what the final configuration looks like just yet, but I will explain the basic mechanics of the trade.

How you make money from trading, rather than pure gambling, is quite easy to understand. Two terms you need to understand are “backing” and “laying”. By backing a horse, you are betting that it will win. By laying a horse, you are betting that it will loose. Betfair simply matches both sides of the bet.

To keep things simple, I only trade the favourite of an event and only ever on a falling market. A complete trade consists of placing a back bet at one price (odds) and a corresponding lay bet at a lower price.

The trades generally go something like this:

Back the favourite for £10 at decimal odds of 2.20

If the horse wins, I give the layer £10 and receive £22 in exchange. Therefore, I profit by £12.
If the horse loses, I give the layer £10 and receive nothing in exchange. Therefore, I lose £10.

Lay the favourite for £11 at decimal odds of 2.00

If the horse wins, the backer gives me £11 and receives £22 in exchange. Therefore, I lose £11.
If the horse loses, the backer gives me £11 and receives nothing in exchange. Therefore, I profit by £11.

As you can see, as long as I back and lay at the right amounts, I make the same amount of money regardless of whether the horse wins or loses. In the example above, in either case, I make £1 from a £10 stake, i.e. 10% profit on a single trade.

All well and good in theory, so I had to try it out for real. As you can see from my Betfair P&L screen below, on the first day I tried it, trading on ten different markets, and risking no more than £10, I made £5.91, or 59% profit. I was very happy with this result. At all times, I was in the loop, and actually making trades based on the network’s advice.

Since then, I have continued development, in the hope that NNATS will trade for me in a fully automated fashion, i.e. a money machine sitting in the corner of my room, quietly going about its business. This has not been without some scares, and the moral if the story is always debug your code before trading with real money. On one occasion, the stop loss feature fired at an inappropriate time and with a crazy expectation at which value I should close my position. Needless to say, I lost a few pounds on that trade!

Anyway, I shall continue to develop NNATS and report on its progress. Maybe one day I can stop working for a living…

John

Flocking Boids (C#)

2008-12-22T18:09:00.002Z

In this post, I shall demonstrate an example of swarm intelligence, which is based on the Boids model. In my ecosystem, two different types of Boids exist, namely Regular Boids and Zombie Boids. The Regular Boids are very social, fast moving creatures, which like to flock together. The Zombie Boids are solitary soles, whose single reason for living is to chase after Regular Boids, albeit very slowly.

There is no real problem I am trying to solve here, other than to enjoy watching the carnage that emerges! It would be very easy to add nicer graphics, or even turn this simulation into a screen saver. As usual, the full C# source code to generate this application is listed below.

Before I go into detail about the code, some background on Boids. In 1986, Craig Reynolds developed a computer model that simulated animal movement, such as flocks of birds and schools of fish. He called the simulated flocking creatures Boids.

As with most artificial life simulations, Boids is an example of emergent behaviour. The complexity of Boids arises from the interaction of individual agents complying with a simple set of rules. Reynolds basic flocking model consisted of three simple steering behaviours that determined how individual Boids should manoeuvre based on their velocity and position within the flock:

Separation: steer to avoid crowding local flock-mates
Cohesion: steer to move toward the average position of local flock-mates
Alignment: steer towards the average heading of local flock-mates

To provide even more life like effects, further rules could be added, such as obstacle avoidance and goal seeking.

The flocking algorithm requires that each Boid only react to flock-mates within its local neighbourhood. This neighbourhood is defined by the Boid’s field of view relative to the rest of the flock. Flock-mates outside of this neighbourhood are ignored.

The video below shows an example of the behaviour you can expect to emerge.

To implement Boids, I have used three classes, which are EcoSystem, Swarm and Boid. The EcoSystem class contains the entry point of the application, handles the graphics and serves as a container for the swarm. The Swarm class is responsible for creating and managing the entire the collection of Boids, known as the swarm. The Boid class encapsulates all logic pertaining to Boid behaviours, which, in this simulation, include separation, cohesion, alignment, avoidance and hunting.

using System;

using System.Collections.Generic;

using System.Drawing;

using System.Drawing.Drawing2D;

using System.Windows.Forms;

public class EcoSystem : Form

{

private Timer timer;

private Swarm swarm;

private Image iconRegular;

private Image iconZombie;

[STAThread]

private static void Main()

{

Application.Run(new EcoSystem());

}

public EcoSystem()

{

int boundary = 640;

SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.DoubleBuffer, true);

FormBorderStyle = FormBorderStyle.FixedToolWindow;

StartPosition = FormStartPosition.CenterScreen;

ClientSize = new Size(boundary, boundary);

iconRegular = CreateIcon(Brushes.Blue);

iconZombie = CreateIcon(Brushes.Red);

swarm = new Swarm(boundary);

timer = new Timer();

timer.Tick += new EventHandler(this.timer_Tick);

timer.Interval = 75;

timer.Start();

}

protected override void OnPaint(PaintEventArgs e)

{

foreach (Boid boid in swarm.Boids)

{

float angle;

if (boid.dX == 0) angle = 90f;

else angle = (float)(Math.Atan(boid.dY / boid.dX) * 57.3);

if (boid.dX < 0f) angle += 180f;

Matrix matrix = new Matrix();

matrix.RotateAt(angle, boid.Position);

e.Graphics.Transform = matrix;

if (boid.Zombie) e.Graphics.DrawImage(iconZombie, boid.Position);

else e.Graphics.DrawImage(iconRegular, boid.Position);

}

private static Image CreateIcon(Brush brush)

{

Bitmap icon = new Bitmap(16, 16);

Graphics g = Graphics.FromImage(icon);

Point p1 = new Point(0, 16);

Point p2 = new Point(16, 8);

Point p3 = new Point(0, 0);

Point p4 = new Point(5, 8);

Point[] points = { p1, p2, p3, p4 };

g.FillPolygon(brush, points);

return icon;

}

private void timer_Tick(object sender, EventArgs e)

{

swarm.MoveBoids();

Invalidate();

}

public class Swarm

{

public List<Boid> Boids = new List<Boid>();

public Swarm(int boundary)

{

for (int i = 0; i < 15; i++)

{

Boids.Add(new Boid((i > 12), boundary));

}

public void MoveBoids()

{

foreach (Boid boid in Boids)

{

boid.Move(Boids);

}

public class Boid

{

private static Random rnd = new Random();

private static float border = 100f;

private static float sight = 75f;

private static float space = 30f;

private static float speed = 12f;

private float boundary;

public float dX;

public float dY;

public bool Zombie;

public PointF Position;

public Boid(bool zombie, int boundary)

{

Position = new PointF(rnd.Next(boundary), rnd.Next(boundary));

this.boundary = boundary;

Zombie = zombie;

}

public void Move(List<Boid> boids)

{

if (!Zombie) Flock(boids);

else Hunt(boids);

CheckBounds();

CheckSpeed();

Position.X += dX;

Position.Y += dY;

}

private void Flock(List<Boid> boids)

{

foreach (Boid boid in boids)

{

float distance = Distance(Position, boid.Position);

if (boid != this && !boid.Zombie)

{

if (distance < space)

{

// Create space.

dX += Position.X - boid.Position.X;

dY += Position.Y - boid.Position.Y;

}

else if (distance < sight)

{

// Flock together.

dX += (boid.Position.X - Position.X) * 0.05f;

dY += (boid.Position.Y - Position.Y) * 0.05f;

}

if (distance < sight)

{

// Align movement.

dX += boid.dX * 0.5f;

dY += boid.dY * 0.5f;

}

if (boid.Zombie && distance < sight)

{

// Avoid zombies.

dX += Position.X - boid.Position.X;

dY += Position.Y - boid.Position.Y;

}

private void Hunt(List<Boid> boids)

{

float range = float.MaxValue;

Boid prey = null;

foreach (Boid boid in boids)

{

if (!boid.Zombie)

{

float distance = Distance(Position, boid.Position);

if (distance < sight && distance < range)

{

range = distance;

prey = boid;

}

if (prey != null)

{

// Move towards closest prey.

dX += prey.Position.X - Position.X;

dY += prey.Position.Y - Position.Y;

}

private static float Distance(PointF p1, PointF p2)

{

double val = Math.Pow(p1.X - p2.X, 2) + Math.Pow(p1.Y - p2.Y, 2);

return (float)Math.Sqrt(val);

}

private void CheckBounds()

{

float val = boundary - border;

if (Position.X < border) dX += border - Position.X;

if (Position.Y < border) dY += border - Position.Y;

if (Position.X > val) dX += val - Position.X;

if (Position.Y > val) dY += val - Position.Y;

}

private void CheckSpeed()

{

float s;

if (!Zombie) s = speed;

else s = speed / 4f;

float val = Distance(new PointF(0f, 0f), new PointF(dX, dY));

if (val > s)

{

dX = dX * s / val;

dY = dY * s / val;

}

I hope you enjoy Boids and much as I do – I find them strangely addictive to watch.

As always, if you have any comments or suggestions, please comment.

Cheers
John

C# Self Organising Map (SOM)

2008-11-16T13:58:00.013Z

In this post, I shall be discussing Self Organising Maps (SOM), which are also known as Kohonen maps or topographical maps. Until now, all of my posts have focussed on supervised learning, i.e. we present a set of patterns to a neural network along with the desired outputs. The network then adjusts its weights in order to recreate the correct outputs. However, suppose we do not know in advance what the outputs should be? How can we get the network to do something useful? This is called unsupervised learning. Some reasons we may choose to do this are:

Finding clusters

Dimensionality reduction

Finding hidden correlations

Data compression

Classification

A SOM is a two layer neural network that accepts N-dimensional input patterns and maps them to a lattice of output neurons, which represents feature space. The output map, which is typically two-dimensional, characterises the relative position of neurons with regards their neighbours, i.e. their topological properties rather than exact geometric locations. All input neurons are fully connected to all output neurons.

The training steps of a SOM are simple.

Initialise the interconnecting weights with random values.

Present an input pattern to the network.

Choose the output neuron with the highest activation (the “winner”).

Update the weights of neurons that are within the “neighbourhood” of the winner, using a relative learning factor.

Reduce the learning factor monotonically.

Reduce the size of the “neighbourhood” monotonically.

Repeat from step two until only small updates are observed.

The spread of the neighbourhood function will initially include all neurons on the grid, gradually reducing to include only the winning neuron.

To provide an example of what to expect from a SOM, I have prepared a simple example that will attempt to group twenty-five foods into regions of similarity, based on three parameters, which are protein, carbohydrate and fat.

Therefore, the challenge for this SOM is to reduce data containing three dimensions down to two, whilst retaining meaning. It does this by automatically indentifying differentiating features that will have the greatest effect.

The input data is as follows:

Item,protein,carb,fat
Apples,0.4,11.8,0.1
Avocado,1.9,1.9,19.5
Bananas,1.2,23.2,0.3
Beef Steak,20.9,0.0,7.9
Big Mac,13.0,19.0,11.0
Brazil Nuts,15.5,2.9,68.3
Bread,10.5,37.0,3.2
Butter,1.0,0.0,81.0
Cheese,25.0,0.1,34.4
Cheesecake,6.4,28.2,22.7
Cookies,5.7,58.7,29.3
Cornflakes,7.0,84.0,0.9
Eggs,12.5,0.0,10.8
Fried Chicken,17.0,7.0,20.0
Fries,3.0,36.0,13.0
Hot Chocolate,3.8,19.4,10.2
Pepperoni,20.9,5.1,38.3
Pizza,12.5,30.0,11.0
Pork Pie,10.1,27.3,24.2
Potatoes,1.7,16.1,0.3
Rice,6.9,74.0,2.8
Roast Chicken,26.1,0.3,5.8
Sugar,0.0,95.1,0.0
Tuna Steak,25.6,0.0,0.5
Water,0.0,0.0,0.0

After running this data through the SOM, the foods were placed on a 10x10 grid representing their relative similarities. A graphical representation is shown below.

How has the feature map grouped items together, whilst crushing three dimensions into two? Well, a number of zones have formed. Water, which contains no protein, carbs or fat, has been pushed to the bottom right. Directly above in the top right hand corner, sugar, which is made almost entirely of carbs, has taken hold. In the top left corner, butter reigns supreme, being almost entirely fat. Finally, the bottom left is occupied by tuna, which has the highest protein content of the foods in my sample. The remaining foods live between these extremes, with a junk food zone occupying the centre ground.

Below is the C# code, which will allow you to recreate and modify this example. Try adding more input dimensions and see what results. It is not always obvious to see what is happening, especially with a high number of dimensions. However, eventually you will normally be able to spot the, sometimes unexpected, correlation.

using System;

using System.Collections.Generic;

using System.IO;

public class Map

{

private Neuron[,] outputs; // Collection of weights.

private int iteration; // Current iteration.

private int length; // Side length of output grid.

private int dimensions; // Number of input dimensions.

private Random rnd = new Random();

private List<string> labels = new List<string>();

private List<double[]> patterns = new List<double[]>();

static void Main(string[] args)

{

new Map(3, 10, "Food.csv");

Console.ReadLine();

}

public Map(int dimensions, int length, string file)

{

this.length = length;

this.dimensions = dimensions;

Initialise();

LoadData(file);

NormalisePatterns();

Train(0.0000001);

DumpCoordinates();

}

private void Initialise()

{

outputs = new Neuron[length, length];

for (int i = 0; i < length; i++)

{

for (int j = 0; j < length; j++)

{

outputs[i, j] = new Neuron(i, j, length);

outputs[i, j].Weights = new double[dimensions];

for (int k = 0; k < dimensions; k++)

{

outputs[i, j].Weights[k] = rnd.NextDouble();

}

private void LoadData(string file)

{

StreamReader reader = File.OpenText(file);

reader.ReadLine(); // Ignore first line.

while (!reader.EndOfStream)

{

string[] line = reader.ReadLine().Split(',');

labels.Add(line[0]);

double[] inputs = new double[dimensions];

for (int i = 0; i < dimensions; i++)

{

inputs[i] = double.Parse(line[i + 1]);

}

patterns.Add(inputs);

}

reader.Close();

}

private void NormalisePatterns()

{

for (int j = 0; j < dimensions; j++)

{

double sum = 0;

for (int i = 0; i < patterns.Count; i++)

{

sum += patterns[i][j];

}

double average = sum / patterns.Count;

for (int i = 0; i < patterns.Count; i++)

{

patterns[i][j] = patterns[i][j] / average;

}

private void Train(double maxError)

{

double currentError = double.MaxValue;

while (currentError > maxError)

{

currentError = 0;

List<double[]> TrainingSet = new List<double[]>();

foreach (double[] pattern in patterns)

{

TrainingSet.Add(pattern);

}

for (int i = 0; i < patterns.Count; i++)

{

double[] pattern = TrainingSet[rnd.Next(patterns.Count - i)];

currentError += TrainPattern(pattern);

TrainingSet.Remove(pattern);

}

Console.WriteLine(currentError.ToString("0.0000000"));

}

private double TrainPattern(double[] pattern)

{

double error = 0;

Neuron winner = Winner(pattern);

for (int i = 0; i < length; i++)

{

for (int j = 0; j < length; j++)

{

error += outputs[i, j].UpdateWeights(pattern, winner, iteration);

}

iteration++;

return Math.Abs(error / (length * length));

}

private void DumpCoordinates()

{

for (int i = 0; i < patterns.Count; i++)

{

Neuron n = Winner(patterns[i]);

Console.WriteLine("{0},{1},{2}", labels[i], n.X, n.Y);

}

private Neuron Winner(double[] pattern)

{

Neuron winner = null;

double min = double.MaxValue;

for (int i = 0; i < length; i++)

for (int j = 0; j < length; j++)

{

double d = Distance(pattern, outputs[i, j].Weights);

if (d < min)

{

min = d;

winner = outputs[i, j];

}

return winner;

}

private double Distance(double[] vector1, double[] vector2)

{

double value = 0;

for (int i = 0; i < vector1.Length; i++)

{

value += Math.Pow((vector1[i] - vector2[i]), 2);

}

return Math.Sqrt(value);

}

public class Neuron

{

public double[] Weights;

public int X;

public int Y;

private int length;

private double nf;

public Neuron(int x, int y, int length)

{

X = x;

Y = y;

this.length = length;

nf = 1000 / Math.Log(length);

}

private double Gauss(Neuron win, int it)

{

double distance = Math.Sqrt(Math.Pow(win.X - X, 2) + Math.Pow(win.Y - Y, 2));

return Math.Exp(-Math.Pow(distance, 2) / (Math.Pow(Strength(it), 2)));

}

private double LearningRate(int it)

{

return Math.Exp(-it / 1000) * 0.1;

}

private double Strength(int it)

{

return Math.Exp(-it / nf) * length;

}

public double UpdateWeights(double[] pattern, Neuron winner, int it)

{

double sum = 0;

for (int i = 0; i < Weights.Length; i++)

{

double delta = LearningRate(it) * Gauss(winner, it) * (pattern[i] - Weights[i]);

Weights[i] += delta;

sum += delta;

}

return sum / Weights.Length;

}

As always, let me know what you think.

John

C# Back Propagation Neural Network with Multiple Outputs

2008-10-19T19:29:00.022+01:00

In this post, I publish an updated version of my multi layer Perceptron. The motivation for this is based on the great comments received on this blog. New features and improvements include:

A graphical representation of network activity
The ability to handle multiple network outputs
The ability to define any network architecture in a single line of code
A cleaner separation of responsibility within the code

In order to put this new network through its paces, I downloaded the classic Iris Plants Database from the UCI Machine Learning Repository. The data set contains three classes of fifty instances each, where each class refers to a type of iris plant. One class is linearly separable from the other two; the latter are not linearly separable from each other. To use this data, save the web page as a text file with a csv file extension. Open with Excel and add three new columns, on the right, filling with 0,0,1 or 0,1,0 or 1,0,0 depending on the species of plant. Delete the species name column and you now have a file which can be fed into your network. The video below shows the graphical output and clearly displays how the network converges on a solution.

There is quite a lot of code so I will cover each class individually.

Unlike my previous back propagation project, this one is a Windows Forms Application, so in Visual Studio begin by creating a new project and delete Form1.cs and Program.cs, which were automatically created for you. Create a new class file for each of the code blocks below.

Graph.cs
This is the container for the project and provides a graphical display of how the network is proceeding with training. In order to use the graphing feature, the penultimate layer of your network must contain two dimensions, which is not as restrictive as is sounds. I have found that being able to visualise network activity helps enormously when tuning your network. Things to look out for are inactivity, meaning the network has become stuck in a local minimum, or erratic activity meaning your learning rate is too high. If at any time you want to restart training, simply hit the space key and the network will reset. I guarantee that once you have tried this, you will never go back to gazing at streams of numbers…

using System;

using System.Drawing;

using System.Windows.Forms;

public class Graph : Form

{

private int iteration;

private Network network;

private Brush[] brushes = { Brushes.Red, Brushes.Green, Brushes.Blue };

[STAThread]

static void Main()

{

Application.Run(new Graph());

}

public Graph()

{

int[] dims = { 4, 4, 2, 3 }; // Replace with your network dimensions.

string file = "iris_data.csv"; // Replace with your input file location.

network = new Network(dims, file);

Initialise();

}

private void Initialise()

{

ClientSize = new Size(400, 400);

SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.Opaque, true);

FormBorderStyle = FormBorderStyle.FixedToolWindow;

StartPosition = FormStartPosition.CenterScreen;

KeyDown += new KeyEventHandler(Graph_KeyDown);

}

protected override void OnPaint(PaintEventArgs e)

{

double error = network.Train();

UpdatePlotArea(e.Graphics, error);

iteration++;

Invalidate();

}

private void UpdatePlotArea(Graphics g, double error)

{

string banner = "Iteration={0} Error={1:0.00}";

Text = string.Format(banner, iteration, error);

g.FillRectangle(Brushes.White, 0, 0, 400, 400);

foreach (float[] point in network.Points2D())

{

g.FillRectangle(brushes[(int)point[2]], point[0] * 395, point[1] * 395, 5, 5);

}

foreach (double[] line in network.HyperPlanes())

{

double a = -line[0] / line[1];

double c = -line[2] / line[1];

Point left = new Point(0, (int)(c * 400));

Point right = new Point(400, (int)((a + c) * 400));

g.DrawLine(new Pen(Color.Gray), left, right);

}

private void Graph_KeyDown(object sender, KeyEventArgs e)

{

if (e.KeyCode == Keys.Space)

{

network.Initialise();

iteration = 0;

}

Network.cs
As the name suggests, this is where the logic of the network resides. The big difference here between this and my previous project is that it can handle multiple outputs. In addition, the new constructor provides the ability to define any network architecture using an integer array. Thus, { 4, 4, 2, 3 } represents a network with four inputs, a first hidden layer with four neurons, a second hidden layer with two neurons, and a final output layer with three neurons.

using System;

using System.Collections.Generic;

using System.IO;

public class Network : List<Layer>

{

private int[] dimensions;

private List<Pattern> patterns;

public Network(int[] dimensions, string file)

{

this.dimensions = dimensions;

Initialise();

LoadPatterns(file);

}

public void Initialise()

{

base.Clear();

base.Add(new Layer(dimensions[0]));

for (int i = 1; i < dimensions.Length; i++)

{

base.Add(new Layer(dimensions[i], base[i - 1], new Random()));

}

private void LoadPatterns(string file)

{

patterns = new List<Pattern>();

StreamReader reader = File.OpenText(file);

while (!reader.EndOfStream)

{

string line = reader.ReadLine();

patterns.Add(new Pattern(line, Inputs.Count, Outputs.Count));

}

reader.Close();

}

public double Train()

{

double error = 0;

foreach (Pattern pattern in patterns)

{

Activate(pattern);

for (int i = 0; i < Outputs.Count; i++)

{

double delta = pattern.Outputs[i] - Outputs[i].Output;

Outputs[i].CollectError(delta);

error += Math.Pow(delta, 2);

}

AdjustWeights();

}

return error;

}

private void Activate(Pattern pattern)

{

for (int i = 0; i < Inputs.Count; i++)

{

Inputs[i].Output = pattern.Inputs[i];

}

for (int i = 1; i < base.Count; i++)

{

foreach (Neuron neuron in base[i])

{

neuron.Activate();

}

private void AdjustWeights()

{

for (int i = base.Count - 1; i > 0; i--)

{

foreach (Neuron neuron in base[i])

{

neuron.AdjustWeights();

}

public List<double[]> HyperPlanes()

{

List<double[]> lines = new List<double[]>();

foreach (Neuron n in Outputs)

{

lines.Add(n.HyperPlane);

}

return lines;

}

public List<float[]> Points2D()

{

int penultimate = base.Count - 2;

if (base[penultimate].Count != 2)

{

throw new Exception("Penultimate layer must be 2D for graphing.");

}

List<float[]> points = new List<float[]>();

for (int i = 0; i < patterns.Count; i++)

{

Activate(patterns[i]);

float[] point = new float[3];

point[0] = (float)base[penultimate][0].Output;

point[1] = (float)base[penultimate][1].Output;

if (Outputs.Count > 1)

{

point[2] = patterns[i].MaxOutput;

}

else

{

point[2] = (patterns[i].Outputs[0] >= 0.5) ? 1 : 0;

}

points.Add(point);

}

return points;

}

private Layer Inputs

{

get { return base[0]; }

}

private Layer Outputs

{

get { return base[base.Count - 1]; }

}

Neuron.cs
This class represents the neuron, and contains activation and training logic.

using System;

using System.Collections.Generic;

public class Neuron

{

private double bias; // Bias value.

private double error; // Sum of error.

private double input; // Sum of inputs.

private double gradient = 5; // Steepness of sigmoid curve.

private double learnRate = 0.01; // Learning rate.

private double output = double.MinValue; // Preset value of neuron.

private List<Weight> weights; // Collection of weights to inputs.

public Neuron() { }

public Neuron(Layer inputs, Random rnd)

{

weights = new List<Weight>();

foreach (Neuron input in inputs)

{

Weight w = new Weight();

w.Input = input;

w.Value = rnd.NextDouble() * 2 - 1;

weights.Add(w);

}

public void Activate()

{

error = 0;

input = 0;

foreach (Weight w in weights)

{

input += w.Value * w.Input.Output;

}

public void CollectError(double delta)

{

if (weights != null)

{

error += delta;

foreach (Weight w in weights)

{

w.Input.CollectError(error * w.Value);

}

public void AdjustWeights()

{

for (int i = 0; i < weights.Count; i++)

{

weights[i].Value += error * Derivative * learnRate * weights[i].Input.Output;

}

bias += error * Derivative * learnRate;

}

private double Derivative

{

get

{

double activation = Output;

return activation * (1 - activation);

}

public double Output

{

get

{

if (output != double.MinValue)

{

return output;

}

return 1 / (1 + Math.Exp(-gradient * (input + bias)));

}

set

{

output = value;

}

public double[] HyperPlane

{

get

{

double[] line = new double[3];

line[0] = weights[0].Value;

line[1] = weights[1].Value;

line[2] = bias;

return line;

}

Layer.cs
This class inherits from List<Neuron> and simply holds a collection of neurons representing a discrete layer within the network.

using System;

using System.Collections.Generic;

public class Layer : List<Neuron>

{

public Layer(int size)

{

for (int i = 0; i < size; i++)

base.Add(new Neuron());

}

public Layer(int size, Layer layer, Random rnd)

{

for (int i = 0; i < size; i++)

base.Add(new Neuron(layer, rnd));

}

Weight.cs
This class holds a pointer to a contributing neuron and the associated weight value.

public class Weight

{

public Neuron Input;

public double Value;

}

Pattern.cs
This class holds a single line of data from your input file in a form that can be consumed by the network.

using System;

public class Pattern

{

private double[] inputs;

private double[] outputs;

public Pattern(string value, int inputDims, int outputDims)

{

string[] line = value.Split(',');

if (line.Length != inputDims + outputDims)

throw new Exception("Input does not match network configuration");

inputs = new double[inputDims];

for (int i = 0; i < inputDims; i++)

{

inputs[i] = double.Parse(line[i]);

}

outputs = new double[outputDims];

for (int i = 0; i < outputDims; i++)

{

outputs[i] = double.Parse(line[i + inputDims]);

}

public int MaxOutput

{

get

{

int item = -1;

double max = double.MinValue;

for (int i = 0; i < Outputs.Length; i++)

{

if (Outputs[i] > max)

{

max = Outputs[i];

item = i;

}

return item;

}

public double[] Inputs

{

get { return inputs; }

}

public double[] Outputs

{

get { return outputs; }

}

I hope you find this network useful. If you have any question or suggestions, I would be happy to hear from you.

How Many Hidden Neurons and Layers?

2008-10-05T17:49:00.012+01:00

In this post, I will be discussing the neural networker’s perennial question – how many hidden neurons and hidden layers are required to solve my problem? My advice is very simple, as few as possible…

There is currently no mathematical theory that provides a definitive answer to this question. The reality is that structured trial and error must be used instead.

Let us frame the problem. If too few hidden neurons are used, the network will be unable to model complex data, resulting in a poor fit. If too many hidden neurons are used, then training will become excessively long and the network may over fit. Over fitting occurs when the network begins to model random noise contained within the data, resulting in a failure to converge on a generalised solution.

How about the number of hidden layers? For most problems, one hidden layer is normally sufficient. However, should your data contain discontinuities, such as a saw tooth waveform, another hidden layer can help. It is worth noting that neural networks with two hidden layers can approximate functions of any shape, so there is no theoretical reason use any more.

So what do I mean by “structured trial and error”? The process I generally use to determine the number of hidden neurons relies on the premise that networks with too many hidden neurons will converge. Therefore, the goal is try to quickly find the smallest network that converges and then refine the answer by working back from there.

Start with one hidden neuron – the equivalent of a single layer Perceptron.
Begin training the network.
If the network fails to converge after a reasonable period, restart training up to ten times, thus ensuring that it has not fallen into a local minimum.
If the network still fails to converge, add another hidden neuron and return to step two.
If you get to here, then the network has converged. Note the number of hidden neurons, as this is your guaranteed maximum required.
Remove a hidden neuron and restart training.
Repeat the cycle of training and restarting, until either the network converges on a new solution or you choose to stop.
If the network converges, then you have just lowered your guaranteed maximum. Return to step five.

Using the process outlined above I will provide some examples of problems I have solved, indicating the corresponding hidden neuron requirement.

Binary Classification
With binary classification, we are only interested in the corners of a hypercube, and not the space contained within. The XOR (or parity) problem falls into this category. The table below represents the complete set of data for a three dimensional XOR problem. These points can be mapped onto a cube, as shown.

x	y	z	out
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Using my multi layer Perceptron published a few weeks ago, I quickly obtained hidden neuron requirements to solve XOR for patterns ranging from one bit to eight bits. The results are shown on the graph below.

Function Approximation
Moving on from binary classification, I fed a selection of continuous functions into the network, and again obtained the number of hidden neurons required for a respectable approximation. These are shown in the graphs below, along with an approximation of the function produced by the network after training. I have indicated the structure of the network using the convention input:hidden:output. As you can see in these examples, the number of hidden neurons ranges from zero to five depending on the complexity of the function.


z = (x + y) / 2	2:0:1 network

z = x y*	2:2:1 network

z = Sin(x 3.142) * Sin(y * 3.142)*	2:3:1 network

z = Abs(Cos(x 3.142) * Sin(y * 3.142))*	2:5:1 network

Pattern Recognition
This is a more complex problem, and really depends on the function you expect the network to perform. Let us say you want to scan a series of infrared satellite images for the existence of military vehicles. The images may have a resolution of 10 mega pixels. Do you create a network containing ten million input nodes and expect it to learn? Probably not - in this case, it would make more sense to slide a square window, consisting of a few hundred pixels across the image, and feed the output of that into a network.

A hidden layer, containing maybe tens of neurons, would then act as a feature detector, trained to detect the various military vehicles. The network may also contain several output neurons, each representing a different type of vehicle. Again, with this type of problem, structured trial and error is required to lead you to the correct outcome.

I hope that this brief explanation provides you with the means to determine the appropriate structure for your networks. It really is an art rather than a science.

In my next post, I will introduce Formula AI. The purpose of this project is to show how an artificial neural network is not only able to learn how to navigate a virtual racetrack, but will also learn optimum racing lines and breaking points. Stay tuned…

Data Mining with Artificial Neural Networks (ANN)

2008-09-27T10:45:00.005+01:00

In this post, I will show how artificial neural networks can be used as a technique for data mining and discovering correlations in seemingly random data sets. To provide a context, I will be conducting a fictitious experiment on lunar fruit bats…

On Moon Base 6, Dr Notion has been assisting a team of exobiologists in performing a study on the recently discovered lunar fruit bat. What puzzles them is that whilst the bats are genetically almost identical, their life spans vary enormously. Adding to the mystery, these strange little creatures eat only once in their short life, so the scientists believe there is a connection between their diet and lifespan.

In a controlled experiment, fifty fruit bats were allowed to eat up to one gram from each of four different fruits. The scientists then observed how long the bats lived after eating. Some dropped dead almost immediately, so clearly something was poisoning them, whilst others lived for nearly a full lunar month. The graph below, sorted by increasing longevity, shows how diet relates to life span.

There appears to be no correlation at all.

Undeterred, Dr Notion decided he would try feeding the data into my neural network published last week. He pasted the experiment’s data set (below) into the patterns.csv file and set the _ inputDims variable to a value of four, representing the four fruits from the experiment.

He ran the program and, almost immediately, the network found a solution, proving there was a correlation between fruit type and life span.

Dr Notion decided to write some code so that he could inspect the value of the weights after training. He noted his observations on the network diagram below.

Using these values, he wrote down the equation of the network, where f is the activation function, and discarding any values approaching zero, which gave:

o = f(1.15 * f(0.87b + 0.47c -0.88d) + 1.30 * f(-0.62b + 0.50c + 0.64d) – 2.00)

He noted that the proportion and sign of the weights were more important than their absolute values, due to the distorting effect of the sigmoid activation function. Therefore, three important features stood out:

Fruit A did not appear, so has no bearing on life span.
Fruit C appears with positive values at each hidden neuron, so has a positive correlation with life span.
Fruits B and D appear in equal and opposite amounts at each hidden neuron, and always with a value larger than fruit C. This meant that similar proportions of fruit B and D had to be eaten otherwise they would be poisonous. They were mutual antidotes.

Armed with this information, Dr Notion theorised that the relation between fruit type and life span could be stated:

Life Span = C - |B-D|

Alternatively:

Life Span = C - ABS(B-D)

He tested his theory by substituting the values from the experiment’s data set into the equation, and Voilà, it matched. Advice for a lunar fruit bat – eat a diet consisting of just fruit C!

Dr Neuron and the exobiologists were happy and went to the pub…

Data set from the experiment:

Fruit A,Fruit B,Fruit C,Fruit D,Life
0.265,0.914,0.262,0.446,0.000
0.232,0.761,0.205,0.371,0.000
0.481,0.011,0.730,0.774,0.000
0.700,0.812,0.042,0.864,0.000
0.149,0.383,0.190,0.022,0.000
0.462,0.452,0.359,0.067,0.000
0.673,0.939,0.898,0.010,0.000
0.971,0.193,0.135,0.993,0.000
0.217,0.163,0.434,0.874,0.000
0.764,0.594,0.074,0.075,0.000
0.197,0.969,0.607,0.201,0.000
0.749,0.309,0.407,0.647,0.070
0.701,0.594,0.186,0.488,0.080
0.685,0.540,0.460,0.167,0.086
0.205,0.275,0.272,0.447,0.099
0.625,0.007,0.251,0.154,0.105
0.238,0.896,0.542,0.476,0.122
0.641,0.402,0.429,0.681,0.150
0.747,0.758,0.725,0.227,0.194
0.656,0.552,0.446,0.790,0.208
0.305,0.831,0.248,0.801,0.219
0.585,0.130,0.389,0.293,0.227
0.695,0.518,0.515,0.237,0.234
0.070,0.512,0.473,0.739,0.246
0.174,0.608,0.810,0.051,0.253
0.845,0.084,0.513,0.316,0.281
0.898,0.676,0.950,0.018,0.292
0.547,0.244,0.606,0.538,0.312
0.040,0.378,0.426,0.490,0.315
0.941,0.663,0.589,0.932,0.320
0.347,0.723,0.495,0.571,0.343
0.213,0.831,0.576,0.646,0.391
0.235,0.127,0.945,0.673,0.399
0.484,0.320,0.832,0.708,0.445
0.873,0.676,0.732,0.948,0.460
0.808,0.551,0.564,0.630,0.485
0.734,0.446,0.666,0.299,0.519
0.911,0.596,0.719,0.405,0.529
0.334,0.997,0.620,0.928,0.551
0.087,0.503,0.585,0.514,0.573
0.614,0.635,0.933,0.316,0.614
0.797,0.340,0.862,0.575,0.626
0.785,0.572,0.931,0.866,0.637
0.090,0.423,0.771,0.304,0.652
0.525,0.075,0.897,0.281,0.691
0.488,0.569,0.780,0.518,0.729
0.779,0.365,0.793,0.340,0.768
0.886,0.742,0.928,0.618,0.804
0.059,0.496,0.900,0.556,0.840
0.151,0.939,0.997,0.999,0.967

Training Neural Networks Using Back Propagation in C#

2008-09-21T16:12:00.010+01:00

In my previous post, I showed how multi layer Perceptrons could be used to solve linearly non-separable problems. In that example, I calculated all the network weights by hand. In this post, I shall introduce the back propagation training algorithm, which will do all the hard work for us.

The back propagation algorithm has become the de facto training algorithm for artificial neural networks, and has been studied by the artificial intelligence community since the 1970s. It is used in commercial neural network software packages, such a MATLAB.

The principle of back propagation is actually quite easy to understand, even though the maths behind it can look rather daunting. The basic steps are:

Initialise the network with small random weights.
Present an input pattern to the input layer of the network.
Feed the input pattern forward through the network to calculate its activation value.
Take the difference between desired output and the activation value to calculate the network’s activation error.
Adjust the weights feeding the output neuron to reduce its activation error for this input pattern.
Propagate an error value back to each hidden neuron that is proportional to their contribution of the network’s activation error.
Adjust the weights feeding each hidden neuron to reduce their contribution of error for this input pattern.
Repeat steps 2 to 7 for each input pattern in the input collection.
Repeat step 8 until the network is suitably trained.

It is important to note that each pattern is presented in turn, and the network adjusted slightly, before moving on to the next pattern. If we simply let the network perfectly correct the errors before moving onto the next pattern, it would never learn a generalised solution for the entire input collection.

The magic really happens in step 6, which determines how much error to feed back to each hidden neuron. Once the error value has been established, training can continue as described in my post about the single layer perceptron.

To illustrate how the error value is calculated, I will use this network diagram.

Then, if we use these variables:

output_o = Activation value of the output neuron
error_o = Error at the output neuron
error_h = Error at a hidden neuron
weight_ho = A weight connecting a hidden neuron to the output neuron

The error feed back to a hidden neuron is calculated:

error_h = error_o * Derivative(output_o) * weight_ho

For an explaination about how to calculate the derivative value, see my post on the sigmoid function.

Unlike the single layer Perceptron, training a multi layer Perceptron with back propagation does not guarantee a solution, even if one is available. This is because training can become stuck in a local error minimum. There are a number of strategies to overcome this, which I shall cover another time. For now, restarting training is normally sufficient for small networks.

I will continue to use the same classification problem from my last post.

Representing these input patterns. You should copy and paste these into a Patterns.csv file to use in the code sample below:

0.10, 0.03, 0
0.11, 0.11, 0
0.11, 0.82, 0
0.13, 0.17, 0
0.20, 0.81, 0
0.21, 0.57, 1
0.25, 0.52, 1
0.26, 0.48, 1
0.28, 0.17, 1
0.28, 0.45, 1
0.37, 0.28, 1
0.41, 0.92, 0
0.43, 0.04, 1
0.44, 0.55, 1
0.47, 0.84, 0
0.50, 0.36, 1
0.51, 0.96, 0
0.56, 0.62, 1
0.65, 0.01, 1
0.67, 0.50, 1
0.73, 0.05, 1
0.73, 0.90, 0
0.73, 0.99, 0
0.78, 0.01, 1
0.83, 0.62, 0
0.86, 0.42, 1
0.86, 0.91, 0
0.89, 0.12, 1
0.95, 0.15, 1
0.98, 0.73, 0

The code below is my implementation of back propagation in C#. In my opinion C# Generics are a beautiful thing, and you will see that I use them extensively. To run this code, create a new C# Console application and paste the code into the Program.cs file. Paste the input patterns into a file named Patterns.csv located in your project directory. Include Patterns.csv in your project, and make sure you set its “Copy to Output Directory” attribute to True.

using System;

using System.Collections.Generic;

using System.IO;

public class Network

{

private int _hiddenDims = 2; // Number of hidden neurons.

private int _inputDims = 2; // Number of input neurons.

private int _iteration; // Current training iteration.

private int _restartAfter = 2000; // Restart training if iterations exceed this.

private Layer _hidden; // Collection of hidden neurons.

private Layer _inputs; // Collection of input neurons.

private List<Pattern> _patterns; // Collection of training patterns.

private Neuron _output; // Output neuron.

private Random _rnd = new Random(); // Global random number generator.

[STAThread]

static void Main()

{

new Network();

}

public Network()

{

LoadPatterns();

Initialise();

Train();

Test();

}

private void Train()

{

double error;

{

error = 0;

foreach (Pattern pattern in _patterns)

{

double delta = pattern.Output - Activate(pattern);

AdjustWeights(delta);

error += Math.Pow(delta, 2);

}

Console.WriteLine("Iteration {0}\tError {1:0.000}", _iteration, error);

_iteration++;

if (_iteration > _restartAfter) Initialise();

} while (error > 0.1);

}

private void Test()

{

Console.WriteLine("\nBegin network testing\nPress Ctrl C to exit\n");

while (1 == 1)

{

try

{

Console.Write("Input x, y: ");

string values = Console.ReadLine() + ",0";

Console.WriteLine("{0:0}\n", Activate(new Pattern(values, _inputDims)));

}

catch (Exception e)

{

Console.WriteLine(e.Message);

}

private double Activate(Pattern pattern)

{

for (int i = 0; i < pattern.Inputs.Length; i++)

{

_inputs[i].Output = pattern.Inputs[i];

}

foreach (Neuron neuron in _hidden)

{

neuron.Activate();

}

_output.Activate();

return _output.Output;

}

private void AdjustWeights(double delta)

{

_output.AdjustWeights(delta);

foreach (Neuron neuron in _hidden)

{

neuron.AdjustWeights(_output.ErrorFeedback(neuron));

}

private void Initialise()

{

_inputs = new Layer(_inputDims);

_hidden = new Layer(_hiddenDims, _inputs, _rnd);

_output = new Neuron(_hidden, _rnd);

_iteration = 0;

Console.WriteLine("Network Initialised");

}

private void LoadPatterns()

{

_patterns = new List<Pattern>();

StreamReader file = File.OpenText("Patterns.csv");

while (!file.EndOfStream)

{

string line = file.ReadLine();

_patterns.Add(new Pattern(line, _inputDims));

}

file.Close();

}

public class Layer : List<Neuron>

{

public Layer(int size)

{

for (int i = 0; i < size; i++)

base.Add(new Neuron());

}

public Layer(int size, Layer layer, Random rnd)

{

for (int i = 0; i < size; i++)

base.Add(new Neuron(layer, rnd));

}

public class Neuron

{

private double _bias; // Bias value.

private double _error; // Sum of error.

private double _input; // Sum of inputs.

private double _lambda = 6; // Steepness of sigmoid curve.

private double _learnRate = 0.5; // Learning rate.

private double _output = double.MinValue; // Preset value of neuron.

private List<Weight> _weights; // Collection of weights to inputs.

public Neuron() { }

public Neuron(Layer inputs, Random rnd)

{

_weights = new List<Weight>();

foreach (Neuron input in inputs)

{

Weight w = new Weight();

w.Input = input;

w.Value = rnd.NextDouble() * 2 - 1;

_weights.Add(w);

}

public void Activate()

{

_input = 0;

foreach (Weight w in _weights)

{

_input += w.Value * w.Input.Output;

}

public double ErrorFeedback(Neuron input)

{

Weight w = _weights.Find(delegate(Weight t) { return t.Input == input; });

return _error * Derivative * w.Value;

}

public void AdjustWeights(double value)

{

_error = value;

for (int i = 0; i < _weights.Count; i++)

{

_weights[i].Value += _error * Derivative * _learnRate * _weights[i].Input.Output;

}

_bias += _error * Derivative * _learnRate;

}

private double Derivative

{

get

{

double activation = Output;

return activation * (1 - activation);

}

public double Output

{

get

{

if (_output != double.MinValue)

{

return _output;

}

return 1 / (1 + Math.Exp(-_lambda * (_input + _bias)));

}

set

{

_output = value;

}

public class Pattern

{

private double[] _inputs;

private double _output;

public Pattern(string value, int inputSize)

{

string[] line = value.Split(',');

if (line.Length - 1 != inputSize)

throw new Exception("Input does not match network configuration");

_inputs = new double[inputSize];

for (int i = 0; i < inputSize; i++)

{

_inputs[i] = double.Parse(line[i]);

}

_output = double.Parse(line[inputSize]);

}

public double[] Inputs

{

get { return _inputs; }

}

public double Output

{

get { return _output; }

}

public class Weight

{

public Neuron Input;

public double Value;

}

When the application runs, it will use the back propagation algorithm to train the network, restarting if it gets trapped in a local error minimum. Once fully trained, you will be able to test the network against untrained points on the graph and observe that it generalises correctly.

It is simple to modify the code to accept more input dimensions and use more hidden neurons, by changing the variables _inputDims and _hiddenDims. If you try this, make sure to add extra columns to the Patterns.csv file. By doing this, this network can be used to solve very complex problems.

In future posts, I will be using networks like this to solve real world problems - I would welcome suggestions.

John

Hidden Neurons and Feature Space

2008-09-13T15:00:00.010+01:00

In this post, I continue on the journey to solve linearly non-separable problems using the Multi Layer Perceptron. I will be using the same problem that I introduced last week.

The network I will be using to solve this problem is shown below. If you read my previous post, you will notice that I have introduced a bias to the network. Without a bias, any hyperplane must always pass through the origin, i.e. (0, 0), which is an unnecessary restriction.

The role of the two hidden neurons is divide input space into partitions. In order to achieve this, I have chosen two arbitrary hyperplanes and drawn them on the graph below.

The values in the equations map directly to the weights in the network. However, first the equations must be rearranged with all terms on the same side of the equals sign, i.e. 0 = y + 0.36x - 0.85, etc. Therefore, the weights in the network are as follows:

xh1 = 0.36
yh1 = 1
bh1 = -0.85

xh2 = 1.92
yh2 = 1
bh2 = -0.70

Using the sigmoid function introduced in my last post, this creates a feature space that looks like this, with h1 along the horizontal axis and h2 along the vertical axis.

As you can see, feature space is a distorted view of input space. Each of the points representing a class clearly fall within a distinct quadrant of the graph, which is evidence that the weights have done their job.

However, this feature space is still linearly non-separable, so the output neuron will still fail in its task of correctly classifying the points. To correct this, we need to modify the sigmoid function, and introduce another variable known as lambda (λ).

public double Function(double x)

{

return 1 / (1 + Math.Exp(-lambda * x));

}

Lambda has the effect of steepening the gradient of the sigmoid function, which in turn further distorts input space. By using a lambda value of six, feature space now looks like this.

As you can see, this now results in a linearly separable pattern of points, which the output neuron can correctly classify. Again, the values in the equation map directly to the weights in the network. Therefore, the weights in the final layer of the network are as follows:

h1o = -0.73
h2o = 1
bo = 0.21

Therefore, we now have a network that can correctly classify the points of a linearly non-separable problem.

However, so far, we have done all the work ourselves. How do we get the network to establish correctly the required values of the weights automatically? In order to do that, we need a learning algorithm. In my next post, I will introduce the Back Propagation algorithm and provide a working example written in C#.

In the meantime, if you have any questions on this post, drop me a comment.

John

The Sigmoid Function in C#

2008-09-07T07:48:00.008+01:00

In my last post, I discussed the Single Layer Perceptron and its limitations regarding solving linearly non-separable problems. If we are to solve this type of problem, then we need a more sophisticated network, and that means adding layers. However, if we do that, how do we train the network?

Until now, we have used the error observed at the output neuron to adjust the weights between it and the input layer. But, what do we do if we add another layer in between, a hidden layer? Well, we still need to feed this error back through the network in order to adjust the weights, and this is a problem.

Currently, a neuron is either “on” or “off”, which is defined by the threshold activation function we are using.

public int Function(double x)

{

return (x >= 0) ? 1 : -1;

}

When graphed, it looks like this, with the blue line representing the function and the red line its derivative, which at zero is infinity (not very useful).

Any adjustment we make to the weights feeding the hidden layer is going to be rather course, so we need to smooth this out. We can do that by replacing our simple threshold function with something better. How about this? This is known as a sigmoid function.

public double Sigmoid(double x)

{

return 2 / (1 + Math.Exp(-2 * x)) - 1;

}

And its derivative.

f'(x) = 1 - f(x)²

public double Derivative(double x)

{

double s = Sigmoid(x);

return 1 - (Math.Pow(s, 2));

}

When graphed, it looks like this.

Now, this looks much more useful. There is a smooth and continuous transition between -1 and 1, and the derivative goes nowhere near infinity. Whilst this function is very popular with many neural net developers, I would like to make one further refinement. I like my neurons to be working in the range of 0 to 1, and to do that I need to modify the function slightly.

public double Sigmoid(double x)

{

return 1 / (1 + Math.Exp(-x));

}

And its derivative.

f'(x) = f(x)(1 - f(x))

public double Derivative(double x)

{

double s = Sigmoid(x);

return s * (1 - s);

}

When graphed, it looks like this.

Now, that is perfect, and it has the added benefit of being computationally less demanding, which will be important for larger networks.

In my next post, I will show you how to use the sigmoid activation function to build a Multi Layer Perceptron, trained with the Back Propagation Algorithm.

I welcome comments on this post, and suggestions for future posts.

John

The Single Layer Perceptron

2008-09-04T19:51:00.014+01:00

This is the first in a series of posts in which I will write about the evolution of neural networks. I will start with the most simple network of all, the Single Layer Perceptron, and work through different architectures and learning methods which will eventually lead to networks that can predict stock market price movements, perform face recognition, handle natural language processing and much more.

I will provide full code samples, written in C#, which can be compiled and run by downloading Visual C# 2008 Express Edition from Microsoft at http://www.microsoft.com/express/vcsharp/

The Perceptron is the grand daddy of all neural networks. It was invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. The Perceptron is the simplest type of feed forward neural network, known as a linear classifier. This means that the type of problems the network can solve must be linearly separable. In the graphs shown below it is easy to visualise what this means in two dimensions.


*This is linearly separable.*	This is linearly non-separable.

The green line represents the separation between the two classes of data the network is attempting to classify. In three dimensions this would be represented by a plane, and in four dimensions or more by a hyperplane. There are other types of network that can solve linearly non-separable problems, which I will cover in later posts.

To begin to solve this problem we need a network as represented below.

As you can see, each input node is connected directly to the output node. By adjusting the value of the connecting weights, the network is able to learn.

In the demonstration below each of the points plotted in the first graph above will be used as training data. The training data will be repeatedly applied to the input nodes of the network and the weights adjusted until the network is performs as desired.

Once the network has been trained the application will step through the range of input data to prove that the network has learnt correctly and is able to perform good generalisation. The following code shows how this is done.

using System;

namespace Perceptron

{

public class Perceptron

{

[STAThread]

static void Main()

{

// Load sample input patterns.

double[,] inputs = new double[,] {

{ 0.72, 0.82 }, { 0.91, -0.69 }, { 0.46, 0.80 },

{ 0.03, 0.93 }, { 0.12, 0.25 }, { 0.96, 0.47 },

{ 0.79, -0.75 }, { 0.46, 0.98 }, { 0.66, 0.24 },

{ 0.72, -0.15 }, { 0.35, 0.01 }, { -0.16, 0.84 },

{ -0.04, 0.68 }, { -0.11, 0.10 }, { 0.31, -0.96 },

{ 0.00, -0.26 }, { -0.43, -0.65 }, { 0.57, -0.97 },

{ -0.47, -0.03 }, { -0.72, -0.64 }, { -0.57, 0.15 },

{ -0.25, -0.43 }, { 0.47, -0.88 }, { -0.12, -0.90 },

{ -0.58, 0.62 }, { -0.48, 0.05 }, { -0.79, -0.92 },

{ -0.42, -0.09 }, { -0.76, 0.65 }, { -0.77, -0.76 } };

// Load sample output patterns.

int[] outputs = new int[] {

-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

int patternCount = inputs.GetUpperBound(0) + 1;

// Randomise weights.

Random r = new Random();

double[] weights = { r.NextDouble(), r.NextDouble() };

// Set learning rate.

double learningRate = 0.1;

int iteration = 0;

double globalError;

{

globalError = 0;

for (int p = 0; p < patternCount; p++)

{

// Calculate output.

int output = Output(weights, inputs[p, 0], inputs[p, 1]);

// Calculate error.

double localError = outputs[p] - output;

if (localError != 0)

{

// Update weights.

for (int i = 0; i < 2; i++)

{

weights[i] += learningRate * localError * inputs[p, i];

}

// Convert error to absolute value.

globalError += Math.Abs(localError);

}

Console.WriteLine("Iteration {0}\tError {1}", iteration, globalError);

iteration++;

} while (globalError != 0);

// Display network generalisation.

Console.WriteLine();

Console.WriteLine("X, Y, Output");

for (double x = -1; x <= 1; x += .5)

{

for (double y = -1; y <= 1; y += .5)

{

// Calculate output.

int output = Output(weights, x, y);

Console.WriteLine("{0}, {1}, {2}", x, y, (output == 1) ? "Blue" : "Red");

}

Console.ReadKey();

}

private static int Output(double[] weights, double x, double y)

{

double sum = x * weights[0] + y * weights[1];

return (sum >= 0) ? 1 : -1;

}

The output from the network after training looks like this, which proves generalisation has been correctly achieved. Each pair of x and y coordinates when presented to the network returns the classification expected, i.e. blue or red.

X, Y, Output
-1.0, -1.0, Blue
-1.0, -0.5, Blue
-1.0, 0.0, Blue
-1.0, 0.5, Blue
-1.0, 1.0, Blue
-0.5, -1.0, Blue
-0.5, -0.5, Blue
-0.5, 0.0, Blue
-0.5, 0.5, Blue
-0.5, 1.0, Red
0.0, -1.0, Blue
0.0, -0.5, Blue
0.0, 0.0, Blue
0.0, 0.5, Red
0.0, 1.0, Red
0.5, -1.0, Blue
0.5, -0.5, Red
0.5, 0.0, Red
0.5, 0.5, Red
0.5, 1.0, Red
1.0, -1.0, Red
1.0, -0.5, Red
1.0, 0.0, Red
1.0, 0.5, Red
1.0, 1.0, Red

Whilst this may seem like a trivial problem to solve in two dimensions, the Perceptron can perform very powerful analysis in higher dimensions. The same general principals shown here will apply.

In my next post, I will start to write about the multi-layer perceptron, which can be used to solve linearly non-separable problems, like the one presented in the second graph above.

I welcome feedback on this post, and would be interested in receiving suggestions for future posts.