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:

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 current layer ($y$), we need to multiply the value of each node 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$.

Note

The reason why we only use a linear function (as compared to for example a quadratic function) between nodes is mainly because it is the most simple expression of relationship between values, and that more complicated relationships are instead modelled by having multiple layers.

As we multiply more and more hidden layers in between, the relationship between the input layer and the output layer becomes more and more complicated.

But when there are more $x$ values (i.e. the previous 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. the current 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} $$

We can then 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]
    for i in [0, n + 1]
        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} & \dots & w_{0,n} & w_{0,n+1} \\ w_{1,0} & w_{1,1} & \dots & w_{1,n} & w_{1,n+1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ w_{m-1,0} & w_{m-1,1} & \dots & w_{m-1,n} & w_{m-1,n+1} \\ w_{m,0} & w_{m,1} & \dots & w_{m,n} & w_{m,n+1} \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ \vdots \\ x_n \\ 1 \end{bmatrix} \\ \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{m-1} \\ y_m \end{bmatrix} &= \begin{bmatrix} w_{0,0}x_0 + w_{0,1}x_1 + \dots + w_{0,n}x_n + w_{0,n+1} \\ w_{1,0}x_0 + w_{1,1}x_1 + \dots + w_{1,n}x_n + w_{1,n+1} \\ \vdots \\ w_{m-1,0}x_0 + w_{m-1,1}x_1 + \dots + w_{m-1,n}x_n + w_{m-1,n+1} \\ w_{m,0}x_0 + w_{m,1}x_1 + \dots + w_{m,n}x_n + w_{m,n+1} \\ \end{bmatrix} \end{aligned} $$

It seems to be all good now, except one thing - we only have 2 layers ($x$ and $y$). We must also generalize it to have multiple layers.

Let $h_k$ be layer $k$, then $h_{k,i}$ is the value of the node $i$ in layer $k$. Also let $w_k$ be the weights between $h_{k-1}$ and $h_k$, then $w_{k,j,i}$ is the weight between $h_{k,j}$ and $h_{k-1,i}$.

Then the previous formula will be further generlized.

$$ \begin{aligned} h_k &= w_k \text{concat}\left(h_{k-1}, [1]\right) \\ \begin{bmatrix} h_{k,0} \\ h_{k,1} \\ \vdots \\ h_{k,m-1} \\ h_{k,m} \end{bmatrix} &= \begin{bmatrix} w_{k,0,0} & w_{k,0,1} & \dots & w_{k,0,n} & w_{k,0,n+1} \\ w_{k,1,0} & w_{k,1,1} & \dots & w_{k,1,n} & w_{k,1,n+1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ w_{k,m-1,0} & w_{k,m-1,1} & \dots & w_{k,m-1,n} & w_{k,m-1,n+1} \\ w_{k,m,0} & w_{k,m,1} & \dots & w_{k,m,n} & w_{k,m,n+1} \\ \end{bmatrix} \begin{bmatrix} h_{k-1,0} \\ h_{k-1,1} \\ \vdots \\ h_{k-1,n} \\ 1 \end{bmatrix} \\ \begin{bmatrix} h_{k,0} \\ h_{k,1} \\ \vdots \\ h_{k,m-1} \\ h_{k,m} \end{bmatrix} &= \begin{bmatrix} w_{k,0,0}h_{k-1,0} + w_{k,0,1}h_{k-1,1} + \dots + w_{k,0,n}h_{k-1,n} + w_{k,0,n+1} \\ w_{k,1,0}h_{k-1,0} + w_{k,1,1}h_{k-1,1} + \dots + w_{k,1,n}h_{k-1,n} + w_{k,1,n+1} \\ \vdots \\ w_{k,m-1,0}h_{k-1,0} + w_{k,m-1,1}h_{k-1,1} + \dots + w_{k,m-1,n}h_{k-1,n} + w_{k,m-1,n+1} \\ w_{k,m,0}h_{k-1,0} + w_{k,m,1}h_{k-1,1} + \dots + w_{k,m,n}h_{k-1,n} + w_{k,m,n+1} \\ \end{bmatrix} \end{aligned} $$

Note

The previous layer is not really the $x$ in our original formula, because remember our original formula's $x$ has a $1$ at the end for multiplying with the bias!

So we also need to $\text{concat}$ a $1$ to $h_{k-1}$ to make the dot product valid.

We are almost there! There is a final step, we need to apply an activation function on the result before really assigning it to the next layer.

$$ h_k = \text{activate}\left(w_k \text{concat}\left(h_{k-1}, [1]\right)\right) $$

Note

While in some scenario, activation functions may not be needed, but the reason why activation functions are often used in between layers is because it provides nonlinearity to the model and clip the values to a certain range, while still preserving differentiability so that the model can still learn.

Intuitively, it is like asking the neural network to think step by step instead of doing everything in one go by keeping the value in a certain range, e.g. "Am I in danger?" -> "Can I outrun the danger?"/"Can I win against the danger?" -> "Should I run or fight?".

After figuring out the math, here is a summary of what we need to do in the activate function:

We need to find the first hidden layer's value self.hiddens[0] from the input parameter by doing the computation $h_0 = \text{activate}\left(w_0 \text{concat}(\dots h_{-1}, [1])\right)$, except we don't have $h_{-1}$ so we replace it with the input.
Then we loop over each adjacent layers $h_k$ and $h_{k-1}$ and apply the same computation $h_k = \text{activate}\left(w_k \text{concat}(\dots h_{k-1}, [1])\right)$.
The output layer will be obtained in the same way.
Remember to clip the final output to [-1, 1] because it is what AICar._get_input expects.

Here are some useful numpy functions: numpy.concatenate, numpy.dot, numpy.clip.

    def activate(
        self, inputs: npt.NDArray[np.float32]
    ) -> npt.NDArray[np.float32]:
        """
        Activate the neural network.

        :param inputs: The input vector
        :return: The output vector
        """
        # Check if the input size is correct
        if len(inputs) != self.layer_sizes[0]:
            raise ValueError(
                f"Expected {self.layer_sizes[0]} inputs, got {len(inputs)}"
            )

        # Calculate the first hidden layer
        self.hiddens[0] = _____(
            np._____(np._____((_____, [1.0])), _____)
        )

        # Calculate the remaining hidden layers in a loop
        for i in range(1, len(self.hiddens)):
            self.hiddens[i] = _____(
                np._____(
                    np._____((_____, [1.0])),
                    _____,
                )
            )

        # Calculate the output layer, and also clip the values to [-1, 1]
        # because it is what is required by the car
        return np.clip(
            np._____(
                np._____((_____, [1.0])),
                _____,
            ),
            -1.0,
            1.0,
        )

Solution Code

    def activate(
        self, inputs: npt.NDArray[np.float32]
    ) -> npt.NDArray[np.float32]:
        """
        Activate the neural network.

        :param inputs: The input vector
        :return: The output vector
        """
        # Check if the input size is correct
        if len(inputs) != self.layer_sizes[0]:
            raise ValueError(
                f"Expected {self.layer_sizes[0]} inputs, got {len(inputs)}"
            )

        # Calculate the first hidden layer
        self.hiddens[0] = self.activation(
            np.dot(np.concatenate((inputs, [1.0])), self.weights[0])
        )

        # Calculate the remaining hidden layers in a loop
        for i in range(1, len(self.hiddens)):
            self.hiddens[i] = self.activation(
                np.dot(
                    np.concatenate((self.hiddens[i - 1], [1.0])),
                    self.weights[i],
                )
            )

        # Calculate the output layer, and also clip the values to [-1, 1]
        # because it is what is required by the car
        return np.clip(
            np.dot(
                np.concatenate((self.hiddens[-1], [1.0])),
                self.weights[-1],
            ),
            -1.0,
            1.0,
        )

Navigation Menu

Tutorial 4: Car Neural Network

Introduction

Preparation

`init` Function

Feedforward Neural Network

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally

Tutorial 4: Car Neural Network

Introduction

Preparation

__init__ Function

Feedforward Neural Network

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally

`init` Function