This article describes the Heidelberg contribution to the CLEF 2011 QA4MRE task for German. We focus on the objective of not using any external resources, building a system that represents questions, answers and texts as formulae in propositional logic derived from dependency structure. Background knowledge is extracted from the background corpora using several knowledge extraction strategies. We answer questions by attempting to infer answers from the test documents complemented by background knowledge, with a distance measure as fall-back. The main challenge is to specify the translation from dependency structure into a logical representation. For this step, we suggest di erent rule sets and evaluate various con guration parameters that tune accuracy and coverage. All of runs exceed a random baseline, but show di erent coverage/accuracy pro les (accuracy up to 44%, coverage up to 65%).
The long-term goal of NLP is to build computer systems that can communicate
with humans. Arguably, an important part of this enterprise is the development of
semantic analysis components which allow systems to understand the information
contained in the text and reason with it. This task is often called machine
reading [
Question Was ist das Ziel von UNAIDS?
What is the goal of UNAIDS? Answer Candidate 1 ein Abkommen mit dem Gesundheitsminister zu tre en to come to an agreement with the minister of health Answer Candidate 2 ein Konzert mit dem African Children's Choir zu geben to give a concert with the African Children's Choir Answer Candidate 3 zu verhindern, dass HIV-positive Frauen schwanger werden to avoid that HIV-positive women become pregnant Answer Candidate 4 UNAIDS' Au enwirkung zu vergro ern
to increase publicity for UNAIDS Answer Candidate 5 zu vermeiden, dass HIV von Muttern auf Kinder ubertragen wird (correct) to avoid that HIV is transmitted from mothers to children Answer Sentence Die Botschaft, die UNAIDS derzeit in der Welt verbreitet, ist, dass wir es scha en wollen, die Ubertragung des Virus von Mutter zu Kind bis 2015 praktisch zu eliminieren.
The message that UNAIDS is currently spreading is that we want
to manage to virtually eliminate the transmission of the virus from
mother to child until 2015.
not to be answerable by simple lexical matching. Answer validation in this setting
can be seen as a textual inference task [
For the rst (primary) of ten QA4MRE runs, the use of external resources like WordNet or paraphrase resources was prohibited. This constraint emphasizes the need for deeper analysis of the texts to (a) consolidate the semantic representations of the test documents and (b) acquire additional knowledge from the background collection. Table 1 shows an example question with its answer candidates and the sentence providing the answer in the test document. The example demonstrates the properties discussed above. None of the answer candidates are contained literally in the answer. To build an inference chain from the text to the correct answer candidate, systems need to acquire the knowledge that \having a goal" has something to do with \wanting to", that \avoiding" something can mean to \eliminate" it; that \HIV" is a \virus", and so forth. 2
At the time of QA4MRE 2011, there was no full- edged general-purpose textual
entailment system for German, only for the related task of question grading
[
Test Documents
Background
Collection 1. Syntactic Analysis and Normalization Predicate-Argument Relations
2. Semantic Relation Extraction
Synonymy and
Hyponymy Relations
3. Inference Module
we assume that every relevant piece of knowledge can be expressed as a ternary
relation. This includes both syntagmatic relations from actual text, e.g.,
dependency relations (Peter,subj,sleeps) and paradigmatic relations, i.e. type-level
semantic relations (natural gas,hypernym,energy source) and semantic relatedness
(book,relatedTo,story) acquired from the background corpus. We treat complex
structures (like dependency graphs) simply as sets of such binary relations, and
use the YAML le format as a universal exchange format among modules [
The overall structure of the system is shown in Figure 1. It consists of three modules. In the rst module, all types of language input (questions, answers, test and background documents) are preprocessed, dependency-parsed, and normalized, to meet the rst need outlined in the introduction (consolidated representation). The second module extracts semantic relations from the background document collection based on distributional similarity and shallow rules, thus addressing the second need from the introduction (acquisition of additional information). Finally, the third module attempts to infer each answer candidate, combined with the question, from the test document.
This module creates dependency-syntactic structures for the German input texts
(questions, answers, test and background documents). We rst perform sentence
splitting with the regular expression-based tokenizer by Sebastian Nagel1 and
then run the MATE dependency parsing toolkit [
Speci cally, we deal with the four most frequent phenomena that we identi ed.
The rst one is passive sentences, which we transform into an active representation,
including changing the edge labels. The second is prepositional phrases, where
we delete the preposition node and encode this information in the edge label.
The third one is coordinations, where we expand the second conjunct which
is by default only realized in a reduced form. These three phenomena can be
treated in German fairly similar to English [
We decided to concentrate on extracting two types of inference rules from the background corpus, namely hyponymy and synonymy. These two relations Regular Expression Pattern (\S+)/N. wie/\S+ zum/\S+ Beispiel/\S+ (\S+)/N. (\S+)/N. ist/\S+ eine?/\S+ (\S+)/N. (\S+)/N. wie/\S+ etwa/\S+ (\S+)/N. (\S+)/N. einschlie lich/\S+ (\S+)/N. (\S+)/N. und/\S+ andere/\S+ (\S+)/N. (\S+)/N. oder/\S+ andere/\S+ (\S+)/N. hypernym RE group 1 2 1 1 2 2 frequently contribute to bridging the \lexical gap" between answer candidates and textual evidence, and can be acquired using well-established methods.
The rst approach we followed was the extraction of hypernym-hyponym pairs
with so-called Hearst Patterns [
In contrast to synonymy, hyponymy is an asymmetrical relationship which
should therefore not be amenable to extraction with symmetrical similarity
measures. We therefore identi ed hypernymy using the asymmetrical Balanced
Average Precision similarity measure [
We take the classical \logical inference" approach to deciding whether an answer
follows from the text [
T , and the background knowledge base B (i.e., our inference rules), as logical
formulae and test the validity of the following formula:
(T ^ B) ` C
(1)
The main problem is how to represent T and C in logical terms. In an ideal world,
we would obtain a complete representation of the sentence meaning as provided by
a full syntax-semantics interface. However, wide-coverage translation of natural
language into logics is still essentially an open research problem. Additionally,
if T and A are represented by strong logical representations, then we need an
equally strong background knowledge base B which can, for example, license
paraphrastic variation between T and C (invent X ! be the rst to think of X ).
This problem has been approached e.g. by acquiring meaning postulates from
WordNet [
We address this problem by deriving weaker representations of the linguistic structures that essentially encode their dependency relations in propositional logic, experimenting with di erent parameters in the process. We take advantage of the fact that we have to solve only a multiple-choice task by searching for construction methods in which exactly one of the answers can be proved: if no answer can be proved, the representation is too strong; if more than one answer can be proved, it is too weak. The names of the binary parameters of this process are marked in boldface and will be used in the next chapter to explain the evaluation results.
Turning test documents into propositional formulae T . Our goal is to translate dependency structures into propositional logical formulae. The rst, optional, step is to prune the dependency structures by removing nodes with no semantic content (option DropPOS). If this option is selected, we remove all leaf nodes with the parts of speech ART (article) and APPR (prepositions2) as well as PWAT, PWAV, PWS (question words { see below for details). The next step is to decide on the shape of the literals. We developed four di erent rulesets which we will demonstrate on the example of the node \durchfuhren/perform" from the right-hand side of Figure 2 and its two outgoing edges (SB to \Arzt/doctor" and OA to \Operation/operation").
{ The Unary ruleset builds a literal for each dependency edge that consists only of the head and the dependent. For the above-mentioned edges, we obtain perform(doctor) and perform(operation). { The LabeledUnary ruleset builds a literal for each dependency edge like Unary, but also includes the edge label. For the example: SB(perform,doctor) and OA(perform,operation). { The Binary ruleset builds a literal for each pair of dependency edges with the same head without taking edges into account: perform(doctor,operation). 2 Note that prepositions should have been re-encoded as edge labels during the preceding syntactic normalization. { The Unrestricted ruleset turns each dependency subtree of depth one (i.e., each head with all of its dependents) into one n-ary literal. For the current example, the result is identical to the output of Binary.
The logical representation of a test document is the conjunction of all its literals. Several rulesets are activated, which leads to a certain amount of redundancy.
QA4MRE, answers are usually not complete propositions, but only words or short phrases. Such answers must be combined with the questions in order to obtain a complete representation of the proposition conveyed by the answer candidate, such as \Is it the goal of UNAIDS to increase publicity for itself" for answer candidate 4 in Table 1. We therefore translate the linguistic realizations of question and answer candidates into propositional logic as detailed above, and combine them into a single formula in a way that is in uenced by two parameters.
The rst parameter is WhSubstitution (question word substitution) concerns the handling of single-word answers. If this option is true, then we simply replace the interrogative pronoun (\who"/"what") in the question with the answer word. If it is false, then we attempt to reconstruct a logical representation, i.e., a literal, for the answer. Recall that our literals must correspond to dependency edges. We therefore search in the dependency representation of the test document for the most frequent head which had the answer word as its argument. As an example, assume that the test document mentioned medicine being an academic discipline. If the question concerns somebody's occupation, and the answer is \medicine", we then obtain as representation for this answer candidate the literal discipline(medicine), corresponding to the more detailed multi-word answer candidate \the discipline of medicine". We also construct answers by searching for heads which had hyponyms and synonyms of the answer as their argument. Additionally we also construct an answer by combining the answer word with the question's head (which in general leads to very similar results as question word substitution).
The second parameter is ANDonly which decides how the literals of question and answer candidate are combined into the formula C. If ANDonly is true, C is the conjunction of all literals of answers in the answer candidate, a representation that is optimized for precision. If ANDonly is false, representations for the answer and question are rst formed as disjunctions over the respective literals, and then combined by conjunction. This formulae is not very precise (since it is valid as soon as one literal of question and answer each is valid), but it may be informative enough for a multiple-choice selection task (cf. the discussion above).
the theorem prover CVC3 [
Run ID Unary LabeledUnary Binary Unrestricted WhSubstitution ANDonly AllKnowledgeAtOnce Threshold DropPOS RankUnprovable As discussed above, the basis of our approach is to attempt to prove the ve formulae in parallel for a growing body of background knowledge B, i.e., synonymy and hyponymy relations. Speci cally, we divide the relations generated by the knowledge extraction component (Section 3.2) into ve categories according to decreasing semantic similarity. In other words, we rst attempt to prove the answer candidates when taking only fairly certain background knowledge into account, and if this is not possible, we proceed to less certain background knowledge. As soon as at least one of the answers can be proved, we stop. This process is skipped by setting the option AllKnowledgeAtOnce, which adds the complete body of background knowledge at once.
At the end of this process, we can have di erent outcomes. If none of the answers can be proved, we do not make a prediction. If exactly one answer can be proved, we return this answer. If more than one answer can be proved, we require a tie-breaker to choose among these candidates. For this end, we score each derivation based on the similarity scores of the background knowledge that was employed, e ectively interpreting similarity scores as con dence values. Questions where more than one answer receives exactly the same score must however still be left unanswered. We also experimented with the option Threshold which introduced a xed threshold that answer scores had to exceed.
Finally, we experimented with a fallback mode called RankUnprovable where answers C that could not be proved (and were thus normally discarded) were included in the output of the system. The decision between these answers was made based on a simple distance metric that quanti es the \closeness" of answer candidates to test documents. 4
We submitted a total of nine runs, as permitted by the QA4MRE guidelines. Preprocessing and knowledge extraction were held constant across runs; we only varied the parameters of the inference step described in Section 3.3, as shown in Table 4. We originally planned to vary only one parameter at a time to observe the impact of parameters, but had to deviate from this idea to sample a larger part of the parameter space. Consequently, we decided to use a quantitative approach to analyze the in uence of run parameter on run performance.
We analyzed our runs with a logistic regression model which have previously
been used successfully to explain the in uence of features in data [
X i ixi (2) where p is the probability of the response variable taking some value and i the coe cient assigned to predictor xi. Model estimation sets the parameters to maximize the likelihood of the data. In the current setup, we are interested in analyzing the predictor weights: for each predictor xi, we can test the hypothesis that it signi cantly contributes to predicting the response.
We rst attempted to t a model to the o cial evaluation metric of QA4MRE
2011, namely C@1. However, we failed to nd any signi cant predictors. While
the fact that we have relatively few runs can de nitely play a role, we attribute
this failure to the property of C@1 to combine coverage and accuracy into a single
gure of merit [
Column 5 in Table 5 (Coverage) shows the coverage gures for our di erent runs. We see that the runs fall into three groups: relatively high coverage (run 9, 68%), medium coverage (runs 2-5 and 8, 40-55%), and low coverage (runs 1, 6, and 7, < 30%). The model with which we analysed these coverage gures revealed two signi cant predictors with a negative in uence on coverage when set to true, namely ANDonly and AllKnowledgeAtOnce. There was also one highly signi cant predictor with a positive in uence on coverage, namely RankUnprovable. runs 0 1,6,7 22 These results tie in well with our intuition about the inference approach that we use. Our model does does not make a prediction if one of two complementary situations take place: (a) none of the answers can be inferred, or (b) there are two or more answers with the same score among which we cannot decide. Since ANDonly means that the answer candidate C is a pure conjunction of the question and answer literals, setting it to true results in more cases of type (a). Conversely, RankUnprovable attempts to answer also questions where none of the answers is provable as a whole, reducing the number of (a) cases. Finally, if AllKnowledgeAtOnce is true, more ties occur, thus more cases of type (b).
To gain a better qualitative understanding of these cases, we make the simplifying, but largely warranted, assumption that our runs coincide on the questions that they can and cannot cover. This gives rise to four classes of questions with respect to coverage, shown on the left-hand side of Figure 3. Class 1 consists of questions that are always covered, even in an ANDonly setting. An example4 is question 1-1-3, What country is Nelson Mandela from?.
Class 2 consists of questions where the conjunction of answer and question cannot be inferred. An example is question 2-7-10, What could happen if the amount of CO2 in the atmosphere is not reduced?. This question, paired with the correct answer, results in a fairly complex formula for C, with more than ten literals. If not all literals are connected by conjunctions (ANDonly), if cannot be proved, but it can if ANDonly is set to false.
Class 3 coverts cases that cannot be decided by the prover, but can be decided by the distance metric when RankUnprovable is true. An example is 2-3-5, What could be a consequence of the reduction of arctic ice?. We cannot prove this question together with any answer because the question contains a description of a causal relation, \a consequence of", which is not expressed in the same way in the test document. The distance metric can, however, make a prediction.
Finally, there are questions (Class 4) which none of our runs covered, such as 1-1-5, What is Annie Lennox' profession? The correct answer would be musician. However, none of the answers can be proved, which means that runs 1 to 8 abstain from answering. Run 9 attempts to apply the distance metric, but runs into a distance tie between the answers musician and dancer both of which are equally close to the test document. A further contributing factor for this question was that the parser returned an incorrect analysis of the question, which directly led to an inappropriate representation for C. 4 For convenience, we present all examples in English. The IDs that we provide have the shape [TopicID]-[DocID]-[QuestionID].
The fourth column in Table 5 lists accuracy gures for the di erent runs, where accuracy is computed as the ratio of correctly answered questions to answered questions. Again, we see three groups, although the overall accuracy is quite low, and the groups are much closer together. One run has very low accuracy (run 5 at 23%), most runs show middling accuracy (runs 1-4, 8, 9) and two runs have fair accuracy (runs 6 and 7, the best run, with 44% accuracy). In terms of accuracy, all of our runs beat a random baseline (at 20%). Due to the fact that the accuracy gures are clustered together more closely, our logistic regression model yielded only one predictor with signi cant (positive) impact on accuracy, namely ANDonly. As discussed above, ANDonly leads to stronger answer representations which reduce the risk for false positives. Thus, ANDonly is a true precision/recall trade-o : activating it yields higher-precision runs, deactivating it higher-recall runs. Another factor which is not signi cant in the regression but which we consider important to explain the performance of run 5 is WhSubstitution (question word substitution). The heuristic we employed to deal with single-word answers for interrogative pronouns (cf. Section 3.3) yielded only mixed results: too frequently, the occurrences of the answer candidate in the test document that form the basis for its interpretation were not related to the question.
In sum, we can distinguish again, though at the risk of oversimpli cation, four groups of questions, shown on the right-hand side of Figure 3: (1), those that are answered correctly by all runs; (2), those where question word substitution leads to wrong answers; (3), those that can be answered correctly if ANDonly is true; and (4), those that no run manages to answer correctly.
An interesting example of group (3) is question 1-3-10, Who wrote 'People do stupid things - that's what spreads HIV' ?, with the correct answer 1: Elizabeth Pisani. Two other answer candidates show a lot of overlap with the correct answer (a friend of Elizabeth Pisani's and Elizabeth Pisani's brother ). If ANDonly is false, and consequently not the complete answer has to be proved, some of the runs mistakenly return one of the two confounds as the correct answer.
An analysis of the group (4) errors made by run 7, our highest-accuracy run, highlights the limitations of our current system architecture. One important limitation is the fact that we consider literals (i.e., individual dependency edges) largely in isolation. This makes our system vulnerable to questions where (parts of) answers are already contained in the test document. For example, one of the answer candidates for question 2-5-4, Why are there more wild res now?, is Global warming, a term which occurs in the test document several times. Since for why-questions, we in e ect try to prove a conjunction of question and answer, we check whether the test document contains There are more wild res and Global warming. This is the case, and we return Global warming as the (incorrect) answer { the correct answer would have been Less water.
A second frequent problem is the inadequacy of our background knowledge
extraction. For example, question 2-5-2 is Where is the third largest ice mass in
the world?, with the correct answer candidate being Asia. The test document
mentions only the Himalaya (mountains). If we had had access to the meronymy
(or location) relation the Himalaya is a part of (or located in) Asia, we would
have been able to prove this answer, but we did not attempt to extract meroynym
relations. Consequently, our systems attempted to prove increasingly weaker
versions of the answers and ended up with incorrect answers. More generally
speaking, the problem is that our current system has a very impoverished notion
of background knowledge. Even within the covered relation (hyponymy), coverage
is far from perfect. Outside hyponymy, a large number of relevant semantic
relations are excluded both at the lexical level (e.g., meronymy or entailment
relations between verbs) and at the lexico-syntactic level (paraphrases), all of
which can play an important role in entailment [
In our contribution to the CLEF 2011 QA4MRE task, we focussed on answer validation completely without the use of any external knowledge resources, merely extracting some background knowledge from the provided background corpora. Our approach was fairly straightforward and consisted in a fairly direct translation of dependency trees into proposional logic formulae, with each edge contributing one literal. Several parameters determine the strength of the resulting formulae. We implemented a back-o proving setup where we proceeded from stronger to weaker logical representations until we were able to prove at least one of the answers. Cases of ties are resolved by a simple distance metric.
We were happy to nd that our best runs showed accuracies of around 40%; however there is a clear inverse relation between coverage and accuracy, with the best runs showing the lowest coverage. This clearly shows that improvements are necessary with respect to both the precision and the recall of our approach, and our data analysis has yielded a number of clear directions for improvements. As for recall, we mainly need to improve the knowledge acquisition techniques with which we extract background knowledge from large corpora and scale them up to a larger set of semantic relations, notably paraphrase. With regard to precision, we feel that we need to improve the handling of di erent question types and go beyond simply matching the linguistic material in the question with the test document. In particular for causal questions, our current approach is much too restricted. More generally, we would like to generalize our current text normalization step into a more sophisticated syntax-semantics interface that maps input texts onto \more semantic" knowledge representation structures.