summaries: The authors present a method that computes a saliency map after each scale block of a CNN and combines them according to the weights of the prior layers in a final saliency map. The paper gives two main contributions: SMOE, which captures the informativeness of the corresponding layers of the scale block and LOVI, a heatmap based on HSV, giving information of the region of interest according to the corresponding scale blocks. The method is interesting as it does not require multiple backward passes such as other gradient-based method and thus prove to be more time-efficient.

summaries: This paper presents a method for creating saliency maps reflecting what a network deems important while also proposing an interesting method for visualizing this. The central premise for the method of characterizing relative importance of information represented by the network is based on an information theoretic measure. A variety of results are presented to examine the impact of keeping or removing information deemed important by this measure and a comparison is made to existing approaches as a justification for the proposed methods.

summaries: The paper presents a new approach, SMOE scale, to extract saliency maps from a neural network. The approach is deemed as efficient, because it does not require one or multiple backward passes, as opposed to other approaches based on gradients. The main idea is to process the output activation tensors of a few selected layers in a deep network using an operator combining mean and std.dev. called SMOE scale. The result of this operator can be combined through different scales to obtain a global saliency map, or visualized in such a way that shows the consistency of saliency maps at different scales. Experiments show some improvement against traditional gradient-based approaches.

abstractText: We describe an explainable AI saliency map method for use with deep convolutional neural networks (CNN) that is much more efficient than popular gradient methods. It is also quantitatively similar and better in accuracy. Our technique works by measuring information at the end of each network scale which is then combined into a single saliency map. We describe how saliency measures can be made more efficient by exploiting Saliency Map Order Equivalence. Finally, we visualize individual scale/layer contributions by using a Layer Ordered Visualization of Information. This provides an interesting comparison of scale information contributions within the network not provided by other saliency map methods. Since our method only requires a single forward pass through a few of the layers in a network, it is at least 97x faster than Guided Backprop and much more accurate. Using our method instead of Guided Backprop, class activation methods such as Grad-CAM, Grad-CAM++ and Smooth Grad-CAM++ will run several orders of magnitude faster, have a significantly smaller memory footprint and be more accurate. This will make such methods feasible on resource limited platforms such as robots, cell phones and low cost industrial devices. This will also significantly help them work in extremely data intensive applications such as satellite image processing. All without sacrificing accuracy. Our method is generally straight forward and should be applicable to the most commonly used CNNs 1.

authors:
Chun-Hao Chang
Elliot Creager
Anna Goldenberg
David Duvenaud

title: Explaining image classifiers by adaptive dropout and generative in-filling

authors:
Aditya Chattopadhyay
Anirban Sarkar
Prantik Howlader
Vineeth N Balasubramanian

title: Gradcam++: Improved visual explanations for deep convolutional networks

venue: In WACV,

authors:
S.C. Choi
R. Wette

title: Maximum likelihood estimation of the parameters of the gamma distribution and their bias

authors:
Piotr Dabkowski
Yarin Gal

title: Real time image saliency for black box classifiers

venue: In NIPS,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: In CVPR,

authors:
Ruth Fong
Andrea Vedaldi

title: Interpretable explanation of black boxes by meaningful perturbation

venue: In ICCV,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Sara Hooker
Dumitru Erhan
Pieter-Jan Kindermans
Been Kim

title: Evaluating feature importance estimates

venue: In ICML workshop on Human Interpretability in Machine Learning,

authors:
Gao Huang
Zhuang Liu
Kilian Q. Weinberger
Laurens van der Maaten

title: Densely connected convolutional networks

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In ICML,

authors:
Laurent Itti
Christof Koch

title: Computational modelling of visual attention

venue: Nature Neuroscience,

authors:
Laurent Itti
Ernst Niebur
Christof Koch

title: A model of saliency-based visual attention for rapid scene analysis

venue: IEEE Transactions on Pattern Analysis & Machine Intelligence,

authors:
Jongheon Jeong
Jinwoo Shin

title: Training cnns with selective allocation of channels

authors:
George H. Joblove
Donald Greenberg

title: Color spaces for computer graphics

venue: Computer Graphics,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E. Hinton

title: ImageNet classification with deep convolutional neural networks

authors:
T Nathan Mundhenk
Goran Konjevod
Wesam A Sakla
Kofi Boakye

title: A large contextual dataset for classification, detection and counting of cars with deep learning

authors:
Vinod Nair
Geoffrey E. Hinton

title: Rectified linear units improve restricted boltzmann machines

authors:
Daniel Omeiza
Skyler Speakman
Celia Cintas
Komminist Weldemariam

title: Smooth gradcam++: An enhanced inference level visualization technique for deep convolutional neural network models

authors:
Badri N Patro
Mayank Lunayach
Shivansh Patel
Vinay P. Namboodiri

title: U-cam: Visual explanation using uncertanty based class activation

authors:
Wojciech Samek
Alexander Binder
Grégoire Montavon
Sebastian Lapuschkin
Klaus-Robert Müller

title: Evaluating the visualization of what a deep neural network has learned

venue: IEEE Transactions on Neural Networks and Learning Systems,

authors:
Ramprasaath R. Selvaraju
Michael Cogswell
Abhishek Das
Ramakrishna Vedantam
Devi Parikh
Dhruv Batra

title: Grad-cam: Visual explanations from deep networks via gradient-based localization

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

authors:
Daniel Smilkov
Nikhil Thorat
Been Kim
Fernanda Vigas
Martin Wattenberg

title: Smoothgrad: removing noise by adding noise

authors:
Jost Tobias Springenberg
Alexey Dosovitskiy
Thomas Brox
Martin Riedmille

title: Striving for simplicity: The all convolutional net

venue: In ICLR Workshop,

title: Axiomatic attribution for deep networks

authors:
Peter Welinder
Steve Branson
Takeshi Mita
Catherine Wah
Florian Schroff
Serge Belongie
Pietro Perona

title: Caltech-UCSD Birds 200

venue: Technical Report CNS-TR-2010-001, California Institute of Technology,

authors:
Linjie Yang
Ping Luo
Chen Change Loy
Xiaoou Tang

title: A large-scale car dataset for finegrained categorization and verification

authors:
Matthew D. Zeiler
Rob Fergus

title: Visualizing and understanding convolutional networks

venue: In ECCV,

authors:
Bolei Zhou
Agata Lapedriza Garcia
Jianxiong Xiao
Antonio Torralba
Aude Oliva

title: Learning deep features for scene recognition using places database

heading: 1 INTRODUCTION

text:
Deep neural networks (DNN) have provided a new burst of research in the machine learning community. However, their complexity obfuscates the underlying processes that drive their inferences. This has lead to a new field of explainable AI (XAI). A variety of tools are being developed to enable researchers to peer into the inner workings of DNNs. One such tool is the XAI saliency map. It is generally used with image or video processing applications and is supposed to show what parts of an image or video frame are most important to a network’s decisions. The seemingly most popular methods derive a gradient saliency map by back-propagating a gradient from the end of the network and project it onto an image plane (Simonyan et al., 2014; Zeiler & Fergus, 2014; Springenberg et al., 2015; Sundararajan et al., 2017; Patro et al., 2019). The gradient can typically be from a loss function, layer activation or class activation. Thus, it requires storage of the data necessary to compute a full backward pass on the input image.
Several newer methods attempt to iteratively augment the image or a mask in ways that affect the precision of the results (Fong & Vedaldi, 2017; Chang et al., 2018). Additionally, saliency map encoders can be trained within the network itself (Dabkowski & Gal, 2017). Both of these methods have a distinct advantage of being more self-evidently empirical when compared with gradient techniques. Class Activation Map (CAM) methods (Selvaraju et al., 2017; Chattopadhyay et al., 2018; Omeiza et al., 2019) efficiently map a specified class to a region in an image, but the saliency map is very coarse. They generally use a method like Guided Backprop (Springenberg et al., 2015) to add finer pixel level details. This requires a full backwards pass through the network, and it adds significant memory and computational overhead to CAM solutions relative to just computing the CAM alone. Several of the CAM methods compute gradients aside from the use of Guided Backprop, but we will differentiate them by referring to them as CAM methods.
1For reproducibility, full source code is available at http://www.anonymous.submission.com

