This is the sixth article of my serie "automating games with python"

source
You can find on my account How I made my own python bot to automate complex games (part 1) Which explains my motivation and the game I'm automating itself. the part 2 is How to control the mouse and keyboard with python for automation
Which digs into the core functions that are needed for automation. Part 3 which talks about a wrapper that I made to easily implement image searching within your python program and how to use it : Image recognition with python.
Part 4 : Why I had to use machine learning for bypassing the anti-bot security explains why I needed machine learning and how simple image recognition was not enough. Part 5 : How to create your own dataset for machine learning is kind of self explanatory.

In my last post How to create your own dataset for machine learning we saw :

• Images are just arrays of pixels containing numbers.
• That we need to split the data in two (one for learning and one for testing).
• How to actually get these arrays.
• What is One hot encoding.

These are the important concepts, if you are not familiar with them, please read the article.

Neural networks

First of all, let's talk a bit about the general problem. Let's say we want to detect if a picture is a picture of a cat or not. To us it is very easy but when you think about it, a cat can be taken from the front, from the back, partially hidden, walking, sleeping, it can be different colors etc. It's really hard to generalize what is "a cat" when you think about it.

So how do you translate a vector (our pixels, an 1d array aka [3, 6, 8......]) into a probability ? Eg : "I'm 94% sure this image is a cat"

Inputs weights, bias and linear classifier

The input to our neural network is simply the pixels ordered as a single column array.
To make predictions we have a system of weights and biases.

A weight is simply multiplied with a pixel. there is one weight per pixel.
The bias is added to the pixel * weight multiplication (one time). This allows more flexibility and so better predictions in the end.

The intuition is that weights and biases are used to give more or less importance to the value of one pixel.

For instance to classify a boat you will give way more importance to the value of the blue pixels around the corners. Because a boat is often in blue water.

This image from Stanford's CS231 really captures the intuition :

Suppose that the image is 4 pixels long and we want to classify if it's a cat, a dog, or a ship :

For each pixel we multiply it by the category weights and add the category's bias so for instance to get the cat score you do :

0.2 * 56 + -0.5 * 231 + 0.1 * 24 + 2.0 * 2 + 1.1 = - 96.8

Now, in this simple example, the dog score is the highest, which means that the weights are not set correctly. But you get the intuition on how the weights affect the classifier.

The problem with this is that it's what is called a linear classifier. This is a very basic system that is really not that effective. Because it can't approximate complex data.

there is no notion of neural net at this level. But these concepts are the core of how neural nets actually do things.

Neurons

In a neural network the neurons plays a huge role and they are not complicated :

A neuron is simply a function that takes some input, compute it's activation function on it and outputs the result.

The activation function is the function that is applied to the input, in the simple model that we are going to use it's going to be the sigmoid function. It's a very simple mathematical function :

source : Wikipedia

See what we did above with the weights and everything ? It can actually be seen as a one neuron neural network :

source : my "awesome" paint skills, the cat : pexels

That little sigma sign in the middle of the neuron (the circle) is the sigmoid activation function.
As you can see, the neuron is fed the result of the equation :

a = W.T*X + b (a is a real number)

side note : We do the multiplications over the entire arrays at once because it's simpler and way faster. This is also why we do W.T which means W transpose. If you don't know much about linear algebra don't worry about it.

And then he calculates the sigmoid function over a :

output = sigmoid(a)

Which will give us a result between 0 and 1. And from that we can do a quick if to print the result :

if result < 0.5 :
    print("not a cat")
else :
    print("it's a cat !")

Non linear models

This was cool and all but it's still a linear model, which means that it can't correctly classify complex data and an image is pretty complex. So how do we do ?

Stack more neurons!

In a neural network you have what is called layers, There are three kinds of layers :

• The input layer where our input will be sent.
• The hidden layers that does calculation and then forward to the next layer.
• The output layer which is the same as the hidden layer except it's the last layer so its activation function may differ.

Source : Still paint, what did you expect ?

This drawing may seem a bit hard to grasp but it's actually very easy to understand.

In our last model we had the same input layer but no hidden layer and an output layer with a single neuron.
Here we have one hidden layer with 2 neurons and one output layer with one neuron.

The way this works is really the same except we have more weights and biases :

Each node has its own set of weights and biases that are used when the data is sent from one layer to the next.
So we have 2 layers that are sending their output to another one (the input and the hidden one).
so the W weight array is of the shape (3, 2) :

For instance :

[

[0.2, 4, 5] (blue line)
[2, -0.1, 5] (green line)
]

The W1 weights have the shape (2,1)

As for the biases it's simply the number of neurons that are forwarding to the next so :

b.shape = (2,1),
b1.shape = (1,1) (a number basically)

Neuron activation

Each neuron has a sigmoid activation function, which will output a number from 0 to 1. This means that each neuron will "fire" (output a high value) or not (output a low value). depending on its input. This is why neural networks are so strong :
This allows the neural network to learn features by himself.

For instance to detect a "8" if you have a neuron firing because he saw the top "o" and another firing for the bottom "o" and all the other neurons are silent, then you can safely assume it's a "8". And the more neurons and layer you stack, the more complex features can be detected.

The layers are important because they can use the output of the previous neurons :

in our previous example of detecting a 8 : the first layer of neurons will detect the top and bottom "o" and the second layer will have a neuron firing if those two neurons fired. Obviously this require a lot more neurons but you get the idea.

Forward propagation example :

Let's use the same neural network above :

Source : Still paint

