Title: COMPACT EMBEDDING OF BINARY-CODED INPUTS AND OUTPUTS USING BLOOM FILTERS

Abstract: The size of neural network models that deal with sparse inputs and outputs is often dominated by the dimensionality of those inputs and outputs. Large models with high-dimensional inputs and outputs are difficult to train due to the limited memory of graphical processing units, and difficult to deploy on mobile devices with limited hardware. To address these difficulties, we propose Bloom embeddings, a compression technique that can be applied to the input and output of neural network models dealing with sparse high-dimensional binary-coded instances. Bloom embeddings are computationally efficient, and do not seriously compromise the accuracy of the model up to 1/5 compression ratios. In some cases, they even improve over the original accuracy, with relative increases up to 12%. We evaluate Bloom embeddings on 7 data sets and compare it against 4 alternative methods, obtaining favorable results. We also discuss a number of further advantages of Bloom embeddings, such as 'on-the-fly' constant-time operation, zero or marginal space requirements, training time speedups, or the fact that they do not require any change to the core model architecture or training configuration.

1. INTRODUCTION:

The size of neural network models that deal with sparse inputs and outputs is often dominated by the dimensionality of such inputs and outputs. This is the case, for instance, with recommender systems, where high-dimensional sparse vectors, typically in the order from tens of thousands to hundreds of millions, constitute both the input and the output of the model (e.g., Wu et al., 2016; Hidasi et al., 2016; Cheng et al., 2016; Strub et al., 2016) . This results in large models that present a number of difficulties, both at training and prediction stages. Apart from training and prediction times, an obvious bottleneck of such models is space: their size (and even performance) is hampered by the physical memory of graphical processing units (GPUs), and they are difficult to deploy on mobile devices with limited hardware (cf. Han et al., 2016) .

One option to reduce the size of sparse inputs and outputs is to embed them into a lower-dimensional space. Embedding sparse high-dimensional inputs is commonplace (e.g., Bengio et al., 2000; Turian et al., 2010; Mikolov et al., 2013) . However, embedding sparse high-dimensional outputs, or even inputs and outputs at the same time, is much less common (cf. Weston et al., 2002; Bengio et al., 2010; Akata et al., 2015) . Importantly, typical embeddings still require the storage and processing of large matrices with the same dimensionality as the input/output (like the original neural network model would do). Thus, the gains in terms of space are limited. As mentioned, the size of such models is dominated by the input/output dimensionality, with input and output layers representing about 99.94% of the total amount of weights of the model1 .

In general, an ideal embedding procedure for sparse high-dimensional inputs/outputs should produce compact embeddings, of much lower dimensionality than the original input/output. In addition, it should consume little space, both in terms of storage and memory space. Smaller sizes imply less parameters, thus training the model on embedded vectors would also be faster than with the original instances. The embedding of the output should also lead to a formulation for which the appropriate loss should be clear. Embeddings should not compromise the accuracy of the model nor the required number of training epochs to obtain that accuracy. In addition, no changes to the original core architecture of the model should be required to achieve good performance (obviously, input/output dimensions must change). The embedding should also be fast; if not to be done directly 'on-the-fly', at least fast enough so that speed improvements made during training are not lost in the embedding operation. Last, but not least, output embeddings should be easily reversible, so that the output of the model could be mapped to the original items at prediction time.

In this paper, we propose an unsupervised embedding technique that fulfills all the previous requirements. It can be applied to both input and output layers of neural network models that deal with binary (one-hot encoded) inputs and/or outputs. In addition, it produces lower-dimensionality binary embeddings that can be easily mapped to the original instances. Provided that the embedding dimension is not too low, the accuracy is not compromised. Furthermore, in some cases, we show that training with embedded vectors can even increase prediction accuracy. The embedding requires no changes to the core network structure nor to the model configuration, and works with a softmax output, the most common output activation for binary-coded instances. As it is unsupervised, the embedding does not require any preliminary training. Moreover, it is a constant-time operation that can be either performed on-the-fly, requiring no disk or memory space, or can be cached in memory, occupying orders of magnitude less space than a typical embedding matrix. Lower dimensionality of input/output vectors result in faster training, and the mapping from the embedded space to the original one does not add an overwhelming amount of time to the prediction stage. The proposed embedding is based on the idea of Bloom filters (Bloom, 1970) , and therefore it inherits part of the theory developed around that idea (Blustein & El-Maazawi, 2002; Dillinger & Manolios, 2004; Mitzenmacher & Upfal, 2005; Bonomi et al., 2006) .

2. RELATED WORK:

A common approach to embed high-dimensional inputs is the hashing trick (Langford et al., 2007; Shi et al., 2009; Weinberger et al., 2009) . However, the hashing trick approach does not deal with outputs, as it offers no explicit way to map back from the (dense) embedding space to the original space. A more elementary version of the hashing trick (Ganchev & Dredze, 2008) can be used at the outputs by considering it as a special case of the Bloom-based methodology proposed here. A framework providing both encoding and decoding strategies is the error-correcting output codes (ECOC) framework (Dietterich & Bakiri, 1995) . Originally designed for single-class outputs, it can be also applied to class sets (Armano et al., 2012) . The compressed sensing approach of Hsu et al. (2009) builds on top of ECOC to reduce multi-label regression to binary regression problems. Similarly, Cissé et al. (2013) use Bloom filters to reduce multi-label classification to binary classification problems and improve the robustness of individual binary classifiers' errors. Another example of a framework offering recovery capabilities is kernel dependency estimation (Weston et al., 2002) .