heading: 1.1 EFFICIENCY AND WHY IT MATTERS HERE

text:
Most saliency map methods require many passes through the network in order to generate results or train. The gradient methods hypothetically would require just one backwards pass, but often require as many as 15 in order to give an accurate rendering (Hooker et al., 2018). This is not always a problem in the lab when a person has a powerful GPU development box. However, what if one would like to see the workings of the network at training time or even run time? This can be a serious hurdle when running a network on mobile or embedded platforms. It is not uncommon for hardware to be barely fast enough to process each image from a video source. Running a full backward pass can lead to dropped frames. Additionally, viewing or saving the saliency map for each frame is infeasible. Another problem is that some platforms may not have the memory capacity to save all the information required for a backward pass. Gradient based methods cannot work in these instances. Sometimes this can even be the case with powerful hardware. Satellite images can be vary large and potentially exhaust generous resources. An efficient method would enable developers in these areas to get feedback in the field and aid in debugging or understanding the behavior of a network.
Here we show a method of computing an XAI saliency map which is highly efficient. The memory and processing overhead is several orders of magnitude lower than the commonly used gradient methods. This makes it feasible in any resource limited environment. Also, since we demonstrate empirically that our method is either similar or more accurate than the most commonly used gradient methods, it can be used it to speed up run-time in any situation. It is fast enough that we already use it automatically when training networks. We notice very little degradation of training speed.

heading: 2 METHODS

heading: 2.1 SALIENCY MAP DERIVATION

text:
We were looking for a method to compute saliency maps based on certain conditions and assumptions.
1. The method used needs to be relatively efficient to support rapid analysis at both test time and during DNN training.
2. The method should have a reasonable information representation. As a DNN processes data, the flow of information should become localized to areas which are truly important.
3. The method should capture the intuition that the informativeness of a location is proportional to the overall activation level of all the filters as well their variance. That is, informative activations should have a sparse pattern with strong peaks.
Our approach works by creating saliency maps for the output layer of each scale in a neural network and then combines them. We can understand scale by noting that the most commonly used image processing DNNs work on images with filter groups at the same scale which down-sample the image and pass it to the group of filters at the next scale, and so on. Given a network like ResNet-50 (He et al., 2015) with in input image size of 224x224, we would have five scale groups of size 112x112, 56x56, 28x28, 14x14 and 7x7. It is at the end of these scale groups where we are interested in computing saliency. In this way, our approach is efficient and is computed during the standard forward pass through the network. No extra pass is needed.
To achieve localization of information, we measure statistics of activation values arising at different input locations. Given an output activation tensor T ∈ R+,p×q×r with spatial indices i, j ∈ p, q and depth index k ∈ r from some layer T = l (X). In our case l (.) is a ReLU (Nair & Hinton, 2010). We apply a function to each column at i, j over all depths k. This yields a 2D saliency map S ∈ R+,p×q where S = ϕ (T). We process the tensor after it has been batch-normalized (Ioffe & Szegedy, 2015) and processed by the activation function. When we compute Truncated Normal statistics as an alternative in later section, we take the tensor prior to the activation function.
Finally, to capture our intuition about the informativeness of an output activation tensor, we derived ϕ (.) by creating a special simplification of the maximum likelihood estimation Gamma Scale parameter (Choi & Wette, 1969). One way we can express it is:
.
ϕ (.) = 1
r · r∑ k=1 xk ·
[ log2 ( 1
r · r∑ k=1 xk ) − 1 r · r∑ k=1 log2 (xk) ] (1)
To avoid log zero, we add 1e − 06 to each xk. How mean and variance relate seems readily apparent with the square bracketed part being the computational formula for the standard deviation with values taken to log2 (.) rather than squared. This is preceded by a typical mean estimate. This meets the third requirement we mentioned. This simplification is Saliency Map Order Equivalent (SMOE) to the full iterative (and expensive) scale parameter estimation. We define SMOE as follows. Given saliency map Sa ∈ R+,p×q and Sb ∈ R+,p×q where we may have Sa 6= Sb, if we sort the pixels by value, then Sa will be sorted in exactly the same order as Sb. That means that the most salient location i, j is exactly the same in both Sa and Sb. This also means that if we create a binary mask of the n% most salient pixels, the mask for both Sa and Sb will also be exactly the same. SMOE is preserved if for instance, we apply independent monotonic functions to a saliency map. As such, we may as well strip these away to save on computation. Tie values may create an imperfect equivalence, but we assert that these should be very rare and not affect results by a measurable amount.
Using µ as the mean of each column r in T, we can see the information relation more clearly if we simplify Eq 1 further which gives us our SMOE Scale method:
ϕ (.) = 1
r · r∑ k=1 µ · log2 ( µ xk ) (2)
The resemblance to conditional entropy is apparent. However, since the values in Eq 2 are not probabilities, this does not fit the precise definition of it. On the other hand, the interpretation is fairly similar. It is the mean activation multiplied by the information we would gain if we knew the individual values which formed the mean. Put in traditional terms, it is the information in the mean conditioned on the individual values. Numerical examples of this method at work can be seen in Appendix Table 3 along with more information on the derivation. To create a 2D saliency map S ∈ R+,p×q , we simply apply Eq 2 at each spatial location i, j ∈ p, q with column elements k ∈ r in the 3D activation tensor T for a given input image.

heading: 2.2 COMBINED SALIENCY MAP GENERATION

text:
For each input image, we derive five saliency maps. For different networks, this number may vary. Given a network such as a ResNet (He et al., 2015), AlexNet (Krizhevsky et al., 2013), VGG Net (Simonyan & Zisserman, 2015) or DenseNet (Huang et al., 2017) we compute saliency on the final tensor computed at each spatial scale. Recall that most image classification networks process images in a pipeline that processes an image in consecutive groups of convolution layers where each group downsamples the image by 1/2x before passing it onto the next. It is just prior to the downsampling that we compute each saliency map. Computing saliency across image scales is a classical technique (Itti et al., 1998). This is also similar to the method used in the XAI saliency technique described in (Dabkowski & Gal, 2017).
.
To make our maps easier to visualize or combine together, we normalize them from 0 to 1 by squashing them with the normal cumulative distribution function γ (s;µ, σ). Here mean and standard deviation are computed independently over each saliency map. We then create a combined saliency map by taking the weighted average of the maps. Since they are at different scales, they are upsampled via bilinear interpolation to match the dimensions of the input image. Given r saliency maps that have been bilinear interpolated (upsampled) to the original input image size p, q, they are then combined as:
ci,j = ∑r k=1 γ (si,j,k;µk, σk) · wk∑r
k=1 wk (3)
Note that technically, we compute γ (s;µ, σ) before we upsample. Weighting is very useful since we expect that saliency maps computed later in the network should be more accurate than saliency maps computed earlier as the network has reduced more irrelevant information in deeper layers, distilling relevant pixels from noise (Tishby et al., 2000). Network activity should be more focused on relevant locations as information becomes more related to the message. We observe this behavior which can be seen later in Figure 4. A saliency map generation example can be seen in Figure 1 with many more examples in Appendix Figures 9 and 10.
The advantages of creating saliency maps this way when compared with most gradient methods are:
• Pro: This is relatively efficient, requiring processing of just five low cost layers during a standard forward pass.
• Pro: We can easily visualize the network at different stages (layers). • Con: The current method does not have a class specific activation map (CAM) (Selvaraju
et al., 2017; Chattopadhyay et al., 2018; Omeiza et al., 2019), but we discuss how this can be done later.

heading: 2.3 VISUALIZING MULTIPLE SALIENCY MAPS

