HyperEmbed:  Tradeoffs Between Resources and Performance in NLP Tasks with Hyperdimensional Computing enabled embedding of n-gram statistics 
Authors: Pedro Alonso
Kumar Shridhar
Denis Kleyko
Evgeny Osipov
Marcus Liwicki
Venue:  (2020)
Keywords: NLP
Hyperdimensional computing
n-gram statistics
word representation
semantic hashing

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.

Under review as a conference paper at ICLR 2020
HYPEREMBED: TRADEOFFS BETWEEN RESOURCES AND PERFORMANCE IN NLP TASKS WITH HYPERDI- MENSIONAL COMPUTING ENABLED EMBEDDING OF n--GRMM STATISTICS
Anonymous authors authorsss Paper under double-blind review
ABSTRACT
Recent advances in Deep Learning have led to a significant performance increase several NLP tasks, however, the models become tionally demanding. Therefore, this paper tackles the domain of computation- ally efficient algorithms for NLP tasks. In particular, it investigates distributed representations of n-gram statistics of texts. The representations are formed us- ing 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 small dataset, the memory reduction was 1.18 times; while train and test speed-ups were 4.62 and 3.84 times, respectively. For many classifiers 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 n-gram statistics, thus, opening a room for tradeoffs.
and more computa-
the large dataset,
INTRODUCTION
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 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, consider NLP systems using well-known technique called n-gram statisties. The key idea is that hyperdimensional computing (Kanerva 2009) allows forming distributed repre- sentations of the conventional n- n-gram statisties (Joshi al. 2016). The use of these distributed representations, in turn, allows trading-off the performance of an NLP system (e.g., Fi score) and its computational resources (i.e., time and memory). The main contribution of this paper is the systematic study of these tradeoff's on nine machine learning algorithms using several benchmark classification datasets. We demonstrate the usefulness of hyperdimensional computing- based em- bedding, 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 reduce memory usage by 10x and speed-up training by 5x without compromising the Fi score. Several important use-cases are motivating the efforts towards trading-off the performance of system against compu- tational resources required to achieve that performance: high-throughput systems with an extremely large number requests/trnssactios (the power of one per cent); resource-constraing where computational resources and energy scarce (edge computing); green computing systems taking into account the aspects of environmental sustainability when considering the efficiency of algorithms (Al HLEG 2019).
systems

---

