The C hinese Remainder Theorem for Compact, Task-Precise, Efficient and Secure Word Embeddings (2021)

Abstract: The growing availability of powerful mobile devices and other edge devices, together with increasing regulatory and security concerns about the exchange of personal information across networks of these devices has challenged the Computational Linguistics community to develop methods that are at once fast, space-efficient, accurate and amenable to secure encoding schemes such as homomorphic encryption. Inspired by recent work that restricts floating point precision to speed up neural network training in hardware-based SIMD, we have developed a method for compressing word vector embeddings into integers using the Chinese Reminder Theorem that speeds up addition by up to 48.27% and at the same time compresses GloVe word embedding libraries by up to 25.86%. We explore the practicality of this simple approach by investigating the trade-off between precision and performance in two NLP tasks: compositional semantic relatedness and opinion target sentiment classification. We find that in both tasks, lowering floating point number precision results in negligible changes to performance.

## introduction in recent years, nlp models, particularly language models, have come under increasing scrutiny for their potential privacy leaks (e.g., @xcite ). one answer has been to push nlp models onto edge devices, such as mobile phones and browsers, for on-device inference using differentially private federated learning (e.g., @xcite ). edge computing, in turn, requires smaller and faster models, such as distill-bert @xcite or mobilebert @xcite , which theoretically improves the viability of using bert embeddings on these @xcite what has yet to take place, however, is careful numerical analysis of word embeddings at varying precisions for different nlp tasks. numerical analysis can inform potential alternatives to defining the representations of word embeddings themselves. we must carefully orchestrate a balance among the size of these representations, their security, the algebra of operations that they enable, and, because many edge devices are resourcerestricted relative to the gpu clusters that we do research on, the efficiency and power consumption of those operations. in particular, feature/basic phones are growing in popularity in developing nations 12 , often with the possibility of expanding their memory to about 16gb with a microsd. many privacy-enabled language models, in particular, are simply out of reach for these low-resource devices. no work to date has proposed using the chinese remainder theorem (crt) to create softwarebased compressed word embeddings, adapted to single instruction multiple data (simd). we propose here a crt-based method which speeds up addition by up to 48.27% and compresses glove @xcite word embedding libraries by up to 25.86% (up to 68.68% of the original full-precision library), depending on the precision selected. we also explore different levels of numerical precisions for a representative task, as well as more abstractly by analysing the absolute error resulting from adding and multiplying truncated and rounded values. ## algorithm: vec2int first, we must determine a minimum floating point precision (φ) the values within our word embeddings must have. since the crt only works with positive integers (and polynomials), we will multiply each value in the word embeddings (a i ) by 10 φ and truncate (or round) the result, then add the lowest possible integer value that can be found within our word embeddings (s). before running the crt algorithm, we must pre-compute a vector m of moduli, each of which are coprime and strictly greater than any possible value of a i . a and m can then be input into the crt algorithm in order to produce an integer x. since we know the values of m, we can easily perform a "reverse crt" by calculating a i ← x (mod m i ). when two crt-encoded vectors (say x 1 and x 2 ) are added together, their sum at index i can still be decoded by calculating (x 1 + x 2 ) (mod in other words, this representation supports vector addition, multiplication and, in a more restricted range, subtraction, through executing those operations directly on integers. addition and multiplication are fundamental to most compositional semantics approaches, beginning with @xcite . addition is also central to measuring the relationship between word pairs, particularly when using the l1-norm as a metric, which is less sensitive to outliers than the l2-norm @xcite . word analogy is an example of such a task. of course, the these operations can also be applied to measuring the relationship between sentence pairs and document pairs. ## reasoning about precision using numerical analysis one might assume that we have to perform extensive empirical analysis to determine the minimum floating point precision necessary for the inputs of a particular nlp algorithm. however, there are generalizations we can make based on concepts as simple as the absolute error and relative error of components of the operations, described in heath (2018) as: absolute @xmath0. valuetrue value (1) for our operations, the vectors truncated or rounded at precision φ within a dataset |d φ | are denoted v φi , while the vectors of the original dataset are denoted v i . if we want to refer to index k of vector v i , we write it as v i [k], where |v 1 | is the size of the embeddings we are working with. the average absolute error between the vectors of the two datasets of size |d| is computed as follows: we calculate the average absolute error of addition as follows: recall also the findings of @xcite , who did not observe a significant decrease in performance when using an 8-bit fixed-point value for word embeddings in word and phrase similarity and dependency parsing tasks. this implies that there is some room for compromise on precision practical nlp tasks as well. ## discussion and future work these preliminary results suggest that the vec2int algorithm would be an efficient way of encoding word vectors for specific nlp tasks, namely those which would benefit from arithmetic-supporting vector compression (which tar and zip are not). they also suggest that analysis of average relative and absolute error can be used to tune these representations. we have yet to test the effectiveness of using integer representations of word2vec @xcite and bert @xcite , but expect the outcomes to be similar to the results for term context vectors, fasttext, and glove. it would also be particularly interesting to see what kind of performance improvements can be obtained by applying the crt to sentence-as well as document-level embeddings. relevant to privacy concerns, some constraints on homomorphic encryption schemes include limiting the number of possible multiplications and also limiting the precision of the values being computed upon. the same sort of numerical precision analysis and computational limitations that we have done in this paper can inform how we as nlp scientists think of how our methods are integrable into certain privacy technology. average relative and absolute error might be useful for creating better encrypted nlp algorithms using homomorphic encryption, since many homomorphic encryption schemes tend to require integer inputs or limited-precision inputs.