summaries: This works applies neural module network to reading comprehension that requires symbolic reasoning. There are two main contributions: (1) the authors designed a set of differentiable neural modules for different operations (for example, arithmetics, sorting, and counting) that is required to perform reasoning over a paragraph of text. These modules can be compositionally combined to perform complex reasoning. And the parameters of each module (which can be viewed as executor of each operation) are learned jointly with the parser that generates thee program composed of those modules. (2) To overcome the challenge of weak supervision, the authors proposed to use auxiliary loss (information extraction loss, parser supervision, intermediate output supervision). The model is evaluated on a subset of DROP, and outperforms the state-of-the-art models. Ablation studies supported the importance of the auxiliary losses.

summaries: The paper offers a new deep learning approach to symbolic reasoning over text. They propose using Neural Module Networks to perform explicit reasoning steps that are nevertheless differentiable. The process is separated into a semantic parsing of the question, and a resolution using MNMs. Auxiliary tasks improve performance and enable using a BERT pretrained model as a seed. The proposed model's performance surpasses previous SOTA on several question types.

abstractText: Answering compositional questions that require multiple steps of reasoning against text is challenging, especially when they involve discrete, symbolic operations. Neural module networks (NMNs) learn to parse such questions as executable programs composed of learnable modules, performing well on synthetic visual QA domains. However, we find that it is challenging to learn these models for non-synthetic questions on open-domain text, where a model needs to deal with the diversity of natural language and perform a broader range of reasoning. We extend NMNs by: (a) introducing modules that reason over a paragraph of text, performing symbolic reasoning (such as arithmetic, sorting, counting) over numbers and dates in a probabilistic and differentiable manner; and (b) proposing an unsupervised auxiliary loss to help extract arguments associated with the events in text. Additionally, we show that a limited amount of heuristically-obtained question program and intermediate module output supervision provides sufficient inductive bias for accurate learning. Our proposed model significantly outperforms state-of-the-art models on a subset of the DROP dataset that poses a variety of reasoning challenges that are covered by our modules.

authors:
Daniel Andor
Luheng He
Kenton Lee
Emily Pitler

title: Giving BERT a Calculator: Finding Operations and Arguments with Reading Comprehension

authors:
Jacob Andreas
Marcus Rohrbach
Trevor Darrell
Dan Klein

title: Neural module networks

venue: In CVPR,

authors:
Elad Segal Avia Efrat
Mor Shoham

title: Tag-based multi-span extraction in reading comprehension. 2019

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In ICML,

authors:
Jonathan Berant
Andrew Chou
Roy Frostig
Percy Liang

title: Semantic parsing on Freebase from Question-Answer pairs

venue: In EMNLP,

authors:
James Clarke
Dan Goldwasser
Ming-Wei Chang
Dan Roth

title: Driving semantic parsing from the world’s response

venue: In CoNLL,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: In NAACL-HLT,

authors:
Dheeru Dua
Yizhong Wang
Pradeep Dasigi
Gabriel Stanovsky
Sameer Singh
Matt Gardner

title: DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs

authors:
Shi Feng
Eric Wallace
Alvin Grissom
Mohit Iyyer
Pedro Rodriguez
Jordan L. Boyd-Graber

title: Pathologies of neural models make interpretation difficult

authors:
Matt Gardner
Joel Grus
Mark Neumann
Oyvind Tafjord
Pradeep Dasigi
Nelson F. Liu
Matthew E. Peters
Michael Schmitz
Luke S. Zettlemoyer

title: Allennlp: A deep semantic natural language processing

venue: platform. ArXiv,

authors:
Nitish Gupta
Mike Lewis

title: Neural compositional denotational semantics for question answering

authors:
Luheng He
Mike Lewis
Luke S. Zettlemoyer

title: Question-answer driven semantic role labeling: Using natural language to annotate natural language

authors:
Minghao Hu
Yuxing Peng
Zhiheng Huang
Dongsheng Li

title: A multi-type multi-span network for reading comprehension that requires discrete reasoning

authors:
Ronghang Hu
Jacob Andreas
Marcus Rohrbach
Trevor Darrell
Kate Saenko

title: Learning to reason: End-to-end module networks for visual question answering

authors:
Robin Jia
Percy Liang

title: Adversarial examples for evaluating reading comprehension systems

authors:
Yichen Jiang
Mohit Bansal

title: Self-assembling modular networks for interpretable multi-hop reasoning

authors:
Justin Johnson
Bharath Hariharan
Laurens van der Maaten
Li Fei-Fei
C. Lawrence Zitnick
Ross B. Girshick

title: CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning

authors:
Jambay Kinley
Raymond Lin

title: Nabert+ : Improving numerical reasoning in reading comprehension. 2019

authors:
Jayant Krishnamurthy
Pradeep Dasigi
Matt Gardner

title: Neural semantic parsing with type constraints for semi-structured tables

authors:
Percy S. Liang
Michael I. Jordan
Dan Klein

title: Learning dependency-based compositional semantics

venue: Computational Linguistics,

authors:
Jiayuan Mao
Chuang Gan
Pushmeet Kohli
Joshua B. Tenenbaum
Jiajun Wu

title: The neurosymbolic concept learner: Interpreting scenes words and sentences from natural supervision

venue: In ICLR,

authors:
Arvind Neelakantan
Quoc V Le
Martin Abadi
Andrew McCallum
Dario Amodei

title: Learning a natural language interface with neural programmer

authors:
Panupong Pasupat
Percy Liang

title: Compositional semantic parsing on semi-structured tables

authors:
Siva Reddy
Mirella Lapata
Mark Steedman

title: Large-scale semantic parsing without questionanswer pairs

venue: TACL,

authors:
Alon Talmor
Jonathan Herzig
Nicholas Lourie
Jonathan Berant

title: Commonsenseqa: A question answering challenge targeting commonsense knowledge

authors:
Zhilin Yang
Peng Qi
Saizheng Zhang
Yoshua Bengio
William W. Cohen
Ruslan Salakhutdinov
Christopher D. Manning

title: Hotpotqa: A dataset for diverse, explainable multi-hop question answering

authors:
John M Zelle
Raymond J Mooney

title: Learning to parse database queries using inductive logic programming

venue: In Proceedings of the national conference on artificial intelligence,

authors:
Luke S Zettlemoyer
Michael Collins

title: Learning to map sentences to logical form: structured classification with probabilistic categorial grammars

venue: In UAI ’05,

authors:
Zhuosheng Zhang
Yuwei Wu
Junru Zhou
Sufeng Duan
Hai Zhao

title: Sg-net: Syntax-guided machine reading comprehension

venue: arXiv preprint arXiv:1908.05147,

heading: 1 INTRODUCTION

text:
Being formalism-free and close to an end-user task, QA is increasingly becoming a proxy for gauging a model’s natural language understanding capability (He et al., 2015; Talmor et al., 2018). Recent models have performed well on certain QA datasets, sometimes rivaling humans (Zhang et al., 2019), but it has become increasingly clear that they primarily exploit surface level lexical cues (Jia & Liang, 2017; Feng et al., 2018) and compositional QA still remains a challenge. Answering complex compositional questions against text is challenging since it requires a comprehensive understanding of both the question semantics and the text against which the question needs to be answered. Consider the question in Figure 1; a model needs to understand the compositional reasoning structure of the questions, perform accurate information extraction from the passage (eg. extract lengths, kickers, etc. for the field goals and touchdowns), and perform symbolic reasoning (eg. counting, sorting, etc.).
Semantic parsing techniques, which map natural language utterances to executable programs, have been used for compositional question understanding for a long time (Zelle & Mooney, 1996; Zettlemoyer & Collins, 2005; Liang et al., 2011), but have been limited to answering questions against structured and semi-structured knowledge sources. Neural module networks (NMNs; Andreas et al., 2016) extend semantic parsers by making the program executor a learned function composed of neural network modules. These modules are designed to perform basic reasoning tasks and can be composed to perform complex reasoning over unstructured knowledge.
NMNs perform well on synthetic visual question answering (VQA) domains such as CLEVR (Johnson et al., 2017) and it is appealing to apply them to answer questions over text due to their interpretable, modular, and inherently compositional nature. We find, however, that it is non-trivial to extend NMNs for answering non-synthetic questions against open-domain text, where a model needs to deal with
∗Work done while at Allen Institute for AI.
the ambiguity and variability of real-world text while performing a diverse range of reasoning. Jointly learning the parser and executor using only QA supervision is also extremely challenging (§2.2). Our contributions are two-fold: Firstly, we extend NMNs to answer compositional questions against a paragraph of text as context. We introduce neural modules to perform reasoning over text using distributed representations, and perform symbolic reasoning, such as arithmetic, sorting, comparisons, and counting (§3). The modules we define are probabilistic and differentiable, which lets us maintain uncertainty about intermediate decisions and train the entire model via end-to-end differentiability.
Secondly, we show that the challenges arising in learning from end-task QA supervision can be alleviated with an auxiliary loss over the intermediate latent decisions of the model. Specifically, we introduce an unsupervised objective that provides an inductive bias to perform accurate information extraction from the context (§4.1). Additionally, we show that providing heuristically-obtained supervision for question programs and outputs for intermediate modules in a program (§4.2) for a small subset of the training data (5–10%) is sufficient for accurate learning.
We experiment on 21,800 questions from the recently proposed DROP dataset (Dua et al., 2019) that are heuristically chosen based on their first n-gram such that they are covered by our designed modules. This is a significantly-sized subset that poses a wide variety of reasoning challenges and allows for controlled development and testing of models. We show that our model, which has interpretable intermediate outputs by design, significantly outperforms state-of-the-art black box models on this dataset. We conclude with a discussion of the challenges of pushing NMNs to the entire DROP dataset, where some questions require reasoning that is hard to design modules for.

heading: 2 NEURAL MODULE NETWORKS

text:
Consider the question “Who kicked the longest field goal in the second quarter?” in Figure 1. Multiple reasoning steps are needed to answer such a question: find all instances of “field goal” in the paragraph, select the ones “in the second quarter”, find their lengths, compute the “longest” of them, and then find “who kicked” it. We would like to develop machine reading models that are capable of understanding the context and the compositional semantics of such complex questions in order to provide the correct answer, ideally while also explaining the reasoning that led to that answer.
Neural module networks (NMN) capture this intuition naturally, which makes them a good fit to solve reasoning problems like these. A NMN would parse such a question into an executable program, such as relocate(find-max-num(filter(find()))), whose execution against the given paragraph yields the correct answer. These programs capture the abstract compositional reasoning structure required to answer the question correctly and are composed of learnable modules designed to solve sufficiently independent reasoning tasks. For example, the find module should ground the question span “field goal” to its various occurrences in the paragraph; the module find-max-num should output the span amongst its input that is associated with the largest length; and finally, the relocate module should find “who kicked” the field goal corresponding to its input span.

