summaries: This paper addresses an issue of compositionality in self-attention models such Transformer. A simple idea of composing multiple words into a phrase as a hypernode and representing it using a non-linear function to capture the semantic mutation is proposed. In the machine translation and PoS tagging tasks, the proposed PhraseTransformer achieves impressive gain, especially +13.7 BLEU score compared to the Transformer.

summaries: This submission proposes to consider to put attention on "phrases" in NLP. The phrases are generated by taking consecutive words in sentences. Each phrase is treated as a "node" in the same way as words. Then representations of phrases are learned in the network. The algorithm is applied to two applications, translation and pos tagging. The proposed method achieved better performance than transformer.

abstractText: How to represent the sentence “That’s the last straw for her”? The answer of the self-attention is a weighted sum of each individual words, i.e. semantics = α1Emb(That) + α2Emb(’s) + · · ·+ αnEmb(her) . But the weighted sum of “That’s”, “the”, “last”, “straw” can hardly represent the semantics of the phrase. We argue that the phrases play an important role in attention. If we combine some words into phrases, a more reasonable representation with compositions is semantics = α1Emb(That’s)+Emb2(the last straw)+α3Emb(for)+α4Emb(her) . While recent studies prefer to use the attention mechanism to represent the natural language, few noticed the word compositions. In this paper, we study the problem of representing such compositional attentions in phrases. In this paper, we proposed a new attention architecture called PhraseTransformer. Besides representing the words of the sentence, we introduce hypernodes to represent the candidate phrases in attention. PhraseTransformer has two phases. The first phase is used to attend over all word/phrase pairs, which is similar to the standard Transformer. The second phase is used to represent the inductive bias within each phrase. Specially, we incorporate the non-linear attention in the second phase. The non-linearity represents the the semantic mutations in phrases. The experimental performance has been greatly improved. In WMT16 English-German translation task, the BLEU increases from 20.90 (by Transformer) to 34.61 (by PhraseTransformer).

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

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

venue: In ICLR,

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

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

authors:
Tsu-Jui Fu
Peng-Hsuan Li
Wei-Yun Ma

title: Graphrel: Modeling text as relational graphs for joint entity and relation extraction

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

authors:
Qipeng Guo
Xipeng Qiu
Pengfei Liu
Yunfan Shao
Xiangyang Xue
Zheng Zhang

title: Startransformer. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)

authors:
Matthew Honnibal
Ines Montani

title: spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov

title: Roberta: A robustly optimized BERT pretraining approach

authors:
Mitchell Marcus
Beatrice Santorini
Mary Ann Marcinkiewicz

title: Building a large annotated corpus of english: The penn treebank

authors:
Alec Radford
Jeff Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

authors:
Emma Strubell
Patrick Verga
Daniel Andor
David Weiss
Andrew McCallum

title: Linguisticallyinformed self-attention for semantic role labeling

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

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

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
Alex Wang
Amanpreet Singh
Julian Michael
Felix Hill
Omer Levy
Samuel R Bowman

title: Glue: A multi-task benchmark and analysis platform for natural language understanding

venue: EMNLP 2018,

heading: 1 INTRODUCTION

text:
The word-to-word attention (Bahdanau et al., 2015; Vaswani et al., 2017) updates the state of a word by the weighted sum of the current states of the words. The weights depend on the attention scores. Such mechanism incurs two major problems. Firstly, it is unfeasible to incorporate the semantics of phrases in the attention. For example, in figure 1a and figure 1b, using the attention over phrase “the last straw” is more intuitive than using the attention over the three individual words. However, such word composition (i.e. “the last straw”) cannot be represented atomically by word level attentions. Secondly, the literal meaning of each individual words can be quite different from the implied meaning of the phrase. The weighted sum in attention cannot capture the semantic mutation. For example, it’s hard to represent the semantics of the unpleasantness, the struggling, and being unable to continue by the weighted sum of individual words “the”, “last”, and “straw”. Deepening the attention layers as in Devlin et al. (2019); Liu et al. (2019) cannot solve these issues.
Instead of representing the natural language via word-to-word attentions, incorporating phrase as atoms in the attention provides a more intuitive representation. In figure 1b, if we regard “the last straw” as an atom node in the attention in figure 1b, it is much more intuitive to represent the semantics.
For multiple words that form semantic compositions (e.g. idioms, chunkings, phrases), their semantics should be computed uniformly as an atom in the attention mechanism. The traditional word level attention mechanism should be expanded to represent the attentions over such compositions. To this end, we make a very simple framework called PhraseTransformer, based on Transformer. We leverage the concept of hypernodes in hypergraph. The traditional Transformer only consists of
That’s the last straw for her.
semantics = α1Emb(That’s) + α2Emb(the) + · · ·+ αnEmb(her)
(a) Word level self-attention
That’s the last straw for her.
semantics = α1Emb(That’s) + α2Emb(the last straw) + α2Emb(for) + αnEmb(her)
(b) Attention over adjacent phrases.
Representation learning is not only popular but also important.
semantics =α1Emb(Representation learning) + α2Emb(is) + α3Emb(not only ... but also) + α3Emb(hot) + α4Emb(important)
(c) Attention over nonadjacent phrases.
nodes representing single words. From the perspective of graph, Transformer is a complete bipartite graph, that the information transfers through all node pairs according to their attention scores. In hypergraph, a hypernode consists of one or more nodes. Likewise, we use such hypernodes in PhraseTransformer to represent the semantics of the composition. Each hypernode represents multiple words in a composition.
The information propagation in PhraseTransformer has two stages: the propagation across arbitrary node pairs and the propagation within a hypernode.
Attention of arbitrary node pairs works similar to the classical Transformer. We compute the attention scores for all nodes and all hypernodes. The information propagates accordingly. We use hypernodes to represent the atomic information propagation of semantic compositions in attentions.
Non-linear attention within each phrase reflects the inductive bias of the phrases. The nodes within a phrase should be updated by each other via attention. For example, the states of the hypernode the last straw should be updated by the node of the, last, straw etc. And the states of node straw should also be updated by the node of the last straw. To do this, we limit the attention in Transformer to nodes within each phrase.
Compared to the attention of arbitrary node pairs, a significant difference of the attention within each phrase is that we incorporate nonlinearity. As suggested in figure 1a, the literal meaning of each individual words can be quite different from the implied meaning of the phrase. We use the non-linearity to represent the semantic mutations of phrases.
Our proposed PhraseTransformer is able to capture any multi-word compositions. In this paper, we mainly study one of the simplest form of phrase: a sequence of adjacent words. For detecting phrases with adjacent words, we do not utilize existing identification algorithms (e.g. chunking). We roughly added all sequences of words in the sentence whose length is less than a given threshold. The attention mechanism itself decides the weights of these candidate phrases by assigning them different attention scores during the inference.
We summarize the contributions of this paper below:
• We propose to represent semantic compositions in the attention mechanism. We show that such representation is more intuitive than the traditional word-to-word attention.
• We incorporate the hypernodes in Transformer as PhraseTransformer. The semantics of a composition can be computed atomically via cross-node attentions. The inductive bias is reflected by the information propagation within each hypernode.
• We evaluate our approach over two widely used types of semantic compositions, i.e., chunking and semantic dependency. We conduct extensive experiments to verify the effectiveness of our proposed approaches.

heading: 2 MODEL

heading: 2.1 ARCHITECTURE

text:
In this subsection, we show how the PhraseTransformer works on an abstract level. In the attention, we use “simple node” and “hypernode” to denote nodes that correspond to a single word and a phrase, respectively. We denote both the simple nodes and hypernodes as nodes. The PhraseTransformer contains n simple nodes, where n is the length of the sentence, and m hypernodes representing m phrases. For each node s, we denote the words it corresponds to as word(s). For simple nodes, |word(s)| = 1. For hypernodes, |word(s)| > 1. For example, in figure 2, “straw” is represented by a single node s1. word(s1) = (straw). The phrase “the last straw” is represented by a hypernode s2, word(s2) = (the, last, straw).
The attention in PhraseTransformer has two phases. The first phase uses the node-to-node attention over all node pairs. This is represented by the blue edges in figure 2. For example, the state of the placeholder [CLS] will be updated according to its attention scores to nodes of “That’s”, “for”, “the last straw”, etc. Similarly, the states of a hypernode (e.g. “the last straw”) will be updated according to its attention scores to all nodes (e.g. “That’s”, “for”, “last straw”).
The second phase uses limited attention mechanism to update the states within each phrase. In figure 2, the orange edges show the attention within the phrase “the last straw”. The state of s2 will be updated according to its attention scores to “the”, “last”, “straw”, but will not be updated by “for” or “her”. And the state of s1 will also be updated by s2.

heading: 2.2 PHRASE GENERATION

text:
As mentioned in the introduction section, a hypernode represents a phrase formed by multiple words. In this paper, we consider the phrases formed by adjacent words in the original sentences. For a given length threshold k and a word sequence w1, · · · , wn, we generate hypernodes that consists of adjacent word sequence whose length is less than or equal to k. More specifically, we generate all hypernode s such that
word(s) = (wi, wi+1, · · ·wj), s.t. j − i < k (1)
Our proposed neural network is feasible for any phrase generation strategies. We also compare with other the phrase generation w.r.t. the dependency parsing trees. The details of such strategy are shown in section 4.3.

heading: 2.3 MUTLI-HEAD ATTENTION OVER ALL NODE PAIRS

text:
The attention over all node pairs in the first phase works similar to the standard Transformer (Vaswani et al., 2017). Given a sequence of vectors H ∈ Rn+m, where m is the number of hypernodes, we compute the attention of all nodes by:
Attn(Q,K, V ) = softmax( QKᵀ√ d )V (2)
, where Q = HWQ, K = HWK , V = HWV , and WQ, WK , WV are trainable parameters. By following Transformer (Vaswani et al., 2017), we use multi-head attention to jointly attend to different representation subspaces:
MultiHead(H) = Concat(head1, · · · , headh)WO (3) , where headi = Attn(HW Q i , HW K i , HW V i ), h is the number of heads.

