This paper presents a combination of algorithms for automatic ontology building based mainly on lexical cooccurrence statistics. We populate an ontology with hypernymy links, thus we refer more specifically to a taxonomy of lexical units (nouns organized by hypernymy relations) rather than an ontology of formally defined concepts. A set of combined statistical procedures produce fragments of taxonomies from corpora that are later integrated into a unified taxonomy by a central algorithm. Our results show that with an ensemble of different components it is possible to achieve an accuracy only slightly worse than human performance. Finally, as our methods are based on quantitative linguistics, the algorithm we propose is not language specific. The language used for the experiments is, however, Spanish.
The study of the vocabulary in its real context of use
is currently a central part of linguistics
This paper presents a preliminary description and
assessment of results of a methodology based on co-occurrence
statistics to transform text into a knowledge structure, which
can be later developed into a taxonomy or an ontology. The
objective is to populate with lexical units the CPA
Ontology (http://www.pdev.org.uk/#onto), handcrafted by
For a more precise definition of the terms, taxonomies
and ontologies are different kinds of knowledge structures.
Whereas an ontology is “a system of categories accounting
for a certain vision of the world”
In different ways, the paper represents an innovative way of addressing the problem. Our method is based on a combination of five different algorithms which produce raw results from corpora in the form of fragments of taxonomies, which are later compared and integrated into a single structure by a central algorithm in charge with the decision making process. The result is a tree of hyponym/hypernym relations between nouns, i.e. words rather than concepts and their formal definitions, characteristic of the linguistic view. Another novelty of the approach is that it is quantitative, thus it does not involve language or domain specific knowledge coded directly into the system. No external resources are needed apart from the analyzed corpora, a Part-of-Speech tagger and the CPA Ontology itself, which does not change because it uses English as a metalanguage. Up to now, however, experiments have been carried out only in English and more extensively in Spanish. We are starting with French and expect to continue replicating the experiment in other languages and offering the results in the accompanying website (http://www.verbario.com).
In the following sections we present a general overview of the related work and then we describe our proposal. We offer an evaluation of the results and, finally, we draft some conclusions and plans for future work.
The interest for the development of taxonomies is of course not new, as the publications on the subject span for four decades. Space limitations only allow us to offer a very brief account of the research in this field, which we organize as follows: first, some efforts to produce taxonomies by hand. Then, the literature on automatic taxonomy building from machine readable dictionaries. Finally, taxonomy extraction from corpora, on the one hand by rule-based systems and, on the other, based on quantitative analysis. 2.1
There is a large body of work in handcrafted taxonomy creation. We will only focus on some of the most representative modern efforts, not 3rd century Porphyrian tree or Roget’s Thesaurus. We also exclude from this account all the specialized ontologies, restricting ourselves to some of the most well-known projects devoted to general vocabulary. Among the most cited projects are FrameNet, Cyc, WordNet and the CPA Ontology. With the exception of WordNet, that also includes a Spanish version, the rest are only available in English1.
FrameNet is aimed at the implementation of
Charles
An examination of these taxonomies reveals different limitations. FrameNet departs from our main interest because strictly speaking it cannot be considered a taxonomy. In the case of the Cyc ontology, the formalisms used to express the relations are too complex to be manipulated and used as a basis for this Spanish taxonomy. In the case of WordNet, 1There are, however, ongoing efforts to produce a Spanish version of FrameNet as well, cf. http://sfn.uab.es/ its general architecture based on synsets can often be problematic because at times the words in a synset are too different from a semantic point of view. For instance, the case of the Spanish synset containing the words animal, bestia, criatura and fauna, which is equivalent to the English synset containing ‘animal’, ‘animate being’, ‘beast’, ‘brute’, ‘creature’ and ‘fauna’. Here, the Spanish word pez and its English equivalent ‘fish’ are correctly placed as hyponyms of ‘animal’, but not as hyponyms of ‘beast’. Furthermore, WordNet is a top-down approach, while our interest is on the corpusdriven approach.
Overall, we decided in favor of the CPA Ontology for our taxonomy population project because its architecture, based on lexical units rather than synsets, is simple enough to be manipulated as needed. 2.2
The field of automatic semantic relation extraction and, in
particular, hypernymy extraction, began to develop soon
after the publication of the first machine readable dictionaries
in the seventies and eighties. This new resource favored the
development of different methodologies to transform
dictionaries made for human users into a lexical database with
information stored and organized for computers
The first researchers shared the idea of taking a machine readable dictionary and study the regularities and patterns in the definitions and subsequently write a system of rules that would allow to extract hypernymy and other semantic relations between vocabulary units. Depending on the dictionary, one of these rules could be that the first noun of the definition would be the hypernym of a defined noun. However, this is not always the case, and thus one needs to develop more rules to cope with the exceptions. 2.3
The Pattern-based Approaches With the advent of
corpus linguistics in the nineties, researchers interested in
semantic relation extraction moved on to corpus analysis but
keeping the same philosophy as in the previous attempts
with dictionaries, that is, elaborating rule-based systems that
would search for lexico-syntactic patterns in corpora
expressing the desired information. Typically, if one finds in
running text a sequence such as “X is a type of Y” or
“X and other (types of) Y”, etc., then one would assume
that any pair of nouns occupying the positions X and Y
would hold a hypernymy relation
Of course, the problem with this approach is that not always the collected patterns express the desired relations and, in addition, many times the desired relations appear expressed in patterns that the researchers were not able to anticipate.
subject is the extraction of thesauri from corpora based on distributional similarity. There are two main lines of research, one that specializes in finding semantic similarity between groups of words and the other in establishing hypernymy links between pairs of words.
In the first case, the semantic similarity between groups
of words is calculated on the basis of distributional
similarity, as it is considered that semantically similar words will
tend to occur in similar contexts. To be semantically
similar, in this case, means to be synonyms or near-synonyms
or, more interestingly, words that pertain to the same
semantic class, i.e., cohyponyms
The second trend goes a step further than the previous
notion of distributional thesauri as just clusters of
similar words, and emphasizes the importance of
establishing a hierarchic organization of the vocabulary, a difficult
task that imposes its own challenges. As in the previous
case, the data is obtained from corpora defined as
document collections, the Wikipedia or the Web, but the method
used is most often directed co-occurrence graphs
After so many publications on the subject, there continue to be attempts on taxonomy extraction, because despite the variety of ideas already proposed there is still plenty of room for improvement. The large body of bibliography appears to indicate that the field has come to a point in which the integration of different ideas is needed, i.e., an algorithm able to integrate different fragments of taxonomies. 3
The novelty of our approach lies on the modular design. Modular algorithms produce small fragments of taxonomies which are later contrasted and integrated into a larger taxonomy by a central module.
Algorithm 1 computes distributional similarity between words. Algorithm 2 calculates asymmetric relations in word co-occurrence in corpora. Algorithm 3 analyzes definitions from various dictionaries of a language and detects cases of significant definiens-definiendum co-occurrence. Algorithm 4 is a variant of 1 because it computes distributional similarity as the number of identical ngrams (as sequences of words) that a group of words may share. Algorithm 5 is an inference engine, which tries to reason upon the results of the other algorithms and extract new hypernymy assertions. Algorithm 6, finally, is the “assembly algorithm”, which is in charge of integrating the taxonomy fragments produced by all the components into a modified version of the CPA Ontology.
Experimental evaluation shows that with this method it
is possible to obtain a robust homeostatic or self-regulated
taxonomy, because it is based on corpus statistics and can
update itself automatically. Evidently, this list of methods is
not exhaustive and, as this is work in progress, we foresee
the integration of other methodologies as well. Up to now
we have avoided matching Hearst patterns because they are
costly to develop, they are language specific and, depending
on the implementation, can also be error prone, as in the case
of the Text2onto software, with precision figures of 17.38%
and 29.95% recall for hypernymy extraction
As a textual corpus for our experiments we used a collection of Spanish press articles and Wikipedia pages accumulated on a single text file of ca. a billion tokens. In the case of algorithm 3, as it is fed with a lexicographic corpus, we used online dictionaries via a web search engine. 3.1
The first component is based on a clustering technique that
produces sets of semantically related nouns on the basis
of distributional similarity. It bears some resemblance with
the quantitative approach of
Consider, for instance, the semantic class of drinks, with elements such as “coffee”, “tea”, “beer”, “brandy”, and so on. In the case of these nouns, there is a great probability that they will co-occur with other words such as the verb “to drink” or nouns such as “glass”, “cup” or “bottle”. These and other shared words are the ones we used as indicators of the nouns’ semantic relatedness, without POS-tag distinction.
We can represent the overlap of shared vocabulary between lexical units as a Venn diagram (figure 1). In the intersection we can observe words that are shared by the units cerveza (beer), cafe´ (coffee) and te´ (tea), e.g. servir (to serve), beber (to drink), tomar (to drink), querer (to want), etc. Of course, we also have words that are shared only by two of the units, e.g., cafe´ and te´ share caliente (hot), which does not co-occur with cerveza. By the same token, cerveza and cafe´ share the unit amargo/a (bitter), which does not cooccur with te´.
In concrete, this component analyzes the syntagmatic context in which a word appears and extracts the vocabulary (excluding function words). It then obtains pairs of words that, following the previous examples of drinks, could be brandy france´s, bebiendo brandy, tomar brandy, brandy barato, etc. (French brandy, drinking brandy, drink brandy, cheap brandy, etc.). From these elements, a data structure is created in which each term is associated with the lexical units it co-occurs with.
Terms are then represented as co-occurrence vectors, and
thus the algorithm conducts a pairwise comparison of the
terms applying a similarity measure which calculates the
degree of overlapping between vectors. In this case, this is
calculated with the Jaccard coefficient, as suggested by
J (A, B) = |A [ B| (1)
|A \ B|
As it is usual in any clustering procedure, for this comparison we need a table of distances, from which we obtain a pair of units showing the greatest similarity. Hereafter, the members of this pair merge and create the first cluster, which occupies the place of both words and contains the sum of their attributes. The process is iterative, thus, another table of distances is created, but every time with one less element. This process stops when the units to cluster do not reach a similarity threshold, defined as a minimum proportion of attributes in common that a set of units must have in order to be assigned the same cluster.
Class Vehicles Types of cheese
In order to obtain an estimation of the quality of the results produced by this single module, we manually evaluated an arbitrary selection of 145 nouns which can be classified as drinks, hats, vehicles, animals and types of cheese. Table 1 shows some examples of the clusters created from these nouns and their member elements. In this experiment, our algorithm was able to produce correct clusters in 96% of the cases, though it was only capable of classifying half of the input words (51%). Better precision was met at the expense of a considerable loss of recall. More details on this experiment will appear in Nazar & Renau (In press). 3.2
Instead of clusters of semantically-related words, as produced by the first algorithm, the second one consists of creating hyponym-hypernym pairs based on their co-occurrence patterning. Here, we define co-occurrence as a tendency of two lexical units to appear together in the same sentences, not taking into account the distance nor their order in the sentence. The main idea behind this study is that cooccurrence is asymmetric in the case of hyponym-hypernym pairs. For instance, the word motocicleta shows a tendency to appear in the same sentences with the word veh´ıculo, but the relation is not reciprocated. The asymmetric nature of such association allows us to automatically represent hierarchical relations without resorting to external knowledge bases. The computation of these relations is produced with the help of directed graphs that express the co-occurrence relations.
The graphs shown in figure 2 illustrate this method. The arrows in the graph represent asymmetric co-occurrence relations, and the node with most incoming arrows is selected as the hypernym of the input term. Here, the input term cortisol tends to co-occur with glucocoricoide and hormona. In turn, glucocoricoide also tends to co-occur with hormona, but this last unit does not reciprocate the relation with neither of both. The output of the graph is read as saying that hormona is the hypernym of cortisol because it is the node with the largest number of incoming arrows. As shown by the other graph, the same pattern is exhibited by noun phrases, very common in multiword terms.
In order to test the performance of this module alone, we
manually evaluated the results of an experiment with 200
Spanish nouns pertaining to the semantic classes of
mammals, insects, drinks, hats, vehicles and, again, varieties of
cheese. This preliminary evaluation shows that we can
expect approximately a 60% chance of obtaining a correct
hypernym for a given noun using this algorithm in isolation.
More details on this experiment can be found in
As already mentioned in subsection 2.2, electronic dictionaries have been used in the past to extract hypernymy and other semantic relations, but in general the approach has been focused on a single dictionary, which is parsed with a rulebased system to extract the relations from the definitions. Our approach here is different because we use a set of dictionaries and infer the hypernymy relations by the frequency of co-occurrence between lexical items in the headword and in the definitions. The algorithm uses the frequency to select hypernyms from the text of the definitions, assuming that there will be some consensus among the dictionaries when selecting a given hypernym, and thus this should be the most frequent word (excluding function words). In this way we save the effort of building a set of rules for each dictionary and we make it possible to replicate the experiment in other languages.
In order to obtain an evaluation of the performance of this
single module, we manually examined the results for a
random sample of 150 nouns and concluded that we can expect
approximately 70% chance of obtaining a correct hypernym
for a given input word. More details on this experiment can
be found in Renau &
With algorithm 4 we explored the possibility of creating clusters of words that have a tendency to occur in exactly the same positions in short sequences of words. This is why we describe this module “ngrams with asterisks”.
What we do here is to study large samples of ngrams, defined as sequences of three to five words, and then replace one of the words inside the ngram with an asterisk. The goal is to record then which are the words that most frequently occur in the position of such asterisk. Normally, these words will show some kind of paradigmatic relation and therefore will have some features in common, such as the grammatical category and, in most cases, also a semantic relatedness. Consider, for instance, the case of the ngram ‘at * airport’, taken from the BNC corpus (table 2). Only a limited number of words can occur in the position of the asterisk, and these are semantically related.
at * airport [645] Heathrow 56, Manchester 23, Gatwick 19, London 15, Frankfurt 15, Teesside 10, Edinburgh 8, an 7, Glasgow 7, Stansted 7, Dublin 6, Birmingham 5, Coventry 5, Aberdeen 5, ...
To share a single ngram is of course not and indication of semantic similarity. But if there are words that show a tendency to appear in the same positions in a large number of different ngrams, then one can conclude that these words are paradigmatically related. As a result, this algorithm produces clusters of words, where it can be seen that the members of each class share not only the same grammatical category but also an evident semantic relatedness. Table 3 shows some examples of the results in English. Results were virtually the same in Spanish. In this paper we are only interested in nouns, but as the table shows, the same procedure can be applied to the study of other grammatical categories.
POS-tag Adverbs Adjectives Proper nouns Nouns
Members of the cluster entirely, exclusively, mainly, primarily, principally cost-effective, efficient, elaborate, professional, subtle Australia, Dublin, England, France, India, Janeiro, Middlesbrough, Newcastle, Sunderland, Yorkshire chess, cricket, football, golf, rugby, soccer, tennis
In order to evaluate this component, we again carried out a manual examination of the results. This was done by a random sample of 30 clusters, containing 1191 words in total. We found that in 96% of the cases the clusters were consistent. This internal consistency is computed as the mean consistency of each individual cluster, with numbers for the individual clusters ranging from 80 to 100% consistency. More details on this experiment will appear in Nazar & Renau (Submitted). 3.5
We use algorithm 5 as an inference engine to analyze the results produced by the previous modules. It is the only component that is not corpus-driven, in the sense that it only analyzes the morphological and lexical features of the terms.
This component is described as an analogical inference engine because it learns to associate features of the lexical items with the category that is assigned to them by the other algorithms. In this way, if a term cannot be found in the analyzed corpora, it may still be classified by this module.
The features that are learned are both lexical and
morphological. The lexical level is only useful in the case of
multiword expressions, but of course these are also very frequent,
especially in the case of technical or specialized domains.
For instance, this algorithm first learns that the other ones
are placing terms such as s´ındrome de Carpenter (Carpenter
syndrome) and s´ındrome de Meretoja (Meretoja syndrome),
among others, as hyponyms of enfermedad (disease). Thus,
it learns to associate features of the terms (in the case, the
sequence s´ındrome de) with a semantic class, and
subsequently classify new terms such as s´ındrome de Maffucci
(Maffucci syndrome) also as a disease. The same is done at
the morphology level: the module learns to detect
morphological similarities between the members of the same
semantic class. Continuing with the same example, it can learn that
very frequently the terms denoting diseases have the suffixes
-osis or -itis, such as hepatitis or endometriosis. Given, thus,
a new term such as pancreatitis, the module will recognize it
as a disease. More details on this experiment were published
in
The integration procedure is however not straightforward, because each algorithm is of a different nature, and thus the combination of the results cannot be solved with a simple voting scheme. Algorithms 1 and 4 result in groups of semantically-similar words, while 2, 3 and 5 result in hypernymy pairs. Moreover, the desired result is to populate the already existing CPA Ontology, which, as already explained, refers to very general or abstract concepts.
Two basic operations are conducted. On the one hand, to integrate the results of modules that produce clusters of semantically similar words and, on the other hand, to link these clusters of words with a correct hypernym. This is done in sequential steps. For each noun in each cluster produced by modules 1 and 4, there (might) be a hypernym candidate provided by modules 2, 3 and 5. The result is that, for each cluster, there will be a most frequent hypernym candidate, which is thus selected as the semantic class of all the members of the cluster. As a result, a pairing of a hypernym with a group of hyponyms is obtained, e.g. seda´n, coche, limusina, etc. are classified as hyponyms of automo´vil. A chain of ascending hypernymy links is built until one of the semantic types of the CPA Ontology is found, and then each word is integrated in an hypernymy chain until the top node Entity:
Entity ! Physical Object ! Inanimate ! Artifact ! Machine ! Vehicle ! Automobile ! sedan 3.7
A first prototype is now being developed as a web demo, available at http://www.verbario.com. The taxonomy of nouns is only a module of Verbario.com, a website that is part of a wider project devoted to lexical analysis. The “Taxonomy” part shows two ways of obtaining results: the user can either introduce a noun and get the hypernymy chain or viceversa, he/she can obtain all the hyponyms of a given target noun. At the moment, more than 30,000 Spanish nouns have already been introduced and, while the system is running, more words are being added at a fast pace with a reasonably low error rate, as shown in the next section. We plan to offer regular back up files of the taxonomy in OWL format at this website.
4
Samples of the overall results were evaluated by a group of 8 human judges, all of them advanced graduate students in linguistics. Each one received the same instructions and a random sample of 52 nouns to evaluate. Criteria for considering a link between a word and a node as correct was that it should correspond to the hypernymy relation type. Among the words from the samples we have, for instance, lechuga (‘lettuce’). In this case, the taxonomy offers two hypernymy chains:
Entity ! Physical Object ! Plant [Planta] ! [Arbusto] ! lechuga
Entity ! Physical Object ! Plant [Planta] ! lechuga For one, it states that it is a type of bush ([Arbusto]), which, in turn, is a type of plant, and so on. But a lettuce is not really a bush, thus this chain is incorrect (it cannot be analyzed as “lettuce IS A bush”). For the other, it asserts that a lettuce is a type of plant ([Planta]), which in turn is a type of physical object, and so on. This last chain is considered correct (it can be analyzed as “lettuce IS A plant”).
For each noun, our human judges indicate how many hypernyms were offered by the taxonomy (two in the case of lechuga) and how many of them were correct: one out of two in this case. We thus calculated overall precision as the ratio of correct chains over total chains. We consider recall very difficult to calculate, because of the lack of corpusbased lexicographic material in Spanish. As a consequence, we only evaluated precision, and obtained that for a total of 763 hypernymy chains examined, 586 were found to be correct, which makes a precision of 76.80%. The standard deviation in the group of judges is 14.34. If we exclude the two judges with more extreme positive and negative scores, then mean precision rate is 77.18%, with a standard deviation of 12.82.
Regarding the control of inter-coder agreement, we included in all samples given to the judges a common group of 11 nouns, which makes 88 judgments that should ideally be identical. However, raters agreed only on 72 cases, which is still more than moderate agreement (81.8% or 63.2% if measured with a Kappa coefficient to correct for chance-related agreement). We can interpret the agreement percentage as the ceiling of the precision one can expect from this type of algorithms.
With respect to error analysis, we found out that they
mostly occurred as a consequence of the polysemy of the
words, a circumstance already noticed by
Another frequent cause of error is confusion between hypernymy and other semantic relation. Vit´ıligo, for instance, is correctly classified as a disease in one case but incorrectly as a hyponym of piel (skin) in another, obviously because it is a skin-related disease and then both words tend to cooccur in the same contexts. The same happens in the case of synonyms, which are often placed incorrectly in a hypernymy relation. For instance, the word cuch´ı is a synonym and not a hyponym of cerdo (pig). There are also cases of meronymy, such as the word oce´ano (ocean), which is wrongly connected to agua (water): an ocean is made of water, but it is not a type of water.
5
This paper has presented a set of combined algorithms for building a taxonomy of Spanish nouns based on procedures from quantitative linguistics. The method, based mainly on the study of co-occurrence patterns, could in principle be replicated with different languages. The precision we obtain at the moment can be improved but at the same time it is only slightly lower than the inter-coder agreement percentage. In semantic analysis, total agreement is unrealistic given the fact that even dictionaries not always agree.
For future work, we are focusing on the following aspects:
on the one hand, we will try to improve precision by
addressing the problem of polysemy and the confusion between
synonyms and meronyms with hypernyms. We have already
experimented with sense-induction algorithms which, for each
noun found in a corpus, will produce a list of different senses
6
This paper has been made possible thanks to funding from Projects Fondecyt 11140704, lead by Irene Renau, and Fondecyt 11140686, lead by Rogelio Nazar (http://www.conicyt.cl/fondecyt). We would like to express our gratitude to the students for their participation and to the reviewers for their extended and detailed comments, which have been very helpful to improve this paper. Unfortunately, lack of time and space prevented us from introducing all of the changes that were suggested.