1.1 Coding Examples

In this chapter you will find code examples. However, unlike the other chapters in this book these examples will be written in Python, primarily because most of the ML libraries and supporting tools are based on this programming language. We are aware that Python is slower than C ++ and similar languages. On the other hand, most of the libraries, like NumPy [1], are written in C ++ and well optimized and Python is just an interface enabling much easier and faster development, and the computational overhead is negligible. Python code is also more readable and shorter allowing us to provide more examples. Furthermore, Python is more suitable for ML when there is a need for a fast way to test hypotheses. Once a proper way is found Python be rewritten and optimized into C ++ format.

To be able to run the code examples the reader needs to have access to Python 3.7.* and the following libraries: NumPy, Matplotlib, Scikit-Learn, PyTorch, torchvision. These are widely used on most platforms, and installation issues can be solved with solutions found using Google Search.

1.2 The Machine Learning Revolution

Lately the primary focus on machine learning has been on neural networks (NNs) and so-called deep learning. The main reasons for this focus are:

• ⦁ There are huge data sets available and the information continues to expand.
• ⦁ Processing hardware is more powerful than ever before.
• ⦁ Industry experts have discovered that deep NNs are able to outperform the current state-of-the-art techniques that have been handcrafted and tuned for decades. Previously, no one was able to sufficiently train these deep architectures because there just weren’t enough data or processing power to do it.

In this chapter we will discuss deep learning and the methods used before its widespread adoption. These classical methods are usually lightweight in size and might also be faster than NNs. For some applications they might provide comparable accuracy, but with much smaller costs and it would be a huge mistake to ignore them. Sometimes they are also used in combination with neural nets.

3.1 Bias vs. Variance Trade-off

There are two sources of error that prevent supervised learning algorithms from generalizing beyond their training set:

• ⦁ Bias is an erroneous assumption in the learning algorithm. It can cause relevant relations between features (input data) and outputs (e.g., fitting polynomials of degree 1 (linear) into data with quadratic relations) to be missed. This issue is also called an underfitting problem.
• ⦁ Variance is an error that results from sensitivity to small fluctuations in the training set. It can cause an algorithm to model random noise in the training data and somehow mimic memorizing the dataset. It is also called an overfitting problem.

Bias can be prevented by using a more complex model, but as the number of parameters increases the model will be more prone to overfitting. Overfitting can be prevented with more data. There is always some trade-off between bias and variance when we are choosing the proper model. To support intuition see Figs. 2 and 3.

Regularization techniques are another way to prevent overfitting. These techniques add an associated cost into the loss function for each parameter used. This allows the model to have the flexibility to choose the proper complexity. There is no silver bullet for choosing a proper technique, and it usually requires lots of experience and intuition to set up everything properly.

To support the intuition behind overfitting go back to the example of learning to detect faces in images—what happens if we only show 10 examples to a lazy student with a good memory (big number of model parameters). The student will probably find it easier to memorize the answer instead of learning to generalize/use reasoning. Then we can determine whether the student was able to generalize if we show him previously unseen examples. If he just memorized the question and answers, then he will fail. The same approach is used in machine learning, whereby the previously unseen data are called test data, and with this approach we can estimate how the algorithm will perform in the future (additional details are provided in the next section).

4.1 Data Are Crucial

• ⦁ If you don’t have enough data, then state-of-the-art algorithms won’t help you.
• ⦁ If you don’t have enough data, then complex models (with a high number of parameters) will tend to overfit (see Section 3.1) and fail dramatically when deployed.

The natural question arises: How many data are enough? The higher the model’s complexity, the higher the demand for data. There are some theoretical boundaries, like the Vapnik-Chervonenkis theory for VC dimension [4], providing rough estimates. Some basic rules are that we need at least k independent examples for each class; there must be more independent examples than the number of input features and more independent examples for each parameter in the model. If we take, for example, an input to be an image of size 500 × 500 × 3, we at least know that we should have more than 0.75 M images to train a given model. Another approach to estimate the required amount of data is to look at similar problems and published papers.

Another thing we should be aware of is that a lot of ML algorithms assume that data are independent and identically distributed (i.i.d.). This is a terminology from probability theory and statistics. I.i.d. means that each random variable has the same probability distribution as the others and all are mutually independent. But what happens when we violate that? What happens when we have fewer training data? Usually, the model still learns something, but might be more prone to overfitting. This is task dependent as well as algorithm dependent.