Data-dependent embeddings that require some form of learning also exist. A typical approach is to rely on variants of latent semantic analysis or singular value decomposition (SVD), exploiting similarities or correlations that may be present in the data. Again, the issue of mapping from the embedding space to the original space is left unresolved. Nonetheless, recently, Chollet (2016) has successfully applied a K-nearest neighbors (KNN) algorithm to perform such a mapping and to derive a ranking of the elements in the original space. An SVD decomposition of the pairwise mutual information matrix (PMI) is used to perform the embedding, and cosine similarity is used as loss function and to retrieve neighbors. Using the KNN trick offers the possibility to exploit different types of factorization of similarity-based matrices. Canonical correlation analysis is an example that considers both inputs and outputs at the same time (Hotelling, 1936) . Other examples considering output embeddings are nuclear norm regularized learning (Amit et al., 2007) , label embedding trees (Bengio et al., 2010) , or the WSABIE algorithm (Weston et al., 2010) . In the presence of side information, like text descriptions, element or class taxonomies, or manually-collected data, a range of approaches are applicable. Akata et al. (2015) provide a comprehensive list. In our study, we assume no side information is available and focus on input/output-based embeddings.

From a more general perspective, reducing the space of (or compressing) neural network models is an active research topic, driven by the need to deploy such models in systems with limited hardware resources. A common approach is to reduce the size of already trained models by some quantization and/or pruning of the connections in dense layers (Courbariaux et al., 2015; Han et al., 2016; Kim et al., 2016) . A less frequently used approach is to reduce the model size before training (Chen et al., 2015) . These methods typically do not focus on input layers and, to the best of our knowledge, none of them deals with high-dimensional outputs. It is also worth noting that a number of techniques have been proposed to efficiently deal with high-dimensional outputs, specially in the natural language processing domain. The hierarchical softmax approach (Morin & Bengio, 2005) or the more recent adaptive softmax (Grave et al., 2016) are two examples of those. Yet, as mentioned, the focus of these works is on speed, not on space. The work of Vincent et al. (2015) focuses on both aspects of very large sparse outputs but, to the best of our knowledge, cannot be applied to traditional softmax outputs.

3 BLOOM EMBEDDINGS 3.1 BLOOM FILTERS Bloom filters (Bloom, 1970) are a compact probabilistic data structure that is used to represent sets of elements, and to efficiently check whether an element is a member of a set (Mitzenmacher & Upfal, 2005) . Since the instances we deal with represent sets of one-hot encoded elements, Bloom filters are an interesting option to embed those in a compact space with good recovery (or checking) guarantees.

In essence, Bloom filters project every element of a set to k different positions of a binary array u of size m. Projections are done using a set of k independent hash functions H = {H i } k i=1 , each of which with a range from 1 to m, ideally distributing the projected elements uniformly at random (Mitzenmacher & Upfal, 2005) . Proper independent hash functions can be derived using enhanced double hashing or triple hashing (Dillinger & Manolios, 2004) . The number of hash functions k is usually a constant, k m, proportional to the expected number of elements to be projected.

To check if an element is in u, one feeds it to the k hash functions H to get k array positions. If any of the bits at these positions is 0, then the element is definitely not in the set. Thus, element checks return no false negatives, meaning that the structure gives an answer with 100% recall (Mitzenmacher & Upfal, 2005) . However, if all k bits at the projected positions are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other set elements. This implies that false positives are possible, due to collisions between projections of different elements (Blustein & El-Maazawi, 2002) . The values of m and k can be adjusted to control the probability of such collisions. However, in practice, m is usually constrained by space requirements, and k ≤ 10 is employed, independent of the number of elements to be projected, and giving less than 1% false positive probability (Bonomi et al., 2006) .

3.2. EMBEDDING AND RECOVERY:

In the following, we describe the use of Bloom filter techniques in embedding binary highdimensional instances, and the recovery or mapping to such instances from these embeddings. We denote our approach as Bloom embedding (BE). The idea we pursue is to embed both inputs and outputs and to perform training in the embedding space. To do so, only a probability-based output activation is required, together with a loss function that is appropriate for such activations.

Let x be an input or output instance with dimensionality d, such that x = [x 1 , . . . x d ], x i ∈ {0, 1}. Instances x are assumed to be sparse, that is,

d i=1 x i d.

Because of that, we can more conveniently (and compactly) represent x as set z = {z i } c i=1 , z i ∈ N ≤d , where c is the number of non-zero elements and z i is the position of such elements in x. For every set z, we generate an embedded instance u of dimensionality m < d, such that u = [u 1 , . . . u m ], u i ∈ {0, 1}. To do so, we first set all m components of u to 0. Then, iteratively, for every element z i , i = 1, . . . c, and every projection H j , j = 1, . . . k, we assign u Hj (zi) = 1.

(1)

Notice that, since H j has a range between 1 and m, k ≥ 1, and m < d, a number of z i elements may map to the same index of u. Bloom filters mitigate this by properly choosing k independent hash functions H (see above). Notice furthermore that the process has no space requirements, as H is computed on-the-fly. Finally, notice that the embedding of a set z is constant time: the process is O(ck), with c bounded by the maximum number of non-sparse elements in x, c d, and k being a constant that is set beforehand, k m < d. In practice, this constant time is dominated by the time spent on H to generate a hash. If we want to be faster than that, and at the same time ensure an optimal (uniform) distribution of the outputs of H, we can decide to compromise part of the available memory to pre-compute a hash matrix storing the projections or hash indices for allthe potential elements in z. We can do it by generating vectors h = [h 1 , . . . h k ] for each z i , where h j is a uniformly randomly chosen integer between 1 and m (without replacement). This way, by pregenerating all projections for all d elements, we end up with a d × k matrix H of integers between 1 and m, which we can easily store in random-access memory (RAM), not in the GPU memory.