Under review as a conference paper at ICLR 2020
The paper is structured as follows. Section covers the related work. Section outlines the eval- uation and describes the datasets. The methods being used are presented in Section Section evaluates of the experimental results. Discussion and concluding remarks are presented in Section 6
2 RELATED WORK
Commonly, data for NLP tasks 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 one- hot 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 Ge (Pennington et al. 20144) 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 Jouuln et al. (2016) by representing words with character n n-grams. Another efficient way of representing word the concept of Byte Pair Encoding, which has been introduced in Gage (1944). The disadvantage of the learnable representations, however, is that they require pretraining involving large train corpus well as have 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- of-the-ar art results on three datasets for intent classification.
The Subword Semantic Hashing, however, relies on n-gram statistics for extracting the represen- tation vector used as an input to classification algorithms. is worth noting that the conventional n-gram statisties 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 that the size of the vector grows exponentially with Nevertheless, it is possible to untie the size of represen- tation from n by using distributed representations (Hinton et al.] 1986), where the information is distributed across the vectors positions. In particular, Poshi et al. (2016) suggest how to embed conventional n- r-gram statistics into a high-dimensional vector (HD vector) using the principles of hyperdimensional computing. Hyperdimensional computing also known Vector Symbolic Ar- chitectures (Plate, 2003) Kanerva 2009; Eliasmith, (013) 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 merdware-friendhe (Rahimi et al., 2016). In Najalabadi 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 NL.P datasets when using the supervised classifiers.
3 EVALUATION OUTLINE
3.1 CLASSIFIERS AND PERFORMANCE METRICS
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-leam 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 compu- tational resources, we have to define metrics for both aspects. The quality of the classification performance of model will be measured by simple and well-known metric Fi score (please
2

---

Under review as a conference paper at ICLR 2020
see (Faweett 2006)). The computational resources will be characterized by three metries: the time it takes to trai 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 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
3.2 DATASETS
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 (WebAppli- cation), 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 al. 2017) are available on GitHub
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, StationDext, Criterion, Vehicle, Line), which were not used in our benchmarks, as the results were only for intent classifi- cation. 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 (ä,ö,ü,B). The dataset has the following data sample distribution (train/test): Departure Time (43/35); Find Connection (57 (57/71).
The AskUbuntu dataset comprises five intents with the following data sample distribution (train/test): Make Update (10/37); Setup Printer (10/13) 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 distribu- tion (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.
4 METHODS
4.1
CONVENTIONAL R-GRAM STATISTICS
An empty vector stores n-gram statistics for an input text D. D consists of symbols from the alpha- bet of size a; ith position in keeps the counter of the corresponding n-gram As = (S), .2....... S..) from the set A of all unique n-grams; Sj corresponds to symbol in jth position of A, The dimen- sionality of s equals the total number of n-grams in & and calculated as a". Usually, s is obtained via a single pass-through D using the overlapping sliding window of size n. The value of position in (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- n-gram in A was observed in D.
is worth noting that the speed-ups reported in Section 5 do include the time it takes obtain the corresponding HD vectors. Please see the discussion this issue in Section 6
Under the Creative Commons CC BY-SA 3.0 license: NLU Rva i
https:: /7g' w thub. cwm/cooceeeeoeeeo schair //
3

---

Under review as a conference paper at ICLR 2020
4.2 WORD EMBEDDINGS WITH SUBWORD INFORMATION
Work by [Bojanowsii et al. (0177) demonstrated that words' representations can be formed via learn- ing character n-gramm, which then summed up to represent words. This method (FastText) has an advantage over the conventional word embeddings since unseen words could be better approxi- mated as it is highly likely that some of their n- n-gram subwords have already appeared in other words. Therefore, each word w is represented as bag of its character n-gram. Special boundary symbols "<" and ">" are added the beginning and the end of each word. The word itself is added 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, No C {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 is defined for each word that is represented as set of respective n-grams and the context word (denoted as c), as:
g(w, c)
Σ gEN
T 2g
Vc:
where ve 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.
4.3 BYTE PAIR ENCODING
The idea of Byte Pair Encoding (BPE) was introduced in Gage 19994). 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 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 counted iteratively and then replaced with new symbol. Each operation results a new symbol, which represents an n-gram. Similarly, frequently occurring n-grams are eventually merged into single symbol. This makes the final vocabulary size equal to the sum of initial vocabulary and number of merge operations.
4.4 WORD SEMANTIC HASIIIGG
Subword Semantic Hashing (SemHash) is described in details in Shridhar et al. (2019): Huang et al. (213). SemHash represents the input sentence in the form of subword tokens using 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 given input sample text T, e.g., "I have flying disk". we split it into a list of words t4. The output of the split would look as follows: "II", "have", "a". "fflyng", "Jisk"]. Each word is then passed into prehashing function H(tt). H((t)) first adds a # at the beginning and at the end of f. Then it generates subwords via extracting n- grams (n=3) from #t e.g., H(have) denoted as t/. where j is the index of a subword. H(t+) is then applied the entire text corpus to generate subwords via n-gram statistics. These subwords are used to extract features for given text.
[H,, hav, ave, ve#). These tri-grams the subwords
4.5 EMBEDDING G-GRAM STATISTICS INTO AN HD VECTOR
Alphabet's 's symbols are the most basic elements of system. We assign each symbol with dom d-dimensional bipolar HD vector. These vectors are stored in a matrix (denoted as H. where H [d x a)), which is referred as the item memory, For given symbol S its HD vector is denoted as Hs E +1]1==1 To manipulate HD vectors, hyperdimensional computing defines three key operations on them: bundling (denoted with + and implemented via position-wise addi-
Please see Kanerva (209) for proper definitions and properties hhhperdimensiooall computing operations. *The bundling operation allows storing information HD vectors Frady al. (2018); if several copies of any HD vector are included (e.g.. 2Hs, + H.,).. ). 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, (0188 for the relevant analysis.
4

---

Under review as a conference paper at ICLR 2020
tion), binding (denoted with @ and implemented via position wise multiplication), and permutation (denoted with p).
Three operations above allow embedding n-gram statistics into distributed representation (HD vec- tor) Joshi et al. (016). First, H is generated for the alphabet. A position of symbol Sy in A, is represented by applying p to the corresponding HD vector Hs, J times, which is denoted as ('H,)). Next, single HD vector for A; (denoted as m mA.) is formed via the consecutive binding of permuted HD vectors p¹ (Hs,) representing symbols in each position j of Ag. For example, the
trigram 'cha' will be mapped to HD vector as follows: p (H.) @ (Hb) @ (Ha,). In general,
the process of forming HD vector of an n can be formalized as follows:
mA: II II (Hs,) j=1
where II denotes the binding operation when applied to n HD vectors. Once it is known how to get m A. embedding the conventional n n-gram statistics stored in (see section 4.1) is straightforward. HD vector h corresponding to 8 is created by bundling together all n-grams observed in the data:
a"'
12
s.m A =
Σ
s:
p (Hs,).
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 Eg norm.
EMPIRICAL EVALUATION
5.1
SETUP
All datasets were preprocessed by removing control characters and stop words (see the Appendix for details). It also worth noting that the realization of the conventional n-gram statistics used in the experiments was forming model, which was storing only n 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 computing cluster (CPU only) without the intervention of other users. More details about experimental settings could be found in the Appendix section.
5.2 RESULTS
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 of HD vectors embedding n-gram statistics affects the Fi scores and the computational resources. Figures La present the results for the AskUbuntu, Chatbot, WebApplication, and 20NewsGroups datasets, respectively. The dimensionality of HD vectors varied as 2*, k E [5, 14). All figures have an identical structure. Shaded areas depict 95% confidence intervals. Left panels depict the Fi score while right panels depict the train and test speed-ups well as memory reduction. Note that there are different scales (y-axes) in the right panels. solid horizontal line indicates I for the corresponding y-axis, i.c., the moment when both models consume the same resources.
to observe how the dimensionality
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 (c.g., 32 = 25) led to the Fi scores, which are far beyond random. For example, for the AskUbuntu dataset, it was 84 % of the conventional n-gram statisties F1 score. For the values above 512 the
'It is convenient use p to bind symbol's HD vector with its position in sequence.
5

---

Under review as a conference paper at ICLR 2020
10
25
Memory
Vemory basetin
8 2
Score
0.9
+ -eemer roductio
Spoed
Speeddup beselree
0.8
man speed-up
up
Memory
+D vectors
Veetor aod
0.7
64
128
256
1024
2048
4098
8192
16384
32
128
2048 Dimensionality of HD vectors
256
512
1024
4096
8182
16984
Dimensionality of vectors
10
Momory
Marrory besel
6 8
Memory reduccion
F. 5cooe
0.9
Marrary reduction
Speed-up base
0.6
HD vectors
Vectorized n-grama
0.7
0-
1024
128
1024 2048 Dimensionality of HD vectors
16384
Dimensionalily of HD vectors
10
8
Memory baod Inc
Memory
8
Memory reduction
F _.oore
0.8
Speed-up
Meenary reduction
Time
Speed-up baselins
0.7
HD vectors
Vector aed n-grame
0.6
128
2048
18384
128
258
512
1024
2048
4086
8182
18364
Dimensionality of HD vectors
Dimensionality of HD vectors
400
4000
300
Marrryy
3000
Memory reduccion
Speed up
Time
200
2000
100
Teal spaedAc
1000
Vactorized n-gnams
32
64
129
256
512
1024
2048
4096
8182
18384
32
64
128
256
512
1024
2048
4096
8192
16984
Dimensionality of
Dimensionality HD
(d)
Figure 1: MLP results the dimensionality of HD vectors (a) the AskUbuntu dataset. (b) the Chatbot dataset. (c) the WebApplication dataset. (d) the 20NewsGroups dataset.
performance saturation begins. Moreover, the improvements beyond 2048 marginal. The situ- ation is more complicated for the 20NewsGroups dataset where for 32-dimensional HD vectors Fj score is fairly low though still better than random guess (0.05). However, increases steeply until 1024 and achieves its maximum at 4096 being 92 % of the conventional n-gram statistics Fi 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 statisties, both approaches consume approximately the same resources. These points 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 1124-dimensiona HD vectors). This is due to its large size it contains huge number of n- grams resulting in large size the n- n-gram statistics. Nevertheless, even for small datasets, the gains noticeable. For instance, for the WebApplication dataset at 256 F score 99 % of the

