Lossless Data Compression with Transformer
Authors: Gautier Izacard
Armand Joulin
Edouard Grave
Venue:  (2020)
Keywords: data compression
transformer

Abstract: Transformers have replaced long-short term memory and other recurrent neural networks variants in sequence modeling. It achieves state-of-the-art performance on a wide range of tasks related to natural language processing, including language modeling, machine translation, and sentence representation. Lossless compression is another problem that can benefit from better sequence models. It is closely related to the problem of online learning of language models. But, despite this ressemblance, it is an area where purely neural network based methods have not yet reached the compression ratio of state-of-the-art algorithms. In this paper, we propose a Transformer based lossless compression method that match the best compression ratio for text. Our approach is purely based on neural networks and does not rely on hand-crafted features as other lossless compression algorithms. We also provide a thorough study of the impact of the different components of the Transformer and its training on the compression ratio.

Under review as a conference paper at ICLR 2020
LOSSLESS DATA COMPRESSION WITH TRANSFORMER
Anonymous authors
Paper under double-blind review
ABSTRACT
Transformers have replaced long-short term memory and other recurrent neural networks variants in sequence modeling. It achieves state-of-the-art performance on a wide range of tasks related natural language processing, including lan- guage modeling, machine translation, and sentence representation. Lossless com- pression is another problem that can benefit from better sequence models. is closely related to the problem of online learning of language models. But, despite this ressemblance, is an area where purely neural network based methods have not yet reached the compression ratio of state-of-the-ard algorithms. In this paper, we propose a Transformer based lossless compression method that match the best compression ratio for text. Our approach is purely based on neural networks and does not rely on hand-crafted features as other lossless compression algorithms. We also provide thorough study of the impact of the different components of the Transformer and its training on the compression ratio.
INTRODUCTION
Lossless compression is class of compression algorithms that allows for the perfect reconstruc- tion of the original data. In the last decades, statistical methods for lossless compression have been dominated by PAQ-type approaches (Mahoney) 2005). The structure of these approaches is similar to the Prediction by Partial Matching (PPM) of Cleary & Witten (1984) and are composed of two separated parts: predictor and an entropy encoding. Entropy coding scheme like arithmetic cod- ing (Rissanen & Langdon| 1979) are optimal and most of the compression gains are coming from improving the predictor. The predictor estimates the probability of a token given its past, which is standard sequence modeling problem. In most PAQ-type approaches, this predictor relies heavily on hand-crafted features, but recent work has used the close connection between sequence mod- eling and machine learning to add neural networks based methods in the predictor. In particular, CMIX (Knoll 2014) has successfully added a Long-Short Term Memory (LSTM, HHochreiter & Schmidhuber 1997)) to the predictor of PAQ8, However, these approaches still heavily relying on hand-craften features along with the neural networks, and purely neural network based models still far from the state of the art (Bellard 2019).
In this work, we aim at building a purely neural network based model that compete the state of the art. We follow Knoll & de Freitas (2011) and formulate the token prediction problem solved by the predictor as the online learning of a sequence model. As opposed to previous work, we propose to use Transformer (Vaswani al. 2017a) to replace entirely the predictor of PAQ8 and its hand- crafted features. Transformer has emerged as the standard model for sequence modeling in natural language processing, achieving state-of-the-art performance in numerous applications, including. but not limited to, language modeling (Dai et al. [2019; (Sukhbattar et al. 2019b), machine transla- tion (Vaswani al. 2017a; Ott al. 2018). or sentence representation (Devlin al. 2018 Yang et al. 2019). As opposed to the recurrent neural networks (RNNs, [Elman] (1990)) used in lossless compression, they are able to capture very long-term dependencies by allowing direct connections between long-distance symbols.
However, the training of a Transformer is unstable and slow, limiting its application to the online setting of lossless compression. We propose several improvements to its architecture and training to accelerate and stabilize its online training. We show that our neural network approach matches the state of the art the competitive benchmark enwik8 used in the Hutter prize (Mahoney) 2005). We also provide a thorough study of all the important components of a Transformer and its training to achieve this performance.

---

Under review as a conference paper at ICLR 2020
2 RELATED WORK
In this section, we briefly introduce statistical based methods for lossless compression, and focus on PAQ based compression methods well as purely neural network based methods.
Statistical based methods. A popular statistical based method for lossless data compression is the Prediction by Partial Matching (PPM) of Cleary & Witten (1984). It is based on a predictor and entropy coding. that often takes the form of arthimetic coding (Rissanen & Langdon 1979]
Witten et al., (987b). but could also be a Huffman coding | 1952b). There are many
variants of PPM such PPM*C (Cleary & Teahan (997) or CPPMI 64 [Shkarin (2002). Another
statistical based method is the stochastic sequence memoizer of Gasthaus et al. (2010) that is based on nonparametric Bayesian model. In particular, the stochastic memoizer of Wood al. (2009) shares many similarities with PPM and reaches similar compression performance. However, most of these models are now surpassed by PAQ based methods like CMIX (Knoll 2014).
PAQ based compression methods. The series of PAQ algorithms, including PAQ8 (Mahoney) 2003), are statistical based methods designed to operate at bit-level, making it applicable to any type of data (Salomon & Motta 2010). There are also different version of PAQ8 specialised in different data types for better compression performance. PAQ uses a context mixer that follows the same structure as PPM. However, unlike PPM. the predictor of the context mixers combines the probability of different prediction models (Knoll & de Freitas 2011). More recently, PAQ based model called CMIX (Knoll, 2014) has been the state of the art for lossless text compression in terms of compression rate. As opposed to PAQ8, CMIX uses a Long Short Term Memory net- work (LSTM, Hochreiter Schmidhuber (1997) in their probabilistic model. The context mixer used in CMIX is also based on gated linear network (Veness et al. 2017).
Neural Network based compression method. More recently, there has been some attempts to use purely neural network based approaches for the probabilistic model. Notably Knoll released istm-compren (Knoll, 2015). which uses only the LSTM introduced in CMIX and the pre- processing of CMIX. Bellard (2019) investigates the performance of pure neural approaches with modern and large neural networks such as LSTM and Transformer. As well as our approach, all of these approaches use arithmetic coding as entropy coding scheme.
LOSSLESS DATA COMPRESSION
In this section, we briefly introduce the core components of statistical methods for lossless compres- sion. As opposed lossy compression where is allowed to lose information about the orginal data in the reconstruction, lossless compression methods restore the data to its original value.
Lossless compression methods are composed of two main elements: predictor and an entropy coding scheme. They are used successively to encode an input stream of tokens 8p,..., 8T. More precisely, for each token, the predictor first evaluates its probability given its past, then the entropy coding scheme uses this probability to store the token into a lossless code. More precisely, if we as- sume that tokens 50, ................................ St-1 are already compressed into a lossless code, the predictor computes the probability of the next token to be equal to its value given all the preceding tokens, i.c., the predictor computes p(sz st-1. 80)) Then, the entropy coding scheme encodes the token s, into a lossless code of bit-length log, p(s: st-1,.... so). Once the token has been encoded, these two steps are repeated on following tokens until the end of the sequence.
The operations performed by the predictor are identical during compression and decompression phases, i.e., both cases it predicts the next token given the preceding tokens. The only differ- ence is that, during the compression, the preceding tokens are taken from the input file, while during the decompression, they are generated by the entropy coding scheme. Note that, as opposed to the predictor, the role of the entropy coding scheme differs during the two phases since, during decom- pression, it acts as a decoder, i.e., given the compressed representation and the sequence of predicted probability distributions (p(s,|s,- ... (o)) sosesT it restores the original sequence of tokens.
There are many efficient and optimal methods for the entropy coding scheme. The source coding theorem (aannoon/Sano||/// 1948) has introduced the fundamental idea that any probability distribution can be
2

---

Under review as a conference paper at ICLR 2020
encoded into a lossless code. For given data point, the bit-length of this code is equal to the negative log probability estimated by the model. Thus, efficient probabilistic models are crucial to design effective compression scheme since the smallest codes obtained when the model estimates the true data distribution. Depending on the type of probabilistic model considered, several compression schemes have been developed to implement this idea in practice, namely Huffman coding Huffman (1952a), arithmetic coding Witten et al. (1987a) and asymmetric coding Duda (2009). The basic idea of all these entropy coding schemes assign shorter codes the more likely tokens. this work, we use the arithmetic coding scheme.
4 OUR APPROACH
In this section, we introduce our approach to lossless data compression using neural networks. First, briefly review transformer networks, which are the core of our method. We then discuss modifications to the standard model, to make it more suitable to long sequence modeling. Finally, we propose a strategy make the online learning of large models more efficient.
4.1 TRANSFORMER NETWORKS
Transformer networks were introduced by Vaswani et al. (2017a) in the context of machine transla- tion. These models are made of sequence of identical blocks, each comprising two sublayers. The first sublayer, called
ion, is based the attention mechanism from Bahdanau et al. (211)). More specifically, given a sequence of T hidden states dimension d, represented by the matrix X RdxT, the output of this layer is given by
Z = W.Xfftmaax (x" W W&
where W., WA and W, are the parameters of the sublayer used to compute the values, keys and queries of the attention mechanism. Multiple self-attention mechanisms are usually applied in par- allel, leading to the multi-head self-attention sublayer.
The second sublayer, called FFN, is a fully connected feed forward network with RELU activation, which is applied independently at each time step. Each sublayer is followed by a skip connection and layer norm operator, to finally obtain:
Z layee:Nommm@eeffAttettttt
-)),
and
LayerNozm(FFN(2) Z).
Following Dai et al. (011)). we use relative positional encodings at each layer, as well as cache mechanism, to make the processing of long sequences more efficient. the following, we will refer to this model as Transformer-XI. We refer the reader to Vaswani et al. (2017a) and Dnd et al. (2019) for a more detailed introduction to these models.
4.2 MODIFICATIONS TO THE TRANSFORMER XL MODEL
We propose several modifications the Transformer-X XI. model that found to improve the compression rate empirically. First, we follow Devlin et al. (2018) and use the GELU activation of Hendryckk & Gimpel| (2016) instead of ReLUs. Second.
opposed to Transformer-XL. (Dai) ct al. 2019), we do not use Adaptive Inputs (Baevski & Auli 2018) to tie the weights of embeddings and the classifier. Finally,
use different attention span size across all layers was suggested by Sukhbaatar et al.] (2019a). In particular, an observation from this work is that attention span can be short in the first half of the network while it has be longer in the last layers. We exploit this observation by restricting the attention span of the first layers of the Transformer and is extended linearly with the depth. More specifically, we restrict the attention size of the first layers to be equal to 6 x k for the k-th layer.
4.3 ADDING G-GRAMS AS INPUT
We also propose to enrich the input of the transformer with n-gram information. More specifi- cally, time step the input of the model is all the n-grams for between 1 and N of the form
3

