Marianna Apidianaki Alpage
email: marianna.apidianaki@inria.fr

Unsupervised Cross-Lingual Lexical Substitution

Cross-Lingual Lexical Substitution (CLLS) is the task that aims at providing for a target word in context, several alternative substitute words in another language. The proposed sets of translations may come from external resources or be extracted from textual data. In this paper, we apply for the first time an unsupervised cross-lingual WSD method to this task. The method exploits the results of a cross-lingual word sense induction method that identifies the senses of words by clustering their translations according to their semantic similarity. We evaluate the impact of using clustering information for CLLS by applying the WSD method to the SemEval-2010 CLLS data set. Our system performs better on the 'out-of-ten' measure than the systems that participated in the SemEval task, and is ranked medium on the other measures. We analyze the results of this evaluation and discuss avenues for a better overall integration of unsupervised sense clustering in this setting.

Introduction

Lexical Substitution (LS) aims at providing alternative substitute words (or phrases) for a target word in context, a process useful for monolingual tasks such as paraphrasing and textual entailment (Mc-Carthy and Navigli, 2009). Its multilingual counterpart, Cross-Lingual Lexical Substitution (CLLS), aims at finding for a target word in context, alternative substitute words in another language. CLLS systems may assist human translators and language learners, while their output may constitute the in-put to cross-language Information Retrieval and Machine Translation (MT) systems [START_REF] Sinha | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF][START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF].

The multilingual context in which CLLS is performed permits to override some issues common to monolingual semantic processing tasks, such as the selection of an adequate sense inventory and the definition of the granularity of the semantic descriptions. In a multilingual context, word senses can be easily identified using their translations in other languages [START_REF] Resnik | Distinguishing Systems and Distinguishing Senses: New Evaluation Methods for Word Sense Disambiguation[END_REF]. Although this conception of senses presents some theoretical and practical drawbacks, it provides a standard criterion for sense delimitation which explains its wide adoption in recent works on multilingual Word Sense Disambiguation (WSD) and WSD in MT [START_REF] Carpuat | Improving Statistical Machine Translation using Word Sense Disambiguation[END_REF]Ng and Chan, 2007).

In this paper, we explain how semantic clustering may provide answers to some of the issues posed by the traditional cross-lingual sense induction approach, and how it can be efficiently exploited for CLLS. Given that existing CLLS systems rely on predefined semantic resources, we show, for the first time, that CLLS can be performed in a fully unsupervised manner. The paper is organized as follows: in the next section, we present some arguments towards unsupervised clustering for crosslingual sense induction. The clustering method used is presented in section 3. Section 4 describes the SemEval-2010 CLLS task, and section 5 presents the cross-lingual WSD method used for CLLS. In section 6, we proceed to a detailed analysis of the obtained results, before concluding with some avenues for future work.

Cross-lingual sense induction 2.1 Related work

Word sense induction (WSI) methods offer an alternative to the use of predefined semantic resources for NLP. They automatically define the senses of words from textual data and may adapt the obtained descriptions to the WSD needs of specific applications. In a monolingual context, WSI is performed by exploiting more or less refined distributional information [START_REF] Navigli | Word Sense Disambiguation: a Survey[END_REF], while in a multilingual context WSI is mostly based on translation information. In this setting, the senses of words in one language are identified by their translations in another language, usually found in a parallel corpus [START_REF] Resnik | Distinguishing Systems and Distinguishing Senses: New Evaluation Methods for Word Sense Disambiguation[END_REF].

This empirical approach to sense induction offers a standard criterion for sense delimitation and, consequently, dissociates WSD from semantic theories and predefined semantic inventories. Moreover, by establishing semantic distinctions pertinent for translation between the implicated languages, it allows to tune sense induction to the needs of multilingual applications. It has thus been widely adopted in works on multilingual WSD and WSD in MT, where senses are derived from parallel data [START_REF] Diab | Word sense disambiguation within a multilingual framework[END_REF][START_REF] Ide | Cross-lingual sense determination: Can it work?[END_REF][START_REF] Ide | Sense discrimination with parallel corpora[END_REF][START_REF] Hwee | Exploiting Parallel Texts for Word Sense Disambiguation: An Empirical Study[END_REF]Chan et al., 2007;[START_REF] Carpuat | Improving Statistical Machine Translation using Word Sense Disambiguation[END_REF]. By linking WSD and its evaluation to translation, this hypothesis also offers a solution to the problem of non-conformity of monolingual WSD methods in this setting.

Nevertheless, the assumption of biunivocal ('oneto-one') correspondences between senses and translations is rather simplistic. One word sense may be translated by different synonymous words in another language, whose relatedness should be considered during sense induction. Furthermore, this approach does not permit to account for cases of parallel ambiguities [START_REF] Resnik | WSD in NLP applications[END_REF], and cases where the senses of a word share some of their translations [START_REF] Sinha | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF]. Additional problems arise at the practical level as the induced senses are uniform and, so, the constraints used during WSD for selecting between close and distant senses are similar. Furthermore, when WSD coincides with lexical selection in MT, the selection of a translation different from the reference is considered as wrong even if it is semantically correct. So, this conception of senses does not per-mit to penalize WSD errors relatively to their importance [START_REF] Resnik | Distinguishing Systems and Distinguishing Senses: New Evaluation Methods for Word Sense Disambiguation[END_REF], unless semantic resources are used to identify semantic correspondences.

Cross-lingual sense clustering

Instead of using translations as straightforward sense indicators, it is possible to perform a more thorough semantic analysis during cross-lingual WSI by combining distributional and translation information. The sense clustering method proposed by [START_REF] Apidianaki | Translation-oriented sense induction based on parallel corpora[END_REF] identifies complex semantic relations between word senses and their translations. The method is based on the contextual hypotheses of meaning and of semantic similarity [START_REF] Harris | Distributional structure[END_REF][START_REF] Miller | Contextual correlates of semantic similarity[END_REF], which underlie monolingual WSI methods, and is combined to the assumption of a semantic correspondence between words and their translations in real texts [START_REF] Chesterman | Contrastive Functional Analysis[END_REF]. Following these hypotheses, information coming from the source contexts of a target word when translated with a precise translation in a parallel corpus, is used to reveal the senses carried by the translation. Furthermore, the similarity of the source contexts reveals the semantic relatedness of the translations.

This cross-lingual WSI method groups the semantically similar translations of ambiguous words into clusters that serve to describe their senses instead of the individual translations. For instance, the traditional cross-lingual WSI approach would propose three senses for the English noun coach, corresponding to each of its Spanish translations: entrenador, autocar and autobús. 1 However, this solution is not sound given that the translations autocar and autobús are semantically related and do not lexicalize distinct senses of the English word, as is the case with entrenador. Sense clustering permits to estimate the semantic similarity of the translations and to not consider synonymous translations as indicators of distinct senses. Consequently, the English word coach has two senses after sense clustering: one described by the cluster {autocar, autobús} (the "bus" sense) and one described by the cluster {entrenador} (the "trainer" sense). In the automat-ically built bilingual inventories, the senses of the words in one language are thus described by clusters of their translations in another language.

Applications

