We describe three language-independent methods for the task of answer validation. All methods are based on a scoring mechanism that re ects the degree of similarity between the question-answer pairs and the supporting text. We evaluate the proposed methods when using various string similarity metrics, such as exact matching, Levenshtein, Jaro and Jaro-Winkler. In addition to this baseline approach, we take advantage of the multilingual QA4MRE dataset, and devise an ensemble method, which chooses the answer indicated as correct by the largest number of analyses of the individual translations. Finally, we present a language-augmented method that enriches the questions and answers with paraphrases obtained by means of machine translation. Our methods depend on parameters which we estimate using the dataset from CLEF2011. We show that all of the described approaches achieve a signi cant improvement over the random baseline, and that both majority voting and language augmentation lead to superior accuracy as compared with the original method.
Question answering (QA) is a di cult problem situated at the intersection of
several domains, including natural language processing and knowledge
representation [
Identifying paraphrases of the question and answer in the supporting text
helps locating the sentences containing their correct answer. In order to obtain
paraphrases, semantic and syntactic resources have been used [
We present here three methods for answer validation: an overlap-based algorithm (denoted by OV), a language augmented approach which builds on top of the overlap approach (called LAM-OV) and an ensemble model based on majority voting called voting overlap (V-OV). We will make use of the following simple notations: the questions are denoted by Q(1); :::; Q(n), the answers pertaining to question i are denoted as A(i; 1); :::; A(i; 5) and the supporting text is called T .
We note that both our algorithms always indicate the best scoring answer as the correct answer (according to our scoring scheme) and never leave a question unanswered. Also, our approaches are entirely based on the supporting text (and do not consider any additional knowledge sources). 2.1
The OV algorithm performs two steps: rst, a ltering approach selects only the sentences from the supporting text that are similar to both the question and the answers. Then, the pairs (answer, supporting sentence) that yield highest similarity are returned.
More precisely, for each question Q(i), the OV algorithm performs the following steps: rst, it compares the lexical overlap between all concatenated questionanswer pairs fhQ(i); A(i; 1)i; :::; hQ(i); A(i; 5)ig, and all sentences of the supporting text s1; :::; sjT j 2 T . The overlap is computed using a function of some similarity measure between text snippets . We will discuss the scoring function and our choices for later in this section. We proceed by computing a relevance score:
(sk) = maxj=1;:::;5 (hQ(i); A(i; j)i; sk); k 2 f1; :::; jT jg
and retain the top-scoring l sentences for futher analysis, concatenating them into a single long string. Hence, for each question Q(i), a text extract S(i) results. These extracts combine the sentences that are most relevant to any of the given question-answer combinations.
Then, the OV algorithm ranks the answers A(i; 1); :::; A(i; 5) in decreasing order by their similarity to the text in S(i). The pair with largest similarity (A(i; j); S(i)) gives the winning answer A(i; j) to the question Q(i).
The number l and the similarity measure are parameters of the OV method. In our experiments, we tried several values of l 2 f1; 2; 3; 4; 5g and several similarity measures . Speci cally, for two text snippets (e.g. sentences, represented as bag-of-words), a target t0 and an arbitrary t, the similarity between t and the target t0 is de ned as follows: (t0; t) =
;
Pjit=01j maxjjt=j1 (t0(i); t(j))
jt0j
where corresponds to a distance measure between two words. In our
experiments, is either exact matching, Levenshtein [
The V-OV approach that we present is an ensemble method. For a speci c question, each of the models based on the parallel corpora vote for the correct answer choice. The answer that gathers most votes is indicated as correct. The assumption that we make is that some answers are easier to validate in some languages and more di cult in others. However, this approach heavily relies on the parallelism of the corpora in di erent languages, in the sense that the sentences forming the supporting text, the questions and the answers must carry the same information, and the questions and answers must follow the same order. Also, the prediction of the correct answer is identical, irrespective of the target language. 2.3
The LAM-OV method uses automated translation as a means of enriching the text with paraphrases and synonyms prior to executing the answer selection algorithm, in order to improve its performance. Speci cally, for each target language, we transform the questions and answers by successive translations into intermediate languages. For example, in order to obtain several (synonymous) paraphrases in Bulgarian, we translate the question and answers from the Bulgarian corpus into other languages (English, German, Swedish, Arabic) and then back to Bulgarian. Thus, the answers that contain paraphrases of the support text have a higher chance of being matched. We used the online Google Translate4 service for obtaining translations.
Before the algorithms are applied we perform the following preprocessing steps. All questions, answers and supporting text are converted to lower-case. Next, possible abbreviations are discovered via a regular expression that looks for recurring sequences comprising letters and periods without any white-space characters in between, and the period symbols are deleted from the matched sequences. Also, in particular for the Bulgarian corpus, we added several rules that instruct the algorithm to ignore several common abbreviations of the type 'years' (ª.), 'millions' ( Łº. ), 'billions' (ÆŁº.), etc. by eliminating the period character in such cases. The supporting text is then segmented into sentences by splitting the transformed strings at each remaining period symbol. All text undergoes one more phase of preprocessing, through which symbols other than numbers and letters are replaced with white-space characters (we use a common mask for all languages apart from Arabic, for which our system is not directly applicable). Eventually, we tokenize each sentence using the resulting white-space subsequences as a delimiter. 3
ID Method Language Perf 01 OV Bulgarian 0.28 02 OV English 0.31 03 OV Italian 0.35 08 OV Romanian 0.34 09 OV German 0.28 10 OV Spanish 0.28 04 V-OV Bulgarian 0.29 05 V-OV English 0.29 06 V-OV Italian 0.29 07 LAM-OV Bulgarian 0.30 Table 1. Experiments submitted. Description of the method is given in the second column. Last column indicates the accuracy of the model.
EN
BG @l@@ E L J J-W E L J J-W
1 0.36 0.26 0.26 0.28 { { { { 2011 2 0.36 0.3 0.3 0.26 { { { { 3 0.38 0.3 0.32 0.28 { { { { 4 0.36 0.30 0.31 0.31 { { { { 5 0.36 0.31 0.32 0.32 { { { { 1 0.31 0.34 0.31 0.32 0.3 0.3 0.3 0.27 2 0.33 0.34 0.31 0.29 0.27 0.24 0.29 0.29 2012 3 0.31 0.33 0.33 0.31 0.28 0.28 0.27 0.29 4 0.28 0.31 0.31 0.31 0.29 0.29 0.26 0.29 5 0.27 0.31 0.33 0.31 0.28 0.31 0.25 0.29 Table 2. Performance of the OV model for English and Bulgarian. Results for the corpora from 2011 and 2012 are shown. Values corresponding to parameters l and are presented, optimal values being indicated by the marked cell from the 2011 corpus.
The values of the similarity are E (exact match),
L (Levenshtein), J (Jaro) and J-W (Jaro-Winkler).
For the QA4MRE competition at CLEF2012 we submitted a total of 10 models. A summary can be found in Table 3. We submitted models based on the OV method for 6 of the languages included in the competition. Performance gures are presented in the last column of Table 3. The performance is around 0:30 (accuracy), with larger values for Italian, Romanian and English and worse results for Bulgarian, German and Spanish. A similar trend was observed when applying the algorithms to the reading tests included in the CLEF2011 dataset. More details on the performance of the OV algorithm are given in Table 3. We show how the results vary with the choice of parameters l and , on two corpora (from 2011 and 2012) and for two of the languages (Bulgarian and English). We used the 2011 corpus for selecting the optimal parameters, speci cally l = 3 and = ExactMatching. These values maximized the mean accuracy of the system calculated against the reading tests in all supported languages. In Table 3, the accuracy corresponding to these parameters is marked (0:38).
The performance of the voting algorithm V-OV (0:29) is superior than that of the OV algorithm for several languages, including Bulgarian, Spanish and German, but worse for English, Italian and Romanian (Table 3). The poor score is the consequence of the lack of parallelism between the corpora, meaning that the reading tasks, questions and answers were arranged in di erent order in the 2012 corpus available at submission time. We repeated our experiments against the synchronized dataset released after the system submission and found out that a simple ensemble voting scheme that excludes the worst-performing systems (Spanish and German languages, according to the results for the 2011 corpus) would have achieved an accuracy of 0:38. We report this number in this manuscript as the best result that we have obtained against the CLEF2012 dataset.
We applied the LAM-OV approach only to the Bulgarian corpus. In order to enrich the questions and answers with paraphrases, we translated the original corpus to several other languages and then back to Bulgarian. We performed three such experiments, where the intermediate languages were: i ) English, ii ) German and iii ) Swedish followed by Arabic. For cases i ) and ii ), we obtained 0.29 accuracy. In the case iii ), the accuracy reached 0.31. In all cases, we improve the OV baseline. We carried out an additional experiment in which we concatenated all translations (from German, English and Swedish/Arabic) to the original. The performance of the model was 0:31. 4
The OV algorithm is a very simple and generic approach, which can be applied to most of the languages included in the QA4MRE dataset without any supplementary resources. Its generality comes at the price of modest performance, although the accuracy is signi cantly larger than a random baseline of 0:20 (which picks the correct answer uniformly at random among the choices).
The OV approach essentially searches for common words between supporting text and question/answers using an approximate string matching paradigm. Interestingly, we found that metrics like Levenstein, Jaro, and Jaro-Winkler, which re ect the small di erences between words, were not better than exact matching with respect to system performance. We expected that approximate matching would have a similar e ect to applying a lemmatizer, with the advantage of language independence. However, the experiments did not support our expectations.
One of the reasons why our overlap-based method did not perform very well
lies in its inability to address more complex textual inferences, such as synonymy,
paraphrases, nominalization/verbalization, etc. (Refer to [
Below we list three classes of issues addressed by the language-augmented technique.
The rst one is the generation of synonyms, in a form suitable for exact matching. For instance, we have been able to generate the term "states" from a sentence/answer pair containing the closely related term "countries" (originally: "ae Ł" and " oe Ł" , in Bulgarian). Other examples include: "American"/"U.S." (" ŁŒ aeŒ " / " " ), pairs of interchangeable Bulgarian terms for "industry" (" Łłº ae " / "Ł ae Ł "), "electricity" (" º Œ Ł ae "/ " Œ"), etc.
The second one is the generation of paraphrases, such as " ae ŁŒ , ı " and " ae ŁŒ ª ı " (two expressions roughly translated as "a part of Africa to the south of Sahara"). Albeit the phrases generated in this way are not always gramatically correct, this class of transformations has the advantage of providing a more varied set of word forms given a term from the source text, and thus can improve the recall of matching during the candidate scoring phase.
Lastly, we observed issues related to the alternative representations of numerical values. For instance, the correct answer to the question "For how long has Rebecca Lolosoli been working with MADRE?" (reading test 4, question 9, synchronized gold standard dataset) has been provided in both a numerical and lexical forms, accross the various translations of the dataset. As Google Translate can interchange numerical values with their string representation in some cases (that seem to depend on the particular choice of a language pair), the language-augmented method can be regarded as a simple ad-hoc approach for resolving this kind of issues.
We considered approaches that could improve the performance of the proposed method by incorporating knowledge from the background collection, but were not able to implement them due to time limitations. We could extend our unsupervised and language-independent approach by incorporating some importance-based weighting scheme (such as tf*idf) into the score computation mechanism, in order to boost the scores of answers containing terms of high relevance within the context of a concrete article. Similarly, an instantiation of the language-augmented approach that enriches the queries and answers with semantically close terms, extracted by some clustering technique from the background collection, could also lead to a better performance.
Presently, we consider the best scoring sentences from the text as likely to contain the answer, based on the assumption that the answer is indeed contained in the provided supporting text. However, in a general setting, some or all of the best scoring sentences might not be `good enough', in the sense that their overlap with the question/answers text is very low. Introducing a minimal threshold parameter that eliminates sentences with too small overlap can for example result in unanswered questions - a choice which is encouraged by the evaluation system at the QA4MRE challenge. Also, it would allow for e cient scanning of very large collections of text, in addition to the corpus provided. Choosing a minimal threshold for text similarity can be for example done by comparing the distributions of the similarities between question/true answer and sentences containing answer and the rest of the similarities (false answers, arbitrary text, etc). 5
In this paper, we have described the array of algorithms that constitute our submission to the QA4MRE at CLEF2012 competition. The reported results reveal that our basic algorithm outperforms the random baseline irrespective of the language of the analyzed textual content, without resorting to any side resources nor language-speci c tools. We have shown that the results of the basic system can be improved signi cantly by incorporating a mechanism for majority voting based on the analysis of the individual translations included in the data collection. Lastly, we have shown that bidirectional statistical machine translation can introduce some amount of variation in the corpus that allows for improved overlap-based approaches.
This work was partially supported by the MOLTO European project (FP7-ICT247914). Ontotext AD is a part of the MOLTO consortium. highestSimilarity := -Inf; for each answer A(i, j), j=1..m s := delta(A(i, j) and R(i)); if s > highestSimilarity bestAnswer := A(i, j); highestSimilarity := s; endif endfor endfor
Output bestAnswer for Q(i); endfor end.
The OV Algorithm. The basic algorithm that underlies all of the described methods. Described in detail in section 2.1.