We will predict from the 3 pixels the result (if it's a cat picture or not for instance).

Our variables are the following :

The input layer X, with the weights and biases W and b.
The second layer with the result of the first layer in X1 and the weights and biases W1 and b1

How do you get a prediction from that ? Well we do all the calculations going from the input layer to the ouput layer, this is called forward propagation .

So here let's calculate the value of the first neuron : X1[0]

The output is simply each input pixel by the specific weights for this neuron plus the neuron's bias :

a = X[0] * W[0][0] + X[1] * W[0][1] + X[2] * W[0][2] + b[0]  
X1[0] =  sigmoid(a) # activation function 

And it's the same for X1[1] except we use different weights and bias.

Exercise : try to calculate how we get X2[0]

it's simply sigmoid(X1[0] * W1[0] + X1[1] * W1[1] + b1)

and that's it ! It's not more complicated than that. But keep in mind that this is a simple example with 3 input neurons.
To give you a sense of scale, a colored 1920*1080 image will result in 6 220 800 input neurons. And deep neural network can have around 1000 or more layers so it's millions of weights and biases per layer.

So you can get a sense of why huge computing power is often needed for AI.

Multi class classification

So far we've only seen how a neural network can detect one thing (is it a cat or is it not a cat). The cool thing with neural nets is that you can make it detect several things at the same time, for instance let's say we want to recognize cats, dogs and boats using the model that we've been using :

source : Me Myself and I

Everything is almost the same, except we now have 3 output neurons. And instead of going for the "if superior to 0.5 then it's a cat", we simply take the output neuron that fired the most (the one with the highest value).

And this is where one-hot encoding is interesting, because we can just take the output column vector X2. Apply a max function on it (the maximum value becomes one and the rest becomes 0) and boom you have the correct encoding.

Example :

The one hot encoding for a boat is :

[0, 0, 1]

And the output (X2) was

[0.3, 0.2, 0.8]

We apply the max function

[0, 0, 1]

This way we can extract the "boat" prediction directly from the output.

Learning

So we talked a lot about how a neural network can predict output given an input via it's weights and biases, but how can the network learn the correct weights and biases to make good predictions ?

Cost function

First we have to define a way to measure how well our network is doing, and edit the weight and biases to make it better and better. There are a lot of them because it directly affect how fast the network will learn and so it's one of the core components of the training.

We will use the Cross entropy cost function because it works well and it's often used in production environment.

For the sake of simplicity I'm going to define it for a single neuron for now.

source : myself and LateX

So let's see what we have here :

n is the number of items in the training data (eg : 455)
We sum over each item in the training data
a is the output of the network (eg : 0.384)
y is the desired output (eg : 1).

And this gives us a positive number (C > 0) which will denote of how good we are. The closer to 0 the cost function is the best the neural network is.

To give you a sense of how it works let's calculate a few shall we ?
( we'll use only one example because it's simplifies the calculation)

Here this is an example where the network got pretty close to the desired output :

n = 1
a = 0.95
y = 1

source : myself and LateX

This gives us : 0.0512933, a low score which is good.

On the other hand if we had

a = 0.33

source : myself and LateX

We get : 1.10866

Note that the cost function works over multiple neurons and multiple examples which allows us to see how we are doing on an entire training set at once.

Now we have a function that tells us how our parameters W and b are doing. So now we only need to minimize this function (aka find the parameters W and b that will output the lowest value possible)

Gradient descent

When you learn a new skill, you don't get instantly good at it, as you learn you get better little by little, well machine learn the same way. So first we initialize the weights and biases with random numbers, very low numbers in the range of 0.01 because the algorithm works better that way. This has to do with the activation function.

Now we want to update these weights and biases so that we get better result with every iteration. To do this we use gradient descent.

It's a very simple algorithm :

Imagine you are on a mountain and you want to get the the bottom. To get down the fastest way possible, you take a step in the steepest direction. Then once you are there, you look for the next steepest direction and go there. And repeat until you are to the bottom and you can no longer take steps to get lower.

If you only had one neuron you would only have one W and b so the graph would look like this :

Graph made using Wolfram Alpha

You can see each step of gradient descent toward the minimum.

I'm not showing you a graph with several neurons because each new neuron adds a new set of weights and biases which result in 2 more dimensions. In our example above we had 3 neurons, that's a 6d graph. Which is not something our 3d brain can understand easily (or at all).

Applying gradient descent to our neural network

So how do we find the steepest route ? Well we compute the partial derivatives of the cost function J and and update our parameters (here W for instance):

source : myself and LateX

The alpha here is the learning rate aka how big of a step we are taking downhill. It's important not to set it to be too high because otherwise you will overshoot the minimum and actually make matter worse. For instance :

graph from wolframAlpha edited

We took a step (black arrow), saw where to go, took a step but since our learning rate is so high, we overshoot the minimum to end up on the other side, so we take another step which gets us closer but still not. Basically unless we get lucky and magically land perfectly on the spot, we will keep going up and down forever.

But if we set a learning rate that is too low, reaching the minimum will take a lot of steps. And since calculating the cost function means going through every example it takes some time. So each step can cost you a lot of compute time.

Backpropagation

In order to learn multiple layers we have to use another algorithm like gradient descent.

it's called backpropagation. I won't go into the details here because it's a (mathematically) complex algorithm and It would take some time to actually teach it to you, and this post is already very long. So just consider it as a black box that can adjust the weights and biases of multiple layers to make it learn the correct weight and biases.

I know it's frustrating, if you really want to jump into it here is a great explanation :

http://neuralnetworksanddeeplearning.com/chap2.html

I'm warning you : if you felt that my post long, it's nothing compared to that article.

Conclusion

And that's it ! This may seem a bit like cheating. We get a huge dataset of cat images, let the algorithm learn how to set its millions of parameters to detect a cat with a teraflop of computing power and yet, it works.

We've learn how machine learning actually detect things, and how it learned to do that. In the next episode, we'll see how we can implement all that into tensorflow (a machine learning framework), and how I use it in my bot.

Martin