HYPEREMBED: TRADEOFFS BETWEEN RESOURCES
Year: 2019

Abstract:
Recent advances in Deep Learning have led to a significant performance increase on several NLP tasks, however, the models become more and more computationally demanding. Therefore, this paper tackles the domain of computationally efficient algorithms for NLP tasks. In particular, it investigates distributed representations of n-gram statistics of texts. The representations are formed using hyperdimensional computing enabled embedding. These representations then serve as features, which are used as input to standard classifiers. We investigate the applicability of the embedding on one large and three small standard datasets for classification tasks using nine classifiers. The embedding achieved on par F1 scores while decreasing the time and memory requirements by several times compared to the conventional n-gram statistics, e.g., for one of the classifiers on a small dataset, the memory reduction was 6.18 times; while train and test speed-ups were 4.62 and 3.84 times, respectively. For many classifiers on the large dataset, the memory reduction was about 100 times and train and test speed-ups were over 100 times. More importantly, the usage of distributed representations formed via hyperdimensional computing allows dissecting the strict dependency between the dimensionality of the representation and the parameters of n-gram statistics, thus, opening a room for tradeoffs.

heading: 1 INTRODUCTION
text: Recent work (Strubell et al., 2019) has brought significant attention by demonstrating potential cost and environmental impact of developing and training state-of-the-art models for Natural Language Processing (NLP) tasks. The work suggested several countermeasures for changing the situation. One of them recommends a concerted effort by industry and academia to promote research of more computationally efficient algorithms. The main focus of this paper falls precisely in this domain.
In particular, we consider NLP systems using a well-known technique called n-gram statistics. The key idea is that hyperdimensional computing (Kanerva, 2009) allows forming distributed representations of the conventional n-gram statistics (Joshi et al., 2016). The use of these distributed representations, in turn, allows trading-off the performance of an NLP system (e.g., F1 score) and its computational resources (i.e., time and memory). The main contribution of this paper is the systematic study of these tradeoffs on nine machine learning algorithms using several benchmark classification datasets. We demonstrate the usefulness of hyperdimensional computing-based embedding, which is highly time and memory efficient. Our experiments on a well-known dataset (Braun et al., 2017) for intent classification show that it is possible to reduce memory usage by ∼ 10x and speed-up training by ∼ 5x without compromising the F1 score. Several important use-cases are motivating the efforts towards trading-off the performance of a system against computational resources required to achieve that performance: high-throughput systems with an extremely large number of requests/transactions (the power of one per cent); resource-constrained systems where computational resources and energy are scarce (edge computing); green computing systems taking into account the aspects of environmental sustainability when considering the efficiency of algorithms (AI HLEG, 2019).
The paper is structured as follows. Section 2 covers the related work. Section 3 outlines the evaluation and describes the datasets. The methods being used are presented in Section 4. Section 5 evaluates of the experimental results. Discussion and concluding remarks are presented in Section 6.

