Automatic Discovery of Fuzzy Synsets from Dictionary Definitions

1 Introduction

Information systems are becoming more and more dependent on natural language processing (NLP) tasks, including the determination of similarities [Agirre et al., 2009], word sense disambiguation (WSD) [Gomes et al., 2003] or question-answering [Pasca and Harabagiu, 2001], where broad-coverage lexical resources, as WordNet [Fellbaum, 1998], play a crucial role. In opposition to formal languages, natural language is ambiguous - different words may have the same meaning and the same word may have different meanings, commonly referred to as word senses. Therefore, WordNet-based lexical resources represent concepts as synsets, which are groups of words that, in some context, have the same meaning and are thus synonyms.

However, from a linguistic point of view, word senses are not discrete and cannot be separated with clear boundaries [Kilgarriff, 1997] [Hirst, 2004]. They are typically complex and overlapping structures. So, sense division in dictionaries and lexical resources is most of the times artificial. On the other hand, this trade-off is often needed to increase the usability of computational lexical resources.

A more realistic approach for coping with this fact is to represent synsets as models of uncertainty, such as fuzzy sets, where each word has a membership degree. The fuzzy membership of a word in a synset can be interpreted as the confidence level about using this word to indicate the meaning of the synset. It can also have a probabilistic interpretation, and denote the likelihood of a word conveying the meaning of each synset it belongs to.

We propose to obtain fuzzy synsets from dictionaries, which are broad-coverage resources structured on word senses, though not fully ready to be used as computational lexical resources. First, we exploit specific textual patterns in definitions for extracting synonymy pairs (hereafter synpairs). Then, the similarity between words in synpairs is computed and fuzzy clusters (hereafter fuzzy synsets) are discovered, in a graph formed by these pairs. The result is a fuzzy thesaurus, Padawik, which, after applying a cut point to the membership degrees, can also be used as a simple thesaurus, similar to the WordNet synset-base.

This work is in the scope of a project [Gonc¸alo Oliveira and Gomes, 2010] aiming to create a lexical ontology for Portuguese semi-automatically, from existing textual resources. It is an alternative to the manual creation of lexico-semantic resources and, even though it may be applied to other languages, intends to be a contribution towards the development of Portuguese NLP. Moreover, Padawik is not only the largest free Portuguese thesaurus, but also the first attempt to create a Portuguese thesaurus based on uncertainty.

We start by introducing some related work and move on to the description of our approach, including the extraction of synpairs from dictionaries and the discovery of clusters in synonymy graphs. Then, we present our experimentation and some results. Fuzzy synsets were discovered from a graph extracted from three Portuguese dictionaries. Before concluding, we compare the resulting thesaurus, Padawik, with handcrafted Portuguese thesauri and show the results of the manual synset evaluation, where more than 73% of the synsets were classified as correct.

2 RelatedWork

During the last decades, dictionaries have been exploited in the automatic creation of computational lexico-semantic resources (e.g. [Chodorow et al., 1985]). Semantic relations (e.g. synonymy, hyponymy), represented as triples (a relation b) were extracted, but words (a and b) can denote different concepts, thus making this representation impractical for tasks such as the inference of new knowledge. As a result, popular lexical resources (e.g. WordNet) organise words in synsets, which are groups of synonymous words that can be seen as the concepts of a lexical ontology.

Despite structured on word senses, dictionaries are not ready to be used as computational lexical resources nor to produce synsets, because they list word senses and describe them by words, not senses. Therefore, ambiguity prevents a straightforward match between the occurrences of words and their possible senses. Furthermore, word senses in different dictionaries do not always match, because there is not a welldefined criteria for the division of meanings into word senses [Dolan, 1994] [Peters et al., 1998]. Senses of the same word can go from tightly related (e.g. in polysemy or metonymy) to completely unrelated (e.g. homonymy).

Regarding that information in dictionaries is usually incomplete, using more than one dictionary [Ide and Veronis, 1995], or using alternative sources of knowledge, such as corpora [Lin and Pantel, 2002], can minimise this problem. However, in opposition to other kinds of relation, synonymous words, despite sharing similar neighbourhoods, may not co-occur frequently in corpora text [Dorow, 2006], which leads to few textual patterns connecting this kind of words. Most of the works on synonymy (or near-synonymy) extraction from corpora rely on the application of mathematical models (e.g. [Turney, 2001]), including graphs, clustering algorithms, or both (e.g. [Dorow, 2006]). Claiming that the so called broad-coverage lexical resources do not cover many concepts found in text, [Lin and Pantel, 2002] propose an algorithm for discovering concepts described by words belonging to some class (e.g. firearms, cells), after clustering words occurring in similar contexts.