This type of sense clustering has proved to be useful in various application settings. When exploited in cross-lingual WSD, it permits to assign 'sensetags' containing several semantically correct translations to new instances of words in context [START_REF] Apidianaki | Data-driven Semantic Analysis for Multilingual WSD and Lexical Selection in Translation[END_REF]. Moreover, the use of clustering information during evaluation allows for a differing penalization of WSD errors. In an MT evaluation setting, sense clusters have been integrated into an MT evaluation metric (METEOR) [START_REF] Lavie | METEOR: An Automatic Metric for MT Evaluation with High Levels of Correlation with Human Judgments[END_REF]) and brought about an increase of the metric's correlation with human judgments of translation quality in different languages [START_REF] Apidianaki | An algorithm for cross-lingual sense clustering tested in a MT evaluation setting[END_REF]. The use of sense clusters in this setting permits to identify semantic correspondences between translations and hypotheses, and to circumvent the strict requirement for exact surface correspondences, one of the main critics addressed to MT evaluation metrics. The same notion of sense clusters has been adopted in the most recent SemEval Cross-Lingual WSD task [START_REF] Lefever | SemEval-2010 Task 3: Cross-lingual Word Sense Disambiguation[END_REF]. Instead of considering translations as indicators of distinct senses, as was the case in previous tasks, the senses of a small number of ambiguous words were described by manually created clusters of translations.

We consider that the sense cluster inventories created by the unsupervised WSI method proposed by [START_REF] Apidianaki | Translation-oriented sense induction based on parallel corpora[END_REF] would be useful in other applicative contexts as well and, especially, in CLLS. In unsupervised cross-lingual WSD, the clusters constitute the candidate senses from which one has to be selected for each new instance of the words in context. So, when an instance of a word is disambiguated, a cluster of semantically related translations is selected on the basis of the source context describing its sense. This is exactly the goal of CLLS, as described in the relevant task set up in SemEval-2010, where the systems had to provide for instances of words in context, several possible translations in another language [START_REF] Sinha | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF][START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF]. It seems thus that CLLS constitutes a suitable field for exploiting this sense clus-tering method and, in what follows, we will try to evaluate this assumption.

Unsupervised clustering for sense induction

Bilingual lexicons

The SemEval-2010 CLLS task concerned the pair of languages English (EN) -Spanish (SP). In order to apply our cross-lingual WSD method to the data of the SemEval-2010 CLLS task, an EN-SP sense cluster inventory had first to be built where the senses of English words would be described by clusters of their Spanish translations. The training corpus used for building the sense cluster inventory is the SP-EN part of Europarl (release v5), which contains 1,689,850 aligned sentence pairs [START_REF] Koehn | Europarl: A Parallel Corpus for Statistical Machine Translation[END_REF]. Before clustering, some preprocessing steps are performed. First, the corpus is lemmatized and tagged by POS [START_REF] Schmid | Probabilistic Part-of-Speech Tagging Using Decision Trees[END_REF]. Then sentence pairs presenting a great difference in length (i.e cases where one sentence is three times longer than the other) are eliminated and the corpus is aligned at the level of word types using Giza++ [START_REF] Franz | A Systematic Comparison of Various Statistical Alignment Models[END_REF]. Two bilingual lexicons of content words are built from the alignment results, one for each translation direction (EN-SP/SP-EN). In the entries of these lexicons, source words are associated with the translations to which they are aligned. As these lexicons are automatically created, they contain some noise mainly due to spurious word alignments. In order to eliminate erroneous translation correspondences, we first apply a filter which discards translations with a probability below 0.001 (according to the scores assigned during word alignment). Then an intersection filter is applied which discards correspondences not found in lexicons of both directions. Finally, the two lexicons are filtered by POS, keeping for each w only its translations that pertain to the same POS category. 2 The translations of a word (w) used for clustering are the ones that translate w at least 20 times in the training corpus. This frequency threshold leaves out some translations of the source words but has a double merit: it eliminates erroneous translations and reduces data sparseness issues which pose problems in distributional semantic analysis.

Clustering based on semantic similarity

The semantic clustering is performed in the target language by using source language feature vectors. Each translation of a word w is characterized by a vector built from the content words that cooccur with w whenever it is translated by this word in the aligned sentences of the training corpus. 3 The vector similarity is calculated using a variation of the Weighted Jaccard measure [START_REF] Grefenstette | Explorations in Automatic Thesaurus Discovery[END_REF] which weighs each source context feature according to its relevance for the estimation of the translations similarity.

The input of the similarity calculation consists of the frequency lists of w's translations. The score assigned to a pair of translations indicates their degree of similarity. Each feature (j) gets a total weight (tw) relatively to a translation (i), which corresponds to the product of its global (gw) and its local weight (lw) with this translation. The gw is based on the dispersion of j in the contexts of w, and on its frequency of cooccurrence (cooc freq) with w when translated by each i (cf. formula 1). So, it depends on the number of translations with which j is related (nrels) and on its probability of cooccurrence with each one of them (cf. formula 2). The local weight (lw) between j and i depends on their frequency of cooccurrence (cf. formula 3).

gw(j) = 1 -i p ij log(p ij ) nrels (1)
p ij = cooc freq of j with i |js| for i (2) lw(j, i) = log(cooc freq of j with i) (3)
The Weighted Jaccard (WJ) coefficient of two translations m and n is given by formula 4.

WJ(m, n) = j min(tw(m, j)tw(n, j)) j max(tw(m, j)tw(n, j)) (4)
The pairwise similarity of the translations is thus estimated by comparing the corresponding weighted source feature vectors. A similarity score is assigned to each pair of translations and stored in a table that is being looked up by the clustering algorithm. The pertinence of the relation of each translation pair is estimated by comparing its score to a threshold defined locally for each w by the following iterative procedure.

1. The initial threshold (T) corresponds to the mean of the scores (above 0) of the translation pairs of w.

2. The set of translations is segmented into pairs whose score exceeds the threshold and pairs whose score is inferior to the threshold, creating two sets (G1, G2).

3. The average of each set is computed (m1 = average value of G1, m2 = average value of G2).

4. A new threshold is created that is the average of m1 and m2 (T = (m1 + m2)/2).

5. Go back to step 2, now using the new threshold computed in step 4, keep repeating until convergence has been reached.

The clustering algorithm groups the translations by exploiting the similarity calculation results. The condition for a translation to be included in a cluster is to have pertinent relations with all the elements already in the cluster. The clustering stops when all the translations of w are included in some cluster and all their relations have been checked. All the elements of the final clusters are linked to each other by pertinent relations. The translations not having any strong relations to other translations are included in separate one-element clusters.

The EN-SP sense cluster inventory

In the obtained semantic inventory, the senses of each English word are described by clusters of its semantically similar translations in Spanish. 4 third column of the table gives the number of Spanish words (SP Ts) translating more than 20 occurrences of the English words in the corpus and retained for clustering. This threshold ensures that the words being clustered are good translations of the English words. The fourth column of the table shows the number of English word occurrences translated by the retained translations.

As is shown in these examples, the translations of the English words are not considered as straightforward indicators of their senses but are grouped into clusters describing senses. For instance, the word drop, which is translated by ten different words into Spanish (disminuir, reducir, bajar, caer, descender, retirar, dejar, abandonar, lanzar) is not considered as having ten distinct senses but four, described by each cluster of translations: {disminuir, reducir, bajar, caer, descender}: "decrease, reduce", {retirar}: "remove, withdraw", {dejar, abandonar}: "leave, abandon" and {lanzar}: "launch". The obtained clusters group semantically similar words which would be erroneously considered as indicators of distinct senses by the traditional cross-lingual sense induction method.

