AriEL: Volume Coding for Sentence Generation Comparisons
Authors: Luca Celotti
Simon Brodeur
Jean Rouat
Venue:  (2021)

Abstract: Mapping sequences of discrete data to a point in a continuous space makes it difficult to retrieve those sequences via random sampling. Mapping the input to a volume would make it easier to retrieve at test time, and that is the strategy followed by the family of approaches based on Variational Autoencoder. However the fact that they are at the same time optimizing for prediction and for smoothness of representation, forces them to trade-off between the two. We benchmark the performance of some of the standard methods in deep learning to generate sentences by uniformly sampling a continuous space. We do it by proposing AriEL, that constructs volumes in a continuous space, without the need of encouraging the creation of volumes through the loss function. We first benchmark on a toy grammar, that allows to automatically evaluate the language learned and generated by the models. Then, we benchmark on a real dataset of human dialogues. Our results indicate that the random access to the stored information can be significantly improved, since our method AriEL is able to generate a wider variety of correct language by randomly sampling the latent space. VAE follows in performance for the toy dataset while, AE and Transformer follow for the real dataset. This partially supports the hypothesis that encoding information into volumes instead of into points, leads to improved retrieval of learned information with random sampling. We hope this analysis can clarify directions to lead to better generators.

Under review as a conference paper at ICLR 2021
ARIEL: VOLUME CODING FOR SENTENCE GENERATION COMPARISONS
Anonymous authors Paper under double-blind review
ABSTRACT
Mapping sequences of discrete data to a point in a continuous space makes it dif- ficult to retrieve those sequences via random sampling. Mapping the input to a volume would make easier to retrieve at test time, and that is the strategy fol- lowed by the family of approaches based on Variational Autoencoder. However the fact that they are at the same time optimizing for prediction and for smooth- ness of representation, forces them to trade-off between the two. We benchmark the performance of some of the standard methods in deep learning to generate sen- tences by uniformly sampling continuous space. We do it by proposing AriEL, that constructs volumes in a continuous space, without the need of encouraging the creation of volumes through the loss function. We first benchmark grammar, that allows to automatically evaluate the language learned and generated by the models. Then, we benchmark on real dataset of human dialogues. Our re- sults indicate that the random access to the stored information can be significantly improved, since our method AriEL is able generate wider variety of correct language by randomly sampling the latent space. VAE follows in performance for the toy dataset while, AE and Transformer follow for the real dataset. This partially supports the hypothesis that encoding information into volumes instead of into points, leads improved retrieval of learned information with random sampling. We hope this analysis can clarify directions to lead to better generators.
a toy
INTRODUCTION
It is standard for neural networks map an input a point in d-dimensional real space (Hochre- iter and Schmidhuber, 1997; Vaswani et al., 2017; LeCun et al., 1989). However, that makes difficult to find specific point when the real space is being sampled randomly. That can limit the applicability of pre-trained models to their initial scope. Some approaches do map an input into volumes in the latent space. The family of approaches that stems out of the idea of Variational Au- toencoders (Kingma and Welling, 2014; Bowman et al., 2016; Rezende and Mohamed, 2015; Chen al., 2018) are trained to encourage such type of representations. By encoding an input into a prob- ability distribution that is sampled before decoding, several neighbouring points in RR can end up representing the same input. However, often implies having two summands the loss, log-prior term and a log- likeliieehood term (Kingma and Welling, 2014; Bowman et al., 2016), that fight for two different causes. In fact, if we want a smooth and volumetric representation, encouraged by the log-prios it might come the cost of having worse reconstruction or classification, encouraged by the log-likelihood. Therefore, each diminishes the strength and influence of the other.
By giving partially up the smoothness of the representation, we propose instead method to explicitly construct volumes, without a loss that is implicitly encouraging such behavior. We pro- pose AriEL, a method map sentences volumes in Rd for efficient retrieval with either random sampling, or a network that operates in its continuous space. It draws inspiration from arithmetic coding (AC) (Elias and Abramson, 1963) and k-d trees (KdT) (Bentley, 1975), and we name it after them Arithmetic coding and k-d trEes for Language (AriEL). For simplicity we choose to focus on language, even though the technique applicable for the coding of any variable length sequence of discrete symbols. More precisely, we plan to use AriEL in the context of dialogue systems with the goal to provide a tool to optimize interactive agents. The interaction of AriEL with longer text is left as future work.

---

Under review as a conference paper at ICLR 2021
In particular, it can be used as an objective benchmark to compare other methods and to understand how their latent space used. AriEL attempts to fill completely the latent space with the sentences present in the training dataset, using notions from information theory. AriEL uses language model to split the latent space in volumes guided by the probability assigned to the next symbol a sentence. For this reason, it can simplify as well the reuse of pretrained language models for new tasks and in larger architectures. In fact, can provide a training agent with a simpler interface with language model, e.g. GPT-2 (Radford et al., 2019), where the agent could choose the optimal dimensionality of the interwface. We prove how such a volume representation eases the retrieval of stored learned patterns and how use to set references for other models.
Our contributions are therefore:
AriEL, a volume coding technique based on arithmetic coding and k-d trees (Section 3.1), to improve the retrieval of learned patterns with random sampling;
the use of context-free grammar and random bias in the dataset (Section 3.3), that allows us to automatically quantify the quality of the generated language;
the notion that explicit volume coding (Section and 5) can be a useful technique in tasks that involve the generation of sequences of discrete symbols, such as sentences.
RELATED WORK
Volume codes: We define volume code as a pair of functions, encoder and decoder func- tions, where the encoder maps an input x into set that contains compact and connected sets of R (Munkres, 2018), and the decoder maps every point within that set back to x. It is form of distributed representations (Hinton et al., 1984) since the latter only assumes that the input will be represented as a point in Rdd We define point codes as the distributed representations that are not volume codes. Volume codes differ from coarse coding (Hinton et al., 1984) since in this case the code represented by a list of zeros and ones that identifies in which overlapping sets x falls into. We call implicit volume codes, when the volume code is encouraged through a term in the loss func- tion
Both generative and discriminative models (Ng and Jordan, 2002; Kingma and Welling, 2014; Jebara, 2012) can Icarn volume codes this way. We call explicit volume code, when the volumes are constructed instead through the operations that define the architecture, and are created independently from any loss and optimizer choice.
Sentence generation through random sampling: Generative Adversarial Networks (GAN)
(Goodfellow et al., 2014) map random samples to a learned generation through 2-players game training procedure. They have had trouble for text generation, due to the non differentiability of the orgmaa at the end of the generator, and given that partially generated sequences are triv- ial to score (Yu et al., 2017). Several advances have significantly improved their performance for text generation, such as using the generator as a reinforcement learning agent trained through Pol- icy Gradient (Yu et al., 2017), avoiding binary classification in favor of a cross-entropy for the discriminator that evaluates each word generated (Xu et al., 2018), or with the Gumbel-Softmax distribution (Kusner and Hernández-Lobato, 2016). Random sampling the latent space is used as well by Variational Autoencoders (VAE) (Kingma and Welling, 2014), to smooth the representation of the learned patterns. Training VAE for text has been shown to be possible with KL annealing and word dropout (Bowman et al., 2016), and made easier with convolutional decoders (Severyn et al., 2017: Yang al., 2017). Several works explore how VAE and GAN can be combined (Makhzani et al., 2015; Tolstikhin et al., 2017; Mescheder et al., 2017). AriEL can be used as a generator or a discriminator in GAN, as encoder decoder in autoencoder. However it differs from them in the explicit procedure to construct volumes in the latent space that correspond to different inputs. The intention is to fill the entire latent space with the learned patterns, to ease the retrieval by uniform random sampling.
Arithmetic coding and neural networks: AC is one of the most efficient lossless data compression techniques (Witten et al., 1987; Elias and Abramson, 1963). AC assigns a sequence to a segment in [0.1] whose length is proportional to its frequency in the dataset. AC used for neural network compression (Wiedemann et al., 2019) but typically, neural networks are used in AC as the model of the data distribution, to perform prediction based compression (Pasero and Montuori, 2003; Tri- antafyllidis and Strintzis, 2002; Jiang et al., 1993; Ma et al., 2019; Tatwawadi, 2018). We turn AC

---

