Word sense induction (WSI) is the task of discovering senses of words without supervision (Schütze, 1998). Recent approaches include multi-sense word embeddings (MSEs), i.e. vector space models of word distribution with more vectors for ambiguous words. In MSEs, each vector is supposed to correspond to a different word sense, but in practice models frequently have different sense vectors for the same word form without an interpretable difference in meaning.

In Borbély et al. (2016), we proposed a cross-lingual method for the evaluation of sense resolution in MSEs. The method is based on the principle that words may be ambiguous to the extent to which their postulated senses translate to different words in some other language. For the translation of words, we applied the method by Mikolov et al. (2013b) who train a translation mapping from the source language embedding to the target as a least-squares regression supervised by a seed dictionary of the few thousand most frequent words. The translation of a source word vector is the nearest neighbor of its image by the mapping in the target space. In the multi-sense setting, we have translated from MSEs. (The target embedding remained single-sense.)

Section 1 discusses our linguistic motivation; and Section 2 introduces MSEs. In Section 3, we elaborate on the cross-lingual evaluation. Part of the evaluation task is to decide on empirical grounds whether different good translations of a word are synonyms or translations in different senses. Reverse nearest neighbor search, the orthogonality constraint on the translation mapping, and related techniques are also discussed. Section 4 offers experimental results with quantitative and qualitative analysis. It should be noted that our evaluation is not very strict, but rather a process of looking for something conceptually meaningful in present-day unsupervised MSE models.¹

1 Towards a less delicious inventory

We emphasize that our evaluation proposal probes an aspect of MSEs, semantic resolution, which is not well measured by the well-known word sense disambiguation (WSD) task that aims at classifying occurrences of a word form to different elements of a sense inventory pre-defined by some experts. Our goal in WSI is to probe the granularity of the inventory itself. The differentiation of word senses, as already noted in Borbély et al. (2016), is fraught with difficulties, especially when we wish to distinguish homophony, i.e. using the same written or spoken form to express different concepts, such as Russian mir ‘world’ and mir ‘peace’ from polysemy, where speakers feel that the two senses are very strongly connected, such as in Hungarian nap ‘day’ and nap ‘sun’.

The goal of WSI can be set at two levels. We may more modestly aim to distinguish homophony from polysemy. Ideally, we could even differentiate between metonymy and metaphor, two subtypes of polysemy, discussed in more detail by Veronika Lipp in the next section.

1.1 Lexicographic Background
(Veronika Lipp)

Lexical ambiguity is linguistically subdivided into two main categories: homonymy and polysemy (Cruse, 2004). Homonymous words have semantically unrelated and mutually incompatible meanings, such as punch₁ , which means ‘a blow with a fist’, and punch₂, which means ‘a drink’. Some have described such homonymous word meanings as essentially distinct words that accidentally have the same phonology (Murphy, 2002). Polysemous words, on the other hand, have semantically related or overlapping senses (Cruse, 2004; Jackendoff, 2002; Pustejovsky, 1995), such as mouth meaning both ‘organ of body’ and ‘entrance of cave’.

Two criteria have been proposed for the distinction between homonymy and polysemy. The first criterion has to do with the etymological derivation of words. Words that are historically derived from distinct lexical items are taken to be homonymous. However, the etymological criterion is not always decisive. One reason is that there are many words whose historical derivation is uncertain. Another reason is that it is not always very clear how far back we should go in tracing the history of words (Lyons, 1977).

The second criterion for the distinction between homonymy and polysemy has to do with the relatedness/unrelatedness of meaning. The distinction between homonymy and polysemy seems to correlate with the native speaker’s feeling that certain meanings are connected and that others are not. Generally, unrelatedness in meaning points to homonymy, whereas relatedness in meaning points to polysemy. However, in a large number of cases, there does not seem to be an agreement among native speakers as to whether the meanings of the words are related. So, it seems that there is not a clear dichotomy between homonymy and polysemy, but rather a continuum from ‘‘pure’’ homonymy to ‘‘pure’’ polysemy (Lyons, 1977).

Most discussions about lexical ambiguity, within theoretical and computational linguistics, concentrate on polysemy, which can be further divided into two types (Apresjan, 1974; Pustejovsky, 1995). The first type of polysemy is motivated by metaphor (irregular polysemy). In metaphorical polysemy, a relation of analogy is assumed to hold between the senses of the word. The basic sense of metaphorical polysemy is literal, whereas its secondary sense is figurative. For example, the ambiguous word eye has the literal basic sense ‘organ of the body’ and the figurative secondary sense ‘hole in a needle.’ The other type of polysemy is motivated by metonymy (regular polysemy). In metonymy, the relation that is assumed to hold between the senses of the word is that of contiguity or connectedness. In metonymic polysemy, both the basic and the secondary senses are literal. For example, the ambiguous word chicken has the literal basic sense referring to the animal and the literal secondary sense of the meat of that animal.

2 Multi-sense word embeddings

