SST-BERT at SemEval-2020 Task 1: Semantic Shift Tracing by Clustering in BERT-based Embedding Spaces

Problem Setup

Consider two corpora $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ for a same language but associated with different time stamps (say, respectively, $t_{1}$ and $t_{2}>t_{1}$). Let $\mathcal{W}$ be a set of target words occurring in both corpora. Each target word $w\in\mathcal{W}$ might assume multiple meanings, to be called senses, within the two corpora. A pool of experts annotated a representative amount of occurrences with their corresponding senses. The problem we consider is to characterize the semantic shift related to those senses from one corpus to the other without having access to the expert annotations. In particular, we address the two following two subtasks:

Subtask 1: Decide, for each $w\in\mathcal{W}$, whether or not $w$ gained or lost at least a sense between $t_{1}$ and $t_{2}$. This is a binary decision task. We will denote this subtask as (S1).

Subtask 2: Define, for the elements of $\mathcal{W}$, a measure of their degree of lexical semantic change between $t_{1}$ and $t_{2}$ and sort these elements consequently. This is a ranking task. This subtask will be referred to as (S2).

WeOur team name in SemEval2020 competition is NLP@IDSIA. describe two different methods able to address both subtasks. As both methods require a preprocessing step based on transformers, let us start from this preliminary operation.

Preprocessing

For the proposed approach, we used embeddings derived from BERT (Bidirectional Encoder Representations from Transformers) [Devlin et al., 2018] model to represent the text information in the corpora. BERT uses attention mechanism to learn the contextual relations and reads the input bidirectionally. It is an encoder-only model (as the goal is to generate a language model) opposed to transformers (encoder-decoder model)[Vaswani et al., 2017]. BERT is trained on two main objectives, masked language model (MLM) and next sentence prediction (NSP). The corpus data is initially segmented at sentence-level and the BERT Word Piece tokenizer is applied on these sentences, to get the token-level representations. BERT-base model with twelve transformer layers is used and we derived the final embedding by concatenating the final four layers. If a single word gets split by the tokenizer, we take the average embedding value of the sub-tokens. Thus, for each target word we extract the embeddings from all the sentences associated with it from both corpora, $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$. For corpora other than English language, we used multilingual BERT models of respective languages. We used the pre-trained model to generate the embeddings for all experiments, since the task is completely unsupervised in nature.

Both methods will be based on clustering algorithms used to cluster the vectors associated with a given target word of a single corpus or of the union of the two. We adopt the classical $k$-means clustering algorithm, which forms the clusters by attempting to minimize the intra-cluster variance. So called silhouette method is used for the selection of the optimal number of clusters $k$ and the initialization (i.e., the position of the centroids before starting the algorithm) [Rousseeuw, 1987]. Accordingly, given a value of $k$, we compute in the corresponding cluster, the means of both the nearest-inter cluster distance and the nearest-cluster distance. The difference between these two quantities normalized by the maximum of the two is used as a fitness score to be maximized in order to select the optimal value of $k$. The same approach is used to determine the initial centroids. In this case, we use the optimal $k$ value and run the $k$-means algorithm for $N$ iterations, to determine the best centroids.

Method 1: Joint Clustering Vectors of Both Corpora

