A Survey on Methods and Theories of Quantized Neural Networks

Introduction

Since the success on the ImageNet dataset Krizhevsky et al. (2012), deep neural networks has drawn a huge amount of attention from academia, industry and media. Subsequent works show that deep neural network models can achieve the state-of-the-art results on many real-world tasks, such as computer vision He et al. (2016a), natural language processing Young et al. (2017) and speech recognition Hinton et al. (2012a). One constraint that hinders the wide use of deep neural network models is that it consumes a huge amount of memory to store the models. For example, AlexNet Krizhevsky et al. (2012) requires 200MB memory, VGG-Net Simonyan and Zisserman (2014) requires 500MB memory and ResNet-101 He et al. (2016a) requires 200MB memory. For mobile or embedded devices that do not have enough memory space, it is hard to deploy these models into production stack. Quantization is a potential solution to this problem. Quantized neural networks represent weights, activations or even gradients with a small numbers of bits, such as 8 bits or even 1 bit. In this way, we can effectively shrink the model size and accelerate both the training and the inference procedures.

Quantizing neural networks dates back to the 1990s Fiesler et al. (1990); Balzer et al. (1991); Tang and Kwan (1993); Marchesi et al. (1993). In the early days, the main reason to quantize these models is to make it easier for digital hardware implementation. Recently, the research of quantizing neural networks has revived due to the success of deep neural networks and their huge sizes. A slew of new quantization methods and methodologies have been proposed. These efforts have enabled the quantized neural networks to have the same accuracy level as their full-precision counterparts. In this paper, we give a thorough survey on methods and approaches of quantized neural networks. We also discuss the challenges of quantizing neural networks and address future trends.

The rest of the paper is organized as follows: Section 2 gives background on neural networks and specially on quantized neural networks. Section 3 introduces some common quantization methods. In section 4, we discuss the quantization of different network components. In section 5, we compare two types of quantization methodologies. Section 6 gives some case studies. Section 7 discusses about why quantized neural networks work well in practice. In section 8 we discuss possible future directions of quantized neural networks.

Background

If there are $m$ neurons in layer $l-1$ and $n$ neurons in layer $l$, with fully-connected layer the weights between the two layers are represented as an $m\times n$ matrix. This matrix consumes a large amount of memory when $m$ or $n$ is too large. For example, if a gray-scale input image of the neural network is of size $256\times 256$ and the first hidden layer has $512$ neurons. Storing the weight matrix with floating-point numbers requires 128M memory. In practice, the images are much larger than this example so a fully-connected layer cannot scale well.

1.2 Convolutional Neural Networks

Convolutional neural network (CNN) is a type of artificial neural network that has been successfully applied in many areas, especially in visual imagery LeCun et al. (1998). A convolutional neural network consists of three building blocks: convolutional layer, pooling layer and fully-connected layer. A simple convolutional neural network is shown in Fig 2.

Convolutional layer is a major building block of CNNs. It is used to extract features from images. In each convolutional layer we have a set of filters. During the forward pass, we slide each filter across the image and compute dot products between the filter and the local receptive field. The output of the convolutional layer is called activation map that gives the response of each filter. Given an image $I$ and a $m\times n$ filter $F$, an element $a_{i,j}$ in the activation map can be computed as,

The convolution operation is computationally very expensive. For example, the total time complexity of all convolutional layers can be expressed as $O(\sum_{l=1}^{d}n_{l-1}\cdot s_{l}^{2}\cdot n_{l}\cdot m_{l}^{2})$ He and Sun (2015). Here $l$ is the index of a convolutional layer and $d$ is the number of convolutional layers. $n_{l}$ is the number of filters in the $l$-th layer. $n_{l-1}$ is the number of input channels of the $l$-th layer. $s_{l}$ is the spatial size of the filter. $m_{l}$ is the spatial size of the activation map. The computational cost of the convolutional layer motivates us to use low bit-width filters and inputs. With low bit-width filters and inputs, the dot product can be efficiently implemented by bitwise operations which can greatly accelerate the computation.

The success of Alexnet Krizhevsky et al. (2012) at ILSVRC 2012 spawned a lot of novel CNN architectures. In this paper, we focus on the following four CNN architectures,

The performance of these models is impressive, however their huge size hinders them from being widely used. This motivates researchers to develop quantization methods to further reduce the model size. The four architectures are widely used as baselines to compare the effectiveness of different quantization approaches. The specifications of these models are given in Table 1. More details can be found in the corresponding papers.

1.3 Recurrent Neural Networks (RNNs) and LSTM

Recurrent neural networks (RNNs) and Long Short-Term Memory (LSTM) Hochreiter and Schmidhuber (1997) are used to model the dynamics of sequences. Different from feed-forward neural networks and convolutional neural networks (CNNs), RNNs and LSTM may include loops that are used to consider the previous computations. An example of RNN is shown in Fig 3. The motivation to quantize RNNs and LSTM is not fundamentally different from quantizing feed-forward neural networks and CNNs. In order to achieve satisfactory performances, we need millions of parameters to model complex sequential relations Amodei et al. (2016) which makes it infeasible to deploy these models into embedded or mobile devices.

2 Quantized Neural Networks

