extfieldsofstudy:
Mathematics
Computer Science

text:
Fixed Point Quantization of Deep Convolutional Networks

In recent years increasingly complex architectures for deep convolution networks (DCNs) have been proposed to boost the performance on image recognition tasks. However, the gains in performance have come at a cost of substantial increase in computation and model storage resources. Fixed point implementation of DCNs has the potential to alleviate some of these complexities and facilitate potential deployment on embedded hardware. In this paper, we propose a quantizer design for fixed point implementation of DCNs. We formulate and solve an optimization problem to identify optimal fixed point bit-width allocation across DCN layers. Our experiments show that in comparison to equal bit-width settings, the fixed point DCNs with optimized bit width allocation offer>20% reduction in the model size without any loss in accuracy on CIFAR-10 benchmark. We also demonstrate that fine-tuning can further enhance the accuracy of fixed point DCNs beyond that of the original floating point model. In doing so, we report a new state-of-the-art fixed point performance of 6.78% error-rate on CIFAR-10 benchmark.

Abstract
In recent years increasingly complex architectures for deep convolution networks (DCNs) have been proposed to boost the performance on image recognition tasks. However, the gains in performance have come at a cost of substantial increase in computation and model storage resources. Fixed point implementation of DCNs has the potential to alleviate some of these complexities and facilitate potential deployment on embedded hardware. In this paper, we propose a quantizer design for fixed point implementation of DCNs. We formulate and solve an optimization problem to identify optimal fixed point bit-width allocation across DCN layers. Our experiments show that in comparison to equal bitwidth settings, the fixed point DCNs with optimized bit width allocation offer > 20% reduction in the model size without any loss in accuracy on CIFAR-10 benchmark. We also demonstrate that fine-tuning can further enhance the accuracy of fixed point DCNs beyond that of the original floating point model. In doing so, we report a new state-of-the-art fixed point performance of 6.78% error-rate on CIFAR-10 benchmark.

