A nalogy-Guided Evolutionary Pretraining of Binary Word Embeddings (2022)

Abstract: As we begin to see low-powered computing paradigms (Neuromorphic Computing, Spiking Neural Networks, etc.) becoming more popular, learning binary word embeddings has become increasingly important for supporting NLP applications at the edge. Existing binary word embeddings are mostly derived from pretrained real-valued embeddings through different simple transformations, which often break the semantic consistency and the so-called “arithmetic” properties learned by the original, real-valued embeddings. This paper aims to address this limitation by introducing a new approach to learn binary embeddings from scratch, preserving the semantic relationships between words as well as the arithmetic properties of the embeddings themselves. To achieve this, we propose a novel genetic algorithm to learn the relationships between words from existing word analogy data-sets, carefully making sure that the arithmetic properties of the relationships are preserved. Evaluating our generated 16, 32, and 64-bit binary word embeddings on Mikolov’s word analogy task shows that more than 95% of the time, the best fit for the analogy is ranked in the top 5 most similar words in terms of cosine similarity.

## introduction word embeddings see very common use in many widely-adopted nlp applications, e.g., document summarization @xcite , sentiment analysis @xcite , entity extraction @xcite , question answering @xcite , etc. however, the majority of commonly-used word embeddings are far too demanding in terms of energy and computational resources required to train and load them, making state-of-the-art word embeddings unsuitable for use in a low-energy environment, like in an internet of things (iot) device @xcite @xcite or in a neuromorphic processor @xcite . as we observe these low-powered devices entering the mainstream, we become increasingly aware of our inability to use typical word embeddings in those environments, since typical word embeddings usually require multiple gigabytes for storage and hundreds (if not thousands) of floating-point multiplications to capture meaningful relationships between words. furthermore, lowenergy neuromorphic computers in particular are based on binary "spiking" inputs and perform calculations using "accumulation" (sum) operations, therefore not supporting floating-point operations @xcite . hence, real-valued embeddings are of little use to these low-energy computing paradigms, which is our main motivation for learning high-quality binary embeddings. an intuitive way to address this issue is to take the pretrained real-valued word embeddings and directly binarize them so they can be easily used as a spike train for input to a neuromorphic processor. the potential benefits of this approach are astronomical, as the vector's size can be reduced by more than 95% and the number of operations needed goes down significantly @xcite . as an example, calculating the similarity between two words goes from requiring o(n) floating-point operations to 2 binary operations: an xnor and a bit-count operation. however, one of the primary issues to address when binarizing word embeddings is making sure that this oversimplification in word representation does not cause a significant drop in semantic and syntactic accuracy of the learned embeddings. in other words, binary embeddings still need to encode semantic and syntactic information properly so that meaningful relations can be captured when these embeddings are used. the simplest approach for creating binary embeddings is to quantize the real-valued embedding vectors into binary labels based on some thresh-olds @xcite . while the thresholding approach is simple, it often breaks the semantic relationships learned by the real-valued vectors, as an infinite range of real-valued numbers are forced to map into one/zero labels without considering the loss in semantic consistency during the process. another approach is to learn an auto-encoder which can transform a real-valued embedding vector into a binary vector while minimizing the loss in semantic consistency during the process @xcite . however, this process still assumes that high-quality, real-valued embeddings are already available, and their experimental results show that the binary embeddings learned this way fail to achieve comparable performance against realvalued embeddings in both semantic and syntactic analogy tasks @xcite . to address these limitations, we propose to learn binary embeddings from scratch, which will guarantee the preservation of the semantic and syntactic relationships between words even in the restricted binary latent space. our primary motivation for proposing this method is to take a step forward towards enabling nlp in the emerging low-power neuromorphic computing paradigm. we envision using this binary embedding as an encoded input to spiking neural networks (snns), providing a compact spike-representation for words to be processed in downstream nlp tasks. furthermore, since snns currently have difficulty learning with methods supported by backpropagation @xcite , we opt to utilize a method that has no need for it, i.e., a genetic algorithm @xcite . genetic algorithms are a class of methods for solving both constrained and unconstrained optimization problems based on the concept of "survival of the fittest" @xcite , and naturally they fit binary representations intuitively because of the crossover and mutation operators associated with them @xcite . however, one common criticism of genetic algorithms is their slow convergence @xcite . we propose to address this limitation by designing an objective function which is guided by high quality analogy examples to facilitate faster convergence. to be more specific, in a typical embedding training process, the final encoding is learned by observing word co-occurrences @xcite , which is often very noisy. in contrast, our proposed method learns this encoding using a data-set of high-quality targeted analogies, allowing for a more focused un-derstanding of the relationships between words in a curated vocabulary and a faster convergence while training. this becomes especially useful for iot applications, where a full vocabulary may not be necessary as opposed to a smaller collection of relevant words. another major benefit of the proposed approach is that it can learn the goal "binary" embeddings without worrying about the hassles of implementing backpropagation in spiking neural networks. experiments with the evolved 16-, 32-, and 64bit binary word embeddings on the word analogy task @xcite show that more than 95% of the time, the best fit for the analogy is ranked among the top 5 most similar words in the vocabulary. this demonstrates that the proposed technique is effective as well as useful. the rest of the paper is organized as follows: section 2 presents the related works. next, section 3 provides some basic background on genetic algorithms and evolutionary operators. section 4 presents the details of the proposed evolutionary training process followed by our experimental setup (section 5) and experimental results (section 6). finally, we conclude the paper in section 7. n-gram and sentence embeddings: beyond word embeddings, researchers have proposed methods that encode larger language constructs, such as n-grams @xcite or sentences @xcite , but those are also beyond the scope of this paper as we focus exclusively on word embeddings. ## background on genetic algorithm genetic algorithms are a family of computational models inspired by evolution @xcite . these algorithms encode a potential solution to a specific problem through a simple chromosomelike data structure and apply recombination operators to these structures so as to preserve critical information. genetic algorithms are often viewed as function approximators, although the range of problems to which evolutionary algorithms have been applied is quite broad @xcite . an implementation of a genetic algorithm begins with a population of (typically random) chromosomes. one then evaluates these structures and allocates reproductive opportunities in such a way that those chromosomes which represent a better solution to the target problem are given more chances to reproduce than the chromosomes which are poorer solutions. the "goodness" of a solution is typically defined w.r.t. the current population. ## evolutionary pretraining of binary word embeddings in this section, we describe the details of the evolutionary pretraining process to learn binary word embeddings from scratch which is guided by a collection of word analogy examples. ## conclusion as low-energy computing paradigms like spiking neural networks (snns) become increasingly popular for nlp applications, learning accurate binary word embeddings also becomes very important as snns can only process binary/spike inputs. at the same time, as backpropagation is tricky in snns and simple quantization-based binarization techniques fail to achieve reasonable accuracy, an alternative approach that can learn high-quality binary embeddings has become a pressing need. in this paper, we introduced a new evolutionary approach to learn binary embeddings from scratch, preserving both the semantic/syntactic relationships between words and the arithmetic properties of the embeddings themselves; while bypassing the difficulties associated with implementing backpropagation in snns. experimental results show that the proposed learning technique is both feasible and promising.