summaries: This work introduces SNIP, a simple way to prune neural network weights before training according to a specific criterion. SNIP identifies prunable weights by the normalised gradient of the loss w.r.t. an implicit multiplicative factor “c” on the weights, denoted as the “sensitivity”. Essentially, this criterion takes two factors into account when determining the relevance of each weight; the scale of the gradient and the scale of the actual weight. The authors then rank the weights according to their sensitivity and remove the ones that are not in the top-k. They then proceed to train the surviving weights as normal on the task at hand. In experiments they show that this method can offer competitive results while being much simpler to implement than other methods in the literature.

summaries: The paper focuses on pruning neural networks. They propose to identify the nodes to be pruned even before training the whole network (conventionally, it is done as a separate step after the nn was trained and involves a number of iterations of retraining pruned nn). This initial step that identifies the connections to be pruned works off a mini-batch of data.

abstractText: Pruning large neural networks while maintaining their performance is often desirable due to the reduced space and time complexity. In existing methods, pruning is done within an iterative optimization procedure with either heuristically designed pruning schedules or additional hyperparameters, undermining their utility. In this work, we present a new approach that prunes a given network once at initialization prior to training. To achieve this, we introduce a saliency criterion based on connection sensitivity that identifies structurally important connections in the network for the given task. This eliminates the need for both pretraining and the complex pruning schedule while making it robust to architecture variations. After pruning, the sparse network is trained in the standard way. Our method obtains extremely sparse networks with virtually the same accuracy as the reference network on the MNIST, CIFAR-10, and Tiny-ImageNet classification tasks and is broadly applicable to various architectures including convolutional, residual and recurrent networks. Unlike existing methods, our approach enables us to demonstrate that the retained connections are indeed relevant to the given task.

authors:
Sanjeev Arora
Rong Ge
Behnam Neyshabur
Yi Zhang

title: Stronger generalization bounds for deep nets via a compression approach

title: Better subset regression using the nonnegative garrote

venue: Technometrics,

title: Carreira-Perpiñán and Yerlan Idelbayev. “Learning-compression” algorithms for neural net pruning

title: A back-propagation algorithm with optimal use of hidden units

authors:
Kyunghyun Cho
Bart Van Merriënboer
Caglar Gulcehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

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

authors:
Xin Dong
Shangyu Chen
Sinno Pan

title: Learning to prune deep neural networks via layer-wise optimal brain surgeon

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

authors:
Yunchao Gong
Liu Liu
Ming Yang
Lubomir Bourdev

title: Compressing deep convolutional networks using vector quantization

venue: arXiv preprint arXiv:1412.6115,

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient dnns

authors:
Suyog Gupta
Ankur Agrawal
Kailash Gopalakrishnan
Pritish Narayanan

title: Deep learning with limited numerical precision

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

authors:
Babak Hassibi
David G Stork
Gregory J Wolff

title: Optimal brain surgeon and general network pruning

venue: Neural Networks,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

title: Structural learning with forgetting

authors:
Max Jaderberg
Andrea Vedaldi
Andrew Zisserman

title: Speeding up convolutional neural networks with low rank expansions

title: A simple procedure for pruning back-propagation trained neural networks

authors:
Diederik P Kingma
Jimmy Ba

venue: ICLR,

authors:
Pang Wei Koh
Percy Liang

title: Understanding black-box predictions via influence functions

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

authors:
Quoc V Le
Navdeep Jaitly
Geoffrey E Hinton

title: A simple way to initialize recurrent networks of rectified linear units

authors:
Yann LeCun
John S Denker
Sara A Solla

title: Optimal brain damage

authors:
Yann LeCun
Léon Bottou
Genevieve B. Orr
Klaus-Robert Müller

title: Efficient backprop

venue: Neural Networks: Tricks of the Trade,

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

authors:
Christos Louizos
Max Welling
Diederik P Kingma

title: Learning sparse neural networks through l0 regularization

authors:
Dmitry Molchanov
Arsenii Ashukha
Dmitry Vetrov

title: Variational dropout sparsifies deep neural networks. ICML, 2017a

authors:
Pavlo Molchanov
Stephen Tyree
Tero Karras
Timo Aila
Jan Kautz

title: Pruning convolutional neural networks for resource efficient inference. ICLR, 2017b

authors:
Michael C Mozer
Paul Smolensky

title: Skeletonization: A technique for trimming the fat from a network via relevance assessment

authors:
Sharan Narang
Erich Elsen
Gregory Diamos
Shubho Sengupta

title: Exploring sparsity in recurrent neural networks

authors:
Steven J Nowlan
Geoffrey E Hinton

title: Simplifying neural networks by soft weight-sharing

venue: Neural Computation,

authors:
Ameya Prabhu
Girish Varma
Anoop Namboodiri

title: Deep expander networks: Efficient deep networks from graph theory

title: Pruning algorithms-a survey

authors:
Abigail See
Minh-Thang Luong
Christopher D Manning

title: Compression of neural machine translation models via pruning

authors:
Karen Simonyan
Andrew Zisserman

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

authors:
Karen Ullrich
Edward Meeds
Max Welling

title: Soft weight-sharing for neural network compression

authors:
Andreas S Weigend
David E Rumelhart
Bernardo A Huberman

title: Generalization by weightelimination with application to forecasting

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning structured sparsity in deep neural networks

authors:
Wojciech Zaremba
Ilya Sutskever
Oriol Vinyals

title: Recurrent neural network regularization

venue: arXiv preprint arXiv:1409.2329,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

heading: 1 INTRODUCTION

text:
Despite the success of deep neural networks in machine learning, they are often found to be highly overparametrized making them computationally expensive with excessive memory requirements. Pruning such large networks with minimal loss in performance is appealing for real-time applications, especially on resource-limited devices. In addition, compressed neural networks utilize the model capacity efficiently, and this interpretation can be used to derive better generalization bounds for neural networks (Arora et al. (2018)).
In network pruning, given a large reference neural network, the goal is to learn a much smaller subnetwork that mimics the performance of the reference network. The majority of existing methods in the literature attempt to find a subset of weights from the pretrained reference network either based on a saliency criterion (Mozer & Smolensky (1989); LeCun et al. (1990); Han et al. (2015)) or utilizing sparsity enforcing penalties (Chauvin (1989); Carreira-Perpiñán & Idelbayev (2018)). Unfortunately, since pruning is included as a part of an iterative optimization procedure, all these methods require many expensive prune – retrain cycles and heuristic design choices with additional hyperparameters, making them non-trivial to extend to new architectures and tasks.
In this work, we introduce a saliency criterion that identifies connections in the network that are important to the given task in a data-dependent way before training. Specifically, we discover important connections based on their influence on the loss function at a variance scaling initialization, which we call connection sensitivity. Given the desired sparsity level, redundant connections are pruned once prior to training (i.e., single-shot), and then the sparse pruned network is trained in the standard way. Our approach has several attractive properties: • Simplicity. Since the network is pruned once prior to training, there is no need for pretraining
and complex pruning schedules. Our method has no additional hyperparameters and once pruned, training of the sparse network is performed in the standard way. • Versatility. Since our saliency criterion chooses structurally important connections, it is robust to architecture variations. Therefore our method can be applied to various architectures including convolutional, residual and recurrent networks with no modifications.
i
• Interpretability. Our method determines important connections with a mini-batch of data at single-shot. By varying this mini-batch used for pruning, our method enables us to verify that the retained connections are indeed essential for the given task.
We evaluate our method on MNIST, CIFAR-10, and Tiny-ImageNet classification datasets with widely varying architectures. Despite being the simplest, our method obtains extremely sparse networks with virtually the same accuracy as the existing baselines across all tested architectures. Furthermore, we investigate the relevance of the retained connections as well as the effect of the network initialization and the dataset on the saliency score.

heading: 2 RELATED WORK