heading: 2.1 COMPONENTS OF A NMN FOR TEXT

text:
Modules. To perform natural language and symbolic reasoning over different types of information, such as text, numbers, and dates, we define a diverse set of differentiable modules to operate over these different data types. We describe these modules and the data types in §3. Contextual Token Representations. Our model represents the question q as Q ∈ Rn×d and the context paragraph p as P ∈ Rm×d using contextualized token embeddings. These are outputs of either the same bidirectional-GRU or a pre-trained BERT (Devlin et al., 2019) model. Here n and m are the number of tokens in the question and the paragraph, respectively. Appendix §A.1 contains details about how these contextual embeddings are produced.
Question Parser. We use an encoder-decoder model with attention to map the question into an executable program. Similar to N2NMN (Hu et al., 2017), at each timestep of decoding, the attention that the parser puts on the question is available as a side argument to the module produced at that timestep during execution. This lets the modules have access to question information without making hard decisions about which question words to put into the program.
In our model, the data types of the inputs and output of modules automatically induce a typeconstrained grammar which lends itself to top-down grammar-constrained decoding as performed by Krishnamurthy et al. (2017). This ensures that the decoder always produces well-typed programs. For example, if a module f1 inputs a number, and f2 outputs a date, then f1(f2) is invalid and would not be explored while decoding. For example, if a module f1 inputs a number, and f2 outputs a date, then f1(f2) is invalid and would not be explored while decoding. The output of the decoder is a linearized abstract syntax tree (in an in-order traversal). See §A.2 for details. Learning. We define our model probabilistically, i.e., for any given program z, we can compute the likelihood of the gold-answer p(y∗|z). Combined with the likelihood of the program under the question-parser model p(z|q), we can maximize the marginal likelihood of the answer by enumerating all possible programs; J = ∑ z p(y
∗|z)p(z|q). Since the space of all programs is intractable, we run beam search to enumerate top-K programs and maximize the approximate marginal-likelihood.

heading: 2.2 LEARNING CHALLENGES IN NMN FOR TEXT

text:
As mentioned above, the question parser and the program executor both contain learnable parameters. Each of them is challenging to learn in its own right and joint training further exacerbates the situation.
Question Parser. Our model needs to parse free-form real-world questions into the correct program structure and identify its arguments (e.g. ”who kicked”, ”field goal”, etc.). This is challenging since the questions are not generated from a small fixed grammar (unlike CLEVR), involve lexical variability, and have no program supervision. Additionally, many incorrect programs can yield the same correct answer thus training the question parser to highly score incorrect interpretations.
Program Executor. The output of each intermediate module in the program is a latent decision by the model since the only feedback available is for the final output of the program. The absence of any direct feedback to the intermediate modules complicates learning since the errors of one module would be passed on to the next. Differentiable modules that propagate uncertainties in intermediate decisions help here, such as attention on pixels in CLEVR, but do not fully solve the learning challenges.
Joint Learning. Jointly training the parser and executor increases the latent choices available to the model by many folds while the only supervision available is the gold answer. Additionally, joint learning is challenging as prediction errors from one component lead to incorrect training of the other. E.g., if the parser predicts the program relocate(find()) for the question in Fig. 1, then the associated modules would be incorrectly trained to predict the gold answer. On the next iteration, incorrect program execution would provide the wrong feedback to the question parser and lead to its incorrect training, and learning fails.

heading: 3 MODULES FOR REASONING OVER TEXT

text: Modules are designed to perform basic independent reasoning tasks and form the basis of the compositional reasoning that the model is capable of. We identify a set of tasks that need to be performed to support diverse enough reasoning capabilities over text, numbers, and dates, and define modules accordingly. Since the module parameters will be learned jointly with the rest of the model, we would like the modules to maintain uncertainties about their decisions and propagate them through the decision making layers via end-to-end differentiability. One of the main contributions of our work is introducing differentiable modules that perform reasoning over text and symbols in a probabilistic manner. Table 1 gives an overview of representative modules and §3.2 describes them in detail.

heading: 3.1 DATA TYPES

text:
The modules operate over the following data types. Each data type represents its underlying value as a normalized distribution over the relevant support.
• Question (Q) and Paragraph (P) attentions: soft subsets of relevant tokens in the text. • Number (N) and Date (D): soft subset of unique numbers and dates from the passage. 1 • Count Number (C): count value as a distribution over the supported count values (0− 9). • Time Delta (TD): a value amongst all possible unique differences between dates in the
paragraph. In this work, we consider differences in terms of years. • Span (S): span-type answers as two probability values (start/end) for each paragraph token.

heading: 3.2 NEURAL MODULES FOR QUESTION ANSWERING

text:
The question and paragraph contextualized embeddings (Q and P) are available as global variables to all modules in the program. The question attention computed by the decoder during the timestep the module was produced is also available to the module as a side argument, as described in §2.1.
find(Q)→ P This module is used to ground attended question tokens to similar tokens in the paragraph (e.g., “field goal” in Figure 1). We use a question-to-paragraph attention matrix A ∈ Rn×m whose i-th row is the distribution of similarity over the paragraph tokens for the i-th question token. The output is an expected paragraph attention; a weighted-sum of the rows of A, weighed by the input question attention, P = ∑ iQi ·Ai: ∈ Rm. A is computed by normalizing (using softmax) the rows of a question-to-paragraph similarity matrix S ∈ Rn×m. Here Sij is the similarity between the contextual embeddings of the i-th question token and the j-th paragraph token computed as, Sij = wf
T [Qi: ;Pj: ;Qi: ◦Pj:], where wf ∈ R3d is a learnable parameter vector of this module, [; ] denotes the concatenation operation, and ◦ is elementwise multiplication.
filter(Q, P) → P This module masks the input paragraph attention conditioned on the question, selecting a subset of the attended paragraph (e.g., selecting fields goals “in the second
1We extract numbers and dates as a pre-processing step explained in the Appendix (§A.3)
quarter” in Fig. 1). We compute a locally-normalized paragraph-token mask M ∈ Rm where Mj is the masking score for the j-th paragraph token computed as Mj = σ(wfilterT [q ;Pj: ;q ◦Pj:]). Here q = ∑ iQi ·Qi: ∈ Rd, is a weighted sum of question-token embeddings, wfilterT ∈ R3d is a learnable parameter vector, and σ is the sigmoid non-linearity function. The output is a normalized masked input paragraph attention, Pfiltered = normalize(M ◦ P ).
relocate(Q, P)→ P This module re-attends to the paragraph based on the question and is used to find the arguments for paragraph spans (e.g., shifting the attention from “field goals” to “who kicked” them). We first compute a paragraph-to-paragraph attention matrix R ∈ Rm×m based on the question, as Rij = wrelocateT [(q + Pi:) ;Pj: ; (q + Pi:) ◦Pj:], where q = ∑ iQi ·Qi: ∈ Rd, and wrelocate ∈ R3d is a learnable parameter vector. Each row of R is also normalized using the softmax operation. The output attention is a weighted sum of the rows R weighted by the input paragraph attention, Prelocated = ∑ i Pi ·Ri:
find-num(P)→ N This module finds a number distribution associated with the input paragraph attention. We use a paragraph token-to-number-token attention map Anum ∈ Rm×Ntokens whose i-th row is probability distribution over number-containing tokens for the i-th paragraph token. We first compute a token-to-number similarity matrix Snum ∈ Rm×Ntokens as, Snumi,j = PTi:WnumPnj :, where nj is the index of the j-th number token and Wnum ∈ Rd×d is a learnable parameter. Anumi: = softmax(Snumi:). We compute an expected distribution over the number tokens T = ∑ i Pi · Anumi: and aggregate the probabilities for number-tokens with the same value to compute the output distribution N . For example, if the values of the number-tokens are [2, 2, 3, 4] and T = [0.1, 0.4, 0.3, 0.2], the output will be a distribution over {2, 3, 4} with N = [0.5, 0.3, 0.2]. find-date(P)→ D follows the same process as above to compute a distribution over dates for the input paragraph attention. The corresponding learnable parameter matrix is Wdate ∈ Rd×d.
count(P) → C This module is used to count the number of attended paragraph spans. The idea is to learn a module that detects contiguous spans of attention values and counts each as one. For example, if an attention vector is [0, 0, 0.3, 0.3, 0, 0.4], the count module should produce an output of 2. The module first scales the attention using the values [1, 2, 5, 10] to convert it into a matrix Pscaled ∈ Rm×4. A bidirectional-GRU then represents each token attention as a hidden vector ht. A single-layer feed-forward network maps this representation to a soft 0/1 score to indicate the presence of a span surrounding it. These scores are summed to compute a count value, cv = ∑ σ (FF (countGRU(Pscaled))) ∈ R. We hypothesize that the output count value is normally distributed with cv as mean, and a constant variance v = 0.5, and compute a categorical distribution over the supported count values, as p(c) ∝ exp(−(c−cv)2/2v2) ∀c ∈ [0, 9]. Pretraining this module by generating synthetic data of attention and count values helps (see §A.4).
compare-num-lt(P1, P2)→ P This module performs a soft less-than operation between two passage distributions. For example, to find the city with fewer people, cityA or cityB, the module would output a linear combination of the two input attentions weighted by which city was associated with a lower number. This module internally calls the find-nummodule to get a number distribution for each of the input paragraph attentions, N1 and N2. It then computes two soft boolean values, p(N1 < N2) and p(N2 < N1), and outputs a weighted sum of the input paragraph attentions. The boolean values are computed by marginalizing the relevant joint probabilities:
p(N1 < N2) = ∑ i ∑ j 1Ni1<N j 2 N i1N j 2 p(N2 < N1) = ∑ i ∑ j 1Ni2<N j 1 N i2N j 1
The final output is, Pout = p(N1 < N2) ∗ P1 + p(N2 < N1) ∗ P2. When the the predicted number distributions are peaky, p(N1 < N2) or p(N2 < N1) is close to 1, and the output is either P1 or P2.
We similarly include the comparison modules compare-num-gt, compare-date-lt, and compare-date-gt, defined in an essentially identical manner, but for greater-than and for dates.
time-diff(P1, P2)→ TD The module outputs the difference between the dates associated with the two paragraph attentions as a distribution over all possible difference values. The module internally calls the find-date module to get a date distribution for the two paragraph attentions,
D1 and D2. The probability of the difference being td is computed by marginalizing over the joint probability for the dates that yield this value, as p(td) = ∑ i,j 1(di−dj=td)D i 1D j 2.
find-max-num(P) → P, find-min-num(P) → P Given a passage attention attending to multiple spans, this module outputs an attention for the span associated with the largest (or smallest) number. We first compute an expected number token distribution T using find-num, then use this to compute the expected probability that each number token is the one with the maximum value, Tmax ∈ RNtokens (explained below). We then re-distribute this distribution back to the original passage tokens associated with those numbers. The contribution from the i-th paragraph token to the j-th number token, Tj , was Pi ·Anumij . To compute the new attention value for token i, we re-weight this contribution based on the ratio Tmaxj /Tj and marginalize across the number tokens to get the new token attention value: P̄i = ∑ j Tmaxj /Tj · Pi ·Anumij .
Computing Tmax: Consider a distribution over numbers N , sorted in an increasing order. Say we sample a set S (size n) of numbers from this distribution. The probability that Nj is the largest number in this set is p(x ≤ Nj)n − p(x ≤ Nj−1)n i.e. all numbers in S are less than or equal to Nj , and at least one number is Nj . By picking the set size n = 3 as a hyperparameter, we can analytically (and differentiably) convert the expected distribution over number tokens, T , into a distribution over the maximum value Tmax.
span(P) → S This module is used to convert a paragraph attention into a contiguous answer span and only appears as the outermost module in a program. The module outputs two probability distributions, Ps and Pe ∈ Rm, denoting the probability of a token being the start and end of a span, respectively. This module is implemented similar to the count module (see §A.5).