text:
One advantage to computing multiple saliency maps at each scale is that we can get an idea of what is happening in the middle of the network. However, with so many saliency maps, we are starting to be overloaded with information. This could get even worse if we decided to insert saliency maps after each layer rather than just at the end of each scale. One way to deal with this is to come up with
a method of combining saliency maps into a single image that preserves useful information about each map. Such a composite saliency map should communicate where the network is most active as well as which layers specifically are active. We call our method Layer Ordered Visualization of Information (LOVI). We do this by combining saliency maps using an HSV color scheme (Joblove & Greenberg, 1978) where hue corresponds to which layer is most active at a given location. That is, it shows the mean layer around which a pixels activity is centered. Saturation tells us the uniqueness of the activation. This is the difference between the maximum value at a location and the others. Value (intensity) corresponds to the maximal activation at that location. Basically, this is a pixel’s importance.
If only one layer is active at a location, the color will be very saturated (vivid colors). On the other hand, if all layers are equally active at a given location, the pixel value will be unsaturated (white or gray). If most of the activation is towards the start of a network, a pixel will be violet or blue. If the activation mostly happens at the end, a pixel will be yellow or red. Green indicates a middle layer. Thus, the color ordering by layer follows the standard order of the rainbow. Examples can be seen in Figure 2. Given k ∈ r saliency maps S (in this instance, we have r = 5 maps), we stack them into a tensor S ∈ R+,p×q×r. Note that all s ∈ [0, 1] because of Eq 3 and they have been upsampled via bilinear interpolation to match the original input image size. Given:
φ (k) = 1− k−1r · ( r−1 r )−1 , ν = 1r (4)
Hue ∈ [0, 360] is basically the center of mass of activation for column vector s at each location i, j ∈ p, q in S:
Hue = ∑r k=1 sk · φ (k)∑r
k=1 sk · 300 (5)
Saturation ∈ [0, 1] is the inverse of the ratio of the values in s compared to if they are all equal to the maximum value. So for instance, if one value is large and all the other values are small, saturation is high. On the other hand, if all values are about the same (equal to the maximum value), saturation is very small:
Sat = 1− ∑r
k=1 (sk)− ν r ·max (s) · (1− ν)
(6)
Value ∈ [0, 1] is basically just the maximum value in vector s : V al = max (s) (7)
Once we have the HSV values for each location, we then convert the image to RGB color space in the usual manner.

heading: 2.4 QUANTIFICATION VIA ROAR AND KAR

text:
(Hooker et al., 2018) proposed a standardized method for comparing XAI saliency maps. This extends on ideas proposed by (Dabkowski & Gal, 2017; Samek et al., 2017) and in general hearkens back to methods used to compare computational saliency maps to psychophysical observations (Itti & Koch, 2001). The general idea is that if a saliency map is an accurate representation of what is important in an image, then if we block out salient regions, network performance should degrade. Conversely, if we block out non-salient regions, we should see little degradation in performance. The ROAR/KAR metrics measure these degradations explicitly. The KAR metric (Keep And Retrain) works by blanking out the least salient information/pixels in an input image, and the ROAR (Remove And Retrain) metric uses the contrary strategy and removes the most salient pixels. Figure 3 shows an example of ROAR and KAR masked image. A key component to the ROAR/KAR method is that the network needs to be retrained with saliency masking in place. This is because when we mask out regions in an input image, we unavoidably create artifacts. By retraining the network on masked images, the network learns to ignore the new artifacts and focus on image information.
We will give a few examples to show why we need both metrics. If a saliency map is good at deciding which parts of an image are least informative but gets the ranking of the most salient objects wrong, ROAR scores will suggest the method is very good. This is because it masks out the most salient locations in one large grouping. However, ROAR will be unable to diagnose that the saliency map has erroneously ranked the most informative locations until we have removed 50% or more of the salient pixels. As such, we get no differentiation between the top 1% and the top 10% most salient pixels. On the other hand, KAR directly measures how well the saliency map has ranked the most informative locations. By using both metrics, we can quantify the goodness of both the most and least salient locations in a map.
.

heading: 3 QUANTITATIVE EXPERIMENTS

heading: 3.1 COMPARING DIFFERENT EFFICIENT STATISTICS

text:
We tested our SMOE Scale saliency map method against several other statistical measures using three different datasets that have fairly different tasks and can be effectively trained from scratch. The sets used are ImageNet (Deng et al., 2009), CSAIL Places (Zhou et al., 2014) and COWC (Mundhenk et al., 2016). ImageNet as a task focuses on foreground identification of objects in standard photographic images. Places has more emphasis on background objects, so we would expect more spatial distribution of useful information. COWC, Cars Overhead With Context is an overhead dataset for counting as many as 64 cars per image. We might expect information to be spatially and discretely localized, but distributed over many locations. In summary, these three datasets are expected to have fairly different distributions of important information within each image. This should give us more insight into performance than if we used several task-similar datasets (e.g. Three photographic foreground object sets such as; ImageNet + CUB (birds) (Welinder et al., 2010) + CompCars (Yang et al., 2015)).
For compatibility with (Hooker et al., 2018), we used a ResNet-50 network (He et al., 2015). We also show performance on a per layer basis in order to understand the accuracy at different levels of the network. For comparison with our SMOE Scale method, we included any statistical measure which had at least a modicum of justification and was within the realm of the efficiency we were aiming for. These included parameter and entropy estimations from Normal, Truncated-normal, Log-normal and Gamma Distribution models. We also tested Shanon Entropy and Renyi Entropy. To save compute time, we did a preliminary test on each method and did not continue using it if the results qualitatively appeared very poor and highly unlikely to yield good quantitative results. Normal entropy was excluded because it is SMOE with the Normal standard deviation. This left us with nine possible statistical models which we will discuss in further detail.
Saliency maps for each method are computed over each tensor column in the same way as we did with our SMOE Scale metric. The only difference is with the truncated-normal statistic which computes parameters prior to the ReLU layer. We should note that (Jeong & Shin, 2019) uses a truncated normal distribution to measure network information for network design. Recall that we have five saliency map layers. They are at the end of each of the five network spatial scales. We test each one at a time. This is done by setting the network with pre-trained weights for the specific dataset. Then, all weights in the network which come after the saliency mask to be tested are allowed to fine-tune over 25 epochs. Otherwise, we used the same methodology as (He et al., 2015) for data augmentation etc. This is necessary in order to adapt the network to mask related artifacts as specified in the ROAR/KAR protocol. At the level where the saliency map is generated, we mask out pixels in the activation tensor by setting them to zero. For this experiment, we computed the ROAR statistic for the 10% least salient pixels. For KAR, we computed a map to only let through the top 2.5% most salient pixels. This creates a more similar magnitude between ROAR and KAR measures. Layer scores for the top five methods can be seen in Figure 4. We combine layer scores two different ways since ROAR and KAR scores are not quite proportional. These methods both yield very similar results. The first method takes the improvement difference between
.
tested method’s score and a randomized mask score. We have five κ ∈ [0, 1] KAR scores for a method. We have five ρ ∈ [0, 1] ROAR scores for a method and five z ∈ [0, 1] scores from a random mask condition. This corresponds to each saliency map spatial scale which we tested. We compute a simple difference score as:
D (ρ, κ) = 5∑ p=1 (zp − ρp) + 5∑ q=1 (κq − zq) (8)
The second method is an information gain score given by:
I (ρ, κ) = − 5∑
p=1
ρp · log2 ( ρp zp ) − 5∑ q=1 zq · log2 ( zq κq ) (9)
Table 1 shows the results.

heading: 3.2 COMPARISON WITH POPULAR METHODS

text:
We compare our method with three popular saliency map methods using the standard ROAR/KAR methodology. These are Gradient Heatmaps (Simonyan et al., 2014), Guided Backprop (Springenberg et al., 2015) and Integrated Gradients (Sundararajan et al., 2017). All methods use SmoothGrad-Squared (Smilkov et al., 2017) which gives generally the best results. We should note that without SmoothGrad or another augmentation, all three do not yield very good ROAR/KAR scores.
We compare three different weighting strategies when combining the saliency maps from all five scales. In the first strategy, we weight all five maps equal [1,1,1,1,1]. In the second, we use a ruleof-thumb like approach where we weight the first layer the least since it should be less accurate. Then each successive layer is weighted more. For this we choose the weights to be [1,2,3,4,5]. The third method weights the maps based on the expected accuracy given our results when we computed Table 1. These prior weights are [0.18, 0.15, 0.37, 0.4, 0.72]. The reason for showing the rule-ofthumb results is to give an idea of performance given imperfect weights since one may not want to spend time computing optimal prior weights.
To fairly compare the three popular saliency map methods with our own, we adopt a methodology as close as possible to (Hooker et al., 2018). We train a ResNet-50 from scratch on ImageNet with either ROAR or KAR masking (computed by each of the different saliency mapping approaches in turn) at the start of the network. Otherwise, our training method is the same as (He et al., 2015). The comparison results are shown in Figure 5. We can try and refine these results into fewer scores by subtracting the sum of the ROAR scores from the sum of the KAR scores. The results can be seen in Table 2. The KAR score for our method is superior to all three comparison methods. The ROAR score is better than Guided Backpropagation and Integrated Gradients. This suggests our method is superior at correctly determining which locations are most salient, but is not as good as Gradient Heatmaps for determining which parts of the image are least informative.