Let us focus on a particular target word $w\in\mathcal{W}$. Accordingly, for the sake of readability, denote its vectors in corpus $\mathcal{C}_{j}$ simply as $\mathcal{X}_{j}:=\{x_{ij}\}_{i=1}^{n_{j}}$, for each $j=1,2$. We cluster the whole set of vectors of the two corpora, say $\mathcal{X}:=\mathcal{X}_{1}\cup\mathcal{X}_{2}$, and denote as $\{\mathcal{X}^{k}\}_{k=1}^{m}$ the $n$ clusters returned by the algorithm. Note that we cope with hard clustering methods, i.e., $\cup_{k=1}^{n}\mathcal{X}^{k}=\mathcal{X}$ and $\mathcal{X}^{k_{1}}\cap\mathcal{X}^{k_{2}}=\emptyset$ for each $k_{1},k_{2}=1,\ldots,m$, with $k_{1}\neq k_{2}$. For each cluster $\mathcal{X}^{k}$ we count how many of its elements belong to $\mathcal{X}_{1}$, say $n_{1,k}$, and to $\mathcal{X}_{2}$, say $n_{2,k}$. We call impure a cluster such that both $n_{1,k}>0$ and $n_{2,k}>0$. As we regard the clusters as equivalence classes for the abstract notion of sense, if all the $m$ clusters are impure it means that no new senses appeared in $\mathcal{C}_{2}$ and no new senses have been lost from $\mathcal{C}_{1}$ to $\mathcal{C}_{2}$. If this is not the case we might have new senses in $\mathcal{C}_{2}$, i.e., there is at least a $k$ such that $n_{1,k}=0$, or, vice versa, an old sense has been lost, i.e., there is at least a $k$ such that $n_{2,k}=0$. Following the guidelines of the SemEval shared task, we might set a lower bound $\underline{n}$ to the number of occurrences of a word in a cluster before deciding to regard it as a new sense. If this is the case the above conditions for the counts equal to zero should be replaced by $n_{j,k}<\underline{n}$. Overall, this procedure corresponds to a sound algorithm to address (S1). We refer to it as M1S1.

Regarding (S2), after the clustering, we might define a random variable $S$, to be called the sense variable, whose $m$ states are in one-to-one correspondence with the clusters. The variable denotes how likely is finding an occurrence of $w$ with sense $S$ in a corpus. Accordingly, we might use the counts $\{n_{j,k}\}_{k=1}^{m}$ to learn a probability mass function $P_{j}(S)$ for each $j=1,2$. Following a Bayesian approach, based on a Laplace uniform prior with equivalent sample size $\sigma>0$ [Gelman et al., 2013], we have:

In such a probabilistic setup, the semantic shift of the target word $w$ between the two corpora can be therefore described by the dissimilarity between the mass functions $P_{1}(S)$ and $P_{2}(S)$. We measure that by the Shannon-Jensen distance $SJ$, i.e., a symmetrization of the popular Kullback-Leibler divergence. This semantic shift of $w$ corresponds therefore to the distance $\delta$, with $\delta:=SJ(P_{1},P_{2})$ and $SJ(P_{1},P_{2}):=\frac{1}{2}[KL(P_{1},P_{2})+KL(P_{2},P_{1})]$ and $KL(P_{1},P_{2}):=\sum_{k=1}^{m}P_{1}(s_{k})\ln\frac{P_{1}(s_{k})}{P_{2}(s_{j})}$. Note that with the Bayesian smoothing in Equation (1), we cannot have zero probabilities and degenerate values in the computation of the distance. The overall procedure gives an algorithm to address subtask S2, as this corresponds to sort the elements of $\mathcal{W}$ with respect to their value $\delta$. We refer to this procedure as M1S2.

Method 2: Separate Clustering of the two Corpora

The optimal matching minimizing the sum of the weights can be computed in cubic time with the classical Hungarian algorithm [Kuhn, 1955, Jonker and Volgenant, 1987] and the results is a one-to-one correspondence between the clusters, no matter whether proper or dummy, of the two corpora. As a dummy cluster in a corpus has zero distance from all the clusters of the other corpus, the matching returned by the Hungarian algorithm is properly minimizing the distance between the proper clusters. Two proper clusters in the two corpora matched by the algorithm are intended as representative of the same sense. Proper clusters of a corpus pointing to dummy cluster are regarded instead as a new sense appeared in the second corpus only, or old sense occurred in the first corpus only.

After the matching, we define a single clustering with $m:=\max\{m_{1},m_{2}\}$ clusters and proceed exactly as in the previous section. In practice, the vectors of two clusters matched by the Hungarian algorithm are assigned to a single, impure, cluster, while those linked to dummy clusters produce pure clusters. We term M2S1 and M2S2 the two algorithms corresponding to the approach discussed in this section to address the two subtasks. Next section describes the experimental analysis and evaluation results.

Method 3: An alternative approach for Subtask 2 (S2)

As an alternative to the previously explained procedure for handling (S2), based on Bayesian approach and Shannon-Jensen divergence, we consider another approach, exploiting only the number of word occurrences per cluster and corpora. More precisely, assuming that we have $\mathcal{K}$ clusters in total and $\forall k\in\{1,..,\mathcal{K}\}$ already calculated $n_{1,k}$ and $n_{2,k}$ from each corpora (regardless whether clusters come from single clustering in M1 or after performing optimal cluster matching in M2), we define the coefficient of semantic change of the word (ranking in (S2) terminology), as:

