Grouping Words with Semantic Diversity (2021)

Abstract: Deep Learning-based NLP systems can be sensitive to unseen tokens and hard to learn with high-dimensional inputs, which critically hinder learning generalization. We introduce an approach by grouping input words based on their semantic diversity to simplify input language representation with low ambiguity. Since the semantically diverse words reside in different contexts, we are able to substitute words with their groups and still distinguish word meanings relying on their contexts. We design several algorithms that compute diverse groupings based on random sampling, geometric distances, and entropy maximization, and we prove formal guarantees for the entropy-based algorithms. Experimental results show that our methods generalize NLP models and demonstrate enhanced accuracy on POS tagging and LM tasks and significant improvements on medium-scale machine translation tasks, up to +6.5 BLEU points. Our source code is available at https://github.com/abdulrafae/dg .

## introduction natural language understanding has seen remarkable success with the rise of deep learning. however, human languages' variety and richness result in high-dimensional inputs to nlp models, increasing learning complexity and error rates. first, openvocabulary inputs inevitably bring rare and outof-vocabulary words (oovs). second, network complexity increases with input dimension, specifically the "curse of dimensionality" makes learning difficult on medium and small datasets. this paper addresses these limitations by introducing new grouping methods to compute alternative language representations that simplify textual inputs. we currently have alternative language representations, such as pinyin, metaphone, logogram, and emoji, that exist in natural languages and that have been shown to improve various nlp applications @xcite @xcite . while these representations can help, they are not developed for nlp performance. our goal is to design algorithms for computing new language representations specifically to enhance nlp performance in this work. we ask: an intuitive approach to answering this question is to group similar words in training and test sets and replace each word with its group. a word grouping viewed as a many-to-one mapping function can significantly reduce the vocabulary size that lowers the input feature dimensions leading to a generalized nlp model learning. for example, let us take two sentences: (a) "you ask me."; (b) "she tells me." there are five words "ask", "she", "tells", "me", and "you" in the vocabulary. grouping words into "a" and "b" will reduce the vocabulary size to two, resulting in a simplified language representation. we can apply conventional word clustering to group words after embedding words into a vector space and measuring their distances with cosine similarity. however, clustering can map different sentences to the same sequence of groups, making them indistinguishable. in our example, we cluster similar pronouns "you", "she" and "me" into one group indicated by "a", and verbs "ask", "tells" by "b". then both sentences are rewritten as "a b a." the distinct meanings of the two original sentences are lost. however, if we group diverse semantic words, namely, "you", "tell" as "a"; "she", "me", "ask" as "b", then we maintain two samples of (a) "a b b." and (b) "b a b." so, the distinct meanings of the two sentences are retained. this example illustrates the need to group words so that each sentence is uniquely represented. now, to generalize this idea, "how can we design an algorithm that simplifies language representation while preserving meaning expressiveness? " our key observation is that the context of semantically diverse words varies more than that of semantically close words. in our approach, we measure semantic similarity using the cosine of word embeddings, learned based on context, see @xcite @xcite . thus, similar contexts indicate semantic similarity and vice versa. in this way, our diverse grouping uses context to distinguish words from the same group, leading to a more expressive representation. in this paper, we introduce five novel algorithms in three types that group semantically diverse words together. we develop novel theoretical methods for diverse grouping and port them in our nlp context. we begin by considering random sampling grouping. next, we develop a grouping algorithm based on geometric distances by designing an algorithm that computes a partition of a set of points in some metric space to maximize the sum of intra-group distances. this approach is essentially the opposite of the objectives used in clustering problems, such as k-means @xcite and k-medians @xcite , where one seeks to minimize a monotonic function of intra-group distances. finally, we present a grouping algorithm to maximize diversity by maximizing the unigram entropy of the representation. we show that the unigram entropy algorithm is c-1 4c+4εc -approximations of the optimal solutions of maximizing the entropy of the new representation, where c is the number of groups, and ε is a small positive real number. this bound means that in the worst case, our algorithm is about 1/4 away from the optimal, while in typical cases, it could be very close to the optimal. importantly, our theoretical results' outcomes show their usefulness in nlp tasks after we appropriately adjust them. in our experiments, each of the above methods significantly enhances the nmt accuracy by up to 6.5 bleu points (36.9% relatively). our contribution can be summarized as follows: ## related work while typical word clustering @xcite @xcite (or word class @xcite ) methods collect similar words together, while our method groups semantically diverse words together. however, unlike the common use of clustering to smooth unseen words, our goal is to deduce the input sentence's dimension by grouping diverse words so that a word-group sequence uniquely represents a word sequence. our diverse grouping approach is also close to the sparse representation @xcite , which makes the network parameter matrices sparse without changing its dimension. our methods reduce the neural network (nn) input dimension. such a dimension reduction can be seen as a kind of regularization on nns. there have been many types of nn regularization methods. @xcite adds a parameter norm penalty to the objective function, @xcite adds constrained optimization, and many works exploit the sub-structure of network models, such as dropout, early stopping, and weight decay. those approaches are very popular but may limit the capacity of models, while our methods benefit from indomain linguistic knowledge. work such as @xcite adds augmented data (e.g., noisy data, pseudo data, etc.) but is a domain-dependent approach that inventively increases the training time. our work is perpendicular to the successful research in word embedding, whereby a word is mapped one-one onto a real number vector trying to preserve word pair distances. in contrast, our methods map many words into one group in a discrete space. also, our systems build on bpe, but we do not decompose and recombine words. therefore, our methods are additive to any improved word embedding @xcite , or bpe @xcite versions. different from the inspiring work that uses soundex, nysiis, metaphone, logogram @xcite , pinyin @xcite , skip-ngram @xcite , and huffman coding @xcite ; khan algorithm 1 random grouping input: vocabulary of words v, a phonetic encoding parameter: output: grouping γ 1: perform a phonetic encoding (e.g. metaphone) as baseline 2: initialize the current group i ← 1 3: for each unique phonetic encoding do 4: ## algorithms for diverse grouping we now present our algorithms. we denote the set of words by v, and the set of groups by v, i.e., v is a subset of the powerset of v. each grouping can be encoded as a function γ that maps each word @xmath0. ## entropy maximization as submodular maximization in order to apply the optimization techniques from @xcite , which we briefly describe in section 3.3.1, we need to use a different representation of grouping. we view a grouping γ as the set of all pairs (w, γ i ) where γ(w) = γ i . for algorithm 4 initial grouping @xcite input: vocabulary of words v, relative frequencies f w parameter: groups [γ 1 , . . . , γ c ], @xmath1, precision parameter ε output: grouping γ ′ : @xmath2: brute-force search for w 0 with the biggest partial entropy note that an arbitrary set in v × v may not define a grouping. for instance, the set {("she", 1), ("tells", 1), ("tells", 2), ("me", 2)} does not, as it maps "tells" to more than one group. to apply the results of @xcite , we need to show that the grouping set family forms a matroid @xcite lemma 1. the grouping set family defines a matroid on v × v. to satisfy the conditions of a matroid, we need algorithm 5 unigram entropy diverse grouping input: vocabulary of words v, relative frequencies f w parameter: groups [γ 1 , . . . , γ c ], @xmath3, precision parameter ε output: grouping γ : @xmath4: compute initial grouping γ ′ using algorithm (4) 2: if γ ′ (w) is undefined for some w then 3: find a group γ i 0 with the lowest partial unigram entropy: moreover, the algorithm from @xcite ) requires an objective function to be submodular @xcite . intuitively, submodularity means that a function value changes less for larger inputs. lemma 2. the function h : v × @xmath5. to see that h is submodular, consider v and v as pictured in figure partial entropies of a group indexed by 1: now we give a sketch of the proof of theorem 1. proof. we claim that h(γ) ≥ c-1 4c+4εc h * where h * is the largest unigram entropy among all groupings. we should consider the case h(γ) < h(γ ′ ). the groupings γ and γ ′ differ only in index i 0 . thus the difference h(γ) -h(γ ′ ) is equal to the difference in the partial entropies we note that the group γ ′ i 0 with the smallest partial entropy contributes at most h(γ ′ )/c to the total entropy of γ ′ . moreover, partial entropy of γ i 0 is always non-negative. we obtain h(γ) -h(γ ′ ) ≥ -h(γ ′ )/c. our bound follows by plugging in the estimation h(γ ′ ) ≥ h * /(4 + 4ε) which is the approximation guarantee for the algorithm 4 from @xcite . ## experiments combination methods below, we will discuss how to incorporate our new representation using any of our grouping methods in nlp tasks. firstly, we group each word independently. applying a grouping function γ(•) in section 3 on each word one by one generates a sequence of word groups γ(x 1 ), γ(x 2 ), γ(x 3 ), • • • , γ(x i ), • • • , γ(x i ′ ) in the same length i ′ . note that we use the term "word" loosely here; it can mean a word or a subword (of a bpe token), or even a character. the first combination method is concatenation, see figure 3a . we apply this method in nmt. first, we concatenate two input sources. next, we apply the byte-pair-encoding @xcite (bpe) and word embeddings implemented by @xcite on each word ǫ(x) and its codeword ǫ γ (γ(x)). we separately train word embedding on groups and on words. thus, ǫ γ (•) and ǫ(•) are different functions. as shown in figure 3 , the input to the nlp system is the embedded words of a sentence, ǫ(x 1 ), ǫ(x 2 ), ǫ(x 3 ), • • • , ǫ(x i ), • • • , ǫ(x i ), where ǫ(x i ) is the concatenation of the embedded words ǫ(x i ) and their groups ǫ γ (γ(x i )): the second method is linear combination on encoder outputs, see figure 3b . we use this method in part-of-speech (pos) tagging. the input to the linear combiner is the grouped sentence, represented by a sequence of hidden states . j is the number of nodes at each decoder layer. recall that each hidden state is a real vector r d , which is why we can use the vector space operations such as addition on it. for convenience, we denote the last hidden state of the j-th encoder layer, which we take as the input to the decoder, hj (ǫ(x i )), by hj i , the last hidden state of the j-th encoder layer of the original textual sentence h j (ǫ(x i )) by h j i , and the last hidden state of the j-th encoder layer of the grouped sentence h j (ǫ γ (γ(x i ))) by h γ j i . the combined encoder hidden state hj is a linear interpolation of the hidden states of the textural input and its group input: as shown in figure ( 3b ), each layer's combined last hidden state is fed into the baseline decoder with the operator of +. α is the encoder weight of the grouped sentence, and here, α = 0.5. in the following context, we will show the our methods' evaluation results on three representative nlp tasks: (1) machine translation as a recognition and generation problem; (2) language modeling as a regression problem; and (3) pos tagging as a typical sequence labeling problem. we will show that our methods have the potential to improve any nlp application with textual inputs. ## conclusion we introduce a novel approach that generalizes deep learning models by grouping input words to maximize their semantic diversity. to this end, we design a family of algorithms based on random sampling, geometric distance, and entropy, and provide provable guarantees to the entropy-based diverse grouping. our methods reduce the number of low-quality translation outputs (< 10% in bleu) to half and greatly increase the high-quality translation (> 20% in bleu) ratio. experiments show that our approach significant improves over stateof-the-art baselines in neural machine translation (i.e., up to +6.5 bleu points) and achieves higher accuracy in pos tagging and language modeling. an arbitrary w ′ ∈ π(q) \ π(r) and its group γ i ′ in q; we have (w ′ , γ i ′ ) ∈ q\r. moreover, since w ′ is ungrouped by r, we conclude that r ∪ {(w ′ , γ i ′ )} ∈ g and finish the proof.