heading: 4 DISCUSSION

heading: 4.1 METHOD EFFICIENCY

text:
The method as proposed is much faster than the three baseline comparison methods. Given a ResNet-50 network, we only process five layers. The other methods require a special back propagation step over all layers. We can compute the cost in time by looking at operations that come from three sources. The first is the computation of statistics on tensors in five layers. The second is
the normalization of each 2D saliency map. Third we account for the cost of combing the saliency maps.
Ops for our solution ranges from 1.1x107 to 3.9x107 FLOPs (using terminology from (He et al., 2015)) for a ResNet-50. The network itself has 3.8x109 FLOPs in total. The range in our count comes from how we measure Log and Error Function operations that are computationally expensive compared to more standard ops and whose implementations vary. We estimate the worst case from available software instantiations. Most of the work comes from the initial computation of statistics over activation tensors. This ranges from 9.2x106 to 3.7 x 107 FLOPs. In total, this gives us an overhead of 0.3% to 1.0% relative to a ResNet-50 forward pass. All gradient methods have a nominal overhead of at least 100%. A breakdown of the FLOPs per layer and component can be seen in Table 6 in the appendix.
Compared to any method which requires a full backward pass, such as gradient methods, our solution is nominally between 97x and 344x faster for non-SmoothGrad techniques, which according to (Hooker et al., 2018) performs poorly on ROAR/KAR scores. We are between 1456x and 5181x faster than a 15-iteration SmoothGrad implementation that yields the competitive results in Table 2. 15 iterations as well as other parameters was chosen by (Hooker et al., 2018) who describe this selection in more detail.
The memory footprint of our method is minuscule. Computation over tensors can be done inline which leaves the largest storage demand being the retention of 2D saliency maps. This is increased slightly by needing to store one extra 112x112 image during bilinear up-sampling. Peak memory overhead related to data is about 117 kilobytes per 224x224 input image.

heading: 4.2 USAGE WITH A CLASS ACTIVATION MAP

text:
Our method does not have a class activation map (Selvaraju et al., 2017; Chattopadhyay et al., 2018; Omeiza et al., 2019) in the current implementation. This is because what we have is more akin to Guided Backprop which Grad-CAM etc. combine with their class activation map to improve their pixel level accuracy. The overhead for the class activation map itself is not large since in practice, it involves computing gradients over the last few network layers only. This makes Guided Backprop
.
the most expensive computational part. By replacing it with our method, accuracy should increase as per Table 2 while dramatically reducing both computational and memory overhead.

heading: 4.3 SMOE SCALE IS THE MOST ROBUST MEASURE

text: SMOE Scale is the only metric without a failure case among all the statistics we tested. It is the only static that reliably scores in the top half of all the ones we tested. For Image Net and Places, it is the only one always in the top three. All statistics except for SMOE Scale and Shannon Entropy have at least one layer where they have a difference score at or below zero. This means they are as accurate as a random saliency map for at least one condition. SMOE Scale is the most robust statistic to use in terms of expected accuracy. The next highest scoring statistics, standard deviation and truncated normal entropy, are no better than a random on layer 1. Figure 6 shows why this may be. It is important to note that layer 1 contains the finest pixel details and should be expected to be important in rendering visual detail in the final combined saliency map.

heading: 5 CONCLUSION

text: We have created a method of XAI saliency which is extremely efficent and is quantitatively comparable or better than several popular methods. It can also be used to create a saliency map with interpretability of individual scale layers. Future work includes creating a class specific activation map and expanding it to non-DNN architectures. We are currently testing our class activation map integration Fast-CAM and will introduce it in a future work.

heading: A APPENDIX

heading: A.1 DERIVATION OF SMOE SCALE

text:
The maximum likelihood estimator of scale in the Gamma probability distribution is given as:
θ̂ = 1
kn n∑ i=1 xi (10)
This requires the additional iterative estimation of the shape parameter k starting with an estimate s:
s = ln
( 1
n n∑ i=1 xi ) − 1 n n∑ i=1 ln(xi) (11)
Then we get to within 1.5% of the correct answer via:
k ≈ 3− s+ √ (s− 3)2 + 24s 12s
(12)
Then we use the Newton-Ralphson update to finish:
k ← k − ln(k)− ψ(k)− s1 k − ψ′(k)
(13)
But we can see application of Eqs 12 and 13 is monotonic. This is also apparent from the example which we can see in Figure 7.
k is SMOE to 1s , so we rewrite Eq 10 with the reciprocal of k and optionally use the more efficient log2 as:
θ̂SMOE = 1
n · n∑ i=1 xi ·
[ log2 ( 1
n · n∑ i=1 xi ) − 1 n · n∑ i=1 log2 (xi) ] (14)
This then simplifies to:
θ̂SMOE = 1
n · n∑ i=1 µ · log2 ( µ xn ) (15)
We can see the results this gives with different kinds of data in Table 3

heading: A.2 MORE EXAMPLES OF KAR SALIENCY MASKS

heading: A.3 MORE EXAMPLES OF COMBINED SALIENCY MAPS

heading: A.4 MORE EXAMPLES OF LOVI SALIENCY MAPS

heading: A.5 COMPARING DIFFERENT EFFICIENT STATISTICS IN MORE DETAIL

text: This subsection shows the raw scores for each statistic over each dataset.

heading: COWC

heading: A.6 COMBINED KAR AND ROAR SCORES WITH MORE DETAIL

text: This subsection shows the raw scores for each ROAR and KAR mask. We also added the nonSmoothGrad methods so we can see how much of an improvement it makes.

heading: A.7 OPERATIONS COMPUTATION


summaries: This work proposes an alternative approach to non-autoregressive translation (NAT) by predicting positions in addition to the word identities, such that the word order in the final prediction doesn't matter as long as the positions are correct. The length of the translation is predicted similar to Gu et al 2017, as well as smoothly copying the source sequence to decoder input. However, since the positions are unknown, this paper employs a heuristic search method to find the nearest neighbors in the embedding space to obtain position supervision.

summaries: This work builds on the non-autoregressive translation (NAT) by using position as a latent variable. Unlike the work by Gu et. al. 2018, where they assume the output word order to follow the word order of the input sentence, this work explores predicting word order supervision as an additional train signal. It shows that predicting the position of the words improves the performance of the translation and paraphrase task. This paper uses a heuristic that the inputs positions and output positions of the decoder with close by embeddings are more likely to represent the position mapping.

summaries: This work proposes a non-autoregressive model for conditioned text generation. The non-autoregressive decoder conditions on a sequence of discrete latent variables, which represent the generation order and can be autoregressively calculated. Instead of doing marginal inference, the paper takes the top 1 generation order that best match inputs. Experiments on machine translation and paraphrase generation show strong result in comparison to other non-autoregressive models.

abstractText: Non-autoregressive models are promising on various text generation tasks. Previous work hardly considers to explicitly model the positions of generated words. However, the position modeling is an essential problem in non-autoregressive text generation. In this study, we propose PNAT, which incorporates positions as a latent variable into the text generative process. Experimental results show that PNAT achieves top results on machine translation and paraphrase generation tasks, outperforming several strong baselines.

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: arXiv preprint arXiv:1409.0473,

authors:
Kyunghyun Cho
Bart van Merrienboer
Caglar Gulcehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using rnn encoder–decoder for statistical machine translation