Another important point is that this algorithm performs a soft clustering, highly adequate in this setting. Given that the generated clusters describe senses, their overlaps describe the relations between the corresponding senses. For instance, the two senses of the word test described by the clusters {experimentación, control, análisis, exper-imento} and {experimento, control, análisis, exa-men} share three elements and are closer than those described by {experimentación, control, análisis, experimento} and {evaluación}, which have no element in common. The first two senses could also be considered as nuances of a coarser sense ("examination / analysis") that could be obtained by merging the overlapping clusters. Capturing inter-sense relations is important in lexical semantics and numerous works have been criticized for just enumerating word senses without describing their relations. Discovering these links automatically, as is done with this sense clustering method, permits to account for differences in the status of senses during WSD and its evaluation. It also offers the possibility to automatically modify the granularity of the obtained senses according to the WSD needs of the applications. Moreover, when the sense cluster inventory is used for cross-lingual WSD, it allows to capture subtle relations between word usages in cases where the senses of a word share some of their translations but not all of them, an issue highlighted in the Se-mEval CLLS task [START_REF] Sinha | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF] which will be presented in the next section.

The SemEval-2010 CLLS task

In the SemEval-2010 Cross-Lingual Lexical Substitution task, annotators and systems had to provide several alternative correct translations in Spanish for English target words in context. Given a paragraph containing an instance of an English target word, the annotators had to find as many good substitute translations as possible for that word in Spanish. Unlike a full-blown MT task, CLLS targets one word at a time rather than an entire sentence. So, annotators were asked to translate the target word and not entire sentences. Moreover, they were asked to supply, for each instance, as many translations as they felt were valid and not just one translation, which would be the case in MT.

The task of the participating systems was then to predict the translations provided by the annotators for each target word instance. By analyzing the context of the English target word instances, the systems had to provide for each instance, several correct Spanish translations which should fit the given source language context. The set of target words in the SemEval CLLS task is composed of Nouns, Verbs, Adjectives and Adverbs exhibiting a wide variety of substitutes. The annotators were allowed to use any resources they wanted to in order to supply substitutes for instances of the English target words. So, instances of the target words in context were tagged by sets of Spanish translations. 5 The interannotator agreement for this task was calculated as pairwise agreement between sets of substitutes from annotators and corresponds to 0.2777.

The sets of translations provided for different instances of a target word could overlap in different degrees, depending on the meaning of the instances. These overlaps reveal subtle relations between word usages in cases where they share some of their translations but not all of them [START_REF] Sinha | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF]. This also shows the absence of clear divisions between usages and senses: usages overlap to different extents without having identical translations. Although no clustering of translations from a specific resource into senses was performed for this task, the interest of examining the possibility of clustering the transla-

Cross-lingual WSD

The source language features that revealed the similarity of the translations and served to their clustering (cf. section 3) can be exploited by an unsupervised WSD classifier [START_REF] Apidianaki | Data-driven Semantic Analysis for Multilingual WSD and Lexical Selection in Translation[END_REF]. In order to disambiguate a new instance of an English word w, cooccurrence information coming from its context is compared to these feature sets and the cluster that has the highest similarity with the new context is selected. We adopt this WSD method in order to exploit the sense clustering results and perform CLLS in an unsupervised manner. Instead of comparing the new contexts to the features that are common to all the translations in a cluster (i.e. the intersection of their source language features), as is done in the initial method, we compare them to the features shared by each pair of translations. This increases the coverage of the method, given that these source features sets are larger than the ones containing the intersection of the features of all the clustered translations. As the training corpus was lemmatized and POS-tagged prior to building the feature vectors (only content word cooccurrences were retained), the new contexts have to be lemmatized and POS-tagged as well.

If common features (CFs) are found between the new context and a translation pair, a score is assigned to this 'context-pair' association which corresponds to the mean of the weights of the CFs relatively to each translation of the pair. The weights used here are the total weights (tws) that were assigned to the context features relatively to the translations during the semantic similarity calculation (cf. section 3.2). In formula 5, i is equal to 2 (i.e. the number of translations in the pair) and j is the number of CFs between the translation pair and the new context.

If the highest-ranked translation pair is found in just one sense cluster, this cluster is selected as describing the sense of the new instance. Otherwise, if the translation pair is found in different clusters, it is checked whether the CFs characterize the other translations in these clusters (or some of them). If this is the case, a score is assigned to each cluster junta directiva 2;consejo 2;mesa directiva 1;junta 1;junta de ayuda 1;directiva 1;comite 1;comision 1; drop.v 1288 bajar;disminuir;reducir;caer;descender dejar caer 2;tirar 1;arrojar 1;lanzar 1;soltar 1;dejar 1;bajar 1; check.v 851 comprobar;controlar;verificar; verificar 3;checar 2;confirmar 1;anotar 1;rectificar 1;revisar 1;comprobar 1; yet.r 1766 todavía;aún;sin embargo; sin embargo 2;pero 2;no obstante 1;aun 1;todavia 1; now.r 1019 hoy;aquí;actualmente;ahora bien; hoy 2;ahora 2;este momento 2;a partir 1;el presente 1;de aqui 1;

Table 2: Clusters suggested by the WSD method.

depending on the weights of the features with the other translations, and the cluster with the highest score is selected as describing the sense of the new instance. The score is again calculated by formula 5 but this time i is equal to the number of translations in the cluster having CFs with the new context.

score = i j tw(i, j) i * j (5)
If no CFs are found using the translation pairs, the WSD algorithm considers each translation's feature set separately (which is naturally larger than the feature sets of the translation pairs). If CFs exist, the translation with the highest score is selected as well as the cluster containing it. If the translation is found in the intersection of different clusters, it is checked whether the CFs characterize some of the other translations found in the clusters. If this is the case, a score is assigned to the clusters depending on the weights of the features with the translations and the cluster with the highest score is selected. The cluster containing the translation pair with the highest similarity to the new context is retained as the sense of the new instance. If no CFs are found in this way neither, a most frequent sense heuristic is used which selects the most frequent cluster (i.e. the one assigned to most of the new instances of w).

For the 1000 test instances in the SemEval CLLS task, the WSD method proposes 625 clusters with more than one element and 118 one element clusters. 6 The most frequent translation is suggested in 210 cases while the most frequent cluster is chosen in 43 cases. A cluster is chosen randomly only in 3 cases. In Table 2, we present some suggestions made by the WSD method for target words of different POS (n: nouns, v: verbs, a: adjectives, r: adverbs) and the corresponding gold standard (GS) annotations. For instance, the following occurrence of the English noun test:

Entries typically identify the age or school grade levels for which the test is appropriate, as well as any subtests.

is tagged by the Spanish cluster {prueba, examen, ensayo} during WSD, which is close to the GS annotation {examen, prueba, test} and correctly describes its sense.

The first translation provided in the results is the word of the cluster that translates most of the English target word instances in the corpus (and which is duplicated in order to be reinforced during the 'out-of-ten' evaluation, as we will explain in the next section). We observe that this most frequent word, although it is a correct translation (i.e. found in the GS annotations), does not coincide with the annotators' first choice. This explains the evaluation results that we present in the next section.

It is also important to note that the system suggests not only translations that have been proposed by the annotators, but also other semantically pertinent translations that were found in the training corpus and which do not exist in the GS annotations. This is the case, for instance, with the translation than ten elements; 23 clusters with ten elements and 22 clusters with more than ten elements.

"controlar" of the verb check and the translation "ensayo" proposed for the noun test. This shows that the suggestions made by the WSD method greatly depend on the corpus used for training.