4.2 Data Preprocessing, Grooming, and Preparation

The goal of data preprocessing is to prepare data into a “tabular” numerical arrangement. This means that ultimately all data must be transformed into numbers. For example, this might mean encoding categorical variables using one-hot encoding. Tabular means that each data sample is in a row, whereas columns represent features and a few of the last columns have the right answers (e.g., class number).

The entire process can be reduced to:

• ⦁ Data cleaning—a process in which wrongly completed questionnaires, invalid experimental data, or data not passing through logical control are removed.
• ⦁ Data labeling and tagging—for cases where some of the data are unlabeled we must “get our hands dirty” and create annotations. This step is usually also educative because we can learn a lot about the nature of the given task. This task is usually outsourced.
• ⦁ Augmentation—allows us to automatically enlarge our data set (explained later in more detail).
• ⦁ Selection of training, validation, and testing sets (described later).
• ⦁ Normalization—this step normalizes data. The reason is that most algorithms work better after this step. The only algorithm class (of those covered in this chapter) that doesn’t need this step are decision trees (see end of Section 6 for an explanation of why the algorithm might fail without normalization).
• ⦁ Feature extraction (covered later).

4.3 Training/Test and Validation Data Split

To prevent overfitting, data are usually divided into three categories. The first and biggest category is the training data set; it is usually 80%–90% of the size of the regular data set. To have a balanced data set the training data set is typically pseudorandomly chosen from the whole data set. For example, 80% are randomly chosen from each class to ensure all classes are represented.

The remaining 10%–20% of the data are typically divided into two equal-sized data sets—a test set and a validation set. The test set will only be used in the final process to evaluate and predict how well the model generalizes for new data (i.e., not used during the training phase!). The validation set is used to tune hyperparameters for a given ML algorithm.

A slightly more complex but commonly used technique is called k-fold cross-validation [5]. This technique divides the data set into k balanced folds (whereby the user determines the number of folds k and balanced means in which the percentage distribution of classes stays approximately the same proportion as in the full data set). Then the training process is done for all except the kth fold (this is used as the test and validation set). The entire process is done k times. By measuring the accuracy average and standard deviation we get a much better estimate on how the model generalizes. Commonly used values of k are between 5 and 10. Typically, higher values are better, but this increases the training time. This k-fold technique is not commonly used with neural networks because the training time is usually more demanding than a suitable non-NN algorithm.

4.4 Semantic Gap

Humans have a very advanced perception of the world around us. For example, when we see something we don’t think about each photon or atom. Instead, we perceive objects, faces, textures, etc. The same applies to audio; we don’t think about frequencies in time, instead we perceive words from which we build sentences and on top of that we reason.

On the other hand, observe how a machine sees the world (Fig. 4). The bottom section of the images are 10 × 10 matrices representing the highlighted red blocks. Notice how different the matrices look even after rotating the block by only 2°, although humans have no problem recognizing the rotated image. This demonstrates the huge semantic gap within data and how humans interpret them. For obvious reasons we want to design our systems to be resilient to such changes (e.g., slight rotations, translations, noises, intensity changes) (Fig. 5).

4.5 Data Augmentation

We’ve learned that data are crucial and that usually it is difficult to obtain enough training data to achieve close to 100% accuracy on predictions. Data augmentation is a great way to increase the number of training examples. Using an example of image classification we want to classify an image of a dog as a dog even if the image is horizontally flipped, contains a little random noise, or is scaled, translated, or rotated. In computer vision these data modifications are straightforward and applicable beyond traditional image classification (e.g., it can be used for regression like object detection). The only rule is that the augmented image still maintains the same label or at least we know how to change the label (e.g., in the case of object detection, if we rotate an image slightly, we must change the object’s digital position as well). It is possible to do the same for audio (e.g., adding background noise, increasing the tempo, phase shifting, etc.). Similar techniques can be applied to other domains.

Why does data augmentation work? Looking at Fig. 4 we don’t think the image changed significantly, but from the computer’s perspective the data matrix is completely different even when small changes are applied. This process is artificially accomplished by adding more examples of the same class, and more examples should help to prevent overfitting. Furthermore, compared with manual labeling the computational cost of augmentation is negligible.

