Rinat Abdullin on NeuroEvolution

Strategy Pattern in .NET NeuroEvolution Algorithms

2009-01-08T13:32:30Z

Getting back to the NeuroEvolution research after a couple of years of delay has turned out to be quite rewarding.

For example, while writing new implementation of the algorithm from scratch I just could not avoid leveraging some principles from the Lokad Shared (apart from using the core library). One of these patterns is about cleanly separating some logic in the delegates, and then combining these delegates to produce the desired effects.

We had Action Policies and Validation Rules in .NET enterprise development. In NeuroEvolution algorithms we can also apply these principles to mutation strategies.

By the way, I've created a separate page to serve as an index for these NeuroEvolution series. And there also is a NeuroEvolution RSS feed.

Strategy Pattern

Every evolutionary algorithm leverages operations like mutate or crossover that have certain probability of occuring. Additionally, NeuroEvolutional algorithms (being more specific) have to operate with the networks that can grow and thus they leverage strategies like AddConnection, RemoveConnection, Jiggle and some others.

Since such algorithms are being developed within the the research process, soon they turn into a mess of heuristics:

foreach (var genome in winners)
{
  if (Rand.NextDouble() < mutationChance)
  {
    // do mutation
  }
  if (Rand.NextDouble() < crossOverChance)
  {
    var parent = Rand.NextItem(winner);
    // do crossover    
  }
  if (Rand.NextDouble() < addSynapse)
  {
    // add synapse
  }
  // etc
}

Let's try to make everything slightly more extensible and fit for the research process.

We'll define our strategy as:

public delegate Genome MutationStrategy(Genome source, Genome parent,
  Context context);

where the Genome is just genocode, and Context class contains population-specific properties like PopulationAge or JiggleFactor.

Given that, we can cleanly define our strategies in C# like this:

public static Genome AddSynapse(Genome source, Genome parent, 
  Context context)
{
  // Rand is a class from Lokad Shared that makes it easier
  // to use various random generators
  var input = Rand.NextItem(source.Neurons).Index;
  var output = Rand.NextItem(source.Neurons).Index;
  var param = Rand.NextDouble();
  var newConnection = new SynapseGene(input, output, param);
  return Genome.AddConnection(source, newConnection);
}

public static Genome FastestWins(Genome source, Genome parent, 
  Context context)
{
  if (source.Synapses.Length < parent.Synapses.Length)
    return source;
  return parent;
}

or even reuse one strategy in another:

public static Genome RemoveSynapse(Genome source, Genome parent,
  Context context)
{
  var length = source.Synapses.Length;
  if (length > 1)
  {
    var idx = Rand.Next(length);

    return Genome.DropConnection(source, idx);
  }
  return FastestWins(source, parent, context);
}

Obviously, you could also create parametrized strategies as well.

Then these strategies could be combined together (with probabilities of happening) like this:

// Tuple is a class from Lokad Shared that makes it more
// simple to bind values together
var chances = new List<Tuple<int, MutationStrategy>>();

chances.Add(5, Strategies.AddSynapse);
chances.Add(10, Strategies.RemoveSynapse);
chances.Add(20, Strategies.DadWins);
chances.Add(10, Strategies.MutateSynapse);
chances.Add(20, Strategies.MutateNeuron);
chances.Add(5, Strategies.AddNeuron);
chances.Add(20, Strategies.Cross);

var strategies = CreateRoulette(chances);

where CreateRulette simply creates array of strategies, where each strategy has N number of entries (thus the probability of being applied is Pi = Ni/Sum(Ni)):

public static T[] CreateRoulette<T>(IEnumerable<Tuple<int,T>> source)
{
  return source.SelectMany(tuple => 
    Enumerable.Repeat(tuple.Item2, tuple.Item1)).ToArray();
}

With that we can apply random strategy to every item in the population pool like this (random item from the winners collection is being picked as the primary parent):

population = population.Convert(g =>
  Rand.NextItem(strategies)(Rand.NextItem(winners), g, context));

New .NET 3.5 features make wonders to these old C# algorithm implementations, do not they?