Co-occurrence graphs extracted from corpora are useful for identifying not only synonymous words, but also word senses [Dorow, 2006]. As for syonymy graphs extracted from dictionaries, clusters tend to express concepts [Gfeller et al., 2005] and can be exploited for the establishement of synsets. Methods for the improvement of synonymy graphs, extracted from different resources, were presented by [Navarro et al., 2009].

From a linguistic point of view, word senses are not discrete, so their representation as crisp objects does not reflect the human language. Therefore, it is more realistic to adopt models of uncertainty, including fuzzy logic, to handle word senses and natural language concepts. For instance, [Velldal, 2005] describes a similar work to [Lin and Pantel, 2002], but he represents word sense classes as fuzzy clusters, where each word has an associated membership degree. Furthermore, [Borin and Forsberg, 2010] present an ongoing work on the creation of Swedish fuzzy synsets. They propose two methods for achieving their purpose using a lexicon with word senses and a set of synpairs. The fuzzy membership values are based on human judgements of the synpairs.

3 From dictionary definitions to fuzzy synsets

The process of identifying fuzzy synsets, described in this section, consists of two stages: i) extraction of a synonymy graph from a dictionary; ii) clustering words in synsets, based on the configuration of the graph.

3.1 Extraction of synpairs from dictionaries

As referred in Section 2, sense divisions in dictionaries are almost arbitrary, so we do not consider them. Synpairs can be extracted from plain definitions consisting of only one word, enumerations or definitions using synonymy textual patterns as the following:

• mind, n: brain, head, intellect
• (brain, mind) (head, mind) (intellect, mind)
• machine, n: the same as computer
• (computer, machine)

In addition, dictionaries such as the Wiktionary provide synonymy lists for some of its entries.

3.2 Discovery of fuzzy synsets in synonymy graphs

Synonymy graphs are structures G = (N, E), with |N| nodes and |E| edges, E ⊂ N 2 . Each node na ∈ N represents a word and each edge connecting na and nb, E(na, nb), indicates that, in some context, words na and nb may have the same meaning and are thus synonymous.

In our case, each synpair defines an edge of the synonymy graph, G. Synsets with fuzzy membership are then identified after running the following graph clustering algorithm on G:

1. Create an empty sparse matrixM, |N| × |N|.
2. Fill each cell Mij with the similarity between the adjacency vectors of the words ni and nj, ⃗ ni and ⃗ nj .
3. Normalise the columns of M, so that the values in each column, Mj , sum up to 1.
4. Extract a fuzzy cluster Fi from each rowMi, consisting of the words nj where Mij > 0. The value in Mij is used as the membership degree of the word nj to Fi, μFi (nj).
5. For each cluster Fi with all elements included in a bigger cluster Fj (Fi∪Fj = Fj and Fi∩Fj = Fi), Fi and Fj are merged, giving rise to a new cluster Fk with the same elements of Fj, where the membership degrees of the common elements are summed, μFk (nj ) = μFi (nj ) + μFj (nj ).

This algorithm is simpler than fuzzy c-means [Bezdek, 1981]. In opposition to the latter, there is no need to keep two matrixes, one with the weights and another with the centroids, which is important because synonymy graphs can be very large. Moreover, there is no need to specifiy the number of clusters - words are organised into m clusters, where m is never higher than the number of unique words, |N|.

If μFi (na) > 0, the word na has a sense with a common meaning to the other words in Fi. The membership degree μFi (na) is thus the confidence level on the usage of the word na with the meaning of the synset Fi. Looking at all the membership degrees of the same word, they all sum up to 1, ∑ μFi (nj) = 1. As a result, membership degrees of na can also be interpreted as the possible senses of the word na and the likelihood of the word na conveying their meanings.

Any measure for computing the similarity of two vectors can be used in item 2 of the algorithm. If the adjacencies are binary vectors, measures typically used for computing the similarity between sets, such as the Jaccard coefficient, are a suitable alternative.