---

Under review as a conference paper at ICLR 2020
Method
BPC
Standard text compression
gzip -9
2.92
x2 -9
1.99
paq8hp12am
1.31
CMIX
1.20
Neural Network based compression
1stm- compress
1.65
Transformer Bellard 2019)
1,46
LSTM Bellard (2019
1.35
ours without revisit
1.33
ours with revisit
1.20
Table 1: Compression rate enwik8 for different methods
Tt-n++l Ur. Concretely, have an embedding vector for each regram, and for given time step, we average the vectors corresponding to the n--rams of different lengths. For large n, there many rare n-grams, leading an important increase of parameters and memory consumption. A potential solution would be to only keep the most frequent ones, but this would require computing dictionary of n-grams and add it to the archive. Instead, we propose to hash the n-grams into fixed number of bins, allowing to constrain the memory requirement, without having to increase the size of the archive.
4.4 TRAINING WITH OR WITHOUU REVISITS
During the compression phase (resp. decompression), once token has been encoded (resp. de- coded), it can be used to update the probabilistic model. This means that compression using statis- tical models can be framed an online learning problem. Traditionally, previously encoded tokens are used only once to update the probabilistic model. However, nothing prevents re-using the tokens compute multiple updates of the model, besides memory consumption. Indeed, be able to do so, one needs to store the data being compressed to be able to revisit it. In the following we propose explore this strategy learn better probabilistic models based on transformer networks. The main motivation is that large overparametrized neural networks usually needs many passes over the data to trained. In practice, every F' compressed tokens, we re-use the last M compressed tokens to further train the network. This strategy will improve the quality of the probabilistic model, leading to better predictions and compression rate the data not yet processed. This phase is determined by the frequency of revisit F' and the number of tokens revisited M.
5 EXPERIMENTS
In this section, investigate the influence of different parameters the performance of our ap- proach. We also provide numerical evidence that purely neural based approach can be competitive with state-of-ther -he methods in terms of compression ratio.
5.1 IMPLEMENTATION DETAILS
Dataset. The standard dataset for text compression is enwik k8, notably used for the Hutter Prize. is composed of 100MB of English Wikipedia data. In the compression setting, we report the bit per character (BPC) obtained the first time visit each token of the full dataset. This differs from language modeling where we report the BPC on withheld data.
Preprocessing. We use the CMIX preprocessor where all uppercase letters converted to lower- case ones preceded by an escape code. This reduces the size of the vocabulary from 205 characters to 165 characters, while increasing the number of symbols by approximately 3% enwi 8
4

---

Under review as a conference paper at ICLR 2020
1.8
1.8
2.4
dim 256
dim-256
dim 256
1.7
dim-512
1.7
dim-$12
2.2
dim-512
Bit per character
dim-1024
dim-1024
2.0
dim-1024
1.6
1.6
1.8
1.5
1.5
1.6
1.4
1.4
1.4
1.2
o
1.3
1.3
1.0
10M
100M
12
18
0
20
40
60
80
100
Number of parameters (log scale)
Number of layers
Percentage of data
Figure I: Impact the model size on compression rate. We report the compression rate in BPC for transformer networks of various sizes. In particular, vary the number of layers (6, 12, 18, 24) as well as the dimension of each layer (256, 512, 1024). Left: we observe that on the full enw k8 dataset, larger models obtain better compression rate. Middle: using models deeper than 12 layers does not seem to improve the compression. Right: Instantaneous compression rate (averaged over the last million characters) for 12 layers models. Larger models obtain better performance, even at the beginning of compression.
Impact of Context Size
2.0
Bit per character
1.8
256
768
Context size
BPC
1.6
256
1.36
1.4
512
1.34
1.2
768
1.33
1.0
Compression rate the full enwik8 data for models with different context sizes.
Table 2:
20
40
60
80
100
Percentage of data
Figure 2: Instantaneous compression rate (averaged over the last million characters) for models with different context sizes.
Transformer. We consider Transformers with either 12, 18 24 layers, a hidden size d of either 256, 512 or 1024, and a number of heads between 4, 8 and 16. The dimension of the feedforward d 4d. We consider several size for the span, i.e., 256, 512 and 768. but in practice longer spans work better. The optimizer used to train the Transformer impacts greatly the compression ratio. Our best results were obtained with Adam optimizer Kingma Ba (2015) with the correction introduced in/Reddi et (2018) and its variant Adamw Loshchilov & Hutter (017). The impact of the different hyperparameters involved in these optimizer is investigated in the following subsections.
5.2 RESULTS
In table we summarize the performance obtained with transformer networks in this report. the fact that other approaches require the transmission of a dictionary to the decoder makes the comparison difficult: in most cases is not accounted in the performance although it can represent up to 400kb of uncompressed data. in order obtain comparison that makes sense, take into account the size the dictionary used in the different methods after compression with gzip -9. the code used train the different networks also needs to be transmitted the decoder, but its size negligible.

---

Under review as a conference paper at ICLR 2020
Fixed Learning Rate
Learning Rate Schedules
2.0
2.0
LR=2e-5
Fixed LR
1.8
1.8
Bit per character
LR=5e-5
Bit per character
Linear LR
LR=le-4
1.6
1.6
1.4
1.4
1.2
1.2
1.0
1.0
0
20
40
60
80
100
0
20
40
60
80
100
Percentage of data
Percentage of data
Figure 3: Instantancous compression rate (averaged over the last 1 million characters) for different fixed learning rates (left) and linear decay schedule (right). We observe that higher learning rates get better compression rate at the beginning of the compression phase, but lower learning rates tend to obtain better results at the end. A linear decay schedule allows to match the best performing fixed learning rate most steps of the compression.
5.3 IMPACT OF THE NUMBER OF PARAMETERS
First, we investigate the influence of the model size, well as its depth and layer dimension, on the compression rate. In many previous work, it has been observed that large overparametrized models lead ofate-of-the-ar performance. For example, Vaswani et al. (2017b) notice that large transformers with up to 160M parameters obtain better results than smaller networks. Similarly, for language modeling, Dai et al. (2019); Sukhbaatar et al. (2019)); Radford et al. (2019) present better results with larger networks. However, our online learning setting is different from these works, and natural question is whether this observation also true for compression. More specifically, could be possible that smaller networks would learn faster, as less parameters needs to be trained.
In Figure I we report the compression rate on enwik8 obtained by transformers of various sizes. The rest of the parameters, such as the optimization parameters, are identical for all runs and are close to the best we have found. First, we observe that, as in the supervised learning setting, larger models do obtain better performance. In particular, best model was also the largest one, contain- ing almost 350M parameters.
More surprisingly, larger models also obtained better compression ratio, of the compression phase. In Figure we also report the BPC averaged over the last 1M characters processed by the model (instantancous compression rate). We compare three networks made of 12 layers: small network with 4 heads, a hidden state of dimension d = 256, medium network, with 8 heads and a hidden state of dimension 512 and finally, large network, with 16 heads and hidden state of dimension 1024. Even after processing only one percent of the data, the large model have a better compression rate than the small and medium models.
the very beginning
Finally, we study the influence of the depth of the network on the compression rate. In Figure I we report results obtained by networks of various depths, all the other dimensions being equal. Here, we observe that using models deeper than 12 layers do not really improve the compression rate. In particular, as opposed to other sequence modeling tasks, it seems more efficient to consider wider networks than deeper ones, for constant number of parameters.
5.4 IMPACT OF THE CONTEXT SIZE
The size of the context in transformer networks determines the maximum number of previous hidden states the model obtained by using different context sizes, from 256 to 768. We show that larger context size results in better performance overall. A larger memory provides to the network more information, but it
predict the next symbol. In Table 2 compare the compression rate