heading: 4 AUXILIARY SUPERVISION

text: As mentioned in §2.2, jointly learning the parameters of the parser and the modules using only endtask QA supervision is extremely challenging. To overcome issues in learning, (a) we introduce an unsupervised auxiliary loss to provide an inductive bias to the execution of find-num, find-date, and relocate modules (§4.1); and (b) provide heuristically-obtained supervision for question program and intermediate module output (§4.2) for a subset of questions (5–10%).

heading: 4.1 UNSUPERVISED AUXILIARY LOSS FOR IE

text:
The find-num, find-date, and relocate modules perform information extraction by finding relevant arguments for entities and events mentioned in the context. In our initial experiments we found that these modules would often spuriously predict a high attention score for output tokens that appear far away from their corresponding inputs. We introduce an auxiliary objective to induce the idea that the arguments of a mention should appear near it. For any token, the objective increases the sum of the attention probabilities for output tokens that appear within a window W = 10, letting the model distribute the mass within that window however it likes. The objective for the find-num is
Hnloss = − m∑ i=1 log (Ntokens∑ j=0 1nj∈[i±W ]A num ij ) We compute a similar loss for the date-attention map Adate (Hdloss) and the relocate-map R (H r loss). The final auxiliary loss is Hloss = Hnloss +H d loss +H r loss.

heading: 4.2 QUESTION PARSE AND INTERMEDIATE MODULE OUTPUT SUPERVISION

text:
Question Parse Supervision. Learning to parse questions in a noisy feedback environment is very challenging. For example, even though the questions in CLEVR are programmatically generated, Hu et al. (2017) needed to pre-train their parser using external supervision for all questions. For DROP, we have no such external supervision. In order to bootstrap the parser, we analyze some questions manually and come up with a few heuristic patterns to get program and corresponding question attention supervision (for modules that require it) for a subset of the training data (10%
of the questions; see §A.6). For example, for program find-num(find-max-num(find())), we provide supervision for question tokens to attend to when predicting the find module.
Intermediate Module Output Supervision. Consider the question, “how many yards was the shortest goal?”. The model only gets feedback for how long the shortest goal is, but not for other goals. Such feedback biases the model in predicting incorrect values for intermediate modules (only the shortest goal instead of all in find-num) which in turn hurts model generalization.
We provide heuristically-obtained noisy supervision for the output of the find-num and find-date modules for a subset of the questions (5%) for which we also provide question program supervision. For questions like “how many yards was the longest/shortest touchdown?”, we identify all instances of the token “touchdown” in the paragraph and assume the closest number to it should be an output of the find-num module. We supervise this as a multi-hot vector N∗ and use an auxiliary loss, similar to question-attention loss, against the output distribution N of find-num. We follow the same procedure for a few other question types involving dates and numbers; see §A.7 for details.

heading: 5 EXPERIMENTS

heading: 5.1 DATASET

text:
We perform experiments on a portion of the recently released DROP dataset (Dua et al., 2019), which to the best of our knowledge is the only dataset that requires the kind of compositional and symbolic reasoning that our model aims to solve. Our model possesses diverse but limited reasoning capability; hence, we try to automatically extract questions in the scope of our model based on their first n-gram. These n-grams were selected by performing manual analysis on a small set of questions. The dataset we construct contains 20, 000 questions for training/validation, and 1800 questions for testing (25% of DROP). Since the DROP test set is hidden, this test set is extracted from the validation data. Though this is a subset of the full DROP dataset it is still a significantly-sized dataset that allows drawing meaningful conclusions. We make our subset and splits available publicly with the code.
Based on the manual analysis we classify these questions into different categories, which are: Date-Compare e.g. What happened last, commission being granted to Robert or death of his cousin? Date-Difference e.g. How many years after his attempted assassination was James II coronated? Number-Compare e.g. Were there more of cultivators or main agricultural labourers in Sweden? Extract-Number e.g. How many yards was Kasay’s shortest field goal during the second half? Count e.g. How many touchdowns did the Vikings score in the first half? Extract-Argument e.g. Who threw the longest touchdown pass in the first quarter?
Auxiliary Supervision Out of the 20, 000 training questions, we provide question program supervision for 10% (2000), and intermediate module output supervision for 5% (1000) of training questions. We use curriculum learning (Bengio et al., 2009) where the model is trained only on heuristically-supervised non-count questions for the first 5 epochs.

heading: 5.2 RESULTS

text:
We compare to publicly available best performing models: NAQANet (Dua et al., 2019), NABERT+ (Kinley & Lin, 2019), TAG-NABERT+ (Avia Efrat & Shoham, 2019), and MTMSN (Hu et al., 2019), all trained on the same data as our model. We implement our model using AllenNLP (Gardner et al., 2018). 2
The hyperparameters used for our model are described in the appendix. All results are reported as an average of 4 model runs.
Overall. Table 2a compares our model’s performance to state-of-the-art models on our full test set. Our model achieves an F1 score of 73.1 (w/ GRU) and significantly outperforms NAQANet (62.1 F1). Using BERT representations, our model’s performance increases to 77.4 F1 and outperforms SoTA models that use BERT representations, such as MTMSN (76.5 F1). This shows the efficacy of our proposed model in understanding complex compositional questions and performing multi-step
2Our code is available at http://cogcomp.org/page/publication_view/899.
reasoning over natural language text. Additionally, this shows that structured models still benefit when used over representations from large pretrained-LMs, such as BERT.
Performance by Question Type. Table 2b shows the performance for different question types as identified by our heuristic labeling. Our model outperforms MTMSN on majority of question types but struggles with counting questions; it outperforms MTMSN on only some of the runs. Even after pre-training the count module using synthetic data, training it is particularly unstable. We believe this is because feedback from count questions is weak, i.e., the model only gets feedback about the count value and not what the underlying set is; and because it was challenging to define a categorical count distribution given a passage attention distribution— finding a better way to parameterize this function is an interesting problem for future work.
Effect of Additional Supervision. Figure 2a shows that the unsupervised auxiliary objective significantly improves model performance (from 57.3 to 73.1 F1). The model using BERT diverges while training without the auxiliary objective. Additionally, the intermediate module output supervision has slight positive effect on the model performance.
Effect of Training Data Size. Figure 2b shows that our model significantly outperforms MTMSN when training using less data, especially using 10-25% of the available supervision. This shows that by explicitly modeling compositionality, our model is able to use additional auxiliary supervision effectively and achieves improved model generalization.
Incorrect Program Predictions. Mistakes by our model can be classified into two types; incorrect program prediction and incorrect execution. Here we show few mistakes of the first type that highlight the need to parse the question in a context conditional manner:
1. How many touchdown passes did Tom Brady throw in the season? - count(find) is incorrect since the correct answer requires a simple lookup from the paragraph.
2. Which happened last, failed assassination attempt on Lenin, or the Red Terror? - date-compare-gt(find, find)) is incorrect since the correct answer requires natural language inference about the order of events and not symbolic comparison between dates.
3. Who caught the most touchdown passes? - relocate(find-max-num(find))). Such questions, that require nested counting, are out of scope of our defined modules because the model would first need to to count the passes caught by each player.

heading: 6 RELATED WORK

text:
Semantic parsing techniques have been used for a long time for compositional question understanding. Approaches have used labeled logical-forms (Zelle & Mooney, 1996; Zettlemoyer & Collins, 2005), or weak QA supervision (Clarke et al., 2010; Berant et al., 2013; Reddy et al., 2014) to learn parsers to answer questions against structured knowledge bases. These have also been extended for QA using symbolic reasoning against semi-structured tables (Pasupat & Liang, 2015; Krishnamurthy et al., 2017; Neelakantan et al., 2016). Recently, BERT-based models for DROP have been been
Supervision Type w/ BERT w/ GRU Hloss MOD-SUP
3 3 77.4 73.1 3 76.3 71.8
3 –* 57.3
(a) Effect of Auxiliary Supervision: The auxiliary loss contributes significantly to the performance, whereas module output supervision has little effect. *Training diverges without Hloss for the BERT-based model.
(b) Performance with less training data: Our model performs significantly better than the baseline with less training data, showing the efficacy of explicitly modeling compositionality.
Figure 2: Effect of auxiliary losses and the size of training data on model performance.
proposed (Hu et al., 2019; Andor et al., 2019; Kinley & Lin, 2019), but all these models essentially perform a multiclass classification over pre-defined programs. Our model on the other hand provides an interpretable, compositional parse of the question and exposes its intermediate reasoning steps.
For combining learned execution modules with semantic parsing, many variations to NMNs have been proposed; NMN (Andreas et al., 2016) use a PCFG parser to parse the question and only learn module parameters. N2NMNs (Hu et al., 2017) simultaneously learn to parse and execute but require pre-training the parser. Gupta & Lewis (2018) propose a NMN model for QA against knowledge graphs and learn execution for semantic operators from QA supervision alone. Recent works (Gupta & Lewis, 2018; Mao et al., 2019) also use domain-knowledge to alleviate issues in learning by using curriculum learning to train the executor first on simple questions for which parsing is not an issue. All these approaches perform reasoning on synthetic domains, while our model is applied to natural language. Concurrently, Jiang & Bansal (2019) apply NMN to HotpotQA (Yang et al., 2018) but their model comprises of only 3 modules and is not capable of performing symbolic reasoning.