text:
Classical methods. Essentially, early works in network pruning can be categorized into two groups (Reed (1993)): 1) those that utilize sparsity enforcing penalties; and 2) methods that prune the network based on some saliency criterion. The methods from the former category (Chauvin (1989); Weigend et al. (1991); Ishikawa (1996)) augment the loss function with some sparsity enforcing penalty terms (e.g., L0 or L1 norm), so that back-propagation effectively penalizes the magnitude of the weights during training. Then weights below a certain threshold may be removed. On the other hand, classical saliency criteria include the sensitivity of the loss with respect to the neurons (Mozer & Smolensky (1989)) or the weights (Karnin (1990)) and Hessian of the loss with respect to the weights (LeCun et al. (1990); Hassibi et al. (1993)). Since these criteria are heavily dependent on the scale of the weights and are designed to be incorporated within the learning process, these methods are prohibitively slow requiring many iterations of pruning and learning steps. Our approach identifies redundant weights from an architectural point of view and prunes them once at the beginning before training.
Modern advances. In recent years, the increased space and time complexities as well as the risk of overfitting in deep neural networks prompted a surge of further investigation in network pruning. While Hessian based approaches employ the diagonal approximation due to its computational simplicity, impressive results (i.e., extreme sparsity without loss in accuracy) are achieved using magnitude of the weights as the criterion (Han et al. (2015)). This made them the de facto standard method for network pruning and led to various implementations (Guo et al. (2016); Carreira-Perpiñán & Idelbayev (2018)). The magnitude criterion is also extended to recurrent neural networks (Narang et al. (2017)), yet with heavily tuned hyperparameter setting. Unlike our approach, the main drawbacks of magnitude based approaches are the reliance on pretraining and the expensive prune – retrain cycles. Furthermore, since pruning and learning steps are intertwined, they often require highly heuristic design choices which make them non-trivial to be extended to new architectures and different tasks. Meanwhile, Bayesian methods are also applied to network pruning (Ullrich et al. (2017); Molchanov et al. (2017a)) where the former extends the soft weight sharing in Nowlan & Hinton (1992) to obtain a sparse and compressed network, and the latter uses variational inference to learn the dropout rate which can then be used to prune the network. Unlike the above methods, our approach is simple and easily adaptable to any given architecture or task without modifying the pruning procedure.
Network compression in general. Apart from weight pruning, there are approaches focused on structured simplification such as pruning filters (Li et al. (2017); Molchanov et al. (2017b)), structured sparsity with regularizers (Wen et al. (2016)), low-rank approximation (Jaderberg et al. (2014)), matrix and tensor factorization (Novikov et al. (2015)), and sparsification using expander graphs (Prabhu et al. (2018)) or Erdős-Rényi random graph (Mocanu et al. (2018)). In addition, there is a large body of work on compressing the representation of weights. A non-exhaustive list includes quantization (Gong et al. (2014)), reduced precision (Gupta et al. (2015)) and binary weights (Hubara et al. (2016)). In this work, we focus on weight pruning that is free from structural constraints and amenable to further compression schemes.

heading: 3 NEURAL NETWORK PRUNING

text:
The main hypothesis behind the neural network pruning literature is that neural networks are usually overparametrized, and comparable performance can be obtained by a much smaller network (Reed (1993)) while improving generalization (Arora et al. (2018)). To this end, the objective is to learn
ii
a sparse network while maintaining the accuracy of the standard reference network. Let us first formulate neural network pruning as an optimization problem.
Given a dataset D = {(xi,yi)}ni=1, and a desired sparsity level κ (i.e., the number of non-zero weights) neural network pruning can be written as the following constrained optimization problem:
min w L(w;D) = min w
1
n n∑ i=1 `(w; (xi,yi)) , (1)
s.t. w ∈ Rm, ‖w‖0 ≤ κ . Here, `(·) is the standard loss function (e.g., cross-entropy loss), w is the set of parameters of the neural network, m is the total number of parameters and ‖ · ‖0 is the standard L0 norm. The conventional approach to optimize the above problem is by adding sparsity enforcing penalty terms (Chauvin (1989); Weigend et al. (1991); Ishikawa (1996)). Recently, Carreira-Perpiñán & Idelbayev (2018) attempts to minimize the above constrained optimization problem using the stochastic version of projected gradient descent (where the projection is accomplished by pruning). However, these methods often turn out to be inferior to saliency based methods in terms of resulting sparsity and require heavily tuned hyperparameter settings to obtain comparable results.
On the other hand, saliency based methods treat the above problem as selectively removing redundant parameters (or connections) in the neural network. In order to do so, one has to come up with a good criterion to identify such redundant connections. Popular criteria include magnitude of the weights, i.e., weights below a certain threshold are redundant (Han et al. (2015); Guo et al. (2016)) and Hessian of the loss with respect to the weights, i.e., the higher the value of Hessian, the higher the importance of the parameters (LeCun et al. (1990); Hassibi et al. (1993)), defined as follows:
sj =  |wj | , for magnitude based w2jHjj
2 or w2j
2H−1jj for Hessian based .
(2)
Here, for connection j, sj is the saliency score, wj is the weight, and Hjj is the value of the Hessian matrix, where the Hessian H = ∂2L/∂w2 ∈ Rm×m. Considering Hessian based methods, the Hessian matrix is neither diagonal nor positive definite in general, approximate at best, and intractable to compute for large networks.
Despite being popular, both of these criteria depend on the scale of the weights and in turn require pretraining and are very sensitive to the architectural choices. For instance, different normalization layers affect the scale of the weights in a different way, and this would non-trivially affect the saliency score. Furthermore, pruning and the optimization steps are alternated many times throughout training, resulting in highly expensive prune – retrain cycles. Such an exorbitant requirement hinders the use of pruning methods in large-scale applications and raises questions about the credibility of the existing pruning criteria.
In this work, we design a criterion which directly measures the connection importance in a datadependent manner. This alleviates the dependency on the weights and enables us to prune the network once at the beginning, and then the training can be performed on the sparse pruned network. Therefore, our method eliminates the need for the expensive prune – retrain cycles, and in theory, it can be an order of magnitude faster than the standard neural network training as it can be implemented using software libraries that support sparse matrix computations.

heading: 4 SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY

text: Given a neural network and a dataset, our goal is to design a method that can selectively prune redundant connections for the given task in a data-dependent way even before training. To this end, we first introduce a criterion to identify important connections and then discuss its benefits.

heading: 4.1 CONNECTION SENSITIVITY: ARCHITECTURAL PERSPECTIVE