---

Under review as a conference paper at ICLR 2020
Learning rate
Beta Parameter
1.7
Bit Bit per char.
1.42
warmup=1.25%
1.40
1.38
Bit per character
1.6
warmup=0.25%
1.36
1.34
0.0
0.2
0.4
0.6
0.8
1.0
1.5
Gradient Clipping
Bit per char.
1.42
1.4
1.40
1.38
1.36
1.34
1.3
le-5
Se-5
le44
0.0
0.2
0.4
0.6
0.8
1.0
Figure Impact of different optimization parameters. Left: we report the BPC over the full enwi data for different learning rate with linear decay and number of warmup steps. Top right: small 81 values for ADAM variants lead to better compression rate on the full enwik8. Bottom right: as for supervised learning, gradient clipping is helpful in the compression setup.
could also be more difficult to exploit: the most useful information to predict the next character is usually located in the few preceding characters. In particular, we observe that at the beginning the compression phase, models with shorter contexts tend to perform better. To illustrate this, we report in Figure instantaneous BPC for models with context sizes 256 and 768. Finally, is important to note that the computation time and the memory scale linearly with the size of the context.
5.5 IMPACT OF THE LEARNING RATE SCHEDULE
In general, the learning rate is parameter having an important influence on the convergence speed of neural networks. In Figure
report the compression rate, averaged over the last one mil- lion characters, obtained by using different fixed learning rate with the AMSGrad algorithm. As expected, higher learning rate leads to better compression rate at the beginning of the run, but smaller learning seems important to obtain good performance at the end of the compression phase. linear decay schedule, such that the learning rate is
In order have the best of both worlds, equal to zero at the end of the compression phase. In Figure 3 we observe that this scheme outper- forms fixed learning rate schedules over most of the compression. Overall, the best fixed learning rate leads to compression rate of 1.38 BPC, while linear decay get to 1. 1.36 BPC.
a warmup phase at the beginning of learn- ing, during which the learning rate increases from zero to its peak value (Vaswani et al. 2017b). We follow this practice, meaning that our linear learning schedule is determined by two parameters: the peak learning rate and the length of the warump phase. We report the influence of these two parameters on the overall compression rate in Figure 4 It appears that longer warmup phase is detrimental to the performance of transformer based data compression.
When training transformers, is standard practice
5.6 OTHER OPTIMIZER PARAMETERS
Finally we found that the compression ratio sensitive the optimizer parameters. In this section, we evaluate the impact of the following parameters of the Adam optimizer: B1, B2 and We report the BPC over the full enwik8 data for different values of 3, in Figure The fact that small 3 give usually, values close 1.0 are used. For example, the default 31 value in Py Porch is 0.9, and gives a compression rate of 1.39 BPC, compared to 1.36 for the optimal value of $1. On the other hand, found the 3g and parameters to have little influence the compression rate, and standard values to give the best results. Finally, Figure 4 shows that gradient clipping is helpful, but the performance are not very sensitive its value.
the best results is surprising,

