The Shape of Word Embeddings: Quantifying Non-Isometry with Topological Data Analysis (2024)

Abstract: Word embeddings represent language vocabularies as clouds of d -dimensional points. We investigate how information is conveyed by the general shape of these clouds, instead of representing the semantic meaning of each token. Specifically, we use the notion of persistent homology from topological data analysis (TDA) to measure the distances between language pairs from the shape of their unlabeled embeddings. These distances quantify the degree of non-isometry of the embeddings. To distinguish whether these differences are random training errors or capture real information about the languages, we use the computed distance matrices to construct language phylogenetic trees over 81 Indo-European languages. Careful evaluation shows that our reconstructed trees exhibit strong and statistically-significant similarities to the reference.

## introduction does the shape of an unlabeled, monolingual word embedding carry relevant information about the language it represents? word embeddings are wellestablished objects of interest in natural language processing, being d-dimensional vector representations that capture the semantics of each vocabulary word. the vocabulary of language l can thus be viewed as a cloud of points, whose geometric and structural properties encode considerable information about the language. in this paper, we demonstrate that, even after disassociated from their bindings to particular words, the "shape" of these point clouds correlates with the history of the languages they represent. we use techniques from topological data analysis (tda), a field studying spatial aspects of data, to quantify this correlation. how much shapes of word embeddings differ, and for what reasons, is an ongoing debate with important consequences. many authors assume that the word embeddings of different languages are essentially isometric: meaning they only differ by an orthogonal transformation. such assumptions are necessary, for example, to construct translators between languages via bilingual lexicon induction @xcite @xcite . this assumption has been disputed by @xcite or @xcite . later @xcite argued that observed deviations from isometry are largely due to insufficient data or training in construction of embeddings for some languages. in this paper, we demonstrate that these observed non-isometries across languages contain real information and are thus not random training artifacts. we analyze fasttext embeddings of 81 indo-european languages and quantify nonisometry among the 10k most frequent tokens of each language with tda-based distance matrices. to show that those distances contain real information we construct phylogenetic trees and compare these to a gold-standard reference tree from ethnologue @xcite . the history of language evolution is typically studied by identifying cognate word pairs of languages l 1 and l 2 , namely homologous word forms inherited from the common ancestor of these languages. cognates usually share some level of surface-form similarity between them, with language pairs sharing more cognates presumed to be more closely related. the identification of cognate pairs traditionally requires extensive labor by skilled linguists, although computational methods for detecting cognate pairs are emerging @xcite @xcite . an interesting aspect of tda on word embeddings is that it makes no assumption or use of translation pairs, surface similarities between words, or cognate pairs. word embeddings are treated as unlabeled sets of points, shorn of any binding to corresponding tokens. tda compares the relative shape of word embeddings in terms of structural properties like components of connectivity and holes. that we demonstrate even a weak ability to reconstruct language phylogenies through tda is quite surprising, and suggests that there are hitherto unknown structures reflected in word embeddings that go beyond the semantics of individual words. our major contributions in this paper include: further evidence that even within the indo-european family the non-isometry between unlabeled word embeddings is not completely erroneous. the fact that we reconstruct phylogenetic trees that, despite not very precise, are considerably better than chance, suggests that there is some real information represented in the differences between unlabeled shapes of embeddings. it is fair to argue that more careful training, normalization and lemmatisation could yield more similar embeddings that miss the information; were that the case, it would suggest that the differences mitigated by those processes correlate with language history, which is an equally interesting observation. a case study of natural generalizations of previously used methods to quantify non-isometry. tda provides a relatively new set of tools for data science able to capture features often missed by more traditional approaches. due to the general framework it provides, there are many parameters to choose from and a priori no obvious canonical choices. our analysis on word embeddings represents a rigorous evaluation for an interesting use-case of this technology. a particular instance of tda was used in @xcite ; @xcite as an approximation @xcite of difficult-tocompute gromov-hausdorff distance to quantify non-isometry of word embeddings. in the tda terminology, they computed bottleneck distance between degree 0 persistent diagrams-we additionally explore degrees 1 and 2, and three different distances in addition to bottleneck; each combination for both euclidean and cosine metric on the word embedding. altogether this totals to 24 different combinations of parameters, and for each we obtain a distance matrix between the studied languages. all those notions of distances are invariant under orthogonal transformations foot_0 , and therefore serve as quantifications for non-isometry. the alternative combinations can be better suited for studying word embeddings, e.g., by being less prone to irrelevant outliers that can artificially significantly increase the gh distance. our analysis also shows that degree 2, which is not that often used in large high-dimensional data because of the expense in constructing them and difficulty to interpret them, yield statistically-strong results in our experiments, in some cases outperforming degrees 0 and 1. ## topological data analysis topological data analysis (tda) is a growing field that applies methods developed for studying shapes to data, both geometrical and abstract, to extract features that are often not captured by classical approaches of data science. in the case of points or vectors in 2d or 3d, we observe patterns like clusters of points, loops, voids or tunnels. in this paper, the input is a word embedding of a language-collection of points in high-dimensional euclidean space, one for each token-and the output is a summary of its topological features. we compute such summaries for embeddings of different languages, and use them to compare the structural similarity. as orthogonal transformations would preserve the summaries, those differences quantify non-ismoetry of the different embeddings. to keep the explanation intuitive, we stay with low dimensional point sets, but the general framework is limited neither by dimension of the data nor by the euclidean metric-indeed, we use 300dimensional word embedddings and impose both euclidean and cosine metrics. for a gentle introduction to tda see @xcite . for more technical details, see @xcite . for applications of tda to a wide variety of real-world data, see the database of nontheoretical uses of topology @xcite . ## constructing phylogenetic trees to evaluate whether the distances between languages calculated based on persistence homology are relevant, we use this data to attempt to reconstruct the historical evolution of indo-european languages. we perform a hierarchical clustering, obtain a phylogenetic tree, and compare this tree to a ground-truth reference tree. we emphasize that reconstructing language phylogenies is not the goal of our analysis, but rather we use it as a tool to evaluate whether the computed distances carry a relevant signal, meaning the unlabeled topological "shape" of word embeddings retain and reflect broader properties of the underlying languages. phylogeny reconstruction is an enormous area within computational linguistics, and space does not permit us to make a substantial survey of work in this field. see @xcite ; @xcite ; @xcite for recent reviews of this literature. in this paper, we experiment with two popular agglomerative hierarchical clustering algorithms for reconstructing phylogenetic trees from a pairwise distance matrix, d(•, •). we start with each language as an individual cluster, and then we connect two closest clusters in each step. the difference is what "closest" means for each of the algorithms: unweighted pair group method with arithmetic mean (upgma). the upgma method @xcite approximates distances between clusters as the average distance between the elements: for clusters a, b, the distance is starting with singleton clusters, in each step it merges the two closest clusters into one. neighbor joining (nj). the nj method @xcite defines distances between clusters, d(•, •), inductively through a merging process. let c be the collection of current clusters. for each cluster, @xmath0, define ## analysis pipeline this section details the data, the process of going from the data to trees, and finally the evaluation of the reconstructed trees. our code for the analysis is published on github. foot_3 ## results of the experiments the experiments show correlation between the word embedding dissimilarity and language phylogeny-for 484 out of 864 distributions, at least 95,000 (95%) of the permutations are further from the reference tree e than the reconstructed tree t is. figure 2 is the primary result in this paper, presenting the results of evaluations of 144 different tree reconstructions based on tda, each evaluated on six different tree similarity measures, for a total of 864 different points. by employing permutation tests, we can map each such point to a significance level, expressed in terms of (a) the fraction of random samples dominated by the reconstructed tree or (b) the number of standard deviations the reconstructed tree sits from the mean value over 100,000 permutations of leaves; the options are tightly correlated. figure 2 10 4 10 3 10 2 10 1 10 0 p-value [log scale] 0% 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100% fraction of parameter combinations 30 languages 50 languages 81 languages p=.5 further summary of these results is in figure 3 . the cumulative distribution plots show the fraction of experimental conditions which satisfy a given permutation test p-value. with respect to this value, 484 out of the 864 conditions proved significant to at least the 0.05-level. of these, 255 were significant to at least 0.01, 57 to at least 0.001, and 10 to 0.0001. in one case the algorithmic tree dominated all @xmath1,000 random permutations evaluated. our statistically strongest results came when using 50 languages: possibly large enough to encode topologies hard to find by chance while avoiding low resource languages with poorly shaped embeddings. twice as many tests for upgma trees (114) were significant to the 0.005-level as nj trees (63), demonstrating that better combinatorial optimization leads to more significant phylogenies. different distances between persistent diagrams seem to fit well with different degree and token-totoken metric. overall, bars statistics and sliced wasserstein seem to perform better, while bottleneck is the least successful-this might be explained by its strong sensitivity to outliers, and suggests that the other notions might be better suited for analyses of word embeddings' (dis)similarities. detailed breakdowns of the success of different parameters are provided in tables 1 , 2 , 3, 4 in the appendix. that our best tree beats all trial t permutations in our experiment implies it is significant beyond the 1/t level. by measuring the quality score of each tree with respect to each distance in terms of the number of standard deviations above its random background mean and assuming normality, we can obtain a p-value associated with each such z-score. the maximum achieved 6.87σ corresponds to a bonferroni-corrected p-value of 2.77 × 10 -9 = p [@xmath2.87] * 864, assuming a normal distribution. coupled with all other presented permutation test results, clearly tda is picking up real signal from the shape of word embeddings. ## conclusions our analysis of fasttext word embeddings of 81 indo-european languages suggests that deviations from pair-wise isometry correlates with the historical origin of the languages-an interesting contribution to the debate about the extent to which the variance between monolingual embeddings is explained by essential differences between the languages versus scarcity of resources and undertraining when constructing them. a natural question is to what extent the presented results generalize. would we get comparably significant results for word embeddings trained with different algorithms, with different parameters or on a different corpus? and if more careful training should lead to isometric embeddings, as suggested by @xcite , is there an explanation for a correlation of lower quality of embeddings with language phylogeny? the results suggest that tda methods can help us better understand the structure of word embeddings, and further research can lead to useful insights. different parameters can be better suited for comparing word embeddings than the previously used bottleneck lower bound of gromov-hausdorff distance. furthermore, better understanding of the particular detected topological features could lead to interesting insights. for example, looking at a single language embedding, we can look back at concrete loops in degree 1 persistence diagrams and ask whether the collection of words it passes through has some meaningful linguistic interpretation. or, identifying a large loop in one language, we can ask whether the translation of the words also forms a large loop in other languages.