heading: 7 FUTURE DIRECTIONS

text:
We try a trivial extension to our model by adding a module that allows for addition & subtraction between two paragraph numbers. The resulting model achieves a score of 65.4 F1 on the complete validation data of DROP, as compared to MTMSN that achieves 72.8 F1.
Manual analysis of predictions reveals that a significant majority of mistakes are due to insufficient reasoning capability in our model and would require designing additional modules. For example, questions such as (a) How many languages each had less than 115, 000 speakers in the population? and Which racial groups are smaller than 2%? would require pruning passage spans based on the numerical comparison mentioned in the question; (b) Which quarterback threw the most touchdown passes? and In which quarter did the teams both score the same number of points? would require designing modules that considers some key-value representation of the paragraph; (c) How many points did the packers fall behind during the game? would require IE for implicit argument (points scored by the other team). It is not always clear how to design interpretable modules for certain operations; for example, for the last two cases above.
It is worth emphasizing here what happens when we try to train our model on these questions for which our modules can’t express the correct reasoning. The modules in the predicted program get updated to try to perform the reasoning anyway, which harms their ability to execute their intended operations (cf. §2.2). This is why we focus on only a subset of the data when training our model. In part due to this training problem, some other mistakes of our model relative to MTMSN on the full dataset are due to incorrect execution of the intermediate modules. For example, incorrect grounding by the find module, or incorrect argument extraction by the find-num module. For mistakes such as these, our NMN based approach allows for identifying the cause of mistakes and supervising these modules using additional auxiliary supervision that is not possible in black-box models. This additionally opens up avenues for transfer learning where modules can be independently trained
using indirect or distant supervision from different tasks. Direct transfer of reasoning capability in black-box models is not so straight-forward.
To solve both of these classes of errors, one could use black-box models, which gain performance on some questions at the expense of limited interpretability. It is not trivial to combine the two approaches, however. Allowing black-box operations inside of a neural module network significantly harms the interpretability—e.g., an operation that directly answers a question after an encoder, mimicking BERT-QA-style models, encourages the encoder to perform complex reasoning in a non-interpretable way. This also harms the ability of the model to use the interpretable modules even when they would be sufficient to answer the question. Additionally, due to our lack of supervised programs, training the network to use the interpretable modules instead of a black-box shortcut module is challenging, further compounding the issue. Combining these black-box operations with the interpretable modules that we have presented is an interesting and important challenge for future work.

heading: 8 CONCLUSION

text:
We show how to use neural module networks to answer compositional questions requiring symbolic reasoning against natural language text. We define probabilistic modules that propagate uncertainty about symbolic reasoning operations in a way that is end-to-end differentiable. Additionally, we show that injecting inductive bias using unsupervised auxiliary losses significantly helps learning.
While we have demonstrated marked success in broadening the scope of neural modules and applying them to open-domain text, it remains a significant challenge to extend these models to the full range of reasoning required even just for the DROP dataset. NMNs provide interpretability, compositionality, and improved generalizability, but at the cost of restricted expressivity as compared to more black box models. Future research is necessary to continue bridging these reasoning gaps.

heading: ACKNOWLEDGMENTS

text: We would like to thank Daniel Deutsch and the anonymous reviewers for their helpful comments. This material is based upon work sponsored in part by the DARPA MCS program under Contract No. N660011924033 with the United States Office Of Naval Research, an ONR award, the LwLL DARPA program, and a grant from AI2.

heading: A APPENDIX

text:
A.1 QUESTION AND PARAGRAPH ENCODER
Our model represents the question q as Q ∈ Rn×d and paragraph p as P ∈ Rm×d using contextualized token embeddings. These embeddings are either produced using a multi-layer GRU network that is trained from scratch, or a pr-trained BERT model that is fine-tuned during training.
GRU: We use a 2-layer, 64-dimensional (d = 128, effectively), bi-directional GRU. The same GRU is used for both, the question and the paragraph. The token embeddings input to the contextual encoder are a concatenation of 100-d pre-trained GloVe embeddings, and 200-d embeddings output from a CNN over the token’s characters. The CNN uses filters of size=5 and character embeddings of 64-d. The pre-trained glove embeddings are fixed, but the character embeddings and the parameters for the CNN are jointly learned with the rest of the model.
BERT: The input to the BERT model is the concatenation of the question and paragraph in the following format: [CLS] Question [SEP] Context [SEP]. The question and context tokens input to the BERT model are sub-words extracted by using BERT’s tokenizer. We separate the question and context representation from the output of BERT as Q and P, respectively. We use ‘bert-base-uncased‘ model for all out experiments.
A.2 QUESTION PARSER DECODER
The decoder for question parsing is a single-layer, 100-dimensional, LSTM. For each module, we use a 100-dimensional embedding to present it as an action in the decoder’s input/output vocabulary. The attention is computed as a dot-product between the decoder hidden-state and the encoders hidden states which is normalized using the softmax operation.
As the memory-state for the zero-eth time-step in the decoder, we use the last hidden-state of the question encoder GRU, or the [CLS] embedding for the BERT-based model.
We use a beam-size of 4 for the approximate maximum marginal likelihood objective. Optmization is performed using the Adam algorithm with a learning rate of 0.001 or using BERT’s optimizer with a learning rate of 1e− 5.
A.3 NUMBER AND DATE PARSING
We pre-process the paragraphs to extract the numbers and dates in them. For numbers, we use a simple strategy where all tokens in the paragraph that can be parsed as a number are extracted. For example, 200 in “200 women”. The total number of number-tokens in the paragraph is denoted by Ntokens. We do not normalize numbers based on their units and leave it for future work.
To extract dates from the paragraph, we run the spaCy-NER3 and collect all “DATE” mentions. To normalize the date mentions we use an off-the-shelf date-parser4. For example, a date mention “19th November, 1961” would be normalized to (19, 11, 1961) (day, month, year). The total number of date-tokens is denoted by Dtokens
A.4 PRE-TRAINING COUNT MODULE
As mentioned in the paper, training the count module is challenging and found that pre-training the parameters of the count module helps.
To re-iterate, the module gets as input a paragraph attention P ∈ Rm. The module first scales the attention using the values [1, 2, 5, 10] to convert it into a matrix Pscaled ∈ Rm×4. A bidirectional-GRU then represents each token attention as a hidden vector ht. A single-layer feed-forward network maps this representation to a soft 0/1 score to indicate the presence of a span surrounding it. These scores
3https://spacy.io/ 4https://github.com/scrapinghub/dateparser
are summed to compute a count value, cv . countscores = σ ( FF (countGRU(Pscaled)) ) ∈ Rm
cv = ∑ countscores ∈ R
We generate synthetic data to pre-train this module; each instance is a normalized-attention vector x = Rm and a count value y ∈ [0, 9]. This is generated by sampling m uniformly between 200−600, then sampling a count value y uniformly in [0, 9]. We then sample y span-lengths between 5− 15 and also sample y non-overlapping span-positions in the attention vector x. For all these y spans in x, we put a value of 1.0 and zeros everywhere else. We then add 0-mean, 0.01-variance gaussian noise to all elements in x and normalize to make the normalized attention vector that can be input to the count module.
We train the parameters of the count module using these generated instances using L2-loss between the true count value and the predicted cv .
The countGRU in the count module (spanGRU – span module) is a 2-layer, bi-directional GRU with input-dim = 4 and output-dim = 20. The final feed-forward comprises of a single-layer to map the output of the countGRU into a scalar score.
A.5 SPAN MODULE
The span module is implemented similar to the count module. The input paragraph attention is first scaled using [1, 2, 5, 10], then a bidirectional-GRU represents each attention as a hidden vector, and a single-layer feed-forward network maps this to 2 scores, for span start and end. A softmax operation on these scores gives the output probabilities.
A.6 AUXILIARY QUESTION PARSE SUPERVISION
For questions with parse supervision z∗, we decouple the marginal likelihood into two maximum likelihood objectives, p(z∗|q) and p(y∗|z∗). We also add a loss for the decoder to attend to the tokens in the question attention supervision when predicting the relevant modules. The question attention supervision is provided as a mutli-hot vector α∗ ∈ {0, 1}n. The loss against the predicted attention vector α is, Qloss = − ∑n i=1 α ∗ i logαi. Since the predicted attention is a normalized distribution, the objective increases the sum of log-probabilities of the tokens in the supervision.
The following patterns are used to extract the question parse supervision for the training data:

heading: 1. what happened first SPAN1 or SPAN2?

text: span(compare-date-lt(find(), find())): with find attentions on SPAN1 and SPAN2, respectively. Use compare-date-gt, if second instead of first.

heading: 2. were there fewer SPAN1 or SPAN2?

text:
span(compare-num-lt(find(), find())): with find attentions on SPAN1 and SPAN2, respectively. Use compare-num-gt, if more instead of fewer.
3. how many yards was the longest {touchdown / field goal}? find-num(find-max-num(find())): with find attention on touchdown / field goal. For shortest, the find-min-num module is used.
4. how many yards was the longest {touchdown / field goal} SPAN ? find-num(find-max-num(filter(find()))): with find attention on touchdown / field goal and filter attention on all SPAN tokens.
5. how many {field goals, touchdowns, passes} were scored SPAN? count(filter(find())): with find attention on {field goals, touchdowns, passes} and filter attention on SPAN.
6. who {kicked, caught, threw, scored} SPAN? span(relocate(filter(find()))): with relocate attention on {kicked, caught, threw, scored}, find attention on {touchdown / field goal}, and filter attention on all other tokens in the SPAN.
A.7 HEURISTIC INTERMEDIATE MODULE OUTPUT SUPERVISION
As mentioned in Section 4.3, we heuristically find supervision for the output of the find-num and find-date module for a subset of questions that already contain question program supervision. These are as follows:
1. how many yards was the longest/shortest {touchdown, field goal}? We find all instances of touchdown/field goal in the passage and assume that the number appearing closest should be an output of the find-num module.