Introduction
Recent advances in the development of deep convolution networks (DCNs) have led to significant progress in solving non-trivial machine learning problems involving image recognition (Krizhevsky et al., 2012) and speech recognition (Deng et al., 2013). Over the last two years several advances in the design of DCNs (Zeiler & Fergus, 2014;Szegedy et al., 2014;Chatfield et al., 2014;He et al., 2014;Ioffe & Szegedy, 2015) have not only led to a further boost in achieved accuracy on image recognition tasks but also have played a crucial role as a feature generator for other machine learning tasks such as object detection (Krizhevsky et al., 2012) and localization (Sermanet et al., 2013), semantic segmentation (Girshick et al., 2014) and image retrieval (Krizhevsky et al., 2012;Razavian et al., 2014). These advances have come with an added cost of computational complexity, resulting from DCN designs involving any combinations of: increasing the number of layers in the DCN (Szegedy et al., 2014;Chatfield et al., 2014), increasing the number of filters per convolution layer (Zeiler & Fergus, 2014), decreasing stride per convolution layer (Sermanet et al., 2013; and hybrid architectures that combine various DCN layers (Szegedy et al., 2014;He et al., 2014;Ioffe & Szegedy, 2015).
While increasing computational complexity has afforded improvements in the state-of-the-art performance, the added burden of training and testing makes these networks impractical for real world applications that involve real time processing and for deployment on mobile devices or embedded hardware with limited power budget. One approach to alleviate this burden is to increase the computational power of the hardware used to deploy these networks. An alternative approach that may be cost efficient for large scale deployment is to implement DCNs in fixed point, which may offer advantages in reducing memory bandwidth, lowering power consumption and computation time as well as the storage requirements for the DCNs.
In general, there are two approaches to designing a fixed point DCN: (1) (Rastegari et al., 2016;Lin & Talathi, 2016), it requires tight integration between the network design, training and implementation, which is not always feasible. In this paper, we will mainly focus on the former approach. In many real-world applications a pre-trained DCN is used as a feature extractor, followed by a domain specific classifier or a regressor. In these applications, the user does not have access to the original training data and the training framework. For these types of use cases, our proposed algorithm will offer an optimized method to convert any off-the-shelf pre-trained DCN model for efficient run time in fixed point.
The paper is organized as follows: In Section 2, we present a literature survey of the related works. In Section 3, we develop quantizer design for fixed point DCNs. In Section 4 we formulate an optimization problem to identify optimal fixed point bit-width allocation per layer of DCNs to maximize the achieved reduction in complexity relative to the loss in the classification accuracy of the DCN model. Results from our experiments are reported in Section 5 followed by conclusions in the last section.

Related work
Fixed point implementation of DCNs has been explored in earlier works (Courbariaux et al., 2014;Gupta et al., 2015). These works primarily focused on training DCNs using low precision fixed-point arithmetic. More recently, Lin et al. (2015) showed that deep neural networks can be effectively trained using only binary weights, which in some cases can even improve classification accuracy relative to the floating point baseline.
The works above all focused on the approach of designing the fixed point network during training. The works of Kyuyeon & Sung (2014); Sajid et al. (2015) more closely resemble our work. In Kyuyeon & Sung (2014), the authors propose a floating point to fixed point conversion algorithm for fully-connected networks. The authors used an exhaustive search strategy to identify optimal fixed point bit-width for the entire network. In a follow-up paper (Sajid et al., 2015), the authors applied their proposed algorithm to DCN models where they analyzed the quantization sensitivity of the network for each layer and then manually decide the quantization bit-widths. Other works that are somewhat closely related are Vanhoucke et al. (2011);Gong et al. (2014). Vanhoucke et al. (2011) quantized the weights and activations of pre-trained deep networks using 8-bit fixed-point representation to improve inference speed. Gong et al. (2014) on the other hand applied codebook based on scalar and vector quantization methods in order to reduce the model size.
In the spirit of Sajid et al. (2015), we also focus on optimizing DCN models that are pre-trained with floating point precision. However, as opposed to exhaustive search method adopted by Sajid et al. (2015), our objective is to convert the pre-trained DCN model into a fixed-point model using an optimization strategy based on signal-toquantization-noise-ratio (SQNR). In doing so, we aim to improve upon the inference speed of the network and reduce storage requirements. The benefit of our approach as opposed to the brute force method is that it is grounded in a theoretical framework and offers an analytical solution for bit-width choice per layer to optimize the SQNR for the network. This offers an easier path to generalize to networks with significantly large number of layers such as the one recently proposed by He et al. (2015).
Other approaches to handle complexity of deep networks include: (a) leveraging high complexity networks to boost performance of low complexity networks, as proposed in Hinton et al. (2014), (b) compressing neural networks using hashing (Chen et al., 2015), and (c) combining pruning and quantization during training to reduce the model size without affecting the accuracy (Han et al., 2015). These methods are complementary to our proposed approach and the resulting networks with reduced complexity can be easily converted to fixed point using our proposed method. In fact, the DCN model that we performed experiments with and report results on, (see Section 5.2), was trained under the dark knowledge framework by using the inception network (Ioffe & Szegedy, 2015) trained on ImageNet as the master network.

Floating point to fixed point conversion
In this section, we will propose an algorithm to convert a floating point DCN to fixed point. For a given layer of DCN the goal of conversion is to represent the input activations, the output activations, and the parameters of that layer in fixed point. This can be seen as a process of quantization.

Optimal uniform quantizer
There are three inter-dependent parameters to determine for the fixed point representation of a floating point DCN: bitwidth, step-size (resolution), and dynamic range. These are related as: Given a fixed bit-width, the trade-off is between having large enough range to reduce the chance of overflow and small enough resolution to reduce the quantization error. The problem of striking the best trade-off between overflow error and quantization error has been extensively studied in the literature. Table 1 below shows the step sizes of the optimal symmetric uniform quantizer for uniform, Gaussian, Laplacian and Gamma distributions. The quantizers are optimal in the sense of minimizing the SQNR. Table 1.
Step-sizes of optimal symmetric uniform quantizer for various input distributions (Shi & Sun, 2008) Bit-width β Uniform Gaussian Laplacian Gamma For example, suppose the input is Gaussian distributed with zero mean and unit variance. If we need a uniform quantizer with bit-width of 1 (i.e. 2 levels), the best approach is to place the quantized values at -0.798 and 0.798. In other words, the step size is 1.596. If we need a quantizer with bit-width of 2 (i.e. 4 levels), the best approach is to place the quantized values at -1.494, -0.498, 0.498, and 1.494. In other words, the step size is 0.996.
In practice, however, even though a symmetric quantizer is optimal for a symmetric input distribution, sometimes it is desirable to have 0 as one of the quantized values because of the potential savings in model storage and computational complexity. This means that for a quantizer with 4 levels, the quantized values could be -0.996, 0.0, 0.996, and 1.992.
Assuming an optimal uniform quantizer with ideal input, the resulting SQNR as a function of the bit-width is shown in Figure 1. It can be observed that the quantization efficiency decreases as the Kurtosis of the input distribution increases. Figure 1. Optimal SQNR achieved by uniform quantizer for uniform, Gaussian, Laplacian and Gamma distributions (You, 2010) Another take-away from this figure is that there is an ap-proximately linear relationship between the bit-width and resulting SQNR: where γ dB = 10 log 10 (γ) is the SQNR in dB, κ is the quantization efficiency, and β is the bit-width. Note that the slopes of the lines in Figure 1 depict the optimal quantization efficiency for ideal distributions. The quantization efficiency for uniform distribution is the well-known value of 6dB/bit (Shi & Sun, 2008), while the quantization efficiency for Gaussian distribution is about 5dB/bit (You, 2010) . Actual quantization efficiency for non-ideal inputs can be significantly lower. Our experiments show that the SQNR resulting from uniform quantization of the actual weights and activations in the DCN is between 2 to 4dB/bit.

Empirical distributions in a pre-trained DCN
Figure 2(a) and Figure 2(b) depict the empirical distributions of weights and activations, respectively for the convolutional layers of the DCN we designed for CIFAR-10 benchmark (see Section 5). Note that the activations plotted here are before applying the activation functions. Given the similarity of these distributions to the Gaussian distribution, in all our analysis we have assumed Gaussian distribution for both weights and activations. However, we also note that the distribution of weights and activations for some layers are less Gaussian-like. It will therefore be of interest to experiment with step-sizes for other distributions (see Table 1), which is beyond the scope of present work.

Model conversion
Any floating point DCN model can be converted to fixed point by following these steps: • Run a forward pass in floating point using a large set of typical inputs and record the activations.
• Collect the statistics of weights, biases and activations for each layer. • Determine the fixed point formats of the weights, biases and activations for each layer.
Note that determining the fixed point format is equivalent to determining the resolution, which in turn means identifying the number of fractional bits it requires to represent the number. The following equations can be used to compute the number of fractional bits: • Determine the effective standard deviation of the quantity being quantized: ξ. • Calculate step size via Table 1: s = ξ · Stepsize(β).
• Compute number of fractional bits: n = − log 2 s .
In these equations, • ξ is the effective standard deviation of the quantity being quantized, an indication of the width of the distribution we want to quantize. For example, if the quantized quantities follow an ideal zero mean Gaussian distribution, then ξ = σ, where σ is the true standard deviation of quantized values. If the actual distribution has longer tails than Gaussian, which is often the case as shown in Figure 2(a) and 2(b), then ξ > σ. In our experiments in Section 5, we set ξ = 3σ. • Stepsize(β) is the optimal step size corresponding to quantization bit-width of β, as listed in Table 1. • n is the number of fractional bits in the fixed point representation. Equivalently, 2 −n is the resolution of the fixed point representation and a quantized version of s. Note that · is one choice of a rounding function and is not unique.

Bit-width optimization across a deep network
In the absence of model fine-tuning, converting a floating point deep network into a fixed point deep network is essentially a process of introducing quantization noise into the neural network. It is well understood in fields like audio processing or digital communications that as the quantization noise increases, the system performance degrades. The effect of quantization can be accurately captured in a single quantity, the SQNR.
In deep learning, there is not a well-formulated relationship between SQNR and classification accuracy. However, it is reasonable to assume that in general higher quantization noise level leads to worse classification performance. Given that SQNR can be approximated theoretically and analyzed layer by layer, we focus on developing a theoretical framework to optimize for the SQNR. We then conduct empirical investigations into how the proposed optimization for SQNR affect classification accuracy of the DCN.

Impact of quantization on SQNR
In this section, we will derive the relationship between the quantization of the weight, bias and activation values respectively, and the resulting output SQNR.

QUANTIZATION OF INDIVIDUAL VALUES
Quantization of individual values in a DCN, whether it is an activation or weight value, readily follows the quantizer discussion in Section 3.1. For instance, for weight value w, the quantized versionw can be written as: where n w is the quantization noise. As illustrated in Figure  1, if w approximately follows a uniform, Gaussian, Laplacian or Gamma distribution, the SQNR, γ w , as a result of the quantization process can be written as: where κ is the quantization efficiency and β is the quantizer bit-width.

WEIGHTS
Consider the case where weight w is multiplied by activation a, where both w and a are quantized with quantization noise n w and n a , respectively. The product can be approximated, for small n w and n a , as follows: w ·ã = (w + n w ) · (a + n a ) = w · a + w · n a + n w · a + n w · n a ∼ = w · a + w · n a + n w · a.
The last equality holds if |n a | << |a| and |n w | << |w|. A very important observation is that the SQNR of the product, w · a, as a result of quantization, satisfies This is characteristic of a linear system. The defining benefit of this realization is that introducing quantization noise to weights and activations independently is equivalent to adding the total noise after the product operation in a normalized system. This property will be used in later analysis.

FORWARD PASS THROUGH ONE LAYER
In a DCN with multiple layers, computation of the ith activation in layer l+1 of the DCN can be expressed as follows: Fixed Point Quantization of Deep Convolutional Networks where (l) represents the lth layer, N represents number of additions, w i,j represents the weight and b i represents the bias.
Ignoring the bias term for the time being, since a (i+1) i is simply a sum of terms like w (l+1) i,j a (l) j , which when quantized all have the same SQNR γ w (l+1) ·a (l) . Assuming the product terms w (l+1) i,j a (l) j are independent, it follows that the value of a (i+1) i , before further quantization, has inverse SQNR that equals After a (l+1) i is quantized to the assigned bit-width, the resulting inverse SQNR then becomes 1 γ a (l+1) + 1 γ w (l+1) + 1 γ a (l) . We are not considering the biases in this analysis because, assuming that the biases are quantized at the same bit-width as the weights, the SQNR is dominated by the product term w

FORWARD PASS THROUGH ENTIRE NETWORK
Equation 8 can be generalized to all the layers in a DCN (although we have found empirically that the approximation applies better for convolutional layers than fully-connected layers). Consider layer L in a deep network, where all the activations and weights are quantized. Extending Equation 8, we obtain the SQNR (γ output ) at the output of layer L as: In other word, the SQNR at the output of a layer in DCN is the Harmonic Mean of the SQNRs of all preceding quantization steps. This simple relationship reveals some very interesting insights: • All the quantization steps contribute equally to the overall SQNR of the output, regardless if it's the quantization of weights, activations, or input, and irrespective of where it happens (at the top or bottom of the network). • Since the output SQNR is the harmonic mean, the network performance will be dominated by the worst quantization step. For example, if the activations of a particular layer has a much smaller bit-width than other layers, it will be the bottleneck of network performance, because based on Equation 9, γ output ≤ γ a (l) for all l.
• Depth makes quantization more challenging, but not exceedingly so. The rest being the same, doubling the depth of a DCN will half the output SQNR (3dB loss). But this loss can be readily recovered by adding 1 bit to the bit-width of all weights and activations, assuming the quantization efficiency is more than 3dB/bit. However, this theoretical prediction will need to be empirically verified in future works.

EFFECTS OF OTHER NETWORK COMPONENTS
• Batch normalization: Batch normalization (Ioffe & Szegedy, 2015) improves the speed of training a deep network by normalizing layer inputs. After the network is trained, the batch normalization layer is a fixed linear transformation and can be absorbed into the neighboring convolutional layer or fully-connected layer. Therefore, the quantization effect due to batch normalization does not need to be explicitly modeled.
• ReLU: In Equation 7, for simplicity we omitted the activation function applied to a (l) j . When the activation function is ReLU and the quantization noise is small, all the positive values at the input to the activation function will have the same SQNR at the output, and the negative values become zero (effectively reducing the number of additions, N ). In other words, where g(·) is the ReLU function and M ≤ N is the number of a (l) j 's that are positive. In this case, the ReLU function has little impact on the SQNR of a (l+1) i . ReLU only starts to affect SQNR calculation when the perturbation caused by quantization is sufficiently large to alter the sign of a (l) j . Therefore, our analysis may become increasingly inaccurate as the bit-width becomes too small (quantization noise too large).
• Non-ReLU activations: Other nonlinear activation functions such as tanh, sigmoid, PReLU functions are much harder to model and analyze. However, in Section 5.1 we will see that applying the analysis in this section to a network with PReLU activation functions still yields useful enhancements.

Cross-layer bit-width optimization
From Equation 9, it is seen that trade-offs can be made between quantizers of different layers to produce the same Fixed Point Quantization of Deep Convolutional Networks γ output . That is to say, we can choose to use smaller bitwidths for some layers by increasing bit-widths for other layers. For example, this may be desirable because of the following reasons: • Some layers may require a large number of computations (multiply-accumulate operations). Reducing the bit-widths for these layers would reduce the overall network computation load. • Some layers may contain a large number of network parameters (weights). Reducing the weight bit-widths for these layers would reduce the overall model size.
Interestingly, such objectives can be formulated as an optimization problem and solved exactly. Suppose our goal is to reduce model size while maintaining a minimum SQNR at the DCN output. We can use ρ i as the scaling factor at quantization step i, which in this case represents the number of parameters being quantized in the quantization step.
The problem can be written as: where 10 log γ i is the SQNR in dB domain, and (10 log γ i )/κ is the bit-width in the ith quantization step according to Equation 2. γ min is the minimum output SQNR required to achieve a certain level of accuracy. The optimization constraint follows from Equation 9 that the output SQNR is the harmonic mean of the SQNR of intermediate quantization steps.
Substituting by λ i = 1 γ i and removing the constant scalars from the objective function, the problem can be reformulated as: where the constant C = 1 γ min . This is a classic convex optimization problem with the water-filling solution (Boyd & Vandenberghe, 2004): Or equivalently, Recognizing that 10 log γ i = κβ i based on Equation 2, the solution can be rewritten as: In other words, the difference between the optimal bitwidths of two quantization steps is inversely proportional to the difference of ρ's in dB, scaled by the quantization efficiency.
This is a surprisingly simple and insightful relationship. For example, assuming κ = 3dB/bit, the bit-widths β i and β j would differ by 1 bit if ρ j is 3dB (or 2x) larger than ρ i . More specifically, for model size reduction, layers with more parameters should use relatively lower bit-width, as it leads to better model compression under the overall SQNR constraint.

Experiments
In this section we study the effect of reduced bit-width for both weights and activations versus traditional 32bit single-precision floating point approach (16-bit halfprecision floating point is expected to produce comparable results as single-precision in most cases). In particular, we will implement the fixed point quantization algorithm described in Section 3 and investigate the effectiveness of the bit-width optimization algorithm in Section 4. In addition, using the quantized fixed point network as the starting point, we will further fine-tune the fixed point network within the restricted alphabets of weights and activations.

Bit-width optimization for CIFAR-10 classification
We evaluate our proposed cross-layer bit-width optimization algorithm on the CIFAR-10 benchmark using the algorithm prescribed in Section 4.2. In Table 2, we compute the number of parameters in each layer of our CIFAR-10 network. Consider the objective of minimizing the overall model size. Provided that the quantization efficiency κ = 3dB/bit, our derivation in Section 4.2 shows that the optimal bit-width of layer conv0 and conv1 would differ by 10 log(0.295/0.007)/κ = 5bits. Similarly, assuming the bit-width for layer conv0 is β 0 , the subsequent convolutional layers should have bit-width values as indicated in Table 3.
In our experiment in this section, we will ignore the fullyconnected layer and assume a fixed bit-width of 16 for both weights and activations. This is because fully-connected layers have different SQNR characteristics and need to be optimized separately. Although the fully-connected lay- Table 3. Optimal bit-width allocation in our CIFAR-10 network, assuming the bit-width of layer conv0 is β0 Layer conv1 conv2 conv3 conv4 conv5 Bit-width β0 − 5 β0 − 5 β0 − 6 β0 − 6 β0 − 8 ers can often be quantized more aggressively than convolutional layers, since the number of parameters of fc0 is very small in this experiment, we will set the bit-width to a large value to eliminate the impact of quantizing fc0 from the analysis, knowing that the large bit-width of fc0 has very little impact on the overall model size. We will also set the activation bit-widths of all the layers to a large value of 16 because they do not affect the model size. Figure 3 displays the model size vs. error rate in a scatter plot, we can clearly see the advantage of crosslayer bit-width optimization. When the model size is large (bit-width is high), the error rate saturates at around 6.9%. When the model size reduces below approximately 25Mbits, the error rate starts to increase quickly as the model size decreases. In this region, cross-layer bit-width optimization offers > 20% reduction in model size for the same performance.

Bit-width optimization for ImageNet classification
In Section 5.1, we performed cross-layer bit-width optimization for our CIFAR-10 network with the objective of minimizing the overall model size while maintaining accuracy. Here we carry out a similar exercise for an AlexNetlike DCN that is trained on ImageNet-1000. The DCN architecture is described in Table 4.
For setting the bit-width of convolutional layers of this DCN, we follow the steps in Section 5.1 with the assumption that the bit-width for layer conv1 is β 1 . The resulting  -4.194 bit-width allocation for all convolutional layers is summarized in Table 5. Table 5. Optimal bit-width allocation in our AlexNet-like network, assuming the bit-width of layer conv1 is β1 For fully-connected layers we first keep the network as floating point and quantize the weights of fully-connected layers only. We then reduce bit-width of fully-connected layers until the classification accuracy starts to degrade. We found that the minimum bit-width for the fully-connected layers before performance degradation occurs is 6.   Figure 4 depicts the convolutional layer model size vs. top-5 error rate tradeoff for both optimized bit-width and equal bit-width scenarios. Similar to our CIFAR-10 network, there is a clear benefit of cross-layer bit-width optimization in terms of model size reduction. In some regions the saving can be upto 1Mbits.
However, unlike our CIFAR-10 network where the convo-lutional layers make up most of the model size, in AlexNetlike DCN the fully-connected layers dominate in terms of number of parameters. With bit-width of 6, the overall size of fully-connected layers is more than 100Mbits. This means that the saving of 1Mbits brings in less than 1% of overall model size reduction! This is in clear contrast to the 20% model size reduction we reported for our CIFAR-10 network. Therefore, it is worth nothing that the proposed cross-layer layer bit-width optimization algorithm is most effective when the network size is dominated by convolutional layers, and is less effective otherwise.
The experiments on our CIFAR-10 network and AlexNetlike network demonstrate that the proposed cross-layer bitwidth optimization offers clear advantage over the equal bit-width scheme. As summarized in Table 3 and Table 5, a simple offline computation of the inter-layer bit-width relationship is all that is required to perform the optimization.
However, in the absence of customized design, the implementation of the optimized bit-widths can be limited by the software or hardware platform on which the DCN operates. Often, the optimized bit-width needs to be rounded up to the next supported bit-width, which may in turn impact the network classification accuracy and model size.

Validation for SQNR prediction
To verify that our SQNR calculation presented in Section 4.1 is valid, we will conduct a small experiment. More specifically, we will focus on the optimized networks in Figure 3 and compare the measured SQNR per layer to the SQNR predictions according to Equation 4 and 8.  Table 6 contains the comparison between the theoretical SQNR and the measured SQNR (in dB) for layers conv1 to conv5 for two of the optimized networks. We observe that while the two SQNR values do not match numerically, they follow similar decreasing trend as the activations propagate deeper into the network. It should be noted that our theoretical SQNR predictions are based purely on the weight and activation bit-widths of each layer as well as the quantization efficiency κ. The theory does not rely on any in-formation related to the network parameters or the data it is tested on.

Model fine-tuning
Although our focus is fixed point implementation without training, our quantizer design can also be used as a starting point for further model fine-tuning when the training model and training parameters are available.  Table 7 contains the classification error rate (in %) for the CIFAR-10 network after fine-tuning the model for 30 epochs. We experiment with different weight and activation bit-width combinations, ranging from floating point to 4-bit, 8-bit, and 16-bit fixed point. It is shown that even the (4b, 4b) bit-width combination works well (8.30% error rate) when the network is fine-tuned after quantization. In addition, the (float, 8b) setting generates an error rate of 6.78%, which is the new state-of-the-art result even though the activations are only 8-bit fixed point values. This may be attributed to the regularization effect of the added quantization noise (Lin et al., 2015;Luo & Yang, 2014).

Conclusions
Fixed point implementation of deep networks is important for real world embedded applications, which involve real time processing with limited power budget. In this paper, we develop a principled approach to converting a pretrained floating point DCN model to its fixed point equivalent. We show that the naive method of quantizing all the layers in the DCN with uniform bit-width value results in DCN networks with subpar performance in terms of error rates relative to our proposed approach of SQNR based optimization of bit-widths. Specifically, we present results for a floating point DCN trained CIFAR-10 benchmark, which on conversion to its fixed point counter-part results in >20 % reduction in model size without any loss in accuracy. We note that our proposed algorithm facilitates easy conversion of any off-the-shelf DCN model for efficient real world on-device application. Finally, through fine-tuning experiments we demonstrate that our quantizer design methodology is a useful starting point for further model fine-tuning after the floating-point-to-fixed-point conversion.


extfieldsofstudy:
Computer Science
Mathematics

text:
Interactive Learning from Multiple Noisy Labels

Interactive learning is a process in which a machine learning algorithm is provided with meaningful, well-chosen examples as opposed to randomly chosen examples typical in standard supervised learning. In this paper, we propose a new method for interactive learning from multiple noisy labels where we exploit the disagreement among annotators to quantify the easiness (or meaningfulness) of an example. We demonstrate the usefulness of this method in estimating the parameters of a latent variable classification model, and conduct experimental analyses on a range of synthetic and benchmark datasets. Furthermore, we theoretically analyze the performance of perceptron in this interactive learning framework.

Introduction
We consider binary classification problems in the presence of a teacher, who acts as an intermediary to provide a learning algorithm with meaningful, well-chosen examples. This setting is also known as curriculum learning [1,2,3] or self-paced learning [4,5,6] in the literature. Existing practical methods [4,7] that employ such a teacher operate by providing the learning algorithm with easy examples first and then progressively moving on to more difficult examples. Such a strategy is known to improve the generalization ability of the learning algorithm and/or alleviate local minima problems while optimizing non-convex objective functions.
In this work, we propose a new method to quantify the notion of easiness of a training example. Specifically, we consider the setting where examples are labeled by multiple (noisy) annotators [8,9,10,11]. We use the disagreement among these annotators to determine how easy or difficult the example is. If a majority of annotators provide the same label for an example, then it is reasonable to assume that the training example is easy to classify and that these examples are likely to be located far away from the decision boundary (separating hyperplane). If, on the other hand, there is a strong disagreement among annotators in labeling an example, then we can assume that the example is difficult to classify, meaning it is located near the decision boundary. In the paper by Urner et al. [12], a strong annotator always labels an example according to the true class probability distribution, whereas a weak annotator is likely to err on an example whose neighborhood is comprised of examples from both classes, i.e., whose neighborhood is label heterogeneous. In other words, both strong and weak annotators do not err on examples far away from the decision boundary, but weak annotators are likely to provide incorrect labels near the decision boundary where the neighborhood of an example is heterogeneous in terms of its labels. There are a few other theoretical studies where weak annotators were assumed to err in label heterogeneous regions [13,14]. The notion of annotator disagreement also shows up in the multiple teacher selective sampling algorithm of Dekel et al. [15]. This line of research indicates the potential of using annotator disagreement to quantify the easiness of a training example.
To the best of our knowledge, there has not been any work in the literature that investigates the use of annotator disagreement in designing an interactive learning algorithm. We note that a recent paper [16] used annotator disagreement in a different setting, namely as privileged information in the design of classification algorithms. Self-paced learning methods [4,5,6] aim at simultaneously estimating the parameters of a (linear) classifier and a parameter for each training example that quantifies its easiness. This results in a non-convex optimization problem that is solved using alternating minimization. Our setting is different as the training example is comprised of not just a single (binary) label but multiple noisy labels provided by a set of annotators, and we use the disagreement among these annotators (which is fixed) to determine how easy or difficult a training example is. We note that it is possible to parameterize the easiness of an example as described in Kumar et al.'s paper [4] in our framework and use it in conjunction with the disagreement among annotators.
Learning from multiple noisy labels [8,9,10,11] has been gaining traction in recent years due to the availability of inexpensive annotators from crowdsourcing websites like Amazon's Mechanical Turk. These methods typically aim at learning a classifier from multiple noisy labels and in the process also estimate the annotators' expertise levels. We use one such method [10] as a test bed to demonstrate the usefulness of our interactive learning framework.

Problem Definition and Notation
Let X ⊆ R n denote the input space. The input to the learning algorithm is a set of m examples with corresponding (noisy) labels from L annotators denoted by S = x i , y i , y i , . . . , y . . , m} and ∈ {1, . . . , L}. Let z 1 , z 2 , . . . , z L ∈ [0, 1] denote the annotators' expertise scores, which is not known to the learning algorithm. A strong annotator will have a score close to one and a weak annotator close to zero. The goal is to learn a classifier f : X → {±1} parameterized by a weight vector w ∈ R n , and also estimate the annotators' expertise scores {z 1 , z 2 , . . . , z L }. In this work, we consider linear models f (x) = w, x , where ·, · denotes the dot-product of input vectors.