text:
Since we intend to measure the importance (or sensitivity) of each connection independently of its weight, we introduce auxiliary indicator variables c ∈ {0, 1}m representing the connectivity of
iii
parameters w.1 Now, given the sparsity level κ, Equation 1 can be correspondingly modified as:
min c,w L(c w;D) = min c,w
1
n n∑ i=1 `(c w; (xi,yi)) , (3)
s.t. w ∈ Rm , c ∈ {0, 1}m, ‖c‖0 ≤ κ ,
where denotes the Hadamard product. Compared to Equation 1, we have doubled the number of learnable parameters in the network and directly optimizing the above problem is even more difficult. However, the idea here is that since we have separated the weight of the connection (w) from whether the connection is present or not (c), we may be able to determine the importance of each connection by measuring its effect on the loss function.
For instance, the value of cj indicates whether the connection j is active (cj = 1) in the network or pruned (cj = 0). Therefore, to measure the effect of connection j on the loss, one can try to measure the difference in loss when cj = 1 and cj = 0, keeping everything else constant. Precisely, the effect of removing connection j can be measured by,
∆Lj(w;D) = L(1 w;D)− L((1− ej) w;D) , (4) where ej is the indicator vector of element j (i.e., zeros everywhere except at the index j where it is one) and 1 is the vector of dimension m.
Note that computing ∆Lj for each j ∈ {1 . . .m} is prohibitively expensive as it requires m + 1 (usually in the order of millions) forward passes over the dataset. In fact, since c is binary, L is not differentiable with respect to c, and it is easy to see that ∆Lj attempts to measure the influence of connection j on the loss function in this discrete setting. Therefore, by relaxing the binary constraint on the indicator variables c, ∆Lj can be approximated by the derivative of L with respect to cj , which we denote gj(w;D). Hence, the effect of connection j on the loss can be written as:
∆Lj(w;D) ≈ gj(w;D) = ∂L(c w;D)
∂cj
∣∣∣∣ c=1 = lim δ→0 L(c w;D)− L((c− δ ej) w;D) δ ∣∣∣∣ c=1 .
(5) In fact, ∂L/∂cj is an infinitesimal version of ∆Lj , that measures the rate of change of L with respect to an infinitesimal change in cj from 1 → 1 − δ. This can be computed efficiently in one forward-backward pass using automatic differentiation, for all j at once. Notice, this formulation can be viewed as perturbing the weight wj by a multiplicative factor δ and measuring the change in loss. This approximation is similar in spirit to Koh & Liang (2017) where they try to measure the influence of a datapoint to the loss function. Here we measure the influence of connections. Furthermore, ∂L/∂cj is not to be confused with the gradient with respect to the weights (∂L/∂wj), where the change in loss is measured with respect to an additive change in weight wj .
Notably, our interest is to discover important (or sensitive) connections in the architecture, so that we can prune unimportant ones in single-shot, disentangling the pruning process from the iterative optimization cycles. To this end, we take the magnitude of the derivatives gj as the saliency criterion. Note that if the magnitude of the derivative is high (regardless of the sign), it essentially means that the connection cj has a considerable effect on the loss (either positive or negative), and it has to be preserved to allow learning on wj . Based on this hypothesis, we define connection sensitivity as the normalized magnitude of the derivatives:
sj = |gj(w;D)|∑m k=1 |gk(w;D)| . (6)
Once the sensitivity is computed, only the top-κ connections are retained, where κ denotes the desired number of non-zero weights. Precisely, the indicator variables c are set as follows:
cj = 1[sj − s̃κ ≥ 0] , ∀ j ∈ {1 . . .m} , (7) where s̃κ is the κ-th largest element in the vector s and 1[·] is the indicator function. Here, for exactly κ connections to be retained, ties can be broken arbitrarily.
We would like to clarify that the above criterion (Equation 6) is different from the criteria used in early works by Mozer & Smolensky (1989) or Karnin (1990) which do not entirely capture the
1Multiplicative coefficients (similar to c) were also used for subset regression in Breiman (1995).
iv
Algorithm 1 SNIP: Single-shot Network Pruning based on Connection Sensitivity Require: Loss function L, training dataset D, sparsity level κ . Refer Equation 3 Ensure: ‖w∗‖0 ≤ κ
1: w← VarianceScalingInitialization . Refer Section 4.2 2: Db = {(xi,yi)}bi=1 ∼ D . Sample a mini-batch of training data 3: sj ←
|gj(w;Db)|∑m k=1|gk(w;Db)|
, ∀j ∈ {1 . . .m} . Connection sensitivity 4: s̃← SortDescending(s) 5: cj ← 1[sj − s̃κ ≥ 0] , ∀ j ∈ {1 . . .m} . Pruning: choose top-κ connections 6: w∗ ← arg minw∈Rm L(c w;D) . Regular training 7: w∗ ← c w∗
connection sensitivity. The fundamental idea behind them is to identify elements (e.g. weights or neurons) that least degrade the performance when removed. This means that their saliency criteria (i.e. −∂L/∂w or −∂L/∂α; α refers to the connectivity of neurons), in fact, depend on the loss value before pruning, which in turn, require the network to be pre-trained and iterative optimization cycles to ensure minimal loss in performance. They also suffer from the same drawbacks as the magnitude and Hessian based methods as discussed in Section 3. In contrast, our saliency criterion (Equation 6) is designed to measure the sensitivity as to how much influence elements have on the loss function regardless of whether it is positive or negative. This criterion alleviates the dependency on the value of the loss, eliminating the need for pre-training. These fundamental differences enable the network to be pruned at single-shot prior to training, which we discuss further in the next section.

heading: 4.2 SINGLE-SHOT PRUNING AT INITIALIZATION

text:
Note that the saliency measure defined in Equation 6 depends on the value of weights w used to evaluate the derivative as well as the dataset D and the loss function L. In this section, we discuss the effect of each of them and show that it can be used to prune the network in single-shot with initial weights w.
Firstly, in order to minimize the impact of weights on the derivatives ∂L/∂cj , we need to choose these weights carefully. For instance, if the weights are too large, the activations after the non-linear function (e.g., sigmoid) will be saturated, which would result in uninformative gradients. Therefore, the weights should be within a sensible range. In particular, there is a body of work on neural network initialization (Goodfellow et al. (2016)) that ensures the gradients to be in a reasonable range, and our saliency measure can be used to prune neural networks at any such initialization.
Furthermore, we are interested in making our saliency measure robust to architecture variations. Note that initializing neural networks is a random process, typically done using normal distribution. However, if the initial weights have a fixed variance, the signal passing through each layer no longer guarantees to have the same variance, as noted by LeCun et al. (1998). This would make the gradient and in turn our saliency measure, to be dependent on the architectural characteristics. Thus, we advocate the use of variance scaling methods (e.g., Glorot & Bengio (2010)) to initialize the weights, such that the variance remains the same throughout the network. By ensuring this, we empirically show that our saliency measure computed at initialization is robust to variations in the architecture.
Next, since the dataset and the loss function defines the task at hand, by relying on both of them, our saliency criterion in fact discovers the connections in the network that are important to the given task. However, the practitioner needs to make a choice on whether to use the whole training set, or a mini-batch or the validation set to compute the connection saliency. Moreover, in case there are memory limitations (e.g., large model or dataset), one can accumulate the saliency measure over multiple batches or take an exponential moving average. In our experiments, we show that using only one mini-batch of a reasonable number of training examples can lead to effective pruning.
Finally, in contrast to the previous approaches, our criterion for finding redundant connections is simple and directly based on the sensitivity of the connections. This allows us to effectively identify and prune redundant connections in a single step even before training. Then, training can be performed on the resulting pruned (sparse) network. We name our method SNIP for Single-shot Network Pruning, and the complete algorithm is given in Algorithm 1.
v

heading: 5 EXPERIMENTS

text:
We evaluate our method, SNIP, on MNIST, CIFAR-10 and Tiny-ImageNet classification tasks with a variety of network architectures. Our results show that SNIP yields extremely sparse models with minimal or no loss in accuracy across all tested architectures, while being much simpler than other state-of-the-art alternatives. We also provide clear evidence that our method prunes genuinely explainable connections rather than performing blind pruning.
Experiment setup For brevity, we define the sparsity level to be κ̄ = (m − κ)/m · 100 (%), where m is the total number of parameters and κ is the desired number of non-zero weights. For a given sparsity level κ̄, the sensitivity scores are computed using a batch of 100 and 128 examples for MNIST and CIFAR experiments, respectively. After pruning, the pruned network is trained in the standard way. Specifically, we train the models using SGD with momentum of 0.9, batch size of 100 for MNIST and 128 for CIFAR experiments and the weight decay rate of 0.0005, unless stated otherwise. The initial learning rate is set to 0.1 and decayed by 0.1 at every 25k or 30k iterations for MNIST and CIFAR, respectively. Our algorithm requires no other hyperparameters or complex learning/pruning schedules as in most pruning algorithms. We spare 10% of the training data as a validation set and used only 90% for training. For CIFAR experiments, we use the standard data augmentation (i.e., random horizontal flip and translation up to 4 pixels) for both the reference and sparse models. The code can be found here: https://github.com/namhoonlee/snip-public.

heading: 5.1 PRUNING LENETS WITH VARYING LEVELS OF SPARSITY

text:
We first test our approach on two standard networks for pruning, LeNet-300-100 and LeNet-5-Caffe. LeNet-300-100 consists of three fully-connected (fc) layers with 267k parameters and LeNet-5-Caffe consists of two convolutional (conv) layers and two fc layers with 431k parameters. We prune the LeNets for different sparsity levels κ̄ and report the performance in error on the MNIST image classification task. We run the experiment 20 times for each κ̄ by changing random seeds for dataset and network initialization. The results are reported in Figure 1.
The pruned sparse LeNet-300-100 achieves performances similar to the reference (κ̄ = 0), only with negligible loss at κ̄ = 90. For LeNet-5-Caffe, the performance degradation is nearly invisible. Note that our saliency measure does not require the network to be pre-trained and is computed at random initialization. Despite such simplicity, our approach prunes LeNets quickly (single-shot) and effectively (minimal accuracy loss) at varying sparsity levels.

heading: 5.2 COMPARISONS TO EXISTING APPROACHES

text:
What happens if we increase the target sparsity to an extreme level? For example, would a model with only 1% of the total parameters still be trainable and perform well? We test our approach for extreme sparsity levels (e.g., up to 99% sparsity on LeNet-5-Caffe) and compare with various pruning algorithms as follows: LWC (Han et al. (2015)), DNS (Guo et al. (2016)), LC (Carreira-Perpiñán &
vi
Idelbayev (2018)), SWS (Ullrich et al. (2017)), SVD (Molchanov et al. (2017a)), OBD (LeCun et al. (1990)), L-OBS (Dong et al. (2017)). The results are summarized in Table 1.
We achieve errors that are comparable to the reference model, degrading approximately 0.7% and 0.3% while pruning 98% and 99% of the parameters in LeNet-300-100 and LeNet-5-Caffe respectively. For slightly relaxed sparsities (i.e., 95% for LeNet-300-100 and 98% for LeNet-5-Caffe), the sparse models pruned by SNIP record better performances than the dense reference network. Considering 99% sparsity, our method efficiently finds 1% of the connections even before training, that are sufficient to learn as good as the reference network. Moreover, SNIP is competitive to other methods, yet it is unparalleled in terms of algorithm simplicity.
To be more specific, we enumerate some key points and non-trivial aspects of other algorithms and highlight the benefit of our approach. First of all, the aforementioned methods require networks to be fully trained (if not partly) before pruning. These approaches typically perform many pruning operations even if the network is well pretrained, and require additional hyperparameters (e.g., pruning frequency in Guo et al. (2016), annealing schedule in Carreira-Perpiñán & Idelbayev (2018)). Some methods augment the training objective to handle pruning together with training, increasing the complexity of the algorithm (e.g., augmented Lagrangian in Carreira-Perpiñán & Idelbayev (2018), variational inference in Molchanov et al. (2017a)). Furthermore, there are approaches designed to include architecture dependent constraints (e.g., layer-wise pruning schemes in Dong et al. (2017)).
Compared to the above approaches, ours seems to cost almost nothing; it requires no pretraining or additional hyperparameters, and is applied only once at initialization. This means that one can easily plug-in SNIP as a preprocessor before training neural networks. Since SNIP prunes the network at the beginning, we could potentially expedite the training phase by training only the survived parameters (e.g., reduced expected FLOPs in Louizos et al. (2018)). Notice that this is not possible for the aforementioned approaches as they obtain the maximum sparsity at the end of the process.

heading: 5.3 VARIOUS MODERN ARCHITECTURES

text:
In this section we show that our approach is generally applicable to more complex modern network architectures including deep convolutional, residual and recurrent ones. Specifically, our method is applied to the following models:
• AlexNet-s and AlexNet-b: Models similar to Krizhevsky et al. (2012) in terms of the number of layers and size of kernels. We set the size of fc layers to 512 (AlexNet-s) and to 1024 (AlexNet-b) to adapt for CIFAR-10 and use strides of 2 for all conv layers instead of using pooling layers. • VGG-C, VGG-D and VGG-like: Models similar to the original VGG models described in Simonyan & Zisserman (2015). VGG-like (Zagoruyko (2015)) is a popular variant adapted for CIFAR-10 which has one less fc layers. For all VGG models, we set the size of fc layers to 512, remove dropout layers to avoid any effect on sparsification and use batch normalization instead. • WRN-16-8, WRN-16-10 and WRN-22-8: Same models as in Zagoruyko & Komodakis (2016).
vii
• LSTM-s, LSTM-b, GRU-s, GRU-b: One layer RNN networks with either LSTM (Zaremba et al. (2014)) or GRU (Cho et al. (2014)) cells. We develop two unit sizes for each cell type, 128 and 256 for {·}-s and {·}-b, respectively. The model is adapted for the sequential MNIST classification task, similar to Le et al. (2015). Instead of processing pixel-by-pixel, however, we perform rowby-row processing (i.e., the RNN cell receives each row at a time).
The results are summarized in Table 2. Overall, our approach prunes a substantial amount of parameters in a variety of network models with minimal or no loss in accuracy (< 1%). Our pruning procedure does not need to be modified for specific architectural variations (e.g., recurrent connections), indicating that it is indeed versatile and scalable. Note that prior art that use a saliency criterion based on the weights (i.e., magnitude or Hessian based) would require considerable adjustments in their pruning schedules as per changes in the model.
We note of a few challenges in directly comparing against others: different network specifications, learning policies, datasets and tasks. Nonetheless, we provide a few comparison points that we found in the literature. On CIFAR-10, SVD prunes 97.9% of the connections in VGG-like with no loss in accuracy (ours: 97% sparsity) while SWS obtained 93.4% sparsity on WRN-16-4 but with a non-negligible loss in accuracy of 2%. There are a couple of works attempting to prune RNNs (e.g., GRU in Narang et al. (2017) and LSTM in See et al. (2016)). Even though these methods are specifically designed for RNNs, none of them are able to obtain extreme sparsity without substantial loss in accuracy reflecting the challenges of pruning RNNs. To the best of our knowledge, we are the first to demonstrate on convolutional, residual and recurrent networks for extreme sparsities without requiring additional hyperparameters or modifying the pruning procedure.

heading: 5.4 UNDERSTANDING WHICH CONNECTIONS ARE BEING PRUNED

text:
So far we have shown that our approach can prune a variety of deep neural network architectures for extreme sparsities without losing much on accuracy. However, it is not clear yet which connections are actually being pruned away or whether we are pruning the right (i.e., unimportant) ones. What if we could actually peep through our approach into this inspection?
Consider the first layer in LeNet-300-100 parameterized by wl=1 ∈ R784×300. This is a layer fully connected to the input where input images are of size 28 × 28 = 784. In order to understand which connections are retained, we can visualize the binary connectivity mask for this layer cl=1, by averaging across columns and then reshaping the vector into 2D matrix (i.e., cl=1 ∈ {0, 1}784×300 → R784 → R28×28). Recall that our method computes c using a minibatch of examples. In this experiment, we curate the mini-batch of examples of the same class and see which weights are retained for that mini-batch of data. We repeat this experiment for all classes
viii
(i.e., digits for MNIST and fashion items for Fashion-MNIST) with varying sparsity levels κ̄. The results are displayed in Figure 2 (see Appendix A for more results).
The results are significant; important connections seem to reconstruct either the complete image (MNIST) or silhouettes (Fashion-MNIST) of input class. When we use a batch of examples of the digit 0 (i.e., the first column of MNIST results), for example, the parameters connected to the foreground of the digit 0 survive from pruning while the majority of background is removed. Also, one can easily determine the identity of items from Fashion-MNIST results. This clearly indicates that our method indeed prunes the unimportant connections in performing the classification task, receiving signals only from the most discriminative part of the input. This stands in stark contrast to other pruning methods from which carrying out such inspection is not straightforward.

heading: 5.5 EFFECTS OF DATA AND WEIGHT INITIALIZATION

text:
Recall that our connection saliency measure depends on the network weights w as well as the given data D (Section 4.2). We study the effect of each of these in this section. Effect of data. Our connection saliency measure depends on a mini-batch of train examples Db (see Algorithm 1). To study the effect of data, we vary the batch size used to compute the saliency (|Db|) and check which connections are being pruned as well as how much performance change this results in on the corresponding sparse network. We test with LeNet-300-100 to visualize the remaining parameters, and set the sparsity level κ̄ = 90. Note that the batch size used for training remains the same as 100 for all cases. The results are displayed in Figure 3.
Effect of initialization. Our approach prunes a network at a stochastic initialization as discussed. We study the effect of the following initialization methods: 1) RN (random normal), 2) TN (truncated random normal), 3) VS-X (a variance scaling method using Glorot & Bengio (2010)), and 4) VS-H (a variance scaling method He et al. (2015)). We test on LeNets and RNNs on MNIST and run 20 sets of experiments by varying the seed for initialization. We set the sparsity level κ̄ = 90, and train with Adam optimizer (Kingma & Ba (2015)) with learning rate of 0.001 without weight decay. Note that for training VS-X initialization is used in all the cases. The results are reported in Figure 3.
For all models, VS-H achieves the best performance. The differences between initializers are marginal on LeNets, however, variance scaling methods indeed turns out to be essential for complex RNN models. This effect is significant especially for GRU where without variance scaling initialization, the pruned networks are unable to achieve good accuracies, even with different optimizers. Overall, initializing with a variance scaling method seems crucial to making our saliency measure reliable and model-agnostic.
ix
5.6 FITTING RANDOM LABELS
To further explore the use cases of SNIP, we run the experiment introduced in Zhang et al. (2017) and check whether the sparse network obtained by SNIP memorizes the dataset. Specifically, we train LeNet-5-Caffe for both the reference model and pruned model (with κ̄ = 99) on MNIST with either true or randomly shuffled labels. To compute the connection sensitivity, always true labels are used. The results are plotted in Figure 4.
Given true labels, both the reference (red) and pruned (blue) models quickly reach to almost zero training loss. However, the reference model provided with random labels (green) also reaches to very low training loss, even
with an explicit L2 regularizer (purple), indicating that neural networks have enough capacity to memorize completely random data. In contrast, the model pruned by SNIP (orange) fails to fit the random labels (high training error). The potential explanation is that the pruned network does not have sufficient capacity to fit the random labels, but it is able to classify MNIST with true labels, reinforcing the significance of our saliency criterion. It is possible that a similar experiment can be done with other pruning methods (Molchanov et al. (2017a)), however, being simple, SNIP enables such exploration much easier. We provide a further analysis on the effect of varying κ̄ in Appendix B.

heading: 6 DISCUSSION AND FUTURE WORK

text:
In this work, we have presented a new approach, SNIP, that is simple, versatile and interpretable; it prunes irrelevant connections for a given task at single-shot prior to training and is applicable to a variety of neural network models without modifications. While SNIP results in extremely sparse models, we find that our connection sensitivity measure itself is noteworthy in that it diagnoses important connections in the network from a purely untrained network. We believe that this opens up new possibilities beyond pruning in the topics of understanding of neural network architectures, multi-task transfer learning and structural regularization, to name a few. In addition to these potential directions, we intend to explore the generalization capabilities of sparse networks.
x

heading: ACKNOWLEDGEMENTS

text: This work was supported by the Korean Government Graduate Scholarship, the ERC grant ERC2012-AdG 321162-HELIOS, EPSRC grant Seebibyte EP/M013774/1 and EPSRC/MURI grant EP/N019474/1. We would also like to acknowledge the Royal Academy of Engineering and FiveAI.

heading: B FITTING RANDOM LABELS: VARYING SPARSITY LEVELS

heading: C TINY-IMAGENET

text:
2https://tiny-imagenet.herokuapp.com/
xiv

heading: D ARCHITECTURE DETAILS

text: xv

title: SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY


summaries: This paper addresses issues with the beam search decoding algorithm that is commonly applied to recurrent models during inference. In particular, the paper investigates why using larger beam widths, resulting in output sequences with higher log-probabilities, often leads to worse performance on evaluation metrics of interest such as BLEU. The paper argues that this effect is related to ‘search discrepancies’ (deviations from greedy choices early in decoding), and proposes a constrained decoding mechanism as a heuristic fix.

summaries: - The paper generalizes upon past observations by Ott et al. that NMT models might decode "copies" (of the source sentence) when using large beam widths, which results in degraded results. In particular, the present paper observes similar shortcomings in two additional tasks (summarization and captioning), where decoding with large beam widths results in "training set predictions." It's unclear if this observation is novel, but in any case the connection between these observations across NMT and summarization/captioning tasks is novel.

abstractText: Beam search is the most popular inference algorithm for decoding neural sequence models. Unlike greedy search, beam search allows for a non-greedy local decisions that can potentially lead to a sequence with a higher overall probability. However, previous work found that the performance of beam search tends to degrade with large beam widths. In this work, we perform an empirical study of the behavior of the beam search algorithm across three sequence synthesis tasks. We find that increasing the beam width leads to sequences that are disproportionately based on early and highly non-greedy decisions. These sequences typically include a very low probability token that is followed by a sequence of tokens with higher (conditional) probability leading to an overall higher probability sequence. However, as beam width increases, such sequences are more likely to have a lower evaluation score. Based on our empirical analysis we propose to constrain the beam search from taking highly non-greedy decisions early in the search. We evaluate two methods to constrain the search and show that constrained beam search effectively eliminates the problem of beam search degradation and in some cases even leads to higher evaluation scores. Our results generalize and improve upon previous observations on copies and training set predictions.

authors:
Peter Anderson
Basura Fernando
Mark Johnson
Stephen Gould

title: Guided open vocabulary image captioning with constrained beam search

venue: arXiv preprint arXiv:1612.00576,

title: Spice: Semantic propositional image caption evaluation

venue: In ECCV,

authors:
J Christopher Beck
Laurent Perron

title: Discrepancy-bounded depth first search

venue: In CPAIOR, pp

authors:
Sumit Chopra
Michael Auli
Alexander M Rush

title: Abstractive sentence summarization with attentive recurrent neural networks

venue: In NAACL-HLT,

authors:
Eldan Cohen
J Christopher Beck

title: Local minima, heavy tails, and search effort for GBFS

venue: In IJCAI,

authors:
Markus Freitag
Yaser Al-Onaizan

title: Beam search strategies for neural machine translation

venue: In WNMT,

authors:
David Furcy
Sven Koenig

title: Limited discrepancy beam search

venue: In IJCAI, pp

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

title: Convolutional sequence to sequence learning

venue: In ICML,

authors:
Ian P Gent
Toby Walsh

title: Easy problems are sometimes hard

venue: Artificial Intelligence,

authors:
Carla P Gomes
Cèsar Fernández
Bart Selman
Christian Bessière

title: Statistical regimes across constrainedness

venue: regions. Constraints,

authors:
Chris Hokamp
Qun Liu

title: Lexically constrained decoding for sequence generation using grid beam search

venue: In ACL,

authors:
Andrej Karpathy
Li Fei-Fei

title: Deep visual-semantic alignments for generating image descriptions

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Guillaume Klein
Yoon Kim
Yuntian Deng
Jean Senellart
Alexander Rush

title: Opennmt: Opensource toolkit for neural machine translation

venue: ACL (System Demonstrations),

authors:
Philipp Koehn
Rebecca Knowles

title: Six challenges for neural machine translation

title: Rouge: A package for automatic evaluation of summaries

venue: Text Summarization Branches Out,

authors:
Chin-Yew Lin
Franz Josef Och

title: Orange: a method for evaluating automatic evaluation metrics for machine translation

venue: In COLING,

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C Lawrence Zitnick

title: Microsoft coco: Common objects in context

authors:
Kenton Murray
David Chiang

title: Correcting length bias in neural machine translation

venue: arXiv preprint arXiv:1808.10006,

authors:
Myle Ott
Michael Auli
David Grangier
Marc’Aurelio Ranzato

title: Analyzing uncertainty in neural machine translation

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

title: Bleu: a method for automatic evaluation of machine translation

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

venue: In ICLR,

authors:
Alexander M Rush
Sumit Chopra
Jason Weston

title: A neural attention model for abstractive sentence summarization

venue: arXiv preprint arXiv:1509.00685,

authors:
Ramakrishna Vedantam
C Lawrence Zitnick
Devi Parikh

title: Cider: Consensus-based image description evaluation

authors:
Ashwin K Vijayakumar
Michael Cogswell
Ramprasaath R Selvaraju
Qing Sun
Stefan Lee
David J Crandall
Dhruv Batra

title: Diverse beam search for improved description of complex scenes

venue: In AAAI,

authors:
Oriol Vinyals
Quoc V. Le

title: A neural conversational model

venue: In ICML Deep Learning Workshop,

authors:
Oriol Vinyals
Alexander Toshev
Samy Bengio
Dumitru Erhan

title: Show and tell: Lessons learned from the 2015 mscoco image captioning challenge

venue: IEEE TPAMI,

title: Depth-bounded discrepancy search

authors:
Sam Wiseman
Alexander M Rush

title: Sequence-to-sequence learning as beam-search optimization

venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,

authors:
Yilin Yang
Liang Huang
Mingbo Ma

title: Breaking the beam search curse: A study of (re-) scoring methods and stopping criteria for neural machine translation

venue: arXiv preprint arXiv:1808.09582,

heading: 1 INTRODUCTION

text:
Neural sequence models are among the most popular tools for modeling sequential data and have been applied to a range of applications including machine translation (Gehring et al., 2017), summarization (Chopra et al., 2016), image captioning (Vinyals et al., 2017), and conversation modeling (Vinyals & Le, 2015). The most commonly used inference algorithm for decoding neural sequence models is beam search, a search algorithm that generates the sequence tokens one-by-one while keeping a fixed number of active candidates (beams) at each step.
Recently, several works reported the problem of performance degradation in beam search. In machine translation, Koehn & Knowles (2017) found that beam search “only improves translation for narrow beams and deteriorates when exposed to a larger search space”. They chose this problem as one of six central challenges in machine translation. Ott et al. (2018) proposed the existence of training pairs in which the target is a copy of the source as an explanation for the performance degradation. For larger beams, more predictions can be classified as “copies”1 and filtering these copies reduces the performance degradation.
In image captioning, Vinyals et al. (2017) observed performance degradation for wider beams and highlighted the use of a narrower beam search as one of the most significant improvements in their model. They hypothesized that the performance degradation is either due to overfitting or that the objective function used in training (likelihood) is not aligned with human judgement. Their analysis found that wider beams exhibited more predictions that repeat training captions and fewer novel ones. They claim that this observation supports the hypothesis that the model is overfitted and therefore see the use of smaller beam width as “another way to regularize”.
In this work, we analyze the performance of beam search across multiple tasks including machine translation, abstractive summarization, and image captioning. We present an explanatory model that
1“Copies” are predictions that share at least 50% of their unigrams with their source (Ott et al., 2018).
is based on the concept of search discrepancies (deviations from greedy choices) and perform an empirical study of the distribution of such discrepancies. We make the following contributions:
1. We show that increasing the beam width leads to solutions with more and larger early discrepancies. These sequences often have lower evaluation score, leading to the observed performance degradation. As we increase the beam width, the difference between discrepancies that are associated with improved vs. degraded solutions grows substantially.
2. We show that our explanatory model generalizes the previously observed copies and predictions that repeat training set targets and accounts for more of the degraded predictions.
3. Exploiting the above insights, we propose a fix that is based on constraining the discrepancies considered by the beam search. An empirical analysis shows it successfully eliminates the performance degradation.

heading: 2 PRELIMINARIES

heading: 2.1 NEURAL SEQUENCE MODELS

text:
Given a model parameterized by θ and an input x, the problem of sequence generation consists of finding a sequence ŷ such that ŷ = argmaxy∈Y Pθ(y | x), where Y is the set of all sequences. y is a sequence of tokens y = {y0, ...yT−1} from vocabulary V , where T is the length of the sequence y. The expression Pθ(y | x) can then be factored as Pθ(y | x) = ∏T−1 t=0 Pθ(yt | x; {y0, ..., yt−1}),
or for convenience using log-probability as ∑T−1 t=0 logPθ(yt | x; {y0, ..., yt−1}).
It is common to model logPθ(yt | x; {y0, ..., yt−1}) using a Recurrent Neural Network (RNN), where the sequence {y0, ..., yt−1} conditioned on is expressed by a fixed length hidden state ht. This hidden state is updated using a non-linear function f : ht+1 = f(ht, yt).
Exhaustive search to find the globally optimal sequence is not tractable. A greedy algorithm that selects the best candidate at each time step yt = argmaxy∈V logPθ(y | x; {y0, ..., yt−1}) makes a sequence of locally optimal decisions, but can lead to a globally sub-optimal sequence. Beam search, in contrast, extends the B most probable partial solutions at each step, where B is called beam width. Following Vijayakumar et al. (2018), we denote the set of B solutions held by the beam search at step t − 1 as Y[t−1]={y1,[t−1], ..., yB,[t−1]}. At each step, beam search selects the top scoring B candidates from the set of all possible one token extensions of its beams Yt={y[t] | y[t−1] ∈ Y[t−1] ∧ yt ∈ V}. Formally, the beam search candidates are updated as follows:
Y[t] = argmax y[1,t],...,y[B,t]∈Yt ∑ b∈[1..B] logPθ(yb,t | x)
s.t. yi 6= yj ∀i 6= j; i, j ∈ [1..B] (1)

heading: 2.2 SEARCH DISCREPANCIES IN NEURAL SEQUENCE GENERATION

text:
In combinatorial search, a search discrepancy is a decision made by the search algorithm that is not the most highly rated one according to the heuristic (Harvey & Ginsberg, 1995). In the context of search for neural sequence generation, we define a search discrepancy as extending a partial sequence with a token that is not the most probable one (i.e., different than the greedy algorithm). More formally, a sequence y is considered to have a search discrepancy at time step t if
logPθ(yt | x; {y0, ..., yt−1}) < max y∈V logPθ(y | x; {y0, ..., yt−1}). (2)
We denote the ratio between the most probable token and the chosen token as discrepancy gap. We measure the gap based on the difference in log-probability, i.e., the discrepancy gap at step t is
max y∈V
log Pθ(y | x; {y0, ..., yt−1})− log Pθ(yt | x; {y0, ..., yt−1}). (3)

heading: 3 EXPERIMENTAL SETUP

text:
We perform an extensive empirical evaluation over multiple tasks, models, datasets, toolkits, and evaluation metrics. Following is a description of the experimental setup for each task.
Machine Translation. We use the convolutional model by Gehring et al. (2017) implemented in the fairseq-py toolkit. We present results for two models, trained on WMT’14 En-Fr and En-De datasets and evaluated on newstest2014 En-Fr and En-De, respectively.
Summarization. We use the abstractive summarization model by Chopra et al. (2016) implemented in OpenNMT toolkit (Klein et al., 2017). The model is trained and evaluated using Rush et al.’s (2015) test split of the Gigaword corpus (Graff et al., 2003).
Image Captioning. We use the model by Vinyals et al. (2017), trained on the MSCOCO dataset (Lin et al., 2014). The test set includes 5000 images based on Karpathy & Fei-Fei’s (2015) splits.
In machine translation and summarization, we apply length normalization on the hypotheses loglikelihood, as it was shown to reduce the performance degradation by not prioritizing short sentences (Koehn & Knowles, 2017; Gehring et al., 2017). For image captioning, consistent with previous works, we do not use length normalization (we also found it reduces the overall performance).

heading: 3.1 EVALUATION METRICS

text:
While beam search finds the (approximately) most probable sequence, the quality of a sequence is evaluated based on human references using a task-specific evaluation metric. For machine translation and image captioning we use BLEU-n (Papineni et al., 2002), a geometric average of precision over 1- to n-grams multiplied by a brevity penalty for short sentences. As in recent literature, we present results for BLEU-4. Corpus-level BLEU is reported without smoothing, while for sentencelevel BLEU we use smoothed n-gram counts for n > 1 (Lin & Och, 2004). For image captioning, we also evaluated the performance using CIDEr (Vedantam et al., 2015) and SPICE (Anderson et al., 2016b) and report these metrics in Appendix E.
For summarization, we use ROUGE (Lin, 2004), the n-gram recall between candidate summary and a reference. We report the F-score of ROUGE-1, however similar trends were observed for the F-score of ROUGE-L (for longest common subsequence).

heading: 4 EMPIRICAL ANALYSIS OF SEARCH DISCREPANCIES IN BEAM SEARCH

text: In this section we present an empirical analysis of the search discrepancies. We analyze and compare the most likely hypotheses found by a beam search for the following beam widths: {1, 3, 5, 25, 100, 250}. Due to space, we present detailed results for one of the tasks and summarize the results for the others. The results for all tasks and metrics can be found in Appendix A.

heading: 4.1 BASELINE RESULTS

text: Table 1 presents the performance of beam search with different beam widths, based on the chosen evaluation metrics. The performance degradation for larger beam widths appears for all tested tasks based on their task-specific evaluation metric. These results are consistent with the existing reports of such performance degradation (Koehn & Knowles, 2017; Ott et al., 2018; Vinyals et al., 2017).

heading: 4.2 THE DISTRIBUTION OF SEARCH DISCREPANCIES

text:
In this section, we analyze the distribution and size of search discrepancies vs. their position (index) in sequence. Figure 1 shows the number of discrepancies per position for the most likely hypotheses generated by a beam search on the WMT’14 En-De test set for different beam widths (all graphs
are based on the same number of solutions, however the total number of discrepancies in the generated solutions is not necessarily the same for different beam widths). In general, the majority of discrepancies happen in early positions. More interestingly, for larger beams, the number of early discrepancies grows significantly while the number of later discrepancies stays approximately the same. Larger beams seem to allow the search to find solutions with higher overall probability by exploring less probable early tokens, however they do not seem to lead to more probable sequences that share a prefix with solutions found for a smaller beam width. Similar results for the other tasks are reported in Appendix A. For image captioning (MSCOCO), we find the majority of early search discrepancies appear on the second token due to the first token being “a” with high probability in almost all sentences (in greedy search, for example, 99% of the generated captions start with “a”).
Next, we analyze the discrepancy gap vs. sequence position. Figure 2 presents the mean gap per position for WMT’14 En-De for different beam widths. Again, we can see that the changes are mainly in the early positions: as we increase the beam width, the search tends to find solutions with larger early discrepancy gap, i.e., the early tokens are relatively less likely. The discrepancy gap of the other tokens remains similar. Similar results for the other tasks are reported in Appendix A.
The increase in count and size of early discrepancies for larger beams means that the search manages to find solutions with higher overall probability when starting from a large discrepancy. However, these solution are not necessarily better according to the evaluation metric. The observed performance degradation suggests that the more probable solutions found by larger beams are, in fact, worse. Identifying discrepancies that are likely to lead to a worse solution is therefore a key task in addressing the performance degradation. In the next section, we analyze the differences between discrepancies in solutions with higher evaluation vs. solutions with lower evaluation.

heading: 4.3 IMPROVED VS. DEGRADED SOLUTIONS

text:
We now compare the solutions generated by a greedy search with the solutions generated by beam search with different widths. We then analyze the discrepancies in solutions that were improved by increasing the beam width (with respect to the evaluation metric) vs. solutions that were degraded.
Figure 3 shows the number of discrepancies per position for WMT’14 En-De, comparing solutions that were improved vs. solutions that were degraded. For B=5 there are 386 solutions in which the first token is not based on a greedy decision. Of those, 200 have a better evaluation than the greedy solution and 169 have a worse evaluation. However, as we increase the beam width, we see that the increase in early discrepancies observed in Figure 1 is associated almost entirely with degraded
solutions. This result explains the observed performance degradation for larger beam widths. Similar results for the other tasks are reported in Appendix A.
Next, we compare the discrepancy gaps in degraded vs. improved solutions. Figure 4 presents the mean discrepancy gap per position for the WMT’14 En-De dataset, for both the improved and the degraded solutions. Interestingly, we find that the additional early discrepancies that are associated with degraded solutions tend to have a much higher discrepancy gap compared to the ones associated with improved solutions. Similar results for the other tasks are reported in Appendix A.

heading: 4.4 SEARCH DISCREPANCIES AND THE MOST LIKELY HYPOTHESIS

text:
In order for a sequence with early large discrepancy to be selected by a beam search as (approximately) the most likely hypothesis, it has to be followed by tokens with higher (conditional) probability. Figure 5 shows the average (conditional) token probability for WMT’14 En-De (we use log-scale on the x axis to highlight the early positions). For larger beam widths, the average probability of early tokens decreases (due to larger discrepancy gaps) while the average probability of later tokens increases explaining the overall higher probability.2 Figure 5 also shows the same graph for the improved vs. degraded solutions (compared to greedy search). For improved solutions, we do not see significant change as we increase the beam width. For degraded solutions, however, as we increase the beam width we find more and more early discrepancies that lead to an overall higher probability but a worse evaluation metric value. For all tasks, we found the differences for the degraded solutions to be larger than the improved solutions (see Appendix A).
Ott et al. (2018) observed the same pattern for copies, i.e., they have low first token probability and higher probabilities for subsequent tokens. Our analysis accounts for this behavior and suggests that copies are one instance of a more general pattern that leads to degraded sequences. In the next section, we show that our analysis generalizes copies, as well as training set predictions, and even accounts for additional degraded sequences.

heading: 4.5 GENERALIZING COPIES AND TRAINING SET PREDICTIONS

text:
Table 2 shows the number of copies in machine translation and training set predictions in summarization and image captioning. For larger beams, the number of copies and training set predictions grows. Table 2 also reports the mean discrepancy gap of the first token (second token for MSCOCO, see Section 4.2). As our analysis predicts, the early gap of these predictions also grows significantly.
2When length normalization is not used, we should compare the product of token probabilities rather than the average token probabilities. See Appendix A.3 for results on the unnormalized image captioning task.
Note that copies and training set predictions only partially account for the beam performance degradation. In WMT’14 En-De machine translation withB = 25, we find that copies account for≈ 40% of degraded solutions with first token gap. In Gigaword summarization with similar beam width, we find that training set examples account for ≈ 68% of degraded solutions with first token gap. Furthermore, in MSCOCO, since many of the solutions in the greedy search, as well as many of the improved sequences, are training set captions, eliminating them all together is not desired. Instead, we are interested in avoiding the training set captions in the larger beam widths that led to the performance degradation. These, as Table 2 shows, have larger difference in the discrepancy gap.

heading: 4.6 AN ILLUSTRATIVE EXAMPLE

text:
Consider the following example of training set predictions in Gigaword summarization. As we increase the beam width, we find more predictions with the structure: “〈weekday〉’s sports scoreboard” (Table 3).3 As expected, these predictions have a large early discrepancy, followed by highly (conditionally) probable tokens. For B = 100, the average first token discrepancy gap for these summaries is ≈ 3.63 compared to ≈ 0.39 in the full test set. As none of the test references includes “sports scoreboard”, these summaries have low evaluation score.
As a potential explanation for this phenomenon, we find that all texts that were summarized as “〈weekday〉’s sports scoreboard” included the corresponding weekday. In the training set, we found
3Without length normalization, the numbers are higher as this sequence is shorter than most summaries.
that in 2962 of the 2971 texts that were summarized to “〈weekday〉’s sports scoreboard” included the corresponding weekday. This can lead to the weekday’s token suggested as a first token with a low, but sufficiently high, probability to get into the top B tokens. Followed by high probability tokens, it can, in some cases, have an overall probability that is higher than the alternatives.

heading: 5 DISCREPANCY-CONSTRAINED BEAM SEARCH

text:
Building on our empirical analysis, we propose to constrain the beam search to avoid considering highly unlikely discrepancies. To do so, we evaluate two methods of constraining the beam search:
1. Discrepancy gap: Given a thresholdM, we modify beam search to only consider candidates with a discrepancy gap smaller or equal toM. Formally, we modify Eq. 1 to include the constraint maxy∈V log Pθ(y | x; {y0, ..., yt−1})−log Pθ(yt | x; {y0, ..., yt−1}) ≤M.
2. Beam candidate rank: Given a thresholdN , we modify Yt to only include the topN one token extensions in each beam. Note that the beam search still retains the topB candidates, however it will not consider more than N candidates from the same beam.
Using the setup in Section 4.1, we compare these methods to the baseline. Although the analysis in Section 4 was done on the test set (to account for the performance degradation that was previously observed on the test set),M and N are tuned on a held-out validation set and no information from the test set was used to tune our methods.
As shown in Table 4, both methods significantly reduce, and in some cases completely eliminate, the performance degradation. In translation and summarization, we improve performance compared to baseline with the best test beam width. In general, the gap constraint seems to be perform better (most notably, for MSCOCO). The gap constraint allows for a finer-grained control over the accepted discrepancies, however the rank constraint is simpler and easier to tune.
We also compared the number of copies and training set predictions in the baseline vs. the two discrepancy-constrained variants of beam search. We find that the constrained methods reduce the growth in the number of copies and training set predictions that happen as we increase the beam width. The detailed comparison can be found in Appendix B.
Finally, we repeated our analysis above and find that both constrained beam search variations substantially reduce the discrepancy phenomena observed in Section 4. Complete results and graphs for both constrained methods on WMT’14 En-De are in Appendix C (other tasks exhibited similar results).

heading: 6 DISCUSSION

text:
Our results show that larger beam width leads to increasingly large early discrepancies. These very unlikely early tokens are later compensated by subsequent tokens with a much higher (conditional) probability compared to the subsequent tokens of the more probable early tokens. The large difference in the conditional probability of the subsequent tokens is at the heart of the observed performance degradation. Previous work has highlighted two potential biases that can account for this difference. Exposure bias (Ranzato et al., 2015) occurs since the model is only exposed to the training data and can be biased towards the training set distribution (our illustrative example demonstrates such bias due to a repetitive pattern in the training data). Label bias (Wiseman & Rush, 2016) occurs since token probabilities at each time step are locally normalized and therefore the successors of incorrect histories receive the same probability mass as the successors of a correct history.
These above biases help explain the observed behavior with large beam width: a biased (conditional) probability that concentrates high probability mass on one token and is locally normalized to sum to one compensates for earlier low probability tokens. The negative effects of these biases have been discussed before, however the described connection to the performance degradation in beam search and the explanatory framework to allow such analysis is, to our best knowledge, novel.
The use of the search discrepancy concept from heuristic and combinatorial search views the probabilities predicted by the neural network as a heuristic to guide the search. Early mistakes in such search have been shown to have a large negative effect on performance (Gent & Walsh, 1994). Substantial work has analyzed and proposed techniques to mitigate the phenomenon (Gomes et al., 2005; Cohen & Beck, 2018), including limited discrepancy search (Harvey & Ginsberg, 1995). Further investigation of the connection between such work and neural decoding may lead to further insight.

heading: 7 RELATED WORK

text:
Search discrepancies have been the base of many search techniques in combinatorial search and optimization (e.g., Harvey & Ginsberg, 1995; Walsh, 1997; Beck & Perron, 2000). Furcy & Koenig (2005) proposed BULB, a complete variant of beam search that backtracks based on search discrepancies, as a memory-efficient alternative to best-first heuristic search for path-finding problems.
Several works have modified or constrained beam search for different purposes. Vijayakumar et al. (2018) changed the objective to allow diverse decoding. Hokamp & Liu (2017) proposed grid beam search to support lexical constraints. Anderson et al. (2016a) proposed a constrained beam search that forces inclusion of selected tokens in the output. Freitag & Al-Onaizan (2017) analyzed pruning techniques for beam search in machine translation. Their strategy of limiting “maximum candidates per node” is similar to the rank constraint in our work, however their analysis is focused on speeding up beam search rather than addressing the phenomenon of performance degradation.
A recent line of work in machine translation suggested the performance degradation is due to length bias (Yang et al., 2018; Murray & Chiang, 2018). For larger beams, an end-of-sentence token with a lower probability that leads to an overall more probable hypothesis is more likely to be considered by the beam search. However, we showed peformance degradation above even when using length normalization and in tasks where length bias does not appear (see Appendix D for more details).

heading: 8 CONCLUSION

text:
In this work, we perform an empirical analysis of the performance degradation in beam search across three neural sequence decoding tasks. We find that the performance degradation for large beam widths is due to the increasing number of early and large search discrepancies. Our analysis generalizes previous results including the existence of copy predictions in machine translation and the training set predictions in image captioning, and accounts for additional degraded sequences. Based on our analysis, we propose two constrained variants of beam search that avoid large discrepancy gaps and successfully eliminate the performance degradation in beam search.
This work provides a deeper understanding of beam search behavior and an analytical framework to study search discrepancies. We believe the analysis, the framework, and the proposed solutions can support the development of better training methods and decoding algorithms.

heading: A FULL EMPIRICAL ANALYSIS

text:
A.1 MACHINE TRANSLATION ON WMT’14 EN-FR
A.2 SUMMARIZATION ON GIGAWORD
A.3 IMAGE CAPTIONING ON MSCOCO

heading: B COPIES AND TRAINING SET PREDICTIONS IN DISCREPANCY-CONSTRAINED BEAM SEARCH

text:
Table 6 compares the number of copies in the baseline vs. the discrepancy-constrained methods for the machine translation tasks for each beam width. For the baseline, we can see that as we increase the beam width, the number of copies grows significantly. However, both discrepancy-constrained methods significantly reduce this growth.
Table 7 compares the number of training set predictions in the baseline vs. the discrepancyconstrained methods for the summarization and image captioning tasks for each beam width. For
the baseline, we can see that as we increase the beam width, the number of training set predictions grows significantly. However, as with copies, both discrepancy-constrained methods significantly reduce the growth in training set predictions.

heading: C RESULTS FOR CONSTRAINED BEAM SEARCH ON WMT’14 EN-DE

text:
C.1 RESULTS FOR DISCREPANCY GAP CONSTRAINED BEAM SEARCH (M = 1.5)
C.2 RESULTS FOR RANK CONSTRAINED BEAM SEARCH (N = 2)

heading: D ANALYSIS OF LENGTH BIAS

text:
Table 8 shows the mean length of generated sentences for different beam widths for the baseline, normalized to the best tested beam width. All values are very close 1.0, which suggest that the observed performance degradation is not due to length bias. We note that for machine translation and summarization this is due to the use of length normalization on the hypotheses log-likelihood, as suggested by Koehn & Knowles (2017) (without normalization, the performance degradation would have been worse).4 In image captioning, however, there is no observed length bias even when length normalization is not used.5
In Section 4.1, we showed substantial performance degradation as we increase the beam width. As the results in Table 8 demonstrate that there is no significant change in the length of generated sequences, the observed performance degradation cannot be attributed to length bias.
E IMAGE CAPTIONING: CIDER AND SPICE
Table 9 compares the baseline vs. the constrained beam search methods on the MSCOCO image caption task using the metrics CIDEr and SPICE. The results show similar trends to those observed for BLEU in Section 5. In particular, we see that the performance degradation for larger beams also occurs for CIDEr and SPICE in the baseline, and that our gap constraint method eliminates this degradation. Similar to our results for BLEU, we note that our rank constraint is not as effective as our gap constraint for the image captioning task.