Lexically Grounded Subword Segmentation (2024)

Abstract: We present three innovations in tokenization and subword segmentation. First, we propose to use unsupervised morphological analysis with Morfessor as pre-tokenization. Second, we present an algebraic method for obtaining subword embeddings grounded in a word embedding space. Based on that, we design a novel subword segmentation algorithm that uses the embeddings, ensuring that the procedure considers lexical meaning. Third, we introduce an efficient segmentation algorithm based on a subword bigram model that can be initialized with the lexically aware segmentation method to avoid using Morfessor and large embedding tables at inference time. We evaluate the proposed approaches using two intrinsic metrics and measure their performance on two downstream tasks: part-of-speech tagging and machine translation. Our experiments show significant improvements in the morphological plausibility of the segmentation when evaluated using segmentation precision on morpheme boundaries and improved Rényi efficiency in 8 languages. Although the proposed tokenization methods do not have a large impact on automatic translation quality, we observe consistent performance gains in the arguably more morphological task of part-of-speech tagging.

## introduction statistical approaches to subword segmentation are the state of the art in most natural language processing (nlp) applications of neural networks, most notably the transformer model @xcite . the unigram model from sentencepiece @xcite and byte-pair encoding (bpe; @xcite are among the two most widely employed tokenization techniques. these methods gained popularity because of their versatility -they are language-independent and have convenient properties for model training, reducing the vocabulary size while assuring even learning of the token representations. despite the indisputable advantages, one aspect of the statistical word segmentation algorithms has remained a thorn in the eyes of many linguisticallyoriented researchers: subwords do not reflect morphology. this problem is especially pronounced in multilingual models, which share a common vocabulary across all languages. without a careful and balanced data selection, lower-resourced languages tend to have fewer allocated subwords, resulting in a large token-to-word ratio @xcite . we posit that a strong segmentation retains the property of the statistical approaches, i.e., that frequent words are split into fewer tokens than rare words. however, once a word is split into more tokens, the subword boundaries should ideally match the actual morpheme boundaries. 1 we hypothe-size that the standard algorithms lack morphology awareness because they do not work with lexical meaning, which is a crucial concept in language morphology. following @xcite , we conceptualize tokenization as a process with three steps (as illustrated in figure 1 ): pre-tokenization, vocabulary construction, and segmentation. within this conceptual framework, we propose three innovations throughout the whole process: in section 2, we discuss pre-tokenization and vocabulary construction. besides the standard pretokenization, which splits the text into word-like units (words, punctuation, etc.), we also experiment with morfessor @xcite , which we apply on top of the word-like pre-tokenized text. for lexically grounded segmentation, we derive a formula for computing subword embeddings using a pre-trained word embedding model and a training corpus (section 3.1). next, we use the subword embeddings to design a subword segmentation algorithm based on semantic similarity between the word and its subwords (section 3.2). finally, we propose a subword-bigram-based statistical segmentation algorithm that retains the properties of the embedding-based segmentation (section 4). with the bigram-based algorithm, we can have a model for subword segmentation that does not require running morfessor or storing a large embedding table. we test our approach using two intrinsic evaluation metrics and two downstream tasks (section 5.1). in the intrinsic evaluation, we test our approach on the sigmorphon 2018 shared task dataset @xcite and observe significantly better morphological generalization in both proposed algorithms with a fixed vocabulary size. we also measure the rényi efficiency @xcite of the unigram distribution of the segmented text, which has been shown to correlate with downstream model performance @xcite . additionally, we evaluate our segmentation algorithm on part-of-speech (pos) tagging using universal dependencies @xcite , showing an improvement compared to other segmentations. finally, we evaluate our tokenization on machine translation using a simulated low-resource iwslt 2017 dataset @xcite where we reach results comparable with currently used subword tokenizers. we show the code examples in appendix a and we release the code for the segmentation tool, legros, foot_2 as well as the experimental code. foot_3 ## pre-tokenization and vocabulary construction neural networks can only have limited vocabularies in order 10 4 -10 5 , which rules out using wordbased vocabularies. a common solution is statistical heuristics that keep frequent words intact and split rare words into smaller units, ensuring that there are no rare tokens, such that embeddings of all tokens get updated reasonably often. the most popular methods are byte-pair encoding (bpe; sennrich et al., 2016) based on greedily merging the most frequent token pairs and the unigram model (as implemented in sentencepiece; kudo, 2018) that returns high-probability segmentations using a unigram language model. however, these methods manifest low morphological generalization, which in turn might lead to reduced interpretability, compositional generalization, and cross-lingual transfer capabilities. perhaps the most straightforward approach for lexically grounded word segmentation is to use unsupervised morphological analyzers, such as morfessor. however, direct use of these linguistically motivated tools leads to worse results @xcite and is only beneficial in low-resource scenarios @xcite . furthermore, morphological analysis does not fully address the problems of rare tokens and vocabulary size. to address these issues, we propose only using morphological analyzers during pretokenization (step 1 in figure 1 ). after pretokenization, we apply the well-established statistical methods for vocabulary construction. this combination ensures that there will be a low number of rare tokens and efficient control of vocabulary size while still preserving the lexical meaning of the subwords. ## segmentation with subword embeddings in this section, we describe a novel lexicallygrounded segmentation method (step 2 in figure 1 ). when considering language morphology, we assume the word can be decomposed into several smaller meaningful units that carry the meaning of the original word when combined together. we consider the segmentation of a word to be lexically grounded when it respects the word's meaning and does not introduce subword boundaries in the middle of meaningful units. to find such a segmentation, we need to model the meaning of both words and subword units jointly. 4 a widely used proxy for capturing the lexical meaning of words is word embeddings. to capture the meaning of subwords, we introduce a method to compute subword embeddings in a shared space with the word embeddings ( § 3.1). we also describe a segmentation algorithm that takes the subword embeddings into account ( § 3.2). ## bigram model the segmentation algorithm described in the previous section has several drawbacks: it requires storing relatively large embedding tables for words and subwords and does not generalize for oov words without embeddings. moreover, pre-tokenization with morfessor requires running language-specific models, making the segmentation more computationally demanding than the established method. we avoid this drawback by introducing an alternative segmentation algorithm based on subword bigram statistics. it is a straightforward generalization of the commonly used unigram model. at inference time, we search for a segmentation that maximizes probability predicted by a subword bigram model instead of a unigram model. the optimization problem is solvable using dynamic programming, similar to the unigram model. however, the algorithm has a quadratic complexity in the segmented string length. therefore, we propose using a linear-time beam search algorithm that only considers k best segmentations in each step. the full algorithm is described in algorithm 2 in appendix a. we use the subword bigram statistic obtained by counting subword bigram and unigram frequencies in a corpus tokenized by a tokenizer that we want to distill into the bigram model. to account for unknown bigrams encountered during inference, we need to eliminate zero probabilities from the bigram distribution. to this end, we apply laplacian smoothing, i.e., we increase the frequency of every bigram (s i |s i-1 ) by one. additionally, if s i-1 is an unknown unigram, we assign the unigram probability of s i to the bigram. if both s i and s i-1 are unknown unigrams, we assign uniform probability 1/|s| to the bigram. ## experiments we evaluate our proposed methods intrinsically using morpheme boundary precision and rényi efficiency, as well as extrinsically on two downstream tasks: part-of-speech tagging and machine translation. ## conclusions in this paper, we devised morphologically plausible methods for subword segmentation. inspired by @xcite , we divide the tokenization process into three steps: pre-tokenization, vocabulary construction, and segmentation. we described three key contributions of our work. our first contribution focuses on the pretokenization step: instead of the standard approaches, which split the text into word-like units, we use morfessor, which splits the text into morphemes. however, we only regard this as pretokenization. next, we proposed a novel segmen-tation algorithm based on word and subword embeddings, which provides lexical grounding to the segmentation. finally, we proposed a statistical bigram segmentation model that can be used to simplify complex tokenization pipelines. the intrinsic evaluation results show that the proposed method better captures language morphology than standard statistical subword segmentation approaches. this is further confirmed by the results we obtained on pos tagging, in which information about morphology is a key feature. however, our method did not significantly improve the performance of machine translation, which is a more complex nlp task. we argue that a dedicated analysis would be required to determine the exact influence of the lexically grounded segmentation on the translation quality, which might be improved in one dimension but reduced in another. in our work, we have taken steps to create a more morphologically accurate tokenization method while keeping the benefits of statistical subword segmentation. we believe these methods will improve modeling language overall and contribute to model interpretability and cross-lingual transfer.