---

Under review as a conference paper at ICLR 2020
Table Performance of all classifiers for the AskUbuntu dataset.
Fi score
Resources:
SH
vs. HD
Resources: SH vs. BPE
Classifier
SH
BPE
HD
Tr.
Ts.
Mem.
Tr.
Ts.
Mem.
MLP
0.92
0.91
0.91
4.62
3.84
6.18
1.67
1.61
1.72
Passive Aggr.
0.92
0.93
0.90
4.86
3.07
6.3L
2.19
2.14
1.76
SGD Classifier
0.89
0..9
0.88
4.66
3.50
-6.r
I,94
2.16
1.76
Ridge Classifier
0.90
0.91
0.90
3,91
4.74
6.31
I.63
1.62
1.76
KNN Classifier
0.79
'.722
0.82
2.T1
4.53
8.48
I,56
1.79
1.76
Nearest Centroid
0.90
0.89
0.90
1.66
3.41
6.32
1.35
1.87
1.76
Linear SVC
0.90
0.92
0,90
1.18
2.39
6,29
0.91
1,91
1.76
Random Forest
0.88
0.90
0.86
0.91
1.09
6.11
1.15
0.96
1.75
Bernoulli NB
0.91
0.92
0.85
2.30
3.72
6.34
1.96
2.42
1.76
Table 2: Performance of all classifiers for the Chatbot dataset.
Fi score
Resources: SH
HD
Resources: SH
BPE
Classifier
SH
BPE
HD
Tr.
Ts.
Mem.
Tr.
Ts.
Mcm.
MLP
0.96
0.94
0.96
3.42
2.62
4.58
1.86
1.52
1.86
Passive Aggr.
0.95
0.91
0.94
4.40
2.38
4.72
2.29
2.22
1.92
SGD Classifier
0.93
0..33
0.92
3.16
2.06
4.72
1.88
1.84
1.92
Ridge Classifier
0.94
00.94
0.92
2.88
2.22
4.72
T.67
1.38
7.92
KNN Classifier
0.75
'0.7
0.83
1.66
3.59
6.3L
I,43
1.79
1.92
Nearest Centroid
0.89
0.94
0.84
1.41
2.13
4.73
I.17
1.61
1.92
Linear SVC
0.94
0.93
0.94
0.52
1.57
4.72
1.28
1.66
1.92
Random Forest
0.95
0.95
0.91
0.95
1.10
4.61
1.16
0.98
1.91
Bernoulli NB
0.93
0.93
0.82
1.92
2.60
4.73
1.53
1.72
1.92
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 Fj 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 report the results for three small datasets when applying all the considered classifiers. Due to the space limitation, fixed dimensionality of HD vectors is reported only: 512 for small datasets in Tables 3 and 2048 for the 20NewsGroups dataset Table / These dimensionalities were chosen based the results in Figures Ta ld the ones allowing to achieve good approxi- mation Fj score while providing substantial speed-up/reduution.. 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 Ask 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., MIP, SGD, KNN) where Fi scores are well approximated (or even improved) while achieving noticeable computational reductions. In the case of Linear SVC. Fi scores are well-preserved and there is 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-
TThe notations Tr., Ts., Mem. the tables stand for train speed-up, test speed-up, and the memory reduction for the given classifier, respectively. SH stands for SemHash. Due the page limit, results for the 20NewsGroups dataset are presented in the Appendix (see Table 0

---

Under review as a conference paper at ICLR 2020
Table Performance of all classifiers for the WebApplication dataset.
Fi score
Resources:
SH
vs.
HD
Resources: SH vs. BPE
Classifier
SH
BPE
HD
Tr.
Ts.
Mem.
Tr.
Ts.
Mem.
MLP
0.77
0.77
0.79
3.10
2.00
4.43
1.74
1.44
1.73
Passive Aggr.
0.82
0.80
0.80
3.73
1.45
4.33
T.86
1.32
1.75
SGD Classifier
0.75
'0.7
0.73
3.01
L87
4.33
I.62
1.32
-
1.75
Ridge Classifier
0.79
0.80
0.80
1.66
2.40
4.34
0.71
1.09
1.75
KNN Classifier
0.72
'0.75
0.76
I.16
2.76
3,96
1.14
1.51
1.76
Nearest Centroid
0.74
0.73
0.77
1.42
1.79
4.34
1.13
1.21
1.75
Linear SVC
0.82
0.80
0,80
1.04
1.48
4.29
0,47
1.18
1.75
Random Forest
0.87
0.85
0.72
0.95
1.26
4.11
1.05
1.12
1.73
Bernoulli NB
0.74
0.75
0.64
1.31
2.08
4.38
1.19
1.49
1.75
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 con- tained individual features, which is not the case in HD vectors where information represented distributively across the whole vector. The slow train time of Random Forest is likely because in the absence of well-separable features tries to construct large trees.
Last, due to the difference in the implementation (the official implementation of FastText only linear classifier), we were not able to have a proper comparison of computational resources with the obtained the following Fi scores with auto hyperparameter search: 0.91,
FastText [] However, 0.97, 0.76 for the AskUbuntu, Chatbot, and WehApplication datasets, respectively. These results indicate that for the considered datasets there is drastic classification performance improvement (even worse for the WebApplication) when using the learned representations of n-grams.
DISCUSSION AND CONCLUSIONS
The first observation is that the results on the 20NewsGroups dataset are not the state-of-the-ar which is currently 0.92 Fj score achieved with the BERT model reported in Mahahal et al. (2019). Nevertheless, it is important to keep in mind that the main goal the experiments with the 20NewsGroups dataset has been demonstrate that n-gram statistics embedded into HD vec- tors allows getting the tradeoff even for large text corpus. We even observed that for large datasets the usage of HD vectors likely to provide the best gains in terms of resource-efficienn -oource-efficiency. More- over, the gains on the small datasets were also noteworthy (several times). Thus, based on these observations we conclude that HyperEmbed would be very useful feature in the standard ML libraries. A more general conclusion is that it is worth revisiting results in the area of random pro- jection (Rachkovskij) (016)) as they are likely to allow achieving performance/resourees tradeoff in range of NLP scenarios.
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 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 5 512-dimensional HD vectors of the train split (the same machine) took about 7.5 % of the MLP training time, which is positive result.
Despite the demonstrated tradeoff's between the Fi score and the computational resources, it is extremely hard have objective function, which would tell when the compromise is acceptable and when it is not. In our opinion, a general solution would be to define utility function, which
'We could have implemented the algorithm ourselves but it can be claimed unfair to compare the required memory and time, if we do use the best practices, which unknown us.
8