where $S_{1}\!=\!\!\sum\limits_{k=1}^{\mathcal{K}}{n_{1,k}}$ and $S_{2}\!=\!\!\sum\limits_{k=1}^{\mathcal{K}}n_{2,k}$. Let us assume that word $w$ has $p$ occurrences in both corpora. It is trivial to see that in the case with $\mathcal{K}=2$ and clear cut between corpora (e.g. all occurrences in cluster 1 belong to $\mathcal{C}_{2}$ and all occurrences in cluster 2 belong to $\mathcal{C}_{1}$, i.e. $n_{2,1}\!=\!n_{1,2}\!=\!p,n_{1,1}\!=\!n_{2,2}\!=\!0$, our coefficient equals 1, which indicates complete change of sense. Likewise, if the distribution of occurrences is uniform ($n_{*,*}\!=\!p/2$), it yields 0, meaning no sense change. We denote these two new procedures for (S2) for M1 and M2 as NM1 and NM2, respectively.

Experimental Analysis

Experimental analysis is performed according to the rules posed by SemEval2020 challengehttps://competitions.codalab.org/competitions/20948#learn_the_details-overview organizers, using provided corpora (2) and baselines (3). Corpora are provided in four languages: English [Alatrash et al., 2020], Latin [McGillivray and Kilgarriff, 2013], German [Textarchiv, 2018] and Swedish [Adesam et al., 2019]. Table 1 provides brief statistics for given corpora stating the number of target words (NTW), the total and average number of sentences containing target words (NSTW) per each language. The three baselines provided are: normalized frequency difference (FD), count vectors with column intersection and cosine distance (CNT+CI+CD) and a random baseline always predicting a majority class (RND/MC) - for details see [Schlechtweg et al., 2019].

For evaluation purposes (as instructed by SemEval guidelines), accuracy is exploited for (S1), while Spearman coefficient, taking values between -1 (corresponding to negative correlation) and 1 (perfect correlation), was used for (S2). More details can be found in the system description paper [Schlechtweg et al., 2020].

It is worth mentioning that the upper bound for the number of clusters for K-means which could be retrieved by the silhouette score was set to 10.

As explained before, for (S1), the idea was to compare the number of elements of each cluster $\mathcal{X}^{k}$ coming from different corpora, say $n_{1,k}$ and $n_{2,k}$, and claim a change in senses if $\exists k\!:n_{1,k}\!=\!0\;\vee\;n_{2,k}\!=\!0$. This indeed was the procedure applied for Latin corpora. For other languages (with larger sizes of corpora), following the guidelines of the SemEval shared task, additional restrictions in terms of lower ($\underline{n}$) and upper bounds ($\bar{n}$) were set, with the following purpose: word is considered as gaining a new sense, if $\exists k\!:n_{1,k}\!\leq\!\bar{n}\;\wedge\;n_{2,k}\!\geq\!\underline{n}$ (and vice versa for losing a sense). Additionally, suggested values for these bounds were set to $\underline{n}=5$ and $\bar{n}=2$.

The codeThe source code is available at: https://github.com/vanikanjirangat/SST_BERT-SEMEVAL_TASK1 is implemented in Python using Scikit [Buitinck et al., 2013] and Transformers [Wolf et al., 2019] library.

The experimental results on the corpora over the two subtasks (S1) and (S2) are reported using the methods M1 and M2, in Table 2. Results are shown for the four target languages and overall, as well as compared with provided SemEval baselines. Best results per language and subtask are underlined. Overall best results per subtask are denoted in boldface. As can be seen, except for the Latin, the proposed methods are outperforming all baselines on (S1) with the procedure M1S1 being the best for German and Swedish and M2S1 for English. On the other hand, for (S2), results are quite corpus/language dependent, M1S2 scores best for English, M2S2 for Swedish, while baseline 2 (CNT+CI+CD) wins over all the others for Latin and German. Overall, Method 2 outperforms its competitors on both subtasks. The performance with the contextualized embeddings is actually comparable with the baseline approaches in many cases. This could be the fact that pre-trained embeddings from BERT may not be completely suitable for representing meaningful sentence vectors for clustering [Reimers and Gurevych, 2019]. These factors have to be investigated in the future.

Figure 1(a) shows an example of the application of method M1 for the English target word tip, based on 2D t-SNE [Maaten and Hinton, 2008] projections. The method produces two clusters, each denoted with a different color. As it can be seen, one of the clusters (orange, $k=1$) is remarkably larger than the other (blue, $k=2$). Additionally, it is also quite impure containing word occurrences from both corpora (more precisely, $n_{1,1}=112$ and $n_{2,1}=211$), while the other cluster contains only 31 instance whose distribution is $n_{1,2}=1$ and $n_{2,2}=30$. Given that $n_{1,2}=1\leq 2=\bar{n}$ and $n_{2,2}=30\geq 5=\underline{n}$, method M1S1 correctly detects the sense change for the word tip.

Figure 1(b) shows an example of the application of method M2 for the English target word lane (2D t-SNE projections). The clustering algorithms produce three clusters for each corpus, each denoted with a different color, and the matching algorithm detect the correspondence between clusters minimizing the distances between the centers of mass, depicted as squares in the figure. Matching clusters of the two corpora are depicted with the same color.

The results of the alternative method M3 for subtask (S2) with respect to M1 and M2 and two baselines (FD and CNT+CI+CD), are provided in Table 3. We can see that NM1 improves results on English and German languages, and overall.

Related Work

The task of identifying words whose meaning has changed over time is well-known and the related literature is, therefore, resourceful with many recent advancements. Albeit, there are still quite some issues to be resolved, primary regarding the methodology and the respective ground truth (missing semantic change annotations).

As for the latter, the first step is to decide whether to aim for a binary response (equivalent of SemEval2020 subtask 1) or to provide graded ratings of a sense change (equivalent of SemEval2020 subtask 2). Given that in both cases, but particularly with graded rating, inter-annotator agreement rates vary greatly, as evidenced in [Erk et al., 2009], establishing a definition of a standard test set is extremely difficult. In [Schlechtweg et al., 2018] a unifying evaluation framework for unsupervised lexical semantic change detection was proposed based on changes in relatedness of word use pairs in each time period.

Regarding the former, many different approaches for unsupervised lexical semantic change detection have been suggested. A detailed survey of studies can be found in [Kutuzov et al., 2018, Tahmasebi et al., 2018]. Most notably, several works [Baroni et al., 2014, Kim et al., 2014, Hamilton et al., 2016] showed the benefits of using dense word representations for semantic shift detection. Furthermore, [Kulkarni et al., 2015] showcased that these outperform the frequency-based methods. However, unlike our work, none of these works exploits clustering. More close to our approach, that is, considering clusters as representative semantic areas, are the works of [Mitra et al., 2014] and [Dubossarsky et al., 2015]. The main differences are however, that in [Mitra et al., 2014], clustering is performed on the level of the ego-network of each word, where the network is constructed based on word co-occurences, while we perform clustering of the word embeddings itself. Additionally, in contrast to [Dubossarsky et al., 2015] where the authors consider incremental learning of word embeddings in yearly chunks and vary the number of clusters from 500 to 5000, we use silhouette scores to determine the optimal number of clusters per each target word.

Conclusion and Future Work

A word can have a different meaning (sense) in different contexts and/or different time periods. Despite being quite extensively studied, the problem of identifying words that have changed their meaning over time, particularly in an unsupervised way, still challenges researchers.

In this work, we propose two approaches, both of which combine contextualized word embeddings (obtained by BERT) and clustering, differing thus only in the way the clustering has been performed. Considering obtained clusters as proxies for word meanings allows us to quantify the level of change per each target word in four target languages. The obtained results, especially looking overall, across all target languages, where we are outperforming all provided baselines, demonstrate the usefulness of the suggested approach.

As potential directions for future work we plan to investigate various strategies, including different clustering methods and time-wise comparison of target words nearest-neighbours, in an attempt to identify actual word senses more accurately. Additionally, we would like to further scrutinize how the linguistic particularities of different corpora might have contributed to the variability of the results.

References