Bio-inspired Structure Identification in Language Embeddings

Similar to Coenen et al., this dataset uses base BERT for embedding generation and Wikipedia as language corpus [5]. Each generated dataset is particular to a single word, and defines the context relative to that word – typically resulting in 1000s of tokens. Each data point then refers to a sentence in which the word occurred within the corpus. We can interpret this as a volume of semantic space where the meaning of a token can fluctuate based on its actual usage in the text. We will be referring to these as “BERT-X”, with “X” being the represented word.

This dataset uses Gensim Continuous Skipgram – a variation of Word2Vec – to process the English Wikipedia Dump of February 2017, resulting in approximately 300k tokens. In contrast to contextual embeddings, each data point refers to a single token instead of the sentence in which a token is used. A token includes two pieces of information: the word and its part of speech. For example, wind_NOUN and wind_VERB are considered separate tokens and occupy different positions. This is different from BERT where the part of speech is not made explicit. We will be referring to this dataset as “W2V-300k”.

The original word embeddings are high-dimensional: BERT embeddings are 768-dimensional while those by Gensim Continuous Skipgram are 300-dimensional. To make visualization and analysis feasible, we rely on UMAP (with neighborhood size of 15) to project the data to 3D space. The dimensionality reduction is necessary, due to the high memory requirements of our notion of transport network: this is based on a continuous representation by a density field, both in the visualization (Section 3) and exploration (Section 4) stages.

Naturally, this implies the loss of some information, particularly sacrificing the global structure of the data to preserve local neighborhood relations (however, less so than other dimensionality reduction methods such as PCA or TriMap [2]). It is also likely that additional geometric structures are induced in this process. Yet in Section 4 we show that even these distortions do not render the dataset unusable when the detected structures are used for navigating the embedding. Sections 5 and 6 discuss this in further detail.

Even though the token data in W2V-300k appear disorganized on the first glance (Figure 1), MCPM reveals rich network-like geometry. This structure is chaotic, even fractal, with filaments folded into themselves – probably as a result of compressing the high-dimensional embedding data into 3D. The structures exist at the level of entire clusters, rather than interconnecting individual words, although this might be a limitation of the underlying lattice resolution.

Even though some outlying tokens are present, the vast majority of these data forms a single densely interconnected network. This might be a reflection of how interlinked the source Wikipedia corpus is. We observe two recurrent features: filaments and knots. Some token clusters are distributed along the filaments, while others lie in the knots where multiple filaments intersect. We also notice different strengths (densities) of filaments, usually in proportion to the number of tokens contained within them.

Since each local embedding corresponds to a specific word, we have generated the BERT embeddings for several interesting words and then chose three representative ones: wind (a homonym), back (a polysemous word), and research. The geometric structures that MCPM infers here (Figure 2) are similar to W2V-300k, but exist on a smaller scale: the filaments interconnect words or groups of words, rather than entire clusters.

MCPM also functions as an implicit clustering mechanism. UMAP is designed to preserve components during the dimensionality reduction, but clustering them is not trivial due to their irregular shapes. MCPM manages to identify and interconnect the clusters (as a function of the model’s characteristic feature scale). Some clusters are interconnected densely similar to W2V-300k, others are sparse and branchy, perhaps indicative of the usage patterns of these words. The number of connected components also matches intuition: words like wind and back have multiple discrete contexts, while research has only one but very broad context. General terms like class and suit yield more than 10 components. Further discussion on clustering is provided in Section 5.

We deploy an agent-based algorithm inspired by MCPM (see Section 3), but significantly simplified. We will refer to the agents of this process as probe agents. The main difference is that probe agents traverse the already detected trace field without modifying it. Second, their geometric behavior is more basic in comparison to MCPM agents.