We now explain how to recover a probability-based ranking of the d elements of x at the output of the model. Assuming a softmax activation is used, we have a probability vector v = [v 1 , . . . v m ] that, at training time, is compared to the binary embedding u of some ground truth set z (or vector x). We can think of v i as the probability of being the projection of some element z l , that is, v i ∼ P (u i = 1) ∼ P (H j (z l ) = i) (see Eq. 1). To unravel the embedding v and map to the d original elements of x, we can understand v as a k-way factorization of every element x i . Following the idea of Bloom filters, if an element maps to u i and v i = 0, then the element is definitely not in the output of the model. Otherwise, if an element maps to u i and v i is relatively large, we want the likelihood of that element to reflect that. Specifically, given an element position z i from x, we can compute the likelihood of z i as

EQUATION

and assign outputs

x i = L(z i ).

Alternatively, if a more numerically-stable output is desired, we can compute the negative log-likelihood

EQUATION

Both operations, when iterated for i = 1, . . . d, define a ranking over the elements in x, which is the most common way to define (and evaluate) sparse high-dimensional outputs. One could potentially also recover a probability distribution by re-normalization, but the problems we consider are information retrieval-type of problems (Manning et al., 2008) , which are typically seen as ranking problems, such as ranking recommendations based on user preferences (Weimer et al., 2008) .

Note that BE, by construction, already offers a number of the aforementioned desired qualities for sparse high-dimensional embeddings (Sec. 1). Specifically, BE is designed for both inputs and outputs, offering a rank-based mapping between the original instances and the embedded vectors. BE yields a more compact representation of the original instance and requires no disk or memory space (at most some marginal RAM space, not GPU memory). In addition, BE can be performed on-the-fly, without training, and in constant time. In the following, we demonstrate the remaining desirable qualities using a comprehensive experimental setup: we show that the accuracy of the model is not compromised given a reasonable embedding dimension (sometimes it even improves), that no changes in the model architecture nor configuration are required, that training times are faster thanks to the reduction of the number of parameters of the model, that evaluation times do not carry much overhead, and that performance is generally better than a number of alternative approaches.

4. EXPERIMENTAL SETUP:



4.1. GENERAL CONSIDERATIONS:

We demonstrate that BE works under several settings and that it can be applied to multiple tasks.

We consider a number of data sets, network architectures, configurations, and evaluation measures.

In total, we define 7 different setups, which we summarize in Sec. 4.2 and detail in Appendix A. We Data sets are formed by inputs with n instances, corresponding to either individual instances (or onehot encoded user profiles) or to sequences of instances (or profile lists). Outputs, also of n instances, correspond to individual instances or to class labels. Instances have an original dimensionality d, corresponding to the cardinality of all possible profile items. Given the nature of the considered problems, instances are very sparse, with all but c elements being different from 0, c d, typically with c/d in the order of 10 -5 (Table 1 ).

For each data set, and based on the literature, we select an appropriate baseline neural network architecture. We experiment with both feed-forward (autoencoder-like) and recurrent networks, carefully selecting their parameters and configuration to match (or even improve) the state-of-theart results. For the sake of comparison, we also choose appropriate and well-known evaluation measures. Depending on the data set, we work with mean average precision, reciprocal ranks, or accuracy (Manning et al., 2008) .

Each combination of data set, network architecture, configuration, and evaluation measure defines a task. For every task, we compute a baseline score S 0 , corresponding to running the plain neural network model without any embedding. We then report the performance of the i-th combination of training with a particular embedding on a particular task with respect to the baseline score using S i /S 0 . This way, we can compare the performance across different tasks using different evaluation measures, reporting relative improvement/loss with respect to the baseline. Similarly, to compare across different dimensionalities, we report the ratio of embedding dimensionality with respect to the original dimensionality, m/d, and to compare across different training and evaluation times, we report time ratios with respect to the baseline, T i /T 0 .

4.2. TASKS:

We now give a brief summary of the 7 considered tasks (Tables 1 and 2 ). For a more detailed explanation related to data, network architecture, configuration, or evaluation methodology, we refer the reader to Appendix A. Further references can be also found there. All data sets are publiclyavailable, and for all tasks we use categorical cross-entropy as loss function.

1. Movielens (ML): movie recommendation with the Movielens data set (Harper & Konstan, 2015) . We employ a 3-layer feed-forward neural network model and optimize its parameters with Adam. We evaluate the accuracy of the model with mean average precision.

2. Penn treebank (PTB): next word prediction with the Penn treebank data set (Mikolov, 2012) . We employ a long short-term memory (LSTM) network and optimize its parameters with stochastic gradient descent (SGD). We evaluate the accuracy of the model with the reciprocal rank of the correct prediction.

3. CADE web directory (CADE): text categorization with the CADE web directory data set (Cardoso-Cachopo, 2007) . We employ a 4-layer feed-forward neural network model and optimize its parameters with RMSprop. This is the only considered task where output embeddings are not required (classification into 12 text categories). We use accuracy as evaluation measure.

4. Million song data set (MSD): song recommendation with the Million song data set (Bertin-Mahieux et al., 2011) . We employ a 3-layer feed-forward neural network model and optimize its parameters with Adam. We evaluate the accuracy of the model with mean average precision.

5. Amazon book reviews (AMZ): book recommendation with the Amazon book reviews data set (McAuley et al., 2015) . We employ a 4-layer feed-forward neural network and optimize its parameters with Adam. We evaluate the accuracy of the model with mean average precision.

6. Book crossing (BC): book recommendation with the book crossing data set (Ziegler et al., 2005) . We employ a 4-layer feed-forward neural network and optimize its parameters with Adam. We evaluate the accuracy of the model with mean average precision.

7. YooChoose (YC): session-based recommendation with the YooChoose RecSys15 challenge data set2 . We employ a gated recurrent unit (GRU) model and optimize its parameters with Adagrad. We evaluate the accuracy of the model with the reciprocal rank.

4.3. ALTERNATIVE APPROACHES:

To compare the performance of BE with the state-of-the-art, we consider 4 different embedding alternatives. We base our evaluation on performance, measured at a given input/output compression ratio. It is important to note that, in general, besides performance, alternative approaches do not present some of the other desired qualities (Sec. 1) that BE offers, such as on-the-fly operation, constant-time, no supervision, or no network/configuration changes.

1. Hashing trick (HT). We first consider the popular hashing trick for classifier inputs (Langford et al., 2007; Weinberger et al., 2009) . In general, these methodologies only focus on inputs and are not designed to deal with any type of output. Nonetheless, in the case of binary outputs, variants like the one used by Ganchev & Dredze (2008) can be adapted to map to the original items using Eqs. 2 or 3. In fact, considering this adaptation for recovery, the approach can be seen as a special case of BE with k = 1.

2.. Error-correcting output codes (ECOC).:

Originally designed for single-class targets (Dietterich & Bakiri, 1995) , ECOC can be applied to class sets (inputs and outputs), with its corresponding encoding and decoding strategies (Armano et al., 2012 ). Yet, in the case of training neural networks, it is not clear which loss function should be used. The obvious choice would be to use the Hamming distance. However, in pre-analysis, a Hamming loss turned out to be significantly inferior than cross-entropy. Therefore, we use the latter in our experiments. We construct the ECOC matrix with the randomized hill-climbing method of Dietterich & Bakiri (1995) . is based on the SVD of a PMI matrix computed from counting pairwise co-occurrences. It uses cosine similarity as the loss function and, at prediction time, it performs KNN (again using cosine similarity) with the projection of individual labels to obtain a ranking. 4. Canonical correlation analysis (CCA). CCA is a common way to learn a joint dense, realvalued embedding for both inputs and outputs at the same time (Hotelling, 1936) . CCA can be computed using SVD on a correlation matrix (Hsu et al., 2012) and, similarly to PMI, we can use the KNN trick to rank elements or labels at prediction time. Correlation is now the metric of choice, both for the loss function and for determining the neighbors.