---

Under review as a conference paper at ICLR 2020
would be able assign certain cost both 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 the utility function would allow deciding whether 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 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, believe that is the way forward get an objective comparison criterion.
REFERENCES
AI HLEG. High-Level Expert Group on Artificial Intelligence. Ethics Guidelines for Trustworthy AI. 2019.
P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov. Enriching Word Vectors with Subword Infor- mation. Transactions of the Association for Computational Linguistics, 5:135-146, 2017.
D. Braun, A. Hemandez-Mendeer F. Matthes, and M. Langen. Evaluating Natural Language Un- derstanding Services for Conversational Question Answering Systems. Anmual Meeting of the Special Interest Group Discourse and Dialogue (SIGDIAI.), pp. 174-185, 2017.
C. Fliasmith. How to Build a Brain. Oxford University Press, 2013.
Fawcett. An Introduction ROC Analysis. Pattern Recognition Letters, 27:861-874, 2006.
E.P. Frady, D. Kleyko, and F.T. Sommer. A Theory of Sequence Indexing and Working Memory in Recurrent Neural Networks. Neural Computation, 30:1449 $0:1449-1513 2018.
P. Gage. A New Algorithm for Data Compression. The C Users Journal, 12(2):23-38, 1994.
G.E. Hinton, J.L McClelland, and D.E. Rumelhart, Distributed Representations. In D.E. Rumelhart and J.L. McClelland (eds.), Parallel Distributed Processing. Explorations in the Microstructure of Cognition, Volume 1. Foundations, pp. 77-109. MIT Press, 1986.
Huang, X.He, J. Gao, L., Deng, Acero, and I.. Heck, Learning Deep Structured Semantic Mod- els for Web Search using Clickthrough Data. In ACM international conference on Information and Knowledge Management (CIKM), pp. 2333-2338, 2013.
A. Joshi, J.T. Halseth, and P. Kanerva. Language Geometry Using Random Indexing. In Quantum Interaction (Q!), pp. 265-274, 2016.
A. Joulin, E. Grave, P. Bojanowski, and Mikolov. Bag of Tricks for Efficient Text Classification. 11Xiv:160. 2016.
Kanerva. Hyperdimensional Computing: An Introduction Computing in Distributed Represen- tation with High-Dimensional Random Vectors. Cognitive Computation, (32):139-19, 2009.
D. Kleyko, E. Osipov, D. De Silva, U. Wiklund, Vyatkin, and D. Alahakoon. Distributed Repre- sentation of n-gram Statistics for Boosting Self- Self-Organizing Maps with Hyperdimensional Com- puting. In The Ershov Informatics Conference (PSI), pp. 1-16, 2019.
Kohonen. Self-Organizing Maps. Springer Series in Information Sciences, 2001.
A. Mahabal, J. Baldridge, B. K. Ayan, V. Perot, and D. Roth. Text Classification with Few Examples using Controlled Generalization. In Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT), 3158-38 3167, 2019.
Mikolov, Chen, Corrado, and Dean. Efficient Estimation of Word Representations in Vector Space. arXiv:1301.378/ 2013.
F.R. Najafabadi, A. Rahimi, P. Kanerva, and J.M. Rabaey. Hyperdimensional Computing for Text Classification. In Design, Automation and Test in Europe Conference (DATE), pp. 1-1, 2016.