venue: In EMNLP,

authors:
Jonas Gehring
Michael Auli
David Grangier
Denis Yarats
Yann N Dauphin

title: Convolutional sequence to sequence learning

authors:
Alex Graves
Abdel-rahman Mohamed
Geoffrey Hinton

title: Speech recognition with deep recurrent neural networks

venue: IEEE international conference on acoustics, speech and signal processing,

authors:
Jiatao Gu
James Bradbury
Caiming Xiong
Victor O.K. Li
Richard Socher

title: Non-autoregressive neural machine translation

venue: In ICLR,

authors:
Junliang Guo
Xu Tan
Di He
Tao Qin
Linli Xu
Tie-Yan Liu

title: Non-autoregressive neural machine translation with enhanced decoder input

venue: In AAAI,

authors:
Ankush Gupta
Arvind Agarwal
Prawaan Singh
Piyush Rai

title: A deep generative framework for paraphrase generation

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Lukasz Kaiser
Samy Bengio
Aurko Roy
Ashish Vaswani
Niki Parmar
Jakob Uszkoreit
Noam Shazeer

title: Fast decoding in sequence models using discrete latent variables

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Philipp Koehn
Hieu Hoang
Alexandra Birch
Chris Callison-Burch
Marcello Federico
Nicola Bertoldi
Brooke Cowan
Wade Shen
Christine Moran
Richard Zens
Chris Dyer
Ondřej Bojar
Alexandra Constantin
Evan Herbst

title: Moses: Open source toolkit for statistical machine translation

venue: In ACL,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: In NIPS, pp

authors:
Jason Lee
Elman Mansimov
Kyunghyun Cho

title: Deterministic non-autoregressive neural sequence modeling by iterative refinement

authors:
Zhuohan Li
Di He
Fei Tian
Tao Qin
Liwei Wang
Tie-Yan Liu

title: Hint-based training for non-autoregressive translation

venue: In NeuralIPS (to appear),

authors:
Tianyu Liu
Kexiang Wang
Lei Sha
Baobao Chang
Zhifang Sui

title: Table-to-text generation by structure-aware seq2seq learning

authors:
Xuezhe Ma
Chunting Zhou
Xian Li
Graham Neubig
Eduard Hovy

title: FlowSeq: Nonautoregressive conditional sequence generation with generative flow

venue: In EMNLP-IJCNLP,

authors:
Ning Miao
Hao Zhou
Lili Mou
Rui Yan
Lei Li

title: CGMH: Constrained sentence generation by Metropolis-Hastings sampling

authors:
Kishore Papineni
Salim Roukos
Todd Ward
Wei-Jing Zhu

title: BLEU: A method for automatic evaluation of machine translation

venue: In ACL, pp

authors:
Aurko Roy
Ashish Vaswani
Niki Parmar
Arvind Neelakantan

title: Towards a better understanding of vector quantized autoencoders

authors:
Rico Sennrich
Barry Haddow
Alexandra Birch

title: Neural machine translation of rare words with subword units

authors:
Chenze Shao
Yang Feng
Jinchao Zhang
Fandong Meng
Xilin Chen
Jie Zhou

title: Retrieving sequential information for non-autoregressive neural machine translation

authors:
Peter Shaw
Jakob Uszkoreit
Ashish Vaswani

title: Self-attention with relative position representations

venue: In NAACL-HLT,

authors:
Xiaoyu Shen
Hui Su
Yanran Li
Wenjie Li
Shuzi Niu
Yang Zhao
Akiko Aizawa
Guoping Long

title: A conditional variational framework for dialog generation

venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics

authors:
Yikang Shen
Zhouhan Lin
Athul Paul Jacob
Alessandro Sordoni
Aaron Courville
Yoshua Bengio

title: Straight to the tree: Constituency parsing with neural syntactic distance

authors:
Martin Sundermeyer
Ralf Schlüter
Hermann Ney

title: Lstm neural networks for language modeling

venue: In Thirteenth annual conference of the international speech communication association,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Yiren Wang
Fei Tian
Di He
Tao Qin
ChengXiang Zhai
Tie-Yan Liu

title: Non-autoregressive machine translation with auxiliary regularization

authors:
Bingzhen Wei
Mingxuan Wang
Hao Zhou
Junyang Lin
Xu Sun

title: Imitation learning for non-autoregressive neural machine translation

heading: 1 INTRODUCTION

text:
Transformer (Vaswani et al., 2017) has been widely used in many text generation tasks, which is first proposed in neural machine translation, achieving great success for its promising performance. Nevertheless, the auto-regressive property of Transformer has been a bottleneck. Specifically, the decoder of Transformer generates words sequentially, and the latter words are conditioned on previous ones in a sentence. Such bottleneck prevents the decoder from higher efficiency in parallel computation, and imposes strong constrains in text generation, with which the generation order has to be left to right (or right to left) (Shaw et al., 2018; Vaswani et al., 2017).
Recently, many researches (Gu et al., 2018; Lee et al., 2018; Wang et al., 2019; Wei et al., 2019) are devoted to break the auto-regressive bottleneck by introducing non-autoregressive Transformer (NAT) for neural machine translation, where the decoder generates all words simultaneously instead of sequentially. Intuitively, NAT abandons feeding previous predicted words into decoder state at the next time step, but directly copy encoded representation at source side to the decoder inputs (Gu et al., 2018). However, without the auto-regressive constrain, the search space of the output sentence becomes larger (Wei et al., 2019), which brings the performance gap (Lee et al., 2018) between NAT and auto-regressive Transformer (AT). Related works propose to include some inductive priors or learning techniques to boost the performance of NAT. But most of previous work hardly consider explicitly modeling the position of output words during text generation.
We argue that position prediction is an essential problem of NAT. Current NAT approaches do not explicitly model the position of output words, and may ignore the reordering issue in generating output sentences. Compared to machine translation, the reorder problem is much more severe in tasks such as table-to-text (Liu et al., 2018) and dialog generations (Shen et al., 2017). Additionally, it is straightforward to explicitly model word positions in output sentences, as position embeddings are used in Transformer, which is natively non-autoregressive, to include the order information. Intuitively, if output positions are explicitly modeled, the predicted position combined with Transformer to realize non-autoregressive generation would become more natural.
In this paper, we propose non-autoregressive transformer by position learning (PNAT). PNAT is simple yet effective, which explicitly models positions of output words as latent variables in the text generation. Specifically, we introduce a heuristic search process to guide the position learning, and max sampling is adopted to inference the latent model. The proposed PNAT is motivated by learning syntax position (also called syntax distance). Shen et al. (2018) show that syntax position of words in a sentence could be predicted by neural networks in a non-autoregressive fashion, which even obtains top parsing accuracy among strong parser baselines. Given the observations above, we try to directly predict the positions of output words to build a NAT model for text generation.
Our proposed PNAT takes following advantages:
• We propose PNAT, which first includes positions of output words as latent variables for text generation. Experiments show that PNAT achieves very top results in non-autoregressive NMT, outperforming many strong baselines. PNAT also obtains better results than AT in paraphrase generation task. • Further analysis shows that PNAT has great potentials. With the increase of position
prediction accuracy, performances of PNAT could increase significantly. The observations may shed light on the future direction of NAT. • Thanks to the explicitly modeling of position, we could control the generation by facilitating
the position latent variable, which may enable interesting applications such as controlling one special word left to another one. We leave this as future work.

heading: 2 BACKGROUND

heading: 2.1 AUTOREGRESSIVE DECODING

text:
A target sequence Y =y1:M is decomposed into a series of conditional probabilities autoregressively, each of which is parameterized using neural networks. This approach has become a de facto standard in language modeling(Sundermeyer et al., 2012), and has been also applied to conditional sequence modeling p(Y |X) by introducing an additional conditional variable X=x1:N :
p(Y |X) = M∏ t=1 p(yt|y<t, X; θ) (1)
With different choices of neural network architectures such as recurrent neural networks (RNNs) (Bahdanau et al., 2014; Cho et al., 2014), convolutional neural networks (CNNs) (Krizhevsky et al., 2012; Gehring et al., 2017), as well as self-attention based transformer (Vaswani et al., 2017), the autoregressive decoding has achieved great success in tasks such as machine translation (Bahdanau et al., 2014), paraphrase generation (Gupta et al., 2018), speech recognition (Graves et al., 2013), etc.

