OwnFramework

Multi-Layered Perceptrons

Building our own Neural Framework

This notebook is a part of AI for Beginners Curricula. Visit the repository for complete set of learning materials.

In this notebook, we will gradually build our own neural framework capable of solving multi-class classification tasks as well as regression with multi-layered preceptrons.

First, let's import some required libraries.

Sample Dataset

As before, we will start with a simple sample dataset with two parameters.

Machine Learning Problem

Suppose we have input dataset $\langle X,Y\rangle$, where $X$ is a set of features, and $Y$ - corresponding labels. For regression problem, $y_i\in\mathbb{R}$, and for classification it is represented by a class number $y_i\in\{0,\dots,n\}$.

Any machine learning model can be represented by function $f_\theta(x)$, where $\theta$ is a set of parameters. Our goal is to find such parameters $\theta$ that our model fits the dataset in the best way. The criteria is defined by loss function $\mathcal{L}$, and we need to find optimal value

Loss function depends on the problem being solved.

Loss functions for regression

For regression, we often use abosolute error $\mathcal{L}_{abs}(\theta) = \sum_{i=1}^n |y_i - f_{\theta}(x_i)|$, or mean squared error: $\mathcal{L}_{sq}(\theta) = \sum_{i=1}^n (y_i - f_{\theta}(x_i))^2$

Loss functions for classification

Let's consider binary classification for a moment. In this case we have two classes, numbered 0 and 1. The output of the network $f_\theta(x_i)\in [0,1]$ essentially defines the probability of choosing the class 1.

0-1 loss

0-1 loss is the same as calculating accuracy of the model - we compute the number of correct classifications:

However, accuracy itself does not show how far are we from the right classification. It could be that we missed the correct class just by a little bit, and that is in a way "better" (in a sense that we need to correct weights much less) than missing significantly. Thus, more often logistic loss is used, which takes this into account.

Logistic Loss

$\mathcal{L}_{log} = \sum_{i=1}^n -y\log(f_{\theta}(x_i)) - (1-y)\log(1-f_\theta(x_i))$

To understand logistic loss, consider two cases of the expected output:

• If we expect output to be 1 ($y=1$), then the loss is $-log f_\theta(x_i)$. The loss is 0 is the network predicts 1 with probability 1, and grows larger when probability of 1 gets smaller.
• If we expect output to be 0 ($y=0$), the loss is $-log(1-f_\theta(x_i))$. Here, $1-f_\theta(x_i)$ is the probability of 0 which is predicted by the network, and the meaning of log-loss is the same as described in the previous case

Neural Network Architecture

We have generated a dataset for binary classification problem. However, let's consider it as multi-class classification right from the start, so that we can then easily switch our code to multi-class classification. In this case, our one-layer perceptron will have the following architecture:

Two outputs of the network correspond to two classes, and the class with highest value among two outputs corresponds to the right solution.

The model is defined as

where $\theta = \langle W,b\rangle$ are parameters.

We will define this linear layer as a Python class with a forward function that performs the calculation. It receives input value $x$, and produces the output of the layer. Parameters W and b are stored within the layer class, and are initialized upon creation with random values and zeroes respectively.

In many cases, it is more efficient to operate not on the one input value, but on the vector of input values. Because we use Numpy operations, we can pass a vector of input values to our network, and it will give us the vector of output values.

Softmax: Turning Outputs into Probabilities

As you can see, our outputs are not probabilities - they can take any values. In order to convert them into probabilities, we need to normalize the values across all classes. This is done using softmax function: $\sigma(\mathbf{z}_c) = \frac{e^{z_c}}{\sum_{j} e^{z_j}}, \quad\mathrm{for}\quad c\in 1 .. |C|$

Output of the network $\sigma(\mathbf{z})$ can be interpreted as probability distribution on the set of classes $C$: $q = \sigma(\mathbf{z}_c) = \hat{p}(c | x)$

We will define the Softmax layer in the same manner, as a class with forward function:

You can see that we are now getting probabilities as outputs, i.e. the sum of each output vector is exactly 1.