Vector-space language models with more vectors for each meaning of a word originate from Reisinger and Mooney (2010). Huang et al. (2012) trained the first neural-network-based MSE. Both works use a uniform number of clusters for all words that they select before training as potentially ambiguous. The first system with adaptive sense numbers and an effective open-source implementation is a modification of skip-gram Mikolov et al. (2013c), multi-sense skip-gram by Neelakantan et al. (2014), where new senses are introduced during training by thresholding the similarity of the present context to earlier contexts.

Bartunov et al. (2016) and Li and Jurafsky (2015) improve upon the heuristic thresholding by formulating text generation as a Dirichlet process. In AdaGram (Bartunov et al., 2016), senses may be merged as well as allocated during training. mutli-sense skip-gram² (Li and Jurafsky, 2015) applies the Chinese restaurant process formalization of the Dirichlet process. Both AdaGram and mutli have a parameter for semantics resolution (more or less senses): α and γ, respectively.

MSEs are still in the research phase: Li and Jurafsky (2015) demonstrate that, when meta-parameters are carefully controlled for, MSEs introduce a slight performance boost in semantics-related tasks (semantic similarity for words and sentences, semantic relation identification, part-of-speech tagging), but similar improvements can also be achieved by simply increasing the dimension of a single-sense embedding.

3 Linear translation from MSEs

Mikolov et al. (2013b) discovered that embeddings of different languages are so similar that a linear transformation can map vectors of the source language words to the vectors of their translations.

The method uses a seed dictionary of a few thousand words to learn translation as a linear mapping W : ℝ^d₁ →ℝ^d₂ from the source (monolingual) embedding to the target: the translation z_i ∈ℝd2 of a source word x_i ∈ℝd1 is approximately its image Wx_i by the mapping. The translation model is trained with linear regression on the seed dictionary

and can be used to collect translations for the whole vocabulary by choosing z_i to be the nearest neighbor (NN) of Wx_i. We follow Mikolov et al. (2013b) in (i) using different metrics, Euclidean distance in training and cosine similarity in collection of translations, and in (ii) training the source model with approximately three times greater dimension than that of the target embedding.

In a multi-sense embedding scenario, Borbély et al. (2016) take an MSE as the source model, and a single-sense embedding as target. The quality of the translation has been measured by training on the most frequent 5k word pairs and evaluating on another 1k seed pairs.

3.1 Reverse nearest neighbor search

A common problem when looking for nearest neighbors in high-dimensional spaces (Radovanović et al., 2010; Suzuki et al., 2013; Tomašev and Mladenic, 2013), and especially in embedding-based dictionary induction (Dinu et al., 2015; Lazaridou et al., 2015) is when there are hubs, data points (target words) returned as the NN (translation) of many points (Wxs), resulting in incorrect hits (translations) in most of the cases. Dinu et al. (2015) attack the problem with a method they call global correction. Here, instead of the original NN, which we will call forward NN search to contrast with the more sophisticated method, they first rank source words by their similarity to target words. In reverse nearest neighbor (rNN) search, source words are translated to the target words to which they have the lowest (forward) NN rank.³

In reverse NN search, we restricted the vocabulary to the some tens of thousands of the most frequent words. We introduced this restriction for memory saving, because the |V _sr|×|V _tg| similarity matrix has to be sorted column-wise for forward and row-wise for reverse ranking, so at some point of the computation we keep the whole integer matrix of forward NN ranks in memory. It turned out that the restriction makes the results better: a vocabulary cutoff of 2¹⁵ = 32768 both on the source and the target size yields slightly better results (74.3%) than the more ambitious 2¹⁶ = 65536 (73.9%). This is not the case for forward NN search, where accuracy increases with vocabulary limit (but remains far below that of reverse NN).

3.2 Orthogonal restriction and other tricks

Xing et al. (2015) note that the original linear translation method is theoretically inconsistent due to its being based on three different similarity measures: word2vec itself uses the dot-product of unnormalized vectors, the translation is trained based on Euclidean distance, and neighbors are queried based on cosine similarity. They make the framework more coherent by length-normalizing the embeddings, and restricting W to preserve vector length: their matrix W is orthogonal, i.e. the mapping is a rotation. Faruqui and Dyer (2014) achieve even better results by mapping the two embeddings to a lower-dimensional bilingual space with canonical correlation analysis. Artetxe et al. (2016) analyze elements of these two works both theoretically and empirically, and find a combination that improves upon dictionary generation and also preserves analogies (Mikolov et al., 2013d) like

among the mapped points Wx_i. They find that the orthogonality constraint is key to preserve performance in analogies, and it also improves bilingual performance. In their experiments, length normalization, when followed by centering the embeddings to 0 mean, obtains further improvements in bilingual performance without hurting monolingual performance.

4 Experiments

4.1 Data