heading: 2. what happened first EVENT1 or EVENT2?

text: Similar to above, we perform fuzzy matching to find the instance of EVENT1 and EVENT2 in the paragraph and assume that the closest dates should be the output of the two find-date module calls made by the compare-date-lt module in the gold program.

heading: 3. were there fewer SPAN1 or SPAN2?

text:
This is exactly the same as previous for find-num module calls by compare-num-lt.
A.8 EXAMPLE PREDICTIONS
In Figures 3, 4, 5, 6, 7 we show predictions by our model that shows the learned execution of various modules defined in the paper.


summaries: This paper analyzes how signals propagate through randomly initialized neural networks that have undergone a kind of pruning/sparsification. The pruning method utilizes a metric called 'connection sensitivity', which has been used in prior work and which measures the infinitessimal impact of turning off specific parameters. The distribution of singular values in the layer-to-layer Jacobian matrices for pruned networks becomes increasingly pathological as the depth increases. This observation motivates the concept of 'layerwise dynamical isometry' (LDI), a slight generalization of the concept of 'dynamical isometry' that has been studied in prior work. Several methods for approximately obtaining differing amounts of LDI are investigated in a series of in-depth experiments that show a strong correlation between increased signal propagation and improved trainability of sparse networks.

summaries: In this paper, the authors studied and formalized the effect of initialization to connection-sensitivity-based pruning. The authors first pointed out that a previously studied pruning criterion -- connection sensitivity (CS) -- is a normalized magnitude of gradients. Based on signal propagation theory, to achieve a 'faithful' (with minimal amplification) CS, the gradients must be also faithful. Then by using relation of Jacobians and gradient, the authors proved that orthogonally initial weights guarantees faithful on linear networks and certain distribution property on nonlinear network can achieve layerwise dynamic isometry, which is to ensure faithful signal propagation. Based on these findings, the authors proposed an initialization setup for improving pruning performance, with the goal to ensure dynamic isometry by orthogonal initialization and approximation.

abstractText: Network pruning is a promising avenue for compressing deep neural networks. A typical approach to pruning starts by training a model and then removing redundant parameters while minimizing the impact on what is learned. Alternatively, a recent approach shows that pruning can be done at initialization prior to training, based on a saliency criterion called connection sensitivity. However, it remains unclear exactly why pruning an untrained, randomly initialized neural network is effective. In this work, by noting connection sensitivity as a form of gradient, we formally characterize initialization conditions to ensure reliable connection sensitivity measurements, which in turn yields effective pruning results. Moreover, we analyze the signal propagation properties of the resulting pruned networks and introduce a simple, data-free method to improve their trainability. Our modifications to the existing pruning at initialization method lead to improved results on all tested network models for image classification tasks. Furthermore, we empirically study the effect of supervision for pruning and demonstrate that our signal propagation perspective, combined with unsupervised pruning, can be useful in various scenarios where pruning is applied to non-standard arbitrarily-designed architectures.

title: 2018): large sparse networks

authors:
REFERENCES Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

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

title: Deep residual learning for image recognition

authors:
Geoffrey E Hinton
Ruslan R Salakhutdinov

title: Reducing the dimensionality of data with neural networks

authors:
Nal Kalchbrenner
Erich Elsen
Karen Simonyan
Seb Noury
Norman Casagrande
Edward Lockhart
Florian Stimberg
Aaron van den Oord
Sander Dieleman
Koray Kavukcuoglu

title: Efficient neural audio synthesis

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

title: Efficient backprop

venue: Neural Networks: Tricks of the Trade,

authors:
Namhoon Lee
Thalaiyasingam Ajanthan
Philip HS Torr

title: Snip: Single-shot network pruning based on connection sensitivity

authors:
Razvan Pascanu
Tomas Mikolov
Yoshua Bengio

title: On the difficulty of training recurrent neural networks

authors:
Jeffrey Pennington
Samuel Schoenholz
Surya Ganguli

title: Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice

venue: NeurIPS,

authors:
Jeffrey Pennington
Samuel S Schoenholz
Surya Ganguli

title: The emergence of spectral universality in deep networks

authors:
Ben Poole
Subhaneil Lahiri
Maithra Raghu
Jascha Sohl-Dickstein
Surya Ganguli

title: Exponential expressivity in deep neural networks through transient chaos

title: Pruning algorithms-a survey

venue: Neural Networks,

authors:
Andrew M Saxe
James L McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

authors:
Wojciech Tarnowski
Piotr Warchoł
Stanisław Jastrzębski
Jacek Tabor
Maciej A Nowak

title: Dynamical isometry is achieved in residual networks in a universal way for any activation function

authors:
Lechao Xiao
Yasaman Bahri
Jascha Sohl-Dickstein
Samuel S Schoenholz
Jeffrey Pennington

title: Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. ICML, 2018

venue: Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. NeurIPS,

authors:
Greg Yang
Jeffrey Pennington
Vinay Rao
Jascha Sohl-Dickstein
Samuel S

title: Schoenholz. A mean field theory of batch normalization

heading: 1 INTRODUCTION

text:
Deep learning has made great strides in machine learning and been applied to various fields from computer vision and natural language processing, to health care and playing games (LeCun et al., 2015). Despite the immense success, however, it remains challenging to deal with the excessive computational and memory requirements of large neural network models. To this end, lightweight models are often preferred, and network pruning, a technique to reduce parameters in a network, has been widely employed to compress deep neural networks (Han et al., 2016). Nonetheless, designing pruning algorithms has been often purely based on ad-hoc intuition lacking rigorous underpinning, partly because pruning was typically carried out after training the model as a post-processing step or interwoven with the training procedure, without adequate tools to analyze.
Recently, Lee et al. (2019) have shown that pruning can be done on randomly initialized neural networks in a single-shot prior to training (i.e., pruning at initialization). They empirically showed that as long as the initial random weights are drawn from appropriately scaled Gaussians (e.g., Glorot & Bengio (2010)), their pruning criterion called connection sensitivity can be used to prune deep neural networks, often to an extreme level of sparsity while maintaining good accuracy once trained. However, it remains unclear as to why pruning at initialization is effective, how it should be understood theoretically and whether it can be extended further.
In this work, we first look into the effect of initialization on pruning, and find that initial weights have critical impact on connection sensitivity, and therefore, pruning results. Deeper investigation shows that connection sensitivity is determined by an interplay between gradients and weights. Therefore when the initial weights are not chosen appropriately, the propagation of input signals into layers of
these random weights can result in saturating error signals (i.e., gradients) under backpropagation, and hence unreliable connection sensitivity, potentially leading to a catastrophic pruning failure.
This result leads us to develop a signal propagation perspective for pruning at initialization, and to provide a formal characterization of how a network needs to be initialized for reliable connection sensitivity measurements and in turn effective pruning. Precisely, we show that a sufficient condition to ensure faithful1 connection sensitivity is layerwise dynamical isometry, which is defined as all singular values of the layerwise Jacobians being concentrated around 1. Our signal propagation perspective is inspired by the recent literature on dynamical isometry and mean field theory (Saxe et al., 2014; Poole et al., 2016; Schoenholz et al., 2017; Pennington et al., 2017), in which the general signal propagation in neural networks is studied. We extend this result to understanding and improving pruning at initialization.
Moreover, we study signal propagation in the pruned sparse networks and its effect on trainability. We find that pruning neural networks can indeed break dynamical isometry, and hence, hinders signal propagation and degrades the training performance of the resulting sparse network. In order to address this issue, we propose a simple, yet effective data-free method to recover the layerwise orthogonality given the sparse topology, which in turn improves the training performance of the compressed network significantly. Our analysis further reveals that in addition to signal propagation, the choice of pruning method and sparsity level can influence trainability in sparse neural networks.
Perfect layerwise dynamical isometry cannot always be ensured in the modern networks that have components such as ReLU nonlinearities (Pennington et al., 2017) and/or batch normalization (Yang et al., 2019). Even in such cases, however, our experiments on various modern architectures (including convolutional and residual neural networks) indicate that connection sensitivity computed based on layerwise dynamical isometry is robust and consistently outperforms pruning based on other initialization schemes. This indicates that the signal propagation perspective is not only important to theoretically understand pruning at initialization, but also it improves the results of pruning for a range of networks of practical interest.
Furthermore, this signal propagation perspective for pruning poses another important question: how informative is the error signal computed on randomly initialized networks, or can we prune neural networks even without supervision? To understand this, we compute connection sensitivity scores with different unsupervised surrogate losses and evaluate the pruning results. Interestingly, our results indicate that we can in fact prune networks in an unsupervised manner to extreme sparsity levels without compromising accuracy, and it often compares competitively to pruning with supervision. Moreover, we test if pruning at initialization can be extended to obtain architectures that yield better performance than standard pre-designed architectures with the same number of parameters. In fact, this process, which we call neural architecture sculpting, compares favorably against hand-designed architectures, taking network pruning one step further towards neural architecture search.

heading: 2 PRELIMINARIES