However, if it is possible to extract a synpair more than once, we can take advantage of redundancy. So, the number of edges between nodes na and nb can be considered for calculating the adjacency vectors, ⃗ na and ⃗ nb. Each edge of the graph thus becomes a triple E(ni, nj, wij), where a synpair (na, nb) has an associated weight, wab, relative to the number of times it was extracted 1 . Furthermore, inspired by [Lin and Pantel, 2002], each position of the vectors ⃗ ni can be filled with the pointwise mutual information (pmi) between the word ni and all the other words, computed using expression 1. As the pmi is biased towards infrequent words, it should be multiplied by the discounting factor in expression 2, also suggested by [Lin and Pantel, 2002]. Finally, the similarity of two words is given, for instance, by the cosine similarity between their vectors (expression 3).

4 A fuzzy thesaurus for Portuguese

In this section, we describe our experimentation towards the creation of a fuzzy Portuguese thesaurus, Padawik, and analyse some results. As information in dictionaries is often incomplete [Ide and Veronis, 1995], three dictionaries were used to maximise both quality and coverage.

4.1 Resources used

Synpairs were acquired from two public domain dictionaries of Portuguese and from a public domain lexical network, PAPEL 2.0 [Gonc¸alo Oliveira et al., 2010], extracted from a proprietary dictionary. Both public domain dictionaries were processed by the grammars available through PAPEL's website 2 , created specifically to extract several semantic relations, including synonymy, from definitions in Portuguese.

One of the dictionaries used was Dicion´ario Aberto [Sim˜oes and Farinha, 2010], a resource based on the transcription of a Portuguese dictionary from 1913. It contains approximately 227K definitions, some of them written in old Portuguese. Therefore, for each pair with words containing disused sequences, several replacements were made according to the suggestions in [Sim˜oes et al., 2010]. If the new words were in PAPEL, we kept the pair, otherwise we discarded it. The other dictionary was the 25th October 2010

1 If the order of the words in a synpair is considered (e.g. (a,b), (b,a)) at most two equivalent synpairs can be extracted from each dictionary.

2 Available through http://www.linguateca.pt/PAPEL/

dump of the Portuguese Wiktionary 3 , a collaborative dictionary by the Wikimedia foundation. Despite several parsing issues due to the lack of standartisation of the wiki text (also referred by [Navarro et al., 2009]), 54K definitions and synonymy lists were collected from Wiktionary.

4.2 Synonymy graph data

Table 1 has the properties of the graphs established by our synpairs: number of nodes |N| and edges |E|, average degree deg(G) of the graph, average clustering coefficient CClcs and the number of nodes of the largest connected subgraph |Nlcs|. Weights were not considered in the construction of this table.

The average degree (expression 4) is the ratio between the number of nodes |N| and the number of edges |E| in the graph. The average clustering coefficient (expression 5) measures the degree to which nodes tend to cluster together as a value in [0-1]. In random graphs, this coefficient is close to 0. The local clustering coefficient CC(ni) (expression 6) of a node ni quantifies how connected its neighbours are.

Despite having a large number of nodes, all the graphs are quite sparse. It is thus possible to represent them as sparse matrixes and minimise memory consumption.

An interesting fact is that the largest connected subgraph lcs contains always more than half of the total nodes. If there was no ambiguity, this would mean all the words in lcs were synonymys of each other, which is not true. This points out the need of additional organisation of synonymy automatically extracted from dictionaries. Clustering coefficients are slightly higher than those of graphs extracted from several Wiktionaries (between 0.2 and 0.28) [Navarro et al., 2009].

4.3 Qualitative results

Figure 1 presents one subgraph and the fuzzy synsets obtained after clustering. It shows words denoting a person who rules and divides them in two slightly different concepts. A ceaser/emperor is someone who rules an empire, while a king rules a kingdom. Nevertheless, several words can denote both concepts, with different membership degrees.

To have and idea on how ambiguity was handled in the establishment of fuzzy synsets, we selected two polysemic Portuguese words, pasta and cota, looked at some of the synsets containing them, and divided them into possible senses of these words, as shown in Table 2.

3 Available through http://pt.wiktionary.org/

4.4 Thesaurus data for different cut points

Different cut-points (θ) applied to a fuzzy thesaurus result in different simple thesauri. Table 3 is an overview on the noun thesauri obtained from Padawik. It includes the number of words and ambiguous words, the average number of senses per word, the number of senses of the most ambiguous word, the number of synsets, the average synset size in terms of words, synsets of size 2 and size larger than 25, which are less likely to be useful [Borin and Forsberg, 2010], and the largest synset. This table does not consider synsets of size 1.

Before collecting the data in Table 3, we followed one of the clustering methods for word senses proposed for EuroWordNet [Peters et al., 1998], which suggests that synsets with three members in common can be merged. However, the design of our clustering algorithm and the configuration of our synonymy graphs are prone to create synsets sharing more than one word. So, to minimise the possibility of merging synsets denoting different concepts, we made sure that merged synsets had at least 75% overlap (expression 7).