As the NeuroEvolution series go on, we'll see if it is possible to make it even more simple to write these machine-learning heuristics that leverage the latest technology.

PS: .NET F# can make wonders to the performance of these algorithms by making them as fast as pure C. Check out the latest update to the previous post for details.

F# Has Better Performance than C# in Math

2009-01-06T10:35:38Z

As it turns out algorithms coded in F# code might have much better performance, compared to the ones in C# code.

Below you will find F# version of optimized sigma-comparison algorithm from the previous post.

Compared to the C#, this .NET code:

executes sigmoid1 benchmark in 588.8ms instead of 3899,2ms
executes sigmoid2 (LUT) benchmark in 156.6ms instead of 411.4ms

You'll see below that this performance of F# is quite close to the performance of the similar implementation written in C.

Here's the F# code:

#light

let Scale = 320.0f;
let Resolution = 2047;

let Min = -single(Resolution)/Scale;
let Max = single(Resolution)/Scale;

let range step a b =
  let count = int((b-a)/step);
  seq { for i in 0 .. count -> single(i)*step + a };

let lut = [| 
  for x in 0 .. Resolution ->
    single(1.0/(1.0 +  exp(-double(x)/double(Scale))))
  |]

let sigmoid1 value = 1.0f/(1.0f + exp(-value));

let sigmoid2 v = 
  if (v <= Min) then 0.0f;
  elif (v>= Max) then 1.0f;
  else
    let f = v * Scale;
    if (v>0.0f) then lut.[int (f + 0.5f)]
    else 1.0f - lut.[int(0.5f - f)];

let getError f = 
  let test = range 0.00001f -10.0f 10.0f;
  let errors = seq { 
    for v in test -> 
      abs(sigmoid1(single(v)) - f(single(v)))
  }
  Seq.max errors;

open System.Diagnostics;

let test f = 
  let sw = Stopwatch.StartNew(); 
  let mutable m = 0.0f;
  let result = 
    for t in 1 .. 10 do
      for x in 1 .. 1000000 do
        m <- f(single(x)/100000.0f-5.0f);
  sw.Elapsed.TotalMilliseconds;

printf "Max deviation is %f\n" (getError sigmoid2)
printf "10^7 iterations using sigmoid1: %f ms\n" (test sigmoid1)
printf "10^7 iterations using sigmoid2: %f ms\n" (test sigmoid2)

let c = System.Console.ReadKey(true);