Learning from Multiple Noisy Labels
One of the algorithmic advantages of interactive learning is that it can potentially alleviate local minima problems in latent variable models [4] and also improve the generalization ability of the learning algorithm. A latent variable model that is relevant to our setting of learning from multiple noisy labels is the one proposed by Raykar et al. [10] to learn from crowdsourced labels. For squared loss function, 1 i.e., regression problems and a linear model, 2 the weight vector w and the annotators' expertise scores (the latent variable) {z } can be simultaneously estimated using the 1 We consider squared loss function to describe our method and in our experiments for the sake of convenience. The method can be naturally extended to the classification model described in Raykar et al.'s paper [10]. Also, we note that it is perfectly valid to minimize squared loss function for classification problems [17]. 2 Although we consider linear models in our exposition, we note that our method can be adapted to accommodate any classification algorithm that can be trained with weighted examples. following iterative updates: where λ is the regularization parameter. Intuitively, the updates estimate the score z of an annotator based on her performance (measured in terms of squared error) with the current modelŵ, and the label of an example is adjusted {ŷ i } by taking the weighted average of all its noisy labels from the annotators. In practice, the labels {ŷ i } are initialized by taking a majority vote of the noisy labels. The above updates are guaranteed to converge only to a locally optimum solution.
We now use the disagreement among annotators in the regularized risk minimization framework. For each example x i , we compute the disagreement d i among annotators as follows: and solve a weighted least-squares regression problem: where g : R → [0, 1] is a monotonically decreasing function of the disagreement among annotators, and iteratively update {z } using: In our experiments, we use g  Figure 1. The parameter α is a hyperparameter that the user has to tune akin to tuning the regularization parameter.
The optimization problem (3) has a closed-form solution. Let X ∈ R m×n denote the matrix of inputs, D ∈ R m×m denote a diagonal matrix whose diagonal entries are g(d i ), for all i ∈ {1, . . . , m} andŷ denote the (column) vector of labels. The solution is given by:ŵ = (X DX + λI) −1 X Dŷ, where I is the identity matrix. Hence, optimization solvers used to estimate the parameters in regularized least-squares regression can be adapted to solve this problem by a simple rescaling of inputs via X ← √ DX andŷ ← √ Dŷ. In the above description of the algorithm, we fixed the weights g(·) on the examples. Ideally, we would want to reweight the examples uniformly as learning progresses. This can be done in the following way. Let P X denote some probability distribution induced on the examples via g(·). In every iteration t of the learning algorithm, we pick one of P X or the uniform distribution based on a Bernoulli trial with success probability 1/t c for some fixed positive integer c to ensure that the distribution on examples converges to a uniform distribution as learning progresses. Unfortunately, we did not find this to work well in practice and the parameters of the optimization problem did not converge as smoothly as when fixed weights g(·) were used throughout the learning process. We leave this as an open question and use fixed weights in our experiments.