heading: 2.2 NON-AUTOREGRESSIVE DECODING

text:
Autoregressive model suffers from the issue of slow decoding in inference, because tokens are generated sequentially and each of them depends on previous ones. As a solution to this issue, Gu et al. (2018) proposed Non-Autoregressive Transformer (denoted as NAT) for machine translation, breaking the dependency among the target tokens through time by decoding all the tokens simultaneously. Put simply, NAT (Gu et al., 2018) factorizes the conditional distribution over a target sequence into a series of conditionally independent distributions with respect to time:
p(Y |X) = pL(M |X : θ) · M∏ t=1 p(yt|X) (2)
which allows trivially finding the most likely target sequence by arg maxY p(Y |X) for each timestep t, effectively bypassing computational overhead and sub-optimality in decoding from an autoregressive model.
Although non-autoregressive models achieves 15× speedup in machine translation compared with autoregressive models, it comes at the expense of potential performance degradation (Gu et al., 2018). The degradation results from the removal of conditional dependencies within the decoding sentence(yt depend on y<t). Without such dependencies, the decoder is hard to leverage the inherent sentence structure in prediction.

heading: 2.3 LATENT VARIABLES FOR NON-AUTOREGRESSIVE DECODING

text:
A non-autoregressive model could be incorporated with conditional dependency as latent variable to alleviate the degradation resulted from the absence of dependency:
P (Y |X) = ∫ z P (z|X) M∏ t=1 P (yt|z, X)dz (3)
For example, NAT-FT (Gu et al., 2018) models the inherent sentence structure with a latent fertility variable, which represents how many target tokens that a source token would translate to. Lee et al. (2018) introduces L intermediate predictions Y 1:L as random variables , and to refine the predictions from Y 1 to Y L in a iterative manner.

heading: 3 PNAT: POSITION-BASED NON-AUTOREGRESSIVE TRANSFORMER

text: We propose position-based non-autoregressive transformer (PNAT), an extension to transformer incorporated with non auto-regressive decoding and position learning.

heading: 3.1 MODELING POSITION WITH LATENT VARIABLES

text:
Languages are usually inconsistent with each other in word order. Thus reordering is usually required when translating a sentence from a language to another. In NAT family, words representations or encoder states at source side are copied to the target side to feed into decoder as its input. Previously, Gu et al. (2018) utilizes positional attention which incorporates positional encoding into decoder attention to perform local reordering. But such implicitly reordering mechanism by position attention may cause a repeated generation problem, because position learning module is not optimized directly, and is likely to be misguided by target supervision.
To tackle with this problem, we propose to explicitly model the position as a latent variable. We rewrite the target sequence Y with its corresponding position latent variable z = z1:M as a set Yz = yz1:zM . The conditional probability P (Y |X) is factorized with respect to the position latent variable:
P (Y |X) = ∑
z∈π(M)
P (z|X) · P (Y |z, X) (4)
where π(M) is a set consisting of permutations with M elements. At decoding time, the factorization allows us to decode sentences in parallel by pre-predicting the corresponding position variables z.
3.2 MODEL ARCHITECTURE
Decoder Inputs
Length Predictor
Soft-copy
Multi-Head Attention
Add & Norm
x M
Positions
Multi-Head Attention
Add & Norm
Input Embedding
Figure 1: The Transformer - model architecture.
Decoder: The decoder is also composed of a stack of N = 6 identical layers. In addition to the two sub-layers in each encoder layer, the decoder inserts a third sub-layer, which performs multi-head attention over the output of the encoder stack. Similar to the encoder, we employ residual connections around each of the sub-layers, followed by layer normalization. We also modify the self-attention sub-layer in the decoder stack to prevent positions from attending to subsequent positions. This masking, combined with fact that the output embeddings are offset by one position, ensures that the predictions for position i can depend only on the known outputs at positions less than i.
3.2 Attention
An attention function can be described as mapping a query and a set of key-value pairs to an output, where the query, keys, values, and output are all vectors. The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.
3.2.1 Scaled Dot-Product Attention
We call our particular attention "Scaled Dot-Product Attention" (Figure 2). The input consists of queries and keys of dimension dk, and values of dimension dv . We compute the dot products of the query with all keys, divide each by p dk, and apply a softmax function to obtain the weights on the values.
Inputs
N x
Feed Forward
Add & Norm
Figure 1: The Transformer - model architecture.
D c der: The decoder is also compo ed of a s ack of N = 6 identical layers. In addition to the two sub-layers in each encoder the decoder inserts a third sub-layer, which performs multi-head attention over the output f the encoder stack. Similar to the encoder, we employ residual connections around each f the sub-layers, foll wed b layer normalization. We also modify the self-attention sub-layer n the decod r stack to prevent positions from attending to subsequent positions. This masking, combined with ac that the utput embeddings are offset by one position, ensures that the predictions for position i c n depend only on the known outputs at positions less than i.
3.2 Attention
An attention function can be described s mapping a query and a set of key-value pairs to an output, where the query, keys, values, and output are all v ctors. The output is computed as a weighted sum of he values, where the w ight assigned to each value is computed by a compatibility function of the query with the corresponding key.
3.2.1 Scaled Dot-Product Attention
We call our particular attention "Scaled Dot-Product At ention" (Figure 2). The input consists of queri s and keys of dimension dk, and values of dimension dv . We compute the dot products of the query with all keys, divide each by p dk, and apply a oftmax function to obtain the weights on the values.
3
Feed Forward
Add & Norm
Multi-Head Attention
Add & Norm
Add & Norm
Self-Masked Multi-Head Attention
Linear
Softmax
Output Probabilities
x N
c
Bridge Position Predictor
Pointer Predictor
Figure 1: Illustr ti n of the pr posed model, where the black olid arrows represent diff re tiable connections and the dashed arrows are non-differentiable operations.
As shown in Figure 1, PNAT is composed of four modules: an encoder stack, a bridge block, a position predictor as well as a decoder stack. Before detailing each component of PNAT model, we overview the architecture for a brief understanding.
3
Like most sequence-to-sequence models, PNAT first encodes a source sequence X=x1:N into its contextual word representations E=e1:N with the encoder stack. With generated contextual word representation E at source side, the bridge block is leveraged to computed the target length M as well as the corresponding features D=d1:M , which is fed into the decoder as its input. It is worth noting that the decoder inputs D is computed without reordering. Thus the position predictor is introduced to deal with this issue by predicting a permutation z=z1:M over D. Finally, PNAT generates the target sequence from the decoder input D and its permutation z.
Encoder and Decoder Given a source sentence X with length N , PNAT encoder produces its contextual word representations E. The contextual word representations E are further used in computing target length M and decoder initial states D, and are also used as memory of attention at decoder side.
Generally, PNAT decoder can be considered as a transformer with a broader vision, because it leverages future word information that is blind to the autoregressive transformer. Intuitively, we use relative position encoding in self-attention(Shaw et al., 2018), rather than absolute one that is more likely to cause position errors. Following Shaw et al. (2018) with a clipping distance d (usually d ≥ 2) set for relative positions, we preserve d = 4 relations.
Bridge The bridge module predicts the target length M , and initializes the decoder inputs D from the source representations E. The target length M could be estimated from the source encoder representation:
M = N + arg maxφ(E) (5)
where φ(·) produces a categorical distribution ranged in [−B,B] (B = 20). It is notable that we use the predicted length at inference stage, although during training, we simply use the length of each reference target sequence. Then, we adopt the method proposed by Li et al. (2019) to compute D. Given the source representation E and the estimated target length M , we linearly combine the embeddings of the neighboring source tokens to generate D as follows:
dj = ∑ i wji · ei (6)
wji = softmax(−|j − i|/τ) (7) where wji is a normalized weight that reflects the contribution of ei to dj , and τ is a hyperparameter indicating the sharpness of the weight distribution.
Position Predictor For the proposed PNAT, we model position permutations with a position predictor. As shown in Figure 1, the position predictor takes the decoder inputs D and the source representation E to predict a permutation z. The position predictor has a sub-encoder which stacks multiple layers of encoder units to predict its predicted input R=r1:M .
With the predicted inputsR, we conduct an autoregressive position predictor, denoted as AR-Predictor. The AR-Predictor searches a permutation z with:
P (z|D,E) = M∏ t=1 p(zt|z<t, D,E; θ) (8)
where θ is the parameter of AR-Predictor, which includes a RNN-based model incorporated with a pointer network (Vinyals et al., 2015).
To purse the efficiency of decoding, we also explore a non-autoregressive version for the position predictor, denoted as NAR-Predictor, to model the position permutation probabilities with:
P (z|D,E) = M∏ t=1 p(zt|D,E; θ) (9)
To obtain the permutation z, AR-Predictor performs greedy search whereas NAR-Predictor performs direct arg max. We chose the AR-Predictor as our mainly position module in PNAT, and we also analyze the effectiveness of position modeling in Sec. 4.4.