Evaluation

The setting

We evaluate our method on the SemEval-2010 CLLS task test set. The metrics used for evaluation are the best and out-of-ten (oot) precision (P) and recall (R) scores. In the SemEval task, the systems were allowed to supply as many translations as they felt fit the context. These suggestions were then given credit depending on the number of annotators that had picked each translation. The credit was divided by the number of annotator responses for the item. For the best score, the credit for the system answers for an item was also divided by the number of answers provided by the system, which allows more credit to be given to instances with less variation.

The oot scorer allows up to ten system responses and does not divide the credit attributed to each answer by the number of system responses. This scorer allows duplicates which means that systems can get inflated scores (i.e. > 100), as the credit for each item is not divided by the number of substitutes and the frequency of each annotator response is used. Allowing duplicates permits that the systems boost their scores with duplicates on translations with higher probability. 7Two baselines are used for evaluation: a dictionary-based one (DICT), which contains the Spanish translations of all target words provided by an SP-EN dictionary, and a dictionary and corpusbased one (DICTCORP), where the translations provided by the dictionary for a given target word are ranked according to their frequencies in the Spanish Wikipedia. In DICT, the best baseline is produced by taking the first translation provided by the dictionary while the oot baseline considers the first ten translations.

Results

In order to evaluate our WSD method, we proceed as follows. If the cluster selected by the WSD method contains ten translations (or more), all the translations are given in the oot results. Otherwise, the translations found in the cluster are proposed and the most frequent translation is duplicated till reaching ten elements. For best, we always retain the most frequent translation of the selected cluster.

Our intuition was that the WSD method, which assigns sense clusters (i.e. sets of semantically similar and, more or less, substitutable translations), would fit and perform well on the oot subtask of the SemEval CLLS task. This is confirmed by the results presented in Table 3. 8 Our method (denoted by 'WSD' in the table) outperforms the 14 systems that participated in the CLLS task as well as the recall (R) and precision (P) baselines. It is important to note that, contrary to our method which is totally unsupervised, all the systems that participated in the SemEval-2010 task used predefined resources. The second ranked system (SWAT-E), for instance, performs lexical substitution in English and then translates each substitute into Spanish using two predefined bilingual dictionaries, while SWAT-S does the inverse, performing lexical substitution in the translated text [START_REF] Wicentowski | SWAT: Cross-Lingual Lexical Substitution using Local Context Matching, Bilingual Dictionaries and Machine Translation[END_REF]. Another interesting point is that the sense cluster inventory used by the cross-lingual WSD method is derived from Europarl, which is the European Parliament Proceedings parallel corpus [START_REF] Koehn | Europarl: A Parallel Corpus for Statistical Machine Translation[END_REF]. Despite this fact, the WSD method that exploits this inventory performs particularly well on this task which concerns the semantic analysis and translation of words of general language. We would thus expect the results to be even better if the sense induc-tion and the WSD method were trained on a bigger, or more general, parallel corpus.

Systems

The mode recall and precision (Mode R and Mode P) metrics evaluate the performance of the systems in predicting the translation that was most frequently selected by the annotators, provided that such a translation extists. To identify the most frequent response, we order the system responses according to their frequency as translations of the target words in the training corpus. The relatively low scores obtained for the Mode R and Mode P metrics (compared to R and P) are explained by the fact that the most frequent translation in the training corpus does not always correspond to the translation that was most frequently selected by the annotators, although it may be a good translation for the target word.

The same reason explains the weaker performance of the method in the best evaluation subtask (cf. Table 4), where our system is ranked eighth compared to the 14 systems that participated in the task. 9 Here too, the best translation according to the annotators does not correspond to the most frequent translation in the corpus. This highlights the impact that the relevance of the training corpus to the domains of the processed texts has on unsupervised CLLS. Another important factor that has to be taken into account is that the WSD method that we use is oriented towards multilingual applications (more precisely MT). In these applications, it is possible to filter the proposed sense clusters by reference to the 9 We report some indicative results from the best subtask. The full table of results can be found in [START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF]. target language context (for instance, by using a language model) in order to retain the most adequate translation. It is interesting to note that the systems that perform better in the best subtask get relatively low results in the oot subtask, and the inverse. This is the case, for instance, for UBA-T (Basile and Semeraro, 2010), while [START_REF] Aziz | USPwlv and WLVusp: Combining Dictionaries and Contextual Information for Cross-Lingual Lexical Substitution[END_REF] clearly specify that their main goal is to maximize the accuracy of their system (USPwlv) in choosing the best translation. A conclusion that can be drawn is that each subtask has different requirements, which may be satisfied by different types of methods.

Systems

In order to investigate other possible reasons behind the different behavior of the WSD method in the two evaluation subtasks, we performed the evaluation separately for each POS. The results are presented in Tables 5 and6. In both the oot and best evaluation subtasks, the best scores are obtained for adjectives. Especially in the best subtask, where the method seemed to perform worse than the other systems, the recall and precision scores obtained for adjectives (with and without mode) are higher than those obtained by the highest-ranked system (cf. Table 4) and much higher than the baselines. A more detailed look at the obtained results proved that the most frequent translation of the English adjectives in our training corpusproposed in the best evaluation subtask and emphasized in the oot subtask -is often the most frequent translation proposed by the annotators. This is not the case for the other POS, where the most frequent translation in the corpus often does not correspond to the annotators' first choice. Furthermore, the translation proposed by the system is not the same as the most frequent translation of the word in the general dictionary and the Spanish Wikipedia which were used, respectively, for the DICT and DICT-CORP baselines. Consequently, this issue could probably be resolved if a more balanced corpus was used for training the WSI and WSD methods.

Conclusions and future work

We have shown that Cross-Lingual Lexical Substitution can be performed in a totally unsupervised manner, if a parallel corpus is available. We applied an unsupervised cross-lingual WSD method based on semantic clustering to the SemEval-2010 CLLS task. The method performs well compared to the systems that participated in the task, which exploit predefined lexico-semantic resources. It is ranked first on the out-of-ten measure and medium on measures that concern the choice of the best translation. We wish to pursue this work and explore other ways for selecting best translations than solely relying on frequency information. As unsupervised methods heavily rely on the training data, it would also be interesting to experiment with different corpora in order to evaluate the impact of the type and the size of the corpus on CLLS.

The sense clusters assigned to target word instances during CLLS contain semantically similar translations of these words, more or less substitutable in the target language context. We consider that it would be interesting to integrate target language information in the CLLS decision process for selecting best translations. Given that MT is one of the envisaged applications for this type of task, but the use of a full-blown MT system would probably mask system capabilities at a lexical level, a possibility would be to exploit the CLLS system suggestions in a simplified MT task such as word translation [START_REF] Vickrey | Word-Sense Disambiguation for Machine Translation[END_REF] or lexical selection [START_REF] Apidianaki | Data-driven Semantic Analysis for Multilingual WSD and Lexical Selection in Translation[END_REF], or in an MT evaluation context. This would permit to estimate the usefulness of the system suggestions in a specific application setting.