---

Under review as a conference paper at ICLR 2020
1.8
Bit per character
1.7
no ngram
1.6
1.5
4 4-gram
Kmax
Number of vectors
BPC
1.4
20k
1.337
1.3
1.2
4
50k
1.337
1.1
3
80k
1.334
1.0
4
80k
1.335
20
40
60
80
100
No n-gram information
1.360
Percentage of data
Figure 6: Compression ratio depending on kmax and the number of vectors used to represent the n-grams
Figure 5: Instantaneous compression rate (averaged over the last I million characters) for models with and without n-grams. We observe that adding n-gram in- formation lead to better compression rate for the whole compression phase.
5.7 IMPACT OF PREPROCESSING AND n-GRAMS
We only apply minimal preprocessing step to the data, consisting in replacing uppercase characters by lowercase ones, with an additional escape code. This simple step, also used by other compression algorithms such as CMIX, leads to an improvement of 0.01 BPC. We also considered adding n-gram information to the input of the transformer model. At each time step f, the input corresponds to the current character, as well as the n-grams ending at position t. To avoid storing dictionary of n-grams in the archive, being associated to a learned embedding vector. We report the effect of adding n-grams Table 6 and Figure We show that adding this information lead to improvement of 0.025 BPC, and this improvement can still be observed at the end of the compression phase. By combining the optimal parameters derived from the different experiments reported in this section, enwik8 using 1.33 bits per character. While this is far from the performance of CMIX, it improves previous results obtained with transformer networks (Bellard 2019).
instead hash the n-grams into
fixed number of bins, each bin
compress
5.8 IMPACT OF REVISITING DATA
Finally, we study the impact of revisiting data already compressed, to improve the quality of the model and its predictions on data be processed. Overall, this is a critical strategy that allows to improve the compression rate from 1.33 BPC to 1 1.20 BPC, for the full enwik8 dataset. For this, every 512k compressed characters, we re-use the last 12.8M characters with batch size of 32 to further train the network. During the revisit phase, we use dropout regularization, with rate of = 0.25, so that the model does not overfit the past data, Introducing the use of dropout during the revisit improves the compression rate by approximately 0.05 BPC.
CONCLUSION
In this paper, we explore the application of transformer networks to the problem of lossless data compression, which is closely related to the online learning of sequence models. One challenge of using large neural networks to this task is the fact that many passes over the data are usually required to train them. We thus propose to periodically revisit tokens that were already compressed to further train the model, and improve its predictions. We also perform a thorough study the impact of various papre-parameters, such the model architecture, the compression rate. Based on this study, we show that a transformer based approach obtains state-of-the-ee results on the competitive enwi i 88 benchmark, without using hand crafted features.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. arXiv preprint arXiv:1809. 10853, 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.044: 409.044,, 2014.
Fabrice Bellard. Lossless data compression with neural networks. 2019.
URL https: //
bellard. wwtp:///......c//.......op pdf
Fabrice Bellard. Lossless data compression with neural networks. 2019.
John Cleary and Ian Witten. Data compression using adaptive coding and partial string matching. IEEE transactions on Communications, 32(4):396-402, 1984.
John G Cleary and William J Teahan. Unbounded length contexts for ppm. The Computer Journal,
1997.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoe V. Le, and Ruslan Salakhut- dinov. Transformer-xl: Attentive language models beyond fixed-length context. CoRR, abs/1901.02260, 2019.
Jacob Devlin, Ming- bidirectional transformers for language understanding. arXiv preprint ,rXI1v1881.004805 2018.
Beig-Wei&o Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
Jarek Duda. Asymmetric numeral systems. CoRR, 0aaa000992..27,,20000 2009. URL http://arxiv. orq/ exq/abs/De 0902. 0271
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):199-211, 1990.
Jan Gasthaus, Frank Wood, and Yee Whye Teh. Lossless compression hased on the sequence mem- oizer. In 2010 Data Compression Conference, pp. 337-345. IEBE, 2010.
Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
David Huffman. A method for the construction of minimum-rrdundancy codes. Proceedings of the Institute of Radio Engineers, 40(9): September 1952a.
David A Huffman. A method for the construction of minimum codes. Proceedings of the IRE, 1099):1088-110 1952b.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Truck Proceedings, 2015.
Byron Knoll. CMIX version 17. 2014. URL htt.ittt://ww.bgcnnnoolll.. com/ ct/ccmixxcc/ html
Byron Knoll. 1stmmccompress: data compression using LSTM. 2015. URL https://
Byron Knoll and Nando de Freitas. A machine learning perspective predictive coding with PAQ
CoRR, abs/1 108.3298, 2011. URL uttpatt:://axxi..co wwwpr///aaa//l1/ /tt///11.... 3298
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization adam.
CoRR,
abs/1711.05101, 2017.
hbcp://b//11 hbtp/aass/1111 05101
Matthew Mahoney. Adaptive weighing of context models for lossless data compression. Florida Tech. Technical Report, 2005.
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. In Proc. of WMT, 2018

