What’s in a search?

Last week I asked you to investigate the effect of the number of generations on the discovered solution. Setting the number of generations to 20 might give an output something like this:

Generation 0 best fitness: 272
Generation 1 best fitness: 278
Generation 2 best fitness: 278
Generation 3 best fitness: 294
Generation 4 best fitness: 297
Generation 5 best fitness: 317
Generation 6 best fitness: 317
Generation 7 best fitness: 334
Generation 8 best fitness: 334
Generation 9 best fitness: 337
Generation 10 best fitness: 337
Generation 11 best fitness: 337
Generation 12 best fitness: 350
Generation 13 best fitness: 350
Generation 14 best fitness: 350
Generation 15 best fitness: 350
Generation 16 best fitness: 350
Generation 17 best fitness: 350
Generation 18 best fitness: 350
Generation 19 best fitness: 350
Generation 20 best fitness: 350

As you can see, the fitness stops increasing (‘converges’) after 12 generations — but why does this happen?

Well, with selection and crossover being the only search operations in our GA, we only have a very limited gene pool to search. What’s worse, as the GA is iterating from one generation to the next, the search space shrinks. And after a while, the entire population will become exact clones of one another. At this stage the selection and crossover operations don’t actually do anything!

You may have also noticed that the GA search isn’t exhaustive — it won’t always discover the most optimum solution to the problem like a brute force method will. This is also partly down to the limited gene pool. The optimal solution will only be discovered if two criteria apply: the initial random population contains that magic set of genes, and they’re not lost in the crossover process. Quite a small chance of success, then.

In order to fix these two issues, we need to introduce the final weapon in the GA’s arsenal: mutation.

Mutating the search

In the theory of natural selection, forward leaps in fitness can only be achieved by a chance change in an organism’s genes. These genetic mutations may have allowed the first fish to breathe air, or the first mammals to walk upright — sometimes even spawning entirely new species.

In GAs, mutation is implemented by altering a few genes in a chromosome, based on some random chance. So far, we’ve looked at binary chromosomes — chromosomes containing zeros and ones — and for these a simple mutation function can be implemented like so:

Since mutation has the chance to result in a worse solution, it is usually implemented with a sense of elitism, where the best performing chromosome is not mutated:

Evolution and balance

What’s really happening with mutation is that we’re adding some randomness back into the population in order to keep variety in the search space, and potentially explore new spaces that weren’t in the initial population or have been lost over the generations. However, as with many things in AI, mutation isn’t a magic bullet. The GA will be sensitive to the balance between the population size and the mutation chance.

The following table shows this in action:

The larger the population size, the smaller the mutation chance should be. In the above example, a population of 10 got the best result with a mutation chance of 0.03, 20 worked best with 0.01 and when the population was 50 a mutation chance of 0 was the best.

Convergence

That’s it for this week! We’ve covered mutation and finished our implementation of a GA. The full code for the GA is on our GitHub.

We’re going to be taking a break for a little while on Code of AI, while I do some genetic evolution of my own (I’m having a baby). So be sure to subscribe to our mailing list here or give us a follow to stay up to date and receive updates on our latest posts. Please feel free to send us some feedback on what you might like to learn when Code of AI returns later this year!

Enter the Mutant: Genetic algorithms, part III was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

The fitness function

As any Pokémon trainer knows, you need to build your Pokémon’s experience to make them evolve and become stronger. In GA terms, a Pokémon’s experience in battle would be known as its fitness. More generally, we can measure the fitness of any chromosome with a problem-specific fitness function. For instance, here’s my fitness function for the knapsack problem:

We first create a phenotype solution out of the chromosome, and then calculate the fitness based on weight and value. The more value we have in the knapsack, the higher the fitness.

The evolutionary process

Natural evolution is a process that happens among a population of entities. If you really want to be the very best, one Pokémon in your roster just won’t cut it — you need a team of Pokémon, each with their own unique abilities. In a GA, having a number of chromosome candidates to search your space will lead to a better result, faster. In the below function, we create a population of chromosomes by simply making a list of lists:

Only the fittest members of this population will be able to survive to the next generation. This is known as selection. First, the entire population is ranked by its fitness scores, and then a certain ratio (50% in this example) of the population are selected.

One part of evolution that Pokémon conveniently leaves out is exactly how genes are passed down from one generation to the next (NSFW: when a mummy and a daddy Pikachu love each other very much…). In GAs, we simplify the act of creating ‘children’ down to mixing genes, in a process known as crossover. We take two parents and create a child by mixing the chromosomes together:

This is one of the main search operations in a GA (there’s another one, but we’ll cover it next time). The intuition behind this is that by mixing chromosomes together, we can explore the search space in directions we already know work well.

Finally, the resulting children from the crossover process are added back into the population, replacing the rejected chromosomes, and the process continues. The loop of selection and crossover is then repeated for multiple generations.

If you run all the above code snippets (also available as a single script on our GitHub), you should notice fitness improving over time.

Next generation

That’s it for this week! We’ve covered the process of a GA’s evolution from population, to fitness, selection and crossover. I have a couple of challenges for you that won’t endanger your survival:

