This paper presents the extension of the ITC-irst DIOGENE Question Answering system towards multilinguality. DIOGENE relies on a well tested three-components architecture built in the framework of our participation in the QA track at the Text Retrieval Conference (TREC 2002). The novelty factors are represented by the enhancement of the system with language-specific tools targeted to the Italian language (e.g. a module in charge of the answer-type extraction, and a named entities recognizer) and the introduction of a module for the translation of Italian queries into English queries. The overall architecture of the extended system, as well as the results obtained in the CLEF2003 Monolingual Italian and Bilingual Italian/English QA tracks will be presented and discussed throughout the paper. Research in Question Answering (QA) has received a strong boost in recent years by the QA track organized within the TREC conferences (Voorhees and Harman, 1997), which aims at assessing the capability of systems to return exact answers to open-domain English questions. The success of the initiative has reflected on the tendency of system developers to focus their activity on issues raised by the track guidelines (e.g.. how to deal with particular types of questions, how to pinpoint exact answers within a text document, and how to rank them according to the system's confidence). Besides the many positive effects of the TREC experience, several aspects related to the QA problem have not been faced yet. For instance, even though multilinguality has been recognized as an important issue for the future (Burger at al., 2001), up to now little has been done to provide QA systems with the capability of handling languages other than English. However, multilinguality represents a promising direction for future developments for at least two reasons. First, allowing users to interact with machines in their native languages, it would contribute to an easier, faster, and more reliable information access. Second, cross-language capabilities enable the access to information stored in language-specific text collections, that could hardly be captured by seeking only through English documents. In the framework of an increasing interest towards multilinguality testified by the set up of a multiple-language QA track within CLEF-2003, DIOGENE represents the first concrete attempt to develop a QA system capable of dealing with Italian and English, both in monolingual and cross-language scenarios. In the former case, the Italian version of DIOGENE has been built upon the same well tested three-components architecture of the English version (Magnini et al., 2002a). Figure 1 shows the main constituents of this common backbone: these are the question processing component (in charge of the linguistic analysis of the input question), the search component (which performs the query composition and the document retrieval), and the answer extraction component (which extracts the final answer from the retrieved text passages). Sharing the overall architecture, as well as a number of basic tools and resources, the two monolingual versions of DIOGENE provided us with an enough flexible and reliable infrastructure for extensions towards cross-language QA as it is concerned within the CLEF-2003 framework. In particular, in order to retrieve English answers in response to Italian questions, the Italian question processing component has been extended with a module for keyword translation into English (also depicted in Figure 1), and then combined with the search and the answer extraction components of the English version. The following sections will provide a general overview of our participation to the monolingual Italian (M-I) and bilingual Italian/English (B-I/E) tasks of the multiple-language QA track at CLEF-2003. In both the tasks of this new evaluation exercise systems were presented with a set of 200 Italian questions but, while for the M-I task answers had to be sought through an Italian document collection (the 193Mb corpus of the whole 1994 year of La
Stampa newspaper and the 85Mb corpus of the 1994 SDA press agency), the target collection for the B-I/E task was composed of English texts (the 425Mb corpus of the whole year 1994 of Los Angeles Times). Focusing on the system’s architecture, Section 2 will describe the question processing component, while Section 3 and 4 will describe in detail the search, and the answer extraction component respectively. Finally, Section 5 and 6 will conclude the paper presenting the results of the different runs submitted to evaluation and drawing some conclusions.
Tokenization and PoS Tagging Multiwords Recognition Answer Type Identification MI
BI/E Question Processing Component Document Collection
Query
Reformulation Search Engine
Query
Composition Search Component
Answer Validation and Ranking Candidate Answer
Selection Named Entities
Recognition Answer Extraction Component WEB
The overall architecture set up for the ITC-irst participation to the multiple-language QA track at CLEF-2003 is an
adaptation of the one described in
As for the question processing component, both the tasks required the substitution of the original English modules with language specific tools for dealing with the Italian language. In fact, also for the bilingual task, the addition of a module for keywords translation from Italian into English was deemed a more reliable solution than performing automatic translation of the whole question and then rely on the English version of the system.
The analysis of the input question is performed sequentially by the following modules. •
Tokenization and PoS tagging. First the question is tokenized and words are disambiguated with respect to their lexical category by means of a statistical part of speech tagger developed at ITC-Irst. • • • •
Multiwords recognition. As it is done in the English version of the system, about five thousand multiwords (i.e. collocations, compounds and complex terms) have been automatically extracted from a monolingual Italian dictionary (Disc, 1997) and are recognized by pattern matching rules.
Answer type identification. The answer type for a question represents the entity to be searched as answer. This information will be used to select the correct answer to an input question within the documents retrieved by the search engine. In particular, knowing the category of the entity we are looking for (e.g. PERSON, LOCATION, DATE, etc.) we can determine if any “candidate answer” found in a document is an appropriate instantiation of that category. Answer type identification relies on a manually defined taxonomy of answer types (e.g. “LOCATION”, “PERSON”, “ORGANIZATION” “TIME-PERIOD”, “MEASURE”, “TITLE”, etc.), and a set of approximately 250 rules that check different features of an input question. These rules may detect the presence of a particular word occurrence, of words of a given part of speech, and of words belonging to a given semantic category. For instance, the rule described in (1) matches any question starting with “quale” (“what”), whose first noun, if any, is a person. (1) RULENAME: QUALE-CHI
TEST: [“quale” [¬NOUN]* [NOUN:person-p]J +]
OUTPUT: [“PERSON” J]
Rule (1) matches questions like “Quale Primo Ministro Britannico visitò il Sud Africa nel 1960?” (“What
British Prime Minister visited South Africa in 1960?”, which corresponds to Q-89 of the M-I task) since the first
noun encountered after “quale” (i.e. “Prime_Minister”) satisfies the person-p constraint. The same rule does not
match the question: “Quale paese invase il Kuwait nel 1990?” (“What country invaded Kuwait in 1990?”, Q-50
of the M-I task), since “country” does not satisfy the person-p predicate. Following the same methodology that
proved to be successful in the development of the English version of DIOGENE, semantic predicates (e.g.
personp, location-p, organization-p, time-p) have been defined on the MULTIWORDNET taxonomy
Our statistical dictionary-based approach to query translation is rather similar to the one described in
The starting point of our methodology is the noisy-channel model
e We applied statistical techniques to calculate the two probabilities (p(i|e) and p(e)), but further analysis of the results led us to the conclusion that p(i|e) has a small impact on the final results. Therefore, in order to speed up the translation process, in the final version of the system we assigned a constant value to p(i|e). However here we will view how both the probabilities were estimated.
The process is carried out through the following steps.
1. First, DIOGENE extracts all the possible translations for each of the Italian keywords using the Collins
Italian/English dictionary. If the translation is not found (as in the case of multiwords), MULTIWORDNET is
used to translate the word. In case no translation is found and the word is capitalized, it is left as it is (this
works for proper nouns, which are not listed in the dictionaries and whose coverage in MULTIWORDNET is
rather limited). If the word is not capitalized and not found in Collins dictionary, nor in MULTIWORDNET,
we skip it.
2. The next step is to estimate the probability of every translation in order to find the most plausible. Our
algorithm has to deal with all the possible combinations of translations: even if sometimes the number of
these combinations can be very large, our solution easily overcomes the problem. As for ambiguity
resolution, the main resources used by the algorithm are the target English text collection (indexed at
paragraph level), and the DIOGENE’s search engine. Let’s denote with i=(i1, i2, i3…in) a sequence of Italian
keywords, and with e=(ek1 , ek2,…ekm ) the set of English translations for every keyword ik. We search in the
target corpus using a Boolean query of the type:
(e11 OR e12 OR …) AND (e21 OR e22 OR …) AND …AND (en1 OR en2 OR …)
This way we obtain paragraphs which contain at least one translation for every Italian keyword. If no
paragraph is retrieved, a query relaxation algorithm is applied
p(e = (e1i, e2j, e3k, …) ) = frequency(e) / NumberParagraphsInCorpus Probability p(i|e) = p(i1,i2,i3|e1, e2, e3,…) was approximated using trigram model. For example the conditional probability for five keywords has been calculated in the following way: p(i1,i2,i3,i4,i5 | e1,e2,e3,e4,e5) = p(i1 | e1) p(i2| e2, i1,e1) p(i3 | e3, i1, e1, i2, e2) p(i4 | e4, i2, e2, i3, e3) p(i5 | e5, i3, e3, i4, e4) Our approach for calculation of the conditional probabilities relies on the following assumption: If we have a word in English e and a set of its possible translations in Italian denoted by TI(e), we assume that every word from TI(e) in the Italian corpus can be translated in the word e when translating the corpus in English. Of course, this assumption is somehow strong and influences the accuracy of the probabilities. We assume that the appearance of i implies that e appears in the English translation of the corpus. From this assumption it follows that the formula can be rewritten in the following way: p(i1,i2,i3,i4,i5 | e1,e2,e3,e4,e5) = p(i1 | e1) p(i2| e2, i1) p(i3 | e3, i1, i2 ) p(i4 | e4, i2,, i3) p(i5 | e5, i3, i4 ) = p(i1) p(i2, i1) p(i3, i1, i2 ) p(i4, i2,, i3) p(i5 , i3, i4 ) . [p(e1) . p(e2,i1) . p(e3,i1,i2) . p(e4,i2,i3) . p(e5,i3,i4) ]-1 The probabilities in the previous formula can be calculated using the Italian corpus. Probability p(i1, i2, i3) can be calculated counting the number of paragraphs in the Italian corpus where these words occur together. This is acquired by just one query to the index of the corpus. Probability p(e,i1,i2) is calculated by counting the paragraphs where at least one Italian translation of e appears (using again the above mentioned assumption) together with i1 and i2.
Using just frequencies counted in two corpora (Italian and English) we find the combination of English words E using the noisy-channel formula (2): However, as stated before, to speed up the translation process we simplified the calculation of p(i|e). In fact, our final experiments showed that the probability p(i|e) has small impact on the translation quality, but significantly slows down the process. Therefore we changed the above formula into: (4) E = arg max( p(e)) = arg max frequency(e)
e e This means that basically we choose combinations of English translations that have higher frequencies in the target corpus. Using the last formula, our method does not rely on any additional resource or training except for the bilingual dictionary, MULTIWORDNET (as addition to the bilingual dictionary), and the target English corpus.
As we will see in Section 5, the results achieved by DIOGENE in the B-I/E task were similar to those of the monolingual task. Assuming that the question sets in both the tasks have approximately equal level of difficulty, we may conclude that the quality of the translation achieved through this simple approach is more than satisfactory. •
Keyword expansion. Both for the monolingual and the bilingual tasks, basic keywords are then passed to an expansion phase which considers both morphological derivations and synonyms.
Our participation to the QA tasks within CLEF-2003, relies on the same search component developed for the English
version of DIOGENE, as it is described in
Another problem we encountered using MG is related to the lack of language-specific stemming algorithms. Although it allows for different alternatives, derived from different combinations of case-folding and stemming modalities, English is the only language correctly handled while documents are indexed. As a consequence, as for the M-I task, the lack of an Italian stemming algorithm has reflected on a reduced precision of the document retrieval, which probably had some impact on the overall system’s performance.
Once the relevant paragraphs have been retrieved, the answer extraction component first performs a rough selection of answer candidates through named entities recognition. Then, automatic answer validation procedures are applied over the selected candidates to choose and rank, according to the CLEF QA track guidelines, the three final answers to be returned by the system.
The named entities recognition module is in charge of identifying, within the relevant passages returned by the
search engine, all the entities that match the answer type category (e.g. PERSON, ORGANIZATION, LOCATION,
MEASURE, etc.). While the WORDNET-based named entities recognizer already developed for the English version of
DIOGENE
Each version of the system is based on the combination of a set of language dependent rules with a set of predicates, defined on the WORDNET/MULTIWORDNET hierarchy for the identification of both proper names (i.e. person, location and organization names, such as “Galileo Galilei”, “Rome”, and “Bundesbank”) and trigger words (i.e. predicates and constructions typically associated with named entities, such as “astronomer”, “capital”, and “bank”). The process of recognition and identification of the named entities present in a text is carried out in three phases. The first phase (preprocessing) performs tokenization, PoS-tagging, and multiwords recognition of the input text. In the second phase, a set of basic rules (approximately 250 for the English language and 300 for Italian) is used for finding and marking with SGML tags all the possible named entities present in the text (e.g. <MEASURE><CARDINAL>200<\CARDINAL> miles< \ M E A S U R E > f r o m < L O C A T I O N >New York<\LOCATION>). Finally, a set of higher level composition rules which is common to both the versions of the system is used to remove inclusions and overlaps among tags (e.g. <MEASURE>200 miles<\MEASURE> from <LOCATION>New York<\LOCATION>) as well as for co-reference resolution.
The English version of the system has been tested using the test corpora and the scoring software provided in the framework of the DARPA/NIST HUB4 evaluation exercise (Chinchor et al., 1998). Results achieved over a 365Kb test corpus of newswire texts vary among categories (ranging from an F-Measure score of 71% for the category MEASURE, to 96.5% for the category DATE), with an overall F-Measure score of 84%. As for the Italian version, experiments carried out with the same scoring software over a 77Kb text corpus1 revealed a comparable performance, with an overall F-Measure score of 83%.
The automatic answer validation module used for our participation to CLEF-2003 is the same we developed for the
original English version of DIOGENE
ARS (a) =
P(Ka | Kq) P(Ka) 2 / 3 =
hits(Ka NEAR Kq) hits(Kq) * hits(Ka) 2 / 3 * EnglishPages where: • hits(Ka NEAR Kq) is the number of English-language pages returned by AltaVista, where the answer keywords (Ka) and the question keywords (Kq) are in distance of no more than 10 words of each other; hits(Kq) and hits(Ka) are the number of English-language pages where Kq and Ka occur respectively; |EnglishPages| is the number of English pages, indexed by AltaVista. • • This formula can be viewed as a modification of the Pointwise Mutual Information formula, a widely used measure that was first introduced for identifying lexical relationships (in this case the co-occurrence of Kq and Ka). In addition to the measurement of co-occurrence frequencies, for some question types (e.g. Where-location or Whenevent) we applied patterns for answer validation. For instance, given the question “Where is Trento?” and the candidate answer “Italy”, the phrases “Trento in Italy” and “Trento Italy” (which are some of the possible ways in which the answer to a question can be found in a text) are submitted to AltaVista. In these cases, the resulting number of pages is multiplied by 100 and added to the ARS improving its reliability. The effectiveness of the extensions of DIOGENE towards multilinguality have been evaluated over four runs submitted to the monolingual Italian and the bilingual Italian/English QA tasks at CLEF-2003. The results (strict statistics) achieved by each run are shown in Table 1.
Run Irstex031mi Irstst032mi Irstex031bi Irstex032bi The first two rows of Table 1 concern the monolingual task, while the other two concern the bilingual task. Columns 2-6 show, for each submitted run, the total number of answers returned by the system (according to the CLEF QA guidelines, up to three ranked answers for each question could be output), and the number of answers that have been judged right (R), wrong (W), unsupported (U) and inexact (X). Columns 7 and 8 show the number of questions for which no correct answer was returned and the number of questions for which at least one answer was found by DIOGENE. The last two columns show the number of answers correctly marked as NIL out of the total of NIL returned, and the Mean Reciprocal Rank (MRR) obtained for each run. Differences among these figures are due to the adoption of different approaches to produce the final output. In particular, making the most of the opportunity to submit up to two runs for each task, we wanted to test the system’s performance with different settings. The monolingual version was tested in two evaluation scenarios, namely the exact answer task (Irstex031mi), where a TREC-like exact answer had to be returned for each question, and the 50 bytes task (Irstex032mi), where response units with a maximal length of 50 bytes could be returned. In this second case, starting from each candidate answer, longer response units have been extracted by simply considering symmetric left and right windows covering the 50 bytes allowed. Our hypothesis was that by this way the impact of errors due to incorrect named entity tagging and, consequently, the number of inexact answers could have been reduced. Moreover, longer response units were expected to improve the quality of answers to particular classes of questions (e.g. non factoid questions, questions about acronyms, and those asking for entities which do not belong to the classes handled by our named entities recognizer, such as Q 127: “Nomina un farmaco anti-malarico” – “Name an antimalaric drug”), for which the system can only rely on heuristics considering the density of question keywords within the retrieved paragraphs. The evaluation of the 50 bytes run returned unexpected results, with an MRR improvement of only 3% with respect to the exact answer run. As for the number of inexact answers returned, the difference between the two runs is minimal (13 for the exact answer task Vs. 12 for the 50 bytes task), showing an acceptable overall performance of the named entities tagger in the detection of entities’ boundaries. Unfortunately, also the total number of questions that received at least one correct answer and the number of NIL answers are almost the same.
The two runs of the bilingual version of the system have been obtained by varying the answer validation algorithm
described in the previous section, in order to test the impact of combining our statistical approach with traditional
Information Retrieval metrics that take into account also the keywords density within the retrieved paragraphs. In
particular, the significant improvement in the second run (Irstex032bi) results has been obtained by multiplying the
ARS by a keyword density coefficient
In this paper we overviewed the recent extensions of the DIOGENE QA system towards multilinguality. The system’s backbone, built upon a cascade of simple and easily interchangeable modules, relies on a balance of shallow linguistic analysis and statistical techniques that drastically reduces the effort required to cross language barriers. Such an approach proved to be suitable both for handling languages other than English, and for bridging them in cross-language scenarios. In particular, it’s worth noting how the absence of any in-depth text analysis (most of the basic modules use a part of speech tagger as the only linguistic processor) allows for multilingual extensions without developing from scratch crucial language specific tools. Moreover, two of the main system’s components, namely the answer validation module and the keyword translator set up for working in cross-language mode, rely on purely statistical approaches without requiring any language-specific knowledge. Both the modules, in fact, simply use word co-occurrences (either in a document collection or in the Web) as the main source of “knowledge”. The results achieved at the CLEF-2003 Multiple Language QA task confirm the effectiveness of our approach: both the Italian and the Italian/English version of DIOGENE performed well, producing results that are comparable to the English version of DIOGENE (the fourth ranked in the last TREC competition).