heading: 3.3 TRAINING

text:
Training requires maximizing the marginalized likelihood in Eqn. 4. However, this is intractable since we need to enumerate all the M ! permutations of tokens. We therefore optimize this objective by Monte Carlo sampling method with a heuristic search algorithm.
Heuristic Search for Positions Intuitively, each target token should have a corresponding decoder input, and meanwhile each decoder input should be assigned to a target token. Based on this idea, we design a heuristic search algorithm to allocate positions. Given the decoder inputs and its target tokens, we first estimate the similarity between each pair of the decoder input di and the target token embedding yj , which is also the weights of the target word classifier:
simi,j = cosine (di, yj) (10)
Based on the cosine similarity matrix, HSP is designed to find a perfect matching between decoder inputs and target tokens:
HSP(z) = arg max z M∑ i=0 (simi,zi) (11)
Here we apply a greedy algorithm to select the pair with the highest similarity score iteratively until a permutation zref is generated. More details are provided in Appendix A.
The intuition behind is that, if the decoder input di is already the most similar one to a target word, it would be easier to keep and even reinforce this association in learning the model. We also analyze the effectiveness of the HSP in the Sec. 4.4.
Objective Function With the heuristically discovered positions as reference positions zref, the position predictor could be trained with a position loss:
Lp = − logP (zref|D,E) (12)
Grounding on the referenced positions, the generative process of target sequences is optimized by:
Lg = − M∑ t=1 logP (Y |zref;X) (13)
Finally, combining two loss functions mentioned above, a full-fledged loss is derived as
L = Lg + αLp (14)
The length predictor is a classifier that follows the previous settings. We also follow the previous practice (Gu et al., 2018; Wei et al., 2019) and perform an extra training process for the length predictor after the model trained and do not tune the parameter of the encoder.

heading: 3.4 INFERENCE

text:
We follow the common choice of approximating decoding algorithms (Gu et al., 2018; Lee et al., 2018) to reduce the search space of latent variable model.
Argmax Decoding Following Gu et al. (2018), one simple and effective method is to select the best sequence by choosing the highest-probability latent sequence z:
z∗ = arg max z P (z|D,E)
Y ∗ = arg max y P (Y |z∗, X)
where identifying Y ∗ only requires independently maximizing the local probability for each output position.
Length Parallel Decoding We also consider the common practice of noisy parallel decoding (Gu et al., 2018), which generates a number of decoding candidates in parallel and selects the best via re-scoring using a pre-trained autoregressive model. For PNAT, we first predict the target length as M̂ , then generate output sequence with argmax decoding for each target length candidate M ∈ [M̂ −∆M,M̂ + ∆M ] (M = 4 in our experiments), which was called length parallel decoding (LPD). Then we use the pre-trained autoregressive model to rank these sequences and identify the best overall output as the final output.

heading: 4 EXPERIMENTS

text: We test PNAT on several benchmark sequence generation tasks. We first describe the experimental setting and implementation details and then present the main results, followed by some deep studies.

heading: 4.1 EXPERIMENTAL SETTING

text:
To show the generation ability of PNAT, we conduct experiments on the popular machine translation and paraphrase generation tasks. These sequence generation task evaluation models from different perspectives. Translation tasks test the ability of semantic transforming across bilingual corpus. While paraphrase task focuses on substitution between the same languages while keeping the semantics.
Machine Translation We valid the effectiveness of PNAT on the most widely used benchmarks for machine translation — WMT14 EN-DE(4.5M pairs) and IWSLT16 DE-EN(196K pairs). The dataset is processed with Moses script (Koehn et al., 2007), and the words are segmented into subword units using byte-pair encoding (Sennrich et al., 2016, BPE). For both WMT datasets, the source and target languages share the same set of subword embeddings while for IWSLT we use separate embeddings.
Paraphrase Generation We conduct experiments following previous work (Miao et al., 2019) for paraphrase generation. We make use of the established Quora dataset 1 to evaluate on the paraphrase generation task. We consider the supervised paraphrase generation and split the Quora dataset in the standard setting. We sample 100k pairs sentence as training data, and holds out 3k, 30k for validation and testing, respectively.

heading: 4.2 IMPLEMENTATION DETAILS

text:
Module Setting For machine translation, we follow the settings from Gu et al. (2018). In the case of IWSLT task, we use a small setting (dmodel = 278, dhidden = 507, pdropout = 0.1, nlayer = 5 and nhead = 2) suggested by Gu et al. (2018) for Transformer and NAT models. For WMT task, we use the base setting of the Vaswani et al. (2017) (dmodel = 512, dhidden = 512, pdropout = 0.1, nlayer = 6).
For paraphrase generation, we follow the settings from Miao et al. (2019), and set the 300-dimensional GRU with 2 layer for Seq-to-Seq (GRU). We empirically select a Transformer and NAT models with hyperparameters (dmodel = 400, dhidden = 800, pdropout = 0.1, nlayer = 3 and nhead = 4).
Optimization We optimize the parameter with the Adam optimizer (Kingma & Ba, 2014). The hyperparameter α used in Eqn. 14 was be set to 1.0 for WMT, 0.3 for IWSLT and Quora. We also use inverse square root learning rate scheduling (Vaswani et al., 2017) for the WMT, and using linear annealing (from 3e− 4 to 1e− 5, suggested by Lee et al. (2018)) for the IWSLT and Quora. Each mini-batch consists of approximately 2K tokens for IWSLT and Quora, 32K tokens for WMT.
Knowledge Distillation Sequence-level knowledge distillation is applied to alleviate multimodality problem while training, using Transformer as a teacher (Hinton et al., 2015). Previous studies on non-autoregressive generation (Gu et al., 2018; Lee et al., 2018; Wei et al., 2019) have used translations produced by a pre-trained Transformer model as the training data, which significantly improves the performance. We follow this setting in translation tasks.
1https://www.kaggle.com/c/quora-question-pairs/data

heading: 4.3 MAIN RESULTS