heading: 2 RELATED WORK
text: Commonly, data for NLP tasks are represented in the form of vectors, which are then used as an input to machine learning algorithms. These representations range from dense learnable vectors to extremely sparse non-learnable vectors. Well-known examples of such representations include onehot encodings, count-based vectors, and Term Frequency Inverse Document Frequency (TF-IDF) among others. Despite being very useful, non-learnable representations have their disadvantages such as resource inefficiency due to their sparsity and absence of contextual information (except for TF-IDF). Learnable vector representations such as word embeddings (e.g., Word2Vec (Mikolov et al., 2013) or GloVe (Pennington et al., 2014)) partially address these issues by obtaining dense vectors in an unsupervised learning fashion. These representations are based on the distributional hypothesis: words located nearby in a vector space should have similar contextual meaning. The idea has been further improved in Joulin et al. (2016) by representing words with character n-grams. Another efficient way of representing a word is the concept of Byte Pair Encoding, which has been introduced in Gage (1994). The disadvantage of the learnable representations, however, is that they require pretraining involving large train corpus as well as have a large memory footprint (in order of GB). As an alternative to word/character embedding, Shridhar et al. (2019) introduced the idea of Subword Semantic Hashing that uses a hashing method to represent subword tokens, thus, reducing the memory footprint (in order of MB) and removing the necessity of pretraining over a large corpus. The approach has demonstrated the state-of-the-art results on three datasets for intent classification.
The Subword Semantic Hashing, however, relies on n-gram statistics for extracting the representation vector used as an input to classification algorithms. It is worth noting that the conventional n-gram statistics uses a positional representation where each position in the vector can be attributed to a particular n-gram. The disadvantage of the conventional n-gram statistics is that the size of the vector grows exponentially with n. Nevertheless, it is possible to untie the size of representation from n by using distributed representations (Hinton et al., 1986), where the information is distributed across the vectors positions. In particular, Joshi et al. (2016) suggest how to embed conventional n-gram statistics into a high-dimensional vector (HD vector) using the principles of hyperdimensional computing. Hyperdimensional computing also known as Vector Symbolic Architectures (Plate, 2003; Kanerva, 2009; Eliasmith, 2013) is a family of bio-inspired methods of manipulating and representing information. The method of embedding n-gram statistics into the distributed representation in the form of an HD vector has demonstrated promising results on the task of language identification while being hardware-friendly (Rahimi et al., 2016). In Najafabadi et al. (2016) it was further applied to the classification of news articles into one of eight predefined categories. The method has also shown promising results (Kleyko et al., 2019) when using HD vectors for training Self-Organizing Maps (Kohonen, 2001). However there are no previous studies comprehensively exploring tradeoffs achievable with the method on benchmark NLP datasets when using the supervised classifiers.

heading: 3 EVALUATION OUTLINE

heading: 3.1 CLASSIFIERS AND PERFORMANCE METRICS
text: To obtain the results applicable to a broad range of existing machine learning algorithms, we have performed experiments with several conventional classifiers. In particular, the following classifiers were studied: Ridge Classifier, k-Nearest Neighbors (kNN), Multilayer Perceptron (MLP), Passive Aggressive, Random Forest, Linear Support Vector Classifier (SVC), Stochastic Gradient Descent (SGD), Nearest Centroid, and Bernoulli Naive Bayes (NB). All the classifiers are available in the scikit-learn library (Pedregosa et al., 2011), which was used in the experiments.
Since the main focus of this paper is the tradeoff between classification performance and computational resources, we have to define metrics for both aspects. The quality of the classification performance of a model will be measured by a simple and well-known metric – F1 score (please
see (Fawcett, 2006)). The computational resources will be characterized by three metrics: the time it takes to train a model, the time it takes to test the trained model, and the memory, where the memory is defined as the sum of the size of input feature vectors for train and test splits as well as the size of the trained model. To avoid the dependencies such as particular specifications of a computer and dataset size, the train/test times and memory are reported as relative values (i.e., train/test speed-up and memory reduction), where the reference is the value obtained for the case of the conventional n-gram statistics.1