4.6 Introducing an Image Classification Problem

The best way to learn something is to apply what you’ve already learned to solve a problem. In this section we will apply ML algorithms to an image classification task (we’ll train our own convolutional neural net or CNN). We will use a task from the computer vision domain because it is more intuitive to visualize what is happening (Fig. 6).

The CIFAR-10 data set is a relatively small, publicly available data set with 32 × 32 color images sorted into 10 different classes (e.g., airplane, automobile, dog). CIFAR-10 is considered a sandbox data set that is useful for testing but not real-world inferencing, replacing the previously popular MNIST example (28 × 28 images of handwritten digits). The simple MNIST model has become well understood (many recent algorithms have less than 0.25% accuracy error whereas state-of-the-art algorithms on CIFAR-10 achieve rates of around 2%).

4.7 Feature Extraction

For any type of machine learning the input data should be preprocessed. Take audio classification, for example—the incoming audio signal must be filtered to remove ambient noise. For vision applications various types of filtering or color conversion might be utilized to enhance specific colors or lines.

Here we list a few commonly used feature extraction techniques (we can also view feature extraction as a dimensionality reduction): in computer vision a search for key points (e.g., corners, dark/light blobs, etc.) is done and then each key point is described using algorithms like SIFT, SURF, ORB, Tf-idf for text analysis, or MFCCs and MPEG-7 for audio, etc. Handcrafted features can also be utilized.

For image classification, for example, an entire 32 × 32 × 3 image can be unraveled into a 3072 × 1 vector. This vector might be our feature space, the dimensions where the variables live. However, most ML algorithms will suffer from such a big feature space, and this is often referred to as “the curse of dimensionality”—a situation in which data are organized in high-dimensional spaces. The main problem is that as the number of dimensions increases the data points become sparse, statistical significance drops, and this in turn damages the methods that rely on it. A big feature space will also harm the speed of inference as well as training. Finally, another problem of a big feature space in the case of an image is that there is information hidden in the pixel distribution (spatial relations are very important and if you do random permutation of pixels you will no longer be able to recognize the image). If we compare images at the pixel level, there is a huge semantic gap; shifting an image a small amount causes completely different values of the given pixels (refer to Section 4.4). This highlights the fact that we need a better way to represent each image.

An easy and straightforward way to represent images is to make us of a color histogram. A histogram divides a given range into bins and then counts the number of occurrences in each bin. For example, we can divide each color channel into k bins and compute how many pixels of a given intensity in that given channel are present in an image. Using this approach we can reduce the feature space from 3072 × 1 into a much more manageable 3k × 1 vector. See examples of histograms in Fig. 7.

4.8 A Baseline

In the following sections we will introduce several famous ML algorithms, but before starting let’s think about a small experiment. What about having a naive classification algorithm returning a class randomly? This algorithm will have an accuracy of 1/K, where K stands for the number of classes. It is good to consider this as a baseline and sanity check. When our algorithms perform below this number it is an indication of something being broken. Therefore, it is good practice to have these types of sanity checks included during development.

7.1 Ensemble Learning

We will explain ensemble learning here as it relates to decision trees, but these approaches are general and can/should be used with other algorithms. Ensemble learning usually comes with higher computational and memory cost, but it leads to higher accuracy. In accuracy-critical applications these techniques are also used for computationally intense algorithms like NNs. Ensemble learning is a technique that can make decisions based on multiple models which can be homogeneous (e.g., 10 decision trees) or heterogeneous (e.g., decision tree + SVM + neural network). A heterogeneous example is based on the idea of combining the results of different algorithms, assuming that each has its own strengths and weaknesses. Why does it make sense to use it on homogeneous models? Aren’t the models the same? First, since we can use different hyperparameters for each model they might be slightly different. There is also a technique in which the hyperparameters are the same, and yet it still makes sense (one of them is called a random forest classifier/regressor; see Section 7.3).

7.2 Bagging

Using a technique called bagging (bootstrap aggregating) we combat overfitting by taking k-same models. With this technique we randomly sample a subset of data (e.g., 85%) from the training data set for each model. Then we train the model, perform k predictions, and in the case of a classification task take the argmax. We can also recast this information as a probability distribution over classes. This approach works because each trained model saw just a portion of the data set, thus it cannot fully overfit. In combination with other models it generalizes better on a given task.

7.3 Random Forest