Mistake Bound Analysis
In this section, we analyze the mistake bound of perceptron operating in the interactive learning framework. The algorithm is similar to the classical perceptron, but the training examples are sorted based on their distances from the separating hyperplane and fed to the perceptron starting from the farthest example. The theoretical analysis requires estimates of margins of all examples. We describe a method to estimate the margin of an example and also its ground-truth label (from the multiple noisy labels) in the Appendix. We would like to remark that the margin of examples is needed only to prove the mistake bound. In practice, the perceptron algorithm can directly use the disagreement among annotators (2).
for all examples. Then, the number of mistakes made by the perceptron algorithm on this sequence is at most (R/γ) 2 u 2 .
The above result is the well-known mistake bound of perceptron and the proof is standard. We now state the main theorem of this paper.
Theorem 2 Let ((x 1 ,ŷ 1 ,γ 1 ), . . . , (x T ,ŷ T ,γ T )) be a sequence of training examples along with their label and margin estimates, sorted in descending order based on the margin estimates, and with x t ≤ R for all t ∈ {1, . . . , T }. Letγ = min(γ 1 , . . . ,γ T ) =γ T and K = R/γ − 1. Suppose there exists a vector u such thatŷ t u, x t ≥γ for all examples. Divide the input space into K equal regions, so that for any example x t k in a region k it holds thatŷ t k x t k , u ≥ kγ. Let {ε 1 , . . . , ε K } denote the number of mistakes made by the perceptron in each of the K regions, and let ε = k ε k denote the total number of mistakes. Define ε s = 1/K k (ε k − ε/K) 2 to be the standard deviation of {ε 1 , . . . , ε K }.
Then, the number of mistakes ε made by the perceptron on the sequence of training examples is bounded from above via: We will use the following inequality in proving the above result.
Lemma 3 (Laguerre-Samuelson Inequality [19]) Let (r 1 , . . . , r n ) be a sequence of real numbers. Letr = i r i /n and s = 1/n i (r i −r) 2 denote their mean and standard deviation, respectively. Then, the following inequality holds for all i ∈ {1, . . . , n}: Proof Using the margin estimatesγ 1 , . . . ,γ T , we divide the input space into K = R/γ − 1 equal regions, so that for any example x t k in a region k,ŷ t k x t k , u ≥ kγ. Let T 1 , . . . , T K be the number of examples in these regions, respectively. Let τ t be an indicator variable whose value is 1 if the algorithm makes a prediction mistake on example x t and 0 otherwise. Let ε k = T k t=i τ t i be the number of mistakes made by the algorithm in region k, ε = k ε k be the total number of mistakes made by the algorithm.
We first bound w T +1 2 , the weight vector after seeing T examples, from above. If the algorithm makes a mistake at iteration t, then w t+1 Next, we bound w T +1 , u from below. Consider the behavior of the algorithm on examples that are located in the farthest region K. When a prediction mistake is made in this region at The weight vector moves closer to u by at least Kγ. After the algorithm sees all examples in the farthest region K, we have w T K +1 , u ≥ ε K Kγ (since w 1 = 0), and similarly for region K − 1, and so on for other regions. Therefore, after the algorithm has seen T examples, we have where we used the Laguerre-Samuelson inequality to lower-bound ε k for all k, using the mean ε/K and standard deviation ε s of {ε 1 , . . . , ε K }.
Combining these lower and upper bounds, we get the following quadratic equation in √ ε: whose solution is given by:  Note that if ε s = 0, i.e., when the number of mistakes made by the perceptron in each of the regions is the same, then we get the following mistake bound: clearly improving the mistake bound of the standard perceptron algorithm. However, ε s = 0 is not a realistic assumption. We therefore plot x-fold improvement of the mistake bound as a function of ε s for a range of marginsγ in Figure 2. The y-axis is the ratio of mistake bounds of interactive perceptron to standard perceptron with all examples scaled to have unit Euclidean length (R = 1) and u = 1. From the figure, it is clear that even when ε s > 0, it is possible to get non-trivial improvements in the mistake bound.
The above analysis uses margin and label estimates,γ 1 , . . . ,γ T ,ŷ 1 , . . . ,ŷ T , from our method described in the Appendix, which may not be exact. We therefore have to generalize the mistake bound to account for noise in these estimates. Let {γ 1 , . . . , γ T } be the true margins of examples. Let γu , γ ∈ (0, 1] denote margin noise factors such thatγ t / γ ≥ γ t ≥ γuγt , for all t ∈ {1, . . . , T }. These noise factors will be useful to account for overestimation and underestimation inγ t , respectively. Label noise essentially makes the classification problem linearly inseparable, and so the mistake bound can be analyzed using the method described in the work of Freund and Schapire [20] (see Theorem 2). Here, we define the deviation of an example x t as δ t = max(0,γ/ γ −ŷ t u, x t ) and let ∆ = t δ 2 t . As will become clear in the analysis, ifγ is overestimated, then it does not affect the worst-case analysis of the mistake bound in the presence of label noise. If the labels were accurate, then δ t = 0, for all t ∈ {1, . . . , T }. With this notation in place, we are ready to analyze the mistake bound of perceptron in the noisy setting. Below, we state and prove the theorem for ε s = 0, i.e., when the number of mistakes made by the perceptron is the same in all the K regions. The analysis is similar for ε s > 0, but involves tedious algebra and so we omit the details in this paper. ((x 1 ,ŷ 1 ,γ 1 ), . . . , (x T ,ŷ T ,γ T )) be a sequence of training examples along with their label and margin estimates, sorted in descending order based on the margin estimates, and with x t ≤ R for all t ∈ {1, . . . , T }. Letγ = min(γ 1 , . . . ,γ T ) =γ T and K = R/γ − 1. Suppose there exists a vector u such thatŷ t u, x t ≥γ for all the examples. Divide the input space into K equal regions, so that for any example x t k in a region k it holds thatŷ t k x t k , u ≥ kγ. Assume that the number of mistakes made by the perceptron is equal in all the K regions. Let {γ 1 , . . . , γ T } denote the true margins of the examples, and suppose there exists γu , γ ∈ (0, 1] such thatγ t / γ ≥ γ t ≥ γuγt for all t ∈ {1, . . . , T }. Define δ t = max(0,γ/ γ −ŷ t u, x t ) and let ∆ = t δ 2 t . Then, the total number of mistakes ε made by the perceptron algorithm on the sequence of training examples is bounded from above via:

Theorem 4 Let
Proof (Sketch) Observe that margin noise affects only the analysis that bounds w T +1 , u from below. When a prediction mistake is made in region K, the weight vector moves closer to u by at least K γuγ . After the algorithm sees all examples in the farthest region K, we have w T K +1 , u ≥ ε K K γuγ (since w 1 = 0). Therefore, margin noise has the effect of down-weighting the bound by a factor of γu . The rest of the proof follows using the same analysis as in the proof of Theorem 2. Note that margin noise affects the bound only whenγ t is overestimated because the margin appears only in the denominator when ε s = 0.
To account for label noise, we use the proof technique in Theorem 2 of Freund and Schapire's paper [20]. The idea is to project the training examples into a higher dimensional space where the data becomes linearly separable and then invoke the mistake bound for the separable case. Specifically, for any example x t , we add T dimensions and form a new vector such that the first n coordinates remain the same as the original input, the (n + t)'th coordinate gets a value equal to C (a constant to be specified later), and the remaining coordinates are set to zero. Let x t ∈ R n+T for all t ∈ {1, . . . , T } denote the examples in the higher dimensional space. Similarly, we add T dimensions to the weight vector u such that the first n coordinates remain the same as the original input, and the (n + t)'th coordinate is set toŷ t δ t /C, for all t ∈ {1, . . . , T }. Let u ∈ R n+T denote the weight vector in the higher dimensional space.
With the above construction, we haveŷ t u , x t =ŷ t u, x t + δ t ≥γ/ γ . In other words, examples in the higher dimensional space are linearly separable by a marginγ/ γ . Also, note that the predictions made by the perceptron in the original space are the same as those in the higher dimensional space. To invoke Theorem 2, we need to bound the length of the training examples in the higher dimensional space, which is x t 2 ≤ R 2 + C 2 . Therefore the number of mistakes made by the perceptron is at most 4(R 2 + C 2 )( u 2 + ∆ 2 /C 2 )/( 2 γuγ 2 (K + 1 2 )). It is easy to verify that the bound is minimized when C = R∆/ u , and hence the number of mistakes is bounded from above by 4(∆ + R u ) 2 ( 2 γuγ 2 (K + 1) 2 ).  Figure 3: Illustration of the function used to convert the score from a linear model to a probability that is used to simulate noisy labels from annotators.

Empirical Analysis
We conducted experiments on synthetic and benchmark datasets. 3 For all datasets, we simulated annotators to generate (noisy) labels in the following way. For a given set of training examples, For each example x i , we generated L copies of its true label, and then flipped them based on a Bernoulli trial with success probabilityf i /2. This has the effect of generating (almost) equal numbers of labels with opposite sign and hence maximum disagreement among labels for examples that are close to the decision boundary. In the other extreme, labels of examples located far away from the decision boundary will not differ much. Furthermore, we flipped the sign of all labels based on a Bernoulli trial with success probabilityf i if the majority of labels is equal to the true label. This ensures that the majority of labels are noisy for examples close to the decision boundary. The noise parameter p controls the amount of noise injected into the labels -high values result in weak disagreement among annotators and low label noise, as shown in Figure 3. Table 1 shows the noisy labels generated by ten annotators for p = 1 on a simple set of one-dimensional examples  in the range [−1, +1]. As is evident from the table, the simulation is designed in such a way that an example close to (resp. far away from) the decision boundary will have a strong (resp. weak) disagreement among its labels.