---

Under review as a conference paper at ICLR 2020
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. 2019.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. /RLLhhtpp///ppeeeviiee
ri- net/forue ftrt:/ooum?ii 2id r-tuff-uuuuuuu RZ
Jorma Rissanen and Glen G Langdon. Arithmetic coding. IBM Journal of research and development, 23(2):149-16)) 1979.
David Salomon and Giovanni Motta. Handbook of data compression. Springer Science & Business Media, 2010.
C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(3): 379-423, 1948. doi: 10.1002/j.1538-73355 11009)..1588733511948.611111 1948..b01338.x.
Dmitry Shkarin. Ppm: One step to practicality. In Proceedings DCC 2002. Data Compression Conference, pp. 202-211. IEEE, 2002.
Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention span in transformers. In Proceedings of the 57th Conference the Association for Computational Linguistics, 2019, Florence, Italy, July 28- August 2. 2019, Volume 1: Long Papers, pp. 331- 335, 2019a.
Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention span in transformers. arXiv preprint arXiv: 1rXXiv1905.07799 2019b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, pp. 5998-6008, 2017a.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Infor- mation Processing Systems 30, pp. 5998-6008 2017b. URL httt::ttpppppeeee cwtess.nisscc.mm ce/ itt.:nttoo-ttteeeinnnnoo all-you- need.
Joel Veness, Tor Lattimore, Avishkar Bhoopchand, Agnieszka Grabska- Barwinsa, Christo- pher Mattern, and Peter Toth. Online learning with gated linear networks. arXiv preprint arXiv: 2017.
Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520-540, June 1987a.
Ian H Witten, Radford M Neal, and JG LCEARY. Arithmetic coding for data compression. Com- munications the ACM, 3006):20--540, 1987b.
Frank Wood, Cédric Archambeau, Jan Gasthaus, Lancelot James, and Yee whye Teh. stochastic memoizer for sequence data. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1129-1136. ACM, 2009.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. Xlnet: Generalized autoregressive pretraining for language understanding. CoRR, abs/1906.082377, 2019. URL httphh/t//aaa org/ www.aa//..................e...we 1901.082377777777 08237
10