heading: 2.4 NON-LINEAR ATTENTION WITHIN EACH PHRASE

text:
The attention within each phrase captures the inductive bias of the phrase. For example, we use the semantics of “representation”, “learning” to update the semantics of phrase “representation learning”, and vice versa. We consider two nodes have an edge between them if the words of one node is the subset of the words of another node. More specific, for two nodes s1, s2, we consider their attention within a phrase iff
word(s1) ⊆ word(s2) or word(s2) ⊆Word(s1) (4) . Given a sequence of vectors H ∈ Rn+m, the attention within phrases are computed by:
Attn′(Q,K, V ) = σ(softmax( QKᵀ√ d ◦A)V ) (5)
where Q = HWQ ′ , K = HWK ′ , V = HWV ′ , ◦ denotes the Hadamard product, A ∈ [0, 1](n+m)×(n+m) denotes the adjacency of the nodes:
Ai,j = { 1 if word(s1) ⊆ word(s2) or word(s2) ⊆ word(s1) 0 otherwise.
(6)
Note that we use an active function σ in Attn′(Q,K, V ), which is not used in the standard Transformer. We found that the literal meaning of each individual words can be quite different from the implied meaning of the phrase. For example, in figure 1a, the semantics of “the last straw” is not a simple combination of the semantics of “the”, “last”, “straw”. So using a weighted sum of the three words to represent the phrase cannot precisely represent its semantics. We use the non-linearity to represent the semantic mutation. In this paper, we use the sigmoid function as σ.
We also use multi-head attention in the attention within phrases to jointly attend to different representation subspaces::
MultiHead′(H,A) = Concat(head′1, · · · , head′h)WO (7) where head′i = Attn ′(QWQ ′ i ,KW K′ i , V W V ′ i ).

heading: 2.5 ALGORITHM

text:
The overall update algorithm of a k-layer PhraseTransformer is shown in Algorithm 1. We are given the initial states of the words H ∈ Rn×d. We first generate m phrases and the adjacent matrix A. We extend the states of nodes to H ∈ R(n+m)×d by padding m × d zeros. Then we iteratively perform the attention over all node pairs and the attention within phrases k times. The output is the states of the first n nodes, which correspond to the original words of the sentence.
Complexity analysis The standard Transformer considers the attention over n nodes. Thus its complexity is O(n2d). Similarly, the first phase of PhraseTransformer (i.e. attention over all node pairs) is O((n + m)2d), since it consider the attention over all n + m nodes. The second phase of PhraseTransformer (i.e. attention within phrases) considers attentions within each phrase. Since the attention within phrases is sparse than attention over all nodes, overall complexity is O((n + m)2d) = O(k2n2d). Such complexity is acceptable when k is small. In the experiments, we set k = 2 or 3.
Algorithm 1: The update algorithm of PhraseTransformer
Data: H ,n; //Generate the hypernodes and init the states to zeros;
1 Generate m hypernodes and A; 2 H0 ←Pad m× d zeros to H; 3 for i = 1...k do //Attention over all node pairs; 4 Hi ←MultiHead(Hi−1); //Attention within phrases; 5 Hi ←MultiHead′(Hi, A); 6 return Hk[: n, :]

heading: 3 RELATED WORK

text:
Attention-based Natural Language Representation There is a trend to use attention and selfattention Bahdanau et al. (2015); Vaswani et al. (2017) for modeling the natural language. Attention is able to jointly model the semantics of the words and their alignments Bahdanau et al. (2015) or compositions Vaswani et al. (2017). It captures compositions of all word pairs, which is superior to traditional sequential representation (e.g. LSTM) in many tasks Wang et al. (2018). However, previous attention mechanisms work over the word level. They are infeasible to capture the semantics of phrases, especially if the semantics of the phrase is different from the literal semantics of its words. Instead, our proposed PhraseTransformer solves such issue by introducing hypernodes to represent phrases in the attention.
Attention-based pre-training language models achieve state-of-the-art results in many NLP tasks. BERT Devlin et al. (2019), GPT-2 Radford et al. (2019), Roberta Liu et al. (2019) use multi-layer Transformers as the major network structure. We believe that our proposed PhraseTransformer is a good alternative of Transformer for pre-training models, because using phrase-based knowledge is more intuitive than the word-based knowledge. On the hand, as PhraseTransformer has more trainable parameters than Transformer, the large amount of training data in pre-training guarantees these parameters can be trained sufficiently.
Incorporating Inductive Bias in Natural Language Representation is another trend in NLP. These inductive bias are usually from semantic dependencies Strubell et al. (2018); Zhang et al. (2018); Fu et al. (2019) or other external knowledge. LISA Strubell et al. (2018) introduce the dependency parsing as inductive bias to Transformer. It only allows the information transfer through edges of the parsing tree. C-GCN Zhang et al. (2018) and GraphRel Fu et al. (2019) uses graph convolution networks, in which the edges are from the dependency tree, to represent such inductive bias. These approaches all relies on a good algorithm (e.g. dependency parsing) for the given domain. This is usually unsatisfied for different languages and different domains. In contrast, our approach do not rely such knowledge to represent the compositions.

heading: 4 EXPERIMENTS

text: In this section, we evaluate our proposed approaches over two classical NLP tasks: machine translation and POS tagging. All the experiments run over a computer with Intel Core i7 4.0GHz CPU, 96GB RAM, and a GeForce GTX 2080 Ti GPU.

heading: 4.1 MACHINE TRANSLATION

text:
Hyper-parameters We set the dimension of hidden states as 512, the number of heads as 8, and the dimension of each head as 64. We set the number of layers to 6.
Dataset We use the WMT’16 multimodal translation: Multi30k (de-en), which consists of 29k samples for training, 10k samples for development, and 1k samples for testing.
Neural network details: Each layer of the Transformer has two self-attention modules: one for the encoder, and one for the decoder. We apply the PhraseTransformer to the self attention module in the encoder layer.
The results of our proposed approaches are shown in table 1. The PhraseTransformer outperforms Transformer by a large margin. This shows that the intuition of representing natural language via phrases works.
Effectiveness of the non-linearity We want to figure out what make the PhraseTransformer works so well. Note that PhraseTransformer uses an non-linear function in the attention within phrases. We further verify the effectiveness of such non-linearity by using a linear competitor, which is denoted as linear PhraseTransformer. It works the same as PhraseTransformer, except that it does not use the activate function in equation equation 5. We report the results of the linear PhraseTransformer in table 2.
The comparison clearly suggests that most improvement of the PhraseTransformer is obtained from the non-linear activation. This is intuitive because we want to use the non-linearity to represent the semantic mutation in phrases.

heading: 4.2 VISUALIZATION OF PHRASETRANSFORMER

text: We visualize the attention matrix of PhraseTransformer in the self-attention module for WMT’16 multimodal translation in figure 3. We analyze the attention over these phrases. As can be seen, the attention is over the single nodes and the hypernodes. This verifies that the PhraseTransformer successfully use phrases as atoms in attention. For example, in figure 3a, we can see that the phrase “a building” has a higher attention score than other phrases. This makes sense because the two words form a valid phrase. In the attention matrix for attention within phrases in figure 3b, we found that the word “on” attends to the phrase “working on”. This is intuitive because the work “on” itself does not have a clear semantics. It needs the collocation with “working” to represent its semantics.

heading: 4.3 POS TAGGING

text:
Hyper-parameters We follow the parameters in Guo et al. (2019). We set the dimension of hidden states as 300, the number of heads as 6, and the dimension of each head as 50. We set the number of layers to 2.
Dataset We use the POS tagging dataset from Penn Treebank (PTB) Marcus et al. (1993), which consists of 38k samples for training, 5k samples for development, and 5k samples for testing.
Competitor with semantic inductive bias Noticing that the semantic dependency is also a possible inductive bias (Strubell et al., 2018; Zhang et al., 2018), we also compare with PhraseTransformer with dependency parsing trees. We denote it as semantic PhraseTransformer. Each hypernode in it represents an edge in the dependency parsing tree. In this way, the non-adjacent words can form one phrase. For example, it is possible to represent the phrase “not only ... but also” in figure 1c. More formally, in semantic PhraseTransformer, we generate hypernode s such that
word(s) = (wi, wj) s.t. edge (wi, wj) is in the dependency parsing tree (8)
. In this paper, we use spaCy (Honnibal & Montani, 2017) for dependency parsing. The two phases in the semantic PhraseTransformer works the same as in PhraseTransformer.
The results are shown in table 2. The PhraseTransformer outperforms Transformer and semantic PhraseTransformer. Note that semantic PhraseTransformer uses external data to incorporate inductive bias. This verifies we incorporate simple but suitable inductive bias, i.e., the phrases.

heading: 5 CONCLUSION

text:
We noticed that representing phrase as the atoms in attention is more intuitive than the word-to-word attention. Wee proposed the PhraseTransformer, which incorporates the hypernodes in Transformer. Each hypernode represents a possible phrase in the sentence. Without using extra phrase identifi-
cation algorithms, we jointly detect the phrases and attend over them. Our proposed PhraseTransformer has two phases. The first phase achieves phrase level attentions like the word level attention. The second phrase represents the inductive bias between words and phrases. The experiments show a significant improvement in the machine translation task.


summaries: This paper proposes a novel modular neural architecture for algorithm induction. The modules are fixed and a controller policy is learned which outputs a distribution over modules and input/output locations on a memory tape. An oracle (which knows the correct answer) is necessary to decide when to stop computing. The controller is trained by a variant of REINFORCE.

summaries: This paper proposes Modular Algorithm Induction Network (MAIN) that learns algorithms given input-output examples. MAIN is equipped with several components that make it perform better than baselines, but probably the most important part is its use of modules to break-down algorithmic tasks into simpler problems. MAIN is learned end-to-end using reinforcement learning and demonstrated to perform well in several tasks.

abstractText: We present a modular neural network architecture MAIN that learns algorithms given a set of input-output examples. MAIN consists of a neural controller that interacts with a variable-length input tape and learns to compose modules together with their corresponding argument choices. Unlike previous approaches, MAIN uses a general domain-agnostic mechanism for selection of modules and their arguments. It uses a general input tape layout together with a parallel history tape to indicate most recently used locations. Finally, it uses a memoryless controller with a length-invariant self-attention based input tape encoding to allow for random access to tape locations. The MAIN architecture is trained end-to-end using reinforcement learning from a set of input-output examples. We evaluate MAIN on five algorithmic tasks and show that it can learn policies that generalizes perfectly to inputs of much longer lengths than the ones used for training.

authors:
Jacob Andreas
Marcus Rohrbach
Trevor Darrell
Dan Klein

title: Neural module networks

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Matej Balog
Alexander L. Gaunt
Marc Brockschmidt
Sebastian Nowozin
Daniel Tarlow

title: Deepcoder: Learning to write programs

venue: In 5th International Conference on Learning Representations,

authors:
Rudy Bunel
Matthew J. Hausknecht
Jacob Devlin
Rishabh Singh
Pushmeet Kohli

title: Leveraging grammar and reinforcement learning for neural program synthesis

venue: In 6th International Conference on Learning Representations,

authors:
Michael Chang
Abhishek Gupta
Sergey Levine
Thomas L. Griffiths

title: Automatically composing representation transformations as a means for generalization

authors:
Xinyun Chen
Chang Liu
Dawn Song

title: Execution-guided neural program synthesis

venue: In 7th International Conference on Learning Representations,

authors:
Jacob Devlin
Jonathan Uesato
Surya Bhupatiraju
Rishabh Singh
Abdel-rahman Mohamed
Pushmeet Kohli

title: Robustfill: Neural program learning under noisy I/O

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
Lukasz Kaiser
Ilya Sutskever

title: Neural gpus learn algorithms

venue: In 4th International Conference on Learning Representations,

authors:
Louis Kirsch
Julius Kunze
David Barber

title: Modular networks: Learning to decompose neural computation

venue: In NeurIPS,

authors:
Karol Kurach
Marcin Andrychowicz
Ilya Sutskever

title: Neural random-access machines

authors:
Clemens Rosenbaum
Tim Klinger
Matthew Riemer

title: Routing networks: Adaptive selection of non-linear functions for multi-task learning

authors:
Lazar Valkov
Dipak Chaudhari
Akash Srivastava
Charles Sutton
Swarat Chaudhuri

title: Under review as a conference paper at ICLR

venue: Synthesis

authors:
2018. Wojciech Zaremba
Tomas Mikolov
Armand Joulin
Rob Fergus

title: Learning simple algorithms

heading: 1 INTRODUCTION

text:
Many applications in artificial intelligence require the ability to learn and perform tasks that have algorithmic structure, such as learning a sequence of precise actions together with conditional decisions and branching. Therefore, an important research problem is learning to induce algorithms from input-output examples. A particular focus of research attention has been on neural algorithm induction, which are neural architectures for representing algorithms by including unbounded intermediate state and mechanisms for learning control flow. The neural Turing machine (Graves et al., 2014) and its successor the Differentiable Neural Computer (Graves et al., 2016) augment a recurrent network with an external memory using differentiable read/write mechanisms, and are able to learn simple algorithmic tasks such as array copying and sorting. Neural Random-Access Machines (NRAM) (Kurach et al., 2016) learn algorithms by generating a fuzzy circuit comprising of pre-defined modules together with modules for dereferencing and storing values in a fixed memory.
Existing architectures do not fully leverage a key fact that algorithmic tasks can be solved by flexibly combining the results of smaller, reusable procedures, which we call modules. A modular architecture aims to represent in a learning system these aspects of programming languages intended for human developers: (i) procedural abstractions that perform computations to produce outputs given some inputs and that can be reused in the algorithm multiple times; (ii) control flow constructs such as branching and loops to compose and combine intermediate results. Although there has been a recent movement toward modular neural architectures for supervised tasks (Andreas et al., 2016; Kirsch et al., 2018; Rosenbaum et al., 2018; Valkov et al., 2018; Chang et al., 2018), the design space of modular networks has not been fully explored for algorithm induction.
Towards this end, we present a new architecture MAIN (short for Modular Algorithm Induction Network) for neural algorithm induction. Our architecture consists of a neural controller that interacts with a variable-length read/write tape where inputs, outputs, and intermediate values are stored. Each module is a small computational procedure that reads from and writes to a small fixed number of tape cells (a given fixed set of modules are specified in advance). At each time step, the controller selects a module to use together with the tape location of the module’s input arguments and the write location of the module output. This architecture is trained end-to-end using reinforcement learning.
A comparison of architectural design choices in MAIN with those in recent neural program induction approaches NTM (Graves et al., 2014), LSA (Zaremba et al., 2016), NRAM (Kurach et al., 2016), NGPU (Kaiser & Sutskever, 2016), CRL (Chang et al., 2018), and DNC (Graves et al., 2016) is presented in Table 1. Unlike previous architectures, MAIN allows for learning to compose modules
together with the corresponding argument values for the chosen modules using a general domainagnostic mechanism for module and argument choices. It uses a generic linear tape layout together with a parallel history tape of landmark symbols that indicate the most recently read and written cells. Finally, the architecture allows for random access of the memory cells and uses a memoryless controller with a length-invariant self-attention based encoding of input tape contents.
There are two key design choices in MAIN that we found crucial for good performance. The first is in the representation of the previous history of the computation. Like previous work (Graves et al., 2016), we find that providing history to the model is an important source of information. We introduce a simple but effective discrete representation, introducing a parallel history tape of landmark symbols that indicate the most recently read and written cells. This helps the model to learn common patterns of control flow, such as maps and reduce operations over the tape. The second choice is in the encoder architecture of the abstracted tape view with the controller. We find that using an attention-based encoder performs much better than a recurrent network based encoding within the controller, which has been employed by previous architectures for neural algorithm induction.
We evaluate our architecture MAIN on five algorithmic tasks including array copying, reversing, increment, filter-even, and multi-digit add. MAIN can learn these tasks in an end-to-end manner using input-output examples and is also able to generalize to longer input lengths. We observe that both parallel tape history and length-invariant input tape encoding based on self-attention are necessary for the architecture to learn these tasks. Moreover, for tasks such as filter-even and multidigit add that require the controller to perform some computations, we observe that abstracting the tape contents to only certain landmark positions can help it learn the corresponding algorithms.

heading: 2 RELATED WORK

text:
Learning to Compose and Modular Networks: Compositional Recursive Learner (CRL) (Chang et al., 2018) is a framework for learning algorithmic procedures for composing representation transformations, where both the transformations and their compositions are simultaneously learnt from a sparse supervision. The controller that learns to compose transformation is trained using reinforcement learning, whereas the transformations themselves are trained using supervised learning. The CRL architecture supports two forms of transformations: reducers and translators. Because of specialized transformations, CRL imposes a restriction on always selecting either full tape or three consecutive input tokens as arguments (that result in 1 resulting token) for the transformations. In contrast, our architecture allows the controller to select arbitrary locations on the input tape to select as module arguments and also the write locations for their outputs.
There has also been some recent related work on learning Modular Networks (Kirsch et al., 2018) and Routing Networks (Rosenbaum et al., 2018). In routing networks, a router learns to select a sequence of function blocks to compose given an input, and is trained using reinforcement learning. Kirsch et al. (2018) use a probabilistic model to represent the module choice as a latent variable and use Expectation Maximization (EM) to learn the module parameters and the decomposition choice in an end-to-end manner by maximizing a variational lower bound of the likelihood. Both of these approaches learn modular composition of functions with the aim of reusability and better generalization across multiple tasks. Our architecture, in contrast, is designed for learning algorithms where the modules are pre-specified but the task of the controller agent is to learn to compose those modules to achieve desired input-output behavior.
Neural Program Induction and Synthesis: Several neural architectures have been proposed recently to learn algorithmic tasks. Neural Turing Machine (NTM) (Graves et al., 2014) extends an LSTM controller with an external memory together with differentiable read-write mechanism. Differentiable Neural Computer (DNC) (Graves et al., 2016), a successor to NTM, added capabilities of freeing up unused memory for processing long sequences and a temporal link matrix for better tracking the write order. Zaremba et al. (2016) propose an architecture with an RNN controller that learns to navigate a structured input grid by selecting move actions and outputs tokens on an output grid. Unlike our architecture, which separates control from compute, these architectures require the controller to learn both the control structure as well as the desired computations.
Neural RAM (NRAM) (Kurach et al., 2016) uses a neural controller that learns to produce a fuzzy circuit consisting of a fixed number of modules. The controller learns to wire the modules with inputs coming from a fixed set of registers or intermediate outputs, and also learns to write output back to registers and memory tape. There are three key differences between Neural RAM and our architecture. First, NRAM uses a fixed sequence of 14 modules (with an option to repeat the whole sequence multiple times). In contrast, our controller learns to select appropriate module at each time step. Second, since registers and memory tape in NRAM architecture store distributions over integers, the modules also need to be differentiable to compute output over such inputs. Our architecture, on the other hand, does not require the modules to be differentiable and also writes discrete values on the input tape. Finally, our architecture uses a parallel history tape of recent read and write positions for accessing the input tape unlike pointer dereferencing in NRAM.
We summarize the characteristics of these architectures, comparing them to our work in Table 1. To understand the rows of this table, “Modules” means whether computation is performed by composable modules. “General module selection” means the modules can be selected in any order at any point in the computation (NRAM enforces a fixed ordering). “General argument selection” means module arguments can come from anywhere in memory without restriction (CRL enforces inputs be locally adjacent). “Read/write history” means that history of previous read and write locations is provided as context to the controller. “Random access” means the architecture can look up arbitrary memory contents and agregate information across memory regions, rather than be restricted by relative head movements (LSA). “Memoryless controller” means the architecture does not require the controller to have hidden memory over time, i.e. the controller is not recurrent, and only uses external memory for context. Finally, the “Encoder type” indicates how memory is consumed by the controller, feed-forward (FF), convolutional (CNN), recurrent (RNN), or attention-based (Attn).
There is also a growing interest in using neural models to generate symbolic programs as output. RobustFill (Devlin et al., 2017) trains an attention based encoder-decoder model that generates a program given a set of input-output examples. Deepcoder (Balog et al., 2017) learns a probability distribution over a set of functions in a DSL to guide an enumerative search. Chen et al. (2019) also use an encoder-decoder based approach to synthesize Karel programs (Bunel et al., 2018), but in addition also execute the partially decoded program to guide the decoder. In contrast, our architecture uses a more general mechanism to read and write on the variable length input tape, and uses reinforcement learning to learn to compose the desired modules for each individual task.
3 ARCHITECTURE
We describe MAIN, an architecture which can express arbitrary modular Turing machines. Our architecture has three parts: the memory which stores the state of the computation, the modules which update the tape, and the controller which chooses a module Mi to execute at each stage of the computation as illustrated in Figures 3. Once Mi is selected out of the module set (4 modules depicted), and the read/write locations on the tape are chosen, the module sees only the read inputs, and modifies the tape only at the write position. Each module is a user provided function (which could in principle also be learned). In our experiments we picked modules of two arguments and one output, but our architecture is agnostic to the number of read/write heads as shown in Figure 1.
The memory is a finite tape of discrete tokens/symbols. Formally, let s0, s1, . . . , sT be memory states at each computation step t = 0, . . . , T . Each st is itself an array of tokens, indexed as st[0], . . . , st[L − 1]. At the start of the computation, s0 is initialized with the program input, and necessary empty space to perform intermediate computation and write the output. The memory length L is dynamically set based on the size of the given input, so every neural architecture component that depends on L needs to be length invariant.
The memory contains landmark tokens, which are are task-specific tokens, e.g. ‘$’, ‘+’, ‘&’, that provide positional information. For example, these tokens indicate where the input starts, where the output should be written, etc. In our experiments we found that the controller would often overwrite the landmark tokens during training. As a workaround, we provide the positions of landmark tokens as immutable metadata. These are the lambdas λ(1), λ(2), . . . inside σt shown above. Additionally, we place Start-Of-Tape and End-Of-Tape landmarks at the first and last tape positions.
The initial tape s0 contains the input and additional space for scratch work. At the end, the output of computation will be read from designated regions of the tape, called target locations, which are initialized with the empty token ‘.’. Note that the architecture is free to overwrite any position during the course of computation, including important input tokens. When scoring the final tape sT , we only look at designated target positions, designated by the ‘.’ token. The initial tape configurations for Copy and Multi-digit Add Tasks is shown in Figure 2. The tape configuration in addition to the input tape also consists of landmark positions as well as the read/write heads history.
The modules M = {m1, . . . ,mk} are functions that read a narrow portion of the memory, and compute new values that are stored in memory. Each module mi is a function of R arguments, and outputs a vector of size W , i.e. number of read/write heads corresponds to the number of inputs and outputs of the modules. During the computation, each input and output of the modules will be a single cell on the memory tape. Some example modules are the maximum module which returns the maximum of two inputs, and the sum module which returns the sum of two inputs mod base B.
The controller is a policy over actions that specifies a module-tape interaction. The controller cannot directly modify memory. Instead it selects a module and the locations on the tape the module will read from and write to. Specifically, the controller defines a distribution π(H(r,1), . . . ,H(r,R), H(w,1), . . . ,H(w,W ),M | ct), where H(...) are random variables over tape positions (support is {0, . . . , L − 1}); one for each head. The variables H(r,1), . . . ,H(r,R) select read-head locations, and H(w,1), . . . ,H(w,W ) select write-head locations. The random variable M is one of the modules. Finally ct is the context, which contains the current state of memory and information about the computation history. We will define this in more detail shortly.
The controller defines an end-to-end computation as follows. At each step t of the computation, let the current state of the memory by st. To choose the next module and the locations of the read and write heads, we sample from the controller. This produces a module choice mt, and locations h (r,1) t , . . . , h (r,R) t for the read heads, and h (w,1) t , . . . , h (w,W ) t for the write heads. Because the controller is free to choose any tape location for each read and write head independently, the memory is random access. The tape is updated by calling the module mt, with the tape contents under the read heads as input, and then writing to the position specified by the write heads. More formally,
st+1[h (w,j) t ] := m(st[h (r,1) t ], . . . , st[h (r,R) t ])[j] ∀ j ∈ {1, . . . ,W}
st+1[i] := st[i] ∀ i /∈ {h(w,1)t , . . . , h (w,W ) t } .
The selected write indices are updated with module’s output, and other tape elements are unchanged.
The context ct is the input to the controller, which represents both the current tape contents st and an action history that represents information about the previous computation. The action history consists of two parts:
• Fixed-size part: Contains the module choice and head locations chosen at the previous time step. – Module choice: mt−1 – Tape values underneath heads: st[h (r,1) t−1 ], . . . , st[h (r,R) t−1 ], st[h (w,1) t−1 ], . . . , st[h (w,W ) t−1 ].
• Variable-size part: One-hot encoding of {h(...)t−1}, the read and write head locations at the previous step of the computation.
The tape values underneath the heads are technically redundant information, because the controller can use st combined with the head locations from the variable-sized part to lookup the corresponding tape values. However, we found that the controller had a hard time doing this in our experiments, and providing the head values as auxiliary input to the controller proved helpful.
Formally, the context is a tuple ct = (ξt, σt), where ξt is a fixed sized encoding (does not depend on the tape length L), and σt is a variable sized encoding (depends on the tape length L). First, ξt describes the current tape values underneath the tape heads chosen at the previous time step:
ξt = 〈st[h(r,1)t−1 ], . . . , st[h (r,R) t−1 ], st[h (w,1) t−1 ], . . . , st[h (w,W ) t−1 ],mt−1〉 .
where mt−1 is the previous module choice. Second, the variable sized encoding σ is a matrix concatenation that provides complete information about st:
σt =  1V {st[0]} 1V {st[1]} . . . 1V {st[L− 1]} 1L{λ(1)} 1L{λ(2)} ... 1L{h(r,1)t−1 } ...
1L{h(w,1)t−1 } ...
 .
We can think of σt as a stack of binary channels, each a row-vector of lengthL. The one-hot function 1D{d} produces a vector of length D which is filled with 0s, and 1 at position d. Each 1V {st[`]} is a one-hot vector of token st[`]. Their horizontal concatenation produces a channel for each token (indicates its presence or absense). The 1L{λ(i)} and 1L{h(...)t−1} channels indicate the positions of landmarks and heads respectively (λ(i) are fixed throughout the episode and not indexed by t). Note that at t = 0 no actions have been taken, so the previous-action encodings are all 0s.
Now we describe the controller architecture. Given the context ct, the controller begins with a sequence encoder for the variable length encoding σt. We pass σt through two 1D convolutional layers (along the L dimension) with filter width 3 and stride 1. This is the only aspect of our encoder that provides awareness of the local ordering of cells on the tape.
After that, we explore two different seq2fixed encoders:
• RNN encoder: BiLSTM produces fixed length embedding (concat of embedding for each direction) which is fed into the controller.
• Attention encoder: A context-independent query set is learned (fixed during evaluation). Queries are fed into attention over the tape, and the resulting weighted sum over tape values is a fixed length embedding that is fed into the controller.
Next, we pass the resulting fixed-sized embedding for σt along with ξt into a feed forward network which outputs attention queries for the read/write head actions, and logits for the module selection action. Logits for the read/write head actions are produced with dot-product attention over σt (independent attention head for each read/write head).
Learning the Controller. We frame our setup in the reinforcement learning paradigm, where the controller is the agent, and other components (memory and modules) are part of the environment. From the perspective of algorithm induction, only the program input and target outputs are external, while everything in MAIN is part of the black box that performs the computation. The controller is trained end-to-end on all its actions with Impala (Espeholt et al., 2018), a distributed variant of REINFORCE. Simultaneously learning to halt with RL, while learning what computation to perform, proved to be unstable in our experiments. We removed the additional complication of learning when to halt by providing a halting oracle. The oracle is given the correct output, and immediately ends the episode if the answer is in memory. The oracle is used in evaluation as well.

heading: 4 EXPERIMENTS

text:
We now present an empirical evaluation of our architecture MAIN in order to establish that (i) it can learn to perform algorithmic tasks, (ii) attention is important for length generalization, and (iii) separating control flow and data flow through limited view helps in learning.
Tasks: We consider five algorithmic tasks with six pre-defined modules. All but the Multi-Digit Addition task are given the same module pool. We found that Multi-Digit Addition was more difficult to learn, and to reduce the action space we cut down the module pool to only ones needed to perform the computation. For simplicity, we make all the modules have the same number of inputs and outputs. Specifically in our experiments there are two read-heads and one write head. Modules which naturally read less than 2 inputs ignore their additional inputs. We consider the following six modules: Identity, Increment, Max, Sum, SumInc, and Reset. The semantics of the modules is presented in Appendix A.1. We consider the following tasks.
• Copy: Given an array of base 10 digits in the memory tape and a pointer to the destination, the task is to copy all elements from the array to the destination (e.g. see Figure 2(a)). We provide landmarks to start of the input and start of the output location. For an input array of length n, the output would be also of length n, and so the total memory tape size would be 2n+ 1, including 1 separation token. Modules: Reset, Identity, Increment, Max, Sum
• Reverse: Same tape size as Copy task, with the goal of writing the input digits in reverse order. • Increment: Same tape size as Copy task, with the goal of writing the result of adding 1 to each
digit of the input array (modulo base) to the destination.
• Filter Even: Given an array of base 16 digits in the tape, the goal is to output a sequence containing only the even-valued digits in the same order. Modules: Reset, Identity, Increment, Max, Sum
• Multi-Digit Addition: Given two arrays of base 10 digits separated by ‘+’, the goal is to output the sum of the integers (denoted by input arrays) as a sequence of digits. Modules: Sum, SumInc

heading: 4.1 EXPERIMENTAL SETUP

text:
We train the controller with Impala, a distributed asynchronous algorithm. We used 50 data collection workers to sample episodes from the most recent policy. There is one training worker which queues up episodes sent by the data collectors into training batches. We train until 30M timesteps across all episodes. We use a curriculum over task difficulty, which essentially corresponds to the input length. For each episode, an input-output pair is sampled from the task generator given a difficulty level, and the difficulty level is sampled uniformly in range [1, C], where C is the maximum curriculum setting. We vary C from 2 to 10 with a linear schedule starting at 1M and ending at 18M. During training, each data collector generates new task inputs on the fly.
For evaluation, we precompute datasets of 100 test inputs for generalization with larger input lengths 10, 20, and 100 sampled from the same data generator. We run evaluation repeatedly and concurrently with training, and take the highest observed success rate as the final metric. For a given input, we compute success as whether the controller controller produced exactly the desired output. We take the average success across the 100 evaluation inputs as the success rate. Because we run each experiment 10 times, we can estimate the variance of success rate due to random weight initialization, randomly sampling from the policy, and stochastic effects of asynchronous training. We report average success rate (across the 10 trials) and the empirical standard deviation.

heading: 4.2 RESULTS AND ABLATIONS

text:
Table 2 presents the experiment results of evaluating MAIN on the five algorithmic tasks with different ablation choices for the generalization input length of 100. For each task, we report the number of runs out of 10 that achieved 100% success on the test set of 100 evaluation inputs (each of length 100). Additionally, the average of success rates together with their variance for four of the tasks for different input generalization lengths of 10, 20, and 100 is shown in Figure 4.
As shown in Table 2, MAIN can learn to generalize perfectly for inputs of length 100 when trained on inputs with length up to 10 only. For the copy, reverse, increment, and filter-even tasks, MAIN can generalize in majority of runs out of 10. The multi-digit addition task is particularly challenging in our architectural setting. For learning this task, the controller first needs to learn to select appropriate individual digits to be added for each timestep. In addition, it also needs to learn to use the digits and module choices selected in the previous timestep to decide whether to add a carry or not while computing the addition. Remarkably, MAIN was able to learn one such controller.
Now we evaluate whether the special architectural features of MAIN are necessary for good performance. First, we evaluate whether the controller needs to observe the values on the tape, by considering an ablation (labeled “No Tape Values” in the table) which removes the top third of σt (i.e. removes the tape values st). It may then seem like the controller cannot do anything, but it still has access to the action history metadata and values under the previously placed read/write heads. Notably, we found that without tape values, the controller performance goes down, except in MultiDigit Addition, which is the only setting in which could generalize to length 100. Since this task requires the controller to compute whether a carry bit should be used for adding the intermediate result for two digits, hiding the tape contents and only providing the head values constrains the space of possible argument choices for modules and helps the controller to learn desired computation.
Next, we evaluate the usefulness of action history, by considering an ablation (labeled “No Action History” in the table) which removes the fixed context ξt and the bottom third of σt, so that the controller does not have information about previous actions. As expected, these architectures do not generalize, achieving generalization accuracy of 0. The reason is that without the action history, the controller does not have a mechanism to remember which part of the computation it is at currently, and therefore cannot learn iterative computations, which is required by all of our tasks.
Recall that ξt contains the tape values underneath the previous read-write locations, even though the controller could infer this from other context. Next, we evaluate whether this is helpful by removing this in the ablation labeled “No Action History Tape Values”. On most tasks, the performance is comparable to the full model, except on filter-even in which this ablation is slightly better.
Finally, we evaluate whether our attention-based encoder could be replaced with a simpler recurrent controller, as has been used in previous work (Chang et al., 2018). For shorter inputs of length 10, the recurrent encoder achieves perfect average evaluation accuracy for the simpler tasks such as copy, reverse, and increment (Figure 4). However, when evaluated on longer input lengths, its performance degrades significantly. For filter-even and multi-digit addition tasks, the generalization accuracy of the recurrent encoder goes to almost 0 for length 100. On the other hand, attention based tape encoder always result in significantly higher generalization accuracies across all the tasks.

heading: 5 CONCLUSION

text: We presented a new neural architecture MAIN that learns algorithmic tasks from input-output examples. MAIN uses a neural controller that interacts with a variable-length input tape to learn to compose modules. At each time step, the controller chooses which module to use together with the corresponding tape locations for module arguments and for writing the module output back to the tape. This architecture is trained end-to-end using reinforcement learning and we show that it can learn several algorithms successfully that generalize perfectly to inputs of much longer length (100) than the ones used for training (up to 10).

heading: A APPENDIX

text:
A.1 SEMANTICS OF MODULES
The semantics of the modules we consider are as follows.
Modules:
• Reset( , )→ ‘.’. • Identity(x, )→ x. • Increment(x, )→ char(int(x) + 1) if isnumeric(x) else ‘.’. • Max(x, y)→ max(x, y). • Sum(x, y)→ char((int(x) + int(y))%B) if isnumeric(x) and isnumeric(y) else ‘0’. • SumInc(x, y)→ char((int(x) + int(y) + 1)%B) if isnumeric(x) and isnumeric(y) else ‘0’.

title: TOWARDS MODULAR ALGORITHM INDUCTION


summaries: The paper studies the sensitivity of a neural network with respect to quantizing its weights and activations. The idea is to use Monte Carlo Arithmetic (MCA) in order to calculate the number of significant bits in the training loss (e.g. cross entropy) that are lost due to floating-point arithmetic. The results show that the number of significant bits lost correlates with the reduction in classification accuracy when quantizing the weights and activations of the neural network.

summaries: The authors propose a scalable method based on Monte Carlo arithmetic for quantifying the sensitivity of trained neural networks to floating point rounding errors. They demonstrate that the loss of significance metric K estimated from the process can be used for selecting networks that are more robust to quantization, and compare popular architectures (AlexNet, ResNet etc.) for their varying sensitivities.

abstractText: Quantization is a crucial technique for achieving low-power, low latency and high throughput hardware implementations of Deep Neural Networks. Quantized floating point representations have received recent interest due to their hardware efficiency benefits and ability to represent a higher dynamic range than fixed point representations, leading to improvements in accuracy. We present a novel technique, Monte Carlo Deep Neural Network Arithmetic (MCDA), for determining the sensitivity of Deep Neural Networks to quantization in floating point arithmetic. We do this by applying Monte Carlo Arithmetic to the inference computation and analyzing the relative standard deviation of the neural network loss. The method makes no assumptions regarding the underlying parameter distributions. We evaluate our method on pre-trained image classification models on the CIFAR-10 and ImageNet datasets. For the same network topology and dataset, we demonstrate the ability to gain the equivalent of bits of precision by simply choosing weight parameter sets which demonstrate a lower loss of significance from the Monte Carlo trials. Additionally, we can apply MCDA to compare the sensitivity of different network topologies to quantization effects.1

authors:
Jan Achterhold
Jan M. Köhler
Anke Schmeink
Tim Genewein

title: Variational network quantization

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

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

venue: URL http://arxiv.org/abs/1409.0473. cite arxiv:1409.0473Comment: Accepted at ICLR

authors:
Léonard Blier
Yann Ollivier

title: The description length of deep learning models

venue: In Advances in Neural Information Processing Systems,

authors:
Charles Blundell
Julien Cornebise
Koray Kavukcuoglu
Daan Wierstra

title: Weight uncertainty in neural networks

venue: In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37,

title: Algorithms for minimization without derivatives

authors:
Alexander Buchholz
Florian Wenzel
Stephan Mandt

title: Quasi-Monte Carlo variational inference

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Yoojin Choi
Mostafa El-Khamy
Jungwon Lee

title: Towards the limit of network

venue: quantization. ArXiv,

authors:
Ronan Collobert
Jason Weston
Léon Bottou
Michael Karlen
Koray Kavukcuoglu
Pavel Kuksa

title: Natural language processing (almost) from scratch

venue: J. Mach. Learn. Res.,

authors:
Julian Faraone
Nicholas Fraser
Michaela Blott
Philip HW Leong

title: Syq: Learning symmetric quantization for efficient deep neural networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Michael Frechtling
Philip H.W. Leong

title: Mcalib: Measuring sensitivity to rounding error with monte carlo programming

venue: ACM Trans. Program. Lang. Syst.,

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS10). Society for Artificial Intelligence and Statistics,

title: What every computer scientist should know about floating-point arithmetic

venue: ACM Comput. Surv.,

authors:
Suyog Gupta
Ankur Agrawal
Kailash Gopalakrishnan
Pritish Narayanan

title: Deep learning with limited numerical precision

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

title: Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA

venue: USA, 2nd edition,

authors:
Andrew G. Howard
Menglong Zhu
Bo Chen
Dmitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: Mobilenets: Efficient convolutional neural networks for mobile vision

venue: applications. ArXiv,

title: Robust estimation of a location parameter

venue: Annals of Mathematical Statistics,

authors:
Forrest N. Iandola
Matthew W. Moskewicz
Khalid Ashraf
Song Han
William J. Dally
Kurt Keutzer

title: Squeezenet: Alexnet-level accuracy with 50x fewer parameters and <1mb model size

authors:
Benoit Jacob
Skirmantas Kligys
Bo Chen
Menglong Zhu
Matthew Tang
Andrew Howard
Hartwig Adam
Dmitry

title: Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-only inference

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in Neural Information Processing Systems

authors:
Christos Louizos
Karen Ullrich
Max Welling

title: Bayesian compression for deep learning

authors:
Naveen Mellempudi
Sudarshan Srinivasan
Dipankar Das
Bharat Kaul

title: Mixed precision training with 8-bit floating point. CoRR, abs/1905.12334, 2019

authors:
Paulius Micikevicius
Sharan Narang
Jonah Alben
Gregory Diamos
Erich Elsen
David Garcia
Boris Ginsburg
Michael Houston
Oleksii Kuchaiev
Ganesh Venkatesh
Hao Wu

title: Mixed precision training

venue: In International Conference on Learning Representations,

authors:
Douglas Stott Parker
David Langley

title: Monte carlo arithmetic: exploiting randomness in floatingpoint arithmetic. In Monte Carlo Arithmetic: exploiting randomness in floating-point arithmetic

venue: Computer Science Department,

authors:
Douglas Stott Parker
Brad Pierce
Paul R. Eggert

title: Monte carlo arithmetic: how to gamble with floating point and win

venue: Computing in Science and Engineering,

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks

authors:
Charbel Sakr
Naresh Shanbhag

title: An analytical method to determine minimum per-layer precision of deep neural networks

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

title: Per-tensor fixed-point quantization of the back-propagation algorithm

authors:
Charbel Sakr
Yongjune Kim
Naresh Shanbhag

title: Analytical guarantees on numerical precision of deep neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Mark Sandler
Andrew G. Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Mingxing Tan
Quoc Le

title: EfficientNet: Rethinking model scaling for convolutional neural networks

venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning,

authors:
Mingxing Tan
Bo Chen
Ruoming Pang
Vijay Vasudevan
Quoc V. Le

title: Mnasnet: Platformaware neural architecture search for

venue: mobile. ArXiv,

authors:
Naigang Wang
Jungwook Choi
Daniel Brand
Chia-Yu Chen
Kailash Gopalakrishnan

title: Training deep neural networks with 8-bit floating point numbers

venue: In Proceedings of the 32Nd International Conference on Neural Information Processing Systems,

title: Rounding Errors in Algebraic Processes

authors:
Bichen Wu
Alvin Wan
Xiangyu Yue
Peter Jin
Sicheng Zhao
Noah Golmant
Amir Gholaminejad
Joseph Gonzalez
Kurt Keutzer

title: Shift: A zero flop, zero parameter alternative to spatial convolutions

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018a

authors:
Shuang Wu
Guoqi Li
Feng Chen
Luping Shi

title: Training and inference with integers in deep neural networks

authors:
Guandao Yang
Tianyi Zhang
Polina Kirichenko
Junwen Bai
Andrew Gordon Wilson
Christopher De Sa

title: Swalp : Stochastic weight averaging in low precision training

authors:
Jackson H.C. Yeung
Evangeline F.Y. Young
Philip H.W. Leong

title: A monte-carlo floatingpoint unit for self-validating arithmetic

venue: In Proceedings of the 19th ACM/SIGDA International Symposium on Field Programmable Gate Arrays,

authors:
Shuchang Zhou
Zekun Ni
Xinyu Zhou
He Wen
Yuxin Wu
Yuheng Zou

title: Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth

venue: gradients. ArXiv,

heading: 1 INTRODUCTION

text:
Deep Neural Networks have achieved state-of-the-art performances in many machine learning tasks such as such as speech recognition (Collobert et al., 2011), machine translation (Bahdanau et al., 2014), object detection (Ren et al., 2015) and image classification (Krizhevsky et al., 2012). However, excellent performance comes at the cost of significantly high computational and memory complexity, typically requiring teraops of computation during inference and Gigabytes of storage. To overcome these complexities, compression methods have been utilized, aiming to exploit the inherent resilience of DNNs to noise. These engender representations which maintain algorithm performance but significantly improve latency, throughput and power consumption of hardware implementations. In particular, exploiting reduced numerical precision for data representations through quantization has been emphatically promising, whereby on customizable hardware, efficiency scales quadratically with each bit of precision.
Quantization of fixed-point arithmetic (Q-FX) for DNN inference has been extensively studied, and more recently there has been increasing interest in quantized floating point (Q-FP) arithmetic for both DNN inference and training (Wang et al., 2018). Q-FP has the advantage of higher dynamic range compared to equivalent Q-FX representations and reduced hardware cost over single-precision floating point (FP). This has influenced application specific integrated circuits (ASICs) such as Google’s tensor processing unit (TPU), which supports 16-bit floating point (16-FP) and soft processors such as Microsoft’s Project Brainwave which utilizes 8-FP.
To illustrate these hardware benefits, we synthesized arithmetic logic units (ALUs) in different formats and different precision on an FPGA and present performance estimates in operations per second (OPs) and area estimates in Look-up Tables (LUTs) per operation (LUTs/Op) in Figure 1. As shown, 8-bit fixed point (8-FX) achieves improved performance and area over 8-FP. However, 7-FP is a significant improvement over 8 or 12-FX and 8 or 9-FP. These examples demonstrate substantial performance and area benefits from reducing FP precision by only 1 to 2-bits. Thus, if we
1Source code will be available if the paper is accepted
can design networks which not only achieve high accuracy but are robust to quantization, higher performing hardware solutions are possible.
Since in Q-FP, we are trying to represent the infinite set of real numbers using a finite number of bits, quantization and rounding artefacts will be introduced, with inaccuracies being cascaded along the computation graph (IEEE, 1985; Goldberg, 1991; Higham, 2002). This paper proposes Monte Carlo Deep Neural Network Arithmetic (MCDA), a novel way to apply Monte Carlo Arithmetic (MCA) (Parker et al., 2000) for determining the sensitivity of Deep Neural Networks to Q-FP representations. It allows hardware-software designers to quantify the impact of quantization, enabling more efficient systems to be discovered. We do this by exploiting Monte Carlo simulations under which rounding effects are randomized. This, in turn, allows one to infer the sensitivity of executing a computation graph to quantization effects.
Our MCDA technique is highly sensitive, allowing very small differences in quantization behaviour to be detected. The technique makes no assumptions regarding data distributions and directly measures the effects of quantization on the problem under study. This allows us to provide insights into the precision requirements of any inference network for any given dataset. Additionally we can use the technique to select weight parameters which are more robust to floating point rounding. The theoretical and practical contributions of this work can be summarized as follows:
• We introduce a novel and rigorous analysis technique, Monte Carlo Deep Neural Network Arithmetic (MCDA), which measures the sensitivity of Deep Neural Network inference computation to floating point rounding error.
• When applied to neural network inference, we show MCDA can determine the precision requirements of different networks, rank them, and detect small differences between different neural network topologies and weight sets.
• We demonstrate that while a network with the same topology but different weights may have the same loss and validation accuracy, their sensitivity to quantization can be vastly different. Using the CIFAR-10 and ImageNet datasets, we introduce a method to choose weights which are more robust to rounding error, resulting in a greatly improved accuracyarea tradeoff over state-of-the-art methods.
It is worth noting that although we consider convolutional neural networks for image classification, this method could be applied for any neural network model architectures and applications. Moreover, while the experiments in this paper are limited to inference, it may be possible to apply the same idea to analyze training algorithms.

heading: 2 RELATED WORK

text:
Low-precision representations of deep learning have been extensively studied. Many training methods have been developed to design representations for fixed point inference (Jacob et al., 2018; Faraone et al., 2018; Zhou et al., 2016) and training (Wu et al., 2018b; Yang et al., 2019; Gupta et al., 2015; Sakr & Shanbhag, 2019). Other methods have also utilized Q-FP arithmetic for inference and training whilst maintaining single-precision accuracy. (Micikevicius et al., 2018) implemented 16- FP arithmetic training whilst storing a 32-FP master copy for the weight updates. Additionally,
(Wang et al., 2018; Mellempudi et al., 2019) with 8-FP arithmetic whilst using a 16-FP copy of the weights and 16/32-bits for the accumulator. Techniques for determining per-layer sensitivity to quantization have also been studied (Choi et al., 2016; Sakr & Shanbhag, 2018). Further, other studies have successfully determined the minimum fixed point precision requirements for a given DNN accuracy threshold (Sakr et al., 2017). The accuracy and stability of various numerical algorithms in finite precision arithmetic has been studied in (Higham, 2002; Wilkinson, 1994). This has led to techniques for tracking information lost from finite precision arithmetic using random perturbation such as Monte Carlo Arithmetic (Parker et al., 2000; Frechtling & Leong, 2015). Monte Carlo methods have also been used in Bayesian Neural Networks (Buchholz et al., 2018; Blier & Ollivier, 2018). In particular, (Achterhold et al., 2018) introduced a quantizing prior to learn weights which are either close to a quantized representation or have high variance. (Louizos et al., 2017) used hierarchical priors to prune nodes and posterior uncertainties to determine the optimal fixed point precision. (Blundell et al., 2015) use a Monte Carlo approach to learn a probability distribution on the weights of a neural network. To the best of our knowledge, our work is the first to present a technique for directly determining the sensitivity of DNNs to floating point rounding and to explicitly compute precision bounds of a trained network. These ideas can be very usefully applied to extending the limits of low-precision representations in deep learning applications.

heading: 3 BACKGROUND

text: In this section, we describe background theory upon which our technique for determining the sensitivity of DNNs to floating point rounding is based.

heading: 3.1 FLOATING POINT ARITHMETIC

text:
The IEEE-754 binary floating point format (IEEE, 1985) represents most real numbers x by a subset in normal form as: x̂ = (−1)sx(1 +mx)2ex (1) where sx ∈ {0, 1} is the sign bit, ex is an integer representing the exponent of x̂ and mx is the mantissa of x̂. Such number formats can be described as a (sx, ex,mx) tuple. In binary form the representation is (bs, be1, b e 2, ..., b e Bex , bm1 , b m 2 ..., b m Bmx
) ∈ {0, 1}B , with Bex and Bmx being the number of exponent and mantissa bits, respectively. The infinite set of real numbers R is represented in a computer withB = 1+Bex+Bmx bits, and we define the finite set of real numbers representable in floating point format as exact values, F ⊂ R. Real numbers which aren’t representable are rounded to their nearest exact value. We call this set of numbers inexact values, I, where I∪F = R. The approximation x̂ = F(x) = x(1 + δ), given x ∈ I, introduces rounding error into the computation. The value of δ = ∥∥x−x̂ x
∥∥, represents the relative error which is a function of the machine hardware precision, p, as δ ≤ , where = 2−p (IEEE, 1985; Goldberg, 1991; Higham, 2002). In general, inexactness can be caused by finite representations or errors propagating from earlier parts of the computation. Often the primary cause of error in floating point arithmetic is catastrophic cancellation which causes numerical inaccuracy. Catastrophic cancellation occurs when for example, two near equal FP numbers, sharing k significant digits, are subtracted from one another as shown in (2) (Higham, 2002).
0. f1 f2 ... fk f(k+1) ... ft
− 0. f1 f2 ... fk g(k+1) ... gt = 0. 0 0 .... 0 h(k+1) ... ht
(2) 0. f1 f2 ... fk f(k+1) ... ft r(t+1) ... rp
− 0. f1 f2 ... fk g(k+1) ... gt r̂(t+1) ... r̂p = 0. 0 0 .... 0 h(k+1) ... ht i(t+1) ... ip (3)
In normalized form, the leading zeros are removed by shifting the result to the left and adjusting the exponent accordingly. The result is 0.hk+1...hti1...ik which has only (t − k) accurate digits and digits i which are unknown. Additionally, the remaining accurate digits h are most likely affected by rounding error in previous computations. This can significantly magnify errors, especially in computing large computational graphs such as that of state-of-the-art DNNs.
If either operand in (2) is inexact, then the digits h are no more significant than any other sequence of digits. Yet, FP arithmetic has no mechanism of recording this loss of significance. By padding both our operands with random digits r and r̂ in (3), the resulting digits i are randomized. If k
digits are lost in the result, then k random digits will be in the normalized result and when computed over many random trials, the results will disagree on the trailing k digits. In this case, we are able to detect catastrophic cancellation because the randomization over many trials provides a statistical simulation of round-off errors. We can use techniques from numerical analysis such as Monte Carlo methods to appropriately insert precision-dependant randomization in this way.

heading: 3.2 MONTE CARLO ARITHMETIC

text:
Monte Carlo methods can be used to analyze rounding by representing inexact values as random variables (Parker et al., 2000; Frechtling & Leong, 2015). The real value x, as represented in (1), can be modelled to t digits, using:
inexact(x̂, t, δ) = x̂+ 2ex−tδ = (−1)sx(1 +mx + 2−tδ)2ex (4)
where δ ∈ U(− 12 , 1 2 ) is a uniformly distributed random variable and t is a positive integer representing the virtual precision of concern. For the same input x̂ in (4), we can run many Monte Carlo trials which will yield different values on each trial, where 0 < t < p so that the MCA can be run accurately on a computer with machine precision p. The ability to vary t is useful because it allows us to then evaluate the hardware precision requirements of a given system or computational graph for a given DNN.
MCA is a method to model the effect of rounding on a computational graph by randomizing all arithmetic operations. The randomization is applied for both generating inexact operands and also in rounding. In each operation using MCA, ideally both catastrophic cancellation and rounding error can be detected. An operation using MCA is defined as:
x ◦ y = round(inexact(inexact(x) ◦ inexact(y))) (5)
where ◦ ∈ ( +,−,×,÷). By applying the inexact function to both operators we make it possible to detect catastrophic cancellation. Furthermore, applying the inexact function to the operation output and then rounding this value implements random rounding and hence is used to detect rounding error (Parker & Langley, 1997). Hence, for the same input into the system, each trial will yield different operands and output.
After modifying the inexact and rounding operations as described, we use random sampling to simulate Monte Carlo trials. For each trial, we collect data on the resulting output of the system and compute summary statistics to quantify its behaviour (Parker et al., 2000). With sufficiently large number of Monte Carlo trials and virtual precision t, the expected value of the output from these trials will equal the value from using real arithmetic. As explained in the next section, we can determine the total number of digits lost to rounding error and the minimum precision required to avoid a total loss of significance.

heading: 3.3 ANALYSIS

text:
The relative error is bounded by δ ≤ 2−p from the design of IEEE FP arithmetic (Wilkinson, 1994; Goldberg, 1991). With this inequality, we can determine the expected number of significant binary digits available from a p-digit FP system as p ≤ −log2(δ). These definitions can be adapted for MCA by replacing the precision of the FP system, p, by the virtual precision, t, of an MCA operation. Thus, the relative error of an MCA operation, for virtual precision t, is δ ≤ 2−t and the expected number of significant binary digits in a t-digit MCA operation is at most t. Using this definition and the proof provided in (Parker & Langley, 1997), the total significant binary digits in a set of M trials is s′ = log2 µσ where µ is the mean and σ the standard deviation. The output of the system should be some scalar value so that we can perform such analysis. For experimentation, M trials are run for all of t ∈ {1, 2, 3, ..., tmax}. The total number of base-2 significant digits lost in a set of M trials is Kt, in (6):
Kt = t− s′ = t− log2( µ
σ ) = log2 Θ + t (6)
where Θ = σµ , for (µ 6= 0), is the relative standard deviation (RSD) of the MCA results. The virtual precision t controls the perturbation strength applied by the inexact function. For a given Kt, as we reduce t, the RSD should increase according to equation 6. At some point, an unexpected loss of
significance (Frechtling & Leong, 2015) is encountered due to the nonlinear effects of quantization. The value at which this occurs is defined as tmin. The number of significant digits lost for the system being analyzed is then computed by averaging all Kt whereby t > tmin as shown in (7):
K =
{ 1 tmax−tmin ∑tmax t=tmin Kt where tmax > 1
Kt where tmax = 1 (7)
For DNN inference, we propose to use K as a sensitivity measure for the network to FP rounding. The method for implementing this is discussed in the next section.

heading: 4 MONTE CARLO DEEP NEURAL NETWORK ARITHMETIC

text: We now describe MCDA, a methodology for applying MCA techniques to DNN computation, allowing us to understand the sensitivity of a given network and its weight representation to FP rounding.

heading: 4.1 NETWORK MODEL

text:
We consider a generalized non-linear L-layer neural network with an output vector yL, input data vector x and learnable weight parameter tensor w = ⋃ wl (l = 1, . . . , L), whereby yL = f(x;w). To compute y, several layers consisting of general matrix multiplication (GEMM) operations (such as convolutional and fully-connected layers) between the layer input xl and weight parameters wl, followed by a non-linear activation function, h, producing intermediate layer outputs xl, i.e. yl = h(xl ⊗wl). The output of a given layer becomes the input to the subsequent layer, i.e. xl+1 = yl, with x1 = x. A loss function is the objective function to minimize updating w via an optimizer such as stochastic gradient descent. For a given set of input data X , the total network loss during inference is calculated by applying a loss function loss(f(x;w), ŷ(x)) where ŷ(x) is the target ground truth output for x. The total loss for X is then a scalar output, such that:
L(X;w) = 1 |X| ∑ x∈X loss(f(x;w), ŷ(x)) (8)
Updates of w are usually done in small batches over subsets of X .
Naively applying MCA to each operation (fine-grained MCA) as described in equation (5) poses significant computational difficulties for DNN models. We observe two primary issues with employing fine-grained MCA to a DNN computational graph:
• Firstly, the number of required trials for Monte Carlo experiments to generate robust results can typically be in the hundreds or thousands. As DNN inference of state-of-the-art networks typically consist of billions of operations, the computational requirements of applying MCA after each operation will be very large, making the technique impractical. • Using the accuracy as the system output for MCA experiments is problematic because it is
a discrete value. For high values of t, Monte Carlo results across different t then become indistinguishable and the standard deviation for a given t is potentially zero.

heading: 4.2 MONTE CARLO NETWORK INFERENCE

text:
To reduce the computational cost of Monte Carlo experiments, we employ MCDA, which is a coarsegrained approach to MCA for GEMM operations. Conveniently, these can be naturally implemented in modern machine learning frameworks such as PyTorch. Furthermore, to ensure the system output is a continuous value, the loss function output is used, rather than the accuracy. In this case, small perturbations in layer operands are more likely to produce observable changes in the output.
MCDA applies a vector version of (5) to the DNN inference computational problem in (8). Our operands in this case are vectors and ◦ represents a neural network layer operation. For example, the output from performing a GEMM operation can thus be represented by:
yl = round(inexact(inexact(xl)⊗ inexact(wl))) (9) Since the inexact function is applied to the inputs and outputs of a GEMM operation, an optimized implementation can be used. This is in contrast to full MCA which requires the application of (5)
to every individual scalar operation. The vector form in (9) is applied to each edge of neural network computational graph where multiply (division) and/or add (subtract) operations are performed. Hence, it is not applied to operations such as MaxPool and ReLu. As an example, in Figure 2 we show where the inexact function is applied for a residual block with folded batch normalization, which is a repeating sequence of layers found in ResNet models (He et al., 2015). At the final output of the network, the loss is computed with (8) and the inexact function is applied to the outputs y and also the loss output scalar value L. From analyzing the behavior of the loss, we infer the sensitivity of the accuracy of the system to FP rounding. By using MCDA for the GEMM operations, we will not be able to detect all instances of catastrophic cancellation. However, we significantly reduce execution time over fine-grained MCA and show in the next section that we can still retrieve valuable information about our system. In fact, for one trial with one batch of 32 images on ImageNet running on a Nvidia Titan Xp GPU, the speed up of regular inference without MCDA is only 1.05× (for a single Monte Carlo trial). We also note that fine-grained MCA could be applied with a simple modification and would be possible given appropriate customized hardware support for parallel Monte Carlo computations (Yeung et al., 2011).

heading: 5 EXPERIMENTAL RESULTS

text:
In this section, we present experimental results for applying MCDA to exemplary convolutional neural networks. We use the CIFAR-10 and ImageNet image classification datasets to compare MobileNet-v2 (Sandler et al., 2018), EfficientNet (Tan & Le, 2019), AlexNet, ResNet (He et al., 2015), SqueezeNet (Iandola et al., 2016) and MnasNet (Tan et al., 2018). For CIFAR-10, we use a batch size of 128, whilst we use a batch size of 32 for ImageNet experiments. Cross-entropy is used as the loss function for both datasets. For a given network, dataset, weight representation and t, we apply MCDA with M = 1000 trials. The resulting loss from each trial is computed with the same single batch of images and hence additional data is not required. We compute Θt from our results for all t ∈ {1, 2, 3, ..., 16}. Following this, we run linear regression analysis using the MCALIB2 (Frechtling & Leong, 2015) R library, on our Θt values, to determine tmin and K. tmin is defined as the point of lowest t where the difference between the regression line and the equivalent Θt is less than half a binary digit, i.e. log10(2
0.5). Further detail on the calculation of K and tmin from MCALIB can be found in Appendix A.1. We report Q-FP validation accuracy using the quantization function from (Wang et al., 2018) with stochastic rounding3 (See Appendix A.2).

heading: 5.1 DISTINGUISHING WEIGHT PARAMETER REPRESENTATIONS

text:
As discussed in Section 3.1, the inexactness in FP arithmetic largely depends on the numerical value of operands. Two instances of the same network and dataset, with the same validation accuracy, but vastly different weight representations, will likely produce differing sensitivities to FP rounding. We first train 8 instances of EfficientNet-b0 and MobileNet-V2 on CIFAR-10 from scratch with random initialization from (Glorot & Bengio, 2010), all achieving within 1% validation accuracy of one another. Using MCDA, we calculate the K values for each model (See Appendix A.3).
2https://github.com/mfrechtling/mcalib 3https://github.com/Tiiiger/QPyTorch
We then test their percentage validation accuracy decrease from using post-training quantization (i.e. no finetuning) with varying Q-FP precisions. In Figure 3, we see that the models with higher K values typically experience a larger drop in Q-FP accuracy, indicating they are more sensitive to floating point rounding error. Notably, the model with lowest K for 7-bit MobileNet-v2 experiences a lower percentage validation accuracy drop than three of the 8-bit models. In this case, MCDA model selection enables the saving of a bit of precision while achieving smaller accuracy decrease than some of the trained 8-FP models.

heading: 5.2 COMPARISON TO PREVIOUS WORK

text: One practical use case from the insights gained by MCDA is model selection for quantization. Typically when quantizing a given model trained on a given dataset, the model with highest validation accuracy is chosen and the sensitivity to quantization is assumed to be the same across models. As discussed, for Q-FP representations this is not necessarily the case. We can use K from MCDA to predict which models will be more robust to quantization. To demonstrate this, in Table 1 we compare post-training quantization results for model selection based on K from MCDA, against a baseline model chosen based on the highest single-precision validation accuracy. Evidently, even though the single-precision accuracy is initially as much as 0.9% higher, after quantizing the network to 8-5 bits, the accuracy of the network chosen by smallest K is always significantly higher.

heading: 5.3 NETWORK COMPARISON

text:
Modern DNNs consist of convolutional blocks with highly varying computational graphs (Wu et al., 2018a; Howard et al., 2017). Using MCDA we can also compute and compare their sensitivites to floating point rounding error to determine which networks will be robust to Q-FP representations.
In Figure 4 we show the Θt of pre-trained models, trained on the ImageNet dataset from PyTorch4 5, for differing values of t and run linear regression analysis over our data points. From here we can then assign aK value to each network and compare their loss of significance. At each t, the distance from the regression lines to the ideal line represents the values of Kt, as described in (6). From the MCDA results, AlexNet is the least sensitive to rounding and ResNet-50 is the most, with various models in between these two. Additionally we compare EfficientNet at two different model scales and evidently the larger model has much larger sensitivity. We then also compare the validation accuracy percentage decrease of all models at 10, 9 and 8-FP post-training in Figure 5. At 8-FP, besides MnasNet which experiences a large accuracy drop, K is able to predict validation accuracy degradation. Thus, MCDA provides very valuable information about Q-FP model design.

heading: 6 CONCLUSION

text:
We present a novel, highly sensitive, technique to quantify rounding error in DNNs. This is the first method to successfully compare the sensitivity of networks to floating point rounding error. Ultimately, this technique provides a tool for enabling the design of networks which perform higher when quantized. We do this by applying concepts from Monte Carlo Arithmetic theory to DNN computation. Furthermore, we show that by calculating the loss of significance metric K from MCDA, on the CIFAR-10 and ImageNet datasets, we can compare network sensitivities to floating point rounding error and gain valuable insights to potentially design better neural networks. This is an important contribution due to the increasing interest in low-precision floating point arithmetic for efficient DNN hardware systems. The theoretical and practical contributions of this paper will likely translate well to analyzing floating point rounding in backpropagation in future work.
4https://github.com/pytorch/vision/tree/master/torchvision 5https://github.com/rwightman/pytorch-image-models

heading: A APPENDIX

text:
A.1 EXPERIMENTAL SETUP
In all our experiments, for a given network, dataset, weight representation and t, we run 1000 Monte Carlo trials. The network loss output from each trial is computed with the same single batch of images from the training dataset. We then independently compute the Θt of the network loss for t ∈ {1, 2, 3, ..., tmax} where tmax = 16. Following this, we then run linear regression and calculate K and tmin using MCALIB6. To compute the linear regression, MCALIB uses a log transformed variable, with log(Θ) as the dependant variable and t as the exploratory variable (Frechtling & Leong, 2015).
log10(Θ) = log10(2 K−t) (10)
= − log10(2)t+ log10(2)K (11) = mt+ c (12)
6https://github.com/mfrechtling/mcalib
Algorithm 1 Summary of Linear Regression Analysis for MCDA Initialize: Pre-train a single-precision DNN model. Set tmax. Set number of trials M . Inputs: Batch of inputs & targets (X, Ŷ ), loss function loss(f(x;w), ˆy(x)), current weights w Outputs: tmin and K
Monte Carlo Trials: for t = 1 to tmax do
for trials=1 to M do L(X;w) = ForwardPath (X, Ŷ ,w, t) using (9) end for Compute µ and σ of all trials Compute Θt using (6)
end for
Calculate K and tmin: for t = 1 to tmax do
Compute Pt using (10) - (14) Compute Pt −Θt if Pt −Θt < log10(20.5) then tmin = t break else continue
end if end for Compute K using (6) and (7)
where m = − log10(2) = −0.30103 is the slope and c is the intercept such that K = log2(10c). Given these inputs, the intercept c is calculated by minimizing the following objective function using Brents method (Brent, 1973) for single variable optimization:
f(x) = tmax∑ t=1 γtmax−iρH(ei) (13)
where ei = Θi − (mti + c) is the residual error, c ∈ [(Θtmax −mtmax)± 2m] is the initial search space for the intercept, γ = 0.75 and ρH(e) is the Huber loss function (Huber, 1964):
ρH(e) =
{ 1 2e
2 for |e| ≤ k k |e| − 12k 2 for |e| > k (14)
where k = 1.345σe and σe is the standard deviation of the residual error set, e. After determining the linear regression model, Pt = mt+ c, we determine whether each Θt is an outlier. If a value for Θt differs to the equivalent Pt by more than half a binary digit, then it is classed an outlier. tmin is then defined as the lowest t where Pt − Θt < log10(20.5). To compute K for a given network, we then average the values for Kt whereby t > tmin. This removes the outliers from the computation of K. We have summarized how the experiments were simulated in Algorithm 1.
A.2 QUANTIZED FLOATING POINT WITH STOCHASTIC ROUNDING
To quantize our pre-trained networks to Q-FP representations, we used stochastic rounding as described in (Wang et al., 2018) and implemented in QPytorch7. Two common forms of rounding for FP arithmetic are round-to-nearest and stochastic rounding. The former discards information in the least significant bit (LSB) which is rounded off. This information loss can be significant, especially when quantizing to a small number of bits. Stochastic rounding provides a method to capture this information loss from rounding off the LSB. Given x = (−1)sx(1 + mx)2ex as described in (1).
7https://github.com/Tiiiger/QPyTorch
Assume thatmx is in fixed precision with z′ bits which needs to be rounded to z bits, then stochastic rounding is as follows:
Round(x) = { (−1)sx(1 + bmxc+ )2ex with probability mx−bmxc (−1)sx(1 + bmxc)2ex with probability 1− mx−bmxc
(15)
where bmxc is the truncation of z′ − z LSBs of m, = 2−z . For each Q-FP accuracy reported in our experiments, we tested all possible combinations of the number of bits allowed for the exponent and mantissa which satisfied the desired precision. We then chose the combination which produced the highest accuracy.
A.3 CIFAR-10 REGRESSION ANALYSIS
In Figure 6, we display the linear regression analysis using MCALIB for the 8 MobileNet-v2 and EfficientNet-b0 models trained on CIFAR-10. As shown, Monte Carlo trials were run for each of these models for t ∈ {1, 2, 3, ..., 16}. The corresponding tmin and K values were then calculated using methods discussed in Appendix A.1. Thus, in Figure 3, it is these K values which are plotted against 8 and 7-bit Q-FP validation accuracy. Also, the models with lowest K values are chosen for MCDA model selection in Table 1.

title: MONTE CARLO DEEP NEURAL NETWORK ARITH-