And the output (Release compilation against F# 1.9.6.2 CTP with no debugger):

Max deviation is 0.001664
10^7 iterations using sigmoid1: 588.843700 ms
10^7 iterations using sigmoid2: 156.626700 ms

Chances are that the performance of sigmoid2 is better than that, but I just can't figure out how to get rid of the mutable state.

Running as Mono

By the way, that's how similar (although not exact) code works out under Mono (details):

$ gmcs test.cs && mono test.exe
Max detected error using LUT: 0.1568425 %
1000000 iterations using Sigmoid1() took 3591.858 ms
1000000 iterations using Sigmoid2() took 247.561 ms

Running as C

C is supposed to be really close to metal and highly efficient. Let's check out how it works out for this algorithm.

Running C implementation of the code (developed by Henrik Gustafsson) yields following results:

Max deviation is 0.001664
10^7 iterations using sigmoid1: 628 ms
10^7 iterations using sigmoid2: 157 ms

Surprisingly enough, the performance is almost the same as F#. So F# must be doing really good job here.

Caveat: I've been using win32 compiler to get the binaries. 64 bit might improve the performance a bit. I'll update the article if it does.

Summary

So it turns out that F# compiler creates code that is 2-6 times faster for the math code, compared to C# (while the output is still .NET compatible). And this F# code has performance close to the one of the C code.

All this makes me wonder, if it is worth switching to F# for the core NeuroEvolution code. Stay tuned for the series.

Caching Activation Function Is Not Worth It

2009-01-05T14:18:01Z

Let's continue with our NeuroEvolution series.

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil
© Donald Knuth

The statement above applies even to seemingly hi-tech areas like forecasting, data mining or neural networks.

Here's a simple situation.

The function below is called an activation function and it is the piece of code that eats up the most CPU time in old-fashioned neural networks:

static double sigmaActivation(double value)
{
  return 1d / (1 + Math.Exp(-value));
}

One may be tempted to optimize this "bottleneck". Can you?

Caching

One of the options was to create a complete cache of all the function arguments and outputs to save the cost of the computations. The assumption is that this table will perform better and will have reasonably small footprint.

Let's prove that 4k is a mild understatement for size of this table.

We'll use this method to create float values within the range between -10 and +10:

static float CreateRandomFloat()
{
  return (float)((Rand.NextDouble() - 0.5)*Rand.NextDouble()*20);
}

Note, that we a dropping number of values to be hashed by a couple of orders of magnitude here (normally synapse outputs are double and they can easily get out of the (-10;+10) range.

public static void Main()
{
  var hash = new HashSet<float>();

  ThreadStart a = () => {
    while(true)
    {
      hash.AddRange(Range.Create(100, i => CreateRandomFloat()));
    }
  };

  var thread = new Thread(a);
  using (new DisposableAction(thread.Abort))
  {
    thread.Start();

    do
    {
      Console.WriteLine("Press Esc to quit or any other key to poll hash");
      var pureSize = hash.Count*sizeof (float)*2;
      Console.WriteLine("Pure table size is {0} Mb", pureSize/1.Mb());

    } while (Console.ReadKey(true).Key != ConsoleKey.Escape);
  }
}

In the code snippet above we simply launch secondary thread to look up for new floats and put them into the HashSet. The HashSet will obviously keep only unique values.

Then, whenever user presses non-ESC key, we output current raw size of our imaginary look-up table.

After running this code for 20 seconds I've already hit 250 megabytes, and it kept growing.

Now, given the size of that thing and the amount of index walking that has to be done, it does not really make a lot of sense to use hashing, does not it?

And even if it would have a small performance improvement, I'd personally still stay away from this optimization, since the increased code complexity is just not worth it.

Lookup Table

Another possible way is to use lookup tables to break the input into a set of predefined intervals and then output some rough estimation instead.

Unfortunately, this option does not work for me in some situations (especially when using NEAT algorithm derivatives for complex tasks), since this approach messes up the search space for the training algorithm (by introducing local extrema all over the place) and makes it even more CPU intensive in the long run (also lowering the probability of success).

But it might work for your scenario. Here's the snippet posted by Henrik Gustafsson (with some performance tweaks). And kudos go to him for setting me straight on the lookup tables.

const float Scale = 320.0f;
const int Resolution = 2047;
const float Min = -Resolution/Scale;
const float Max = Resolution/Scale;

static readonly float[] _lut = InitLut();

static float[] InitLut()
{
  var lut =  new float[Resolution + 1];
  for (int i = 0; i < Resolution + 1; i++)
  {
    lut[i] = (float) (1.0/(1.0 + Math.Exp(-i/Scale)));
  }
  return lut;
}

static float Sigmoid1(double value)
{
  return (float) (1.0/(1.0 + Math.Exp(-value)));
}

static float Sigmoid2(float value)
{
  if (value <= Min) return 0.0f;
  if (value >= Max) return 1.0f;
  var f = value*Scale;
  if (value >= 0) return _lut[(int) (f + 0.5f)];
  return 1.0f - _lut[(int) (0.5f - f)];
}

static float TestError()
{
  var emax = 0.0f;
  for (var x = -10.0f; x < 10.0f; x += 0.000001f)
  {
    var v0 = Sigmoid1(x);
    var v1 = Sigmoid2(x);

    var e = Math.Abs(v1 - v0);
    if (e > emax) emax = e;
  }
  return emax;
}

static double TestPerformancePlain()
{
  var sw = new Stopwatch();
  sw.Start();
  for (int i = 0; i < 10; i++)
  {
    for (float x = -5.0f; x < 5.0f; x += 0.000001f)
    {
      Sigmoid1(x);
    }
  }

  return sw.Elapsed.TotalMilliseconds;
}

static double TestPerformanceOfLut()
{
  var sw = new Stopwatch();
  sw.Start();
  for (int i = 0; i < 10; i++)
  {
    for (float x = -5.0f; x < 5.0f; x += 0.000001f)
    {
      Sigmoid2(x);
    }
  }
  return sw.Elapsed.TotalMilliseconds;
}

static void Main()
{
  var emax = TestError();
  var t0 = TestPerformancePlain();
  var t1 = TestPerformanceOfLut();

  Console.WriteLine("Max detected deviation using LUT: {0}", emax);
  Console.WriteLine("10^7 iterations using Sigmoid1() took {0} ms", t0);
  Console.WriteLine("10^7 iterations using Sigmoid2() took {0} ms", t1);
  Console.ReadKey(true);
}

Here are the results on my machine (relase mode, no debugger attached):

Max detected deviation using LUT: 0,001663984
10^7 iterations using Sigmoid1() took 3899,1979 ms
10^7 iterations using Sigmoid2() took 411,4441 ms

Keep in mind, that increasing precision will not necessarily improve the overall performance, since it will result in larger lookup table that has lower chance to fit into the CPU cache.

By the way, from my experience even switching from double to float could be enough to turn training some complex model task from hard to unfeasible.

That's it for now. The series on NeuroEvolution will definitely continue till they hit Cloud Computing. Stay tuned.

Update: next post shows that F# version of this algorithm has better performance.

PS: Range.Create, DisposableAction, 1.Mb and other shortcuts come from the Lokad.Shared.dll helper library that is used in this snippet.

PPS: you may also want to check Some performance issues and caveats of using LINQ in math code.

On AI, Neuro-Evolution and Azure

2008-12-22T03:50:34Z

One of the topics that I've never covered in this blog is about developing data-mining and business analytics applications. Especially, the analytics part (which happened to have popularity with terms like Artificial Intelligence or Neural Networks) which is one of the most curious implementation fields in the area of software development.

If you are unfamiliar with the subject but are really interested about it, then I recommend you to have a look at the SharpNEAT implementation. The C# architecture of the solution is far from representing efficient development approach (that's the inseparable feature of scientific projects) but some concepts behind are really nice.

In short, this project leverages neural networks (these were a hype not that much time ago) with augmenting topologies to solve tasks of forecasting and machine learning. The network "training" is done via the evolutionary (genetics) algorithm.

The augmenting topologies part is one of the key features of the project. It is about letting the networks to "grow" more complex during the training process. This is much better than simply changing the synapse weights as it allows to adapt the system to the complexity of the solution (just do not forget about the over-training problem).

Obviously such approach requires the introduction of some new heuristics to the evolutionary algorithm like segmentation of the species into the pools (mixing together networks with different topology will be just a waste of CPU) or introducing the pruning phase to "compact" existing networks that are too large.

If we compare this approach to the traditional statistical learning:

it works better, but nobody can really tell how the models work (black-box situation);
it allows to capture really complex multi-factor dependencies of the nonlinear nature;
it works with the incomplete or noisy data;
less human hours are needed to actually create and update analysis and forecasting models;
it makes development more fun.

One of the major problems with this neuro-evolutional approach lies within the analogy road. Scientists get way too stuck with this neural-networks concept from the Mother Nature to see the development opportunities of the flexibility and technology. Well at least they like to think they are close to real world because these networks do solve real-world problems (although they really are just non-deterministic brute-force algorithms with some slight optimization of the search space).

However, building a full feature set for the proper real-world analogy will require at least:

introduction of the proper electro-chemical reactions with the mediators in an asynchronous and continuous manner;
introduction of the Glia (networks are not just about neurons and synapses, you know);
delivery of the quantum computers into the mass-production.

Fortunately, we do not have to stick to these concepts and can play directly with the development-pure things like mathematical interpretators, model ensembles or evolving functions. New technologies like Windows Azure (we are interested in the Cloud Computing part) or Microsoft Accelerator Research Project (.NET library for delegating some computations to your GPU) make it more affordable.

Side effect is that models are more flexible, leverage CPU more efficiently and are more fun to develop.

We'll see how this research topic on non-statistical learning will go further. Stay tuned.