3.. Pairwise mutual information (PMI:



5. RESULTS:

We start by reporting on the performance of BE. First of all, we focus on performance as a function of the embedding dimension. As mentioned, to facilitate comparisons, we report in relative terms, using score ratios S i /S 0 and dimensionality ratios m/d. When plotting the former as a function of the latter, we see several things that are worth noting (Fig. 1 ). Firstly, we observe that, for most of the tasks, score ratios approach 1 as m approaches d. This indicates that the introduction of BE does not degrade the original score of the Baseline when the embedding dimension m is comparable to the original dimension d. Secondly, we observe that the lower the dimensionality ratio, the lower the score ratio. This is to be expected, as one cannot embed sets of elements with their intrinsic dimensionality to an infinitesimally small m. Importantly, the reduction of S i /S 0 should not be linear with m/d, but should maximize S i for low m (thus getting curves close to the top left corner of Fig. 1 ). We see that BE fulfills this requirement. In general, we can reduce the size of inputs and outputs 5 times (m/d = 0.2) and still maintain more than 92% of the value of the original score. The ML task is the only exception, which we think is due to the abnormally high density of the data (Table 1 ), inhibiting the embedding to low dimensions3 . CADE is the task for which BE achieves the highest S i for low m. Presumably, the CADE task is the easiest one we consider, as only input embeddings are required.

An additional observation is worth noting (Fig. 1 ). Interestingly, we find that BE can improve the scores over the Baseline for a number of tasks. That is the case for 3 out of the 7 considered tasks: MSD with m/d ≥ 0.3, AMZ with m/d ≥ 0.2, and BC with 0.3 ≤ m/d ≤ 0.6. The fact that an embedding performs better than the original Baseline has been also observed in some other methods for specific data sets (Weston et al., 2002; Langford et al., 2007; Chollet, 2016) . For instance, Chollet (2016) has reported increases up to 7% using the PMI approach on the so-called JFT data set. Here, depending on the task and the embedding dimension, relative increases go from 1 to 12%. Given that the data sets where we observe these increases are some of the less dense ones (Table 1 ), we hypothesize that, in the case of BE, such increases come from having k times more active elements in the ground truth output (recall that one output element is projected k times using k independent hash functions, Sec. 3.2). With k more times elements set to 1 in the output, a better estimation of the gradient may be computed (larger errors that propagate back to the rest of the network).

We now focus on performance as a function of the number of projections k, reporting score ratios S i /S 0 as above (Fig. 2 ). From repeating the plots for different values of m/d, we observe that S i /S 0 is always low for k = 1 (Fig. 2 , left), except when m approaches d, where we have an almost flat behavior (Fig. 2 , right). In general, S i /S 0 jumps up for k ≥ 2 and remains stable until k ≈ 10, where the decrease of S i /S 0 becomes more apparent (Fig. 2 , left). The best operating range typically corresponds to 2 ≤ k ≤ 4. The ML task is again an exception, with a best operating range around 7 ≤ k ≤ 10.

Besides performance scores, it is interesting to assess whether the reduction of input and output dimensions has an effect to training and evaluation times. To this end, we plot the time ratios T i /T 0 as a function of the dimensionality ratio m/d (Fig. 3 ). Regarding training times, we basically observe a linear decrease with m/d (Fig. 3 , left). ML is an exception to the trend, and CADE and AMZ experiment almost no decrease for very low dimensionality ratios m/d < 0.2. In general, we confirm faster training times thanks to the reduction of the number of parameters of the model, dominated by input/output matrices (output dimension also affecting the time to compute the loss function). We obtain a 2 times speedup for a 2 times input/output compression and, roughly, a little bit over 3 times speedup for a 5 times input/output compression. Regarding evaluation times, we also observe a linear trend (Fig. 3 , right). However, this time, T i /T 0 is not as low, with values slightly above 1 but always below 1.5 (with the exception of CADE for m/d > 0.6). Overall, this indicates that, compared to the Baseline evaluation time, the mapping used by BE when reconstructing the output does not introduce an overwhelming amount of extra computation time. With the exception of ML, extra computation time is below 20% for m/d < 0.5.

Finally, we compare the performance of BE to the one of the considered alternative methods. We do so by establishing a dimensionality ratio m/d and computing the corresponding score ratio S i /S 0 for a given task (Table 3 ). We see that BE is better than the alternative methods in 5 out of the 7 tasks (10 out of the 14 considered test points). PMI is better in one of the tasks (CADE) and CCA is better also in one of the tasks (AMZ). It is relevant to note that, when BE wins, it always does so by a relatively large margin (see, for instance, the ML or YC tasks). Otherwise, when an alternative approach wins, generally it does so by a smaller margin (see, for instance, the AMZ task). These results become more relevant if we realize that PMI and CCA are both SVD-based approaches, introducing a separate degree of supervised learning to the task by exploiting pairwise element co-occurrences and correlations, respectively (Sec. 4.3). In contrast, BE does not require any learning. We formulate a co-occurrence-based version of BE in Appendix B, which achieves moderate performance increments over BE and more closely approaches the performance of PMI and CCA on the two tasks where BE was not already performing best. To conclude, a further interesting thing to note is that we confirm the small variation in the score ratios obtained for 2 ≤ k ≤ 10 (Fig. 2 ). Here, score ratios for 3 ≤ k ≤ 5 are often comparable in a statistical significance sense (Table 3 ).

6. CONCLUSION:

We have proposed the use of Bloom embeddings to represent sparse high-dimensional binary-coded inputs and outputs. We have shown that a compact representation can be obtained without compromising the performance of the original neural network model or, in some cases, even increasing it by a substantial factor. Due to the compact representation, the loss function and the input and output layers deal with less parameters, which results in faster training times. The approach compares favorably with respect to the considered alternatives, and offers a number of further advantages such as on-the-fly operation or zero space requirements, all this without introducing changes to the core network architecture, task configuration, or loss function.

In the future, besides continuing to exploit co-occurrences (Appendix B), one could extend the proposed approach by considering further extensions of Bloom filters such as counting Bloom filters (Bonomi et al., 2006) . In theory, those extensions could provide a more compact representation by breaking the binary nature of the embedding. However, they could require the modification of the loss function or the mapping process (Eqs. 2 and 3). A faster mapping process using the sorted probabilities of v could also be studied.

A.3 CADE WEB DIRECTORY (CADE):

We perform single-label text categorization using web pages classified by human experts from the CADE web directory of Brazilian web pages5 (Cardoso-Cachopo, 2007) . The data set contains around 40,000 documents assigned to one of 12 categories such as services, education, health, or culture. We use the train and test splits provided by Cardoso-Cachopo (2007) , further splitting the train set randomly to obtain a validation set from it. Validation and test splits comprise 5,000 and 13,661 documents, respectively. The size of the vocabulary is close to 200,000 words with a median number of 17 words per document (Table 1 ).

To perform classification we use a 4-layer feed-forward neural network with a softmax output. The number of units is, from input to output, 400, 200, 100, and 12, and we use rectified linear units as activations for the hidden layers. We train the network for 10 epochs, using batches of 32 instances and RMSprop (Tieleman & Hinton, 2012) with a learning rate of 0.0002 and exponential decay of 0.9. As for the rest, we proceed as with the ML task. We obtain a baseline accuracy of S 0 = 58.0 %, slightly superior than the best baseline reported by Cardoso-Cachopo (2007) , and a random accuracy of S R = 8.5 % (Table 2 ). Notice that this is the only data set that does not have a sparse instance or user profile as output.

A.4 MILLION SONG DATA SET (MSD)

The next task we consider is song recommendation with the million song data set (Bertin-Mahieux et al., 2011) . We take the Echo Nest taste profile subset6 , which includes over 48 million play counts of around 384,000 songs for roughly 1 million users. We assume that a user likes a song when this has listened to it a minimum of 3 times. We then remove the songs that appear less than 20 times and build user profiles with a minimum of 5 songs. We split the data set as with the ML task, keeping 50,000 user profiles for validation and another 50,000 for testing. The MSD data set has a median of 5 songs in input/output profiles (Table 1 ).

To recommend future listens to the user we use a 3-layer feed-forward neural network with a softmax output and 300 rectified linear units in the hidden layers. We fit the model for 10 epochs with batches of 64 instances. As for the rest, we proceed as with the ML task. We obtain a baseline mean average precision of S 0 = 0.066 and a random score of S R below 0.001.

A.5 AMAZON BOOK REVIEWS (AMZ):

We also consider book recommendations with the Amazon book reviews data set 7 (McAuley et al., 2015). The data set originally contains 22 million ratings of over 2 million books by approximately 3 million users. We proceed as with the ML data set, but this time setting the minimum number of ratings per book to 100 and splitting the data with 50,000 instances for validation and another 50,000 instances for testing.

We here use a 4-layer feed-forward neural network with a softmax output and 300 rectified linear units in the hidden layers. We fit the model for 10 epochs with batches of 64 instances and, as for the rest, we proceed as with the ML task. We obtain a baseline mean average precision of S 0 = 0.049 and a random score of S R below 0.001.

A.6 BOOK CROSSING (BC):

Continuing with book recommendations, we consider the book crossing data set 8 (Ziegler et al., 2005). It contains 278,000 users providing over 1 million ratings about a little more than 271,000 books. We remove books with less than 2 ratings, discretize those by a threshold of 4, and proceed as with the ML data set, but keeping 2,500 users for validation and another 2,500 for testing. The BC data set is known to be a very sparse data set, specially after removing users with less than 2 book reviews (Table 1 ).

To perform recommendations we use the same architecture and configuration as with the MSD task, but this time we use 250 units in the hidden layers. We obtain a baseline mean average precision of S 0 = 0.010 and a random score of S R below 0.001.

A.7 YOOCHOOSE (YC):

We finally study session-based recommendations using the YooChoose RecSys15 challenge9 data.

Here, the task is to predict the next click given a sequence of click events for a given session in an e-commerce site (Hidasi et al., 2016) . We work with the training set of the challenge and keep only the click events. We take the first 2 million sessions of the data set which have a minimum of 2 clicks, and keep apart 50,000 for validation and another 50,000 for testing. We form sequences of, at most, 13 clicks to the 35,000 possible links (Table 1 ). Note that this is a sequential data set with one-hot encoded instances of only one event each.

To predict the next click we proceed as in Hidasi et al. (2016) and consider a GRU model (Cho et al., 2014) . We set the inner dimensionality to 100 and train the network with Adagrad (Duchi et al., 2011) , using a learning rate of 0.01. We use batches of 64 instances and train the model for 10 epochs. As for the rest, we proceed as with the ML task. As with PTB, we evaluate the result using the reciprocal rank of the correct prediction. We achieve a performance of S 0 = 0.368, which can be assumed to be as good as state-of-the-art models on this data (Hidasi et al., 2016) . Predicting clicks at random yields a score S R below 0.001.

APPENDIX B GOING ONE STEP FURTHER WITH CO:

-OCCURRENCE-BASED COLLISIONS B.1 CO-OCCURRENCE-BASED BLOOM EMBEDDING (CBE)

In Bloom filters and BE, collisions are unavoidable due to the lower embedding dimensionality and the use of multiple projections (Sec. 3). In addition we have seen that alternative approaches produce embeddings by exploiting co-occurrence information (Secs. 2 and 4.3). Here, we study a variant of BE that takes advantage of co-occurrence information to adjust the collisions that will inevitably take place when performing the embedding. We denote this approach by co-occurrencebased Bloom embedding (CBE).

What we propose is a quite straightforward approach to CBE, which does not add much extra precomputation time. Training and testing times remain the same, as CBE uses a pre-computed hashing matrix H (Sec. 3.2). The general idea of the proposed approach is to 're-direct' the collisions of the co-occurring elements to the same bits or positions of u. Our implementation of this idea is detailed in Algorithm 1, and briefly explained below.

Algorithm 1 Pseudocode for CBE.

Input: Input and/or output instances X (n × d sparse binary matrix), embedding dimensionality m, number of projections k, and pre-computed hashing matrix H (d × k integers matrix). Output: Co-occurrence-based hashing matrix H .

1: C ← X T X 2: C ← C SGN(C-AVGFREQ(X)) 3: c VAL , c ROW , c COL ← COORD(LOWTRI(C)) 4: for i in ARGSORT(c VAL ) 5: a, b ← c ROW i , c COL i 6: r ← URND(1, m, h a ∪ h b ) 7: j a ← URND(1, k, ∅) 8: j b ← URND(1, k, ∅) 9:

h a,ja , h b,j b ← r 10: return H Table 4 : Co-occurrence statistics and average score increase of CBE over BE. From left to right: data set name, input percent of co-occurrent pairs, input average co-occurrence ratio of co-occurrent pairs, output percent of co-occurrent pairs, output average co-occurrence ratio of co-occurrent pairs, and average score increases of CBE over BE (%, calculated using 100(S j -S i )/S 0 and averaging over all m/d points). Co-occurrence values for PTB and YC inputs correspond to considering training sequences, not isolated sequence elements.

Data set:

Co-occurrence statistics Score increase (%)

Input (%) Input (ρ) Output (%) Ouput (ρ) k = 3 k = 4 ML 25.2 1.3 • 10 -4 32.9 1.0 • 10 -4 +0.9 +1.7 PTB 3.3 2.4 • 10 -5 0 0 +0.1 +0.9 CADE 1.3 8.8 • 10 -5 N/A N/A -0.4 -0.1 MSD 1.3 3.0 • 10 -6 1.3 3.1 • 10 -6 +0.5 +1.5 AMZ 3.0 1.8 • 10 -6 3.0 1.8 • 10 -6 +6.6 +8.4 BC 0.8 4.9 • 10 -5 0.4 4.9 • 10 -5 -3.4 -1.0 YC 0.2 1.5 • 10 -6 0 0 +0.4 +0.3

First, we count pairwise co-occurrences and store them in a sparse matrix C (line 1). Next, we threshold C by the average element frequency in X using the Hadamard product and a componentwise sign function (line 2). We then get the lower triangular part of C and return it in coordinates format, that is, using a tuple of values, row indices, and column indices (line 3). We will use the order in c VAL to update the hash matrix H. To do so, we first loop over the indices of the sorted values of c VAL in increasing order (line 4). After selecting the corresponding elements a and b (line 5), we then draw integers from URND (lines 6-8). The function URND(x, y, z) is a uniform random integer generator between x and y (both included) such that the output integer is not included in the set z, that is, URND(x, y, z) ∈ z. Rows a and b of H are transformed to sets h a and h b and its union is computed (line 6). Finally, we use the integers generated by URND to pick projections j a and j b from H, and assign them the same bit r (line 9). By updating the projections in H in increasing order of co-occurrence (line 4), we give priority to the pairs with largest co-occurrence, setting them to collide to the same bit r (line 9).

B.2 CBE RESULTS:

Overall, the performance of CBE only provides moderate increments over the original BE approach (Fig. 4 ). With the exception of the BC task, the performance of CBE is always higher than the one of BE. However, with the exception of the AMZ task, we do not observe dramatic increases of CBE over BE. On average, such increases are between 0.4% and 8.4% (Table 4 , right). One possible explanation for these moderate performance increases is the low co-occurrence in the considered data (Table 4, left) . As it can be seen, typically less than 3% of all possible pairs show a cooccurrence. Moreover, the average co-occurrence count of such co-occurring pairs is very low, with ratios ρ to the total number of instances n in the order of 10 -5 or 10 -6 .

Despite being moderate on average, we observed that the increments provided by CBE were more prominent for low dimensionality ratios m/d. By relating CBE with the best approaches resulting from the comparison of BE with the alternatives, we see that CBE is generally better than BE, sometimes with a statistically significant difference (Table 5 ). Furthermore, we see that CBE, being based on co-occurrences, more closely approaches PMI and CCA in the tasks where those were performing best, and even outperforms them in one test point (AMZ, m/d = 0.2; compare also with Table 3 ). Being closer to those co-occurrence-based approaches is an indication that CBE leverages co-occurrence information to some extent. 

:

An example can be found in the neural network model ofHidasi et al. (2016), which uses a gated recurrent unit to perform session-based recommendations with input/output layers of dimensionality 330,000 and internal layers of dimensionality 100.

http://recsys.yoochoose.net

Note that the ML data is essentially collected through a survey-type method(Harper & Konstan, 2015).

http://grouplens.org/datasets/movielens/20m/

http://ana.cachopo.org/datasets-for-single-label-text-categorization

http://labrosa.ee.columbia.edu/millionsong/tasteprofile

http://jmcauley.ucsd.edu/data/amazon/

http://www2.informatik.uni-freiburg.de/ ˜cziegler/BX/

http://recsys.yoochoose.net/challenge.html

Figures and Tables:

Figure 1: Score ratios S i /S 0 as a function of dimensionality ratio m/d using k = 4. Qualitatively similar plots are observed for other values of k.

Figure 2: Score ratios S i /S 0 as a function of the number of hash functions k: using m/d = 0.3 (left) and m/d = 1 (right).

Figure 3: Time ratios T i /T 0 as a function of dimensionality ratios m/d with k = 4: training time (left) and evaluation time (right). Qualitatively similar plots are observed for other values of k. Bl. denotes baseline.

Figure 4: Comparison of score ratios S i /S 0 as a function of dimensionality ratio m/d for BE (dashed lines) and CBE (solid lines) using k = 4. Qualitatively similar plots are observed for other values of k.

Data set statistics after data cleaning and splitting. From left to right: data set name, type of modeled interaction, number of instances n, test split size, instance dimensionality d, median number of non-zero components c, and median density c/d.

Table content: <table><tr><td>Data set</td><td>Interaction</td><td>n</td><td>Split</td><td>d</td><td>c</td><td>c/d</td></tr><tr><td>ML</td><td>User-Movies</td><td>138,224</td><td>10,000</td><td>15,405</td><td>18</td><td>1.2 • 10 -3</td></tr><tr><td>PTB</td><td>Sequence-Words</td><td>929,589</td><td>82,430</td><td>10,001</td><td>1</td><td>1.0 • 10 -4</td></tr><tr><td>CADE</td><td>Words-Category</td><td>40,983</td><td>13,661</td><td>193,998</td><td>17</td><td>8.8 • 10 -5</td></tr><tr><td>MSD</td><td>User-Songs</td><td>597,155</td><td>50,000</td><td>69,989</td><td>5</td><td>7.1 • 10 -5</td></tr><tr><td>AMZ</td><td>User-Books</td><td>916,484</td><td>50,000</td><td>22,561</td><td>1</td><td>4.4 • 10 -5</td></tr><tr><td>BC</td><td>User-Books</td><td>25,816</td><td>2,500</td><td>54,069</td><td>2</td><td>3.7 • 10 -5</td></tr><tr><td>YC</td><td>Session-Clicks</td><td>1,865,997</td><td>50,000</td><td>35,732</td><td>1</td><td>2.8 • 10 -5</td></tr></table>

Experimental setup and baseline scores. From left to right: data set name, network architecture and optimizer, evaluation measure name, random score S R , and baseline score S 0 .

Table content: <table><tr><td>Data set</td><td>Architecture + Optimizer</td><td>Evaluation measure</td><td>S R</td><td>S 0</td></tr><tr><td>ML</td><td>Feed-forward + Adam</td><td>Mean average precision</td><td>0.003</td><td>0.160</td></tr><tr><td>PTB</td><td>LSTM + SGD</td><td>Reciprocal rank</td><td>0.001</td><td>0.342</td></tr><tr><td>CADE</td><td>Feed-forward + RMSprop</td><td>Accuracy (%)</td><td>8.5</td><td>58.0</td></tr><tr><td>MSD</td><td>Feed-forward + Adam</td><td>Mean average precision</td><td>&lt;0.001</td><td>0.066</td></tr><tr><td>AMZ</td><td>Feed-forward + Adam</td><td>Mean average precision</td><td>&lt;0.001</td><td>0.049</td></tr><tr><td>BC</td><td>Feed-forward + Adam</td><td>Mean average precision</td><td>&lt;0.001</td><td>0.010</td></tr><tr><td>YC</td><td>GRU + Adagrad</td><td>Reciprocal rank</td><td>&lt;0.001</td><td>0.368</td></tr></table>

Comparison of BE with the considered alternatives. Score ratios S i /S 0 for different combinations of data set and compression ratio m/d. Best results are highlighted in bold, up to statistical significance (Mann-Whitney U, p > 0.05).

Table content: <table><tr><td colspan="2">Test point</td><td/><td colspan="2">Alternative methods</td><td/><td/><td>BE</td><td/></tr><tr><td>Data set</td><td>m/d</td><td>HT</td><td>ECOC</td><td>PMI</td><td>CCA</td><td>k = 3</td><td>k = 4</td><td>k = 5</td></tr><tr><td>ML</td><td>0.2</td><td>0.234</td><td>0.342</td><td>0.043</td><td>0.209</td><td>0.750</td><td>0.770</td><td>0.722</td></tr><tr><td>ML</td><td>0.3</td><td>0.285</td><td>0.208</td><td>0.045</td><td>0.200</td><td>0.796</td><td>0.813</td><td>0.815</td></tr><tr><td>PTB</td><td>0.2</td><td>0.357</td><td>0.453</td><td>0.837</td><td>0.638</td><td>0.919</td><td>0.908</td><td>0.881</td></tr><tr><td>PTB</td><td>0.4</td><td>0.528</td><td>0.454</td><td>0.836</td><td>0.695</td><td>0.942</td><td>0.920</td><td>0.902</td></tr><tr><td>CADE</td><td>0.01</td><td>0.857</td><td>0.359</td><td>0.984</td><td>0.928</td><td>0.862</td><td>0.853</td><td>0.855</td></tr><tr><td>CADE</td><td>0.03</td><td>0.914</td><td>0.363</td><td>1.002</td><td>0.950</td><td>0.914</td><td>0.925</td><td>0.926</td></tr><tr><td>MSD</td><td>0.05</td><td>0.078</td><td>0.268</td><td>0.216</td><td>0.679</td><td>0.695</td><td>0.738</td><td>0.738</td></tr><tr><td>MSD</td><td>0.1</td><td>0.151</td><td>0.310</td><td>0.321</td><td>0.740</td><td>0.835</td><td>0.841</td><td>0.832</td></tr><tr><td>AMZ</td><td>0.1</td><td>0.166</td><td>0.182</td><td>0.851</td><td>1.030</td><td>0.864</td><td>0.881</td><td>0.861</td></tr><tr><td>AMZ</td><td>0.2</td><td>0.289</td><td>0.185</td><td>0.995</td><td>1.048</td><td>1.016</td><td>1.029</td><td>1.008</td></tr><tr><td>BC</td><td>0.05</td><td>0.189</td><td>0.817</td><td>0.022</td><td>0.313</td><td>0.777</td><td>0.750</td><td>0.837</td></tr><tr><td>BC</td><td>0.1</td><td>0.199</td><td>0.886</td><td>0.025</td><td>0.465</td><td>0.965</td><td>0.919</td><td>0.831</td></tr><tr><td>YC</td><td>0.03</td><td>0.150</td><td>0.076</td><td>0.776</td><td>0.466</td><td>0.841</td><td>0.858</td><td>0.858</td></tr><tr><td>YC</td><td>0.05</td><td>0.240</td><td>0.083</td><td>0.777</td><td>0.517</td><td>0.919</td><td>0.910</td><td>0.928</td></tr></table>

Comparison of CBE versus the results in Table3. Score ratios S i /S 0 for different combinations of data set and compression ratio m/d. Best results are highlighted in bold, up to statistical significance (Mann-Whitney-U, p > 0.05).

Table content: <table><tr><td colspan="2">Test point</td><td colspan="2">Best so far</td><td>CBE</td><td/></tr><tr><td>Data set</td><td>m/d</td><td>Method</td><td>S i /S 0</td><td>k = 3</td><td>k = 4</td></tr><tr><td>ML</td><td>0.2</td><td>BE</td><td>0.770</td><td>0.760</td><td>0.781</td></tr><tr><td>ML</td><td>0.3</td><td>BE</td><td>0.815</td><td>0.812</td><td>0.867</td></tr><tr><td>PTB</td><td>0.2</td><td>BE</td><td>0.919</td><td>0.915</td><td>0.907</td></tr><tr><td>PTB</td><td>0.4</td><td>BE</td><td>0.942</td><td>0.937</td><td>0.922</td></tr><tr><td>CADE</td><td>0.01</td><td>PMI</td><td>0.984</td><td>0.854</td><td>0.853</td></tr><tr><td>CADE</td><td>0.03</td><td>PMI</td><td>1.002</td><td>0.921</td><td>0.922</td></tr><tr><td>MSD</td><td>0.05</td><td>BE</td><td>0.738</td><td>0.759</td><td>0.756</td></tr><tr><td>MSD</td><td>0.1</td><td>BE</td><td>0.841</td><td>0.856</td><td>0.873</td></tr><tr><td>AMZ</td><td>0.1</td><td>CCA</td><td>1.030</td><td>0.994</td><td>0.991</td></tr><tr><td>AMZ</td><td>0.2</td><td>CCA</td><td>1.048</td><td>1.109</td><td>1.117</td></tr><tr><td>BC</td><td>0.05</td><td>BE</td><td>0.837</td><td>0.774</td><td>0.808</td></tr><tr><td>BC</td><td>0.1</td><td>BE</td><td>0.965</td><td>0.880</td><td>0.878</td></tr><tr><td>YC</td><td>0.03</td><td>BE</td><td>0.858</td><td>0.871</td><td>0.880</td></tr><tr><td>YC</td><td>0.05</td><td>BE</td><td>0.928</td><td>0.933</td><td>0.936</td></tr></table>

Peer review (iclr2017):
The authors propose a simple scheme based on Bloom filters to generate embeddings for inputs and outputs. This reduces memory while introducing limited computational overhead, and it is simple enough to implement that it can easily be added to any practitioner*s toolbox. Pros: - Can be applied to practically any model, either at the input or hte output. - Method is very straightforward: apply multiple hashes, instead of single one. The algorithm for decoding is nice too. Cons: - The paper is a bit difficult to read; the idea is really simple so it doesn*t seem like it warrants such a complex description. - The novelty of the approach is a bit limited since, as other reviewers have mentioned, Bloom filters are in use in a lot of areas including multi-label classification. This seems like it would be a good short paper. There*s a lot of well fleshed out experiments, but the core of the paper is a bit incremental.