Table 1 :

 1 Some entries from the EN-SP sense cluster inventory are presented in Table1. We provide examples for words of different POS (nouns, verbs, adjectives and adverbs) and with varying degrees of polysemy. The actualmente, hoy, ahora bien} {actualmente, ahora, hoy} {entretanto, aquí, ahora bien} {de momento}, {adelante}, {por ahora, en-tretanto} Entries from the EN-SP sense cluster inventory.

	POS	EN word # SP Ts # occ	Sense clusters
	Nouns	coach	3	265	{entrenador}{autocar, autobús} {prueba, ensayo, examen} {experimento, análisis, examen, ensayo}
		test	11	3162	{evaluación} {comprobación} {experimentación, ensayo, análisis, ex-perimento} {inspección} {experimento, control, análisis, examen}
					{experimentación, control, análisis, experimento} {criterio}
	Verbs	drop	10	390	{disminuir, reducir, bajar, caer, descender} {retirar} {dejar, abandonar} {lanzar}
		check	5	1343	{examinar} {revisar} {controlar, verificar, comprobar}
	Adjs	heavy	7	448	{elevado, fuerte, grave, grande}{elevado, enorme}{grave, duro, fuerte, grande} {grave, alto, elevado}
		open	6	6286	{público, libre, transparente} {público, franco, transparente} {abierto} {sincero, franco}
	Advs	around	5	742	{alrededores}{casi, aproximadamente, cerca}{menos} {aquí,
		now	9	33662

Table 3 :

 3 oot results (%)

		R	P	Mode R Mode P
	WSD	180.10 186.25	56.52	58.44
	SWAT-E	174.59 174.59	66.94	66.94
	SWAT-S	97.98	97.98	79.01	79.01
	UvT-v	58.91	58.91	62.96	62.96
	UvT-g	55.29	55.29	73.94	73.94
	DICT	44.04	44.04	73.53	73.53
	DICTCORP	42.65	42.65	71.60	71.60

Table 5 :

 5 oot results for different POS (%)

	POS	R	P	Mode R Mode P
	Adjs	287.94 296.41	72.44	74.43
	Nouns 127.01 141.65	37.78	42.29
	Verbs	115.94 121.43	53.17	55.90
	Advs	111.46 111.46	65.15	65.15
	POS	R	P	Mode R Mode P
	Adjs	30.77 31.00	63.56	64.13
	Nouns 14.61 16.29	25.78	28.86
	Verbs	14.98 14.98	29.76	29.76
	Advs	13.07 13.07	37.88	37.88

Table 6 :

 6 best results for different POS (%)

This set of translations was extracted from the word aligned Europarl corpus(Koehn,

2005) after applying a set of filters that will be described in section 3.

For instance, for English nouns we retain their noun translations in Spanish; for verbs, we keep verbs, etc.

We use a stoplist of English function words (conjunctions, prepositions and articles) that may be erroneously tagged as content words.

The inventory contains entries for all English content words in the corpus. Here, we focus on the target words used in the CLLS task.

The average numbers of substitutes provided by the annotators for words of different POS are: 4.47 for nouns, 5.2 for verbs, 4.99 for adjectives and 4.77 for adverbs. tions provided by the annotators is highlighted[START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF].

262 clusters with two elements; 157 clusters with three;

with four; 64 with five; 69 clusters with more than five and less

The metrics used for evaluation are defined in[START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF].

We report the results obtained by the highest-ranked systems in the SemEval-2010 CLLS task. The full table of results can be found in[START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF].


Tim Van De Cruys

Marianna Apidianaki
email: marianna.apidianaki@inria.fr

Latent Semantic Word Sense Induction and Disambiguation

In this paper, we present a unified model for the automatic induction of word senses from text, and the subsequent disambiguation of particular word instances using the automatically extracted sense inventory. The induction step and the disambiguation step are based on the same principle: words and contexts are mapped to a limited number of topical dimensions in a latent semantic word space. The intuition is that a particular sense is associated with a particular topic, so that different senses can be discriminated through their association with particular topical dimensions; in a similar vein, a particular instance of a word can be disambiguated by determining its most important topical dimensions. The model is evaluated on the SEMEVAL-2010 word sense induction and disambiguation task, on which it reaches stateof-the-art results.

Introduction

Word sense induction (WSI) is the task of automatically identifying the senses of words in texts, without the need for handcrafted resources or manually annotated data. The manual construction of a sense inventory is a tedious and time-consuming job, and the result is highly dependent on the annotators and the domain at hand. By applying an automatic procedure, we are able to only extract the senses that are objectively present in a particular corpus, and it allows for the sense inventory to be straightforwardly adapted to a new domain.

Word sense disambiguation (WSD), on the other hand, is the closely related task of assigning a sense label to a particular instance of a word in context, using an existing sense inventory. The bulk of WSD algorithms up till now use pre-defined sense inventories (such as WordNet) that often contain finegrained sense distinctions, which poses serious problems for computational semantic processing [START_REF] Ide | Making Sense About Sense[END_REF]. Moreover, most WSD algorithms take a supervised approach, which requires a significant amount of manually annotated training data.

The model presented here induces the senses of words in a fully unsupervised way, and subsequently uses the induced sense inventory for the unsupervised disambiguation of particular occurrences of words. The induction step and the disambiguation step are based on the same principle: words and contexts are mapped to a limited number of topical dimensions in a latent semantic word space. The key idea is that the model combines tight, synonymlike similarity (based on dependency relations) with broad, topical similarity (based on a large 'bag of words' context window). The intuition in this is that the dependency features can be disambiguated by the topical dimensions found by the broad contextual features; in a similar vein, a particular instance of a word can be disambiguated by determining its most important topical dimensions (based on the instance's context words).

The paper is organized as follows. Section 2 presents some previous research on distributional similarity and word sense induction. Section 3 gives an overview of our method for word sense induction and disambiguation. Section 4 provides a quantitative evaluation and comparison to other algorithms in the framework of the SEMEVAL-2010 word sense induction and disambiguation (WSI/WSD) task. The last section draws conclusions, and lays out a number of future research directions.

Previous Work

Distributional similarity

According to the distributional hypothesis of meaning [START_REF] Zellig | Distributional structure[END_REF], words that occur in similar contexts tend to be semantically similar. In the spirit of this by now well-known adage, numerous algorithms have sprouted up that try to capture the semantics of words by looking at their distribution in texts, and comparing those distributions in a vector space model.

One of the best known models in this respect is latent semantic analysis -LSA [START_REF] Landauer | A solution to Plato's problem: The Latent Semantic Analysis theory of the acquisition, induction, and representation of knowledge[END_REF][START_REF] Landauer | An Introduction to Latent Semantic Analysis[END_REF]. In LSA, a termdocument matrix is created, that contains the frequency of each word in a particular document. This matrix is then decomposed into three other matrices with a mathematical factorization technique called singular value decomposition (SVD). The most important dimensions that come out of the SVD are said to represent latent semantic dimensions, according to which nouns and documents can be represented more efficiently. Our model also applies a factorization technique (albeit a different one) in order to find a reduced semantic space.

Context is a determining factor in the nature of the semantic similarity that is induced. A broad context window (e.g. a paragraph or document) yields broad, topical similarity, whereas a small context yields tight, synonym-like similarity. This has lead a number of researchers to use the dependency relations that a particular word takes part in as contextual features. One of the most important approaches is [START_REF] Lin | Automatic Retrieval and Clustering of Similar Words[END_REF]. An overview of dependency-based semantic space models is given in [START_REF] Padó | Dependencybased construction of semantic space models[END_REF].

Word sense induction

The following paragraphs provide a succinct overview of word sense induction research. A thorough survey on word sense disambiguation (including unsupervised induction algorithms) is presented in [START_REF] Navigli | Word Sense Disambiguation: a Survey[END_REF].

Algorithms for word sense induction can roughly be divided into local and global ones. Local WSI algorithms extract the different senses of a word on a per-word basis, i.e. the different senses for each word are determined separately. They can be further subdivided into context-clustering algorithms and graph-based algorithms. In the context-clustering approach, context vectors are created for the different instances of a particular word, and those contexts are grouped into a number of clusters, representing the different senses of the word. The context vectors may be represented as first or secondorder co-occurrences (i.e. the contexts of the target word are similar if the words they in turn co-occur with are similar). The first one to propose this idea of context-group discrimination was Schütze (1998), and many researchers followed a similar approach to sense induction [START_REF] Purandare | Word Sense Discrimination by Clustering Contexts in Vector and Similarity Spaces[END_REF]).

In the graph-based approach, on the other hand, a co-occurrence graph is created, in which nodes represent words, and edges connect words that appear in the same context (dependency relation or context window). The senses of a word may then be discovered using graph clustering techniques [START_REF] Widdows | A Graph Model for Unsupervised Lexical Acquisition[END_REF], the HyperLex algorithm [START_REF] Véronis | Hyperlex: lexical cartography for information retrieval[END_REF], or Pagerank algorithm [START_REF] Agirre | Two graph-based algorithms for state-of-the-art WSD[END_REF]. Finally, [START_REF] Bordag | Word sense induction: Tripletbased clustering and automatic evaluation[END_REF] recently proposed an approach that uses word triplets to perform word sense induction. The underlying idea is the 'one sense per collocation' assumption, and cooccurrence triplets are clustered based on the words they have in common.

Global algorithms take an approach in which the different senses of a particular word are determined by comparing them to, and demarcating them from, the senses of other words in a full-blown word space model. The best known global approach is the one by [START_REF] Pantel | Discovering word senses from text[END_REF]. They present a global clustering algorithm -coined clustering by committee (CBC) -that automatically discovers word senses from text. The key idea is to first discover a set of tight, unambiguous clusters, to which possibly ambiguous words can be assigned. Once a word has been assigned to a cluster, the features associated with that particular cluster are stripped off the word's vector. This way, less frequent senses of the word may be discovered. [START_REF] Van De Cruys | Using Three Way Data for Word Sense Discrimination[END_REF] proposes a model for sense induction based on latent semantic dimensions. Us-ing an extension of non-negative matrix factorization, the model induces a latent semantic space according to which both dependency features and broad contextual features are classified. Using the latent space, the model is able to discriminate between different word senses. The model presented below is an extension of this approach: whereas the model described in [START_REF] Van De Cruys | Using Three Way Data for Word Sense Discrimination[END_REF] is only able to perform word sense induction, our model is capable of performing both word sense induction and disambiguation.

Methodology

Non-negative Matrix Factorization

Our model uses non-negative matrix factorization [START_REF] Lee | Algorithms for non-negative matrix factorization[END_REF] in order to find latent dimensions. There are a number of reasons to prefer NMF over the better known singular value decomposition used in LSA. First of all, NMF allows us to minimize the Kullback-Leibler divergence as an objective function, whereas SVD minimizes the Euclidean distance. The Kullback-Leibler divergence is better suited for language phenomena. Minimizing the Euclidean distance requires normally distributed data, and language phenomena are typically not normally distributed. Secondly, the non-negative nature of the factorization ensures that only additive and no subtractive relations are allowed. This proves particularly useful for the extraction of semantic dimensions, so that the NMF model is able to extract much more clear-cut dimensions than an SVD model. And thirdly, the non-negative property allows the resulting model to be interpreted probabilistically, which is not straightforward with an SVD factorization.

The key idea is that a non-negative matrix A is factorized into two other non-negative matrices, W and H

A i×j ≈ W i×k H k×j (1)
where k is much smaller than i, j so that both instances and features are expressed in terms of a few components. Non-negative matrix factorization enforces the constraint that all three matrices must be non-negative, so all elements must be greater than or equal to zero. Using the minimization of the Kullback-Leibler divergence as an objective function, we want to find the matrices W and H for which the Kullback-Leibler divergence between A and WH (the multiplication of W and H) is the smallest. This factorization is carried out through the iterative application of update rules. Matrices W and H are randomly initialized, and the rules in 2 and 3 are iteratively applied -alternating between them. In each iteration, each vector is adequately normalized, so that all dimension values sum to 1.

H aµ ← H aµ i W ia A iµ (WH) iµ k W ka (2) W ia ← W ia µ H aµ A iµ (WH) iµ v H av (3)

Word sense induction

Using an extension of non-negative matrix factorization, we are able to jointly induce latent factors for three different modes: words, their window-based ('bag of words') context words, and their dependency relations. Three matrices are constructed that capture the pairwise co-occurrence frequencies for the different modes. The first matrix contains cooccurrence frequencies of words cross-classified by dependency relations, the second matrix contains co-occurrence frequencies of words cross-classified by words that appear in the noun's context window, and the third matrix contains co-occurrence frequencies of dependency relations cross-classified by cooccurring context words. NMF is then applied to the three matrices and the separate factorizations are interleaved (i.e. the results of the former factorization are used to initialize the factorization of the next matrix). A graphical representation of the interleaved factorization algorithm is given in figure 1.

The procedure of the algorithm goes as follows. First, matrices W, H, G, and F are randomly initialized. We then start our first iteration, and compute the update of matrix W (using equation 3). Matrix W is then copied to matrix V, and the update of matrix G is computed (using equation 2). The transpose of matrix G is again copied to matrix U, and the update of F is computed (again using equation 2). As a last step, matrix F is copied to matrix H, and we restart the iteration loop until a stopping criterion (e.g. a maximum number of iterations, or no more significant change in objective function; we used the Next, the factorization that is thus created is used for word sense induction. The intuition is that a particular, dominant dimension of an ambiguous word is 'switched off', in order to reveal other possible senses of the word. Formally, we proceed as follows. Matrix H indicates the importance of each dependency relation given a topical dimension. With this knowledge, the dependency relations that are responsible for a certain dimension can be subtracted from the original noun vector. This is done by scaling down each feature of the original vector according to the load of the feature on the subtracted dimension, using equation 4.

t = v(u 1 -h k ) (4)
Equation 4 multiplies each dependency feature of the original noun vector v with a scaling factor, according to the load of the feature on the subtracted dimension (h k -the vector of matrix H that corresponds to the dimension we want to subtract). u 1 is a vector of ones with the same length as h k . The result is vector t, in which the dependency features rel-evant to the particular topical dimension have been scaled down.

In order to determine which dimension(s) are responsible for a particular sense of the word, the method is embedded in a clustering approach. First, a specific word is assigned to its predominant sense (i.e. the most similar cluster). Next, the dominant semantic dimension(s) for this cluster are subtracted from the word vector, and the resulting vector is fed to the clustering algorithm again, to see if other word senses emerge. The dominant semantic dimension(s) can be identified by folding vector c -representing the cluster centroid -into the factorization (equation 5). This yields a probability vector b over latent factors for the particular centroid.

b = cH T

(5)

A simple k-means algorithm is used to compute the initial clustering, using the non-factorized dependency-based feature vectors (matrix A). kmeans yields a hard clustering, in which each noun is assigned to exactly one (dominant) cluster. In the second step, it is determined for each noun whether it can be assigned to other, less dominant clusters. First, the salient dimension(s) of the centroid to which the noun is assigned are determined. The centroid of the cluster is computed by averaging the frequencies of all cluster elements except for the target word we want to reassign. After subtracting the salient dimensions from the noun vector, it is checked whether the vector is reassigned to another cluster centroid. If this is the case, (another instance of) the noun is assigned to the cluster, and the second step is repeated. If there is no reassignment, we continue with the next word. The target element is removed from the centroid to make sure that only the dimensions associated with the sense of the cluster are subtracted. When the algorithm is finished, each noun is assigned to a number of clusters, representing its different senses.

We use two different methods for selecting the final number of candidate senses. The first method, NMF con , takes a conservative approach, and only selects candidate senses if -after the subtraction of salient dimensions -another sense is found that is more similar to the adapted noun vector. The second method, NMF lib , is more liberal, and also selects the next best cluster centroid as candidate sense until a certain similarity threshold φ is reached. 2

Word sense disambiguation

The sense inventory that results from the induction step can now be used for the disambiguation of individual instances as follows. For each instance of the target noun, we extract its context words, i.e. the words that co-occur in the same paragraph, and represent them as a probability vector f . Using matrix G from our factorization model (which represents context words by semantic dimensions), this vector can be folded into the semantic space, thus representing a probability vector over latent factors for the particular instance of the target noun (equation 6).

d = fG T (6)
Likewise, the candidate senses of the noun (represented as centroids) can be folded into our semantic space using matrix H (equation 5). This yields a probability distribution over the semantic dimensions for each centroid. As a last step, we compute the Kullback-Leibler divergence between the context vector and the candidate centroids, and select the candidate centroid that yields the lowest divergence as the correct sense. The disambiguation process is represented graphically in figure 2.

Example

Let us clarify the process with an example for the noun chip. The sense induction algorithm finds the following candidate senses:3 1. cache, CPU, memory, microprocessor, processor, RAM, register 2. bread, cake, chocolate, cookie, recipe, sandwich 3. accessory, equipment, goods, item, machinery, material, product, supplies

Each candidate sense is associated with a centroid (the average frequency vector of the cluster's members), that is folded into the semantic space, which yields a 'semantic fingerprint', i.e. a distribution over the semantic dimensions. For the first sense, the 'computer' dimension will be the most important. Likewise, for the second and the third sense the 'food' dimension and the 'manufacturing' dimension will be the most important. 4Let us now take a particular instance of the noun chip, such as the one in (1).

(1)

An N.V. Philips unit has created a computer system that processes video images 3,000 times faster than conventional systems. Using reduced instructionset computing, or RISC, chips made by Intergraph of Huntsville, Ala., the system splits the image it 'sees' into 20 digital representations, each processed by one chip.

Looking at the context of the particular instance of chip, a context vector is created which represents the semantic content words that appear in the same paragraph (the extracted content words are printed in boldface). This context vector is again folded into the semantic space, yielding a distribution over the semantic dimensions. By selecting the lowest Kullback-Leibler divergence between the semantic probability distribution of the target instance and the semantic probability distributions of the candidate senses, the algorithm is able to assign the 'computer' sense of the target noun chip.

Evaluation

Dataset

Our word sense induction and disambiguation model is trained and tested on the dataset of the SEMEVAL-2010 WSI/WSD task [START_REF] Manandhar | SemEval-2010 Task 14: Word Sense Induction & Disambiguation[END_REF] The senses induced during training are used for disambiguation in the testing phase. In this phase, the system is provided with a test set that consists of unseen instances of the target words. The test set contains 8,915 instances in total, of which 5,285 noun and 3,630 verb instances. The instances in the test set are tagged with OntoNotes senses [START_REF] Hovy | Ontonotes: the 90% solution[END_REF]. The system needs to disambiguate these instances using the senses acquired during training.

Implementational details

The SEMEVAL training set has been part of speech tagged and lemmatized with the Stanford Part-Of-Speech Tagger [START_REF] Toutanova | Enriching the Knowledge Sources Used in a Maximum Entropy Part-of-Speech Tagger[END_REF][START_REF] Toutanova | Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network[END_REF] and parsed with Malt-Parser [START_REF] Nivre | Maltparser: A data-driven parser-generator for dependency parsing[END_REF], trained on sections 2-21 of the Wall Street Journal section of the Penn Treebank extended with about 4000 questions from the QuestionBank5 in order to extract dependency triples. The SEMEVAL test set has only been tagged and lemmatized, as our disambiguation model does not use dependency triples as features (contrary to the induction model).

We constructed two different models -one for nouns and one for verbs. For each model, the matrices needed for our interleaved NMF factorization are extracted from the corpus. The noun model was built using 5K nouns, 80K dependency relations, and 2K context words (excluding stop words) with highest frequency in the training set, which yields matrices of 5K nouns × 80K dependency relations, 5K nouns × 2K context words, and 80K dependency relations × 2K context words. The model for verbs was constructed analogously, using 3K verbs, and the same number of dependency relations and context words. For our initial k-means clustering, we set k = 600 for nouns, and k = 400 for verbs. For the underlying interleaved NMF model, we used 50 iterations, and factored the model to 50 dimensions.

Evaluation measures

The results of the systems participating in the SEMEVAL-2010 WSI/WSD task are evaluated both in a supervised and in an unsupervised manner.

The supervised evaluation in the SEMEVAL-2010 WSI/WSD task follows the scheme of the SEMEVAL-2007 WSI task [START_REF] Agirre | SemEval-2007 Task 02: Evaluating word sense induction and discrimination systems[END_REF], with some modifications. One part of the test set is used as a mapping corpus, which maps the automatically induced clusters to gold standard senses; the other part acts as an evaluation corpus. The mapping between clusters and gold standard senses is used to tag the evaluation corpus with gold standard tags. The systems are then evaluated as in a standard WSD task, using recall.

In the unsupervised evaluation, the induced senses are evaluated as clusters of instances which are compared to the sets of instances tagged with the gold standard senses (corresponding to classes). Two partitions are thus created over the test set of a target word: a set of automatically generated clusters and a set of gold standard classes. A number of these instances will be members of both one gold standard class and one cluster. Consequently, the quality of the proposed clustering solution is evaluated by comparing the two groupings and measuring their similarity.

Two evaluation metrics are used during the unsupervised evaluation in order to estimate the quality of the clustering solutions, the V-Measure (Rosenberg and Hirschberg, 2007) and the paired F-Score [START_REF] Artiles | The role of named entities in web people search[END_REF]. V-Measure assesses the quality of a clustering by measuring its homogeneity (h) and its completeness (c). Homogeneity refers to the degree that each cluster consists of data points primarily belonging to a single gold standard class, while completeness refers to the degree that each gold standard class consists of data points primarily assigned to a single cluster. V-Measure is the harmonic mean of h and c.

V M = 2 • h • c h + c (7)
In the paired F-Score [START_REF] Artiles | The role of named entities in web people search[END_REF] evaluation, the clustering problem is transformed into a classification problem [START_REF] Manandhar | SemEval-2010 Task 14: Word Sense Induction & Disambiguation[END_REF]. A set of instance pairs is generated from the automatically induced clusters, which comprises pairs of the instances found in each cluster. Similarly, a set of instance pairs is created from the gold standard classes, containing pairs of the instances found in each class. Precision is then defined as the number of common instance pairs between the two sets to the total number of pairs in the clustering solution (cf. formula 8).

Recall is defined as the number of common instance pairs between the two sets to the total number of pairs in the gold standard (cf. formula 9). Precision and recall are finally combined to produce the harmonic mean (cf. formula 10).

P = |F (K) ∩ F (S)| |F (K)| (8) R = |F (K) ∩ F (S)| |F (S)| (9) F S = 2 • P • R P + R (10)
The obtained results are also compared to two baselines. The most frequent sense (MFS) baseline groups all testing instances of a target word into one cluster. The Random baseline randomly assigns an instance to one of the clusters. 6 This baseline is executed five times and the results are averaged.

Results

Unsupervised evaluation

In table 1, we present the performance of a number of algorithms on the V-measure. We compare our V-measure scores with the scores of the bestranked systems in the SEMEVAL 2010 WSI/WSD task, both for the complete data set and for nouns and verbs separately. The fourth column shows the average number of clusters induced in the test set by each algorithm. The MFS baseline has a V-Measure equal to 0, since by definition its completeness is 1 and its homogeneity is 0.

NMF con -our model that takes a conservative approach in the induction of candidate senses -does not beat the random baseline. NMF lib -our model that is more liberal in inducing senses -reaches better results. With 11.8%, it scores similar to other algorithms that induce a similar average number of clusters, such as Duluth-WSI [START_REF] Pedersen | Duluth-WSI: SenseClusters Applied to the Sense Induction Task of SemEval-2[END_REF]. [START_REF] Pedersen | Duluth-WSI: SenseClusters Applied to the Sense Induction Task of SemEval-2[END_REF] has shown that the V-Measure tends to favour systems producing a higher number of clusters than the number of gold standard senses. This is reflected in the scores of our models as well. 3.9 3.9 3.9 1.58 MFS 0.0 0.0 0.0 1.00 Motivated by the large divergences in the system rankings on the different metrics used in the SEMEVAL-2010 WSI/WSD task, [START_REF] Pedersen | Duluth-WSI: SenseClusters Applied to the Sense Induction Task of SemEval-2[END_REF] performed an evaluation of the metrics themselves. His evaluation relied on the assumption that a good measure should assign low scores to random baselines. Pedersen showed that the V-Measure continued to improve as randomness increased. We agree with Pedersen's conclusion that the V-Measure results should be interpreted with caution, but we still report the results in order to perform a global comparison, on all metrics, of our system's performance to the systems that participated to the SEMEVAL task.

Contrary to V-Measure, paired F-score is a fairly reliable measure and the only one that managed to identify and expose random baselines in the above mentioned metric evaluation. This means that the random systems used for testing were ranked low when a high number of random senses was used.

In table 2, the paired F-Score of a number of algorithms is given. The paired F-Score penalizes systems when they produce a higher number of clusters (low recall) or a lower number of clusters (low precision) than the gold standard number of senses. We again compare our results with the scores of the bestranked systems in the NMF con reaches a score of 60.2%, which is again similar to other algorithms that induce same average number clusters. NMF lib scores 45.3%, indicating that the algorithm is able to retain a reasonable F-Score while at the same time inducing a significant number of clusters. This especially becomes clear when comparing its score to the other algorithms.

Supervised evaluation

In the supervised evaluation, the automatically induced clusters are mapped to gold standard senses, using the mapping corpus (i.e. one part of the test set). The obtained mapping is used to tag the evaluation corpus (i.e. the other part of the test set) with gold standard tags, which means that the methods are evaluated in a standard WSD task.

Table 3 shows the recall of our algorithms in the supervised evaluation, again compared to other algorithms evaluated in the SEMEVAL-2010 WSI/WSD task.

NMF lib gets 62.6%, which makes it the best scoring algorithm on the supervised evaluation. NMF con reaches 60.3%, which again indicates that it is in the same ballpark as other algorithms that induce a similar average number of senses. Some doubts have been cast on the representativeness of the supervised recall results as well. According to [START_REF] Pedersen | Duluth-WSI: SenseClusters Applied to the Sense Induction Task of SemEval-2[END_REF], the supervised learning algorithm that underlies this evaluation method tends to converge to the Most Frequent Sense (MFS) baseline, because the number of senses that the classifier assigns to the test instances is rather low. We think these shortcomings indicate the need for the development of new evaluation metrics, capable of providing a more accurate evaluation of the performance of WSI systems. Nevertheless, these metrics still constitute a useful testbed for comparing the performance of different systems.

Conclusion and future work

In this paper, we presented a model based on latent semantics that is able to perform word sense induction as well as disambiguation. Using latent topical dimensions, the model is able to discriminate between different senses of a word, and subsequently disambiguate particular instances of a word. The evaluation results indicate that our model reaches state-of-the-art performance compared to other systems that participated in the SEMEVAL-2010 word sense induction and disambiguation task. Moreover, our global approach is able to reach similar performance on an evaluation set that is tuned to fit the needs of local approaches. The evaluation set contains an enormous amount of contexts for only a small number of target words, favouring methods that induce senses on a per-word basis. A global approach like ours is likely to induce a more balanced sense inventory using a more balanced, unbiased corpus, and is likely to outperform local methods when such an unbiased corpus is used as input. We therefore think that the global, unified approach to word sense induction and disambiguation presented here provides a genuine and powerful solution to the problem at hand.

We conclude with some issues for future work. First of all, we would like to evaluate the approach presented here using a more balanced and unbiased corpus, and compare its performance on such a corpus to local approaches. Secondly, we would also like to include grammatical dependency information in the disambiguation step of the algorithm. For now, the disambiguation step only uses a word's context words; enriching the feature set with dependency information is likely to improve the performance of the disambiguation.

Figure 1 :

 1 Figure 1: A graphical representation of the interleaved NMF algorithm

Figure 2 :

 2 Figure 2: Graphical representation of the disambiguation process

  . The SEMEVAL-2010 WSI/WSD task is based on a dataset of 100 target words, 50 nouns and 50 verbs. For each target word, a training set is provided from which the senses of the word have to be induced without using any other resources. The training set for a target word consists of a set of target word instances in context (sentences or paragraphs). The complete training set contains 879,807 instances, viz. 716,945 noun and 162,862 verb instances.

Table 1

 1

	: unsupervised V-measure evaluation on SE-
	MEVAL test set

Table 2 :

 2 Unsupervised paired F-score evaluation on SE-MEVAL testset

		SEMEVAL-2010 WSI/WSD
	TASK.
	FS (%)	all noun verb	#cl
	MFS	63.5	57.0 72.7 1.00
	Duluth-WSI-SVD-Gap 63.3	57.0 72.4 1.02
	NMF con	60.2	54.6 68.4 1.58
	NMF lib	45.3	42.2 49.8 5.42
	Duluth-WSI	41.1	37.1 46.7 4.15
	Random	31.9	30.4 34.1 4.00

Table 3 :

 3 Supervised recall for SEMEVAL testset, 80% mapping, 20% evaluation

Note that this is not the only possibly way of interleaving the different factorizations, but in our experiments we found that different constellations lead to similar results.

Note that we do not use the word sense to hint at a lexicographic meaning distinction; rather, sense in this case should be regarded as a more coarse-grained and topic-related entity.

 4 In the majority of cases, the induced dimensions indeed contain such clear-cut semantics, so that the dimensions can be rightfully labeled as above.

http://maltparser.org/mco/english_ parser/engmalt.html

The number of clusters in Random was chosen to be roughly equal to the average number of senses in the gold standard.

Acknowledgments

This work is supported by the Scribo project, funded by the French 'pôle de compétitivité' System@tic, and by the French national grant EDyLex (ANR-09-CORD-008).