The research of quantized neural networks has attracted a lot of attention from the deep learning community Courbariaux et al. (2015); Rastegari et al. (2016); Zhou et al. (2017a). The goal of quantization is to compact the models without performance degradation. Achieving this goal calls for joint solutions from machine learning, optimization computer architecture, and hardware design, etc. With quantized neural networks, we can use bitwise operations rather than floating-point operations to perform the forward and back-propagation. A simple example is that for two binary vectors, their dot product can be computed as follows,

where bitcount() is a function that counts the number of 1s in a binary vector. We can also save energy with quantized neural networks. The computational operations in quantized neural networks are typically bitwise operations which are carried out by the arithmetic logic unit (ALU). An ALU consumes much less energy than a floating-point unit (FPU). For mobile applications where power consumption is critical, a quantized neural network is preferable over its full precision counterpart.

A lot of techniques have been proposed recently to quantize neural networks. Broadly speaking, these techniques can be classified into two types: deterministic quantization and stochastic quantization. In deterministic quantization, there is an one-to-one mapping between the quantized value and the real value. While in stochastic quantization, the weights, activations or gradients are discretely distributed. The quantized value is sampled from the discrete distributions.

There are three components that can be quantized in a neural network: weights, activations and gradients. The motivation and methods to quantize these components are slightly different. With quantized weights and activations we get smaller model size. In a distributed training environment, we can save communication cost with quantized gradients. Generally, it is more difficult to quantize the gradients than quantizing weights and activations since high-precision gradients are needed to make the optimization algorithm converge.

We use quantization codebook to denote the set of discrete values used to represent the real values. From the perspective of quantization codebook, the works on quantized neural networks can be roughly classified into two categories: fixed codebook quantization and adaptive codebook quantization. In fixed codebook quantization, the weights are quantized into some predefined codebook while in adaptive codebook quantization the codebook is learned from the data. Some commonly used codebooks are $\{-1,1\}$, $\{-1,0,1\}$ or power-of-two numbers, which provides binary network, ternary network and power-of-two network separately.

The recent quantized neural networks have achieved accuracy similar to their full-precision counterparts. For example, a binary network Courbariaux et al. (2015) can obtain 98.8% accuracy on the MNIST dataset. For large datasets such as ImageNet, a ternary network Zhu et al. (2016) can obtain comparable performance to the full-precision network. However, there are still several challenges need to be addressed. Training quantized networks needs more tuning and the working mechanism of quantized networks are not well understood. Exploring new quantization methods and developing theories for quantized neural networks are important.

Quantization Techniques

Rounding is possibly the simplest way to quantize real values. In Courbariaux et al. (2015), the authors proposed the following deterministic rounding function,

where $x^{b}$ is the binarized variable and $x$ is the real-valued variable. This function can produce binarized weights, activations or gradients. During forward propagation, the real-value weights are quantized via the Sign(x) function and the quantized weights are used to generate the outputs. However, during back-propagation we cannot back-propagate the errors through the Sign(x) function since the gradients are zero almost everywhere. The usual strategy is to use “straight-through estimator” (STE) Hinton et al. (2012b) which is a heuristic way to estimate the gradient of a stochastic neuron. Assume $E$ is the loss function, with STE the forward and backward computations of above rounding function are as follows,

where $\textnormal{I}_{|x|\leq 1}$ is an indicator function defined as,

In order to round a floating-point number to the nearest fixed-point representation, in Gupta et al. (2015) the authors proposed the following rounding scheme,

In a fixed-point representation, IL represents the number of integer bits and FL represents the number of fractional bits. $\epsilon$ is the smallest positive number that can be represented in this fixed-point format. $\lfloor x\rfloor$ is defined as the largest integer multiple of $\epsilon$. For values that are beyond the range of this fixed-point format, the authors normalized them to either the lower or the upper bound of the fixed-point representation. Rastegari et al. (2016) extended Equation (4) as follows,

where $\textnormal{E}_{F}(|x|)$ is the mean of absolute weight values of each output channel. In Zhou et al. (2016), instead of doing a channel-wise scaling, the authors replaced $\textnormal{E}_{F}(|x|)$ with a constant scalar for all the filters.

More recently, Polino et al. (2018) proposed a general rounding function,

where $sc(x)$ is a scaling function which maps the values from arbitrary range to the values in . $\hat{Q}(x)$ is the actual quantization function. Given a quantization level parameter $s$, the uniform quantization function with $s+1$ levels can be defined as,

The intuition of this quantization function is that $x$ will be assigned to the nearest quantization point of $s-1$ equally spaced points between 0 and 1. This a generalized version of the Sign(x) function and can be used to quantized the real values into multi-levels. In Shuang et al. (2018), the authors proposed a heuristic rounding function to quantize a real value to a k-bit integer,

The idea is to quantize real values with uniform distance $\sigma(k)$, where $\sigma(k)=2^{1-k}$. $Clip$ restricts the quantized values in the range of $[-1+\sigma(k),1-\sigma(k)]$ and $round$ replaces the continuous values with their nearest discrete points.

Challenges: Use a rounding function is an easy way to convert real values into quantized values. However, the network performance may drop dramatically after each rounding operation. It is necessary to keep the real values as reference during training which increases the memory overhead. Meanwhile, since the parameter space is much smaller if we use discrete values, it is harder for the training process to converge. Finally, rounding operation cannot exploit the structural information of the weights in the network.