In case we have more than 2 classes, softmax will normalize probabilities across all of them. Here is a diagram of network architecture that does MNIST digit classification:

Cross-Entropy Loss

A loss function in classification is typically a logistic function, which can be generalized as cross-entropy loss. Cross-entropy loss is a function that can calculate similarity between two arbitrary probability distributions. You can find more detailed discussion about it on Wikipedia.

In our case, first distribution is the probabilistic output of our network, and the second one is so-called one-hot distribution, which specifies that a given class $c$ has corresponding probability 1 (all the rest being 0). In such a case cross-entropy loss can be calculated as $-\log p_c$, where $c$ is the expected class, and $p_c$ is the corresponding probability of this class given by our neural network.

If the network return probability 1 for the expected class, cross-entropy loss would be 0. The closer the probability of the actual class is to 0, the higher is cross-entropy loss (and it can go up to infinity!).

Cross-entropy loss will be defined again as a separate layer, but forward function will have two input values: output of the previous layers of the network p, and the expected class y:

IMPORTANT: Loss function returns a number that shows how good (or bad) our network performs. It should return us one number for the whole dataset, or for the part of the dataset (minibatch). Thus after calculating cross-entropy loss for each individual component of the input vector, we need to average (or add) all components together - which is done by the call to .mean().

Computational Graph

Up to this moment, we have defined different classes for different layers of the network. Composition of those layers can be represented as computational graph. Now we can compute the loss for a given training dataset (or part of it) in the following manner:

Loss Minimization Problem and Network Training

Once we have defined out network as $f_\theta$, and given the loss function $\mathcal{L}(Y,f_\theta(X))$, we can consider $\mathcal{L}$ as a function of $\theta$ under our fixed training dataset: $\mathcal{L}(\theta) = \mathcal{L}(Y,f_\theta(X))$

In this case, the network training would be a minimization problem of $\mathcal{L}$ under argument $\theta$:

There is a well-known method of function optimization called gradient descent. The idea is that we can compute a derivative (in multi-dimensional case call gradient) of loss function with respect to parameters, and vary parameters in such a way that the error would decrease.

Gradient descent works as follows:

• Initialize parameters by some random values $w^{(0)}$, $b^{(0)}$
• Repeat the following step many times:

During training, the optimization steps are supposed to be calculated considering the whole dataset (remember that loss is calculated as a sum/average through all training samples). However, in real life we take small portions of the dataset called minibatches, and calculate gradients based on a subset of data. Because subset is taken randomly each time, such method is called stochastic gradient descent (SGD).

Backward Propagation

To compute $\partial\mathcal{L}/\partial W$ we can use the chaining rule for computing derivatives of a composite function, as you can see in the formulae above. It corresponds to the following idea:

• Suppose under given input we have obtanes loss $\Delta\mathcal{L}$
• To minimize it, we would have to adjust softmax output $p$ by value $\Delta p = (\partial\mathcal{L}/\partial p)\Delta\mathcal{L}$
• This corresponds to the changes to node $z$ by $\Delta z = (\partial\mathcal{p}/\partial z)\Delta p$
• To minimize this error, we need to adjust parameters accordingly: $\Delta W = (\partial\mathcal{z}/\partial W)\Delta z$ (and the same for $b$)

This process starts distributing the loss error from the output of the network back to its parameters. Thus the process is called back propagation.

One pass of the network training consists of two parts:

• Forward pass, when we calculate the value of loss function for a given input minibatch
• Backward pass, when we try to minimize this error by distributing it back to the model parameters through the computational graph.

Implementation of Back Propagation

• Let's add backward function to each of our nodes that will compute the derivative and propagate the error during the backward pass.
• We also need to implement parameter updates according to the procedure described above

We need to compute derivatives for each layer manually, for example for linear layer $z = x\times W+b$:

In the same manner we can define backward function for the rest of our layers:

Training the Model

Now we are ready to write the training loop, which will go through our dataset, and perform the optimization minibatch by minibatch.One complete pass through the dataset is often called an epoch:

Nice to see how we can increase accuracy of the model from about 50% to around 80% in one epoch.