The decision trees concept has many versions, and one of the most frequently used is the random forest approach [12]. This uses the ensemble-learning concept called bagging, but this is not the only randomization performed. During training a vanilla decision tree uses all features to choose which one best divides the data. The random forest approach randomly samples a subset of features in each node (a frequently used subset size is $\sqrt{F}$,where F is the number of features). This helps prevent overfitting and speeds up the training process. In the end the final decision is based on voting (as in any other ensemble method):

As mentioned in Section 6 it is easy to reuse the code for classification and use a different algorithm. We can try to do the classification using a random forest with 10 trees. Classifier has many more parameters like max depth. A great way to build intuition about this is to play around with parameters and observe what Classifier does (Fig. 14).

7.4 Boosting

Boosting is another ML technique that produces a prediction model as an ensemble of so-called weaker models. Boosting is done in an incremental way where each new model emphasizes the training data misclassified by the previous model. Sometimes boosting might have better accuracy than bagging, but it might be more prone to overfitting. AdaBoost [13] is an example of a boosting algorithm. Because of its efficiency and flexibility XGBoost [14] is a commonly used implementation of gradient boosting. It is usually good practice to compare multiple approaches (e.g., gradient boosting vs. random forests) on a given problem and choose the better one (using trial and error).

8.1 Motivation

A distinct historical landmark is the 2012 success of AlexNet [6] in the ILSVRC image classification challenge utilizing the ImageNet data set [15]. The task was to classify ImageNet’s images into one of 1000 classes including animals, dog breeds, cello, cradle, car wheel, volcano, seashore. These algorithms were compared using top-5 metrics, which means the top-5 predictions are returned and if the correct class is among them it is accepted as a correct prediction. As seen in Fig. 15 the last successful classic computer vision approach was done in 2011 where there was a 26% top-5 error. The following year AlexNet [6] reduced this error by almost 10%; this ignited the spread and domination of convolutional neural nets (CNNs). In 2014 AlexNet was followed by the larger VGG network [16] as well as the more complex GoogLeNet [17]. Finally, in 2015 the even deeper CNN architecture ResNet [18] outperformed human performance in the top-5 classification tasks (Figs. 16 and 17).

8.2 What Is a Neural Network?

A neural network is a brain-inspired algorithm in which the basic building block is called a neuron—so-called because it is a simplified, mathematical model of a biological neuron. Each neuron has one or more inputs and a single output. Similarly, inputs are called synapses and there are typically other synapses connected to the output—sending information to other neurons. Each synapse is represented by three properties: a starting neuron, a weight, and an ending neuron. The synapse weights are the primary NN parameters. Where does the “magic” occur? Each neuron takes a signal from each input, multiplies it by a synapse weight, and sums these products together (i.e., a multiply-accumulate function).

On top of that, an activation function is applied. The main purpose of an activation function is to bring nonlinearity into the whole system. This is a very important aspect. Compared with a vanilla SVM (which is linear), NN can solve nonlinear tasks. Recall from Fig. 11 that when we want to separate data points it is not possible to do it with a line (this is called linear nonseparability). Thanks to the nonlinearity added in an activation function the NN is projecting (warping/upscaling) its input feature space into a new one where linear separation might be possible in the end.

Another goal of an activation function might be to scale the output into a given range (e.g., < 0, 1 > for a sigmoid function). For more examples of activation functions see Fig. 18. The output of the activation function is then sent to all other connected neurons, multiplied by the respective weights, and so on through each layer of the network.

In general, neurons are connected and form a graph structure called a directed acyclic graph (DAG). DAGs can have almost any imaginable topology. When referring to currently used deep-learning architectures, DAGs are best organized into layers (Fig. 19). Layers are groups of neurons. As we’ll see in the following sections, layers can be more complex than a straightforward fully connected one (which means that each neuron has a connection with all neurons from previous layers). One example of a more complex layer is a convolution layer, which is described in the Section 8.4. The convolution layer is one of the most important concepts in NNs for vision and other tasks.

8.4 Convolutional Neural Networks

Convolutional neural networks are another important tool/concept in the domain of NNs.

Their main advantage is that they use fewer parameters than a fully connected layer. Thus they are more robust to overfitting and less demanding of memory space.