1.2 Vector Quantization

To the best of our knowledge, Gong et al. (2014) is the first paper to systematically consider using vector quantization to quantize and compress neural networks. The basic idea of vector quantization is to cluster the weights into groups and use the centroid of each group to replace the actual weights during inference.

For a weight matrix $W\in R^{m\times n}$, we can perform k-means clustering to do vector quantization,

where $c_{k}$ is the centroid. After clustering, each weight is assigned to a cluster index. Although this is a simple approach, the authors showed that on the ImageNet dataset Deng et al. (2009), this method can achieve 16 $\sim$ 24 times compression of the network with only 1% loss of classification accuracy using the state-of-the-art CNNs. In Han et al. (2015), the authors adopted a similar approach to Gong et al. (2014) except that after clustering, they retrained the network to fine-tune the quantized centroids.

While simple and effective, Choi et al. (2016) pointed out the above quantization method have two drawbacks. The first one is that we cannot control the loss of accuracy caused by the k-means clustering. The second is that k-means clustering does not impose any compression ratio constraint. To solve the problems, the authors proposed a Hessian-weighted k-means clustering approach. The basic idea is to use the Hessian-weighted distortion to measure the performance degradation that will be caused by the quantization of weights. In this way, those weights have an large impact on the performance of the network are prevented from deviating from their original values too much.

There are many extensions to vector quantization. For example, product quantization Gong et al. (2014) is a way that partitions the weight matrix into many disjoint sub-matrices and performs quantization in each sub-matrix. In Wu et al. (2016), the authors adopted product quantization with error correction to quantize network parameters to enable fast training and testing. Residual quantization Gong et al. (2014) quantizes the vectors into $k$ clusters and then recursively quantize the residuals. In Park et al. (2017), the authors adopted a way which is similar to vector quantization. They used an idea based on weight entropy Guiaşu (1971) to group weights into $N$ clusters. There are more clusters for important ranges of weights. In this way, they can achieve automatic and flexible multi-bit quantization.

Challenges: Due to the number of weights in the network, the computation of the k-means clustering is expensive. Compared with rounding methods, it is hard to use vector quantization to achieve binary weights. Vector quantization is typically used for quantizing pre-trained models. Hence, if the task is to train a quantized network from scratch, it is preferable to use a carefully designed rounding functions. Vector quantization ignores the local information of the network.

1.3 Quantization as Optimization

Recently, a number of works have considered formulating the quantization problem as an optimization problem. In XNOR-net Rastegari et al. (2016), in order to find the best binary approximation to the real-value filters, the authors solved the following optimization problem,

where $W$ is a real-value filter, $B$ is the binary filter and $\alpha$ is a positive scaling factor. The optimal $B$ and $\alpha$ are given as follows,

where $n$ is the number of the elements in the filter. Interestingly, this gives a result similar to Equation (3) except that in this case there is an additional scaling factor.

In Li et al. (2016), the authors relaxed the binary constraint to ternary values and solved the following optimization problem,

In this way, higher accuracy can be achieved compared to XNOR-net Rastegari et al. (2016). Instead of fixing the codebook in ternarization, in Zhu et al. (2016) the authors used a trained quantization method to learn the ternary values which gives the network more flexibility. In Mellempudi et al. (2017), the authors introduced multiple scaling factors into ternary network to account for the unsymmetry between positive and negative weights. In Wang and Cheng (2017), the authors proposed the following semi-discrete decomposition for a weight matrix $W\in R^{m\times n}$:

where $X\in\{-1,0,+1\}^{m\times k}$, $Y\in\{-1,0,+1\}^{n\times k}$ and $D\in R^{k\times k_{+}}$ is a nonnegative diagonal matrix. By choosing different $k$, we can make a trade-off between compression ratio and performance loss.

A different type of approach is to minimize the loss function directly with respect to the quantized weights. In Hou et al. (2016), the authors considered the effect of binarization on the loss function during training and proposed a loss-aware binarization algorithm. They formulated the binarization problem as the following optimization problem:

where $E$ is the loss function and $n_{l}$ is the number of the parameters in layer $l$ and $L$ is the number of layers. The problem then is rewritten to a formulation that can be solved by proximal Newton method.

In Carreira-Perpinán and Idelbayev (2017), the authors formulated the quantization problem as following non-convex optimization problem,

where w is the real-valued weights and $\hat{\textbf{w}}$ is the quantized weights. $E(\hat{\textbf{w}})$ is the loss function of the quantized network and $\Delta$ is a quantization function that converts real-valued weights to discrete values. As compared to Hou et al. (2016), this is a more general setting since it allows us to use different quantization functions. Then they used the “learning-compression” algorithm to train the network. In Leng et al. (2017), the authors formulated the quantization problem as a discretely constraint non-convex optimization problem and used the idea of Alternating Direction Method of Multipliers (ADMM) to decouple the continuous variables from the discrete constraints. The optimization problem is formally defined as,

The authors further introduced a scaling factor to each layer to expand the constraint space. Then the problem is converted into a form that can be solved by ADMM. More recently, Lu Hou (2018) extended Hou et al. (2016) to loss-aware ternarization and $m$-bit quantization. The authors also used proximal Newton algorithm and obtained a closed-form update for the optimization problem.