text:
Pruning at initialization. The principle behind conventional approaches for network pruning is to find unnecessary parameters, such that by eliminating them the complexity of the model is reduced while minimizing the impact on what is learned (Reed, 1993). Naturally, a typical pruning algorithm starts after convergence to a minimum or training to some degree. This pretraining requirement has been left unattended until Lee et al. (2019) recently showed that pruning can be performed on untrained networks at initiailzation prior to training. They proposed a method called SNIP which relies on a new saliency criterion, namely connection sensitivity, defined as follows:
sj(w;D) = |gj(w;D)|∑m k=1 |gk(w;D)| , where gj(w;D) = ∂L(c w;D) ∂cj ∣∣∣∣ c=1 . (1)
Here, sj is the saliency of the parameter j, w ∈ Rm is the network parameters, c ∈ {0, 1}m is the auxiliary indicator variables representing the connectivity of network parameters, m is the total number of parameters in the network, and D is a given dataset. Also, gj is the derivative of the loss L with respect to cj , which turns out to be an infinitesimal approximation of the change in the
1 The term faithful is used to describe signals propagating in a network isometrically with minimal amplification or attenuation, and borrowed from Saxe et al. (2014), the first work to introduce dynamical isometry.
loss with respect to removing the parameter j. Designed to be computed at initialization, pruning is performed by keeping top-κ (where κ denotes a desired sparsity level) salient parameters based on the above sensitivity scores.
Dynamical isometry and mean field theory. The success of training deep neural networks is due in large part to the initial weights (Hinton & Salakhutdinov, 2006; Glorot & Bengio, 2010; Pascanu et al., 2013). In essence, the principle behind these random weight initializations is to have the mean squared singular value of a network’s input-output Jacobian close to 1, so that on average, an error vector will preserve its norm under backpropagation; however, this is not sufficient to prevent amplification or attenuation of an error vector on worst case. A stronger condition that having as many singular values as possible near 1 is called dynamical isometry (Saxe et al., 2014). Under this condition, error signals backpropagate isometrically through the network, approximately preserving its norm and all angles between error vectors. Alongside dynamical isometry, mean field theory is used to develop a theoretical understanding of signal propagation in neural networks with random parameters (Poole et al., 2016). Precisely, the mean field approximation states that preactivations of wide, untrained neural networks can be captured as a Gaussian distribution. Recent works revealed a maximum depth through which signals can propagate at initialization, and verified that networks are trainable when signals can travel all the way through them (Schoenholz et al., 2017; Yang & Schoenholz, 2017; Xiao et al., 2018).

heading: 3 SIGNAL PROPAGATION PERSPECTIVE TO PRUNING RANDOM NETWORKS

text:
Problem setup. Consider a fully-connected, feed-forward neural network with weight matrices Wl ∈ RN×N , biases bl ∈ RN , pre-activations hl ∈ RN , and post-activations xl ∈ RN , for l ∈ {1 . . .K} up to K layers. Now, the feed-forward dynamics of a network can be written as,
xl = φ(hl) , hl = Wlxl−1 + bl , (2)
where φ : R→ R is an elementwise nonlinearity, and the input is denoted by x0. Given the network configuration, the parameters are initialized by sampling from a probability distribution, typically a zero mean Gaussian with scaled variance (LeCun et al., 1998; Glorot & Bengio, 2010).

heading: 3.1 EFFECT OF INITIALIZATION ON PRUNING

text:
It is observed in Lee et al. (2019) that pruning results tend to improve when initial weights are drawn from a scaled Gaussian, or so-called variance scaling initialization (LeCun et al., 1998; Glorot & Bengio, 2010; He et al., 2015). As we wish to better understand the role of these random initial weights in pruning, we will examine the effect of varying initialization on the pruning results.
In essence, variance scaling schemes introduce normalization factors to adjust the variance σ of the weight sampling distribution, which can be summarized as σ → αψlσ, where ψl is a layerwise scalar that depends on an architecture specification such as the number of output neurons in the previous layer (e.g., fan-in), and α is a global scalar throughout the network. Notice in case of a network with layers of the same width, the variance can be controlled by a single scalar γ = αψ as ψl = ψ for all layers l. In particular, we take both linear and tanh multilayer perceptron networks (MLP) of layers K = 7 and width N = 100 on MNIST with σ = 1 as the default, similar to Saxe et al. (2014). We initialize these networks with different γ, compute the connection sensitivity, prune it, and then visualize layerwise the resulting sparsity patterns c as well as the corresponding connection sensitivity used for pruning in Figure 1.
It is seen in the sparsity patterns that for the tanh network, unlike the linear case, more parameters tend to be pruned in the later layers than the earlier layers. As a result, this limits the learning capability of the subnetwork critically when a high sparsity level is requested; e.g., for κ̄ = 90%, only a few parameters in later layers are retained after pruning. This is explained by the connection sensitivity plot. The sensitivity of parameters in the nonlinear network tends to decrease towards the later layers, and therefore, choosing the top-κ parameters globally based on the sensitivity scores results in a subnetwork in which retained parameters are distributed highly non-uniformly and sparsely towards the end of the network. This result implies that the initial weights have a crucial effect on the connection sensitivity, and from there, the pruning results.

heading: 3.2 GRADIENT SIGNAL IN CONNECTION SENSITIVITY

text:
We posit that the unreliability of connection sensitivity observed in Figure 1 is due to poor signal propagation: an initialization that projects the input signal to be strongly amplified or attenuated in the forward pass will saturate the error signal under backpropagation (i.e., gradients), and hence will result in poorly calibrated connection sensitivity scores across layers, which will eventually lead to poor pruning results, potentially with complete disconnection of signal paths (e.g., entire layer).
Precisely, we give the relationship between the connection sensitivity and the gradients as follows. From Equation 1, connection sensitivity is a normalized magnitude of gradients with respect to the connectivity parameters c. Here, we use the vectorized notation where w denotes all learnable parameters and c denotes the corresponding connectivity parameters. From chain rule, we can write:
∂L(c w;D) ∂c ∣∣∣∣ c=1 = ∂L(c w;D) ∂(c w) ∣∣∣∣ c=1 w = ∂L(w;D) ∂w w . (3)
Therefore, ∂L/∂c is the gradients ∂L/∂w amplified (or attenuated) by the corresponding weights w, i.e., ∂L/∂cj = ∂L/∂wj wj for all j ∈ {1 . . .m}. Considering ∂L/∂cj for a given j, since wj does not depend on any other layers or signal propagation, the only term that depends on signal propagation in the network is the gradient term ∂L/∂wj . Hence, a necessary condition to ensure faithful ∂L/∂c (and connection sensitivity) is that the gradients ∂L/∂w need to be faithful. In the following section, we formalize this from a signal propagation perspective, and characterize an initial condition that ensures reliable connection sensitivity measurement.

heading: 3.3 LAYERWISE DYNAMICAL ISOMETRY

heading: 3.3.1 GRADIENTS IN TERMS OF JACOBIANS

text:
From the feed-forward dynamics of a network in Equation 2, the network’s input-output Jacobian corresponding to a given input x0 can be written, by the chain rule of differentiation, as:
J0,K = ∂xK
∂x0 = K∏ l=1 DlWl , (4)
where Dl ∈ RN×N is a diagonal matrix with entries Dlij = φ′(hli)δij , with φ′ denoting the derivative of nonlinearity φ, and δij = 1[i = j] is the Kronecker delta. Here, we will use Jk,l to denote the Jacobian from layer k to layer l. Now, we give the relationship between gradients and Jacobians:
Proposition 1. Let = ∂L/∂xK denote the error signal and x0 denote the input signal. Then,
1. the gradients satisfy: gTwl = J
l,KDl ⊗ xl−1 , (5) where Jl,K = ∂xK/∂xl is the Jacobian from layer l to the output and⊗ is the Kronecker product.
2. additionally, for linear networks, i.e., when φ is the identity:
gTwl = J l,K ⊗
( J0,l−1x0 + a ) , (6)
where J0,l−1 = ∂xl−1/∂x0 is the Jacobian from the input to layer l−1 and a ∈ RN is a constant term that does not depend on x0.
Proof. This can be proved by an algebraic manipulation of the chain rule while using the feedforward dynamics in Equation 2. We provide the full derivation in Appendix A.
Notice that the gradient at layer l constitutes both the backward propagation of the error signal up to layer l and the forward propagation of the input signal x0 up to layer l−1. Moreover, especially in the linear case, the signal propagation in both directions is governed by the corresponding Jacobians. We believe that this interpretation of gradients is useful as it sheds light on how signal propagation affects the gradients. To this end, we next analyze the conditions on the Jacobians, which would guarantee faithful signal propagation in the network, and consequently, faithful gradients.

heading: 3.3.2 ENSURING FAITHFUL GRADIENTS

text:
Here, we first consider the layerwise signal propagation which would be useful to derive properties on the initialization to ensure faithful gradients. To this end, let us consider the layerwise Jacobian:
Jl−1,l = ∂xl
∂xl−1 = DlWl . (7)
Note that it is sufficient to have layerwise dynamical isometry in order to ensure faithful signal propagation in the network.
Definition 1. (Layerwise dynamical isometry) Let Jl−1,l = ∂x l ∂xl−1 ∈ RNl×Nl−1 be the Jacobian matrix of layer l. The network is said to satisfy layerwise dynamical isometry if the singular values of Jl−1,l are concentrated near 1 for all layers, i.e., for a given > 0, the singular value σj satisfies |1− σj | ≤ for all j.
This would guarantee that the signal from layer l to l − 1 (or vice versa) is propagated without amplification or attenuation in any of its dimension. From Proposition 1 and Equation 7, by induction, it is easy to show that if the layerwise signal propagation is faithful, the error and input signals will faithfully propagate throughout the network, resulting in faithful gradients.
For linear networks, Jl−1,l = W l. Therefore, one can initialize the weight matrix to be orthogonal such that (Wl)TWl = I, where I is the identity matrix of dimension N . In this case, all singular values of Wl are exactly 1 (i.e., exact dynamical isometry), and such an initialization guarantees faithful gradients. While a linear network is of little practical use, we note that it helps to develop theoretical analysis and provides intuition as to why dynamical isometry is a useful measure.
For nonlinear networks, the diagonal matrix Dl needs to be accounted for as it depends on the pre-activations hl at layer l. In this case, it is important to have the pre-activations hl fall into the linear region of the nonlinear function φ. Precisely, mean-field theory assumes that for large-N limit, the empirical distribution of the pre-activations hl converges to a Gaussian with zero mean and variance ql, where the variance follows a recursion relation (Poole et al., 2016). Therefore, to achieve layerwise dynamical isometry, the idea becomes to find a fixed point q∗ such that hl ∼ N (0, q∗) for all l ∈ {1 . . .K}. Such a fixed point makes Dl = D for all layers, and therefore, the preactivations are placed in the linear region of the nonlinearity.2 Then, given the nonlinearity, one can find a rescaling such that (DWl)T (DWl) = (Wl)TWl/σ2w = I. The procedure for finding the rescaling σ2w for various nonlinearities are discussed in Pennington et al. (2017; 2018). Also, this easily extends to convolutional neural networks using the initialization method in Xiao et al. (2018).
2 Dynamical isometry can hold for antisymmetric sigmoidal activation functions (e.g., tanh) as shown in Pennington et al. (2017). A recent work by Tarnowski et al. (2019) have also shown that dynamical isometry is achievable irrespective of the activation function in ResNets.
We note that dynamical isometry is in fact a weaker condition than layerwise dynamical isometry. However, in practice, the initialization suggested in the existing works (Pennington et al., 2017; Xiao et al., 2018), i.e., orthogonal initialization for weight matrices in each layer with rescaling based on mean field theory, satisfy layerwise dynamical isometry, even though this term was not mentioned.
Now, recall from Section 3.1 that a network is pruned with a global threshold based on connection sensitivity, and from Section 3.2 that the connection sensitivity is the gradients scaled by the weights. This in turn implies that the connection sensitivity scores across layers are required to be of the same scale. To this end, we require the gradients to be faithful and the weights to be in the same scale for all the layers. Notice, this condition is trivially satisfied when the layerwise dynamical isometry is ensured, as each layer is initialized identically (i.e., orthogonal initialization) and the gradients are guaranteed to be faithful.
Finally, we verify the failure of pruning cases presented in Section 3.1 based on the signal propagation perspective. Specifically, we measure the singular value distribution of the input-output Jacobian (J0,K) for the 7-layer tanh MLP network, and the results are reported in Table 1. Note that while connection sensitivity based pruning is robust to moderate changes in the Jacobian singular values, it failed catastrophically when the condition number of the Jacobian is very large (> 1e+11). In fact, these failure cases correspond to the completely disconnected networks, as a consequence of pruning with unreliable connection sensitivity resulted from poorly conditioned initial Jacobians. As we will show subsequently, these findings extend to modern architectures, and layerwise dynamical isometry yields well-conditioned Jacobians and in turn the best pruning results.