Under review as a conference paper at ICLR 2021
into compression algorithm in d real numbers, to combine its properties with the properties of high-dimensional spaces, which the domain of neural networks.
K-d trees and neural networks: KdT (Bentley. 1975) is a data structure for storage that can handle different types of queries efficiently. is typically used bours in low dimensions (Friedman et al., 1977). It gives binary label to the data with respect to its median. moves through the k dimensions of the data and repeats the process. Neural networks typically used in conjuction with KdT to reduce the dimensionality of the search space, for KdT to be able to perform queries efficiently (Woodbridge et al., 2018; Yin et al., 2017; Vasudevan et al., 2009). KdT has been used as well in combination with Delaunay triangulation for function learning, as an alternative to NN with Backpropagation (Gross, 1995). A KdT inspired algorithm is used in (Maillard and Solaiman, 1994) guide the creation of neurons grow neural network. We use KdT to make sure that when we make AC turn multidimensional, it makes use of all the space available.
fast approximation k-nearest neigh-
METHODOLOGY
3.1 ARIEL: VOLUME CODING OF LANGUAGE IN CONTINUOUS SPACES
Figure 1: Sentence embedding with arith- metic coding and AriEL. In this example, the generating context-fres grammar (CFG) is S + A B AAAAB|ACT ACCCCCA ACCBCCC and the bar plot on top indicates the fre- quency of those sentences in the dataset, as an extra bias to the language. AC (middle) encodes any sequence of this CFG over a single dimension within [0. 1], and the fre- quency of the sentence determines the length assigned on that segment. AriEL is mul- tidimensional extension of AC (here in 2D), where the frequency information is preserved in the volumes. The Language Model pro- vides the boundaries where the next sym- bols are to be found. For a 2D latent space, d 2, the axis split to find symbol 8; is d2 i mod d. In the image d; = 0 and d represent the horizontal and vertical axis.
| |BCC
grammar and blas
AA
ABC
BCC
Arithmetic Coding
B
B
D
D
A
AA
A8
AC
AA
AB
AC
d, mod
= mod 6,
d, mod
d,= 1
d, =
AriEL
AriEL maps the sentence (s1,-.., ,8)) to a dddimensional volume of P((s).... 8n)) P(s (s)))<). The sentence is encoded as the center of that volume for simplicity, and any point within it is decoded to the same sentence. Decoding iteratively computes the bounds of the volumes for all possible next symbols and checks inside which bounds the vector is, to find the next symbol at each step. The algorithm is described in detail in the Supplementary Material.
To adapt KdT to more splits than binary, split the chosen dimension giving a space from 0 to 1 to each possible next symbol, proportional to its probability. The first symbol in the sentence will be assigned segment of length P(si) in the first axis chosen di, and next symbols will be assigned a segment proportional to their probability conditional to the symbols previously seen e.g. P(sal(52. (52, $1)) on the axis dg, where $1, 82 and 8y are the first three symbols in the sentence. Then we turn to the following axis and continue the process of splitting and turning (figure 1). We select the next axis in Rd to split to be d, the sequence. If n is larger than the dimension d, then the segment in d, is split again. We applied a neural network approximate the true statisties of the data P(s;((s;))e the Language Model (LM) of AriEL, Pta (sx (s)))s))))) This will approximate the frequency information that makes
mod d, where E 11...... n) and n the length of
3

---

Under review as a conference paper at ICLR 2021
AC entropically efficient since after successful training, (+) will converge to P(.). AriEL. conserves then the arithmetic coding property of assigning larger volume to frequent sentences.
AriEL only uses a bounded region of R the interval [0, 1J", so encoder and decoder map each input to a compact set and from a compact set. Moreover, they assign sequence to a hyper- rectangle (Johnson, 2018) and back. Since hyper-rectangles cannot be divided into two disjoint non- empty closed sets, they are connected (Munkres, 2018). Therefore AriEL, a volume code. AriEL, is explicit volume code since its LM is trained only next word prediction log- lig-liieldhoo loss, without regularization term that encourages smoothness, and the volumes are constructed by arranging the softmax outputs into d dimensional grid, operation performed with any choice of loss or optimizer.
AriEL with RNN-based language model has computational complexity of O for both encoding and decoding, as it can be seen in algorithms and 2, where ni is the length of the sequence and D is the dimensionality of the RNN hidden state. We use capital D to refer to the length of the longest hidden layer among the recurrent layers in the encoder or in the decoder, while d refers to the length of the latent space. AriEL has minimum number of sequential operations of (n) for both encoding and decoding, which is on par with conventional recurrent networks for seq2seq learning.
3.2 NEURAL NETWORKS: MODELS AND EXPERIMENTAL CONDITIONS
We compare AriEL to some of the classical approaches to map variable length discrete spaces to fixed length continuous spaces. These are the sequence to sequence recurrent autoencoders (AE) (Sutskever et al., 2014), their variational version (VAE) (Bowman et al., 2016) and Tranformer (Vaswani al., 2017). We trained them for next word prediction of word 8i, when all the previous words are given as input, and they are trained over the biased train set, defined in section 3.3. All of them can be split into an encoder that maps the sentences the input into Ed and a decoder that maps back from IRd into sentence. More training details can be found in the appendix.
In this work, AriEL's language model neural network PLM consists of a word embedding of size 64, followed by 140-unit LSTM, feedforward layer and softmax over next possible symbols. At test time the argmax is not applied directly to the softmax, but the latent space point is used as the deterministic pointer that chooses the position in cumulative sum of the softmax probabilities. However the language model trained for next time step prediction through cross-entropy. For both AE and VAE. we stack two GRU layers (Cho et al., 2014) with 128 units at both, the encoder and the decoder, to increase their representational capabilities (Pascanu et al., 2014). Other recurrent networks gave similar results (Hochreiter and Schmidhuber, 1997; Li et al., 2018). The last encoder layer has either d = 16 units or = 512 for all methods. The decoder outputs a softmax over the entire vocabulary.
Tranformer (Vaswani et al., 2017) 1017)i is the state-of-the-art in many S2S problems (Vaswani et al., 2017: Dai et al., 2019; Radford al., 2018). Since it is a fixed-length representation at the word level but it is variable-length at the sentence level, we padded all sentences to the maximum length in the dataset to be able to compare its latent space capacity to the other models. We take as latent dimension the connection between the encoder and decoder, with d'modet size, that will take a value of 16 or 512. We choose most parameters as in the original work (Vaswani et al., 2017): the number of attention heads as Rhead 8, the key and value dimension dkey = 64 and deatue 64, a dropout regularization of 0.1, and we only change the stack of identical decoders and encoders to Mlayers 2. and the dimension of the inner feed-forward network to dinner layer 256 to have a number of parameters similar to the other methods. In the GuessWhat? dataset we tested Mlayers 20 to have amount of parameters comparable for d 16 to the other methods. but performed worse than Maayeer = 2, so we report the latter.
3.3 DATASETS: TOY AND HUMAN SENTENCES
We perform our analysis on two datasets. toy dataset of sentences generated from a context- free grammar (CFG) and realistic dataset of sentences written by humans playing a cooperative game.
The toy dataset: we generate questions about objects with CFG (appendix 1). To stress the learn- ing methods and understand their limits we choose a CFG with large vocabulary and numerous

---