As discussed in the previous sections the NN learns, filters, performs feature extraction, and makes predictions. CNNs are great for tasks where there is spatial information in the input data (e.g., images, audio, the order of words in a sentence).

8.4.1 What is a Convolution?

Convolution is defined as continuous data and as discrete data (the only difference is integration vs. summation). For computer science tasks the discrete, finite form is handier:

$\left(f\ast g\right)\left[n\right]={\displaystyle \sum _{m=-M}^M}f\left[n-m\right]g\left[m\right],$

where M is half the size of the kernel. We can view convolution as computing a dot product with a kernel prescription for each possible position of the kernel in the input space. It is a kind of scanning window approach to searching for positions with the best response to a given kernel.

An intuitive way to imagine convolution is to regard it as a response to a given filter. The higher the data similarity to the kernel, the higher the response (see Figs. 24 and 25).

For example, let’s say we are looking for a step-down edge in 1D data. We define our convolution filter as a simple [− 1, 1] (see Fig. 25 for a convolution response to the signal). Some code to generate Fig. 25 is:

It is straightforward to scale up the convolution into higher dimensions.

8.4.2 A Convolution Layer

So now we know how convolution works. A convolution layer in neural networks does the same thing—a kernel slides over the input and results are written into the output matrix (feature map). The dimensionality of a kernel is given by the kernel size and by a number of channels in the input layer. For example, if we have an image of size 5 × 5 × 3 (where 3 stands for RGB channels) and a convolution layer with two 3 × 3 kernels, the weights in this layer are represented by 3 × 3 × 3 values (3 × 3 kernel times 3 input channels). The number 27 is derived because the input layer has 3 channels and there is a unique 3 × 3 matrix for each channel. In our example the weight matrix W will be 3 × 3 × 3 × 2 (kernel_h × kernel_w × num_input_channels × num_kernels). In comparison, a fully connected layer with 9 outputs will have 5 × 5 × 3 × 9 weights.

Note that by increasing an image size to 128 × 128 × 3 the number of parameters in the convolution layer stays the same (3 × 3 × 3 × 2 = 54 parameters), but the number of fully connected layers, when output should be 3 × 3 × 2, is 128 × 128 × 3 × 9 = ~ 0.5 M parameters. This might have a huge impact on memory requirements and provide a lot of space for overfitting. We can see that the concept of a convolution layer is crucial to solving problems with high-input volumes. Computer vision fulfills that (Fig. 26).

Two additional parameters are usually associated with convolutional layer computation—stride and padding. Stride defines the step the convolution kernel is moved (standard convolution has step 1 in both height and weight). It is possible to have, say, step 3 for convolution kernel 7 × 7, which means that the first convolution will be computed on coordinates (4, 4), the second on (4, 7), and so on. This will also reduce the output size by a factor of 3. The padding parameter defines the way in which border computations are managed. The first option is to do nothing such that stride = 1 and convolution kernel 7 × 7 produces outputs with height and weight smaller by 6 pixels (due to the nature of convolution). The second option is to require output to be the same size. In this case we can either fill the border with zeros (commonly used), or to prevent a potentially big ramp in the signal the border values will have the same values as the nearest pixel. The convolution layer might also be associated with the bias parameter for each kernel allowing output values to be moved by a constant.

8.4.3 Feature Extraction in Neural Networks

We have already discussed a feature extraction step in Section 4.7. All these features can be fed into NNs as well. What is interesting is that we can feed NNs with whole images, audio files, text series, etc., and let the NN learn features on its own. This is especially the case for CNNs where we can clearly see that filters are being learned in each convolutional layer. For example, in the first layer we can distinguish basic edge filters, blobs, corners, etc. In higher layers we can observe geometrical concepts (e.g., circles, squares) followed by others such as eyes, heads, hands, and wheels. In the last layers we can observe filters having high activations for entire objects (e.g., human, car, dog, cat, etc.). There is huge value in this because the NN can learn its own features based on the domain of a given task. It also usually outperforms handcrafted approaches (Fig. 27):

This code example of 2D convolution is a naive implementation. In a real deep-learning framework there will be a lot of different functions implementing convolution to better harness HW-specific operations and caches and using a faster algorithm based on parameters such as input size, kernel size, and number of inputs. One optimization is to modify the input matrix in such a way that convolution can be computed as a single matrix product. Another common technique is computing convolution as a multiplication in the Fourier domain, after appropriate padding (to prevent circular convolution). Usually, a developer doesn't have to implement any of these functions because they are usually done automatically within the deep-learning framework.