heading: 3.2 DATASETS
text: Four different datasets were used to obtain the empirical results reported in this paper: the Chatbot Corpus (Chatbot), the Ask Ubuntu Corpus (AskUbuntu), the Web Applications Corpus (WebApplication), and the 20 News Groups Corpus (20NewsGroups). The first three are referred to as small datasets. The Chatbot dataset comprises questions posed to a Telegram chatbot. The chatbot, in turn, replied the questions of the public transport of Munich. The AskUbuntu and WebApplication datasets are questions and answers from the StackExchange. The 20NewsGroups dataset comprises news posts labelled into several categories. All datasets have predetermined train and test splits. The first three datasets (Braun et al., 2017) are available on GitHub.2
The Chatbot dataset consists of two intents: the (Departure Time and Find Connection) with 206 questions. The corpus has a total of five different entity types (StationStart, StationDest, Criterion, Vehicle, Line), which were not used in our benchmarks, as the results were only for intent classification. The samples come in English. Despite this, the train station names are in German, which is evident from the text where the German letters appear (ä,ö,ü,ß). The dataset has the following data sample distribution (train/test): Departure Time (43/35); Find Connection (57/71).
The AskUbuntu dataset comprises five intents with the following data sample distribution (train/test): Make Update (10/37); Setup Printer (10/13); Shutdown Computer (13/14); Software Recommendation (17/40); None (3/5). Thus, it includes 162 samples in total. The samples were gathered directly from the AskUbuntu platform. Only questions with the highest scores and upvotes were considered. For the task of mapping the correct intent to the question, the Amazon Mechanical Turk was employed. Beyond the questions labelled with their intent, this dataset contains also some extra information such as author, page URL with the question, entities, answer, and the answer’s author. It is worth noting that none of these data was used in the experiments.
The WebApplication dataset comprises 89 text samples of eight intents with the following distribution (train/test): Change Password (2/6); Delete Account (7/10); Download Video (1/0); Export Data (2/3); Filter Spam (6/14); Find Alternative (7/16); Sync Accounts (3/6); None (2/4).
The 20NewsGroups dataset has been originally collected by Ken Lang. It comprises of 20 categories (for details please see Table 7 in the Appendix). Each category has exactly 18, 846 text samples. Moreover, the samples of each category are split neatly into the train (11, 314 samples) and test (7, 532 samples) sets. The dataset comes already prepackaged with the scikitlearn library for Python.

heading: 4 METHODS
text: 4.1 CONVENTIONAL n-GRAM STATISTICS
An empty vector s stores n-gram statistics for an input textD. D consists of symbols from the alphabet of size a; ith position in s keeps the counter of the corresponding n-gram Ai = 〈S1,S2, . . . ,Sn, 〉 from the set A of all unique n-grams; Sj corresponds to a symbol in jth position of Ai. The dimensionality of s equals the total number of n-grams in A and calculated as an. Usually, s is obtained via a single pass-through D using the overlapping sliding window of size n. The value of a position in s (i.e., counter) corresponding to a n-gram observed in the current window is incremented by one. In other words, s summarizes how many times each n-gram in A was observed in D.
1 It is worth noting that the speed-ups reported in Section 5 do not include the time it takes to obtain the corresponding HD vectors. Please see the discussion of this issue in Section 6.
2Under the Creative Commons CC BY-SA 3.0 license: https://github.com/sebischair/ NLU-Evaluation-Corpora

heading: 4.2 WORD EMBEDDINGS WITH SUBWORD INFORMATION
text: Work by Bojanowski et al. (2017) demonstrated that words’ representations can be formed via learning character n-grams, which are then summed up to represent words. This method (FastText) has an advantage over the conventional word embeddings since unseen words could be better approximated as it is highly likely that some of their n-gram subwords have already appeared in other words. Therefore, each word w is represented as a bag of its character n-gram. Special boundary symbols “<” and “>” are added at the beginning and the end of each word. The word w itself is added to the set of its n-grams, to learn a representation for each word along with character n-grams. Taking the word have and n = 3 as an example, (have) = [< ha, hav, ave, ve >, have]. Formally, for a given word w, Nw ⊂ {1, . . . , G} denotes the set of G n-grams appearing in w. Each n-gram g has an associated vector representation zg . Word w is represented as the sum of the vector representations of its n-grams. A scoring function g is defined for each word that is represented as a set of respective n-grams and the context word (denoted as c), as:
g(w, c) = ∑
g∈Nw
z>g vc,
where vc is the vector representation of the context word c. Practically, a word is represented by its index in the word dictionary and a set of n-grams it contains.