heading: 4 SIGNAL PROPAGATION IN SPARSE NEURAL NETWORKS

text:
So far, we have shown empirically and theoretically that layerwise dynamical isometry can improve the process of pruning at initialization. One remaining question to address is the following: how well do signals propagate in the pruned sparse networks? In this section, we first examine the effect of sparsity on signal propagation after pruning. We find that indeed pruning can break dynamical isometry, degrading trainability of sparse networks. Then we follow up to present a simple, but effective data-free method to recover approximate dynamical isometry on sparse networks.
Setup. The overall process is summarized as follows: Step 1. Initialize a network with a variance scaling (VS) or layerwise dynamical isometry (LDI) satisfying orthogonal initialization. Step 2. Prune at initialization for a sparsity level κ̄ based on connection sensitivity (CS); we also test random (Rand) and magnitude (Mag) based pruning for comparison. Step 3. (optional) Enforce approximate dynamical isometry, if specified. Step 4. Train the pruned sparse network using SGD. We measure signal propagation (e.g., Jacobian singular values) on the sparse network right before Step 4, and observe training behavior during Step 4. Different methods are named as {A}-{B}-{C}, where A, B, C stand for initialization scheme, pruning method, (optional) approximate isometry, respectively. We perform this on 7-layer linear and tanh MLP networks as before 3.
3We conduct the same experiments for ReLU and Leaky-ReLU activation functions (see Appendix C).
Effect of pruning on signal propagation and trainability. Let us first check signal propagation measurements in the pruned networks (see Figure 2a). In general, Jacobian singular values decrease continuously as the sparsity level increases (except for {·}-{·}-AI which we will explain later), indicating that the more parameters are removed, the less faithful a network is likely to be with regard to propagating signals. Also, notice that the singular values drop more rapidly with random pruning compared to connection sensitivity based pruning methods (i.e., {·}-Rand vs. {·}-CS). This means that pruning using connection sensitivity is more robust to destruction of dynamical isometry and preserve better signal propagation in the sparse network than random pruning. We further note that, albeit marginal, layerwise dynamical isometry allows better signal propagation than variance scaling initialization, with relatively higher mean singular values and much lower standard deviations especially in the low sparsity regime (see Appendix C).
Now, we look into the relation between signal propagation and trainability of the sparse networks. Figure 2b shows training behavior of the pruned networks (κ̄ = 90%) obtained by different methods. We can see a clear correlation between signal propagation capability of a network and its training performance; i.e., the better a network propagates signals, the faster it converges during training. For instance, compare the trainability of a network before and after pruning. That is, compared to LDI-Dense (κ̄ = 0), LDI-{CS, Mag, Rand} decrease the loss much slowly; random pruning starts to decrease the loss around 4k iteration, and finally reaches to close to zero loss around 10k iterations (see Appendix C), which is more than an order of magnitude slower than a network pruned by connection sensitivity. Recall that the pruned networks have much smaller singular values.
Enforcing approximate dynamical isometry. The observation above indicates that the better signal propagation is ensured on sparse networks, the better their training performs. This motivates us to think of the following: what if we can repair the broken isometry, before we start training the pruned network, such that we can achieve trainability comparable to that of the dense network? Precisely, we consider the following:
min Wl ‖(Cl Wl)T (Cl Wl)− Il‖F , (8)
where Cl, Wl, Il are the sparse mask obtained by pruning, the corresponding weights, the identity matrix at layer l, respectively, and ‖ · ‖F is the Frobenius norm. We optimize this for all layers identically using gradient descent. Given the sparsity topology Cl and initial weights Wl, this datafree method attempts to find an optimal W∗ such that the combination of the sparse topology and the weights to be layerwise orthogonal, potentially to the full rank capacity. This simple method (i.e., {·}-{·}-AI, where AI is named for Approximate Isometry) turns out to be highly effective. The results are provided in Figure 2, and we summarize our key findings below:
• Signal propagation (LDI-{CS, Rand} vs. LDI-{CS, Rand}-AI). The decreased singular values (by pruning κ̄ > 0) bounce up dramatically and become close to the level before pruning. This means that orthogonality enforced by Equation 8 is achieved in the sparse topology of the pruned
network (i.e., approximate dynamical isometry), and therefore, signal propagation on the sparse network is likely to behave similarly to the dense network. As expected, the training performance increased significantly (e.g., compare LDI-CS with LDI-CS-AI for trainability). This works more dramatically for random pruning; i.e., even for randomly pruned sparse networks, training speed increases significantly, implying the benefit of ensuring signal propagation. • Structure (LDI-Rand-AI vs. LDI-CS-AI). Even if the approximate dynamical isometry is enforced identically, the network pruned using connection sensitivity shows better trainability than the randomly pruned network. This potentially means that the sparse topology obtained by different pruning methods also matters, in addition to signal propagation characteristics. • Overparameterization (LDI-Dense vs. LDI-{CS, Rand}-AI). Even though the singular values are restored to a level close to before pruning with approximate isometry, the non-pruned dense network converges faster than pruned networks. We hypothesize that in addition to signal propagation, overparameterization helps in optimization taking less time to find a minimum.
While being simple and data free (thus fast), our signal propagation perspective not only can be used to improve trainability of sparse neural networks, but also to complement a common explanation for decreased trainability of compressed networks which is often attributed merely to a reduced capacity. Our results also extend to the case of convolutional neural network (see Figure 8 in Appendix C).

heading: 5 VALIDATION AND EXTENSIONS

text: In this section, we aim to demonstrate the efficacy of our signal propagation perspective on a wide variety of settings. We first evaluate the idea of employing layerwise dynamical isometry on various modern neural networks. In addition, we further study the role of supervision under the pruning at initialization regime, extending it to unsupervised pruning. Our results show that indeed, pruning can be approached from the signal propagation perspective at varying scale, bringing forth the notion of neural architecture sculpting. The experiment settings used to generate the presented results are detailed in Appendix B. The code can be found here: https://github.com/namhoonlee/spp-public.

heading: 5.1 EVALUATION ON VARIOUS NEURAL NETWORKS AND DATASETS

text:
Here, we verify that our signal propagation perspective for pruning neural networks at initialization is indeed valid, by evaluating further on various modern neural networks and datasets. To this end, we provide orthogonality scores (OS) and generalization errors of the sparse networks obtained by different methods and show that layerwise dynamical isometry with enforced approximate isometry results in the best performance; here, we define OS as 1l ∑ l ‖(Cl Wl)T (Cl Wl)−Il‖F , which can be used to indicate how close are the weight matrices in each layer of the pruned network to being orthogonal. All results are the average of 5 runs, and we do not optimize anything specific for a particular case (see Appendix B for experiment settings). The results are presented in Table 2.
The best pruning results are achieved when the approximate dynamical isometry is enforced on the pruned sparse network (i.e., LDI-AI), across all tested architectures. Also, the second best results are achieved with the orthogonal initialization that satisfies layerwise dynamical isometry (i.e., LDI). Looking closely, it is evident that there exists a high correlation between the orthogonality scores and the performance of pruned networks; i.e., the network initialized to have the lowest orthogonality scores achieves the best generalization errors after training. Note that the orthogonality scores being close to 0, by definition, states how faithful a network will be with regard to letting signals propagate without being amplified or attenuated. Therefore, the fact that a pruned network with the lowest orthogonality scores tends to yield good generalization errors further validates that our signal propagation perspective is indeed effective for pruning at initialization. Moreover, we test for other nonlinear activation functions (tanh, leaky-relu, selu), and found that the orthogonal initialization consistently outperforms variance scaling methods (see Table 3).

heading: 5.2 PRUNING WITHOUT SUPERVISION