Under review as a conference paper at ICLR 2021
grammar rules, rather than more classic alternatives (e.g. REBER). The intention is as well to focus on dialogue agents and that's 's the reason why all sentences are framed as questions about objects.
We distinguish between unbiased sentences, those that have been simply sampled from the CFG, and biased sentences, those that after being sampled from the CFG have been selected according to an additional structural constraint. To do so generate an adjacency matrix of words that can occur together in the same sentence, and we use that as the filter to bias the sentences. Once sentence is produced from the CFG, if all its words matrix, the sentence is considered as biased, and unbiased otherwise. For simplicity the adjacency matrix is random matrix of zeros and ones, generated only once for all the experiments, making sure that some symbols such as the, it or ?, can be found in both types of sentences. The intention is emulate the setting were CFG is constrained by realistic scenes, where not all the grammatically correct sentences are semantically correct: e.g. "Is it the wooden shower in the kitchen ?" could be grammatical, but semantically incorrect given that it is unusual in a realistic scene. We use it to detect how each learning method is able to extract the grammar and extract the roles of each word, despite a bias that makes it harder.
be together in sentence judged by the adjacency
The vocabulary consists of 840 words. The maximal and mean length of the sentences is of 19 and 9.9 symbols. We split the biased dataset into 1M train, 10k test and 512 validation sentences, where no sentence is shared between sets. We created another set of 10k unbiased test sentences with the same CFG, where we only gather sentences that do not follow the adjacency matrix, to make sure that the overlap of this test set is zero with previous ones. We train on the biased sentences and we test if they grasped the grammar behind, with the unbiased.
The real dataset: we choose the What?! dataset (De Vries et al., 2017), dataset of sentences asked by humans to humans to solve a cooperative game, It has a vocabulary of 10,469 words, an order of magnitude larger than the toy CFG. The maximal and mean length of the sentences are of 57 and 5.9 symbols.
3.4
EVALUATION METRICS
3.4.1 QUALITATIVE EVALUATIONS
The two qualitative studies are: (1) we list a few samples of reconstruction via next word prediction of unbiased sentences, to understand the generalization capabilities of the different models (table 1), (2) we list few samples of generated sentences when the latent space is sampled randomly, to understand the generation capabilities (table 2).
3.4.2 QUANTITATIVE EVALUATIONS ON THE TOY GRAMMAR, CFG
We propose measures for 3 properties of an autoencoder: the quality of generation, prediction and generalization. We perform our studies for networks with a latent dimension of 16 units, to under- stand their compression limits, and for 512 units, which is often taken as the default size (Kingma and Welling, 2014; Vaswani et al., 2017).
Generation/Decodine Quality is evaluated with sentences produced by the decoder when the latent space of each model is sampled randomly. The sampling is done uniformly in the continuous latent space, within the maximal hyper-cube defined by the encoded test sentences. We sample 10k sen- tences and apply four measures: i) grammar coverage (GC) as the number of grammar rules (e.g. single adjective, multiple adjectives) that could be parsed in the sampled sentences, maximal number of adjectives plus one for sentences without adjectives; ii) vocabulary coverage (VC) as the ratio between the number of words in the sampled sentences, over 840, the size of the complete vocabulary; iii) uniqueness (U) as a ratio of unique sampled sentences; and iv) validity (V) as a ratio of valid sampled sentences. sentences that were unique and grammatically correct. We keep our definition of grammar rule simple, for computational efficiency, and for clarity, given that the grammar tree defined with an ambiguous number of placeholders and terminal symbols.
four, the
Prediction Quality is evaluated by encoding and decoding the 10k biased test sentences as follows: i) prediction accuracy biased (PAB) as a ratio of correctly reconstructed sentences (i.e. all words must match); ii) grammar accuracy (GA) as ratio of grammatically correct reconstructions (i.e.
5

---

Under review as a conference paper at ICLR 2021
can be parsed by the CFG, even if the reconstruction is not accurate). and iii) bias accuracy (BA) as the ratio of inaccurate reconstructions that are still grammatical and keep the bias of the training set.
Generalization Quality is evaluated using the 10k unbiased test sentences while the embeddings were trained on the biased training set. The prediction accuracy unbiased (PAU) is computed in the same way as PAB, as the ratio of correctly reconstructed ubiased sentences. It allows us to measure how well the latent space generalizes to grammatically correct sentences outside the bias.
3.4.3 QUANTITATIVE EVALUATIONS ON THE REAL DATASET, GUESS
In a real dataset we don't t have a notion of what is grammatically correct, since humans can use spontaneously ungrammatical constructions. We quantified the quality of the language learned with two measures: imqqueness is the percentage of the sentences generated with random sampling that was unique over the 10K generations and validity was the percentage of the unique sentences that could be found in the training data, indicating how easy it was to retrieve the learned information.
3.4.4 QUANTITATIVE EVALUATIONS: RANDOM INTERPOLATIONS WITHIN ARIEL
In figure 2 show what call the interpolation diversity given the dimension of the latent space. measures how many of the sentences generated through a straight line between two random points in IR were unique and grammatically correct for AriEL for different values of d. The Language Model tested is the one trained on the toy grammar.
4 RESULTS
4.1 QUALITATIVE EVALUATIONS
We present the qualitative studies performed for d = 16. Table shows the output of the gener- alization study. To avoid cherry picking, we display the first 4 reconstructed sentences. AE and the unbiased language, however both manage to keep the structure at the
VAE fail to generalize output of the input sentence. Their behavior improved significantly when the latent space dimension is increased to d 512, with the corresponding increase of parameters. In theory, AriEL is able to reconstruct any sequence by design, by keeping a volume for each of them. However in practice, failed only slightly less often than the Transformer. Both produce reconstructions of the unbiased input at a similar rate, as it can be see table and in the metric PAU in table 3 and figure S2. This means that a reasonable degree, the areas that represent unseen data during training, are available and relatively easy to track for AriEL and Transformer. Instead, all the latent space seems to be taken almost exclusively by the content of the training set for AE and VAE, since sentences that are not seen during training (the unbiased sentences) cannot be reconstructed at all.
The generation study shown in Table 2 (first samples for each model). AriEL excels this task, and almost all generations are unique and grammatically correct (valid). AE and VAE perform remarkably well given the small latent space. As it is shown in the quantitative study, VAE almost triples AE performance in terms of generation of valid sentences when d = 16 (table 3). Transformer performs poorly at generating grammatical sentences when the latent space is sampled randomly. The quantitative analysis reveals however that with the increase of the latent space, Transformer, AE and VAE achieve all improved validity, remaining at one third the reference set by AriEL.
4.2 QUANTITATIVE EVALUATIONS
The results of the quantitative study are shown in table and in figure S2. AriEL outperforms or closely matches every other method for all the 8 measures, outperforming the rest by large margin for validity, i.e. unique and grammatical sentences generated, the most important of the metrics. Transformer performs remarkably well at not overfitting and it is able reconstruct biased and unbiased sentences better than the other non-AriEL methods, even under-parameternt manages to cover all grammar rules in generation but performs very poorly at generating diverse set of valid sentences by random sampling. It only needed one iteration through the data achieve almost perfect validation accuracy, without losing performance when we trained for the remaining 9 epochs. VAE 16 despite the poor generalization to the biased and the unbiased test set,
(d 16).

---

Under review as a conference paper at ICLR 2021
Input Sentences
thing this linen carpet made of tile?? ?
huge and teal the thing transparent. huge and slightly heavy?
is the object antique white. tiny and closed? ?
AriEL
is the object that tiny very light set is the thing tiny destroyable abstraction ?
AriEL
is the thing this lime carpet made of tile ?
is the thing this mint cream textured organic structure ?
is it huge and teachable
is the object this small large wearable textile ?
is the thing transparent, huge and slightly heavy? ?
Transformer
object antique white, tiny and closed
is the thing slightly heavy heavy stone squeezable
Transformer
closed sea heavy ?
the thing this stretchable carpet made of tile huge and magenta?
is pale lime executable executable shallow decoration drab turquoise. heavy and potang ?
is the thing transparent, huge and slightly heavy? ?
is it an tomato slot box made of decoration facing stone? ?
is the object antique white, tiny and closed? ?
is the thing short and spring heavy slightly heavy potang ?
AE
AE
is the thing this small toilet made of laminate ?
is the object that light light laminate ?
it this average-sized and average-sized laminate
is the thing light. small and small laminate" is the thing that tiny small decoration stone? is the object the average-sized, textured and averuge-sized laminate? ?
the thing very heavy. . heavy and very heavy? the object light pink, , small and textured?
VAE
VAE
is the thing small and textured deep stone ?
is the thing light and deep office ? is it light, light and light and pink ? is the object dark light and pink ?
is it the light deep bedroom
is the thing textured, textured and moderately heavy ? is the thing light, moderately heavy and light green?? ?
is the object light deep living room
Table I: Generalization: next word predic- tion of unbiased sentences at test time. An un- biased sentence is encoded and decoded by each model. Color means that the word was incor- rectly reconstructed. Blue means that the sen- tence complies with the bias and purple means that the incorrect reconstruction is still unbi- ased. Most reconstructions seem grammatically correct. In practice AriEL also made errors. Some of its failed reconstructions comply with the training bias, some do not. Transformer per- forms remarkably well, and interestingly the er- rors made tend to turn the unbiased input sen- tence into biased version the output. AE produced only biased sentences whose struc- ture resembled the unbiased ones. VAE behaved similarly, producing more unbiased sentences.
Table 2: Generation: output of the decoder when sampled uniformly in the latent space. Red defines grammatically incorrect genera- tions according to the CFG the models are trained on. AriEL produces an extremely varied set of grammatically correct sentences, most of which keep the bias of the training set. Trans- former reveals itself be hard to control via random sampling of the latent space, since it almost never produces correct sentences with this method. AE and VAE manage to produce several different sentences, the latter producing more non grammatical, but as well more varied grammatical ones.
results in the best non-AriEL generator, measured by validity. The conflict between oog-prior and log-lik logllikeihoodd, encouraged VAE to look for sentences outside the bias, since it was able to produce more grammatically correct sentences, albeit unbiased, than AE. Increasing the learned parameters (d 512), had effect Transformer, that was already excellent in several of the metrics, apart from a significant improvement in validity. However, a larger latent space and the increase in number of parameters that followed, prevented AE and VAE from overfitting (better PAU and PAB).
When trained on human sentences, on the Guess What?! dataset, AriEL sets again a large validity to be reached. Every approach seems to generate more unique sentences than AriEL, but the fraction of them that is good generation is very small. Less than 6% of the unique sentences generated by AE, VAE and Transformer are in the training set, while AriEL achieves 22. 22.47% and more.
In the interpolation diversity study (figure 2) we see that for low d, we have to pass through many sentences in between two random points in the latent space, while as we augment the dimensionality. we distribute the sentences in different directions. Therefore we find less sentences when we move on the straight line between two random points. The specific curve, lower threshold and speed of decay, will vary for different vocabulary sizes and given the complexity of the language learned.
7