heading: 4.3 BYTE PAIR ENCODING
text: The idea of Byte Pair Encoding (BPE) was introduced in Gage (1994). BPE iteratively replaces the most frequent pair of bytes in a sequence with a single, unused byte. It can be similarly used to merge characters or character sequences for words representations. A symbol vocabulary is initialized with a character vocabulary with every word represented in the form of characters, where “.” is used as the end of word symbol. All symbol pairs are counted iteratively and then replaced with a new symbol. Each operation results in a new symbol, which represents an n-gram. Similarly, frequently occurring n-grams are eventually merged into a single symbol. This makes the final vocabulary size equal to the sum of initial vocabulary and number of merge operations.

heading: 4.4 SUBWORD SEMANTIC HASHING
text: Subword Semantic Hashing (SemHash) is described in details in Shridhar et al. (2019); Huang et al. (2013). SemHash represents the input sentence in the form of subword tokens using a hashing method reducing the collision rate. These subword tokens act as features to the model and can be used as an alternative to word/n-gram embeddings. For a given input sample text T , e.g., “I have a flying disk”, we split it into a list of words ti. The output of the split would look as follows: [“I”, “have”, “a”, “flying”, “disk”]. Each word is then passed into a prehashing function H(ti). H(ti) first adds a # at the beginning and at the end of ti. Then it generates subwords via extracting ngrams (n=3) from #ti#, e.g.,H(have) = [#ha, hav, ave, ve#]. These tri-grams are the subwords denoted as tji , where j is the index of a subword. H(ti) is then applied to the entire text corpus to generate subwords via n-gram statistics. These subwords are used to extract features for a given text.
4.5 EMBEDDING n-GRAM STATISTICS INTO AN HD VECTOR
Alphabet’s symbols are the most basic elements of a system. We assign each symbol with a random d-dimensional bipolar HD vector. These vectors are stored in a matrix (denoted as H , where H ∈ [d × a]), which is referred to as the item memory, For a given symbol S its HD vector is denoted as HS ∈ {−1,+1}[d×1]. To manipulate HD vectors, hyperdimensional computing defines three key operations3 on them: bundling4 (denoted with + and implemented via position-wise addi-
3Please see Kanerva (2009) for proper definitions and properties of hyperdimensional computing operations. 4The bundling operation allows storing information in HD vectors Frady et al. (2018); if several copies of any HD vector are included (e.g., 2HS1 +HS2 ), the resultant HD vector is more similar to the dominating HD vector than to other components. Since this paper does not go into deep analytical details of why HD vectors allow embedding the conventional n-gram statistics, the diligent readers are referred to Frady et al. (2018) for the relevant analysis.
tion), binding (denoted with and implemented via position-wise multiplication), and permutation5 (denoted with ρ).
Three operations above allow embedding n-gram statistics into distributed representation (HD vector) Joshi et al. (2016). First, H is generated for the alphabet. A position of symbol Sj in Ai is represented by applying ρ to the corresponding HD vector HSj j times, which is denoted as ρj(HSj ). Next, a single HD vector for Ai (denoted as mAi ) is formed via the consecutive binding of permuted HD vectors ρj(HSj ) representing symbols in each position j of Ai. For example, the trigram ‘cba’ will be mapped to its HD vector as follows: ρ1(Hc) ρ2(Hb) ρ3(Ha). In general, the process of forming HD vector of an n can be formalized as follows:
mAi = n∏
j=1
ρj(HSj ),
where ∏
denotes the binding operation when applied to n HD vectors. Once it is known how to get mAi , embedding the conventional n-gram statistics stored in s (see section 4.1) is straightforward. HD vector h corresponding to s is created by bundling together all n-grams observed in the data:
h = an∑ i=1 simAi = an∑ i=1 si n∏ j=1 ρj(HSj ),
where ∑
denotes the bundling operation when applied to several HD vectors. Note that h is not bipolar, therefore, in the experiments below we normalized it by its `2 norm.

heading: 5 EMPIRICAL EVALUATION

heading: 5.1 SETUP
text: All datasets were preprocessed by removing control characters and stop words (see the Appendix for details). It is also worth noting that the realization of the conventional n-gram statistics used in the experiments was forming a model, which was storing only n-grams present in the train split.
The range of n in the experiments with small datasets was [2 − 4] while for the 20NewsGroups dataset it was [2− 3] since the number of possible 4-grams was overwhelming. All results reported for small datasets were obtained by averaging across 50 independent simulations. In the case of the 20NewsGroups dataset, the number of simulations was decreased to 10 due to high computational costs. To have a fair comparison of computational resources, all results for small datasets were obtained on a dedicated laptop without involving GPUs while the results for the 20NewsGroups dataset were obtained with a computing cluster (CPU only) without the intervention of other users. More details about experimental settings could be found in the Appendix section.

heading: 5.2 RESULTS
text: First, we report the results of the MLP classifier on all datasets as it represents a widely used class of algorithms – neural networks. The goal of the experiments was to observe how the dimensionality of HD vectors embedding n-gram statistics affects the F1 scores and the computational resources. Figures 1a-1d present the results for the AskUbuntu, Chatbot, WebApplication, and 20NewsGroups datasets, respectively. The dimensionality of HD vectors varied as 2k, k ∈ [5, 14]. All figures have an identical structure. Shaded areas depict 95% confidence intervals. Left panels depict the F1 score while right panels depict the train and test speed-ups as well as memory reduction. Note that there are different scales (y-axes) in the right panels. A solid horizontal line indicates 1 for the corresponding y-axis, i.e., the moment when both models consume the same resources.
The results in all figures are consistent in a way that up to a certain point F1 score was increasing with the increasing dimensionality. For the small datasets even small dimensionalities of HD vectors (e.g., 32 = 25) led to the F1 scores, which are far beyond random. For example, for the AskUbuntu dataset, it was 84% of the conventional n-gram statistics F1 score. For the values above 512 the
5It is convenient to use ρ to bind symbol’s HD vector with its position in a sequence.
performance saturation begins. Moreover, the improvements beyond 2048 are marginal. The situation is more complicated for the 20NewsGroups dataset where for 32-dimensional HD vectors F1 score is fairly low though still better than a random guess (0.05). However, it increases steeply until 1024 and achieves its maximum at 4096 being 92% of the conventional n-gram statistics F1 score. The dimensionalities above 4096 showed worse results.
When it comes to computational resources, there is a similar pattern for all the datasets. The train/test speed-ups and memory reduction are diminishing with the increased dimensionality of HD vectors. At the point when the dimensionality of HD vectors equals the size of the conventional n-gram statistics, both approaches consume approximately the same resources. These points in the figures are different because the datasets have different size of n-gram statistics: 3729, 2753, 2734, and 192652, for the AskUbuntu, Chatbot, WebApplication, and 20NewsGroups datasets, respectively. Also, for all datasets, the memory reduction is higher than the speed-ups. The most impressive speed-ups and reductions were observed for the 20NewsGroups dataset (e.g., 186 times less memory for 1024-dimensional HD vectors). This is due to its large size it contains a huge number of ngrams resulting in large size of the n-gram statistics. Nevertheless, even for small datasets, the gains were noticeable. For instance, for the WebApplication dataset at 256 F1 score was 99% of the
conventional n-gram statistics while the train/test speed-ups and the memory reduction were 5.6, 3.4, and 7.6, respectively.
Thus, these empirical results suggest that the quality of embedding w.r.t. the achievable F1 score improves with increased dimensionality, however, after a certain saturation or peak point increasing dimensionality further either does not affect or worsen the classification performance and arguably becomes impractical when considering the computational resources.
Tables 1-36 report the results for three small datasets7 when applying all the considered classifiers. Due to the space limitation, a fixed dimensionality of HD vectors is reported only: 512 for small datasets in Tables 1-3 and 2048 for the 20NewsGroups dataset in Table 9. These dimensionalities were chosen based on the results in Figures 1a-1d as the ones allowing to achieve a good approximation of F1 score while providing substantial speed-up/reduction. We also performed experiments when using the BPE instead of the SemHash before extracting n-gram statistics. Throughout the tables, the BPE demonstrated F1 scores comparable to that of the SemHash while showing the train/test speed-ups and memory reduction at about 2. This is because the usage of the BPE resulted in smaller sizes of the n-gram statistics, which were 2176, 1467, and 1508 for the AskUbuntu, Chatbot, and WebApplication datasets, respectively.
In the case of HD vectors, the picture is less coherent. For example, there is a group of classifiers (e.g., MLP, SGD, KNN) where F1 scores are well approximated (or even improved) while achieving noticeable computational reductions. In the case of Linear SVC, F1 scores are well-preserved and there is 4 − 6 memory reduction but test/train speed-ups are marginal (even slower for training the Chatbot). This is because Linear SVC implementation benefits from sparse representations (con-
6The notations Tr., Ts., Mem. in the tables stand for the train speed-up, test speed-up, and the memory reduction for the given classifier, respectively. SH stands for SemHash.
7 Due to the page limit, results for the 20NewsGroups dataset are presented in the Appendix (see Table 9).
ventional n-gram statistics) while HD vectors in this study are dense. Last, for Bernoulli NB and Random Forest F1 scores were not approximated well (cf. 0.93 vs. 0.82 for Bernoulli NB in the case of the Chatbot). This is likely because both classifiers are relying on local information contained in individual features, which is not the case in HD vectors where information is represented distributively across the whole vector. The slow train time of Random Forest is likely because in the absence of well-separable features it tries to construct large trees.
Last, due to the difference in the implementation (the official implementation of FastText only uses a linear classifier), we were not able to have a proper comparison of computational resources with the FastText.8 However, we obtained the following F1 scores with auto hyperparameter search: 0.91, 0.97, 0.76 for the AskUbuntu, Chatbot, and WebApplication datasets, respectively. These results indicate that for the considered datasets there is no drastic classification performance improvement (even worse for the WebApplication) when using the learned representations of n-grams.

heading: 6 DISCUSSION AND CONCLUSIONS
text: The first observation is that the results on the 20NewsGroups dataset are not the state-of-the-art, which is currently 0.92 F1 score achieved with the BERT model as reported in Mahabal et al. (2019). Nevertheless, it is important to keep in mind that the main goal of the experiments with the 20NewsGroups dataset has been to demonstrate that n-gram statistics embedded into HD vectors allows getting the tradeoff even for a large text corpus. We even observed that for large datasets the usage of HD vectors is likely to provide the best gains in terms of resource-efficiency. Moreover, the gains on the small datasets were also noteworthy (several times). Thus, based on these observations we conclude that HyperEmbed would be a very useful feature in the standard ML libraries. A more general conclusion is that it is worth revisiting results in the area of random projection (Rachkovskij, 2016) as they are likely to allow achieving performance/resources tradeoff in a range of NLP scenarios.
It was stated in Section 3.1 the speed-ups reported above did not include the time for forming HD vectors. The main reason for that is that our Python-based implementation of the method was quite inefficient, especially the cyclic shifts implemented with numpy.roll. At the same time, as it could be seen from the formulation of the embedding method in Section 4.5 its complexity is linear and depends on n as well as on the length of the sample text, thus, fast implementation is doable. We made the proof-of-concept implementation in Matlab, which is much faster. For example, for the AskUbuntu dataset forming 512-dimensional HD vectors of the train split (the same machine) took about 7.5% of the MLP training time, which is a positive result.
Despite the demonstrated tradeoffs between the F1 score and the computational resources, it is extremely hard to have an objective function, which would tell us when the compromise is acceptable and when it is not. In our opinion, a general solution would be to define a utility function, which
8We could have implemented the algorithm ourselves but it can be claimed unfair to compare the required memory and time, if we do not use the best practices, which are unknown to us.
would be able to assign a certain cost to both a unit of performance (e.g., 0.01 increase in F1 score) and a unit of computation (e.g., 10 % decrease in the inference time). The use of the utility function would allow deciding whether an alternative solution, which is, e.g., faster but less accurate, is better or not than the existing one. However, the main challenge here would be to define such a utility function since it would have to be defined for each particular application. Moreover, defining such functions even for the considered classification problems is out of the scope of this study. Nevertheless, we believe that it is the way forward to get an objective comparison criterion.

heading: A EXPERIMENTAL SETTINGS
text: Preprocessing All datasets were preprocessed using the spacy library. It was used to remove stop words from data. We used the spacy model called “en core web lg” to parse the datasets. Last, all text samples were preprocessed by removing control characters; in particular, the ones in the set [Cc], which includes Unicode characters from U+0000 to U+009F.
Since the 20NewsGroups dataset is already large, it does not seem to be necessary to apply the SemHash to it, therefore, it was omitted in the experiments (i.e., SH in Table 9 refers to pure ngrams). Last, the small datasets were augmented, making all smaller classes having the same number of samples as the largest class in the train split for that dataset. Using WordNet as a dictionary, nouns and verbs were swapped with their synonyms creating new sentences until all the classes for that set have the same number of samples. The final distributions are shown in Tables 4–6.
Byte Pair Encoding Vocabulary Size of 1000 was used for WebApplication and AskUbuntu dataset whereas a vocabulary size of 250 was used for Chatbot dataset due to its smaller size. N-gram range of (2-4) was used with analyzer as char. Cross Validation was set to 5.
FastText Autotune Validation was used to find the optimal hyperparameters for all the dataset. No quantization of the model was performed to prevent the compromise on model accuracy.
Hyperparameters In order to find optimal hyperparameters, a grid-based search was applied to three small datasets for the following classifiers: MLP, Random Forest, and KNN. The configuration performing best among all small datasets was chosen to be used in order to report the results reported in the paper. Moreover, the same configuration was used for the 20NewsGroups dataset. In the case of MLP, four different configurations of hidden layers were considered: [(100, 50), (300, 100),(300, 200, 100), and (300, 100, 50)]; (300, 100, 50) configuration has been chosen. The maximal number of MLP iterations was set to 500. In the case of Random Forest, two hyperparameters were optimized number of estimators ([50, 60, 70]) and minimum samples leaf ([1, 11]); we used 50 estimators and 1 leaf. In the case of KNN, the number of neighbors between 3 and 7 was considered; 3 neighbors were used in the experiments. For all the other classifiers the default hyperparameter settings provided by Sklearn library were used.

heading: B DISTRIBUTION OF THE DATASETS
text: Tables 4–7 show the data distribution of the four datasets used in the empirical evaluation.

heading: C ADDITIONAL RESULTS NOT INCLUDED IN THE MAIN TEXT
text: One thing to note in Table 8 is the differences in the F1 scores of the Semantic Hashing approach from the ones reported in Shridhar et al. (2019) for all three small datasets. There were some data augmentation techniques, which were used in the paper, most prominently a QWERTY-based word augmentation accounting for the spelling mistakes. This technique was not used in this work, which resulted in a slight difference in the obtained F1 scores.
Note also that Table 9 does not report the results for the BPE. This is purely due to high computational costs required to obtain the BPE model and vocabulary.

Review summaries:
This paper introduces a technique to project n gram statistic vectors into a lower dimensional space in order to improve memory efficiency and lower training time. The paper is motivated by the important problem of trying to improve efficiency of existing language models which can be extremely resource intensive. The authors then compare the performance of n gram statistics with HD vectors on 4 datasets to demonstrate that embedding into HD vectors can preserve performance while reducing resource utilization.

This paper proposes the use of hyperdimensional (HD) vectors to represent n-gram statistics. The HD vectors are first generated from the whole corpus. Then, it is aggregated or bundled to a vector for each sample as an input of a classifier training. The evaluation is conducted on four datasets: Chatbot, AskUbuntu, WebApplication and 20 News Group using a bunch of classifier including KNN, Random Forest, MLP etc.