We trained neela, AdaGram and mutli models on (original and stemmed forms of) two semi-gigaword (.7–.8 B words) Hungarian corpora, the Hungarian Webcorpus (Webkorpusz, Halácsy et al. (2004)) and (the non-social-media part of) the Hungarian National Corpus (HNC, Oravecz et al. (2014)). We used Wiktionary as our seed dictionary, extracted with wikt2dict⁴ (Ács et al., 2013). We tried several English embeddings as target, including the 300 dimensional skip-gram with negative sampling model GoogleNews released with word2vec (Mikolov et al., 2013a)⁵ , and those released with GloVe (Pennington et al., 2014)⁶ .

4.2 Orthogonal constraint

We implemented the orthogonal restriction by computing the singular value decomposition

where S_t and T_t are the matrices consisting of the embedding vectors of the training word pairs in the source and the target space respectively, and taking

where 1 is the rectangular identity matrix of appropriate shape.

Table 1 shows the effect of these factors. Precision in forward NN search follows a similar trend to that in Xing et al. (2015) and Artetxe (2016): the best combination is an orthogonal mapping between length-normalized vectors; however, centering did not help in our experiments. Reverse NNs yield much better results than the simpler method, but none of the orthogonality-related techniques give further improvement here. The cause of reverse NN’s apparent insensitivity to length may be the topic of further research.

4.3 Results

We evaluate MSE models in two ways, referred to as any and disamb. The method any has been used for tuning the (meta)parameters of the source embedding and to choose the target: a traditional, single-sense translation has been trained between the first sense vector of each word form and its translations. (If the training word is ambiguous in the seed dictionary, all translations have been included in the training data.) Exploiting the multiple sense vectors, one word can have more than one translation. During the test, a source word was accepted if any of its sense vectors had at least one good translation among its k reverse nearest neighbors (rNN@k). Table 2 shows results by the best models⁷ .

In disamb, we used the same translation matrix as in any, and inspected the translations of the different sense vectors to see whether the vectors really model different senses rather than synonyms. The lowest requirement for the non-synonymy of sense vectors s₁,s₂ is that the sets of corresponding good rNN@k translations are different. The ratio of words satisfying this requirement among all words with more than one sense vector is shown as disamb in Table 2. The values are low.

Table 3 shows the successfully disambiguated words sorted by the cosine similarity s of good rNN@1 translations of different sense vectors. (We found that most of the few cases when there are more than two sense vectors with a good rNN@1 translation are due to the fact that the seed dictionary contains some non-basic translation, e.g. kapcsolat ‘relationship, conjunction’ has ‘affair’ among its seed translations. In these cases, we chose two sense vectors arbitrarily.) Relying on s is similar to the monolingual setting of clustering the sense vectors for each word, but here we restrict our analysis to sense vectors that prove to be sensible in linear translation.

We see that most words with s < .25 are really ambiguous from a standard lexicographic point of view, but the translations with s > .35 tend to be synonyms instead.

4.4 Part of speech

The clearest case of homonymy is when unrelated senses belong to different parts of speech (POSs), and the translations reflect these POSs, e.g. nő ‘woman; increase’ or vár ‘wait; castle’.⁹ In purely semantic approaches, like 4lang (Kornai, in press; Kornai et al., 2015), POS-difference alone is not enough for analyzing a word as ambiguous, e.g. we see the only difference between the noun and participle senses of alkalmazott, ‘employee; applied’ as employment being the application of people for work; in the case of belső ‘internal; interior’, the noun refers to the part of a building described by the adjective.

More interesting are word forms with related senses in the same POS, e.g. cikk, ‘item; article’ (an article is an item in a newspaper); eredmény, ‘score; result’ (a score is a result measured by a number); magas, ‘tall; high’ (tall is used for people rather than high); or idegen, ‘strange, alien; foreign’, where the English translations are special cases of ‘unfamiliar’ (person versus language).

5 Acknowledgments

1957 was an influential year in linguistics: Harris (1957) developed the frequency-aware variant of the distributional method, Osgood et al. (1957) pioneered vector space models, and the author of a more recent conceptual meaning representation framework (Kornai, 2010, in press) was born. Fifty years later (more precisely in fall 2006) I met András during a class he taught on the book he was writing (Kornai, 2007). I heard about deep cases and karakas sooner than I did about thematic roles. He has since taught me computational linguistics and mathematical linguistics in a master and disciple fashion.

Laozi says that a good leader does not leave a footprint, and András encouraged us to be independent and effective. One of his remarkable citations is that “It’s easier to ask forgiveness than it is to get permission”. The proverb is sometimes attributed to the Jesuits, who are similar to András in having had a great impact on what I’ve become in the past ten years. The real source of the proverb is Grace Hopper, a US navy admiral who invented the first compiler. This paper is a step in my learning to be so effective as the sources mentioned above.

András Kornai, besides the work already acknowledged, rated each item in Table 3. I would like to thank the anonymous reviewer for detailed critique, both substantial and linguistic, Mátyás Lagos for reviewing language errors, and Gábor Recski and Bálint Sass for their useful comments. The orthogonal approximation was implemented following a code¹⁰ by Gábor Borbély.

References