In Zhou et al. (2017b), the authors considered the problem of finding the optimal quantized representation for each layer. Later in the work of Soroosh Khoram (2018) the authors proposed an adaptive quantization method which incorporates the loss function into an optimization problem to consider the importance of different connections. The optimization problems is as follows,

where $N_{q}(w_{i})$ is the minimum number of bits used to represent $w_{i}$ and $N_{Q}(\textbf{w})$ is the total number of bits in the network. $\bar{E}$ is used to bound the accuracy loss. The intuition is to use more precise representation for important weights while allocating few bits for unimportant weights. Different from above works, the work in Deng et al. (2017) proposed gated XNOR networks which use discrete state transition method to optimize the weights in discrete space.

Challenges: The convergence of the proposed optimization algorithms relies on weak assumptions which may not hold for deep neural networks. This makes the theoretical analysis of these algorithms not very convincing. Some of the methods need second-order information for updating the weights which leads to high computational complexity. From a practical perspective, it calls for more efforts to implement the proposed optimization algorithms which hinders their widespread use.

2 Stochastic Quantization

In random rounding, the real value has no one-to-one mapping to the quantized value. Typically, the quantized value is sampled from a discrete distribution which is parameterized by the real values. For example, in Courbariaux et al. (2015) the authors proposed the following random rounding function,

where $\sigma$ is the ”hard sigmoid” function:

The intuition is that if $x$ is a positive value, we will have a high probability to quantize it to +1, otherwise to -1. This gives us a more flexible quantization scheme. In Muller and Indiveri (2015) the authors used the idea in integer programming. The proposed random rounding function maps each real value probabilistically to either the nearest discrete point or to the second nearest discrete point based on the distance to the corresponding point. In Lin et al. (2015), the authors extended binary random rounding to the ternary case. They first split the interval $$into two sub-intervals:$$ and $(0,1]$. If the real-valued weight $w$ is in $$, then the weight is quantized as follows,

The case for $w$ $\in$ $(0,1]$ is similar. In Polino et al. (2018), the authors also proposed a random rounding scheme based on Equation (7). In this case, we sample $\xi\sim Bernoulli(xs-\lfloor xs\rfloor)$. This allows us to quantize the real values to multi-levels probabilistically. One important property of this random rounding function is that it is an unbiased estimator of the input, which means that $E(Q(x))=x$. This reveals that this random rounding method equals to add noises into the training process.

Challenges: Random rounding provides a way to inject noises into the training process. It can act as a regularizer and enable conditional computation. However, with random rounding methods we need to estimate the gradient of the discrete neurons. Such estimation often has a high variance. This fact may cause oscillations in the loss function during training. The work of Bengio et al. (2013) provides an overview of possible solutions for estimating gradients for discrete neurons.

2.2 Probabilistic Quantization

The weights in a trained network often follow some distributions. Figure 4 shows the histogram of weight values in the LeNet LeCun et al. (1998) after trained on MNIST dataset. It is obvious that most of the weight values are close to zero and the distribution is roughly Gaussian. The behavior of the weights inspired researchers to quantize the network from a probabilistic perspective.

In probabilistic quantization, the weights are assumed to be discretely distributed. A learning algorithm is used to infer the parameters of the distributions. In Soudry et al. (2014), the authors developed the Expectation Back-propagation algorithm to train neural networks with binary or ternary weights. They first assumed some discrete prior distribution on the weights $p(\textbf{w}|D_{0})$, and then updated the weights in an online setting based on the Bayesian formula,

Above update rule is intractable in general, the authors adopted mean-field approximation and the Central Limit Theorem (CLT) to obtain an approximated solution.

In Shayar et al. (2017), the authors assumed that each weight is sampled independently from a multinomial distribution and the loss function of the network is as follows,

This function is not differentiable due to the discreteness. The authors used local reparameterization trick Kingma et al. (2015) and the Central Limit Theorem (CLT) to approximate the discrete distributions by a smooth Gaussian distribution. In this way, the gradients can be back-propagated through the discrete nodes.