As expected, as θ grows, ambiguity drops. This is observed not only from the number of ambiguous words, but also from the average number of word senses and the number of synsets.

Out of curiosity, the largest synset in Padawik with θ ≥ 0.075 denotes the concept of money. We manually checked that every word in this synset could have this meaning, which indicates there are many ways of referring to money in Portuguese: informal (e.g. pastel, pasta, carcanhol, pilim), popular (e.g. massaroca, cacau, guita), Brazilian (e.g. grana, tutu) or Mozambican Portuguese variant (e.g. mussuruco, matambira), figurative senses (ouro, metal) and older forms (dieiro), amongst others. Another large synset in most thesauri refers to alcoholic intoxication and contains words such as piela, touca, pifo, chiba, carraspana, bezana or bebedeira.

5 Evaluation

Evaluating clustering results is usually a difficult task so, in order to make it simpler for humans, we selected Padawik with θ = 0.075, whose size was compared against existing Portuguese thesauri and then manually evaluated.

5.1 Comparison with existing Portuguese thesauri

There are two open domain handcrafted Portuguese thesauri, organised in synsets: OpenThesaurus 4 , a small collaborative thesaurus whose main purpose is to suggest writing alternatives in OpenOffice 5 ; and TeP [Maziero et al., 2008], a thesaurus for Brazilian Portuguese. Table 4 puts side-by-side the former thesauri, fuzzy Padawik and Padawik with θ = 0.075, which is between the cut-points that lead to the closest average senses (θ = 0.05) and the closest average synset size (θ = 0.15) as compared to TeP's. Both automatically created thesauri are larger than the handcrafted ones. For nouns, the former have two times more words than TeP.

We did not use these thesauri as gold standards for evaluation because, as other authors analysed [Teixeira et al., 2010], they have low overlaps with PAPEL and Wiktionary.

4 Available through http://openthesaurus.caixamagica.pt/

5 Available through http://www.openoffice.org/

5.2 Manual evaluation

In order to make manual evaluation faster and less tedious, we selected a subset of the noun synsets in Padawik-0.075. First, we removed all the words without occurrences in the frequency lists 6 of AC/DC [Santos and Bick, 2000], which compile word frequencies in several Portuguese corpora. Then, we selected only the 834 synsets with all words with AC/DC frequencies higher than 100. We were left with a thesaurus of 1,920 words, 227 of those ambiguous, and 1.13 senses per word. Synsets had an average of 2.61 words and the largest had 10 words.

From this thesaurus, we created 22 random samples: 11 with 40 synsets and 11 with 40 synpairs, established by two words selected randomly from the same synset. Synpairs can be handled as a synset of two words. So, given a sample, judges classified each synset as: correct (1), if, in some context, all the words could have the same meaning, or incorrect (0), if at least one word could not have the same meaning as the others. Judges were advised to look for possible word senses in different dictionaries. If they still did not know how to classify the synset, they had a third option, N/A (2).

The evaluation results, in Table 5, show that the average correction of Padawik's synsets is higher than 73%, with agreements higher than 80%, which we believe to be a good quality indicator. When we decided to evaluate our data as synsets and also as synpairs, we intended to give two different perspectives on its quality. However, both kinds of evaluation yielded similar results, as the correction of synpairs is 75%.

6 Concluding remarks

Having in mind that word senses are not discrete, representing natural language concepts as fuzzy synsets is closer to reality than using simple synsets. We have shown that the former structures can be acquired from dictionary definitions by identifying clusters in synonymy graphs.

6 Available through http://www.linguateca.pt/ACDC/

Future directions include learning individual cut-points for each fuzzy synset, and also exploring different strategies to capture word senses not described by synonymous words.

Padawik will be publicly available. For instance, it will be possible to integrate Padawik in the OpenOffice tools for Portuguese as an alternative to OpenThesaurus, which is more than four times smaller. Moreover, if Padawik is merged with handcrafted thesauri, an even larger thesaurus can be obtained. Still, since size is not the only important property of a thesaurus, we are devising the creation of smaller thesauri, after filtering less common words.

Acknowledgements

We would like to thank the CMS group for the manual evaluation of synsets and Leticia Ant´on P´erez for developing the Wiktionary parser. Hugo Gonc¸alo Oliveira is supported by the FCT grant SFRH/BD/44955/2008 co-funded by FSE.