This paper reports on Language Computer Corporation's rst QA@CLEF participation. For this exercise, we integrated our open-domain PowerAnswer question answering system with our statistical machine translation engine. For 2006, we participated in the English-to-Spanish, French and Portuguese cross-language tasks. We took the approach of intermediate translation, only processing English within the QA system regardless of the input or source languages. The output snippets were then mapped back into the source language documents for the nal output of the system and submission. What follows is a description of our system and methodology.
For 2006, Language Computer's open-domain question answering system PowerAnswer [5] participated in QA@CLEF for the rst time. PowerAnswer has previously participated in many other evaluations, notably TREC [1], however, this is the rst Multilingual QA evaluation the system has entered. We have developed our own statistical machine translation system, which we integrated with PowerAnswer for this evaluation. Since PowerAnswer is a very modular and extensible system, we were able to make a minimum of modi cations for this integration for our initial approach.
Our goals for this year's participation were (
The paper presents a summary of the PowerAnswer system, our machine translation engine, the integration of the two for QA@CLEF 2006, and then follows with a discussion of our results and challenges in this year's CLEF question topics. Table 1 lists the cross-lingual tasks in which we participated.
2
Automatic question answering requires a system that has a wide range of tools available. There is no one monolithic solution for all question types or even data sources. In realization of this, LCC developed PowerAnswer 2 as a fully-modular and distributed multi-strategy question answering system that integrates semantic relations, advanced inferencing abilities, syntactically constrained lexical chains, and temporal contexts. This section presents an outline of the system and how it was modi ed to meet the challenges of QA@CLEF 2006.
PowerAnswer comprises a set of strategies that are selected based on advanced question processing, and each strategy is developed to solve a speci c class of questions either independently or together. A Strategy Selection module automatically analyzes the question and chooses a set of strategies with the algorithms and tools that are tailored to the class of the given question. PowerAnswer can distribute the strategies across workers in the case of multiple strategies being selected, alleviating the increase in the complexity of the question answering process by splitting the workload across machines and processors.
Syntactic Parsing
Named Entity Recognition
Reference
Resolution Question
Internet
Question Processing
Module (QP)
Passage Retrieval Module
(PR) Web−Boosting
Strategy
Answer Processing Module (AP)
Question Logic Transformation Answer Logic Transformation
QLF COGEX
ALF World Kowledge
Axioms Documents
Answer Selection
(AS) Answer
Each strategy is a collection of components, (
As illustrated in Figure 1, the role of the QP module is to determine (
The translation system used at LCC implements phrase-based statistical machine translation [2], the core translation engine is the open-source Phramer [12] system, developed by one of LCC's engineers. Phramer in turn implements and extends the phrase-based machine translation algorithms implemented by Pharaoh [4]. A more detailed description of the MT solution that we adopted for Multilingual QA@CLEF can be found in [11]. We trained the translation system using the European Parliament Proceedings Parallel Corpus 1996-2003 (EUROPARL) [3], which provides between 600k and 800k pairs of sentences (sentences in English paired with the translation in another European language). We followed the training procedure described in the Pharaoh training manual1 to generate the phrase table required for translation.
In order to translate entire documents, we augmented the core translation engine with (
The tokenization process was performed on the original documents (in French, Portuguese or Spanish), in order to convert the sentences to space-separated entities, in which the punctuation and the words are isolated. The step was required because the statistical machine translation core engine accepts only lowercased tokenized input.
The capitalization process follows the translation process and it restores the casing of the words. The capitalization tool uses three-gram statistics extracted from 150 million words from the English GigaWord Second Edition2 corpus, augmented with two heuristics:
4
Our cross-language solution for Question Answering was based on automatic translation of the documents in the source language (English). QA was performed on a collection consisting only of English documents. The answers were converted back into the target language (the original language of the documents) by aligning the translation with the original document (checking to see what was the original phrase in the original document that generated the answer in English); when this method failed, the system falls back to machine translation (source ! target). 1http://www.iccs.inf.ed.ac.uk/ pkoehn/training.tgz 2http://www.ldc.upenn.edu/Catalog/CatalogEntry.jsp?catalogId=LDC2005T12 Passage Retrieval Making use of PowerAnswer's modular design, we developed three di erent retrieval methods, settling on the rst for our nal experiment.
The rst solution is the default solution. The entire target language document collection is translated into English, processed through the set of NLP tools and indexed for querying. Its major disadvantage is the computational e ort required to translate the entire collection. It also requires updating the English version of the collection when one improves the quality of the translation. Its major advantage is that there are no additional costs during question answering (the documents are already translated). This passage retrieval method is illustrated in Figure 2.
EN Questions
EN query EN passages
PowerAnswer EN
TL
EN Answers
Answer Aligner Target Language
Passages
Target Language Answers
The second solution, as seen in Figure 3, requires minimum e ort during indexing (the document collection is indexed in its native language). In order to retrieve the relevant documents, we translate the keywords of the IR query (the query submitted by PowerAnswer to the Lucenebased 3 IR system) with alternations as the new IR query (step 1). The translation of keywords is performed using Phramer, by generating n-best translations. This translated query is submitted to the target language index (step 2). The documents retrieved by this query are then dynamically translated into English using Phramer (step 3). We use a cache to store translated documents so that IR query reformulations and other questions that might retrieve the same documents will not need to be translated again. The set of translated documents is indexed into a mini-collection (step 4) and the mini-collection is re-queried using the original English-based IR query (step 5). (s0) EN Questions (s1) Keyword translation (s6) EN Answers (s7) (s8)
Target Language Answers Answer Aligner
EN query (s5)
EN passages PowerAnswer Phramer
(s2) Target language query (s3) EN mini−index creation (s4)
TL
EN
For example, the boolean IR query in English (\poem" AND \love" AND \1922") is translated into French as (\poeme" AND (\aiment" OR \aimer" OR \aimez" OR \amour") AND \1922") with the alternations. This new query will return 85 French documents. Some of them do not contain \love" in their automatic translation (but the original document contains \aiment", \aimer", \aimez" or \amour"). Thus, by re-querying the translated sub-collection (that contains only the translation of those 85 documents) we retrieve only 72 English documents that will be passed to PowerAnswer.
The advantage of the second method is that minimum e ort is required during collection preparation. Also, the collection preparation might not be under the control of the QA system (i.e. it can be web-based). Also, improvements in the MT engine can be re ected immediately in the output of the integrated system. The disadvantage is that more computation is required at run-time for translating the IR query and the documents dynamically.
The third alternative extracts during indexing the English words that might be part of the translation and indexes the collection accordingly. The process doesn't involve lexical choice - all choices are considered possible. The set of keywords is determined using the translation table, and collects all words that are part of the translation lattice ([4]). Determining only the words according to the translation table (semi-translation) is approximately 10 times faster than the full translation. The index is queried using the original IR query generated by PowerAnswer (with English keywords). After the initial retrieval, the algorithm is similar to the second method: translate the retrieved documents, re-query the mini-collection. The advantage is the much smaller indexing time when compared with the rst method, besides all the advantages of the second method. Also, it has all the disadvantages of the second method, except that it doesn't require IR query translation.
Because preliminary testing proved that there aren't signi cant di erences in recall between the three methods and because the rst method is fastest after the document collection is prepared, we used only the rst method for the nal evaluation.
Answer Processing For each of the above methods, PowerAnswer returns the exact answer and the supporting sentence answer the exact was extracted from (all in English). Then, these answers are then aligned to the corresponding text in the target language documents. The nal output of the system is the converted responses in the target language with the appropriate supporting snippet. If the alignment method fails, the English answer is converted into the target language as the nal response. 5
Our integrated multilingual PowerAnswer system was tested on 190 English ! Spanish, 190 English ! French and 188 English ! Portuguese factoid and de nition questions and 10 English ! Spanish, 10 English ! French and 12 English ! Portuguese list questions. For QA@CLEF, the main score is the overall accuracy, the average of SCORE(q), where SCORE(q) is de ned for factoids and de nition questions as 1 if the top answer for q is assessed as correct, 0 otherwise. Also included are the Mean Reciprocal Rank (MRR) and the Con dence Weighted Score (CWS) that judges how well a system returns correct answers higher in the ranked list of answers.
Table 2 illustrates the nal results of Language Computer's e orts in our rst participation at QA@CLEF for 2006.
There were several sources of errors in LCC's submission, including one major source that accounts for a 50% loss in accuracy. The sources of errors include: translation misalignments, tokenization errors, and data processing errors - questions and passages.
Translation misalignments Because the version of PowerAnswer used this year is monolingual, the design we used for multilingual question answering involved translating documents dynamically for processing through the QA system and mapping the responses back into the source language documents. This resulted in many places where errors could occur. While the translation of the documents into English did introduce noise into the data such as mistranslations, words that were not translated and should have been or words that should not have been translated and were, it did not a ect the QA system as much as we suspected. By far the greatest source of errors was the alignment between the English answers and the source documents which produced the nal response list. This source accounts for roughly a 50% loss of accuracy for the tasks we participated in, as Table 3 shows. For Portuguese, there was also an error in the submission that accounts for the great di erence in accuracy when compared to the Spanish and French results.
Submission Acc. Data errors Questions that contained common nouns in the source language question were one example of data processing errors. Question 83 in the EN-PT task is Who is the director of the lm \Caro diario"?. Here, the noun \Caro" was translated \expensive" when being indexed in English. Hence, the query keyword \Caro" as it is in the question could not be found in the translated collection by the IR system, causing the passage to receive a lowered score when retrieved on less keywords.
Sometimes the wording of the questions also a ected the system in a negative way. There were some spelling changes that were unrecoverable by our system, such \Huan Karlos" for Juan Carlos (EN-PT #5). There were also a few instances of keywords for which PowerAnswer was unable to generate the correct alternation, for example \celebrated" in EN-ES #75 In which year was the Football World Cup celebrated in the United States?, where the correct alternation would have been a synonym for \to host".
The scoring of de nition questions tends to be subjective, so there were cases where we believe an answer returned warranted at worst an inexact but was judged wrong, such as EN-PT #84 What is the Unhcr?. PowerAnswer responded with \O Acnur (Alto Comissariado das Naco~es Unidas para Refugiados) consultou o Brasil e mais 30 pa ses sobre a possibilidade de acolher um grupo de 5.000 refugiados da ex-Iugoslavia", which was judged as wrong. Additionally, the de nition question strategy often returned answer snippets that were a full sentence and were judged as inexact because of their length. One example is EN-PT question 34 Who was Alexander Graham Bell?. PowerAnswer returns the full sentence containing the important nugget \A empresa foi fundada em 1885 e entre os socios estava Alexander Graham Bell, o inventor do telefone", where the nal part \inventor of the telephone" was all that was necessary. 7
While this year's performance was not what we hoped due to some major errors in the nal stages of processing answers, we look forward to better results in the following years. One large step we will be taking is to make the core of PowerAnswer more language-independent. The English dependency comes from the NLP tools more than the modules of PowerAnswer, where the language dependence occurs primarily in Question Processing. By developing a set of multilingual NLP tools, including syntactic parsers and semantic relations extractors, and abstracting the Englishdependent components of PowerAnswer out and building language-independent as well as some language-speci c question processing, we hope to see great improvement in our multilingual QA capabilities. This work will be eased by the exible design of PowerAnswer and our libraries of generic NLP tool interfaces. For next year's CLEF, we plan on submitting results from an improved and corrected system using the same method we have discussed in this paper, as well as from a more language-independent PowerAnswer that can process the source language text natively without intermediate translation.