Another type of probabilistic quantization is based on variational inference Jordan et al. (1999). The main idea is to place a quantizing prior on the weights and then use variational inference to obtain the discrete posterior distribution of the weights. Assume a dataset $D=(x_{n},y_{n})^{N}_{n=1}$ and let $p(Y|X,\textbf{w})$ be a parameterized neural network model that predicts outputs $Y$ given inputs $X$ and parameters w. In Bayesian neural networks, we want to estimate the posterior distribution of the weights given the data: $P(\textbf{w}|D)=p(D|\textbf{w})p(\textbf{w})/p(D)$. $P(\textbf{w})$ is the prior distribution of the weights. To analytically solve the true posterior is intractable. One approach is to use variational inference algorithm to approximate the true posterior. The true posterior distribution is approximated by a parameterized distribution $q_{\phi}(\textbf{w})$. To find $q_{\phi}(\textbf{w})$, we need to minimize the Kullback-Leibler divergence between the true and the approximated posterior distribution: $D_{KL}(q_{\phi}(\textbf{w})||p(\textbf{w}|D)$. This optimization problem can be further converted to maximize the following “evidence lower bound” (ELBO),

The first term of the right-hand side of Equation (21) is the negative of reconstruction error, which means that maximize this term will ensure good predictive performance. The second term of the right-hand side of Equation (21) regularizes the approximated posterior to be close to the prior distribution.

Traditional Bayesian neural networks do not involve quantization. In Kingma et al. (2015), the authors connected the variational training of Bayesian neural networks with dropout Srivastava et al. (2014). In dropout training, Bernoulli noises or Gaussian noises are added to the weights. In traditional dropout training, the dropout rate $p$ is fixed. Kingma et al. (2015) shown that adding multiplicative noise on weights is equivalent to learn adaptive dropout rate for each weight. If we add a Gaussian noise $\xi_{ij}\sim N(1,\alpha=\frac{p}{1-p})$ on each weight, then the weight is distributed as follows:

In a Bayesian neural networks setting, the gradient of the weights can be computed as,

where $\hat{\xi}\sim N(\xi|1,\alpha I)$. The gradient of ELBO with respect to the weights is Equation 25 plus the gradient of the KL divergence term. To exactly recover the ELBO loss, Kingma et al. (2015) adopted a prior distribution on the weights which makes the KL divergence term in Equation 23 does not depend on $\theta$ but on $\alpha$. This allows us to learn different dropout rates for different weights. Molchanov et al. (2017) shown that we can prune the weights that have high dropout rates and still achieve good predictive performance.

In Jan Achterhold (2018), the authors introduces a ”multi-spike-and-slab” prior which has multiple spikes at locations $c_{k}$, $k\in{1...K}$. After training, they found that most weights of low variance are distributed very closely around the quantization target values $c_{k}$ and can thus be replaced by the corresponding $c_{k}$ without significant loss in accuracy. Weights of large variance can be pruned.

Challenges: Probabilistic quantization can leverage the benefits of Bayesian neural networks which leads to very sparse models. However, it relies on a carefully chosen prior distribution of the weights and the model is often intractable. Meanwhile, some types of neural network models, such as recurrent neural networks, cannot be quantized under this framework.

3 Discussion

The above quantization techniques enable us to quantize neural networks from different perspectives. We summarize all the techniques in Table 5. The merits and drawbacks of these techniques can guide us to select the proper one in different situations. In general, deterministic quantization should be preferred if we want to quantize neural networks for hardware accelerations since we can specify the appropriate quantization levels in advance in order to run the quantized networks on dedicated hardware. This can give us predictive performance improvement on hardware. Round rounding enables us to quantize the weights in a data-dependent manner. This leads to conditional computation Bengio et al. (2013) that can increase the capacity of neural networks. Probabilistic quantization differs from deterministic quantization in that the quantized weights are more interpretable. We can understand the distributions of the weights with probabilistic quantization and gain more insights into how the network works. With probabilistic quantization, we can also have sparser models due to regularization effects of the Bayesian methods.

Quantization of Network Components

The motivation to quantize weights is clear: to reduce model size and accelerate training and inference process. Most of the methods we talked above can be used to quantize weights. In this section, we introduce more weight quantization strategies that we did not cover before.

Anwar et al. (2015) proposed a layer-wise quantization scheme to reduce the performance degradation. In Kim and Smaragdis (2016), the authors adopted a two-step pipeline. In the first step, the weights are compressed into the range of $$ and in the second step the compressed weights are used to initialize the parameters of a binary network. In Zhou et al. (2017a), the authors proposed incremental network quantization (INQ) which consists of three steps: weight partition, group-wise quantization and re-training. They quantized the weights in a group-wise manner to allow some groups of weights to compensate the accuracy loss due to the quantization of other groups. The work in Gudovskiy and Rigazio (2017) extended this method to power-of-two setting.

In Lin et al. (2016) the authors tried to find the optimal fixed point bit-width allocation across layers. They examined how much noise can be introduced by quantizing different layers. Lin et al. (2017) approximated the full-precision weights with a linear combination of multiple binary bases. The results show that it is the first time that a binary neural network can achieve prediction accuracy comparable to its full-precision counterpart on ImageNet dataset. In Moons et al. (2017), the authors studied how to develop energy efficient quantized neural network. The work in Guo et al. (2017) introduced network sketching to quantize a pre-trained model. The idea is to use binary basis to approximate pre-trained filters. They first proposed a heuristic algorithm to find the binary basis and then provided a refined version to better approximation. In Mohamed Amer (2018), the authors proposed an end-to-end training framework to optimize original loss function, quantization error and the total number of bits simultaneously. However, the accuracy is not comparable to other quantized neural networks.

Quantized weights make neural networks harder to converge. A smaller learning rate is needed to ensure the network to have good performance Shuang et al. (2018). Determine how to control the stability of the training process in a quantized neural network with quantized weights is critical.

Quantized weights make back-propagation infeasible since gradient cannot back-propagate through discrete neurons. Approximation methods are needed to estimate the the gradients of the loss function with respect to the input of the discrete neurons. Developing low-variance, unbiased gradient estimates is essential for the success of weight quantization.

It is known that the weights in neural networks often follow some general structures. For an approach that trains quantized networks from scratch, how to quantize the weights locally while maintain their global structure is an issue.

2 Activation Quantization

Quantized activations can replace inner-products with binary operations which can further speed up the network training. We can also reduce the much memory by avoiding full-precision activations. Vanhoucke et al. (2011) quantized the activations to 8 bits. They used a sigmoid function which limits the activations to the range of and quantized the activations after training the network. In Courbariaux et al. (2015); Rastegari et al. (2016); Zhou et al. (2016) the authors adopted a similar approach. They introduced a continuous approximation of the non-differentiable operator during back-propagation to enable the gradients can back-propagate through the discrete neurons. More recently, Cai et al. (2017) proposed an half-wave Gaussian quantizer to approximate the ReLU unit. In the forward approximation, they used a half-wave Gaussian quantization function,

If use mean squared error to measure the performance, the optimal quantizers can be found as follows,

They used batch normalization Ioffe and Szegedy (2015) and Lloyd’s algorithm to find the optimal solution. During back-propagation, they further introduced three possible approximation method to avoid the gradient vanishing problem.

In Mishra et al. (2017), the authors proposed wide reduced-precision networks (WRPN) to quantize activation and weights. They found that activations actually occupy more memory than weights. They adopted a strategy that increases the number of filters in each layer to compensate the accuracy degradation due to quantization.

There are some reasons that make the quantization of activations more difficult than that of weights Cai et al. (2017). The first one is that we need to back-propagate through the non-differentiable operators. Consider the back-propagation equation,

When we replace $g(a_{j})$ with a binary operator, the derivative $g^{\prime}(a_{j})$ is almost zero everywhere which makes gradient descent algorithm infeasible.

The quantized activations can lead to “gradient mismatch” problem Lin and Talathi (2016) which means that there is a discrepancy between the quantized activation with the computed backward gradient.

3 Gradient Quantization

Gradient quantization is a new branch of research in quantization of neural networks. The motivation to quantize gradients is to reduce the communication cost during distributed stochastic gradient descent (SGD) training of large neural networks.

In a distributed SGD training, one case is that each mini-batch data is spread over multiple computing nodes, this is called data-parallel training as shown in Fig 5 (a). Each node has a copy of the weights and need to compute a sub-gradient, and then broadcast its sub-gradient to all other nodes. Each node must accumulate the sub-gradients from other nodes to update the weights. This process causes a significant performance bottleneck because of the exchange of gradients. To solve this problem, Seide et al. (2014) proposed to use 1-bit to represent the sub-gradient. This can reduce the bandwidth greatly. The authors reported a ten times speed-up compared with traditional approaches without a great loss in accuracy. In Strom (2015) the authors proposed a threshold quantization method to quantize gradients. A fixed threshold is selected in advance. Gradients that are greater than the threshold are quantized to +1, and those less than the threshold are quantized to 0. Alistarh et al. (2016) also considered the problem of gradient communication in the parallel SGD. They proposed Quantized SGD (QSGD) to allow each node to make a trade-off between the precision the gradients with the accuracy of the model. QSGD used the idea of random rounding to quantized the gradients to a set of discrete values and utilized lossless code to generate efficient encoding. In Dryden et al. (2016), the authors proposed a simple adaptive quantization method to select a proportion of gradients to be quantized and sent.

In a different setting, there is a centralized parameter server that performs gradient synchronization by accumulating all sub-gradients and averaging them to update the weights. This is called model-parallel training as shown in Fig 5 (b). The updated weights are sent back to each node to do computation. As the number of nodes increases, the communication cost becomes intolerable. Wen et al. (2017) addressed this problem by introducing a method called TernGrad that quantizes the gradients into three levels $\{-1,0,1\}$. Before being sent to the centralized parameter server, each sub-gradient is quantized as follows,

where $s_{t}=\textnormal{max}(\textnormal{abs}(\Delta_{t}))$, $\circ$ is the Hadamard product and $b_{t}$ is a random binary vector that follows a Bernoulli distribution,

In this way, th communication cost between the server and workers can be reduced by about 20 $\times$ compared with sending full-precision gradients.

In a single-machine environment, we can also gain benefits by quantizing gradients. In order to reduce the computational cost in the backward pass, the work in Rastegari et al. (2016) quantized the gradients into 2-bits to enable an efficient training process. In Zhou et al. (2016), the authors also quantized the gradients during back-propagation. They found that using a random rounding method is very important to make quantized gradients work well. They designed the following $k$-bit quantization function,

where $dr=\frac{\partial c}{\partial r}$ is the gradient of the output $r$ in some layer and $\textnormal{quantize}_{k}$ is used to quantize a real number input $r_{i}\in$ into a $k$-bit output number $r_{o}\in$,

They also added additional noises during the training process to compensate for the loss of accuracy due to quantization.

The magnitude and sign of gradients are both important for updating the weights. To quantize gradients, we must address the question of how to take both factors into account.

A naive way to quantize gradients may not work well in practice since it may violate the conditions needed for stochastic gradient descent algorithm to converge. More sophisticated methods are needed in this case.

4 Discussion

We summarize the benefits and challenges of quantizing different network components in Table 3. Achieving highly efficient quantized neural networks calls for a systematic solution to quantize weights, activations and gradients. Quantized weights and activations occupy less memory compared with full-precision counterparts. Meanwhile, the training and inference speed can be greatly accelerated since the dot-products between weights and activations can be replaced by bitwise operations. Quantized gradients can reduce the overhead of gradient synchronization in parallel neural network training. In a single worker scenario, quantized gradients can accelerate back-propagation training as well as requiring less memory.

A Comparison of Two Quantization Methodologies

In fixed codebook quantization, the codebook is predefined. For example, Courbariaux et al. (2015) quantized the weights of the network to $\{-1,1\}$. Hwang and Sung (2014) assumed the codebook is $\{-1,0,1\}$. In Rastegari et al. (2016), the authors further relaxed the constraints to quantize the weights to $\{a,-a\}$. In a more general setting, the weights are quantized into power-of-two numbers that can make the digital implementation of neural networks much faster Tang and Kwan (1993); Gudovskiy and Rigazio (2017).

In order to achieve fixed codebook quantization, we must define a codebook first. How the codebook is designed has a dramatic impact on the performance of the quantized network. A small codebook means that we can only search the parameters in a limited space, which makes the optimization problem very hard. With predefined codebook, it is sometimes necessary to modify the backward step to enable the gradients flow through the discrete neurons. This causes the “gradient mismatch” problem as we discussed in Section 4.2. Approximation is often needed in this case.

2 Adaptive Codebook Quantization

In adaptive codebook quantization, the codebook is learned from the data. Vector quantization and probabilistic quantization are two possible methods to achieve adaptive codebook quantization. In vector quantization, in order to learn the codebook, we must let the real values minimize some sort of distortion measure and cluster them into different buckets. In probabilistic quantization, the codebook can be inferred from the posterior distributions of the weights.

Two kinds of adaptive codebook quantization exist: hard quantization and soft quantization. In hard quantization, the real value is assigned exactly to be one of the discrete values. In soft quantization the real value is assigned to be some discrete value according to a probability distribution. The soft quantization is mostly inspired by the idea of weight sharing Nowlan and Hinton (1992) in which the distribution of weight values is modeled as a mixture of Gaussians. Adaptive quantization is more flexible than fixed codebook quantization but the final codebook may need more bits to represent. The benefit of adaptive quantization is that it can avoid ad hoc modifications to the training algorithm.

Quantized Neural Networks: Case Studies

Neural networks can be quantized during and after training. In this section we introduce some recently proposed quantized neural networks that utilize these this perspective.

BinaryConnect Courbariaux et al. (2015) BinaryConnect is a method that leverages binary weights during the forward and backward pass. As far as we known, it is the first time that a binary network can achieve near state-of-art results on datasets such as MNIST and CIFAR-10. BinaryConnect uses the Sign(x) function to binarize the weights during the forward pass. The real-valued weights are also kept to do parameter update in the backward pass. The algorithm is shown in Algorithm 1.

XNOR-Net Rastegari et al. (2016) XNOR-Net is the first attempt to present an evaluation of binary neural networks on large-scale datasets like ImageNet. They use a different binarization method compared with BinaryConnect. XNOR-Net binarizes inputs, weights, activations and gradients together which can greatly accelerate the network training and inference process. XNOR-net binarizes the gradients in the backward pass with a slightly drop in accuracy. The algorithm is shown in Algorithm 2.

DoReFa-Net Zhou et al. (2016) DoReFa-Net further improves XNOR-net by using more sophisticated rounding mechanism. They claim that it is the first time that during the backward pass quantized gradients with less than 8 bits can work successfully. DoReFa-Net can binarize weights, activations and gradients to arbitrary bit-width. The forward pass and backward pass can both be greatly accelerated. We omit the details of the algorithm here due to space limitation.

ABC-Net Tang et al. (2017) In ABC-Net, the authors studied carefully why the previous binary networks may fail. And they proposed following strategies to alleviate the potential problems,

Use a smaller learning rate to prevent the frequent changes of the directions of weight values.

Use PReLU He et al. (2015) rather than ReLU as the activation function.

Use the following regularization function rather than a $L_{2}$ regularization,

where $L$ is the number of layers. $N_{l}$ and $M_{l}$ are the dimensions of the weight matrix in layer $l$.

In order to successfully quantize the final layer, the authors also added an additional scale layer after the binarized final layer to improve the compression rate of the algorithm.

Figure 6 shows the general procedures of quantizing neural networks during training. It can be noted that the full-precision weights must be saved in the training phase which can cause a large memory overhead.

2 Quantization After Training

DeepCompression Han et al. (2015) DeepCompression is a three stage pipeline that can reduce the memory requirement of network by 35$\times$ to $49\times$ without accuracy degradation. The algorithm first prunes the unimportant connections. Then the remaining weights are quantized to discrete values. Finally, Huffman coding is used to encode the weight values. Figure 7 shows the pipeline of DeepCompression,

In order to compensate the loss of accuracy, DeepCompression also retrains the remaining connections and the quantized centroids. In this way, high compression rate can be achieved while maintaining a good network performance.

Entropy-constrained scalar quantization (ECSQ) Choi et al. (2016) Entropy-constrained scalar quantization (ECSQ) was proposed to improve the performance the vector quantization in 2016. In this work, the authors use the second-order information of the loss function to measure the importance of different weights. The loss function is expanded via Taylor series as follows,

where $H(\textbf{w})$ is the Hessian matrix. To connect Equation (34) with network quantization, the authors approximated the Hessian matrix as a diagonal matrix and treated $\delta\textbf{w}$ as the quantization error. The loss due to quantization can be expressed as,

Incremental network quantization (INQ) Zhou et al. (2017a) The work in Zhou et al. (2017a) proposed Incremental network quantization (INQ). INQ consists of three independent operations: weight partition, group-wise quantization and re-training. In the step of weight partition, the weights in each layer are divided into two groups. One group of weights are quantized while the another group of weights are kept with full-precision values. The network is retrained with the remaining full-precision weights to compensate for the loss due to quantization. This process is continued until all the weights are quantized. Compared with other quantization methods, this approach combines the benefits of quantizing during training and quantizing after training.

3 Performance Comparison of Different Quantized Neural Networks

We report the performance of different quantized neural networks in Table 5. All the results are directly taken from the original papers. The performance of quantized neural networks improved rapidly in the recent years and now can achieve near the state-of-the-art results on ImageNet with binarized weights. We have following observations,

We can achieve much higher accuracy with quantized neural networks if we use more bits to represent weights. In Shayar et al. (2017), the authors found that binary networks are much harder to train compared with a ternary counterpart.

In general, the methods that quantize networks after training obtain better results as compared with those that quantize during training. This is understandable since in the case of quantizing after training we have well pre-trained models as reference.

For some datasets and architectures, there is still a performance gap between the quantized neural networks and full-precision ones.

Why Does Quantization Work?

Deep neural networks have a huge number of parameters, but not all parameters are of equal importance. As pointed out in Denil et al. (2013), in the best cases more than 95% of the parameters in a neural network can be predicted without a drop in predictive performance. This means that we can use simpler parameterization to maintain the expressive power of deep neural networks. Recent work in model compression Molchanov et al. (2017) suggests that nearly 99% of weights can be pruned in some types of neural networks.

Deep neural networks are also robust to noise Sung et al. (2015); Merolla et al. (2016). Adding noise to weights or inputs sometimes can achieve better performance Srivastava et al. (2014). Random noise acts as regularizers which can potentially generalize the network better. In a quantized neural network, low-precision operations can be regarded as noise which may not hurt the network performance. Recent theories Li et al. (2017); Anderson and Berg (2017) suggest that quantized neural networks still maintain many important properties of full-precision ones which guarantees their performance.

Despite the success of many quantized neural networks on real datasets, the theoretical understanding is still very limited. Li et al. (2017) analyzes the convergence properties of stochastic gradient descent (SGD) when the weights are quantized. The authors analyzed the convergence property of BinaryConnect Courbariaux et al. (2015). They found that if we assume the loss function is L-Lipschitz smooth, the loss of the BinaryConnect network will converge at a rate linear in $\Delta$ to the loss of a full-precision network in expectation, where $\Delta$ is the resolution of the quantization function. The authors further gave some results on non-convex cases.

Anderson and Berg (2017) analyzed the properties of binarized neural network from a geometrical perspective. They found that the binarization operation preserves some important properties of the full-precision networks, i.e,

Angle Preservation Property: They found that binarization almost preserves the direction of full-precision high-dimensional vectors. The angle between a random normal vector with its binarized version converges to 37$\degree$.

Dot Product Proportionality Property: They showed that the dot products of the activations with the pre-binarization and post-binarization weights are approximately proportional to each other, i.e., $a\cdot w^{b}\sim a\cdot w^{c}$. Where $a$ is the activation of one layer, $w^{b}$ is the binarized version of full-precision weight $w^{c}$. $a\sim b$ means that $a=cb$, where $c$ is a scalar.

The implication is that although binarization may change the numerical values dramatically, the statistical properties of the forward computation are nearly kept.

Future of Quantized Neural Networks

Quantized neural networks make it practical to deploy deep neural network models into production stack. This enables embedded system based deep learning applications. However, there is still a large gap between the performance of quantized neural networks and full-precision neural networks. To bridge this gap, more sophisticated methods must be developed. Nearly all the works about quantized neural networks focus on feed-forward networks or convolutional neural networks and classification task. Recently, some researchers have looked at recurrent neural networks Ott et al. (2016); Hou et al. (2016); He et al. (2016b); Clark et al. (2017); Lu Hou (2018); Chen Xu and Zha (2018) and other tasks such as semantic segmentation Wen et al. (2016), video processing O’Connor and Welling (2016) and so on. We believe that the wide use of deep neural networks will drive researchers to develop more task-specific quantized neural networks.

We consider the following possible directions for the next steps:

Develop more sophisticated rounding mechanism to train quantized neural network from scratch. One possible approach is to use the structure information of the weights to guide the rounding process.

Design quantized neural networks for tasks such as natural language processing, speech recognition and so on. Due to the varieties of deep learning models, a generally applicable quantization method is necessary.

Develop theoretical guidance for quantizing neural networks.

Conclusion

In this paper, we have provided a comprehensive survey on the recent progress of quantized neural networks. We have traced back to the origins of the research of quantized neural networks and presented many newly developed methods. Both theories and applications of these methods are surveyed. We have pointed out some potential challenges in quantizing neural networks and have gave some general advice. We also identified several potential research directions. Quantized neural networks promote the application of deep learning models in mobile devices and embedded systems. We expect that they will make a significant impact in the future.

References