The so-called Semantic Web vision will certainly benefit from automatic semantic annotation of words in documents. We present a method, called structural semantic interconnections (SSI), that creates structural specifications of the possible senses for each word in a context, and selects the best hypothesis according to a grammar G, describing relations between sense specifications. The method has been applied to different semantic disambiguation problems, like automatic ontology construction, sensebased query expansion, disambiguation of words in glossary definitions. Evaluation experiments have been performed on each disambiguation task, as well
Word sense disambiguation (WSD) is perhaps the most critical task in the area of
computational linguistics. We do not attempt here a survey of the field, but we refer
the interested reader to the Senseval1 home page for a collection of state of art sense
disambiguation methods, and the results of public challenges in this area. During the
most recent Senseval evaluation, the best system in the English all-words task [
However, emerging applications like the so called Semantic Web [
of many research efforts for the construction of on-line knowledge repositories,
ontologies and glossaries are now available (e.g. [
In this paper we present a WSD algorithm, called structural semantic interconnections (SSI), that uses graphs to describe the objects to analyze (word senses) and a contextfree grammar to detect relevant semantic patterns between graphs. Sense classification is based on the number and type of detected interconnections. The graph representation of word senses is automatically built from several available resources, such as lexicalized ontologies, annotated corpora, and glossaries. The SSI algorithm is applied to different problems, namely: § extending and trimming a general-purpose ontology with complex domain terms (e.g. respectively for computer networks, tourism, and finance: local area networks, hotel facility, leveraged buy-out). § disambiguating the words in a natural language concept definition: this is a prerequisite for creating formal axiomatic sense descriptions from informal ones; § disambiguating the words in a query for sense-based web query expansion. The paper is organized as follows: in Section 2 we the structural semantic interconnection algorithm and describes the context-free grammar for detecting semantic interconnections. Section 3 provides implementation details for the three word sense disambiguation problems listed above. Finally, Section 4 is dedicated to the description of several experiments that we made on standard and ad-hoc testing environments.
Our approach to WSD lies in the structural pattern recognition framework. Structural
or syntactic pattern recognition [
The classification task in a structural pattern recognition system is implemented through the use of grammars that embody precise criteria to discriminate among different classes. Learning a structure for the objects to be classified is often a major problem in many application areas of structural pattern recognition. In the field of computational linguistics, however, several efforts have been made in the past years to produce large lexical knowledge bases and annotated resources, offering an ideal starting point for constructing structured representations of word senses.
A structural representation of word senses is automatically built using a variety of
knowledge sources, i.e. WordNet, Domain Labels [
graph (digraph) representations of word senses. We call these semantic graphs, since they represent alternative conceptualizations for a lexical item.
Figure 1 shows an example of the semantic graph generated for senses #1 of market, where nodes represent concepts (WordNet synsets), and edges are semantic relations. In each graph, we include only nodes with a maximum distance of 3 from the central node, as suggested by the dashed ovals in Figure 1. This distance has been experimentally established.
kind-of
trading#1 artifact#1 transpocrtokhamiatniso-mdpn-ea#orer5ftcxep#r1esssaap#-trce1ontmekirmnpd-reiorsfcehi#aaal2cs-tipvaikrttiymn#dh1a-aorsfk-keint#dggg1lllooossssss kitdno-opifc kggilnohoksaosisdn-sdk#-io1enfxdpgoglrocltgs#ooso1nsossdusmf#oe1ordc#lo1cthoinnsgu#m1ption#1 enterprise#k1ind-of abchutsiivnmietoysns#o1pioknlidynu#ds1-toryf#2 servgicloes#s1 kindm-oefrcd-h#oa1fndiskeind-o ggloroscsery#2
load#3 f production#1
All the used semantic relations are explicitly encoded in WordNet, except for the latter three. Topic, gloss and domain are extracted respectively from annotated corpora, sense definitions and domain labels.
The SSI algorithm consists of an initialization step and an iterative step. In a generic iteration of the algorithm the input is a list of co-occurring terms T = [ t1, …, tn ] and a list of associated senses I = [St1 ,..., Stn ] , i.e. the semantic interpretation of T , where Sti 5 is either the chosen sense for ti (i.e., the result of a previous disambiguation step) or the empty set (i.e., the term is not yet disambiguated).
A set of pending terms is also maintained, P = { ti | Sti = ∅ }. I is named the semantic context of T and is used, at each step, to disambiguate new terms in P. The algorithm works in an iterative way, so that at each stage either at least one term is removed from P (i.e., at least a pending term is disambiguated) or the procedure stops because no more terms can be disambiguated. The output is the updated list I of senses associated with the input terms T.
Initially, the list I includes the senses of monosemous terms in T . If no monosemous terms are found, the algorithm makes an initial guess based on the most probable sense of the less ambiguous term. The initialisation policy is adjusted depending upon 5 Note that with we refer interchangeably to the semantic graph associated with a sense or to the sense name. the specific WSD task considered. Section 3 describes the policy adopted for the task of gloss disambiguation in WordNet.
During a generic iteration, the algorithm selects those terms t in P showing an interconnection between at least one sense S of t and one or more senses in I. The likelihood for a sense S of being the correct interpretation of t, given the semantic context I, is estimated by the function fI : C → ℜ , where C is the set of all the concepts in the ontology O, defined as follows:
ρ ({φ (S, S' ) | S'∈ I }) if S ∈ Senses(t) ⊂ Synsets fI (S,t) =
0 otherwise where Senses(t) is the subset of concepts C in O associated with the term t, and e1 e2 en− 1 en ϕ (S, S' ) = ρ' ({w(e1⋅ e2 ⋅ ...⋅ en ) | S→ S1→ ... → Sn− 1→ S' }), i.e. a function (ρ’) of the weights (w) of each path connecting S with S’, where S and S’ are represented by semantic graphs. A semantic path between two senses S and S’, e1 e2 en− 1 en S→ S1→ ... → Sn− 1→ S' , is represented by a sequence of edge labels e1⋅ e2⋅ ...⋅ en . A proper choice for both ρ and ρ’ may be the sum function (or the average sum function).
A context-free grammar G = (E, N, SG, PG) encodes all the meaningful semantic patterns. The terminal symbols (E) are edge labels, while the non-terminal symbols (N) encode (sub)paths between concepts; SG is the start symbol of G and PG the set of its productions.
We associate a weight with each production A → α in PG, where A ∈ N and α ∈ ( N ∪ E) *, i.e. α is a sequence of terminal and non-terminal symbols. If the sequence of edge labels e1⋅ e2⋅ ...⋅ en belongs to L(G), the language generated by the grammar, and provided that G is not ambiguous, then w(e1⋅ e2⋅ ...⋅ en ) is given by the sum of the weights of the productions applied in the derivation SG ⇒+ e1⋅ e2⋅ ...⋅ en.
Finally, the algorithm selects arg max fI (S) as the most likely interpretation of t and
S∈C updates the list I with the chosen concept. A threshold can be applied to f (S to improve the robustness of system’s choices.
At the end of a generic iteration, a number of terms is disambiguated and each of them is removed from the set of pending terms P. The algorithm stops with output I when no sense S can be found for the remaining terms in P such that fI (S) > 0, that is, P cannot be further reduced.
In each iteration, interconnections can only be found between the sense of a pending term t and the senses disambiguated during the previous iteration.
A special case of input for the SSI algorithm is given by I = [∅ ,∅ , ...,∅ ], that is when no initial semantic context is available (there are no monosemous words in T). In this case, an initialisation policy selects a term t ∈ T and the execution is forked into as many processes as the number of senses of t. The grammar G has the purpose of describing meaningful interconnecting patterns among semantic graphs representing conceptualisations in O. We define a pattern as a sequence of consecutive semantic relations e1⋅ e2⋅ ...⋅ en where ei ∈ E , the set of terminal symbols, i.e. the vocabulary of conceptual relations in O. Two relations ei ei+ 1 are consecutive if the edges labelled with i and ei+1 are incoming and/or outgoing from the same concept node, that is → (S)e→i+ 1 , ←(S)e→i+ 1 , → (S)e←i+ 1 , ei ei ei ←(S)e←i+ 1 . A meaningful pattern between two senses S and S’ is a sequence ei e1⋅ e2⋅ ...⋅ en that belongs to L(G).
In its current version, the grammar G has been defined manually, inspecting the intersecting patterns automatically extracted from pairs of manually disambiguated word senses co-occurring in different domains. Some of the rules in G are inspired by previous work on the eXtended WordNet project described in (Milhalcea and Moldovan, 2001). The terminal symbols ei are the conceptual relations extracted from WordNet and other on-line lexical-semantic resources, as described in Section 2.1. G is defined as a quadruple (E, N, SG, PG), where E = { ekind-of, ehas-kind, epart-of, ehas-part, egloss, eis-in-gloss, etopic, … }, N = { SG, Ss, Sg, S1, S2, S3, S4, S5, S6, E1, E2, … }, and PG includes about 50 productions.
As stated in previous section, the weight w(e1⋅ e2⋅ ...⋅ en ) of a semantic path e1⋅ e2⋅ ...⋅ en is given by the sum of the weights of the productions applied in the derivation SG ⇒+ e1⋅ e2⋅ ...⋅ en. These weights have been learned using a perceptron model, using standard word sense disambiguation data, such as the SemCor corpus. Examples of the rules in G are provided in the subsequent Section 3.
The SSI algorithm has been applied in three different WSD tasks. Each of these tasks required some adaptation of the algorithm, as detailed hereafter.
Glossaries and ontologies often provide a textual definition of concepts in which words
are left ambiguous. For example, the WordNet definition of transport#3 is “the
commercial enterprise of transporting goods and materials”. In this gloss, the word
enterprise has 3 senses, and material has 6. Associating the correct sense with each
word in a gloss is a sort of preliminary step to construct formal concept definitions
from informal ones [
For the gloss disambiguation task, the SSI algorithm is initialized as follows: In step 1, the list I includes the synset S whose gloss we wish to disambiguate, and the list P includes all the terms in the gloss and in the gloss of the hyperonym of S . Words in the hyperonym’s gloss are useful to augment the context available for disambiguation. In the following, we present a sample execution of the SSI algorithm for the gloss disambiguation task applied to sense #1 of retrospective: “an exhibition of a representative selection of an artist’s life work”. For this task the algorithm uses a context enriched with the definition of the synset hyperonym, i.e. art exhibition#1: “an exhibition of art objects (paintings or statues)”.
Initially we have: I = { retrospective#1 }6 P = { work, object, exhibition, life, statue, artist, selection, representative, painting, art } At first, I is enriched with the senses of monosemous words in the definition of retrospective#1 and its hyperonym: I = { retrospective#1, statue#1, artist#1 } P = { work, object, exhibition, life, selection, representative, painting, art } since statue and artist are monosemous terms in WordNet. During the first iteration, the algorithm finds three matching paths7: 2
kind −of →3 exhibition#2, statue#1 art#1 and statue#1 object#1 (all instances of rule S1 in Figure 4). retrospective#1 kind −of → kind −of →6
I = { retrospective#1, statue#1, artist#1, exhibition#2, object#1, art#1 } P = { work, life, selection, representative, painting } During the second iteration, a hyponymy/holonymy path (rule S2) is found: has− kind →2 art#1 painting#1 (painting is a kind of art) which leads to: I = { retrospective#1, statue#1, artist#1, exhibition#2, object#1, art#1, painting#1 } P = { work, life, selection, representative } The third iteration finds a co-occurrence (topic rule S5 in Figure 4) path between artist#1 and sense 12 of life (biography, life history):
topic → artist#1 life#12 then, we get: I = { retrospective#1, statue#1, artist#1, exhibition#2, object#1, art#1, painting#1, life#12 } P = { work, selection, representative } The algorithm stops because no additional matches are found. The chosen senses concerning terms contained in the hyperonym’s gloss were of help during disambiguation, but are now discarded. Thus we have: GlossSynsets(retrospective#1) = { artist#1, exhibition#2, life#12, work#2 }
7 With S S’ we denote a path of i consecutive edges labeled with the relation R interconnecting S with S’.
Complex terms can often be defined compositionally from its constituents. For example, we can define revenue management as “the act of managing government income due to taxation”, a definition obtained through the concatenation of the appropriate definitions of management and revenue. Complex concepts are included in general purpose ontologies to a limited extent, and domain ontologies are available only in few technical fields (e.g. medicine, computer science).
Our aim was to extend an existing general purpose ontology through the semantic
interpretation of multi-word terms. For example, revenue and management are in
WordNet, but not revenue management as a complex concept. Both revenue and
management have two senses in WordNet, which leads to 4 possible compositional
semantic interpretations8 for the complex term. In order to extend with complex
domain concepts a general-purpose ontology we devised an ontology learning system,
called OntoLearn [
service
The tree is used as the initial context to activate semantic disambiguation. With reference to Figure 5, the list T in input to the SSI algorithm would be: [service, train, ferry, car, car-ferry, boat, bus, coach, transport, public, taxi, express]. The initialization of I in this case is more complex. If the context is rich enough, as in the service example, one or more monosemous terms are usually found to start the 8 Compositional interpretation of complex nominals applyes in many cases, but clearly not in all. A backoff strategy is to parse glossary definitions, a strategy whose description is outside the scope of this paper. disambiguation process. For example, taxi and car-ferry have only one sense (respectively, “a car driven by a person whose job is to take passengers where they want to go in exchange for money” and “a ferry that transports motor vehicles”), and several interconnections are found during the first execution of the iterative step between the semantic graphs of the monosemous words and the semantic graphs corresponding to the correct sense of the other words in T.
For example, the following rules allow it to disambiguate car, ferry, boat and coach during the first iteration of the SSI algorithm: taxi# 1kind− of→ car# 1 (hyper rule S1) taxi# 1kind− of→ car# 1← kind−of coach# 3 (hyper/hypo rule S3) taxi# 1gloss→ pas sen ger# 1← gloss coach# 3 (gloss rule S6 ) car − ferry# kind− of→ ferry# 1 (hyper rule S1) car − ferry# kind− of→ ferry# 1← has− kind boat# 1 (hyper/hypo rule S3) The subsequent iterations produce a complete disambiguation of the list T. If no monosemous words are found, we explore two alternatives: either we provide manually the synset of the root term (service#2: “a company or agency that performs a public service”) or we fork the execution of the algorithm in as many processes as the number of senses of the root term h. Let n be such a number. For each process i (i = 1, …, n), the input is given by Ii = ∅ ,∅,..., S i , ..., ∅] where h is the i-th sense of h S in Senses(h). Each execution outputs a (partial or complete)i semantic context Ii. Finally, the most likely context Im is obtained by choosing: m = arg max ∑ fIi (S).
1≤ i≤ n S∈Ii The intuition is that, since the root term is included in all the nodes of a term-tree, its “correct” sense should exhibit a high degree of semantic interconnectivity with all the other components. This means that, eventually, one of the processes should cumulate a higher weight fI i (S ) with respect to the others.
When the correct senses have been eventually determined for all the term components of a term-tree, the tree is re-arranged using taxonomic relations, as shown in Figure 3. More details and evaluations on the OntoLearn system are provided in the aforementioned papers. A summary evaluation is in Section 4.
The third application that we explored is the use of sense information for query
expansion. Sense-based query expansion has not really proven its effectiveness in
information retrieval applications: published results are not very recent [
Our claim is that the SSI algorithm offers the additional opportunity of expanding a query with the concepts in an interconnection pattern; for example, the interconnection pattern between smoke and disease in “diseases caused by smoke?”9:
smoke# 7 gloss→ tobacco# 1kind− of→ drug# 1domain→ disease# 1 suggests an expansion with the words tobacco and drug.
In a query expansion task, the SSI algorithm receives a list T including the set of keywords in a query. For example, the (unexpanded) query above is rewritten as T = [ disease, cause, smoke ].
The problem here is that real-world queries are usually very short, reducing the
probability of finding monosemous terms10 for initializing the semantic context I. The
SSI process in this case is forked in as many executions as the number of senses of
the less ambiguous term. Given the limited and less focused context provided by short
queries, the precision in disambiguation is expected to be lower than for the
applications described in previous sub-sections. However, the evaluation section
shows that, even in presence of a WSD error rate higher than the 10% threshold
estimated in [
The gloss disambiguation algorithm has been evaluated on two sets of glosses: a first set of 100 general-purpose glosses11 and a second set of 305 glosses from a tourism domain. This allows us to evaluate the method both on a restricted domain and a nonspecialized task.
For each word in a gloss, the appropriate WordNet sense has been manually assigned,
for over 1,000 words. The annotations are in part those made available by the authors
of the already mentioned eXtended WordNet project [
Table 1 gives an overview of the results. Table 1a provides an overall evaluation of the algorithm, while table 1b computes precision and recall grouped by morphological category. The precision is quite high (well over 90% for both general and domain glosses) but the recall is around 40%. Remarkably, the achieved improvement in precision with respect to the baseline is much higher for general glosses than for domain glosses. This is motivated by the fact that general glosses include words that are more ambiguous than those in domain glosses. Therefore, the general gloss baseline is quite low. This means also that the disambiguation task is far more complex in the case of general glosses, where our algorithm shows particularly good performance.
An analysis of performance by morphological category (Table 1b) shows that noun
disambiguation has much higher recall and precision. This is motivated by the fact
11 The 100 generic glosses have been randomly selected among the 809
glosses used in the OntoClean project (see [
Domains Tourism Generic Domains Tourism Generic noun recall 64.52% 58.27% 305 100 noun prec.
# glosses # words words 1345 421 # disamb. 636 173 adj # of which ok 591 166
Recall
Precision 47,28%
92,92% 41,09%
95,95% verb adj recall prec.
verb recall prec.
# tot nouns # tot adj # tot verbs
Ontology learning is perhaps the task for which our SSI algorithm is best suited: in fact, words in a complex terminological string are expected to be highly related, since the assumption is that the meaning of the entire string may be compositionally obtained from the individual components.
To test the SSI algorithm, we selected 650 complex terms from a set of 3,840 complex nominals extracted from a Tourism corpus and we manually assigned the appropriate WordNet synset to each word composing the term. We did the same for 200 terms in an Economy corpus (Wall Street Journal). Annotation is a rather subjective task, especially since in WordNet certain senses are very close.
We used two annotators with adjustment to reduce this problem. The results of the evaluation are shown in Figure 4. The light and dark towers represent, respectively, the precision and recall of the algorithm, for the Economy and Tourism domains (towers on the right side). Performance is measured also as a function of the number of complex terms from which the initial context T is built (e.g. Figure 2), indicated by |T| in the Figure (towers on the left side). The results show that precision is stable12 around 80%, while the recall considerably increases, as expected, with |T|.
The objective of the query expansion experiment was to obtain a better insight on the
use of sense information for improving web search. In a (still preliminary) study
(described also in [
Synset expansion: “expansible” words are replaced by their synsets, retrieved by the algorithm of previous section.
Hyperonym expansion: “expansible” words are augmented by their WordNet direct hyperonyms.
Gloss synset expansion: “expansible” words are augmented by the synsets of its glosses (disambiguated by an ad-hoc version of our WSD algorithm).
Gloss-topic words expansion: “expansible” words are augmented with the words related to the concepts linked by gloss and topic relations.
Expansible words wi are those for which theβSSI algorithm assigns a sense with a confidence expressed by fI (Swi ) > β , where is an experimentally tuned threshold and
is a sense of wi. We queried the web with the first 24 of the 50 queries used in S the TREC2001 web track. The queries (called “topics”) include the actual query (title) but also text to explain the query (description) and describe precisely the type of documents that should be considered relevant (narrative). For example: <TOP> <num> Number: 518 <title> how we use statistics to aid our decision making? <desc> Description: Find documents that reference the use of statistical data in decision-making. <narr> Narrative: A relevant document will describe a specific statistical method that is used to assist decision-making. </top> 13 TREC is a public challenge that runs every year on specific tasks, called tracks. The web site is http://trec.nist.gov/
Clearly, description and narrative texts cannot be used to expand the query, but only to manually verify the correctness of retrieved documents, as we did. To query the web, we used Google, which revealed not to be the best choice to exploit our algorithm, due to the limitation of 10 words per query. Therefore, for longer queries we are faced with the problem of choosing only a fragment of the candidate expansion words. However, we felt that our results could be stronger if they show an improvement in performance using the most popular search engine.
For each query, we retrieved the first 10 top ranked pages without query expansion, and then we repeated the search with each of the sense based expansion methods outlined above. When expansion terms are synsets, terms of a synset are put in OR. Whenever plain query terms + expansion terms exceed the threshold imposed by Google, we simply choose the first words of the list, a strategy that is certainly not optimized. The results are shown in Table 2 ( β ≥ 0.8 ).
Table 2 Retrieved correct pages when using sense information for all disambiguated words Query short description
Avg. correct pages
over first 10 % variation with respect to plain query words
Plain Query words +Synonyms +Hyperony ms +Gloss synsets
+Gloss/ Topic words
The scope of the experiment is rather limited and preliminary, and there is room for many improvements. For example, no additional mechanisms have been adopted to parse the query, e.g. named entity recognition, nor we conceived a more refined strategy to build a boolean query using sense information. Finally, more sophisticated expansion strategies could be used, exploiting intersecting patterns among sense graphs. Yet, Table 2 shows very interesting results: column 5 shows that the gloss/topic expansion strategy achieves a 23% improvement over the plain query words (column 1), and the improvement is consistent throughout the examples (in 19 over 24 queries). The experiment also shows, not surprisingly, that concepts occurring in the same semantic domain (e.g. taxi and driver) are best suited for query expansion than concepts related by taxonomic relations (e.g. taxi and vehicle).
In a final experiment, we evaluated the SSI algorithm on a standard WSD test set: the “all-words” test set of Senseval-2. In this sense evaluation task, participants were requested to disambiguate all the words in a generic text of 242 sentences, for a total of 2,473 words. For example: <text id="d00"> The <head id="d00.s00.t01">art</head> of <head id="d00.s00.t03">change-ringing</head> <head id="d00.s00.t04">is</head> <head id="d00.s00.t05">peculiar</head> to the <head id="d00.s00.t08">English</head> In the example, all the words annotated with a head tag must be disambiguated, including words with limited semantic content (e.g. is).
Best systems are those achieving both high precision and recall, an evaluation policy that perhaps is not best suited for many WSD applications (e.g. query expansion in previous section). Despite the Senseval task does not depicts a realistic application environment (though presumably this wasn’t an objective for the organizers), we felt that an evaluation on a standard test set would be useful to obtain an unbiased comparison with other WSD methods in literature. For a fair comparison, we ran the experiment using the scoring software provided by the challenge organizers, available on the Senseval-2 web site. The result is shown in Figure 5.
80% 70% 60% 50% 40% 30% 20% 69% 65,30%
63,60% SMU
OntoLearn
AVe-Antwerp
Precision Recall
The figure shows that SSI performs in between the first and second best systems in the Senseval-2 context, out of 26 participant systems. However, SSI is an untrained algorithm, while most Senseval-2 systems (including the first two) have been trained on available semantically tagged corpora. Notice that SSI could be trained, for example, through ad-hoc14 tuning of the rule weights mentioned in Section 2.3. However, ad-hoc training would contradict the general-purpose nature of the SSI methodology.
SSI is an open research area in our group, and several improvements are being explored. The algorithm can be improved both through an enrichment of the structured representation of word senses, and through a refinement and extension of the grammar G. In the current version, grammar rules seek for patterns of conceptual relations (graph edges), but more complex rewriting rules could be defined, involving constraint specifications and type checking on concepts (graph nodes). Finally, machine-learning algorithms could be used to learn recurrent intersection patterns among word senses from semantically annotated corpora, as they are growingly made available from the computational linguistics community. 14 “Ad-hoc” training implies learning from a semantically annotated corpus of word usage examples for at least some of the 2,473 words in the data set.
This work has been partly funded by the INTEROP network of excellence.