1. What happens when you increase the number of generations in the example code (to e.g. 20)? Why do you think this happens?
2. Compare the execution time and results of the previous week’s brute force approach and this week’s GA approach. Run them each a few times, changing the number of items. What do you notice about:

• The discovered solutions?
• The execution time?

As always, you can find the source code for all the above examples on our GitHub.

To begin your AI-coding training at day one, go here. And give us a follow to receive updates on our latest posts.

Selection, Crossover, I choose you! Genetic algorithms, part II was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Searching for… something?

GAs fall into the search or optimisation categories of AI, where, generally speaking, ANNs can’t be used. Sure, they can be used as part of a search solution (classifying web pages based on their content, for instance). But the process of conducting a search or optimising a set of parameters is not one that lends itself well to the architecture of an ANN.

This is because ANNs are essentially statistically-driven input-output mapping machines. Put in an image and the ANN can tell you if it’s a cat or not (most likely yes if you found the picture on the internet). But try to ask an ANN to find a cat on the internet and you get stuck. What are the inputs/outputs? How will you train it? This problem becomes worse when the problem is so ill-defined that you’re not exactly sure of what you’re looking for (finding that perfect cat gif for your team’s #random channel on Slack), or when the number of options to search through grows unreasonably high (my Google search for ‘cat’ just returned 7.5 billion results, which is more than the population of the planet).

The knapsack problem

Now the cat’s out of the bag, let’s illustrate the issue with a classic example of a search/optimisation problem: the knapsack problem.

The knapsack problem goes like this: imagine you’re a travelling salesperson who carries all of your wares in your trusty knapsack. Naturally, you want to make sure that you make the most money you can that day by taking your most valuable goods on your round. But you have a problem — you can only carry so much or your bag will break! Every morning, you need to find the best combination of items to put in your bag that will maximise the value you carry, but not go over the bag’s capacity so it breaks.

Let’s begin tackling this problem by revising a couple of AI search terms we covered way back at the start of this Code of AI series:

• Search space — abstract parameters constraining a search.
• States — positions or sets of conditions in a space.
• Goal state — a desirable outcome, or solution.

The search space in the knapsack problem is every possible combination of items to put in the bag. Each item has an associated value and weight, and the bag itself has a maximum capacity. A single state is one of those combinations of items in the bag, and the goal state is the one single combination that maximises value without going over the bag’s capacity.

A brute force solution

The knapsack is quite a simple problem to solve with a brute force method. In this code snippet we iterate through all the possible combinations of the items in the bag and test each one for its value and weight.

Running this code shows that we do indeed find a solution, and for the 10 items in this example we find the solution quite quickly. But what happens if there are more items to search through? With 10 items we only need to search through around 1000 combinations, and it takes about 7ms on my machine. But with 20 items the number of combinations grows to around 1,000,000 and takes 2.5 seconds. Just five more (25) items makes around 33 million combinations and takes around 2 minutes to search. This trend shows that the knapsack problem has exponential (O(2^n)) complexity, which means that it quickly becomes impractical for larger values of n.

GAs: a different kind of search

Let’s think of a better way to search the vast space of the knapsack problem. The problem we’re facing lies in the exponential rise in the number of combinations when we increase the number of items. What if, instead of searching through every possible combination of items in the bag, we have a fixed number of states, evaluate their value, and then change them in some way to explore the search space.

This is exactly the intuition behind a GA. Inspired by natural evolution — the process by which a simple organism becomes more complex and better adapted to their environment over time through natural selection — GAs evaluate a set of states (a population in GA terms) for their fitness and evolve the best solutions (“fittest”) in the next generation. Eventually, the overall fitness of the population will rise and a best-fit solution to the problem will be found.

We’ll get more into the mechanics of the GA search process next time. For now, let’s focus on a few fundamental concepts in GAs, all of which are inspired by natural evolution: genes, chromosomes, phenotypes and fitness functions.

You can think of a phenotype as analogous to a search state in general AI terms. In biology, you are a living phenotype, and your genes define how you appear. If you have the brown-eyed gene then your phenotypic eyes will be brown too. Similarly in a GA, a gene is an abstract parameter that encodes one aspect of the phenotype. A chromosome is the collection of genes that together fully represent the phenotype in an abstract way. Finally, the fitness function is an application-specific evaluation method that creates a phenotype from a chromosome and computes how good the solution is.

The knapsack as a chromosome

In our knapsack example we’ve already said that a single search state — a phenotype — is one possible combination of items in the bag. Encoding this into a chromosome is as simple as creating a binary list where the length is the number of possible items to put in the bag. If a single gene takes a value of one, it’s included in the bag.

To illustrate this, here’s some example code that creates a random chromosome and converts it into a phenotype.

It’s in the bag

That’s where we’ll leave it for this week. We’ve covered some of the limitations of machine learning and ANNs, and the need for a wider perspective on some AI problems. We also introduced genetic algorithms as an alternative way to search a complex space, and some fundamental concepts in GAs, genes, chromosomes, phenotypes and fitness functions.

I’ve provided some code for a knapsack problem chromosome. If you’re up for a challenge, can you take some code from the bruteForceKnapsack function (above), and create a fitness function to evaluate a single chromosome?

As always, you can find the source code for all the above examples on our GitHub.

To begin your AI-coding training at day one, go here. And give us a follow to receive updates on our latest posts.

Intelligence is in my genes: Genetic algorithms, part I was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Clever Hans — a machine learning fable

Before we dig in to some theory, here’s a true story about a horse named ‘Clever Hans’. As his name suggests, Hans wasn’t like other horses. His owner Wilhelm soon discovered that he could be trained to read basic equations on a chalkboard and tap the correct answer with his foot. This amazed Wilhelm, who promptly showed off Hans all across Germany. However, it was soon discovered that, unbeknown to Wilhelm, Hans only appeared clever, and couldn’t really do maths. Hans’ cleverness hinged on his ability to have an up-close, unobstructed view of the person who knew the correct answer. Take that away, and his accuracy plummeted to zero. Hans was just very good at reading people’s body language, which indicated to him to stop tapping his foot.

So, what does this tell us about machine learning? Just like Hans’ owner Wilhelm, as model trainers we can’t always be sure of exactly what our model has learned from the data. The model may appear to perform superbly in training, but then makes terrible predictions about unseen data in a production environment. This is currently a hot topic within the machine learning community (I even attended an academic conference on the subject). If you’d like to find out more you can check out this paper.

How to be ‘too’ fit

Let’s take the following example. Here we have a dataset containing two classes represented by red crosses and blue circles.

We’d like to train a model that can classify the data into the two classes. After training you might be chuffed to find out that the model scores 100% accuracy on this dataset. But when you feed it some new data, the accuracy might drop completely — a classic sign of overfitting.

The classification boundary our model is using might look something like this:

Here you might already be able to see the problem. The 100% training score is achieved because the model has tightly fit a boundary line, but does not appear to have discovered the general trend in the data. A better generalised model might draw the line more like this:

Sure, the training accuracy of this model will be lower (we have two mistakes in blue and four mistakes in red), but the model has discovered a general pattern that will ensure better accuracy on new data.

Cross-validation to the rescue

To summarise, we need to keep two things in mind when evaluating our trained model. The error on the training set will only give us part of the story. Only through evaluating on a different set of ‘unseen’ data are we able to say that the model is performing well. This is what cross-validation sets out to achieve.

In cross-validation, the dataset is split into chunks. A certain proportion — let’s say 80% — is used for training the model as usual. The remaining data (20%) is not used for backpropagation, but instead is used to keep track of a test error. When this error stops improving (or in most cases, gets worse), it’s a sure sign that we’re overfitting — so we can stop training at that point.

Let’s see what that looks like in code:

Fitter, happier, more productive

That’s it for this week. We’ve covered the concept of overfitting and how to avoid it with cross-validation.

The cross-validation implementation I’ve introduced in this post is a very basic one — it’s far more common to train multiple models (usually up to ten) with a different chunk of test data each time. This is known as k-fold cross-validation. You can try extending the above example into a k-fold cross validator if you’re up for it.

As always, you can find the source code for all the above examples on our GitHub.

To begin your AI-coding training at day one, go here. And give us a follow to receive updates on our latest posts.

You’re fit and you know it: overfitting and cross-validation was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

What is immersion?

Immersion is a state of mind. It’s what happens when you lose the sense of your physical self in an artificial simulation, experience, or fiction, so the simulation appears real and you momentarily forget about the ‘real’ word. The focus of your consciousnesses shifts from the ‘real’ world to the artificial one presented to you. It doesn’t only happen in VR, but it might happen when reading a book or watching a film, or even (for me) when performing a difficult cognitive task, like writing some code. Put another way, in a state of immersion your senses of presence and attention shift into the virtual world, and the more you believe the world you’re in, the more your brain convinces you that what you’re seeing is real.

When it comes down to it, it’s hard to specifically define exactly what causes immersion. If you’re scientifically inclined like me, you’ll look to the existing body of research in the area. You’ll then find that there’s a substantial amount of research out there, but no real consensus on the specific components that lead to an immersive experience. And when even the academics can’t agree, you know you’re on shaky ground.

Staffan Björk and Jussi Holopainen’s four categories of immersion, as defined in their excellent book Patterns In Game Design, seems like an appropriate point of departure. It’s not exhaustive, but it’s still a practical way to think about immersion specifically in games and VR.

Björk and Holopainen’s categories are:

Sensory-motoric immersion

This occurs when you perform actions with your hands or limbs and get feedback through all of your senses — sight, sound and touch — and even smell and taste!

Spatial immersion

When the simulated world is perceptually convincing, you are said to feel spatially immersed, which directly affects your sense of presence. There are subtle nuances to this, including the scale and environmental cues of the world (such as sound).

Cognitive immersion

This occurs when you’re focused on a specific task that requires mental exercise — it’s perhaps the most common form of immersion, as most people experience it when learning something new.

Emotional immersion

This is another common immersive state, often induced when you watch a film or read an engrossing book. It occurs when players become emotionally invested in the experience.

Why is immersion so important for VR?

Many people think that the act of simply having content in VR guarantees a magical boost in ‘immersion’, but this is only true to a certain extent. While it’s definitely easier to achieve a state of immersion in VR, immersion itself is actually a fickle beast that’s difficult to maintain for a longer period of time.

During a VR experience, your senses are bombarded with an overwhelming variety of conflicting information. Usually, players will have most of their senses covered; their eyes enclosed by the headset, their ears in some kind of headphones, and their hands holding one or more controllers. Some companies add more bells and whistles to this setup, but that’s beyond the typical VR rig.

Even with this default sensory-motoric immersion, if something happens in the ‘real’ world, or the simulated experience conflicts with your senses, then the level of immersion can come crashing down — often with nasty side-effects such as disorientation, confusion and motion sickness. Not the virtual roller-coaster ride you signed up for.

As VR developers we can’t fully control the external rigs and environment our players use, so instead we rely on in-experience tricks to playfully coax the user into a deeper sense of immersion. The more immersed a user, the more engaged they’ll feel, and the less likely they are to experience cognitive dissonance between the real and simulated worlds.

Ultimately though, if the experience is deeply immersive, your players will feel happier and find themselves continuously returning to satisfy that need for ‘“just a bit more”. This continued demand is essential to increasing the widespread adoption of VR.

How to increase user immersion with (mostly) audio

As an audiophile, it seems sensible for me to focus on ways to increase the feeling of immersion with only audio techniques. I often feel that audio generally doesn’t receive the attention it deserves, probably because, like the best film soundtracks, if the audio is working well it shouldn’t be noticeable.

Well-implemented audio seamlessly blends into the experience and feels like the real thing. But when this goes wrong it, it’s horrifyingly bizarre — something happens in your brain that most people can’t put their fingers on, they just know it feels ‘wrong’. To avoid this uncomfortable disconnect, a few simple things can be implemented.

Use spatial audio for diegetic sounds…

Diegetic sound is a term stemming from film — it basically means the sounds made by real-world objects, characters, environments etc. When you hear sound in the real world, your brain is doing a lot of complicated stuff to figure out the direction and distance of the sound When this ability is taken away it creates an extremely disorienting effect. Most people won’t be able to pinpoint what’s wrong — the world will just feel odd and fake. This problem boils down to a lack of spatial immersion. However, by using spatial audio techniques you can eliminate this for your players.

Consider film once again. Lack of spatial immersion was also a problem for film-goers, which was the reason for the invention of surround sound. Even with a huge screen in a dark room, hearing audio out of two fixed speakers was a sure-fire way to remove yourself from the experience. The inventors of surround sound placed more speakers around the audience, so that sound actually plays behind you if a character is out of shot. This problem exists in VR, except we can’t just add more speakers to the headset… or can we?!

You don’t need a sci-fi-looking piece of technology from an advanced civilisation to solve this problem. Spatial audio is a tech that’s been around for quite some time in games, and is really taking on a life of its own in VR titles. With spatial audio, sound sources can be placed into the 3D world, and the engine figures out how to manipulate these sounds so they sound like they’re coming from that spot, even through a stereo mix. If you have ambient sound effects in-game, you should definitely spatialise them for their full effect.

…and ambisonic audio for non-diegetic sounds

Spatial audio is great for diegetic sounds that are visible on the screen, such as a babbling brook or a gunshot, but when it comes to non-diegetic sounds — like the game’s soundtrack — we run into another issue. It’s often undesirable to have the music coming out of fixed points in the 3D world; instead, the player should feel enveloped by the music. However, if the music mix is fixed (e.g., the guitar is always in front of you, no matter where you turn), then this can cause feelings of discomfort that lead to a break in sensory-motoric immersion.

To tackle this, we can use ambisonic audio. This is where we have a set of points around the listener in 3D space, that are relative to the listener rather than in absolute positions. The 3D points move with the listener, but changes in the mix can be heard when the player turns around or moves their head. This simulates the experience of being in a real-life environment, almost as if you were at a real-life concert standing in the center of an orchestra. Bravo!

Ease the learning curve with UI audio

One of the most painful, immersion-destroying experiences in VR for players is learning a complicated control scheme. Most players will struggle with pressing more than one button at once, especially if it’s an unnatural gesture. This is an area where VR actually shoots itself in the foot a little bit. Since players can’t see their hands, it’s even harder to learn the new controls.

The control scheme obviously affects sensory-motoric immersion, but also has a strong effect on cognitive immersion. Somewhat counter-intuitively, hard-to-learn controls don’t lead to cognitive immersion, but actually hinder it. This is because, in order to feel cognitively immersed, you also need to feel in control of your own actions and therefore get less frustrated!

But don’t fret, the answer once again lies in the audio. Having simple audio cues that respond to the user’s actions is a method of positive-reinforcement. It aids cognitive immersion, reducing the frustrations of not knowing if you’re even doing the right thing or pressing the right buttons.

An excellent example of well-executed UI audio in VR is Funomena’s Luna. A very simple control scheme, coupled with a few effective gong sounds providing audio feedback, eases the player into the controls, so they feel more engaged from the outset.

Use (deep) adaptive music for your soundtrack

We all know that music is amazingly powerful at conveying emotions, which you’ve no doubt noticed in the real world everywhere you turn. When was the last time you watched an advert on TV with no music, for instance? In VR, though players have their own agency and behaviours — they can choose where to go and how to act. This means that if we want to increase their emotional immersion, we need to dynamically respond to what they do with the music. This is called adaptive music, and is fundamental to interactive media.

The work I do has focused on developing a new way to score interactive media by deepening the adaptive music experience with the help of AI. In our research we’ve found that adaptive music can boost immersion by 30%, most likely due to the increased emotional immersion.

Sound off

So, there are some textbook suggestions for how to improve immersion in VR. Next time you hear the phrase “immersion multiplier”, try to ask yourself which one of the four categories it addresses.

How to increase user immersion with (mostly) audio was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

A quick side note before we begin: from this week forward we’ll be publishing a new Code of AI post every two weeks instead of every week. This will hopefully give me enough time to deeply address some more complex concepts and models, and also give you enough time to digest them.

What are hyperparameters?

We left off last week with an exploration challenge — I asked you to tweak various parameters of our neural network and its training: the network size, the amount of training data and the learning rate. These parameters (and others) are generally referred to as hyperparameters. But what does that mean exactly, and what’s the difference between a hyperparameter and a normal parameter?

To understand this, let’s remember what we said in the last post about what we mean when we say that our machine learning model is learning. This is a process of optimising a model by adjusting it’s parameters to minimise the error. With an ANN, the model is a bunch of neurons and connections, and the parameters are the connection weights. The weights are a set of parameters that are internal to the model. We don’t directly set them from the outside, and their value is set by the training algorithm. These are called model parameters.

Hyperparameters are parameters that we do have ‘control’ over as machine learning programmers. Depending on the model you’re using, you’ll have a number of different hyperparameters to tweak — but for an MLP, you only really have the abovementioned ones to play with.

Let’s now explore how these hyperparameters work together. For each one we’ll l train ten different networks and use the average error as an indication of which one performed best. “Why train ten different networks?”, I hear you ask. Well, since each MLP is initialised with random weights, sometimes the network will take longer to find an optimal solution or, in some cases, never find a good solution at all. Running the training multiple times reduces the chance of this happening. (This idea is similar to a concept known as cross-validation which we’ll cover in a later Code of AI post.) For now, remember this: always train multiple models before you stick with a hyperparameter choice.

Network size

The network size — the number of hidden layers and how many neurons there are in each layer — is a perfect example of a hyperparameter which has a direct impact on the model parameters. If a multilayer perceptron has one input, one output and one hidden layer with three nodes, we know that the network has six (1x3 + 3x1) trainable weights. However, if we add a second hidden layer of three neurons, we know that the network has 15 (1x3 + 3x3 + 3x1) trainable weights. As you add more nodes and more layers, the number of parameters can grow faster than you might expect!

In this next code snippet we’ll explore a number of different network sizes and report the error for each size.

The results will look something like this. The first number refers to the hidden layers; the second is the number of model parameters and the last number is the average error.

As you can see, for our toy dataset the network size doesn’t really make too much of a difference. Although there is an important lesson here: sometimes a simpler architecture is better. Or, to put it another way, you should optimise the size of your network to be the smallest network possible that achieves your goal. You can see this in the final example, where the error is actually bigger for the largest network. Adding more layers and nodes increases the complexity of the network, which not only makes it more difficult to train, but also increases the RAM and CPU requirements for the model. Is one more layer really worth that 0.001 improvement? You be the judge — but only if you’re 99.999% sure.

Amount of training data

One of the easiest ways to play with a hyperparameter is to control the amount of data that is fed into the model during training. Simple problems like the often-used XOR function have complete datasets of every possible input and output pair, but most of the time this isn’t feasible. Instead, we have to work with a sample of data and hope that the ML model will generalise well after training.

The next snippet of code explores a range of dataset sizes and shows the results.

Even in this simple example, the trend is clear: more data = better results. I’ve lost count of the amount of times I’ve told a client, “We need more data”, or read in a research paper’s conclusion that “collecting more data may yield better results” (I think I’m guilty of that one myself).

Adding more data helps the model learn in two ways. First, it avoids the problem of overfitting, which is where the model doesn’t generalise well to new inputs — we’ll talk more about overfitting in the next Code of AI post. Secondly, it helps the model learn by giving it more backpropagation runs to do in one epoch. This means that the more data you add, the more training time you’re giving the model.

Learning rate

The learning rate is the one and only hyperparameter for our implementation of backpropagation gradient descent. There are more complex gradient descent trainers and optimisers available that have more parameters to play with, but learning rate is a simple input that controls how much to follow the gradient and adjust the weights when learning. The general rule of thumb is that bigger learning rates will learn faster, but may step over the optimal points, whereas lower learning rates will learn more slowly but may get stuck in local optima.

ML guru Andrew Ng has a great rule of thumb for how to go about optimising hyperparameters such as learning rate, called the rule of 3. Essentially, you pick a number to start with (usually 1 or 0.1 for learning rate) and then try multiplying it or dividing it by three, rounding where it makes sense, until you find the optimum. This is the approach we’ve taken in the code below:

The learning rate is an interesting hyperparameter to explore because it can greatly affect your model’s performance. Here we can see that the optimal learning rate seems to be around 0.3, but will depend strongly on the network size and complexity of the problem. Now, if only there was a learning rate hyperparameter for human brains…

Hyperparameters optimised

That’s where we’ll leave it for this week. We’ve introduced the concept of hyperparameters, and explored three hyperparameters associated with our MLPs and gradient descent training.

Next week, we’ll finally be able to train a model on some real-world data. We’ll also discuss some of the perils of overfitting and how to mitigate that with cross-validation.

As always, you can find the source code for all the above examples on our GitHub.

To begin your AI-coding training at day one, go here. And give us a follow to receive updates on our latest posts.

Jumping into hyperparameters was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

While there are lots of ways this could have been done, here’s my solution:

This new solution makes it easier to experiment with our network’s architecture (the number of inputs, outputs, hidden layers and their sizes) to see what works best for the problem we’re trying to solve. We can also create a oh-so-popular deep network, by inputting large numbers like:

This code would create an MLP instance with one input, five hidden layers — each with 1024 neurons — and one output.

Apropos propagation

Part of the elegance of ANNs lies in the fact that each layer of the network is “activated” sequentially. This can be seen in the ‘activate’ method above — data is flowing through the network in a simple for-loop, and the output from the previous layer is used as the input to the next. This is known as forward propagation. Here’s where things get really interesting — the network can learn from it’s mistakes by running in reverse, which is known as backwards propagation or backpropagation.

This isn’t a matter of just running the network in reverse, though. While forward propagation propagates the input value(s) from left to right, backpropagation propagates the error value(s) from right to left. For backpropagation to work, we need to calculate the error (a.k.a. cost or loss) by comparing the actual output with the desired output. This calculated error is what is back propagated to the previous layer(s), from right to left. The connection weights of each node are then adjusted by changing the weights to reduce the prediction error.

Training ANNs with supervised learning

For an ANN to learn with backpropagation, we need a dataset of training examples. Each example needs to be made up of the input data and the desired output for that input.

Training an ANN is an iterative process in which training data examples are presented to the network one by one, and the values of the weights are adjusted each time. After all examples get run through the network, one training epoch is finished and the process often starts again. During this phase, the ANN learns to predict the correct output, given the input examples, and, hopefully, is able to generalise the prediction to other data similar to the input examples. This is known as supervised learning (SL).

During the training phase, we pass a training example to the network and then compare the network’s calculated values of the output node(s) against the ‘correct’ values. Then, we calculate an error value. This error can then be backpropagated, and the connecting weights in the hidden layers can be adjusted, with the hope that the output values calculated next time will be closer to the correct values.

The mechanics of backpropagation

Enough theory — let’s get back to the code!

The first thing we need is an error function, since we need to keep track of the network’s performance. There are a lot of error functions to choose from, but for now we’ll stick to the commonly used mean squared error. With numpy, the implementation is pretty straight forward:

When we say that the network is learning, what we really mean is that we’re minimising this error in the network with a gradient descent algorithm. Understanding gradient descent is a little complex to explain mathematically — but essentially it’s a way we can iteratively tweak the weights in the network to reduce the error. If you’re interested in learning more about the maths behind how this works, check out this awesome explanation from 3Blue1Brown.

The magic piece of the puzzle that makes gradient descent work is the derivative of our activation function (sometimes called the prime). Luckily for us, the sigmoid function has a simple derivative:

y = x * (1.0 — x)

Using this deceptively simple code, we can take a step down the error gradient, adjust the weights in the network and improve the performance. We do this by stepping in reverse through each layer in the network, calculating the derivative of the output with respect to the input, and then backpropagating the error to the next layer. Here’s some code that does all that:

Once we have the derivatives for each layer, we can take one final pass through the network to update the weights with gradient descent. There are many versions of gradient descent you could use, but in this lesson we’ll stick to simply integrating the derivative with a learning rate, and then adjusting the weights accordingly.

Putting it all together

We now have all the components in place for backpropagation. All we need to finish our implementation is a controlling algorithm that performs a number of training epochs on some data.

Let’s start with the data by creating a toy dataset of numbers:

We’ll try to get our network to learn this simple mapping with a training routine.

When you run this code, you should notice the error decreasing with each epoch.

Epoch complete

We’ll leave it there for this week. We’ve covered backpropagation and gradient descent for training our MLPs with supervised learning and a labelled dataset. You might have noticed that the network isn’t particularly good at approximating this toy dataset we made. Next week we’ll dig into why this might be, when use our newly-acquired skills on some more realistic data.

In the meantime, I have a simple investigative challenge for you:

1. Play around with different values of the network size, amount of training data and learning rate. What do you notice about how each number affects the performance of the model

As always, you can find the source code for all the above examples on our GitHub.

To begin your AI-coding training at day one, go here.

And give us a follow to receive updates on our latest posts.

Training to train: Artificial Neural Networks, part II was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Welcome back, neurons. This week we’re introducing a new AI topic. Over the next few tutorials, you’ll learn the basic theory behind Artificial Neural Networks (ANNs) — a powerful and versatile AI model — and how to build and train one from scratch.

You could just use a library like TensorFlow to create and train a powerful, ‘deep’ ANN in a few lines of code. While handy for creating efficient ANNs, this isn’t ideal if you want to really understand the system and how to build them yourself. So let’s go deeper, and explore the wonderfully simple-yet-complex world of ANNs.

What is an Artificial Neural Network?

ANNs are vaguely inspired by the way biological brains like our own work. Our brains are made up of individual cells called neurons. On their own, these neurons don’t do that much; they can receive some electrical input and become activated with some output. But when these neurons are connected together, they exhibit higher-level behaviour that gives rise to all of our cognitive processes and abilities such as thought, consciousness and memory. While the human brain has around 100 billion neurons, ANNs use far fewer, massively simplifying matters. Even the deepest of ‘deep’ networks in use today only contain around one million neurons. ANNs simulate the behaviour of their biological counterparts with nonlinear mathematical functions that map a given input onto a desired output.

ANNs consist of the following elements:

• An input layer;
• One or more hidden layers;
• An output layer;
• A set of weighted connections between the layers; and
• An activation function for each layer (except the input layer).

Artificial neurons under the microscope

Neurons are the computational units of an ANN — its building blocks. An artificial neuron, like its biological counterpart, receives one or more inputs, adds them up and passes that sum through an activation function to produce an output.

Let’s see how this works mathematically. We have the following elements to consider:

• xk are the k input signals (from other layers);
• wk are the weights of the connections between the inputs and the neuron;
• f is the activation function

The output of the neuron is y = f(x1w1 + x2w2 + … + xkwk).

There are several types of activation functions we can use in ANNs. ReLU, tanh and sigmoid are some of the most common. For now, we’ll be using the sigmoid function, a beautiful nonlinear function, with some nice mathematical properties like differentiability and continuity:

An artificial neuron can be simply implemented like so:

Connecting the dots

Single neurons by themselves are not particularly powerful processing units. The strength of a NN becomes clear when we connect several neurons in a layered network.

ANNs consist of a number of layers. The first layer is called the input layer. Then we have at least one, but often more, hidden layers. Finally, there is an output layer. One of the simplest ANNs is called a Multilayer Perceptron (MLP). This is a type of feedforward network, meaning that the data is processed in one direction, from input to output. We start from the input nodes, moving through the hidden layers and, eventually, arriving at the output layer.

In an ANN, each connection between the layers is weighted. Usually the network will undergo a process of training, which is nothing more than iteratively tweaking the values of the weights of the connections, so that the network behaves the way you want it to. We’ll cover how to train our networks next week, but for now let’s look at an object-oriented implementation of an MLP.

Brain freeze

That’s it for this week! We learned about ANNs and their architecture, and implemented our first ANN — an MLP. Right now the network isn’t very useful, because it just produces noise. To do anything exciting, we need to train it — and that’s exactly what we’ll do next time.

In the meantime I have a challenge for you: the MLP implementation above only works with one hidden layer. Can you extend it to have any number of hidden layers that differ in size?

We’ll go through the solution to this next week, and as always you can find the source code on our GitHub.

To begin your AI-coding training at day one, go here.

And give us a follow to receive updates on our latest posts.

Thinking artificially: Artificial Neural Networks, part I was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Scrambled eggs

First, let’s look at the solution to last week’s tasks. You were asked to automatically create a Markov chain transition matrix from the famous nursery rhyme “Humpty Dumpty”.

To use this text in a Markov chain, we first need to tokenise it. This is where we split the single string of text into a list of individual words. We can do this with a simple regular expression:

Running the above code will output the following list:

Next, we can create our transition matrix by iterating through this list and updating discrete distributions for each word depending on their previous word. Here’s a function that implements the full procedure.

Finally, we need an initial distribution, which in our case is quite simple, because we know that we always want to start with the word “Humpty”.

Now that we’ve constructed our Markov chain, we can use it to generate a new version of Humpty Dumpty:

Here’s an example output from our Humpty Dumpty generator:

Humpty Dumpty sat on a great fall All the king’s horses and all the king’s horses and all the king’s horses and all the king’s men couldn’t put Humpty together again

Data wrangling

Many AI algorithms rely on creating a statistical model of some dataset. This subset of AI is what’s referred to as Machine Learning (ML) and — guess what — the Humpty Dumpty example above is already a simple application of ML. (How easy was that?).

However, most ML tasks are a little trickier — the dataset will often contain information that’s not important, or need to be cleaned or transformed in some way before it becomes useful and can be given to the algorithm. This process is called data wrangling. Often, the success or failure of many ML projects comes down to data wrangling

Machine Learning is the process of manipulating your dataset so that the algorithm does what it’s supposed to do — Me

Let’s start by looking at a simple example of data wrangling. We’ll use a dataset from the data science portal Kaggle, mousehead’s Song Lyrics dataset. This dataset contains lyrics for 55000+ songs in English. We’ll use data wrangling to count how many songs this dataset contains for a specific artist.

The dataset is in a simple CSV format, similar to a spreadsheet, and contains 4 columns:

1. Artist
2. Song name
3. Link to a webpage
4. Lyrics of the song

So to find the number of songs a specific artist has, we need to loop through the rows in the dataset, check the first column against the artist we’re looking for, and increment the song count if it’s a match.

Outro

Let’s leave it there for this week. We’ve had our first crack at machine learning, and learned how to perform some simple data wrangling to extract useful information from a dataset.

I’ll leave you with a fun challenge for next week:

1. Can you use this week’s code to read the Song Lyrics dataset, create a Markov chain for the entire discography of a single artist, and generate a new song with that Markov chain?

Good luck and, as always, you can get the source code for this week on our GitHub.

Continue your training to supreme master-level AI coding here.

And give us a follow to receive updates on our latest posts.

Sing a song of data: Markov chains, part II was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Welcome back, AI artisans. This week, we’ll continue the theme of stochastic models by implementing our own Markov chain. Before continuing, make sure you’ve warmed up by understanding the basics of probabilistic terminology, systems and some of the helper functions I covered in the previous post.

The trouble with simple distributions

Let’s consider the following sequence:

AEEAAAEAAA

At first glance, there’s not much logic to the sequence. It appears fairly random — a classic case of a stochastic process.

Just like we did in the previous post, we can create a simple, discrete distribution by counting up the As and Es and then normalising the sum. The distribution for this sequence would look something like this:

We could use this to re-generate a sequence and we might get something like the following:

AEAEAAEEAA

This seems reasonable enough at first glance; but isn’t it missing something from the sequence? It’s hard to tell with something as meaningless as As and Es, so let’s look at this more semantic sequence instead:

red flower red car red car red flower

The discrete distribution for the above sequence would look like this:

If we were to use this distribution, it’s entirely possible that we might randomly generate the following sequence:

red red car red red red car flower

Not quite what we’re looking for! What’s gone wrong here is that the simple probability distribution is not capturing any of the local structure of the sequence. In other words, the next word in the sequence depends on the current word — this dependency can’t be captured by this simple frequency distribution approach, which should only be used for independent outcomes.

Markov models

Andrey Markov was a turn of the 20th century Russian mathematician, best known for his work in differential calculus and stochastic processes. As you might’ve guessed, he’s the inventor of the Markov chain, which he first used to model alliteration in Russian literature.

Generally speaking, a Markov chain can be used to model a stochastic process where the next state is influenced by the current state, and, optionally, any number of its previous states. Markov chains belong to a wider set of similar systems, collectively known as Markov models. In a later Code of AI tutorial we’ll delve into the Hidden Markov Model, but for now, we’ll stick with the simpler Markov chain.

Markov chains have two components: an initial distribution and a transition matrix. The initial distribution is a discrete probability distribution that tells us what state to start with. The transition matrix is a set of nested discrete probability distributions, differing depending on the current state.

Let’s think of our initial ‘AE’ sequence in terms of its states. We could visualise the sequence like this:

The initial distribution in this case is easy; A and E both have equal chance of being the first state.

Now, if we are in A, we have a 60% chance of staying in A, and a 40% chance of moving to E. If we are in E, we have a 30% chance of staying in E and a 70% chance of moving back to A. We can represent that quite simply as a transition matrix with nested dictionaries:

And that’s all the data we need to represent a Markov chain!

Now, when we’re using the chain to predict or generate new values, we can sample from the initial distribution to get our starting state, and then sample again from the transitionMatrix from that point on.

Running this code gives us an output sequence very similar to what we’re after, with the added benefit that we can pick up on some dependent local structure in the sequence. And that, is a Markov chain.

Mark-off

This week, we’ve seen the limits of discrete probability distributions for modelling sequences, and how Markov chains can solve that issue by modelling probabilistic state dependencies.

I’ll leave you with a couple of tough nuts to crack for next time:

1. Can you write a Markov chain to describe the ‘red flower red car red car red flower’ sequence?
2. Can you write a function that automatically creates a transition matrix from the words of the popular nursery rhyme Humpty dumpty?

Humpty Dumpty sat on a wall

Humpty Dumpty had a great fall

All the king’s horses and all the king’s men

couldn’t put Humpty together again

3. Can you use this transition matrix along with an initial distribution to create a new remix of Humpty Dumpty?

Next time we’ll walk through the solution to these tasks (which, by the way, is your first machine learning task) and start to work with datasets.

As always, you can get the source code for this week on our GitHub.

Continue your training to supreme master-level AI coding here.

And give us a follow to receive updates on our latest posts.

They call me Mr Stochastic: Markov chains, part I was originally published in The Sound of AI on Medium, where people are continuing the conversation by highlighting and responding to this story.