---

Under review as a conference paper at ICLR 2021
Generation
Prediction
Generalization prediction accuracy
prediction accuracy biased
grammar coverage
vocabulary coverage
bias accuracy
grammar accuracy
param
validity
uniqueness
unbiased
d= 16
AriEL
237K
100.0 = 0.0%
70.4 = 0.2%
97.6 + 0.2%
99.7 0.1%
100.0 + 0.0%
100.0 + 0.0%
100.0 + 0.0%
53.1 + 0.4%
Transformer
258K
100.0 = 0.0%
70.1 = 0.8%
4.7 + 2.7%
99.1 0.5%
99.98 + 0.01%
99.95 + 0.02%
99.92 + 0.02%
49.0 + 0.1%
AE
258K
100.0 = 0.0%
6.89 = 0.7%
11.5 + 4.2%
13.9 5.1%
89.5 + 2.3%
98.0 + 1.7%
0.0 = 0.1%
0.0 0.1%
VAE
258K
100.0 0.0%
11.5 2.6%
16.0 + 9.2%
24.3 + 14.8%
85.4 + 5.2%
85.1 + 8.8%
0.0 0.1%
0.0 + 0.1%
512
AriEL
237K
100.0 = 0.0%
70.2 = 0.3%
97.9 + 0.2%
99.8 0.1%
100.0 0.0%
100.0 0.0%
100.0 0.0%
53.2 0.3%
Transformer
9M
100.0 = 0.0%
67.3 = 0.9%
17.2 + 6.3%
87.2 7.5%
99.99 + 0.01%
99.91 + 0.03%
99.86 + 0.05%
49.0 + 0.1%
AE
120M
100.0 = 0.0%
39.3 = 6.0%
21.0 + 11.8%
71.8 = 5.6%
82.2 + 3.5%
86.8 + 1.3%
34.7 = 11.4%
24.4 + 6.0%
VAE
120M
85.0 + 12.6%
28.9 = 2.4%
26.5 + 2.4%
95.2 = 3.8%
73.8 + 2.2%
89.5 + 2.8%
4,3 = 3.7%
4.9 = 3.6%
Table 3: Evaluation of continuous sentence embeddings on the toy dataset. Results for latent space of d = 16 and d = 512. Each experiment is rum 5 times. AriEL, achieves almost perfect performance in most metrics, especially validity, which quantifies how many random samples were decoded into a unique and grammatical sentence. Transformer performed exceptionally, except for validity. All methods improved their performance increasing d. particularly in validity, but still achieved less than one third the performance of AriEL. VAE is the second best in validity, supporting our hypothesis, that volume coding facilitates retrieval information by random sampling.
interpolation diversity
prediction accuracy
param
uniqueness
validity
16
AriEL
2,901K
92.56%
57.41%
29,59%
Transformer
588K
87.91%
96.75%
1.96%%
2.787K
11.97%
63.68%
2.67%
08-
VAE
2,787K
13.15%
6.26%
1.61%
latent dimemssio d
AriEL
2,901K
92.54%
$5. 55.46%
22.47 %
Transformer
5.94%
AE
4,900K
15.45%
12.4%
2.68%
Figure 2: Interpolations between random points in the latent space of AriEL, and diversity of the sentences generated in be- tween. For low dimensions all sentences are very densely packed, and in the extreme of one dimension, all sentences are found follow- ing one given dimension. As the dimensional- ity increases, the sentences are redistributed in [0, 1j and less sentences are found in given direction. The lower bound at 0.746 is related to the language complexity.
VAF:
5,425K
32,519:
98.51%
0.2%
Table 4: Performance on the What?! Questioner data. For the real dataset the pat- temn is repeated: AriEL shows that larger value of valid sentences is possible
Transformer 16 gave better results than when Alyyer was increased from 2 to 20 to increase its learnable parameters from 588K 2,666K.
5 DISCUSSION
AriEL latent space d is a free parameter. It is worth to stress that the size d of the latent space of AriEL can be defined at any time, for fixed Language Model. It could therefore be controlled with a learnable parameter, with the activity of another neuron, or as another function of the input. In fact, as we increase d, the volumes will have more neighbouring volumes that represent different sentences, confirmed by the interpolation study, figure 2. It could have implications as well during training e.g. to have gradient that can rely more on its angle than on its magnitude.
What to choose for learning agent with a language module? Our study suggests that a learn- ing agent that needs language model to interact with other agents, would benefit from AriEL to generate a diverse language. It outperformed the rest both in the toy dataset and on the real data.

---

Under review as a conference paper at ICLR 2021
Partial evidence for volume codes. The experiments performed suggest that the volume aspect of AriEL is to be held responsible of its success. We have provided evidence on how volume coding can be beneficial for retrieval of stored information that is composed of discrete symbols, and variable length, by random sampling, in contrast with simply distributed representations. It is in fact AriEL to generate more valid sentences, toy dataset, an implicit volume coding method, but performed poorly on the real dataset. The low prediction accuracy of AE/VAE, has to be read in conjuction with the grammar accuracy: it basically means that those methods are overfitting the training data, and even if they often manage to produce grammatically correct sentences when test sentence is given at the input, the volumes/points that would represent new test sentences, seem to have disappeared, all the latent space is dedicated to only the training set.
explicit volume coding method. VAE is the second on the
Transformers are hard to sample from the latent space. The Transformer has been used in this work in an uncommon way: by sampling its latent space instead of its input space. Its low validity score reflects that. Our aim was to better understand the latent organization of language, so, we do not want to suggest this the most effective way to use Transformer. Transformer is excellent when sampled in the input space, but it's difficult to sample from the latent space. This is so because Transformer represents each word by d dimensional vector while the other approaches represent whole sentences in d dimensional vectors, Transformer needs extremely high dimensional vector to represent a sentence, n d where n is the number words a sentence. This makes it extremely hard to find sentences using uniform random sampling in the latent space.
6 CONCLUSION AND FUTURE WORK
We proposed AriEL, volume mapping of language into continuous hypercube to be used reference system. It provides latent organization of language that excels at several metrics related to the use of language, and especially at generating many unique and grammatically correct sen- tences sampling uniformly the latent space. AriEL fuses arithmetic coding and k-d trees to construct volumes that preserve the statistics of dataset. In this way we construct latent representation that assigns data sample to volume, instead of point. When compared to standard techniques it highlights room for improvement their capacity for generation, prediction and generalization.
Recurrent-based continuous sentence embeddings largely overfit the training data and only cover a small subset of the possible language space, particularly when the size of the latent space small. They also fail to learn the underlying CFG and generalize to unbiased sentences from that CFG. However they manage to generate quite a few diverse valid sentences. Transformer managed to avoid overfitting even after being overtrained, proving its robustness. It performed a remarkable generalization the unbiased data. However proves hard to use as generator from the continuous latent space using random sampling.
On the one hand, this study helps to realize how much of the latent space lies unused by standard architectures. On the other hand, AriEL can be seen as technique to provide an effective interface between multi-modal RL agents that need a pretrained language model for language interaction. We stress that volume based codes can provide AriEL allows us to sample/generate in theory the same probability distribution as the training set and in practice more diverse set of sentences, demonstrated the toy and on the human dataset.
advantage point codes in generation tasks.
Our planned next step is to use AriEL as a module a learning agent. This study has been performed for dialogue based language generation, which implies short sentences. It would be useful for the NLP community to understand if this method generalizes to the compression of longer texts.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Bentley, J. L. (1975), 'Multidimensional binary search trees used for associative searching', Com- munications of the ACM 18(9), 509-517.
Bowman, S. R., Vilnis, L.., Vinyals, O., Dai, A., Jozefowicz, R. and Bengio, S. (2016), Generating sentences from a continuous space, in '20th SIGNLL CoNLL', Association for Computational Linguisties, pp. 10-21.
Chen, T. Q.. Rubanova, Y., Bettencourt, J. and Duvenaud, (2018), Neural ordinary differential equations, in 'NeurIPS', pp. 6571-6583.
Cho. K., van Merrienboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H. and Ben- gio, Y. (2014), Learning phrase representations using mnn encoder-decoder for statistical machine translation, in 'EMNLP", Association for Computational Linguistics, pp. 1724-1734.
Dai, Z., Yang. Z., Yang, Y., Carbonell, J., Le, Q. and Salakhutdinov, R. (2019), Transformer-X XL: Attentive language models beyond a fixed-length context, in 'Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics', Association for Computational Lin- guistics, Florence, Italy.
De Vries, H., Strub, F. Chandar, S., Pietquin, O., Larochelle, H. and Courville, A. C. (2017), Guesswhat?! visual object discovery through
dialogue., in 'IEEE CPVR', Vol.
Edelsbrunner, H., Kirkpatrick, and Seidel, (1983), 'On the shape of set of points in the plane', IEEE Transactions on Information Theory 29(4), 551-559.
Elias, P. and Abramson, N. (1963), Information Theory and Coding, Electronic Science, 1st edn, McGraw-Hil Inc.US, pp. 72-89.
Friedman, H., Bentley, J. I.. and Finkel, R. A. (1977), 'An algorithm for finding best matches in logarithmic expected time', ACM TOMS 3(3), 209-226
Glorot, X. and Bengio, (2010), Understanding the difficulty of training deep feedforward neural networks, in 'MLRR W&CP: 13th AISTATS', Vol. 9, pp. 249-256.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley D., Ozair, S., Courville, A. and Bengio, Y. (2014), Generative adversarial nets, in Ghahramani, M. Welling, Cortes, Lawrence and K. Q Weinberger, eds, 'NeurlPS 27', Curran Associates, Inc., pp. 2672-2680.
Gross, E. M. (1995), Kd trees and delaunay based linear interpolation for kinematic control: comparison to neural networks with error backpropagation, in 'Proceedings of 1995 IEEE Inter- national Conference on Robotics and Automation', Vol. 2, IEEE, pp. 1485-1490
Hinton, E., McClelland, J. L. and Rumelhart, D. E. (1984), Distributed representations, Camegie- Mellon University Pittsburgh, PA.
Hochreiter, S. and Schmidhuber, J. (1997), 'Long short-term memory', Neural computation 9(8), 1735-1780.
Jebara, T. (2012), Machine learning: discriminative and generutive, Vol. 755, Springer Science & Business Media.
Jiang, W., Kiang, S., Hakim, N. and Meadows, H. E. (1993), Lossless compression for medi- cal imaging systems using linear/nonlinear prediction and arithmetic coding, in 'ISCAS', IEEE, pp. 283-286.
Johnson, N. W. (2018), Geometries and transformations, Cambridge University Press.
Kingma, D. and Ba, J. (2015), Adam: A method for stochastic optimization, in 'ICLR'.
Kingma, D. and Welling, M. (2014), Auto-encoding variational bayes.. in 'ICLR'.
Kusner, M. J. and Hernández-Lobato, M. (2016), 'Gans for sequences of discrete elements with the gumbel-softmax distribution', arXiv preprint arXiv:1611.0405.
10

---

Under review as a conference paper at ICLR 2021
LeCun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W. and Jackel, L. D. (1989), 'Backpropagation applied to handwritten zip code recognition', NNeral computation 1415,5155551 541-551.
Li, S., Li. W. Cook, C.,, Zhu, C. and Gao, Y. (2018), Independently recurrent neural network (in- drnn): Building A longer and deeper RNN, in 'IEEE CPVR'.
Ma, C., Liu, D., Peng, X., Zha, Z.-J. and Wu, F. (2019), Neural network-based arithmetic coding for inter prediction information in heve, in 'ISCAS' IEEE, pp. 1-5.
Maillard, and Solaiman, B. (1994), neural network based on Ivq2 with dynamic building of the map, in 'ICNN', Vol. 2, IEEE, pp. 766-770.
Makhzani, A., Shlens, J., Jaitly, N., Goodfellow, I. and Frey, B. (2015), 'Adversarial autoencoders', arXiv preprint arXiv: 151.::::111....44..
Mescheder, L.., Nowozin, S. and Geiger, A. (2017), Adversarial variational bayes: Unifying varia- tional autoencoders and generative adversarial networks, in 'Proceedings of the 34th International Conference on Machine Learning-Volumm 70', JMLR. org, pp. 2391-2400.
Miller, G. A. (1995), 'Wordnet: A lexical database for english', Commun. ACM 38(11), 39-41.
Munkres, J. R. (2018), Elements of algebruic topology, CRC Press.
Ng, A. Y. and Jordan, M. I. (2002), On discriminative vs. generative classifiers: comparison of logistic regression and naive bayes, in 'NeurIPS', pp. 841-848.
Pascanu, R., Gülçehre, Ç., Cho, K. and Bengio, Y. (2014), How to construct deep recurrent neural networks, in 'ICLR'.
Pasero, E. and Montuori, A. (2003), Neural network based arithmetic coding for real-time audio transmission on the tms320c6000 dsp platform, in 'ICASSP", Vol. 2, IEEE, pp. II-761.
Radford, A., Narasimhan, K., Salimans, T. and Sutskever, I. (2018), 'Improving language under- standing by generative pre-training' Technical report, OpenAl.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D. and Sutskever, I. (2019), 'Language models unsupervised multitask learners', OpenAl Blog 1(8), 9.
Rezende, D. J. and Mohamed, S. (2015), 'Variational inference with normalizing flows', arXiv preprint ar wxXiv:1505.00777
Saxe, A. M., McClelland, J. I.. and Ganguli, S. (2014), Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, in 'ICLR'.
Severyn, A., Barth, E, and Semeniuta, S. (2017), A hybrid convolutional variational autoencoder for text generation, in 'EMNLP'.
Sutskever, I., Vinyals, O. and Le, Q. V. (2014), Sequence to sequence learning with neural networks, in 'NeurlPSS' MIT Press, Cambridge, MA, USA, pp. 3104-3112.
Tatwawadi, K. (2018), 'Deepzip: Lossless compression using recurrent networks', URL https://wwb. stanford. edw/class/es224nn// 20tilluss//s22//h/perrr222766660 pdf-
Tolstikhin, I., Bousquet. O., Gelly, S. and Schoelkopf, B. (2017), 'Wasserstein auto-encoders', arXiv preprint arXiv:1711.01555
Triantafyllidis, G. and Strintzis, M. (2002), neural network for context-based arithmetic coding in lossless image compression, in "WSES ICNNA'.
Vasudevan, S., Ramos, F., Nettleton, E. and Durrant- of large-scale terrain'. ", Journal of Field Roboties 26(10), 812-840.
Durrant-Whyte, Whyte, H. (2009), 'Gaussian process modeling
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, N., Kaiser, L.. and Polo- sukhin, I. (2017), Attention is all you need, in 'NeurlPS", pp. 5998-6008.

---

Under review as a conference paper at ICLR 2021
Wiedemann, S., Kirchhoffer, H., Matlage, S., Haase, P., Marban, A., Marine, T., Neumann, D., Osman, A., Marpe, D., Schwarz, et al. (2019), 'Deepeaaac: Context-adaptive binary arithmetic coding for deep neural network compression', arXiv preprint arXiv:1955.08
Williams, R. J. and Zipser, D. (1989). 'A learning algorithm for continually running fully recurrent neural networks' Neural Computation 1(2), 270-280.
Witten, H., Neal, R. M. and Cleary, J. G. (1987), 'Arithmetic coding for data compression', Com- munications the ACM 30(6), 520-540.
Woodbridge, J., Anderson, H. S., Ahuja, A. and Grant, D. (2018), Detecting homoglyph attacks with siamese neural network, in 'SPW', IEEE, pp. 22-28.
Xu, J., Ren, X., Lin, J. and Sun, X. (2018), Diversity-pronnee promoting gan: A cross-entropy based gener- ative adversarial network for diversified text generation, in 'EMNLP: pp. 3940-3944
Yang, Z., Hu, Z., Salakhutdinov, R. and Berg-Kirkpatrick, T. (2017), Improved variational autoen- coders for text modeling using dilated convolutions, 'Proceedings of the 34th International Conference on Machine Yearning-Volume 70', JMLR. org, pp. 3881-3890.
Yin, H., Ding, X., Tang, I.., Wang. Y. and Xiong, R. (2017), Efficient 3d lidar based loop closing using deep neural network, 'ROBIO', IEEE, pp. 481-486.
Yu, L., Zhang, W., Wang. J. and Yu, Y. (2017), Seggan: Sequence generative adversarial nets with policy gradient, in "Thirty-First AAAI Conference on Artificial Intelligence'.
12

---

Under review as a conference paper at ICLR 2021
SUPPLEMENTARY MATERIAL
CONTEXT-FREB GRAMMAR (CFG) USED IN THE EXPERIMENTS
The context free grammar used generate the biased and unbiased sentences is composed by the following rules:
gword adjective '.' adjjetive "and" adjective '?'
9 gword adjective "and" adjective
gword adjective 'p'
4 qword "made" "of" noun material '?'
preposition 4 qword up '7'
+ determiner adjective adjective adjective noun
adjective '." adjective 'and" adjective noun uP determiner adjective 'and" adjective noun "made" "of" nonn materiol
nP deierminer adjective adjective noun
determiner adjective "and" adjective determiner adjective noun "made" "of" noun_material 'made" "af" noun_material + determiner adjective noun up determiner
determiner
gword 'is" 'it" "i" "the" "object" "is" "the" 'thing" noun.object noun.material noun.roomtype preposition 4 ireposition_mateiii
adjective + adjective coloo adjective
adjeetiie snfeetive.affordaece | adjective ddjjective-verrlll size size adjective relative per dimension size
adjective .mass adjective adjective.othe
nojn-object "accordion
"acouxtic" 'gramophone"
"bar"
"barrier" ....
"basket"
"outdoor" 'lamp" ouidoor
"seating
nouR material 'bricks"
"carpet" "decoration" "stone ground "laminate" 'laaher
"facing" 'wood"
'stone" ....
"grass"
nour.roomtype "aeration" "balcony" | "bathroom" 'hall"
"bedroom" 'hallway"
'boiler "room" "kithhen
"arage
"guest
determiner 'a' "tha | "the" 'this"
preposition..aatere 'made" "of"
adjective.cotor
"antique" "white" "magenta" 'maroon"
"state" "gray" 'whise "yellow
adljettiveaffoodda
'actable" 'addable" 'addressable 'deliverable
destroyybble "dviddbble 'movable" ....
adjective.size adjjeciive.veraallatz
addretive.rllaivv.eee...... dimenssionitm
adjective overall size "averoge-sized" 'buge' 'large wtw.eeeeeeettee.e..eeeaaesee
'small" 'riny" + 'deep 'narrow" "shallow" 'short "tatl" "wide"
adjective,mass
'keary" 'light" "odderaeely" 'heavy" 'modevately" 'light"
"slightly "heavy
'very" "heavy | "very" "light"
adjective state "closed" 'opened"
adjective
'textared "transparent"

---

Under review as a conference paper at ICLR 2021
SIZE OF THE LANGUAGE SPACE
From the CFG used in the experiment, possible to extract a total of 15,396 distinct grammar rules, some shown below. However, for simplicity. defined only 4, related to the number of adjectives in it. In the case of the unbiased dataset, those rules can produce a total of 9.8le+18 unique sentences. The total number of unique sentences for the biased dataset is expected to be order magnitude smaller.
Iqword. prep material, determiner. stjestate. "and" adj other, noun roomtype.. 'P"]
[qword. prep spatial, deserminer, adh-ether. adj-state adj state noun_object. '?']
Iqword.
determiner. adj_other. '.", adj.mass. "and" adj.affordance. noun.rommiype '
Iqword.
determiner. sil..relaaive.er.dimennoo adj.state. 'and", adj.stare, noan.material, '2 determiner, cdj..overlll.ize.
adj-overall.size, noun-object. '?'1
Iqword. Iqword.
prep.spatial, determiner, odjeorher. adj_mass. afj noun noun.material, '?"] adj-state "and" , rdllrrelatve_siee prep materiat. determiner. adj mass. adj other, adj other. noan material, '7" prep-spatial. deserminer, adj_state. adj-ether adl-color. noun_object, '?']
Iqword.
'?'}
1qword.
[qword.
lqword. determiner. adj_relative_.ize. "and". adj.overall_aize noun-material, '7"l
Iqword. determiner. adj-state, adj-overall
adj-other. noun-roomtype. '?'
[qword. determiner, adj_other, adj adj_state, ad) adssm material '?'l Iqword. determiner, adj
"and". adj other,, noun.material, '
lqword. deserminer. adj.color. adj otker. noun coject '?']
lqword. prep srep-apatial_We rel. determiner, adj mass. adj color. noun roomtype, '7'l Iqword. determiner, adi-state. 'ndd". adj-relative.size noun_object, '2'] Iqword. determiner. adj.color, adj-color. adj.relative.site nown.material, '? Iqword, determiner, adj-affordance, noun-object. '?']
[qword. determiner, other, other, adj_state, noun_roomtype, '?']
3 EXAMPLE OF SENTENCES GENERATED FROM THE CFG
3.1 BIASED SAMPLE SENTENCES
is it large, light yellow and light
is it white, deep pink and average-sized ?
is it light, huge and shallow laminate
is the object average-sized and light
is the object fashionable ghost white and pale turquoise
is the thing huge, huge and khaki ?
is the thing small ignitable and very light ?
is the object notable very light orange carpet ?
is the object this small wood made of facing stone ?
is the object a textured and combinable floor cover made of laminate ?
3.2
UNBIASED SAMPLE SENTENCES
is the object the huge tiny lovable guest room ?
is the object the closed closed transparent textile ?
is the thing transparent, narrow and slightly heavy textile ?
is it steerable, dark orange and light
is it gray, very heavy and textured ?
is it closed, heavy and moderately light? ?
is it transparent, transformable and moderately light ?
is the thing average-sized and dark red
is the thing large and deep garage ?
is it that slightly heavy stucco made of grass