text:
Machine Translation We compare the PNAT with strong NAT baselines, including the NAT with fertility (Gu et al., 2018, NAT-FT), the NAT with iterative refinement (Lee et al., 2018, IR-NAT), the NAT with regularization (Wang et al., 2019, NAT-REG), the NAT with enhanced decoder input (Guo et al., 2019, ENAT), the NAT with learning from auto-regressive model (Wei et al., 2019, imitateNAT), the NAT build on latent variables (Kaiser et al., 2018, LT), and the flow-based NAT model (Ma et al., 2019, Flowseq).
The results are shown in Table 1. We basically compare the proposed PNAT against the autoregressive counterpart both in terms of generation quality, which is measured with BLEU (Papineni et al., 2002) and inference speedup. For all our tasks, we obtain the performance of competitors by either directly using the performance figures reported in the previous works if they are available or producing them by using the open source implementation of baseline algorithms on our datasets.2 Clearly, PNAT achieves a comparable or better result to previous NAT models on both WMT and IWSLT tasks.
We list the result of the NAT models trained without using knowledge distillation in the second block of the Table 1. The PNAT achieves significant improvements (more than 13.0 BLEU points) over the naive baselines, which indicate that position learning greatly contributes to improve the model capability of NAT model. The PNAT also achieves a better result than the Flowseq around 1.0 BLEU, which demonstrates the effectiveness of PNAT in modeling dependencies between the target outputs.
As shown in the third block of the Table 1, without using reranking techniques, the PNAT outperforms all the competitors with a large margin, achieves a balance between performance and efficiency. In
2For the sake of fairness, we have chosen the base setting for all competitors.
particular, the previous state-of-the-art(WMT14 DE-EN) Flowseq achieves good performance with the slow speed(1.1×), while PNAT goes beyond Flowseq in both respects. Our best results are obtained with length parallel decoding which employ autoregressive model to rerank the multiple generation candidates of different target length. Specifically, on the large scale WMT14 DE-EN task, PNAT (+LPD) surpass the NAT-REG by 0.76 BLEU score. Without reranking, the gap has increased to 2.4 BLEU score (27.18 v.s. 24.77). The experiments shows the power of explicitly position modeling which reduces the gap between non-autoregressive and the autoregressive models.
Paraphrase Generation Given a sentence, paraphrase generation aims to synthesize another sentence that is different from the given one, but conveys the same meaning. Comparing with translation task, paraphrase generation prefers a more similar order between source and target sentence, which possibly learn a trivial position model. PNAT can potentially yield better results with the position model to infer the relatively ordered alignment relationship.
The results of the paraphrase generation are shown in Table 2. In consist with our intuition, PNAT achieves the best result on this task and even surpass Transformer around 3.5 BLEU. The NAT model is not powerful enough to capture the latent position relationship. The comparison between NAT-base and PNAT shows that explicit position modeling in PNAT plays a crucial role in generating sentences.

heading: 4.4 ANALYSIS

text:
Effectiveness of Heuristic Searched Position First, we analyze whether the position derived from the heuristic search is suitable for use as supervision to the position predictor. We evaluate the effectiveness of the searched position by training a PNAT as before and testing with the heuristic searched position instead of the predicted position. As shown in the second block of the Table 3, it is easier noticed that as PNAT w/ HSP achieves a significant improvement over the NAT-base and the Transformer, which demonstrates that the heuristic search for the position is effective.
Effectiveness and Efficiency of Position Modeling We are also analysis the accuracy of our position modeling and its influence on the quality of generation on the WMT14 DE-EN task. For evaluating the position accuracy, we adopt the heuristic searched position as the position reference (denoted as “HSP”), which is the training target of the position predictor. PNAT requires the position information at two places. The first is the mutual relative relationship between the states that will be used during decoding. And the second is to reorder the decoded output after decoding. We
then propose the corresponding metrics for evaluation, which is the relative position accuracy (with relation threshold r = 4) and the permutation accuracy.
As shown in Table 3, better position accuracy always yields better generation performance. The non-autoregressive position model is less effective than the current autoregressive position model, both in the accuracy of the permutation and the relative position. Even though the current PNAT with a simple AR-Predictor has surpassed the previous NAT model, the position accuracy is still less desirable (say, less than 30%) and has a great exploration space. We provide a few examples in Appendix B. There is also a trade-off between the effectiveness and efficiency, the choice of the non-autoregressive means the efficiency and the choice of autoregressive means the effectiveness.
Repeated Generation Analysis Previous NAT often suffers from the repeated generation problem due to the lack of sequential position information. NAT is less effective to distinguish adjacent decoder hidden states, which is copied from the adjacent source representation. To further study this problem, we proposed to evaluate the gains of simply remove the repeated tokens. As shown in Table 4, we perform the repeated generation analysis on the paraphrase generation tasks. Removing repeated tokens has little impact for PNAT model, with only 0.05 BLEU differences. However for the NAT-base model, the gap comes with almost 1 BLEU (0.89). The results clearly demonstrate that the explicitly position model essentially learns the sequential information for sequence generation.
Convergence Efficiency We also perform the training efficiency analysis in IWSLT16 DE-EN Translation task. The learning curves are shown in 2. The curve of the PNAT is on the top-left corner. Remarkably, PNAT has the best convergence speed compared with the NAT competitors and even a strong autoregressive model. The results are in line with our intuition, that the position learning brings meaningful information of position relationship and benefits the generation of the target sentence.

heading: 5 RELATED WORK

text:
Gu et al. (2018) first develops a non-autoregressive Transformer for neural machine translation (NMT) tasks, which produces the outputs in parallel and the inference speed is thus significantly boosted.
Due to the removal of the dependencies between the target outputs, it comes at the cost that the translation quality is largely sacrificed. A line of work has been proposed to mitigate such performance degradation. Some previous work is focused on enhancing the decoder inputs by replacing the target words as inputs, such as Guo et al. (2019) and Lee et al. (2018). Lee et al. (2018) proposed a method of iterative refinement based on the latent variable model and denoising autoencoder. Guo et al. (2019) enhances decoder input by introducing the phrase table in statistical machine translation and embedding transformation. Another part of previous work focuses on improving the supervision of NAT’s decoder states, including imitation learning from autoregressive models (Wei et al., 2019) or regularizing the decoder state with backward reconstruction error (Wang et al., 2019). There is also a line studies build upon latent variables, such as Kaiser et al. (2018) and Roy et al. (2018) utilize discrete latent variables for making decoding more parallelizable. Moreover, Shao et al. (2019) also proposed a method to retrieve the target sequential information for NAT models. Unlike previous work, we explicitly model the position, which has shown its importance to the autoregressive model and can well model the dependence between states. To the best of our knowledge, PNAT is the first work to explicitly model position information for non-autoregressive text generation.

heading: 6 CONCLUSION

text: We proposed PNAT, a non-autoregressive transformer by explicitly modeled positions, which bridge the performance gap between the non-autoregressive decoding and autoregressive decoding. Specifically, we model the position as latent variables, and training with heuristic searched positions with MC algorithms. As a result, PNAT leads to significant improvement and move more close to the performance gap between the NAT and AT on machine translation tasks. Besides, the experimental results of the paraphrase generation task show that the performance of the PNAT can exceed that of the autoregressive model, and at the same time, it also has a large improvement space. According to our further analysis on effectiveness of position modeling, in future work, we can still enhance the performance of the NAT model by strengthening position learning.

heading: A HEURISTIC SEARCH FOR POSITIONS

text:
Algorithm 1 Heuristic Search for Positions Input: The candidates set of decoder inputs: D = {d1, · · · , dM} and target embeddings: Y = {y1, · · · , yM}; Output: The position of the decoder inputs ẑ. 1: initial A = {}, D̂ = D, Ŷ = Y ; 2: compute the similarity matrix SimD,Y : the Sim[i, j] in the matrix is the the similarity between
the di and yj computing with simi,j = cosine (di, yj); 3: repeat 4: extract the similarity matrix SimD̂,Ŷ from the SimD,Y ; 5: select: (i, j) = arg max(i,j) SimD̂,Ŷ 6: update: A← A ∪ {(i, j)}, D̂ ← D̂ \ {di}, Ŷ ← Ŷ \ {yj}; 7: until D̂ = {} and Ŷ = {} 8: for each pair (i, j) in A do set ẑi = j 9: end for;
10: return ẑ
As shown in Algorithm 1, we perform a greedy algorithm to select the pair with the highest similarity score iteratively until the permutation ẑ is generated.
The complexity of this algorithm is o(M3) (M is the length of output sentence). Specifically, the complexity to select the maximum from the similarity matrix is o(M2) for each loop. We need M loops of greedy search to allocate positions for all decoder inputs.

heading: B CASE STUDY OF PREDICTED POSITIONS

text: We also provide a few examples in Table 5. For each source sentence, we first analyze the generation quality of the PNAT with a heuristic searched position. Besides, we also show the translation with the predicted position. We have the following observations: First, the output generated by the PNAT using the heuristic searched position always keeps the high consistency with the reference, shows the effectiveness of the heuristic searched position. Second, better position accuracy always yields better generation performance (Case 1,2 against Case 3). Third, as we can see in case 4, though the permutation accuracy is lower, it still generates a good result, the reason why we chose to use the relative self-attention instead of absolute self-attention.