8.4.4 Convolutional Neural Network Classifier Example

Let’s now look at how to use PyTorch [29] (a deep-learning framework—we discuss other frameworks in Section 8.6) to train our own image classification. Our goal will be to classify images from the CIFAR-10 data set (as we’ve already described it in Section 4.6). In this example we won’t do the real heavy lifting. The data set is relatively small as is the neural net. A regular notebook or desktop PC without GPU should make it possible to complete the training within 10–20 min. It is also possible to use GPU clouds. Many companies provide some trial credit (e.g., Google Cloud Platform). While speaking about Google at the time of writing they also provide a service called Colab [30], where some GPU resources are available for free:

First, we need to import all the necessary modules (lines 1–9). The two main packages we are using are torch (PyTorch) and torchvision—utilities that make deep learning for computer vision even easier. Then we set out our neural net definition. Our net class is inherited from nn.Module and must employ the forward method. In constructor __init__ all building blocks are defined. Let us first look at the forward method that defines what our architecture will look like (see also Fig. 29). We have two blocks that are basically the same (lines 23–24)—a convolution layer followed by an activation function (relu) and then by pooling. On line 25 data are just transformed (flattened) from 4D (batch, height, width, channels) to 2D (batch, vector). This is necessary because on lines 26–27 a fully connected layer is used that expects input from only the 1D vector. Fully connected layers are followed by the relu activation function.

As we now know what our network should look like we can better understand the constructor. On line 14 the first convolution layer is defined. It expects 3 channels on its input. It has 8 filters (kernels) and the kernel size is 3 × 3. On line 15 a 2 × 2 max pooling layer is defined (it will reduce the size of feature channels by two as it divides each channel into 2 × 2 blocks and returns the maximum value from these four). On line 16 a second 3 × 3 convolution layer is defined. It expects 8 channels on the input and returns 16 channels. The kernel size is 3 × 3. On lines 18–20 fully connected layers are defined. They are defined by the number of input neurons and the number of output neurons. In this case we need to compute how many neurons there will be on the input. This depends on all previous layers and the input size. We know for sure that there will be 16 channels. Their resolution is affected by input size (32 × 32). The first 3 × 3 convolution without padding is applied, which means the filter size will be 30 × 30. Then max pooling is applied resulting in a size of 15 × 15. On top of that, a second 3 × 3 convolution without padding is applied, which means the filter size is 13 × 13. Max pooling is once again applied, thus making the filter size 6 × 6. Thus the input of the first fully connected layer will be 16 × 6 × 6 (see line 18). The number of output neurons (in our case 100) is a design choice. The last fully connected layer (line 20) must have 10 output neurons (as we have 10 classes).

On line 108 the loss function is chosen. In this case we are using cross-entropy loss $J=-\frac{1}{N}\left({\displaystyle {\sum }_{i=1}^N{y}_i}·log\left({\widehat{y}}_i\right)\right)$, where N is number of classes (in our case 10), y_i is the predicted probability of class i, and ${\hat{y}}_i$ is 1 when the ith class is the correct one. A perfect model would have zero loss. But this won’t happen in practice. If you have zero loss you are either terribly overfitted or something is broken.

On line 109 an optimizer is defined. We are using a stochastic gradient descent (SGD) of learning rate of 0.1 and momentum of 0.9. A learning rate of 0.1 is pretty high (we are quite aggressive on training speed). If training diverges and loss starts to dramatically increase it might be time to consider learning rate reduction. As mentioned before, learning rate is an important hyperparameter.

The rest of the code is self-explanatory. Lines 79, 80 might be worthy of mention—where a data augmentation is added by doing random crop and horizontal flip (think why vertical flip wouldn’t be such a good idea for our case).

Even with this simple NN we were able to achieve a validation accuracy slightly above 60% (60.69%) after 20 epochs. To start building intuition we suggest the reader does the following exercises:

• • Try training without augmentation. What do you expect will happen?
• • Try to experiment with architecture (add more convolution layers) and add padding.
• • Try to experiment with optimizer parameters or try different optimizers (e.g., Adam).

8.5 Recurrent Neural Networks