---

Under review as a conference paper at ICLR 2021
4 VOCABULARY
Annotation
Nb. of classes
Example of classes
Noun
86
air conditioner, mirror, window, door, piano instrument, living thing, furniture, decoration
WordNet category (Miller, 1995)
580
Location
24
kitchen, bedroom, bathroom, office, hallway, garage
Color
139
red, royal blue, dark gray, sea shell transparent, textured
Color property
2
Material
15
wood, textile, leather, carpet, decoration stone
Overall mass
light, moderately light, heavy, very heavy
Overall size
4
tiny, small, large, huge tiny, small, large, huge, short, shallow, narrow, wide opened, closed sound, speech, music attach, bend, divide, play, shake, stretch, wear
Category-relatie size
10
State
2
Acoustical capability
3
Affordance
100
Table S1: Description of vocabulary used.
5 USE OF LATENT SPACE
In figure SI, each dot represents a sentence in the latent space. the first row the dot in the latent space is passed input to the decoder, while in the second and third row the dot is the output of the encoder when the biased test sentence is fed at its input. Two random axis in Rd are chosen for the generator, first row, while a PCA for the encoder, second and third row. In every case, the values in the latent space where normalized between zero and one to case the visualization. Lines are used ease the visualization of the clusters and shifts of data with their label, since the point clouds overlap and are hard to see. The curves are constructed as concave hulls of the dots based on their Delaunay triangulation, method called alpha shapes Edelsbrunner et al. (1983).
axis were chosen subjectively among the first components of
We can see in figure S1 (first row) how easy it is to find grammatical sentences when randomly sampling the latent space for each model. AriEL practically only generates grammatical sentences and AE and VAE perform reasonably well too, while Transformer fails. AriEL failures are plot on top, to remark how few they are, while AE and VAE failures are plot at the bottom, otherwise they would hide the rest given how numerous they are. In the same figure (rows two and three) we observe how different methods structure the input in the latent space, each with prototypical clusters and shifts. The Transformer presents an interesting structure of clusters whose purpose remains unclear. Interestingly, the encoding maps seem to be ones. All the models seem to cluster or shift data belonging to different classes at the encoding, that could be taken advantage of by learning agent placed in the latent space. However it seems hard to use the Transformer as a generator module for an agent. The good performance of AriEL is consequence of the fact that all the latent space is utilized, and in no directions large gaps can be observed. This can be seen in the two encoding rows, where the white spaces around the cloud of dots are consequence of the rotation performed by the PCA, otherwise all the space between 0 and 1 would be utilized by AriEL.
organized than the decoding

