Unsupervised Tokenization Learning (2022)

Abstract: In the presented study, we discover that the so-called “transition freedom” metric appears superior for unsupervised tokenization purposes in comparison to statistical metrics such as mutual information and conditional probability, providing F-measure scores in range from 0.71 to 1.0 across explored multilingual corpora. We find that different languages require different offshoots of that metric (such as derivative, variance, and “peak values”) for successful tokenization. Larger training corpora do not necessarily result in better tokenization quality, while compressing the models by eliminating statistically weak evidence tends to improve performance. The proposed unsupervised tokenization technique provides quality better than or comparable to lexicon-based ones, depending on the language.

## introduction unsupervised language learning, framed as a problem of language modeling based on unannotated corpora, has attracted great attention in recent years, having achieved significant results with transformer-based models such as bert and gpt that rely on deep neural networks (dnns) @xcite . at the same time, the idea of unsupervisedly learning a language grammar represented "interpretably" via a formal grammar such as link grammar has been suggested by @xcite . @xcite proposed yet another approach for the problem: using so-called "deep patterns" with hierarchical "symbolic" grammatical pattern structures learned from texts as a way to model grammars and ontologies for natural languages suiting a wide range of practical applications. further studies on this path performed by @xcite have indicated the possibility of learning grammars as well as domain ontologies given highquality parse trees of texts obtained from unannotated training corpora. unfortunately, the critical part of the pipelines described in the aforementioned studies was the unsupervised generation of the parses, which turned out to be low-quality by virtue of being based on simple "minimum spanning trees" either based on mutual information (mi) (see @xcite or "contextual information" (see @xcite extracted from a bert-based deep learning model @xcite . still further studies by ramesh and kolonin have demonstrated the possibility of building different natural language processing (nlp) applications based on a language model represented by a formal grammar (link grammar in the explored cases) @xcite @xcite . throughout the course of these studies, the concept of "interpretable natural language processing" (inlp) has been introduced to indicate the domain of nlp explorations involving both the learning of language models represented in an interpretable form and the application of these models to different tasks such as text segmentation, language generation, and question answering. yet another problem which has its place in the case of conventional language model learning based on dnns (see @xcite as well as in relation to interpretable unsupervised language learning (see @xcite @xcite is tokenization. in most cases, tokenization is based on predetermined rules and dictionaries, which does not quite fit the "grand plan" of completely unsupervised language learning from scratch with no prior knowledge of the language, including its lexicon and punctuation @xcite . thus, the objective of our proposed study is to evaluate the possibility of learning the sets of tokens representing both punctuation and lexicons without any prior knowledge regarding the language, so that the set of valid combinations of letters or characters specific to punctuation marks or valid lexical entities such as words for a language is learned along with the tokenization process. starting points were found in works of @xcite and @xcite , who explored the possibility of unsupervised segmentation applied to different languages and domain-specific literature. the former work (see @xcite provides an exhaustive overview of different tokenization techniques applied to different languages, exploring different methods and metrics. unfortunately, the f 1 scores reported in this work for completely unsupervised tokenization based on statistical measures appear not high enough, so we further follow this approach in order to outperform these scores on the set of languages relevant and available to us-english, russian, and simplified (mainland) chinese-focusing on unsupervised tokenization only. the latter work (see @xcite focuses on unsupervised tokenization based on statistical measures such as conditional probability (cp) as well as introduces the so-called "freedom of transition" (we henceforth call it "transition freedom" or tf) metric, which appears fundamentally consistent with the notion of "free energy" suggested by @xcite as a key for an artificial intelligence concept. tf in the context of @xcite work corresponds to the number of symbolic states (characters, letters, or n-grams) that follow or precede the current state. then, a sharp increase of the tf level along the temporal sequence of states might correspond to a loss of @xcite "equilibrium," and so "tokens" might be considered as chains of states resting in conditions of mutual equilibrium framed with transitions, with loss of this equilibrium marked by the tf level bursts. furthermore, we explore both statistical measures and tf metrics, finding the latter substantially more practical. in particular, we explore different metrics based on cp and tf such as derivative, variance, and "peak values" as introduced in wrenn et al.'s (2007) work (which indicate expressed local maximums on the derivative curve along the text being tokenized). interestingly, kearsley (2016) writes that, "given that the human ability to successfully read any natural language provides an existence proof that a generalized segmentation system (as implemented in the human mind) is possible, it is reasonable to investigate the feasibility of a languageagnostic segmentation system that could be easily integrated into larger natural language processing systems." extending this statement, we anticipate that advances in this area could be also beneficial to deal with any sequential data such as flows of events and states in experiential or reinforcement learning. in particular, the "global feedback" concept suggested in kolonin's (2022) work demonstrates good learning rates in cases when the cognitive schema leading to the feedback or reward can be reliably associated with entire sequences of preceding actions, which is difficult to deal with in existing reinforcement learning frameworks. the ability to segment sequences of cognitive experiences unsupervisedly might potentially advance research on experiential and reinforcement learning with delayed reward or with no explicit feedback in any subject domain beyond nlp. the importance of the latter goal is also outlined in @xcite work, where it was stated that the "discovery of reusable sub-routines simplifies decision-making and planning in complex reinforcement learning problems." as will be presented further, we find the tf to be superior over mi (see @xcite @xcite and cp (see @xcite for the task of unsupervised text segmentation (tokenization). we find that the english and russian languages require one specific way of handling the tf (variance) while chinese requires a slightly different way (derivative-based "peak values") for the same purpose. tokenization quality for english and russian may have f 1 scores as high as 0.96-1.0 depending on training and testing corpora, while for chinese the best score is f 1 = 0.71 with precision of lexical word discovery reaching 0.92. larger training corpora do not necessarily result in better tokenization quality, while compressing the models by eliminating statistically weak evidence typically improves the quality. unsupervised tf-based tokenization provides quality that is the same as or better than lexicon-based tokenization for english and russian, while for chinese it appears to be the opposite (as could be anticipated); however, the precision of lexicon discovery for chinese using tf-based tokenization appears close to reference tokenization. ## data sets we have used different training data sets for three different languages (english, russian, and chinese), while the same parallel corpus has been used for testing. for english training corpora we have used the brown ( http://www.sls.hawaii.edu/ble y-vroman/brown_nolines.txt ), gutenberg ( https://www.gutenberg.org ) children, and gutenberg adult collections, as well as mixed collections such as gutenberg children and adult blended together and all three corpora blended together. the sizes of the above corpora are 6m, 29m, and 140m, respectively. for russian training corpora we have used the rusage collection ( https://www.kaggle.com/d atasets/oldaandozerskaya/fiction-corpusfor-agebased-text-classification ) as two separate pieces: test (141m size) and previews (825m size), each used as an independent training corpus. for chinese training corpora we have used the clue benchmark news 2016 dataset ( https: //github.com/brightmart/nlp_chinese_cor pus), which contains two pieces: train and validation. each piece was used as an individual training dataset. the raw data encoded in json format have been processed so that title, desc, and content fields were extracted individually and each of the three fields was saved on a separate line in the text file used as input for further processing. after such preprocessing, we obtained an 8, 500m-size training dataset and a 270m-size validation dataset. for the test corpus across all three languages above, we have used a parallel chinese/english/russian corpus of 100 multi-sentence statements within the financial domain, as derived from the dataset released by magic data ( https://magichub.com/datasets/chines e-english-parallel-corpus-finance ). the original corpus is parallel chinese/english, but the russian version of all 100 statements have been added with the help of google translate, with chinese proper names manually replaced with russian or english proper names used in the appropriate subject domain context. english and russian reference lexicons have been obtained from the aigents/pygents open source project: english ( https://raw.github usercontent.com/aigents/aigents-java/m aster/lexicon_english.txt ), russian ( https: //raw.githubusercontent.com/aigents/aige nts-java/master/lexicon_russian.txt). a few different chinese lexicons were obtained for reference: chinese lexical database, or cld ( http://www.chineselexicaldatabase.com /download.php ) (see @xcite ; blcu chinese corpus, or blc ( https://www.plec oforums.com/threads/word-frequency-lis t-based-on-a-15-billion-character-co rpus-bcc-blcu-chinese-corpus.5859 ); and subtlex-ch ( http://crr.ugent.be/progr ams-data/subtitle-frequencies/subtlexch ).