text:
So far, we have shown that pruning random networks can be approached from a signal propagation perspective by ensuring faithful connection sensitivity. Another factor that constitutes connection sensitivity is the loss term. At a glance, it is not obvious how informative the supervised loss measured on a random network will be for connection sensitivity. In this section, we look into the effect of supervision, by simply replacing the loss computed using ground-truth labels with different unsupervised surrogate losses as follows: replacing the target distribution using ground-truth labels with uniform distribution (Unif.), and using the averaged output prediction of the network (Pred.; softmax/raw). The results for MLP networks are in Table 4. Even though unsupervised pruning results are not as good as the supervised case, the results are still interesting, especially for the uniform case, in that there was no supervision given. We thus experiment further for the uniform case on other networks, and obtain the following results: 8.25, 11.69, 11.01, 8.82 errors (%) for VGG16, ResNet32, ResNet56, ResNet110, respectively. Surprisingly, the results are often competitive to that of pruning with supervision (i.e., compare to LDI results in Table 2). Notably, previous pruning algorithms assume the existence of supervision a priori. Being the first demonstration, along with the signal propagation perspective, this unsupervised pruning strategy can be useful in scenarios where there are no labels or only weak supervision is available.
To demonstrate further, we also conducted transfer of sparsity experiments such as transferring a pruned network from one task to another (MNIST ↔ Fashion-MNIST). Table 5 shows that, while pruning results may degrade if sparsity is transferred, or done without supervision, less impact is caused for unsupervised pruning when transferred to a different task (i.e., 0.52 to 0.14 on MNIST, and 1.11 to −0.78 on F-
MNIST). This indicates that inductive bias exists in data, affecting transfer and unsupervised pruning, and potentially, that “universal” sparse topology might be obtainable if universal data distribution is known (e.g., extremely large dataset in practice). This may help in situations where different tasks from unknown data distribution are to be performed (e.g., continual learning). We also tested two other unsupervised losses, but none performed as well as uniform loss (e.g., Jacobian norms ‖J‖1: 5.03, ‖J‖2: 3.00 vs. Unif.: 2.94), implying that if pruning is to be unsupervised, the uniform loss would better be used, because other unsupervised losses depend on the input data (thus can suffer from inductive bias). Random pruning degrades significantly at high sparsity for all cases.

heading: 5.3 NEURAL ARCHITECTURE SCULPTING

text:
We have shown that pruning at initialization, even when no supervision is provided, can be effective based on the signal propagation perspective. This begs the question of whether pruning needs to be limited to pre-shaped architectures or not. In other words, what if pruning is applied to an arbitrarily bulky network and is treated as sculpting an architecture? In order to find out, we conduct the following experiments: we take a popular pre-designed architecture (ResNet20 in He et al. (2016)) as a base network, and consider a range of variants that are originally bigger than the base model, but pruned to have the same number of parameters as the base dense network. Specifically, we consider the following equivalents: (1) the same number of residual blocks, but with larger widths; (2) a reduced number of residual blocks with larger widths; (3) a larger residual block and the same width (see Table 6 in Appendix B for details). The results are presented in Figure 3.
Overall, the sparse equivalents record lower errors than the dense base model. Notice that some models are extremely sparse (e.g., Equivalent 1 pruned for κ̄ = 98.4%). While all networks have the same number of parameters, discovered sparse equivalents outperform the dense reference network. This result is well aligned with recent findings in Kalchbrenner et al. (2018): large sparse networks can outperform their small dense counterpart, while enjoying increased computational and memory efficiency via a dedicated implementation for sparsity in practice. Also, it seems that pruning wider networks tends to be more effective in producing a better model than pruning deeper ones (e.g., Equivalent 1 vs. Equivalent 3). We further note that unlike existing prior works, the sparse networks are discovered by sculpting arbitrarily-designed architecture, without pretraining nor supervision.

heading: 6 DISCUSSION AND FUTURE WORK

text:
In this work, we have approached the problem of pruning neural networks at initialization from a signal propagation perspective. Based on observing the effect of varying the initialization, we found that initial weights have a critical impact on connection sensitivity measurements and hence pruning results. This led us to conduct theoretical analysis based on dynamical isometry and a mean field theory, and formally characterize a sufficient condition to ensure faithful signal propagation in a given network. Moreover, our analysis on compressed neural networks revealed that signal propagation characteristics of a sparse network highly correlates with its trainability, and also that pruning can break dynamical isometry ensured on a network at initialization, resulting in degradation of trainability of the compressed network. To address this, we introduced a simple, yet effective data-free method to recover the orthogonality and enhance trainability of the compressed network. Finally, throughout a range of validation and extension experiments, we verified that our signal propagation perspective is effective for understanding, improving, and extending the task of pruning at initialization across various settings. We believe that our results on the increased trainability of compressed networks can take us one step towards finding “winning lottery ticket” (i.e., a set of initial weights that given a sparse topology can quickly reach to a generalization performance that is comparable to the uncompressed network, once trained) suggested in Frankle & Carbin (2019).
We point out, however, that there remains several aspects to consider. While pruning on enforced isometry produces trainable sparse networks, the two-stage orthogonalization process (i.e., prune first and enforce the orthogonality later) can be suboptimal especially at a high sparsity level. Also, network weights change during training, which can affect signal propagation characteristics, and therefore, dynamical isometry may not continue to hold over the course of training. We hypothesize that a potential key to successful neural network compression is to address the complex interplay between optimization and signal propagation, and it might be immensely beneficial if an optimization naturally takes place in the space of isometry. We believe that our signal propagation perspective provides a means to formulate this as an optimization problem by maximizing the trainability of sparse networks while pruning, and we intend to explore this direction as a future work.

heading: ACKNOWLEDGMENTS

text: This work was supported by the ERC grant ERC-2012-AdG 321162-HELIOS, EPSRC grant Seebibyte EP/M013774/1, EPSRC/MURI grant EP/N019474/1 and the Australian Research Council Centre of Excellence for Robotic Vision (project number CE140100016). We would also like to acknowledge the Royal Academy of Engineering and FiveAI, and thank Richard Hartley, Puneet Dokania and Amartya Sanyal for helpful discussions.

heading: A GRADIENTS IN TERMS OF JACOBIANS

text:
Proposition 1. Let = ∂L/∂xK denote the error signal and x0 denote the input signal. Then,
1. the gradients satisfy: gTwl = J
l,KDl ⊗ xl−1 , (9) where Jl,K = ∂xK/∂xl is the Jacobian from layer l to the output and⊗ is the Kronecker product.
2. additionally, for linear networks, i.e., when φ is the identity:
gTwl = J l,K ⊗
( J0,l−1x0 + a ) , (10)
where J0,l−1 = ∂xl−1/∂x0 is the Jacobian from the input to layer l − 1 and a ∈ RN is the constant term that does not depend on x0.
Proof. The proof is based on a simple algebraic manipulation of the chain rule. The gradient of the loss with respect to the weight matrix Wl can be written as:
gwl = ∂L
∂Wl =
∂L ∂xK ∂xK ∂xl ∂xl ∂Wl . (11)
Here, the gradient ∂y/∂x is represented as a matrix of dimension y-size × x-size. For gradients with respect to matrices, their vectorized from is used. Notice,
∂xl ∂Wl = ∂xl ∂hl ∂hl ∂Wl = Dl ∂hl ∂Wl . (12)
Considering the feed-forward dynamics for a particular neuron i, hli = ∑ j W lijx l−1 j + b l i , (13)
∂hli ∂W lij = xl−1j .
Therefore, using the Kronecker product, we can compactly write:
∂xl
∂Wl = (Dl)T ⊗ (xl−1)T . (14)
Now, Equation 11 can be written as:
gwl = ( J l,KDl)T ⊗ (xl−1)T , (15) gTwl = J l,KDl ⊗ xl−1 .
Here, AT ⊗ BT = (A ⊗ B)T is used. Moreover, for linear networks Dl = I and xl = hl for all l ∈ {1 . . .K}. Therefore, xl−1 can be written as:
xl−1 = φ(Wl−1φ(Wl−2 . . . φ(W1x0 + b1) . . .+ bl−2) + bl−1) , (16)
= Wl−1(Wl−2 . . . (W1x0 + b1) . . .+ bl−2) + bl−1 ,
= l−1∏ k=1 Wkx0 + l−1∏ k=2 Wkb1 + . . .+ bl−1 , = J0,l−1x0 + a ,
where a is the constant term that does not depend on x0. Hence, the proof is complete.

heading: B EXPERIMENT SETTINGS

text:
Pruning at initialization. By default, we perform pruning at initialization based on connection sensitivity scores as in Lee et al. (2019). When computing connection sensitivity, we always use all examples in the training set to prevent stochasticity by a particular mini-batch. Unless stated otherwise, we set the default sparsity level to be κ̄ = 90% (i.e., 90% of the entire parameters in a network is pruned away). For all tested architectures, pruning for such level of sparsity does not lead to a large accuracy drop. Additionally, we perform either random pruning (at initialization) or a magnitude based pruning (at pretrained) for comparison purposes. Random pruning refers to pruning parameters randomly and globally for a given sparsity level. For the magnitude based pruning, we first train a model and simply prune parameters globally in a single-shot based on the magnitude of the pretrained parameters (i.e., keep the large weights while pruning small ones). For initialization methods, we follow either variance scaling initialization schemes (i.e., VS-L, VSG, VS-H, as in LeCun et al. (1998); Glorot & Bengio (2010); He et al. (2015), respectively) or (convolutional) orthogonal initialization schemes (Saxe et al., 2014; Xiao et al., 2018).
Training and evaluation. Throughout experiments, we evaluate pruning results on MNIST, CIFAR-10, and Tiny-ImageNet image classification tasks. For training of the pruned sparse networks, we use SGD with momentum and train up to 80k (for MNIST) or 100k (for CIFAR-10 and Tiny-ImageNet) iterations. The initial learning rate is set to be 0.1 and is decayed by 1/10 at every 20k (MNIST) or 25k (CIFAR-10 and Tiny-ImageNet). The mini-batch size is set to be 100, 128, 200 for MNIST, CIFAR-10, Tiny-ImageNet, respectively. We do not optimize anything specific for a particular case, and follow the standard training procedure. For all experiments, we use 10% of training set for the validation set, which corresponds to 5400, 5000, 9000 images for MNIST, CIFAR-10, Tiny-IamgeNet, respectively. We evaluate at every 1k iteration, and record the lowest test error. All results are the average of either 10 (for MNIST) or 5 (for CIFAR-10 and Tiny-ImageNet) runs.
Signal propagation and approximate dynamical isometry. We use the entire training set when computing Jacobian singular values of a network. In order to enforce approximate dynamical isometry when specified, given a pruned sparse network, we optimize for the objective in Equation 8 using gradient descent. The learning rate is set to be 0.1 and we perform 10k gradient update steps (although it usually reaches to convergence far before). This process is data-free and thus fast; e.g., depending on the size of the network and the number of update steps, it can take less than a few seconds on a modern computer.
Neural architecture sculpting. We provide the model details in Table 6.

heading: C SIGNAL PROPAGATION IN SPARSE NETWORKS: ADDITIONAL RESULTS

title: A SIGNAL PROPAGATION PERSPECTIVE FOR PRUNING NEURAL NETWORKS AT INITIALIZATION