Each step of the probe agents consists of two phases: sensing and steering. In the sensing step, an agent samples values $p_{0}$ and $p_{1}$ from the trace (Figure 4-left). The sample distance $sense\_distance$ is determined prior to the simulation. The value $p_{0}$ lies along the agent’s current movement direction, while $p_{1}$ is sampled from a cone determined by a constant $sense\_angle$. Then in the steering step, the agent makes a decision whether to turn or not based on the probability proportional to $p_{0}$ and $p_{1}$ (Figure 4-right). If the agent turns, its new movement direction is then changed by $0<random\_angle<sense\_angle$ towards the sensing direction, with $random\_angle$ sampled uniformly in the given interval.

Each probe agent’s behavior is a random walk process. Due to the probabilistic steering step, the trace guides the agents so that they effectively follow the transport network structure. Our typical random walk search uses 900 probe agents, each performing 500 steps. We consider a token ‘discovered’ if any of the agents passes around it within a small distance, usually between $1/400$ and $1/200$ of the domain size.

Figure 5 demonstrates the impact of the trace guiding, in comparison to unguided, purely random search. With trace guiding, most agents follow a few distinct paths to discover the surrounding token clusters. Without guiding, the random-walk process ends up being equivalent to the nearest neighbor search: the likelihood of a token being discovered decreases as a square of distance from the origin, as the agents become more spread-out. The two marked regions A and B in Figure 5-right, illustrate this contrast: from the random walk density we see that region A is more thoroughly explored than B in spite of both having a similar Euclidean distance from the source. This translates to A being closer within the paradigm of optimal transport.

Using word embeddings, we can evaluate the relations between words geometrically. For word similarity, the two widely used similarity metrics [7, 3, 24, 16] are the standard Euclidean distance $d_{Euclid}(v1,v2)=||v1-v2||$ and cosine similarity $d_{cos}(v1,v2)=v1\cdot v2$. Cosine similarity assumes that two words represent directions on an N-dimensional hypersphere: the closer the directions, the more similar the words. The implication of this metric is that the spatial distance between two data points matters less than their direction from the origin.

To provide a structure-aware measure, we define our similarity metric by how reachable one data point is from another. In contrast with cosine and Euclidean similarity, MCPM similarity is defined by connectedness rather than their pure distance in space. In other words, the closeness of two data points is measured by whether other data points lay down a clear path between them. To this end we deploy agents from a chosen source point (Figure 5). If a point is found sufficiently close to an agent at any simulation step, a counter for that point is incremented. The resulting similarity to the source data point is proportional to the value of this counter at the end of the search (normalized over all discovered points).

To explore this new similarity measure, we choose $wind\_NOUN$ in W2V-300k to generate the similarity rankings based on the three different metrics. We discuss how the metrics fare in section 5, but some distinctions can be gleaned from the word clouds of the top 30 discovered tokens shown in Figure 3 and the difference list between MCPM ranking and other two rankings shown in Table 1. The entries are ordered by descending difference between the MCPM ranking and Euclidean ranking.

The contextual embeddings visualized in Figure 2 show a clear separation of clusters. MCPM acts as a robust clustering method here, in spite of their highly irregular shape. We identify these clusters visually as components (sub-networks) interconnected by MCPM. Specifically, two tokens belong to the same cluster if one can be reached from the other by following the MCPM trace network. To explore the contents of these clusters, we sample several sample locations inside the embedding BERT-back, and then visualize the resulting searches in Figure 6.

The samples found within each cluster demonstrate clear differences in the word usage patterns (see Table 2). The irregular top cluster usages of back as an indication of spatial relation. Both bottom-left and bottom-right clusters demonstrate back as verbal particles used in phrasal verbs. The smaller cluster in the bottom-left shows usages of back as a movement in time. Finally, the large bottom-right cluster indicates directionality of communication.

The separation of clusters as seen for polysemous words like back and wind (see Figure 2) indicates clear boundaries of these volumes and hints on the number of distinct contexts in which these words occur. MCPM similarity is useful here to not only identify the clusters, but to allow for their efficient exploration starting at arbitrary seed points within the clusters.

