Language is dynamic and constantly evolving: both the usage context and the meaning of words change over time. Identifying words that acquired new meanings and the point in time at which new word senses emerged is elementary for word sense disambiguation and entity linking in historical texts. For example, cloud once stood mostly for the weather phenomenon and only recently gained the new sense of cloud computing. We propose a clustering-based approach that computes sense trees, showing how meanings of words change over time. The produced results are easy to interpret and explain using a drill down mechanism. We evaluate our approach qualitatively on the Corpus of Historic American English (COHA), which spans two hundred years.
An example for WSI can be found in the context of depression. Depression is
commonly known in the sense of a mental health disorder, but also in the sense
of economic crisis in the term great depression. The aim of WSI is to nd out
which senses the word depression has. Word sense disambiguation (WSD), on the
other hand, is known as the automated disambiguation of a word sense within a
text [
We propose a WSI method that detects new senses by creating multiple
co-occurrence graphs over time, and extracts word senses based on so-called
ego-networks. For a given word, it uses graph clustering to extract word senses
from the word's ego-network. These word senses are matched over time to create
a forest of so-called \sense trees". This forest can be explored to nd out if
and when a word gained new senses over time. With the help of linguists, we
annotated a list of 112 words for evaluation1 and tested our approach using
the Corpus of Historical American English (COHA), with 400 million words the
largest corpus of its type [
Research on word sense induction and word sense disambiguation addresses how
to improve information retrieval in search engines, information extraction for
speci c domains, entity linking over time, machine translation, and
lexicography [
Word embeddings are vector representations of words in a semantic space
that allow for word meanings to be induced by context. Word embeddings are
trained by a neural network that learns to predict a word based on its context
words or vice versa. Hence, words with similar contexts have a similar vector
and are thus in close proximity to each other. The initially proposed word2vec
model [
However, neither traditional word embeddings, like word2vec, nor sense
embeddings consider the temporal aspect and assume that words are static across
time. This creates a challenge in the face of dynamic and changing natural
language [
diachronic word embeddings were introduced [
Another method for extracting word senses is through the use of graph
clustering or community detection. This method builds a graph based on
cooccurrence features from a corpus. Such graphs represent the relation of words
to each other, and allows for the extraction of sense clusters through graph
clustering. Automatic word sense change detection based on curvature clustering
can help understand the di erent senses in historic archives [
Mitra et al. present an approach that builds graphs based on distributional
thesauri for separate time periods [
Besides embeddings and graph models, topic modeling has been applied to
WSI as well. Lau et al. model word senses as topics of a word by application of
latent Dirichlet allocation (LDA) as well as non-parametric hierarchical Dirichlet
processes (HDP). They also applied their approach on the eld of novelty sense
detection by comparing induced senses of words of a diachronic corpus containing
two time periods for a self developed dataset of 10 words [
Jatowt and Duh provide a framework for discovering and visualizing semantic
changes w.r.t. individual words, word pairs and word sentiment. They use n-gram
frequencies, positional information and Latent Semantic Analyses to construct
word vectors for each decade of Google Books and COHA. To derive changes of
word senses, they calculate the cosine similarity of vector representations of the
same word at di erent time points. The authors show results of a case study for
semantic changes of single words, inter-decade word similarity and contrasting
word pairs in 16 experiments with mostly di erent words [
Our approach is similar to that of Mitra et al. [
Our approach can be divided into the three parts visualized in Figure 1 using
a ctitious example: (i) construction of a weighted co-occurrence graph, (ii)
extraction of word senses from a word's ego-network in the form of sense clusters,
and (iii) matching them over time to create a forest of sense trees. We separate
the corpus into n time slices Ct, which are handled as subcorpora. Similar to
Mitra et al. [
To build a weighted co-occurrence graph for time slice Ct, we need to count how often words appear in the same context in Ct. Two nouns co-occur if they are part of the same sentence and the word distance between them is nwindow. Therefore, the parameter nwindow controls the complexity of the resulting cooccurrence graph. A smaller window size results in fewer co-occurrence edges and hence in a sparser graph. Having computed the co-occurrences, we can create the graph Gt = (Vt; Et) for each time slice Ct. The sets of nodes and edges of Gt for time slice Ct are de ned as
Vt = fu 2 Ct j u is noun ^ tf(u)
tfg
Et = ffu; vg j u; v 2 Vt ^ u 6= v ^ cooc (u; v)
coocg
(1)
where tf(u) is the term frequency of u in the given time slice and cooc(u; v) is
the number of times words u and v appear within the same window. We use
the threshold parameters tf and cooc to exclude rarely occurring words, as,
depending on the window size nwindow, the number of edges in this graph would
rapidly increase. Oftentimes, a corpus has an unbalanced distribution of data
across all time slices. As a result, some have much higher raw co-occurrence
values. This especially a ects frequently occurring words with generic meanings,
such as man and time. Our initial ltering does not account for that. We use the
point-wise mutual information (PMI) [
(c) Forest of sense trees
where pmi is a threshold parameter to remove the most loosely associated words
in the given time slice.
We use G0t to extract information about word contexts in time slice Ct. We
hypothesize that the context of a word is an indicator for its senses as suggested
by Linden and hence use clustering to extract those senses [
Ebw = ffu; vg 2 Et0 j u 2 Vbw ^ v 2 Vbwg (3)
To extract di erent senses of w, we cluster the nodes of its ego-network Gbw.
In Section 4 we compare di erent clustering strategies. Each of these clustering
algorithms produces a set of p disjoint clusters Swt = fc1; : : : ; cpg from the
egonetwork of word w in time slice Ct. Following Mitra et al. [
In the last step, sense clusters are matched across time slices. We use the Jaccard similarity to compare sets of words, which are given by the clusters of word w from two neighboring time slices Ct and Ct 1. Let ci 2 Swt be a sense cluster for word w in time slice Ct. After a pairwise comparison between all sense clusters across two time slices, we use a greedy approach to iteratively match those with the highest score. However, if there is no cluster c0j 2 Swt 1 that shares any words with ci 2 Swt , it remains unmatched. In this case, it would become the root cluster of a new sense tree.
A disadvantage of this matching strategy is that a word sense might simply not occur in some time slices and thus interrupt the lineage of that word sense. This may happen with sense clusters whose words have low frequencies, such as words that appear in speci c scienti c literature. Because they cannot always be matched between neighboring time slices, we match them across a longer time span. Sense clusters in Swt are matched not only to the sense clusters in Swt 1 , but also to any other previous sense cluster in Sw1 ; : : : ; Swt 2 that remained unmatched. We call this matching strategy leaf-matching.
Sw0t 1 = Swt 1 [ c0 2 Swi j c0 not matched to any c00 2 We compare for each time slice and produce a forest of sense trees Fw = (Vw; Ew): Vw = n [ Swi ; i=1
Ew = f(c; c0) j c 2 Swi ^ c0 2 Swj ^ i < j ^ c matched c0g (5)
Fw contains sense clusters without incoming edges. These clusters are root clusters and represent the beginning of a sense tree. Given a root cluster r, the respective sense tree Fwr = (Vwr ; Ewr ) is de ned as follows:
Vwr = fc 2 Vw j 9p = ((r; c01); : : : ; (c0k; c))g Ewr = f(c; c0) 2 Ew j c; c0 2 Vwr g (6)
Such a sense tree represents a distinct sense of the word w. For example, in Figure 1c, the matched clusters make up three sense trees, referring to three di erent meanings of the word mouse.
In this section we introduce the following algorithms for the clustering step in
Section 3.2: Chinese Whispers [
Chinese Whispers is an agglomerative clustering algorithm introduced by
Biemann [
Inspecting the computed clusters, we discovered that Chinese Whispers
produces one very large sense cluster that contains nearly every word in the
egonetwork, along with very few other small sense clusters. Since the large sense
cluster contains more than one meaning, the results are not tting our use case.
Girvan-Newman is a community detection algorithm named after its authors [
Louvain is a hierarchical community detection algorithm proposed by Blondel
et al. [
The evaluation of WSI approaches is an open challenge, as there are no
standardized experimental settings or gold standards. Kutozov et al. address the need
for standardized, robust test sets of semantic shifts in their 2018 survey [
The word list compiled by Yarowsky [
In total we compiled a set of 112 words with either a single sense, multiple,
but stable senses, or words that gained at least one new sense. Each candidate
word was annotated by 15 linguists (C1 and C2 level) as \Gained an additional
sense since 1800" or \No additional sense since 1800". We measure an overall
agreement of 61% and a free-marginal Fleiss kappa of 0.42 ( xed-marginal: 0.22).
Based on a simple majority vote, 42 words gained an additional sense, whereas
70 did not. For some words, such as android, beef, or pot, we saw a high
annotator agreement over 75%. When using this as a threshold, 14 words gained an
additional sense, whereas 31 did not. The linguists where particularly undecided
on the words cat, honey, power, and state. The annotations are on our website.[
For demonstrating our proposed approach, we use the Corpus of Historical American English (COHA)3. It is one of the largest temporal corpora over one of the
Algorithm
Chinese Whispers
Girvan-Newman
Louvain
longest time ranges [
We split the corpus by decade to generate the time slices, since vastly di
erent vocabularies would result in di erent word contexts. Ideally, the vocabulary
and word distribution is relatively stable across all time slices. Since the number
of tokens increases with each decade, we measure the vocabulary overlap. In our
measurements (not shown due space constraints), neighboring decades share
2030% of their vocabulary, while the decades that are further away from each other
share only 5-15% of their vocabulary for both measures. Very high values
produced by the cosine similarity highlight that frequently occurring words appear
in most decades. We can conclude that using a frequency- and
co-occurrencebased approach to extract information about changes of word senses over time
is feasible. For a deeper statistical analysis of the corpus, we refer readers to the
work by Jatowt et al. [
For evaluation, we derive a score of how likely it is, that a word gained a new sense over time. Therefore we count the number of sense trees for a word and their distribution over time. Sense trees with a length of 1 are ignored. This count is used to rank words, such that word that gained a new sense are at the top. Using our annotated data we calculate the precision@k with k 2 f5; 10; 20g.
The following parameter settings were found by optimizing our approach on the annotated word list. We set the pointwise mutual information (PMI) threshold parameter pmi = 0:01, we used the Jaccard similarity as similarity measure, and we used leaf-matching to match sense clusters across time slices.
We compare the three graph clustering algorithms introduced in Section 3: Chinese Whispers, Girvan-Newman, and Louvain. Table 1 presents the results with these algorithms. The highest precision values are highlighted bold.
Louvain outperforms the other two algorithms at k = 5 and k = 10. GirvanNewman has a much lower precision at k = 5, but performs much better at the values 10 and 20 for k. Chinese Whispers does not perform as well. We suggest Louvain as clustering algorithm, because it ts best for our use case that a sense cluster should only represent a single meaning. diethylamide To qualitatively evaluate our approach, we take a closer look at the drill down example for the word monitor. Our approach produced ve sense trees, each of which can be matched to a single meaning of the word: hall monitor starting in the 1830s, the warship of that name starting in the 1860s (two sensetrees), monitor in the technological sense of a screen starting in the 1920s, and the surveillance sense starting in the 1960s. The time periods at which new senses emerged are accurate. For example, the warship was created in the 1860s and that is also the time slice in which we detect that sense. One weakness of the approach is that although the earliest sense tree can be interpreted easily as sense of hall monitor, a closer look reveals that the clusters are only matched by the word master. This shows that the matching can be in uenced easily by just a few words. Another weakness is that in fact two sense trees represent the meaning of warship. The later sense trees represent distinct senses of monitor : the technological sense and the surveillance sense. However, the branches of these sense trees are not separated su ciently.
Our graph representation of a text corpus can be used to visually explore linguistic features. Figure 2 shows the forest of sense trees for the word acid. Each of the boxes represents a set of words ci 2 Swt as de ned before. Each sense tree begins with a green box, the following clusters that were matched across time slices are connected by straight lines. Interestingly, we can see the discovery of DNA in the late 19th century and LSD in the 1960s. Although our approach is able to identify di erent senses of some words, there is still room for improvement: graph clustering algorithms and matching strategies, the evaluation of di erent window sizes used during the co-occurrence graph creation, and the conduction of a survey to obtain a word dataset that can be used as gold standard for evaluating temporal WSI approaches. Useful features make our approach available as an explorative tool, adjustments in the used language models to make our approach applicable to historic language, a quantitative comparison to word embeddings, veri cation of the stability of our approach, a custom slicing of time periods, sensitivity for di erently spelled variants of the same word, and detecting not only the birth of new word senses but also the death of word senses. However, our approach struggles to create well-partitioned sense clusters for di erent senses, which also a ects the matching strategies. Additionally, these strategies do not prevent sense drifting and sense trees may change their meaning signi cantly over multiple time slices. 6
We proposed an approach to identify words that gained new meanings over time. Additionally, our approach is interpretable and produces intermediate results that can be used to investigate and understand how the sense gain score for a speci c word was constructed. We presented a drill down into speci c words with two di erent visualizations that allow key components of our approach to be easily understood. It enables seeing both the created sense clusters and sense trees, and thus allows one to nd the point in time at which new senses of a word emerged.
We applied our approach to COHA, which spans 200 years and is the largest corpus of its kind. We showed anecdotal evidence for the functioning of our approach by manually annotating and evaluating 109 words. We also evaluated our approach qualitatively by using our drill down to inspect the intermediate results of the word monitor. We found that our approach was able to successfully identify word senses in sense trees.