---

Under review as a conference paper at ICLR 2020
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Couraaeeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
J. Pennington, R. Socher, and C. D. Manning. GloVe: Global Vectors for Word Representation. In Conference on Empirical Methods in Natural Language Processing (EMNLP), volume 14, pp. 1532-1543, 2014.
T. A. Plate. Holographic Reduced Representations: Distributed Representation for Cognitive Struc- tures. Stanford: Center for the Study of Language and Information (CSLI), 2003.
D.A. Rachkovskij. Real-Valued Embeddings and Sketches for Fast Distance and Similarity Estima- tion. Cybernetics and Systems Analysis, 52(6):967-99) 2016.
A. Rahimi, P. Kanerva, and J.M. Rabaey. A Robust and Energy Efficient Classifier Using Brain- Inspired Hyperdimensional Computing. In /EEE/ACM International Symposium on Low Power Electronics and Design (ISLPED), pp. 64 69, 2016.
K. Shridhar, A. Dash, A. Sahu, G. Grund Pihlgren, Alonso, Pondenkandath, G. Kovacs, Simi- stira, and M. Liwicki. Subword Semantic Hashing for Intent Classification on Small Datasets. In International Joint Conference on Neural Networks (IJCN)), pp. 1-6, 2019.
E. Strubell, A. Ganesh, and A. McCallum. Energy and Policy Considerations for Deep Learning in NLP. arXiv: 02244, pp. 1-6, 2019.
10