Network Class

Since in many cases neural network is just a composition of layers, we can build a class that will allow us to stack layers together and make forward and backward passes through them without explicitly programming that logic. We will store the list of layers inside the Net class, and use add() function to add new layers:

With this Net class our model definition and training becomes more neat:

Plotting the Training Process

It would be nice to see visually how the network is being trained! We will define a train_and_plot function for that. To visualize the state of the network we will use level map, i.e. we will represent different values of the network output using different colors.

Do not worry if you do not understand some of the plotting code below - it is more important to understand the underlying neural network concepts.

After running the cell above you should be able to see interactively how the boundary between classes change during training. Note that we have chosen very small learning rate so that we can see how the process happens.

Multi-Layered Models

The network above has been constructed from several layers, but we still had only one Linear layer, which does the actual classification. What happens if we decide to add several such layers?

Surprisingly, our code will work! Very important thing to note, however, is that in between linear layers we need to have a non-linear activation function, such as tanh. Without such non-linearity, several linear layers would have the same expressive power as just one layers - because composition of linear functions is also linear!

Adding several layers make sense, because unlike one-layer network, multi-layered model will be able to accuratley classify sets that are not linearly separable. I.e., a model with several layers will be reacher.

It can be demonstrated that with sufficient number of neurons a two-layered model is capable to classifying any convex set of data points, and three-layered network can classify virtually any set.

Mathematically, multi-layered perceptron would be represented by a more complex function $f_\theta$ that can be computed in several steps:

• $z_1 = W_1\times x+b_1$
• $z_2 = W_2\times\alpha(z_1)+b_2$
• $f = \sigma(z_2)$

Here, $\alpha$ is a non-linear activation function, $\sigma$ is a softmax function, and $\theta=\langle W_1,b_1,W_2,b_2\rangle$ are parameters.

The gradient descent algorithm would remain the same, but it would be more difficult to calculate gradients. Given the chain differentiation rule, we can calculate derivatives as:

Note that the beginning of all those expressions is still the same, and thus we can continue back propagation beyond one linear layers to adjust further weights up the computational graph.

Let's now experiment with two-layered network:

Why Not Always Use Multi-Layered Model?

We have seen that multi-layered model is more powerful and expressive, than one-layered one. You may be wondering why don't we always use many-layered model. The answer to this question is overfitting.

We will deal with this term more in a later sections, but the idea is the following: the more powerful the model is, the better it can approximate training data, and the more data it needs to properly generalize for the new data it has not seen before.

A linear model:

• We are likely to get high training loss - so-called underfitting, when the model does not have enough power to correctly separate all data.
• Valiadation loss and training loss are more or less the same. The model is likely to generalize well to test data.

Complex multi-layered model

• Low training loss - the model can approximate training data well, because it has enough expressive power.
• Validation loss can be much higher than training loss and can start to increase during training - this is because the model "memorizes" training points, and loses the "overall picture"

On this picture, x stands for training data, o - validation data. Left - linear model (one-layer), it approximates the nature of the data pretty well. Right - overfitted model, the model perfectly well approximates training data, but stops making sense with any other data (validation error is very high)

Takeaways

• Simple models (fewer layers, fewer neurons) with low number of parameters ("low capacity") are less likely to overfit
• More complex models (more layers, more neurons on each layer, high capacity) are likely to overfit. We need to monitor validation error to make sure it does not start to rise with further training
• More complex models need more data to train on.
• You can solve overfitting problem by either:
  • simplifying your model
  • increasing the amount of training data
• Bias-variance trade-off is a term that shows that you need to get the compromise
  • between power of the model and amount of data,
  • between overfittig and underfitting
• There is not single recipe on how many layers of parameters you need - the best way is to experiment

Credits

This notebook is a part of AI for Beginners Curricula, and has been prepared by Dmitry Soshnikov. It is inspired by Neural Network Workshop at Microsoft Research Cambridge. Some code and illustrative materials are taken from presentations by Katja Hoffmann, Matthew Johnson and Ryoto Tomioka, and from NeuroWorkshop repository.