Reviews:
[{"review_id": "r1eFrDP19S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a method for lossless compression of text. It's heavily inspired by the language modelling methods that have been developed for the purposes of predicting the next character/word in a sentence, and it uses this idea as its backbone. The only difference is that the results are presented in the compression setting.\n\nI think we should reject this paper due to the following reasons:\n- I don't see enough of a difference between this and previous work\n- the results are nowhere near SoTA for compression, despite the method being sold to this community\n- there are other papers that do lossless neural compression that could have been used to make a comparison rather than making no comparison at all. For example, \"Practical Full Resolution Learned Lossless Image Compression\" (CVPR 2019) provides a framework for image rather than text, but that could be adapted to this field without any major changes (predict convolutionally characters, rather than RGB values).\n- there's no comparison even with BERT (how well it do to predict the next character vs. this)...\n- no runtime numbers\n- no reproducibility discussion (i.e., how can I guarantee that my decoder can get exactly the same numbers as my encoder so that I can decompress on a different machine)\n- no discussion about whether files were created/decompressed (this is ABSOLUTELY CRUCIAL for compression papers to discuss)\n\nOverall, I am not excited about this paper, and unless the authors put a lot more into it, there's just not enough novelty to justify a publication at ICLR.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HklOX_jl5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThis paper explores the effectiveness of the Transformer architecture to the lossless data compression problem.\nIt also proposes a method to periodically revisit tokens that were already compressed for adopting the task setting of data compression, which is essentially online learning of sequence models. \n \nThe authors conduct their experiments on the enwik8 benchmark.\nThey show that the Transformer architecture obtains state-of-the-art results.\n \nThis paper is basically easy to follow, but several typos and statements that should be improved.\nThe problem setting to tackle is interesting.\nHowever, applying a deep neural network approach to data compression problem has already been discussed in several previous studies.\nTherefore, the novelty of this paper is somewhat limited.\n \n \nMy main concern of this paper is that the proposed method was only evaluated on a single benchmark data.\nI believe that it is a bit weak to support the effectiveness of the proposed method.\nThe authors should evaluate their method on several benchmark datasets that have different aspects, such as settings with easy and hard to compress. \n \n \nMinor comment:\nIn Section 4.2, there is a missing citation.\n... we do not use Adaptive Inputs (Baevski & Auli, 2018; ?) ...\nPlease check and fix it.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BkeZpB56FH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe paper investigates using the transformer architecture for neural network-based lossless compression of text. The resulting model, obtained through a thorough investigation of the architecture hyper-parameters are on par with standard SOTA compression. The paper is well-written. In particular the authors have done a great job reviewing existing compression literature and positioning their method within the space of prior work.\n\nRecommendation: Weak Reject\nWhile the paper considers an interesting application of the Transformer architecture, and is well-written, it is of limited novelty. Specifically, the bulk of the paper is concerned with describing experimental results of a thorough (but standard) hyper-parameter search - considering things like Transformer context size, learning rate (schedule), number of layers and key, value, query dimensionality; and does not offer any new architectural modifications / insights.\n\nFurthermore, only a single dataset - enwik8 - is considered in the experimental validation and little attention is given to the description of the dataset split and any distribution differences between splits. Taken together, the existing experimental setup potentially creates an unfair advantage for the neural network-based methods - while the standard methods can be expected to perform similarly across a wide range of datasets / texts, the neural-network based methods have been trained and tested on very similar data and could be expected to perform well on these data, but not in case of a distributional shift (e.g. compressing legal texts instead of Wikipedia). The paper does not answer the question of whether or not this is true.\n\nFurthermore, similar to autoregressive models, transformers are known to be slow at inference time. I expect this to lead to very slow decoding. Therefore, methods in table 1 should be compared in compression/decompression time to give a better overview of the practical impact of this work. \n\nTaken together, in its current form the paper may be better suited for a workshop publication rather than a full conference paper.\n\nMajor comments:\n1. For reasons mentioned above, the paper should include additional experimental evaluation. In particular, it should consider the effect of training the model on one dataset, but evaluating it on another dataset; and discuss how differences in performance (if any) compare to standard methods.\n2. Compression/decompression times of the proposed method should be compared against the other compression methods in table 1. I expect the proposed transformer to be slow at decompressing.\n3. The paper does not contain the loss that the transformer model was used to optimize. I assume that it is the softmax cross entropy, but this is worth mentioning explicitly. It would also be worthwhile to explain the training procedure - for how many epochs was the model trained (see also next question), what was the dataset size? \n4. Description of the “training with revisits” is not very clear. My understanding is that it resembles a pass through the data, where some of it is considered again at specific intervals. My first assessment is that this should not be necessary - the data should already be considered multiple times during the training process.\na) The authors should provide a more detailed description of the training-with-revisits procedure, contrasting it specifically with a procedure where revisits are not done (i.e. normal training).\nb) If the goal of the revisits training is to observe some training examples more than once, then it would be very interesting if simply training for a longer time (several epochs == passes through the data) has a similar effect.\nc) Is there any motivation for the choice of the revisits hyper-parameters F and M? Was a different batch size used during the revisits training? Is the learning rate evolved during the revisits training phase or is it still decayed?\n\nMinor comments:\n1. There is some prior work on using Neural Networks for lossless image compression (e.g. [1], [2]. [3] that achieves SOTA compression ratios compared to standard methods. It may be interesting for the readers to mention these results. In particular the authors’ statement that “[...] purely neural network based models are still far from state of the art [...]” may give the wrong impression to the readers.\n2. The authors mention that they “[...] propose several improvements to its (the Transformer) architecture and training to accelerate and stabilize [...] training”. In my view, the experiments described in the paper resemble a hyper-parameter search more than architectural improvements. The authors may want to clarify in the text which specific improvements they refer to.\n3. Page 1, last paragraph: “[...] of all the important component [...]” -> “[...] of all the important components [...]”\n4. Page 3: “[...] attention span size across all layers as it suggested [...]” -> “[...] attention span size across all layers as was suggested [...]”\n5. Page 3: Missing references.\n6. Page 3: Use of small n and capital N when talking about n-grams. Should be made consistent.\n7. Page 8 (Conclusion): “wihtout” -> “without”\n\n\n[1] F. H. Kingma, P. Abbeel, and J. Ho. Bit-Swap: recursive bits-back coding for lossless compression with hierarchical latent variables. In International Conference on Machine Learning (ICML), 2019.\n[2] Emiel Hoogeboom, Jorn W. T. Peters, Rianne van den Berg, and Max Welling. Integer Discrete Flows and Lossless Compression. arXiv e-prints, 2019.\n[3] Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with Flows via Local Bits-Back Coding. arXiv e-prints, 2019.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to use transformers to do lossless data compression. The idea is simple and straightforward (with adding n-gram inputs). The initial submission considered one dataset, a new dataset was added in the rebuttal. Still, there is no runtime in the experiments (and Transformers can take a lot of time to train). Since this is more an experimental paper, this is crucial (and the improvements reports are very small and it is difficult to judge if there are significant).
Overall, there was a positive discussion between the authors and the reviewers. The reviewers commented that concerns have been addressed, but did not change the evaluation which is  unanimous reject.  
Decision: Reject