Synthetic Datasets
We considered binary classification problems with examples generated from two 10-dimensional Gaussians centered at {−0.5} 10 and {+0.5} 10 with unit variance. We generated noisy labels using the procedure described above. Specifically, we simulated 12 annotators -one of them always generated the true labels, another flipped all the true labels, the remaining 10 flipped labels using the simulation procedure described above. We randomly generated 100 datasets, each of them having 1000 training examples equally divided between the two classes. We used half of the data set for training and the other half for testing. In each experiment, we tuned the regularization parameter   (Figure 1). The parameter p as mentioned before controls label noise. We compared the performance of the algorithm in interactive and non-interactive modes described in Section 2. The non-interactive algorithm is the one described in Raykar et al.'s paper [10].
The results are shown in Table 2. We use area under the receiver operating characteristic curve (AU-ROC) and area under the precision-recall curve (AU-PRC) as performance metrics. In the table, we show the number of times the AU-ROC and the AU-PRC of the interactive algorithm is higher than its non-interactive counterpart (#wins out of 100 datasets). We also show the twosided p-value from the Wilcoxon signed-rank test. From the results, we note that the performance of the interactive algorithm is not significantly better than its non-interactive counterpart for small and large values of α. This is expected because small values of α reweight examples (almost) uniformly and so there is not much to gain when compared to running the algorithm in the noninteractive mode. In the other extreme, large values of α tend to discard a large number of examples close to the decision boundary thereby degrading the overall performance of the algorithm in the interactive mode. α = 2 gives the best performance. We also note that for high values of p, i.e., weak disagreement among annotators and hence low label noise, the interactive algorithm offers no statistically significant gains when compared to the non-interactive algorithm. This, again, is as expected.

Benchmark Datasets
We used LibSVM benchmark 4 datasets in our experiments. We selected binary classification datasets with at most 10,000 training examples and 300 features ( Table 3), so that we could afford to train multiple linear models (100 in our experiments) for every dataset using standard solvers and also afford to tune hyperparameters carefully in a reasonable amount of time. We generated noisy labels with the same procedure used in our experiments on synthetic data. Also, we tuned the regularization parameter in an identical manner. For datasets with no predefined training and For each dataset, we randomly generated 100 sets of noisy labels from the 12 annotators resulting in 100 different random versions of the dataset. The results are shown in Table 4. In the table, we again show the number of times the AU-ROC and the AU-PRC of the interactive algorithm is higher than its non-interactive counterpart (#wins out of 100 datasets). We report results on only a subset of (α, p) values that were found to give good results based on our experimental analysis with synthetic data. From the table, it is clear that the interactive algorithm performs significantly better than its non-interactive counterpart on the majority of datasets. On datasets where its performance was worse than that of the non-interactive algorithm, the results were not statistically significant across all parameter settings. As a final remark, we would like to point out that the performance of the interactive algorithm dropped on some of the datasets with class imbalance. We therefore subsampled the training sets (using a different random subset in each of the 100 experiments for the given dataset) to make the classes balanced. We believe the issue of class imabalance is orthogonal to the problem we are addressing, but needs further investigation and so we leave this open for future work.

Concluding Remarks
Our experiments clearly demonstrate the benefits of interactive learning and how disagreement among annotators can be utilized to improve the performance of supervised learning algorithms. Furthermore, we presented theoretical evidence by analyzing the mistake bound of perceptron. The question as to whether annotators in real world scenarios behave according to our simulation model, i.e., if they tend to disagree more on difficult examples located close to the decision boundary when compared to easy examples farther away, is an open one. However, if this assumption holds then our experiments and theoretical analysis show that learning can be improved. In real-world crowdsourcing applications, an example is typically labeled only by a subset of annotators. Although we did not consider this setting, we believe we could still use the disagreement among annotators to reweight examples, but the algorithm would require some modifications to handle missing labels. We leave this setting open for future work.
Estimating the radius of an annotator's ball.
Let r 1 , r 2 , . . . , r L ≥ 0 denote the radii of the annotators' balls. Let B r (x) = {z ∈ X | d(x, z) ≤ r} denote the ball of radius r centered at x, with d(·, ·) being a distance metric, such as the Euclidean distance for linear models, defined on the input space X . Given the expertise score z for an annotator , we estimate the radius r of her ball by solving the following univariate optimization problem:r = argmin Intuitively, the above optimization problem is trying to estimate the radius of the annotator's ball by minimizing the squared difference between the (noisy) label of the annotator and the average of the estimates of true labels of all neighboring examples in the ball.
Putting it all together.
Given a training example x, its noisy labels (y (1) , . . . , y (L) ), an estimate of the ground-truth label y, and the radius estimates of the annotators' balls, we compute a lower bound on the margin of x, i.e., its distance from the decision boundary, as follows. Centered at x, we draw nested balls of increasing size, one for each annotator using her radius. Starting from the annotator with the smallest ball, we compare her noisy label with the ground-truth label estimate. At some ball/expert, the noisy label and the ground-truth label estimate will differ, and the radius of this ball is a lower bound on the distance of x from the decision boundary.


text:
Node Overlap Removal by Growing a Tree

Node overlap removal is a necessary step in many scenarios including laying out a graph, or visualizing a tag cloud. Our contribution is a new overlap removal algorithm that iteratively builds a Minimum Spanning Tree on a Delaunay triangulation of the node centers and removes the node overlaps by"growing"the tree. The algorithm is simple to implement yet produces high quality layouts. According to our experiments it runs several times faster than the current state-of-the-art methods.

Introduction
Removing node overlap after laying out a graph is a common task in network visualization. Most graph layout algorithms [23] consider nodes as points that do not occupy any geometrical space. In practice, nodes often have shapes, labels, and so on. These shapes and labels may overlap in the visualization and affect the visual readability. To remove such overlaps a specialized algorithm is usually applied.
The main contribution of this paper is a new node overlap removal algorithm that we call Growing Tree, or GTree further on. The basic idea is to first capture most of the overlap and the local structure with a specific spanning tree on top of a proximity graph, and then resolve the overlap by letting the tree "grow".
We compare GTree with PRISM [6], which is widely used for the same purpose. Needing more area than PRISM, our method preserves the original layout well and is up to eight times faster than PRISM. To compare the two algorithms we implemented GTree in the open source graph visualization software Graphviz 1 , where PRISM is the default overlap removal algorithm. On the other side, GTree is the default in MSAGL 2 , where we also have an implementation of PRISM. We ran comparisons by using both tools.

Related Work
There is vast research on node overlap removal. Some methods, including hierarchical layouts [4], incorporate the overlap removal with the layout step. Likewise, force-directed methods [5] have been extended to take the node sizes into account [16,17,24], but it is difficult to guarantee overlap-free layouts without increasing the repulsive forces extensively. Dwyer et al. [2] show how to avoid node overlaps with Stress Majorization [7]. The method can remove node overlaps during the layout step, but it needs an initial state that is overlap free; sometimes such a state is not given.
Another approach, which we also choose, is to use a post-processing step. In Cluster Busting [8,18] the nodes are iteratively moved towards the centers of their Voronoi cells. The process has the disadvantage of distributing the nodes uniformly in a given bounding box.
Imamichi et al. [15] approximate the node shapes by circles and minimize a function penalizing the circle overlaps.
Starting from the center of a node, RWorldle [22] removes the overlaps by discovering the free space around a node by using a spiral curve and then utilizing this space. The approach requires a large number of intersection queries that are time consuming. This idea is extended by Strobelt et al. [21] to discover available space by scanning the plane with a line or a circle.
Another set of node overlap removal algorithms focus on the idea of defining pairwise node constraints and translating the nodes to satisfy the constraints [11,13,19,20]. These methods consider horizontal and vertical problems separately, which often leads to a distorted aspect ratio [6]. A Force-transfer-algorithm is introduced by Huang et al. [14]; horizontal and vertical scans of overlapped nodes create forces moving nodes vertically and horizontally; the algorithm takes O(n 2 ) steps, where n is the number of the nodes. Gomez et al. [9] develop Mixed Integer Optimization for Layout Arrangement to remove overlaps in a set of rectangles. The paper discusses the quality of the layout, which seems to be high, but not the effectiveness of the method, which relies on a mixed integer problem solver. Dwyer et al. [3] reduce the overlap removal to a quadratic problem and solve it efficiently in O(n log n) steps. According to Gansner and Hu [6], the quality and the speed of the method of Dwyer et al. [3] is very similar to the ones of PRISM.
The ProjSnippet method [10] generates good quality layouts. The method requires O(n 2 ) amount of memory, at least if applied directly as described in the paper, and the usage of a nonlinear problem solver.
In PRISM [6,12], a Delaunay triangulation on the node centers is used as the starting point of an iterative step. Then a stress model for node overlap removal is built on the edges of the triangulation and the stress function of the model is minimized. GTree also starts with building this Delaunay triangulation, but then the algorithms diverge.
An input to GTree is a set of nodes V , where each node i ∈ V is represented by an axis-aligned rectangle B i with the center p i . We assume that for different i, j ∈ V the centers p i , p j are different too. If this is not the case, we randomly shift the nodes by tiny offsets. We denote by D a Delaunay triangulation of the set {p i : i ∈ V }, and let E be the set of edges of D.
On a high level, our method proceeds as follows. First we calculate the triangulation D, then we define a cost function on E and build a minimum cost spanning tree on D for this cost function. Finally, we let the tree "grow". The steps are repeated until there are no more overlaps. The last several steps are slightly modified. Now we explain the algorithm in more detail.
We define the cost function c on E in such a way that the larger the overlap on an edge becomes, the smaller the cost of this edge comes to be. Let (i, j) ∈ E. If the rectangles B i and B j do not overlap then c(i, j) = dist(B i , B j ), that is the distance between B i and B j . Otherwise, for a real number t let us denote by B j (t) a rectangle with the same dimensions as B j and with the same orientation, but with the center at p i + t(p j − p i ). We find t ij > 1 such that the rectangles B i and B j (t ij ) touch each other. Let s = p j − p i , where denotes the Euclidean norm. We set c(i, j) = −(t ij − 1)s. See Figure 1 for an illustration.  For overlapping nodes −c ij is equal to the minimal distance that is necessary to shift the boxes along the edge direction so they touch each other.
Having the cost function ready, we compute a minimum spanning tree T on D. Remember that it is a tree with the set of vertices V for which the cost, e∈E c(e), is minimal, where E is the set of edges of the tree. We use Prim's algorithm to find T .
The algorithm proceeds by growing T , similar to the growth of a tree in nature. It starts from the root of T . For each child of the root overlapping with the root, it extends the edge connecting the root and the child to remove the overlap. To achieve this, it keeps the root fixed but translates the sub-tree of the child. The edges between the root and other children remain unchanged. The algorithm recursively processes the children of the root in the same manner. This process is described in Algorithm 1.
The number t ij in line 5 of Algorithm 1 is the same as in the definition of the cost of the edge (i, j) when B i and B j overlap, and is 1 otherwise.
Algorithm 1: Growing T Input: Current center positions p and root r Output: New center positions p The algorithm does not update all positions for the child sub-tree nodes immediately, but updates only the root of the sub-tree. Using the initial positions of a parent and a child, and the new position of the parent, the algorithm obtains the new position of the child in line 5. In total, Algorithm 1 works in O(|V |) steps. The choice of the root of the tree does not matter. Different roots produce the same results modulo a translation of the plane by a vector. Indeed it can be  shown that after applying the algorithm, for any i, j ∈ V the vector p j − p i is defined uniquely by the path from i to j in T . While an overlap along any edge of the triangulation exists, we iterate, starting from finding a Delaunay triangulation, then building a minimum spanning tree on it, and finally running Algorithm 1. See Figure 2 for an example.
When there are no overlaps on the edges of the triangulation, as noticed by Gansner and Hu [6], overlaps are still possible. We follow the same idea as PRISM and modify the iteration step. In addition to calculating the Delaunay triangulation we run a sweep-line algorithm to find all overlapping node pairs and augment the Delaunay graph D with each such a pair. As a consequence, the resulting minimum spanning tree contains non-Delaunay edges catching the overlaps, and the rest of the overlaps are removed. This stage usually requires much less time than the previous one.
It is possible to create an example where the algorithm will not remove all overlaps. However, such examples are extremely rare and have not been seen yet in practice of using MSAGL or in our experiments. MSAGL applies random tiny changes to the initial layout which prevents GTree from cycling.

Comparing PRISM and GTree by Measuring Layout
Similarity, Quality, and Run Time Our data includes the same set of graphs that was used by the authors of PRISM to compare it with other algorithms [6]. The set is available in the Graphviz open source package 3 . We also used a small collection of random graphs and a collection of about 10,000 files 4 . For the experiments we use a modified version of Dot, where we can invoke either GTree or Prism for the overlap removal step, and we also used MSAGL, where we implemented PRISM and GTree. MSAGL was used only to obtain the quality measures. We ran the experiments on a PC with Linux, 64bit and an Intel Core i7-2600K CPU@3.40GHz with 16GB RAM. Some of resulting layouts can be seen in Figures 3,5,6. One can try to resolve overlap by scaling the node centers of the original layout. If there are no two coincident node centers this will work, but the resulting layout may require a huge area if some centers are close to each other. We consider the area of the final layout as one of the quality measures, and usually PRISM produces a smaller area than GTree, see Table 1.
In addition to comparing the areas, we compare some other layout properties. Following Gansner and Hu [6], we look at edge length dissimilarity, denoted as σ edge . This measure reflects the relative change of the edge lengths of a Delaunay Triangulation on the node centers of the original layout.
The other measure, which is denoted by σ disp , is the Procrustean similarity [1]. It shows how close the transformation of the original graph is to a combination of a scale, a rotation, and a shift transformation. PRISM and GTree performs similar in the last two measures as Table 1 shows. PRISM original layout GTree Fig. 3: Comparison between PRISM, original, and GTree layouts. In four top rows the initial layouts were generated randomly. At the bottom are the drawings of nodes of graph "root" which was initially laid out by the Multi Dimensional Scaling algorithm of MSAGL. In our opinion, the initial structure is more preserved in the right column, containing the results of GTree.
To distinguish the methods further, we measure the change in the set of k closest neighbors of the nodes. Namely, let p 1 , . . . , p n be the positions of the node centers, and let k be an integer such that 0 < k ≤ n. Let I = {1, . . . , n} be the set of node indices. For each i ∈ I we define N k (i) ⊂ I \ {i}, such that |N k (p, i)| = k, and for every j ∈ I \ N k (p, i) and for every j ∈ N k (p, i) holds p j − p i ≥ p j − p i . In other words, N k (p, i) represents a set of k closest neighbors of i, excluding i. Let p 1 , . . . , p n be transformed node centers. To see how much the layout is distorted nearby node i, we intersect N k (p, i) and N k (p , i). We measure the distortion as (k − m) 2 , where m is the number of elements in the intersection. One can see that if the node preserves its k closest neighbors then the distortion is zero.
Our experiments for k from 8 to 12 show that under this measure GTree produced a smaller error, showing less distortion, on 8 graphs from 14, and on the rest PRISM produced a better result, see Table 2. GTree produced a smaller error on all small random graphs from other collections 5 . We ran tests on the graphs from a subdirectory of the same site called "dot files", let us call this set of graphs collection A. Each graph from A represents the control flow of a method from a version of the .NET framework. A contains 10077 graphs. The graph sizes do not exceed several thousands. We used the Multi Dimensional Scaling algorithms of MSAGL for the initial layout in this test. The results of the run are summarized in Table 3.

Runtime Comparison
Both methods remove the overlap iteratively using the proximity graph. However, while PRISM needs O(|V | · |V |) time to solve the stress model, GTree needs only O(|V |) time per iteration with the growing tree procedure. Therefore, GTree is asymptotically faster in a single iteration. In addition, as Table 1 (right) shows, GTree usually needs fewer iterations than PRISM, especially on larger graphs. The overall runtime can be seen in Figure 4. It shows that GTree outperforms PRISM on larger graphs.
In Figure 5 we experiment with the way we expand the edges. Instead of the formula p j = p i +t ij (p j −p i ), which resolves the overlap between the nodes i and j immediately, we use the update p j = p i + min(t ij , 1.5)(p j − p i ). As a result, the algorithm runs a little bit slower but produces layouts with smaller area. q q q q q q q q q q q q q q q q q q q q q q q q q q q q

Conclusion & Future Work
We proposed a new overlap removal algorithm that uses the minimum spanning tree. The algorithm is simple and easy to implement, and yet it preserves the initial layout well and is efficient.
Although we introduced our approach in the context of graph visualization, our method can also be used for any other purpose where overlap needs to be resolved while maintaining the initial layout. Finding a measure of how well an overlap removal algorithm preserves clusters of the initial layout seems to be an interesting challenge. and left to right: b100, b102, b124, b143, badvoro, dpd, mode, -NaN, ngk10 4, root, rowe, size, unix, and xx. To make the original drawings more readable they have been changed; In most cases the nodes were diminished and the edges removed. The drawings were scaled differently.


Domain specialization: a post-training domain adaptation for Neural Machine Translation

Domain adaptation is a key feature in Machine Translation. It generally encompasses terminology, domain and style adaptation, especially for human post-editing workflows in Computer Assisted Translation (CAT). With Neural Machine Translation (NMT), we introduce a new notion of domain adaptation that we call"specialization"and which is showing promising results both in the learning speed and in adaptation accuracy. In this paper, we propose to explore this approach under several perspectives.

Introduction
Domain adaptation techniques have successfully been used in Statistical Machine Translation. It is well known that an optimized model on a specific genre (litterature, speech, IT, patent...) obtains higher accuracy results than a "generic" system. The adaptation process can be done before, during or after the training process.
We propose to explore a new post-process approach, which incrementally adapt a "generic" model to a specific domain by running additional training epochs over newly available in-domain data.
In this way, adaptation proceeds incrementally when new in-domain data becomes available, generated by human translators in a post-edition context. Similar to the Computer Assisted Translation (CAT) framework described in (Cettolo et al., 2014).

Contributions
The main contribution of this paper is a study of the new "specialization" approach, which aims to adapt generic NMT model without a full retraining process. Actually, it consist in using the generic model in a retraining phase, which only involves additional in-domain data. Results show this approach can reach good performances in a far less time than full-retraining, which is a key feature to adapt rapidly models in a CAT framework.

Approach
Following the framework proposed by (Cettolo et al., 2014), we seek to adapt incrementally a generic model to a specific task or domain. They show incremental adaptation brings new information in a Phrase-Based Statistical Machine Translation like terminology or style, which can also belong to the human translator. Recent advances in Machine Translation focuses on Neural Machine Translation approaches, for which we propose a method to adapt incrementally to a specific domain, in this specific framework.
The main idea of the approach is to specialize a generic model already trained on generic data. Hence, we propose to retrain the generic model on specific data, though several training iterations (see figure 2). The retraining process consist in re-estimating the conditional probability p(y 1 , . . . , y m |x 1 , . . . , x n ) where (x 1 , . . . , x n ) is an input sequence of length n and (y 1 , . . . , y m ) is its corresponding output sequence whose length m may differ from n. This is done without dropping the previous learning states of the Recurrent Neural Network.
The resulting model is considered as adapted or specialized to a specific domain.

Experiment framework
We create our own data framework described in the next section and we evaluate our results using the BLEU score (Papineni et al., 2002)  In-domain data Figure 1: The generic model is trained with generic data, then the generic model obtained is retrained with in-domain data to generate an specialized model. bines the attention model approach (Luong et al., 2015) jointly with the sequence-to-sequence approach (Sutskever et al., 2014). According to our approach, we propose to compare several configurations, in which main difference is the training corpus. On one hand, we consider the generic data and several amounts of in-domain data for the training process. On the other hand, only the generic data are considered for the training process, then several amounts of in-domain data are used only for the specialization process in a retraining phase. The main idea behind these experiment is to simulate an incremental adaptation framework, which enables the adaptation process only when data are available (e.g.: translation post-editions done by a human translator.) The approach is studied in the light of two experiments and a short linguistic study. The first experiment concerns the impact of "specialization" approach among several additional epochs; then, the second one, focuses on the amount of data needed to observe a significant impact on the translation scores. Finally, we propose to compare some translation examples from several outputs.

Training data
The table 1 presents all data used in our experiments. We propose to create a generic model with comparable amount of several corpora, which each of them belong to a specific domain (IT, literature, news, parliament). All corpora are available from the OPUS repository (Tiedemann, 2012).
We propose to specialize the generic model using a last corpus, which is a corpus extracted from the European Medical Agency (emea). The corpus is composed of more than 650 documents, which are medicine manuals.
We took apart a 2K lines as test corpus, then, to simulate the incremental adding of data, we cre-  ated four training corpora corresponding to several amount of documents: 500, 5K, 50K and all the lines of the training corpus. These amount of data are corresponding roughly to 10% of a document, one document and ten documents, respectively.

Training Details
The Neural Machine Translation approach we use is following the sequence-to-sequence approach (Sutskever et al., 2014) combined with attentional architecture (Luong et al., 2015). In addition, all the generic and in-domain data are pre-processed using the byte pair encoding compression algorithm (Sennrich et al., 2016) with 30K operations, to avoid Out-of-Vocabulary words. We keep the most frequent 32K words for both source and target languages with 4 hidden layers with 500-dimensional embeddings and 800 bidirectional Long-Short Term Memory (bi-LSTM) cells. During training we use a mini-batch size of 64 with dropout probability set to 0.3. We train our models for 18 epochs and the learning rate is set to 1 and start decay after epoch 10 by 0.5. It takes about 8 days to train the generic model on our NVidia GeForce GTX 1080.
The models were trained with the open-source toolkit seq2seq-attn 1 (Kim and Rush, 2016).

Experiments
As a baseline, we fully trained five systems, one with the generic data (generic) and the other with generic and various amount of in-domain data: 500 lines (emea-0.5K), 5K lines (emea-5K) and 50K lines (emea-50K). The evaluation is done on the in-domain test (emea-tst) and presented in the table 2. Without surprises, the more the model is trained with in-domain data the more BLEU and TER scores are improved. These models are baselines in incremental adaptation experiments.

Performances among training iterations
The first study aims to evaluate the approach among additional training iterations (also called "epochs"). Figure 2 presents the curve of performances when the specialization approach is applied to the generic model by using all in-domain data (emea-full). We compare the results with two baselines: on the top of the graphic, we show a line which corresponds to the score obtained by the model trained with both generic and in-domain data (noted generic+emea-full); On the bottom, the line is associated to the generic model score, which is trained with only generic data (noted generic). The curve is done with the generic model specialized with five epochs additional epochs on all in-domain data (noted specialized model with emea). In the graphic, we can observe that a gap obtained with the first additional epoch with more than 13 points, but then the BLEU score improves around 0.15 points with each additional epoch and tend to stall after 10 epochs (not shown).
So far, the specialization approach does not replace a full retraining, while the specialization curve does not reach the generic+emea-full model. But, the retraining time of one additional epoch with all in-domain data is around 1 hour and 45 minutes, while a full retraining would takes   Table 4: Time spent for each process, the training and the specialization process, according to the amount of data we have.
more than 8 days. In our CAT framework, even 1 hour and 45 minutes is too much, the adaptation process need to be performed faster with smaller amount of data like a part of a document (500 lines) or a full document (5K lines). Considering the time constraint, the approach tends to be performed though one additional epoch.

Performances among data size
The second experiment concerns the observation of specialization performances when we vary the amount of data. Using the data presented Table 1, we apply the specialization process on the generic corpus by taking 0.5K, 5K, 50K and all the indomain data (as presented in section 3.1). According to our previous study (see section 3.3.1), we focuses on the results obtained with only one additional epoch.
We can observe that with only 500 lines, the improvements reaches more than 1 BLEU points and 2 TER points. Then, with 10 time more additional data, BLEU and TER scores improved the baseline of 2 and nearly 4 points, respectively. With more additional data (10 documents), improvements reach 8 points of BLEU and 9 points of TER. Finally with all the in-domain data available, the specialization increase the baseline of 13 points of both BLEU and TER scores.
Comparing the approach with retraining all the generic data, with the same amount of in-domain data, it appears our approach reaches nearly the same results. Moreover, with 50K of in-domain data, the specialization approach performs better of 0.5 of BLEU and TER points. But, when we have much more in-domain data available, the specialization approach does not outperforms the full retraining (39.44 against 41.97 BLEU points).

Discussion
Focussing on the time constraint of the CAT framework, the table 4 presents the time taken to process our specialization approach. It goes from less than one minutes to more than 1 hour and 45 minutes. If we compare this table with the table 3, we observe that this approach enables to gain 1 BLEU point in less than 1 minute, 2 points in 1 minute and more than 6 BLEU points in 6 minutes. The ratio of "time spent" to "score gained" seems impressive.
The table 5 shows an example of the outputs obtained with the specialization approach. We compare the generic model compared to the specialized models with respectively 0.5K, 5K and 50K lines of in-domain data.
We can clearly see the improvements obtained on the translation outputs. Even if the last one does not stick strictly to the reference, the translation output can be considered as a good translation (syntactically well formed and semantically equivalent).
This specialization approach can be seen as an optimization process (like in classical Phrase-Based approach), which aims to tune the model (Och, 2003).

Related work
Last years, domain adaptation for machine translation has received lot of attention and studies. These approaches can be processed at three levels: the pre-processing, the training, the postprocessing. In a CAT framework, most of the approaches focuses on the pre-processing or on the post-processing to adapt models.
Such pre-processing approaches like data selection introduced by (Lü et al., 2007) and improved by (Gao and Zhang, 2002) and many others (Moore and Lewis, 2010; Axelrod et al., 2011) are effective and their impact studied (Lambert et al., 2011;Cettolo et al., 2014;Wuebker et al., 2014). But, the main draw back of these approaches is they need a full retrain to be effective.
The post-training family concerns methods which aims to update the model or to optimize the model to a specific domain. Our approach belongs to this category. This approach is inspired by (Luong and Manning, 2015), they propose to train a generic model and, then, they further a training over a dozen of epochs on a full in-domain data (the TED corpus). We do believe this approach is under estimated and we propose to study its efficiency in a specific CAT framework with a few data. On one hand, we propose to follow this approach by proposing to use a fully trained generic model. But, on the other hand, we propose to train further only on small specific data over a few additional epochs (from 1 to 5). In this way, our approach is slightly different and can be equated to a tuning process (Och, 2003).

Conclusion
In this paper we propose a study of the "specialization" approach. This domain adaptation approach shows good improvements with few in-domain data in a very short time. For instance, to gain 2 BLEU points, we used 5K lines of in-domain data, which takes 1 minute to be performed.
Moreover, this approach reaches the same results as a full retraining, when 10 documents are available. Within a CAT framework, this approach could be a solution for incremental adaptation of NMT models, and could be performed between two rounds of post-edition. In this way, we propose as future work to evaluate our approach in a real CAT framework.