With the structural information carried by the MCPM trace, we observe two distinct types of data points: knot words and filament words. As their names suggest, knot words are words positioned inside clusters and their emitted agents travel with no clear directionality, while filament words are positioned on the paths connecting clusters. For instance, the position of research_NOUN, visualized in Figure 7, stands in contrast with that of class_NOUN. We observe a clear difference in the distribution of agents’ travel directions.

So far, the identification of these concepts has been based on the visual analysis (Section 3). To enable automatic extraction of these properties, we propose to measure the directional statistics of agents spawned by a given query token. Per intuition provided by the visual analysis, the directional distribution of probe agents from a filament word should be bi-modal, while knot words should yield more complex multi-modal distributions. Based on these criteria, we plan to study these properties in bulk, and determine their origins and semantic significance.

The three compared rankings emphasize different mathematical relations. Cosine similarity measures orientation with respect to origin, Euclidean similarity measures geodesic distance in a homogeneous space, and MCPM similarity builds on the optimal-transport throughput. Our aim is to explore how these properties can be used for a more intuitive way to understand machine-generated language representations. Based on the similarity rankings, different properties seem to highlight some word tokens that others do not. Curiously, the cosine similarity shows many items not found in other rankings. For the query wind, words such as budget, ornamentation and overpay seem rather out-of-place but are still placed highly in the ranks. Euclidean and MCPM rankings have much more agreeable candidates in higher ranks such as gust, hurricane-force and anemometer. Many of them are specialized terms in climatology. This implies that geodesic distance is an important factor when considering word closeness in W2V-300k.

We also observe a divergence between Euclidean ranking and MCPM ranking in Table 1. MCPM similarity manages to capture words quite far away from the source point. Interestingly, the two words unseasonable and near-record are still consistent with the general climatological theme of the similarity ranking. Words like anticyclone and intertropical are very similar to many of the top candidates such as cyclogenesis and non-tropical. This finding seems to suggest that spatial distance is also an imperfect measurement of similarity, and the measurement of similarity should also consider the throughput between words. This of course needs to be verified by a broader, quantitative study in the future.

It is also important to realize that the definition of similarity as such is rather vague semantically. Computational linguistics distinguishes between the concept of association and similarity. While one would agree that tropical is more similar to wind than overpay, we can only claim they are more similar because it’s easier to associate the word tropical to wind. At the same time, the word gust and squall can be said to be associated with, but also similar to wind [14]. It remains an open question whether there is a way to extract the distinction between associated and similar words in word embeddings.

Since the Monte Carlo exploration is a stochastic process by definition, it is important to address the stability of our similarity ranking. On the word embedding level, studies have shown embedding algorithms to be non-deterministic even with the same training data and configuration [12]. On the trace generation level, and the subsequent trace-guided exploration by probe agents, we solely rely on converged aggregate solutions. In the MCPM similarity ranking, we observe that the results are fairly stable as each ranking only shifts by 1 to 2 places between different results. From this we conclude that the probabilistic nature of our framework does not render the results unreliable, especially considering that even human-produced rankings tend to have significant inter-subject variation.

Ultimately, an important question to consider is to what extent are the discovered transport networks and resulting structures inherent to the embeddings. It has been shown that non-linear methods such as t-SNE and UMAP distort pairwise relationship between embeddings, while PCA can introduce false positive parallel pairs in its result[19]. The important consideration is therefore the choice of the projection method: we chose UMAP because of its recognized ability to preserve both global and local structures, as well as the number of components in the source data. This is in contrast to other methods like t-SNE and PCA, which are known to destroy all global and local structure, respectively. Our experiments with different configurations of UMAP also showed that regardless of the resulting projection shape, the structures were present and reliably recovered by MCPM. Finally, the fact that MCPM similarity yields reasonable results even in 3D is very encouraging, and motivates us to look for solutions that operate in the native, high-dimensional embedding space.