The recurrent neural network (RNN), discovered by John Hopfield in 1982, is used for operations on sequences (e.g., text, voice). It enables NNs to learn patterns over time (e.g., detecting actions in video sequences, speech detection in audio, etc.). RNNs use a connection from their output to their input to allow the NN to gain a concept of temporal memory. This can be imagined as copying the whole NN and adding the same architecture into the new structure, and then sharing weights (see Fig. 30). The RNN can send some signals/states based on what was already processed on the input.

Building on RNNs there is an improved concept called long short-term memory (LSTM). Such networks allow speech applications to be improved dramatically (they are also widely used for text processing like machine translation). LSTMs were also successfully used in combination with CNNs for image captioning [31]. It’s also common to combine CNNs with LSTMs for video streams for tracking or events detection (Fig. 31).

8.6 Deep-Learning Frameworks

Which framework to choose? That’s the question. There are multiple possibilities and new ones are added each year. If asked to name the most common we would come up with TensorFlow [32], Caffe [33], and PyTorch [29].

TensorFlow (TF) is backed by Google. It is definitely the most used. It has a huge community and a fork called TensorFlow Lite focusing on mobile devices. Caffe seems to be in a decline. It was one of the first, widely used frameworks for CNNs.

PyTorch is a great tool for experiments. Compared with TensorFlow it is much easier to use to debug NN (as it boasts dynamic computational graph creation) and is commonly used in research. CNTDK is backed by Microsoft. The author’s personal suggestion is to design, tune, and debug NNs in PyTorch as it is simply easier. When dealing with performance issues try a move to TF (maybe even TensorFlow Lite).

There are also projects such as ONNX (Open Neural Network Exchange Format) [34] or NNEF (Neural Network Exchange Format, backed by Khronos) [35] that provide tools for NN interchange between different deep-learning frameworks. Currently, they work fine for mainstream DNN frameworks and ordinary NNs but might struggle when more complex layers are used.

9.1 Quantization

The most important technique in the NN optimization domain is quantization [37]. Quantization does not change the architecture, instead it decreases the precision of weights and/or the activation functions. Most commonly seen is a decrease from float32 to int8 fixed-point precision—this alone reduces the memory footprint 4 ×. Note that for int8 multiplication you still need int32 registers.

The quantization of weights only reduces the size and might have no effect on inference time, although there’s a possible speedup because size reduction leads to the model fitting better into faster memory/caches, and depending on the HW it might also be computed faster doing computations in INTs instead of FLOATs. To improve performance the quantization of activations is also necessary. Usually, weights and activations are represented using 8 bit, but if there is a bias term (like in a convolutional layer) it is usually represented using 32 bit.

9.2 Pruning

Pruning neural networks is not a new concept. Papers such as Lecun et al. “Optimal Brain Damage” [38] date back to 1990. Pruning assumes, as many results show, that neural networks are overparametrized and thus there is redundancy. Moreover, some neurons do not contribute significantly. There might also be “dead neurons” with outputs that are always zero resulting from too high a learning rate in combination with activation functions prone to this behavior. If we find a way to rank the neurons based on how much they contribute, we can then decide to remove the less valuable ones to save space and potentially speed it up.

Ranking can be done according to either the L1/L2 norm of their weights, the neurons mean activations on some reasonable validation data set, the number of times a neuron wasn’t zero on a validation dataset, and other methods. After the pruning process accuracy drop is expected. The following step is commonly used to fine-tune the network to give the NN an opportunity to recover.

Speedup though is not guaranteed. Pruning usually results in irregular network connections that not only demand extra representation efforts, but also do not fit well with parallel computation. This is usually worthwhile only when NN size is the issue or it results in an NN with high sparsity, where overhead from sparse matrix computation is negligible. Another possibility is structured pruning [39] (e.g., removing whole convolution kernels, etc.).

9.3 Postprocessing vs. Dynamic Optimization

Back in the day, researchers tried the most straightforward approach—take a trained network, prune it, quantize weights, and see what happens. Even if this was done carefully, it was very frequently followed by a huge accuracy drop. Today, what is usually done is either fine-tuning or training where the pruning is scheduled, say, to start at the 50th epoch, and quantization is also added in the end. These techniques usually prolong the training phase but provide smaller and more computationally/energy-efficient NNs without a dramatic drop in accuracy.