---

Under review as a conference paper at ICLR 2021
AriEL
Transformer
AE
VAE
9
9
10
ungrammatical
length percentile 75-100
0 adjectives
length percentile 50-75
1 adjective
length percentile 25-50
2 adjectives
length percentile 0-25
3 adjectives
Figure S1: Random-sammplnng-baes generation in the first row, and encoding of input sen- tences in the remaining rows. A sentence is represented by point in the latent space. First row shows the proportion of grammatically correct sentences that can be decoded by random uniform sampling the latent space. AriEL sampled almost only grammatical sentences (ungrammatical so few that are placed on top in the plot). Transformer mainly yielded ungrammatical sentences, while AE and VAE were able produce many grammatical sentences (ungrammatical are below, otherwise they would cover up the grammatical). Each dot is labeled according to how many ad- jectives the sentence generated has. Second and third rows show the clusters of points in the latent space for the test sentences as they are mapped by the encoders. All models seem shift the clusters to some degree according to the number of adjectives in the sentence, in the second row. similar conclusion applies to the third row, that shows where sentences of different length encoded. For all panels, we searched subjectively for the dimensions that would better reveal some clustering, with the help of PCA. We scaled all latent representations between [0,1] for visualization.

---

Under review as a conference paper at ICLR 2021
VISUALIZATION OF PERFORMANCE ON TOY DATA
R 16
R
512
AHELL Tansfomer
Generaboon
0C MIJ. RMJ
VC AA
Profction
PAU
PAU
GC WII EA RAJI
VC
RAB
Figure S2: Radar Chart of the Quantitative Assessment. Latent space of IR 16 R812 on the right. Training was performed on biased sentences. The metrics are defined in Method- ology: Generalization is measured by prediction accuracy of unbiased sentences (PAU), Prediction by prediction accuracy of biased sentences (PAB), grummar accuracy (GA) and bias accuracy (BA) and Generation by uniqueness (U), validity (V), vocabulary coverage (VC) and grammar coverage (GC). AriEL excels in all the 8 metrics. Most importantly AriEL outperforms every other method Generation Validity (V) and doesn't 't require large latent space do so (E similar to RS12). VAE performs remarkably well at generating unique and grammatical sentences (validity, V) when the latent space small (R 16), probably given the volume-code nature of the method. Transformer performs exceptionally at not overfitting in the reconstruction tasks and generalizing, it manages to cover all grammar rules, even with very small number of parameters (RR1)). Transformer proved to be an inefficient generator using random sampling input (validity) but improved with larger latent space. For a larger latent space of 512 AE and VAE overfit less (PAU and PAB) and improve their Generation (V).
the left and

