Tutorial 4: Car Neural Network

Introduction

Important

This tutorial starts at the workshop-tutorial-3 branch and the complete solution can be found at workshop-tutorial-4 branch.

This tutorial focuses on the implementation of the CarNN class, which contains the main logics for the neural network.

Note

This tutorial will implement/update the following modules:

• engine.car_nn
• engine.entity.ai_car
• game.main
• train.main

Preparation

The CarNN class is already partially implemented as we see in the file, particularlly:

• serialize: turns the neural network's weights into string so that it can be saved to files.
• deserialize: create the neural network from the given activation function, weights string, and the initial mutation noise to be passed to mutate function which we will implement later.

__init__ Function

But we also need to implement the __init__ function before actually implementing other functions of the neural network.

The prev_fitness and prev_weights members, and the activation function are rather obvious to what they should be initialized to. However, the weights, the layer_sizes, and the hiddens members need a bit more design.

When weights is provided, we can actually find out the layer_sizes from it (by checking its len and shape). On the other hand, if weights is not provided, then the user must provide the layer_sizes so that we can initialize the weights to some specific sizes.

To find out what should the size of weights be, we need to understand how neural network works, but in essense weights are the linkage between each node in the previous layer to each node in the next layer. Due to mathematicaly reasons, the previous layer node will have an additional node than the actual number of hidden node. See below for a pseudocode presenting the use of weights.

for j, prev_node in [prev[0], prev[1], ..., prev[layer_sizes[i - 1]], additional]:
    for k, curr_node in [curr[0], curr[1], ..., curr[layer_sizes[i]]]:
        weights[i][j][k] is the link of prev_node and curr_node

Note

The exact mathematical reason is explained in the Feedforward Neural Network section.

Then after finding layer_sizes, the hiddens are just the layer_sizes except the input and the output layer (i.e. the middle layers).

    def __init__(
        self,
        activation: ActivationFunc,
        weights: Optional[List[np.ndarray]] = None,
        layer_sizes: Optional[List[int]] = None,
    ):
        """
        Initialize the neural network.

        Either `weights` or `layer_sizes` must be provided.

        :param activation: The activation function
        :param weights: The weights of the neural network
        :param layer_sizes: The sizes of the layers
        """
        # Check if either weights or layer_sizes is provided
        if not weights and not layer_sizes:
            raise ValueError("Either weights or layer_sizes must be provided")

        # There is no previous fitness and weights, so they are None
        self.prev_fitness = None
        self.prev_weights = None

        # Initialize the either with the given weight, or using a normal
        # distribution
        #
        # The width should be the previous size + 1 for (x_0, x_1, ..., x_n, b)
        # and the height should be the current layer size
        self.weights = weights or [
            np.random.normal(size=(_____, _____))
            for prev_size, curr_size in zip(layer_sizes, layer_sizes[1:])
        ]

        # Initialize the layer sizes by using the given layer sizes, or
        # calculating from the weights
        self.layer_sizes = layer_sizes or (
            [
                weights[0].shape[0] - 1,
                *(weight.shape[1] for weight in weights),
            ]
        )

        # Initialize the hidden layers
        #
        # Since the initial values are not important, we can just use zeros
        self.hiddens = [
            np.array([0] * size, dtype=np.float32)
            for size in self.layer_sizes[_____:_____]
        ]

        # Assign the activation function
        self.activation = activation

Solution Code

    def __init__(
        self,
        activation: ActivationFunc,
        weights: Optional[List[np.ndarray]] = None,
        layer_sizes: Optional[List[int]] = None,
    ):
        """
        Initialize the neural network.

        Either `weights` or `layer_sizes` must be provided.

        :param activation: The activation function
        :param weights: The weights of the neural network
        :param layer_sizes: The sizes of the layers
        """
        # Check if either weights or layer_sizes is provided
        if not weights and not layer_sizes:
            raise ValueError("Either weights or layer_sizes must be provided")

        # There is no previous fitness and weights, so they are None
        self.prev_fitness = None
        self.prev_weights = None

        # Initialize the either with the given weight, or using a normal
        # distribution
        #
        # The width should be the previous size + 1 for (x_0, x_1, ..., x_n, b)
        # and the height should be the current layer size
        self.weights = weights or [
            np.random.normal(size=(prev_size + 1, curr_size))
            for prev_size, curr_size in zip(layer_sizes, layer_sizes[1:])
        ]

        # Initialize the layer sizes by using the given layer sizes, or
        # calculating from the weights
        self.layer_sizes = layer_sizes or (
            [
                weights[0].shape[0] - 1,
                *(weight.shape[1] for weight in weights),
            ]
        )

        # Initialize the hidden layers
        #
        # Since the initial values are not important, we can just use zeros
        self.hiddens = [
            np.array([0] * size, dtype=np.float32)
            for size in self.layer_sizes[1:-1]
        ]

        # Assign the activation function
        self.activation = activation

Feedforward Neural Network

Feedforward neural network refers to neural networks which obtains the value of the next layer's nodes based on the previous nodes value multiplied by some weights.

More specifically, to find the value of the node in the next layer ($y$), we need to multiply the value of each node $i$ in the previous layer ($x_i$) by their assigned weights ($w_i$), then sum them together.

And in reality, we also add a bias ($b$) to the summed value.

The most simple form of a feedforward neural network is a linear function in the form of:

$$ y = w_0x_0 + b $$

Or commonly written as:

$$ y = mx + c $$

Where the $w$ is written as $m$, the $b$ is written as $c$, and the index $0$ is ignored since there is only one $x$.

But when there are more $x$ values (i.e. the layer has multiple nodes), the form will generalize to:

$$ \begin{aligned} y &= w_0x_0 + w_1x_1 + \cdots + w_nx_n + b \\ y &= \sum_{i=0}^n w_ix_i + b \end{aligned} $$

But when there are also multiple $y$ values (i.e. previous layer also has multiple nodes), the form will further generlize to:

$$ \begin{aligned} y_j &= w_{j,0}x_0 + w_{j,1}x_1 + \cdots + w_{j,n}x_n + b_j \\ y_j &= \sum_{i=0}^n w_{j,i}x_i + b_j \end{aligned} $$

But we can make the formula more simple by adding a $1$ to the list of $x$ values, and adding $b_j$ to the list of $w_{j}$ values.

$$ \begin{aligned} x &= [ x_0, x_1, \cdots, x_n, 1 ] \\ w_j &= [ w_{j,0}, w_{j,1}, \cdots, w_{j,n}, b_j ] \\ y_j &= \sum_{i=0}^{n+1} w_{j,i} x_i \end{aligned} $$

In pseudocode, the above formula will be expressed to:

for j in 0..m
    y[j] = 0
    for i in 0..n
        y[j] += w[i][j] * x[i]

Now that we know $y$ is a list of values, $x$ is a list of values, and $w$ is a list of lists of values, there is actually a linear algebra operation made for what we need - dot product.

If we represent $y$ as a vector, $x$ as a vector, and $w$ as a matrix, then $y$ is just the dot product of $w$ and $x$.

$$ \begin{aligned} y &= w x \\ \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{m-1} \\ y_m \end{bmatrix} &= \begin{bmatrix} w_{0,0} & w_{0,1} & \cdots & w_{0,n} & b_0 \\ w_{1,0} & w_{1,1} & \cdots & w_{1,n} & b_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ w_{m-1,0} & w_{m-1,1} & \cdots & w_{m-1,n} & b_{m-1} \\ w_{m,0} & w_{m,1} & \cdots & w_{m,n} & b_m \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ \vdots \\ x_n \\ 1 \end{bmatrix} \end{aligned} $$