---

Under review as a conference paper at ICLR 2020
A EXPERIMENTAL SETTINGS
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_weld Ig" 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, was omitted in the experiments (i.e.. SH in Table Sable/recte refers to pure n- grams). 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 samples. The final distributions are shown in Tables
Byte Pair Encoding Vocabulary Size of 1000 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) used with analyzer as char. Cross Validation set 5.
FastText Autotune Validation was used to find the optimal hyperparameters for all the dataset. No quantization of the model was performed 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 configura- tion 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 MIP, four different configurations of hidden layers
considered: [(100, 50), (300, 130), 200, 100), and (300, 100, 50)]: (300, 100, 50) configuration has been chosen. The maxi- mal number of MLP iterations was were optimized number of estimators ([50, 60, 70]) and minimum samples leaf ([1, 11];; we used 50 estimators and leaf. In the case of KNN, the number of neighbors between and was considered; 3 neighbors were used in the experiments. For all the other classifiers the default hyperparameter settings provided by Sklearn library were used.
500. In the case of Random Forest, two hyperparameters
B DISTRIBUTION OF THE DATASETS
Tables show the data distribution of the four datasets used the empirical evaluation.
Table 4: Data sample distribution for the Chatbot dataset
Intent
Train original
Train Augmented
Test
Departure Time
43
57
35
Find Connection
57
57
71
Table 5: Data sample distribution for the AskUbuntu dataset
Intent
Train original
Train Augmented
Test
Make Update
10
17
37
Setup Printer
10
Shutdown Computer
13
17
14
Software Recommendation
17
17
None
17
11

---

Under review as a conference paper at ICLR 2020
Table Data sample distribution for the WebApplication dataset
Intent
Train original
Train Augmented
Test
Change Password
Delete Account
Download Video
0
Export Data
Filter Spam
14
Find Alternative
Sync Accounts
None
Table 7: Data sample distribution for the 20NewsGroups dataset
Categories
Train
Test
alt.atheism
11314
7532
comp-graphic.
11314
7532
comp.os.m. os-mss www.mms-wiindo windows misc
11314
7532
comp.sys.. www.isy.ss......omoomm pc.hardwarr
11314
7532
comp-sys.mace mac.mardwawaee
11314
7532
comp.wine windows.x
11314
7532
misc.forsale
11314
7532
rec.autos
11314
7532
rec.motorcycles
11314
7532
rec.sport. baseball cec.sport.baseball
11314
7532
rec. pec.sport.hockey
11314
7532
sci.erypt sci.electronics
11314
7532
11314
7532
sci.electronics
11314
7532
sci.space soc.religion.christe christian
11314
7532
11314
7532
talk.politics. guns talk, talk.politics. powitocs. mideest
11314
7532
11314
7532
talk, politics.mii misc
11314
7532
talk. mal.koeligion.mie
11314
7532
12

---

Under review as a conference paper at ICLR 2020
C ADDITIONAL RESULTS NOT INCLUDED IN THE MAIN TEXT
One thing to note Table is the differences in the F1 scores of the Semantic Hashing approach from the ones reported in Shridhar 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 used in this work, which resulted in slight difference in the obtained F1 scores.
Note also that Table 9 does not report the results for the BPE. This purely due high computa- tional costs required to obtain the BPE model and vocabulary.
Table 8: Fi score comparison of various platforms on three smaller datasets with methods mentioned the paper. Some results are taken from Shridhar et al. (2019)
Platform
Chatbot
AskUbuntu
WebApp
Average
Botfuel
0.98
0.90
0.80
0.89
Luuis"
0.98
0.90
0.81
00.90
Dialogflow
0.93
0.85
0.80
0.86
Watson
0.97
0.92
0.83
0.91
RRaaa
0.98
0,86
0.74
0,86
Snips
0.96
0.83
0.78
0.86
Recast
0.99
0.86
0.75
0.87
TildeCNN
0.99
0.92
0.81
"0.9T
FastText
0.97
0.91
0.76
0.88
SemHash
0.96
0.92
0.87
0.92
BPE
0.95
0.93
0.85
0.91
HD vectors
0.97
0.92
0.82
0.90
Table 9: Performance of all classifiers for the 20NewsGroups dataset.
Fi score
Resources: SH vs. HD
Classifier
SH
HD
Train speed-up
Test speed-up
Memory reduction
MLP
0.72
0.64
53.23
79.50
93.19
Passive Aggr.
0.74
0.69
103.64
202.95
93.42
SGD Classifier
0.70
0.66
105.43
186.31
93.42
Ridge Classifier
0.16
0..1
"45.46
338.01
993.22
KNN Classifier
0.31
'0.3T
184.47
65.87
127.54
Nearest Centroid
0.08
70.1
2I2.75
225.74
99.42
Linear SVC
0.75
0.69
5.11
176.62
93.42
Random Forest
0.58
0.26
4.27
21.43
93.41
Bernouli NB
0.60
0.15
57.72
56.54
93.42
13


Reviews:
[{"review_id": "Skgx6y4AYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows a trade-off relationship between computational cost (memory usage, train/test time) and performance on several NLP machine learning algorithms that use n-gram statistics. The authors claim that a simple n-gram representation vector with a conventional classifier (MLP, SVC, Naive Bayes...) is computationally efficient.\n\nThe large set of experiments on various conventional NLP models and n-gram statistics provide detail information about the trade-off relation between performance and computational cost. My concern is that the computational efficiency of the conventional NLP model is well known to NLP researchers. It would be nice if the authors provide a more persuasive explanation for the importance of this research question.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJg_XJYAtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nIt is interesting to see how to hash/project the high dimensional n-gram vector into a lower space for efficiency. The approach is useful in online production systems, and it is eco-friendly. However, there are a few concerns detailed as follows:\n\n1. Can it be generalized to contemporary learned embeddings, e.g., word2vec and GloVe? \n\n2. Lack of proper baselines for comparison. Word2vec, GloVe are trained on large corpora once and can be applied directly to other tasks, and they should be served as baselines. Furthermore, the simple bag of word/TF-IDF should be included as baselines as well.\n\n3. Lack of analysis: it is hard to understand what kind of HD vectors are generated. Are these n-grams semantically related projected nearby in the HD space? This helps readers to understand the constructed embeddings.\n\n4. The SentEval benchmark is popular in sentence level representation learning and it is well known. It is better to see some evaluations on it as well. http://www.lrec-conf.org/proceedings/lrec2018/pdf/757.pdf\n\nMinor comments: \n1. The Subword Semantic Hashing is originally from DSSM published in 2013.  (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/cikm2013_DSSM_fullversion.pdf) \n2. What is $v_c$ in 4.2?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BylO6qgtnB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n\t1. The main methodological contribution (using HD vectors) are a nice contribution. I would like the authors to clarify why they chose those 3 operations to operate on vectors for this particular task. \n\t2. Lack of a competitive baseline : I would like to see how this method compares with existing techniques to speedup n grams such as Pibiri et al. (https://arxiv.org/pdf/1806.09447.pdf). I believe there are other works which work on speeding up n gram models as well but not comparison is presented.  \n\t3. Minor comment: the authors mention using a SGD classifier but I fail to understand what they mean by this. SGD is an optimization technique and not a classifier so I would like the authors to correct this in the paper.  \n\nAs it currently stands, the lack of strong baselines and the incremental nature of the contribution lead me to believe that this paper does not represent a sufficient advance to warrant publication. I would advise the authors to consider submitting to a more specialized venue (in NLP).\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were unanimous that this submission is not ready for publication at ICLR in its present form.

Concerns raised included lack of relevant baselines, and lack of sufficient justification of the novelty and impact of the approach.
Decision: Reject