---

Under review as a conference paper at ICLR 2021
ARIEL ALGORITHM
Algorithm AriEL Encoding
Algorithm AriEL Decoding
Input: sentence: S = (8y)}=1
Input: represents S in [0, 1]d
Output: Z represents S in [0, 1]d
Output: sentence:
(3)))=1
1: function SACELEENCODE(S)
1: function ARIEL DECODE()
2: d = latent space dimension
2: d = dimension
3: Bion zeros(d)
3: Biow = zeros(d)
4:
Bup ones d)
Bup ones (d)
n (en
S (START)
6:
for 0, ... do
6:
for i = =0. ... Rmar 1 do choose dimension to unsplit
bo choose dimension to split
7:
d2 = mod d
7:
d = mod d
8:
Pnent (8) Prnr(s((sijee)
P (s) (s|(s Clow(s) Esso' Prezce(s))
9:
(low(s) Lever Preze(s))
9:
Cup(s) Esso-1 (8)
10:
Cup(s) -5 P Prene(s')
range Bup(d.) (c)
11:
range- Bup(di) BBow
update volume bounds
update volume bounds
12:
Bup Brow + range
12:
Bsup (8) Bup(ds) + range.
Cup
Cup
13:
Biow (di) = (dow(di) + range
13:
(stow Blow(d) + range-
(s;)
Clw (s)
14:
end for
any point in the volume is assigned the symbol 8;
represent the volume by its center
15:
z (Brow + Bup) /2
14:
$, = finds (stoo <z(d;) Bsup(s)
16:
return
15:
Bup B =8sup(8i)
17:
end function
16:
Blow (d4) = Bstow (8i) S S.appeedd
17:
18:
end for
19: return S
20:
end function
Figure S3: Algorithms for AriEL encoder and decoder B stands for bound, and Bup and Brow for the upper and lower bounds that define the AriEL volumes, the blue color identifies the lines with the major differences between encoder and decoder and PLM identifies the Language Model inside AriEL. Its cumulative distributions (Cup. Clww are used to define the limits of the volumes and its size (range). (Left) AriEL Encoding: from sentence continuous space. Finally the volumes represented by their central point z for simplicity. (Right) AriEL decoding: from continuous space sentence. is used identify which volume has to be picked next.
8 TRAINING DETAILS
We go through the training data 10 times, in mini-batches of 256 sentences. We applied teacher forcing (Williams and Zipser, 1989) during training. We the Adam (Kingma and Ba, 2015) optimizer with a learning rate of 1e-3 and gradient clipping at 0.5 magnitude. Learning rate was reduced by factor of 0.2 if the loss function didn't decrease within epochs, with a minimum learning rate of le-5. For all RNN-based embeddings, kernel weights used the Xavier uniform initialization (Glorot and Bengio. 2010), while recurrent weights used random orthogonal matrix initialization (Saxe et al., 2014). Biases are initialized to zero. Embeddings layers are initialized with a uniform distribution between [-1, 1]. For Transformer the multihead attention matrices and the feedforward module matrices, used the Xavier uniform initialization (Glorot and Bengio, 2010), the beta of the layer normalization uses zeros, and its gamma uses ones for initialization. AE and VAE are trained with word dropout of 0.25 at the input, and VAE is trained with KL loss annealing

---

Under review as a conference paper at ICLR 2021
that moves the weight of the KL loss from zero to one during the 7th epoch, similarly to the original work (Bowman al., 2016).


Reviews:
[{"review_id": "yPQBHY8Q_LU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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 proposes \"volume encoding\" for sequence modeling. Unlike traditional autoencoder or variation autoencoder model family, the proposed model AriEL applies KDTree to map the input sequence to a quantized multi-dimensional space as the code, and supports tasks such as reconstruction and generation.\n\n**high level comment**\nIndeed this paper proposes a novel and interesting way to do sequence modeling. From its root, data like language are naturally discrete. The traditional methods ubiquitously adopt a continuous code as the representation that poses a gap between discrete and continuous mode. AriEL, on the other hand, represents this type of data into the discrete mode.\n\nFrom a different perspective, the continuous code does have its own merits. The smoothness of the manifold may allow us to perform vector arithmetic and have better performance at practical tasks like grammar correction or semi-supervised learning. The paper does not include tasks like these. Could the authors clarify?\n\n**table 1**\nCan the authors clarify on how to quantitatively or qualitatively measure the correlation between these generations and the training dataset bias?\n\n**table 2**\nIt's pretty well-known that VAE type of reconstruction may have grammar errors like repeated words. The AriEL model seems to be able to avoid such error but at a cost of wrong n-grams like \"small large\". Could the authors give some intuition here?\n\n**open discussions**\nThe current version of AriEL seems to rely on a sequential modeling workhouse like the RNNs. Is it amenable to other types of models?\n\nWould the usage of KDTrees and dataset stats amplifies the training set bias so it might generalize poorer than the rivalling models?\n\nWhat kind of practical applications can we dream up the AriEL for, e.g. leveraging the volume code?\n\n**conclusion**\nWith all the questions above, I still vote an accept for the proposed model for its novelty. In my honest opinion, this paper is valuable for the community. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ubffdya0Xtq", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 describes a novel methodology of volume coding for encoding and decoding sentences. The algorithm is based on arithmetic coding.\n\nIn general, I believe this is a well written paper. However, I couldn't really understand the content until I read the encoding and decoding algorithms, which are in Section 7 of supplemental material. I strongly think the structure of this paper needs revision, so that people without background of arithmetic coding can understand the core method.\n\nOther than the writing, I still have concerns about the motivation and evaluation. In the first point of contributions, the author states that the proposed method improves the retrieval of learned pattern with random sampling. Does this mean when the coding is randomly sampled, we can see more valid sentences comparing to other methods? If so, the validity in evaluation is the key to claim this contribution.\n\nIn Table 3,  the validity percentage of a Transformer with 512 latent dimensionality is only 17.2%. This low score strongly contrasts with our knowledge that a well-trained Transformer language model is very strong at producing valid sentences. One hypothesis is that the amount of training data is not sufficient for Transformer. If this is the case, the proposed method may lose its edge when the training data is abundantly available. Upon reading the experiment section, I couldn't find an explanation.\n\nWhen comparing with VAE, it's important to compare the interpretability of the latent variables, which is the main purpose we train a generative model. However, if the interpretability is not a major motivation of volume coding, then I'm concerning whether it's meaningful to compare with VAE.\n\nConsidering all these factors, I decide to give a weak acceptance to this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gAFsHsguQM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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: This paper proposes Arithmetic coding and k-d trEes for Language (AriEL), a representation learning method for more efficiently mapping discrete data (text) into a continuous space. Specifically, AriEL uses a language model to split the latent space into volumes.\n\nClarity: The paper is overall easy to follow.\n\nOriginality: The idea to incorporate more structure into the learned encodings via arithmetic coding and K-d trees is an interesting one.\n\nPros: AriEL seems to perform quite well on the toy dataset and the GuessWhat?! dataset.\n\nCons: \n- I think the paper would be more significant if the authors would have demonstrated the efficacy of their method on more benchmark datasets; for example, WMT (Kaiser et al. 2018) or WikiText (Merity et. al 2016).\n- I am curious as to how the performance of some of these models are *so* bad: for example, the Transformer obtains a validity score of 4.7% on the toy dataset, and the AE/VAE get roughly 0% accuracy on the prediction task. I would appreciate it if the authors could elaborate more on why exactly AriEL seems to be doing so well, as well as some of its potential limitations. (at least on the experiments side, there doesn't seem to be any, which seems too good to be true?)\n\nQuestions:\n- Can I understand AriEL to have an encoding/decoding complexity of O(nD^2) rather than the O(n) as written later in the paragraph on page 3, since in practice AriEL will most likely always use a language model? Or is this specific to an RNN? I am wondering if this would hinder the use of AriEL on more complex datasets that require larger hidden sizes (D).\n\nMinor typos:\n- \"followed by a 140-unit LSTM\" (Section 3.2)\n- \"Then we turn to\" (Section 3.1)\n\n---\nUPDATE: Thanks to the authors for responding to my questions and updating the submission. I will keep my score as is, since I think that the paper would greatly benefit from more practical/rigorous empirical evaluations to demonstrate the usefulness of the approach. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Uj0ujSUQP4K", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 proposes a sentence embedding called AriEL. Specifically, based on arithmetic coding and k-d trees, AriEL maps sequences of discrete data into volumes in the latent space, and can then retrieve sequences by random sampling. AriEL is compared to other standard techniques such as Transformer and Variational Autoencoders. Results show that it can generate more diverse and valid sentences.\n\n**Pros:**\n\nThe idea of constructing sentence encoders by arithmetic coding is interesting and novel. AriEL takes the frequency of sentences into account, and the frequency implicitly models the statistics of human language. I have not seen prior work in this direction, and it is worth exploring.\n\n**Cons:**\n1. My major concern is the evaluation. The evaluation metrics in the paper are very limited and not convincing. They fail to assess the strengths of the proposed sentence embedding. Specific downstream applications are missing here. A solid evaluation should at least include either classification tasks, such as sentiment analysis, textual entailment; or generation tasks, such as simplification, machine translation.\n\n\n2. The paper is hard to follow and the writing has greatly impeded understanding. I will mention a few that confuse me most:\\\n(1) In the second paragraph of Section 3.2, what does “but the probabilities defined by the latter are used as a deterministic Russian roulette” mean? Does that mean the argmax is one-hot?\\\n(2) What is the purpose of defining biased and unbiased sentences? And in Table 1, what does “comply with the bias” mean?\\\n(3) In Section 3.4.2, I can hardly believe the definition of “grammar coverage”. Why is the number of adjective able to represent grammar rules?\n\n\n3. I doubt only modeling the frequency of sentences is enough for a sentence encoder. There are many aspects of language (e.g. taxonomy, lexicon) that should be considered. But again, these are to be proved by downstream tasks.\n\nOverall, I suggest rejecting the paper in its current state.\n***\nUPDATE: The authors have addressed some of my comments. I appreciate their efforts for making the paper clearer. That being said, I would still keep my original score, because my major concern (evaluation) has not been addressed. Also, the paper would be much better if its writing and organization can be improved.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2LjybOQx-ek", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 proposes AriEL, a sentence encoding method onto the compact space [0, 1]^d. It leverages essences of arithmetic coding and kd-tree to encode/decode sentences with a fixed region of the space. With the property of arithmetic coding, in theory, it can map sentences with any lengths into individual values, and any points on [0, 1]^d can map back into corresponding sentence. Although the method relies on neural network based LMs to assign sentences into corresponding regions, the generality of mapping between any sentences/points is kept while changing the LM's behavior. The idea is interesting.\n\nHowever, there is some disadvantages of the proposed encoding which are not always mentioned in the paper. First, due to the topological difference between the proposed encoding and other spaces (e.g., Euclidian space), the proposed encoding could not be treated as embeddings in some usual meanings, e.g., it is hard to calculate the \"similarity\" between two encodings by arithmetics on real numbers as many deep learning methods implicitly does. Actually, there seems no evidence of advantages of the proposed encodings on other tasks which are not designed for this encoding unlike experiments on the paper.\n\nSecond, the resulting encodings will be affected directly by the capability of the actual representation of real numbers. E.g., if we used float32 for each dimension, the [0, 1] space can contain only information up to 30 bits long in the most efficient case, which may be insufficient to encode \"all\" sentences into the compact space. It will be problematic when we encode very long sentences (|sentence| >> d). Experiments in the paper did not figure out this point enough because the mean number of words in the corpus is too small (9.9 and 5.9 words, whereas d = 16).\n\nThere are also several presentation errors in the paper:\n\n- Using different format of all citations.\n- Table 3 clearly exceeds the width limit.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: the authors propose to use volume coding to enable uniform sampling from an implicit latent space to be used together with a autoregressive language model. all the reviewers find this approach interesting, but all found that the submission would be much stronger with more thorough evaluation. in particular, i noticed that the reviewers wanted to see how the proposed ariel works in comparison to e.g. VAE on a more diverse set of benchmarks, since the choice of two datasets, one synthetic and one small, narrow-domain, is somewhat limited largely due to their relative simplicity. furthermore, the reviewers were unsure whether various evaluation metrics the authors have used are exhaustive nor appropriate to demonstrate the efficacy of Ariel or to put the proposed approach correctly in the context of other approaches. i agree with the reviewers on both of these points.

i'm thus recommending this manuscript be rejected, and strongly recommend the authors give a bit more thoughts on how to demonstrate the effectiveness of the proposed approach in the context of other approaches and the problem of sentence generation (which is the main problem the authors claim to tackle, as the title directly suggests.) with a better planned experiment and analysis, i believe the authors' efforts will have significant impact.
Decision: Reject