Another important observation for optimization, which might seem counterintuitive, is that starting with an optimized NN (quantized, pruned, and low-rank approximation applied) and training it from scratch doesn’t usually work. It either ends up with poor accuracy (compared with an overparametrized NN) or it doesn’t converge at all. These results are more observational since there are is no proper theory supporting these processes yet.

9.4 Low-Rank Factorization

The key idea behind low-rank factorization is to replace matrix multiplications with more matrix multiplications. Sounds counterintuitive, right? The reason this works is that these new matrices are smaller. The number of operations during matrix multiplication AB, AϵR^M × N, BϵR^N × O is MNO multiplications and M(N − 1)O additions. For simplicity let’s take it as just MNO multiply-accumulation operations (MACs).

A well-known matrix decomposition method is singular value decomposition (SVD). A = UΣV^∗, UϵR^M × M, ΣϵR^M × N, VϵR^N × N. Σ is a diagonal matrix, and diagonal entries are called singular values. By construction these singular values can be placed in descending order. The compression technique is based on the fact that we can take only the first k singular values, thus reducing matrix sizes into UϵR^M × k, ΣϵR^k × k, VϵR^k × N. The magic happens when we do matrix multiplication: UΣVB. We start with VB, which is kNO MACs, and end up with matrix DϵR^k × O. We can have UΣ precomputed as matrix CϵR^M × k, then the CD multiplication will cost MkO MACs. The whole UΣVB with UΣ precomputed cost is kNO + MkO = kO(N + M).

Consider the last fully connected layer of VGG [16]. It has an input size of 4096 and an output size of 1000. What happens here is Wx + b,WϵR^{1000 × 4096}, xϵR^4096 × 1, bϵR^1000 × 1, where W is the weight matrix, x is input, and b is the bias term. When W is decomposed a reasonable k is chosen. For k = 800 there is almost zero gain because the original multiplication will cost 4.096 M MACs, and with decomposition it will be 4.076 M. For k = 400 we need only 2.038 M MACs—a 2 × savings. The memory requirements will also be smaller. From NM (4.096 M) weights going down to kN + kM (for k = 400; it is the same as 2.038 M MACs). The reason memory is the same as MACs is that we are multiplying by a vector, thus O = 1.

This approach is good to follow as it has a fine-tuning phase compensating for a possible drop in accuracy. In the end one FC layer will be replaced by two smaller layers. The first has an input size of 4096, an output size of k, and no bias term. The second layer has an input size of k, an output size of 1000, and a bias term b.

Other techniques take this idea even further. There are more optimal approaches than SVD—a good example is Fastfood kernel decomposition [40, 41]. It is applied only to matrix multiplications. When we speak about convolution we are dealing with tensor multiplication (tensor is a more general concept than matrices and vectors). 4D tensor multiplication usually takes place in convolution. Similar to SVD decomposition are Tucker decomposition [42] and CP decomposition [43]. However, they take place in the higher dimensional space used for NN compression.

9.5 Architecture Design

As is known, fully connected layers consume a lot of memory, but convolutions stress the processing resources. Another way to save resources is to design the architecture with optimality in mind. In the field of CNNs there are networks, such as FD-MobileNet [44] and ShuffleNet [45], doing exactly this. One recent trend is not to use fully connected layers as they are prone to overfitting and have many parameters resulting in a big memory footprint.

There are several ideas related to convolution layers. Probably one of the first was published in [46]. This involved an NN architecture called SqueezeNet where 1 × 1 convolutional kernels are applied before more complex 3 × 3 convolution layers to reduce the number of input channels. The authors showed comparable accuracy with AlexNet, but with fewer parameters. At first sight 1 × 1 convolutional kernels might seem like a nonsense. What they do though is to combine feature maps in the linear way. Usually, an activation is applied on top of them adding more nonlinearity into the system.

Another idea is the depthwise-separable filter, which was introduced as part of the MobileNets architecture [36]. The trick is in dividing the standard convolution layer into two steps. Instead of doing N-times convolution on all input features (where N is the number of filters) a convolution is done only once followed then by N 1 × 1 convolutions to end up with N separate feature maps. For example, a 3 × 3 depthwise-separable convolution (as used in [36]) uses between eight and nine times less computation than standard convolutions with only a small reduction in accuracy.

For further reading we suggest a paper about SqueezeNext that focuses on hardware-aware NN design [47].