The paper features MAVE (MultiNet answer verification), a system for validating results of question-answering systems which serves as a testbed for robust knowledge processing based on multi-layered extended semantic networks (MultiNet [4]). The system utilizes logical inference rather than graph matching for recognising textual entailment, which makes it easily extensible by further knowledge encoded in logical axioms. In order to ensure robustness, the prover is embedded in a relaxation loop which subsequently skips 'critical' literals until a proof of the reduced query succeeds. MAVE uses the number of skipped literals as a robust indicator of logical entailment. Although the detection of 'critical' literals does not necessarily result in the minimal number of non-provable literals, the skipped literal indicator performed very well in the AVE experiments. MAVE parses the hypothesis strings and is therefore sensitive to syntactic errors in hypothesis generation. A regular correction grammar is applied to alleviate this problem. The system also parses the original question (when available) and tries to prove it from the snippet representation. The skipped-literal count for the question is then combined with a similarity index for hypothesis vs. found answer. This method boosts recall by up to 13%. Additional indicators are used for recognizing false positives. The filter increases precision by up to 14% without compromising recall of the system.
1.1
MAVE is a knowledge-based system for answer validation which uses deep linguistic processing and logical inference for recognising textual entailment. The system assumes XML input as specified in the AVE 2006 description. A validation candidate p consists of a hypothesis string constructed by substituting the answer of the QA system into the original question, and by the extracted snippet which contains the relevant text passage. Optionally, the question string can also be given. MAVE uses a standard cascaded architecture for processing validation candidates. The sequence of processing steps involves preprocessing, linguistic analysis, and indicator extraction (the results of logical inference are also represented by indicators). The final aggregation step determines the YES/NO decision and confidence score from a combination of the indicators. These processing stages and the involved components of MAVE are detailed in the following.
Preprocessing The hypotheses are very often syntactically ill-formed or semantically defective due to the
primitive mechanism used for generating hypotheses from fixed templates. For example, the hypothesis
might contain the phrase ‘im Jahre 26. April 1986’ (En: ‘in the year April 26, 1986’) rather than listing
the date only. Sequences of two prepositions are also often found, e.g. ‘in in Lillehammer’ rather than ‘in
Lillehammer’. These errors deteriorate the results of syntactic parsing, and a set of regular expressions is
therefore applied in the preprocessing stage which corrects many of them. For example, sequences of local
prepositions are reduced to a single local preposition. The snippet strings often need correction as well.
Syntactic errors in the snippets mostly result from wrong XML-text conversion (contents of XML elements
are concatenated without proper punctuation), from wrong segmentation (snippet extraction disregards
sentence boundaries), from named entity recognizers which collapse multi-word units into new tokens like
‘Gianni Versace’, and from primitive mechanisms for reference resolution which simply replace pronouns
by a named entity they most likely refer to. Some of these errors can be fixed by regular correction patterns,
but the detoriation of extracted snippets by artefacts of the QA systems remains an issue.
Linguistic analysis The WOCADI parser [
Indicator extraction A total of 46 indicators is extracted from the hypothesis, the snippet and from the question string, which include character-based indicators (like the length of the snippet or the proportion of non-alphabetic characters), lemma-based indicators (like the hypo-triviality ratio described below), concept-based indicators (like the presence of concepts which indicate negative polarity contexts), syntaxbased indicators (e.g. number of sentences in the snippet), indicators computed from the semantic network representation (like the indicator hypo-lexical-focus described below), and finally proof-based and matching-based indicators. It was not yet possible to consider all of these indicators in the scoring function of MAVE because there was no development collection for German. The eleven indicators which were chosen for the scoring criterion are explained at the end of this section.
Robust entailment proving The most important indicators for deciding answer correctness are
determined by the MAVE prover, an improved version of the resolution-based inference engine for MultiNet
described in [
The background knowledge base of the first MAVE prototype comprises 2,484 basic facts which interrelate 4,666 lexicalized concepts. About 2,000 of these lexico-semantic relationships were supplied by the computational lexicon HaGenLex. A typical example is the MultiNet relation CHEA, which holds between events described by verbs like ‘aktivieren’ (En: ‘to activate’) and the corresponding abstractum ‘Aktivierung’ (En: ‘activation’). The remaining 500 facts capture important relationships not covered by HaGenLex, e.g. about the connection between states (‘Spain’), state adjectives (‘Spanish’), and inhabitant names (‘Spaniard’). Apart from the facts, MAVE uses 103 implicative rules. 38 of these rules are so-called ‘R-axioms’, which define key properties of the MultiNet relations. The remaining 65 rules include meaning postulates for frequent verbs not covered by the HaGenLex relations, and also a rudimentary domain modelling which covers a few important topics like the birth and death of a person, being awarded a prize, and being a member or a leader of an organization. These topics were identified based on the known questions of QA@CLEF 2004 and 2005.
HaGenLex is also the source of more than 1,000 high-quality synonyms which are used for normalizing concept names. 525 additional synonyms or near-synonyms for frequent terms were manually compiled from OpenThesaurus synsets. The resulting system comprises 636 synonym classes. Not only the representations of query and snippet, but also the fact knowledge base and the implicative axioms are automatically normalized by replacing known synonyms with a canonical representative for the synset. This normalization increases coverage of this model because distinct lexical constants are mapped to a single canonical representation. The background knowledge which refers to the canonical representation is then applicable to all lexical variants of expressing the underlying concept.
Due to lack of time, it was not possible to integrate additional resources like GermaNet. This means that knowledge modeling in the first MAVE prototype is rather sparse. However, most of the hypothesis-snippet entailments or question-snippet entailments in the AVE test set are not very knowledge intensive, and the robust inference mechanism of MAVE is specifically designed for absorbing a few gaps in knowledge modeling.
Defining the scoring criterion The following basic scoring criterion is used by MAVE. The returned number reflects the imperfection score of the considered hypothesis-snippet pair. A perfect logical entailment is scored 0, while an entailment relationship with slight errors (detailed below) will be scored by a small integer depending on the number of detected mismatches. A large value of 1000 will be returned to indicate that the pair should be rejected in any case. The imperfection score imp-score(p) of hypothesis pair p is given by the expression: (max (* (max (? (>= hypo-triviality 0.8) 0) (= hypo-num-sentences 2)) 1000) (min (? (max (* (max (< hypo-collapse 0.7) hypo-lexical-focus) 1000)
(+ hypo-missing-constraints hypo-failed-literals)) 1000) (? (max (* question-lexical-focus (= hypo-delta-matched 0) 1000) (+ question-failed-literals question-missing-constraints (- hypo-delta-concepts hypo-delta-matched))) 1000))) Indicator evaluation was implemented in the Scheme programming language which explains the prefix notation of operators in the above expression. Note that the indicators can be undefined in certain cases. The functions max, +, - and * are assumed to be defined only if all arguments are defined. The special expression (? A B) is used to handle undefined values. It returns A if A is defined and B otherwise. The basic indicators on which the computation of the imp-score is based are defined as follows. • hypo-triviality – Lemma repetition ratio.
This criterion serves to identify trivial hypotheses like ‘Gianni Versace was Gianni Versace’ which are logically valid but not acceptable as an answer. In order to detect such wrong positives, the hypo-triviality criterion measures the ratio of lemmata which occur an even number of times.1 Trivial hypotheses of the above kind result in a high repetition score. Empirically, a threshold of hypo-triviality ≥ 0.8 was found to identify such hypotheses reliably. In the case that there is no sufficient data for computing the hypo-triviality indicator (because the syntactic processing failed completely), the assumption of a non-trivial hypothesis is a reasonable default. This assumption is captured by the expression (? (>= hypo-triviality 0.8) 0), i.e. no error condition by default. • hypo-num-sentences – The number of sentences in the hypothesis.
Due to odd punctuation and syntax errors, the parser might wrongly consider a hypothesis as consisting of two sentences although in fact we only have single-sentence hypothesis. We therefore know that there is something wrong with the analysis of the parser if hypo-num-sentences = 2. Such hypotheses get the default evaluation NO. 1Certain lemmata like German ‘sein’ (En: ‘be’) will be filtered out before determining this ratio. • hypo-collapse – Query extraction control index
When there is no perfect parse of a sentence, the result of semantic analysis can be incomplete. Compared to the correct query representation, the constructed logical query will contain too few literals in this case and thus be underspecific. In order to detect this cause of false positives, we define a query extraction control measure
hypo-collapse = ##hhyyppoot-hceosnitse-nlti-tweorradlss which relates the size of the constructed query (number of literals in the representation of the hypothesis) and the number of content words in the hypothesis string. A value of hypo-collapse < 0.7 was found to be a reliable indicator for the case that the logical representation is too small compared to the size of the hypothesis. A proof of the logical hypothesis is not useful for judging answer correctness in this case because it likely corresponds to a false positive. • hypo-lexical-focus – Hint at potential false positive
This binary criterion identifies a situation where the logical hypothesis representation is too permissive compared to the intended meaning of the hypothesis. This problem in query construction affects mainly hypotheses involving measurable properties (like ‘8585 meters high’). A modification of the parser will eliminate the need to consider this case in the future. • hypo-missing-constraints – Control index for numerical constraints
Apart from regular words, the hypothesis can also contain numbers. These numbers must occur as restrictions in the constructed logical representations (for example, a restriction of the year to 1994). Although the syntactic-semantic parser normally treats these numeric constraints as expected, it turned out that they are occasionally dropped when a complete parse of the sentence fails. The indicator hypo-missing-constraints was introduced to recognize this case. It is defined as hypo-missing-constraints = #numerical-tokens-in-hypothesis
−#numerical-constraints-in-logical-hypothesis.
The imp-score criterion will treat each missing constraint like a skipped literal which could not be established by logical inference. • hypo-failed-literals – Number of non-provable literals
As explained above, the prover is embedded in a relaxation loop which skips non-provable literals until a proof of the rest literals succeeds. In this way, we obtain the indicator hypo-failed-literals (number of non-provable literals in the hypothesis representation). A value of 0 means strict logical entailment, while a small integer indicates a few mismatches or knowledge gaps. • question-failed-literals – Number of non-provable literals for the question
The MAVE system also tries to prove the original question (rather than the hypothesis) from the snippet. The indicator question-failed-literals counts the number of literals in the logical question representation which had to be skipped in order to prove the remaining question literals. • question-missing-constraints – Control index for numerical constraints in the question The indicator counts the number of numeric tokens in the original question which are not expressed in the logical representation of the question. The evaluation criterion imp-score treats these missing constraints like a skipped literal which cannot be established in the logical proof. See indicator hypo-missing-constraints for motivation. • question-lexical-focus – Hint at potential false positive
Due to a bug in semantics construction, the logical representation of questions involving measurable adjectives is too permissive in a few cases, which means a higher risk of a false positive. These situations are detected by the binary indicator question-lexical-focus, the analogue of hypo-lexical-focus for questions. The problem will be fixed in future revisions of MAVE and the indicators can then be omitted. • hypo-delta-concepts – Number of answer words in the hypothesis
A proof of the original question will only support the given hypothesis if the answer from which the hypothesis has been built is similar to the answer found in the proof of the question. As the basis for establishing such a similarity, we extract the answer part of the hypothesis (knowing that the hypothesis has been constructed from the question and from the original answer determined by the QA system). hypo-delta-concepts counts the number of content-bearing tokens in the hypothesis which likely stem from the original answer of the QA system and not from the question. • hypo-delta-matched – Number of matched answer words
In order to relate the answer of the QA system to a proof of the original question based on the snippet, we use the matching coefficient hypo-delta-matched. Based on the proof of the logical question representation over the snippet and the known origin of literals in one of the sentences of the snippet, we first identify that sentence in the snippet which contains most of the literals supporting the proof. The content-bearing and numeric tokens in the answer part of the hypothesis are then matched against the lexical concepts and cardinality specifications in the MultiNet representation of this central sentence.2 In this way, we obtain the number of those answer words which can be matched with the selected snippet sentence. The focus on a most relevant sentence of the snippet helps detect the case that a hypothesis refers to parts of the snippet not related to the answer. Defining the selection criterion A simple threshold θ is used to determine YES/NO decisions from the basic evaluation score as defined above, i.e.
select(p) = ( YES : imp-score(p) ≤ θ
NO : else .
Thus all hypothesis-snippet pairs with an imperfection score imp-score ≤ θ will be evaluated YES, while those items with more than θ imperfections will be rejected.
Defining the confidence ranking The assignment of confidence scores is based on the assumption that for YES decisions, the results with the least number of imperfections (as expressed by the evaluation criterion) are most reliable. Specifically, results with an imperfection score of 0 (no mismatches at all) should be fully reliable with score 1, and all other YES decisions should get smaller but positive confidence evaluation which depends on the number of detected errors. A simple linear function is used to obtain this behaviour. As to the NO decisions, a larger number of imperfections (non-provable literals) means more evidence that the answer is indeed false. Assuming that σ or more non-provable literals (and other imperfections) mean 2Matching is performed on the level of lexical concepts in order to profit from lemmatization and synonym normalization. ‘totally wrong’, we capture this as follows, imp-score(p) 1 − η θ + 1 confidence(p) = min 1, imp-score(p) − θ − 1 σ − θ − 1 : select(p) = YES : else where 0 ≤ θ < σ − 1. The parameter 0 < η < 1 + θ1 can be used to balance the YES scale of confidence scores with the NO scale of confidence scores. 2
The two submitted runs both instantiate the general scheme for selecting valid hypothesis and for assigning confidence scores.
• In the recall-oriented first run, θ = 2 mismatches (‘imperfections’) were allowed for YES decisions. • In the more precision-oriented second run, θ = 1 mismatch was allowed for YES decisions. We chose σ = 8 in both runs, i.e. the confidence score for NO decisions will reach 1 if the imp-score detects 8 or more mismatches. It was intended to use η = 1 in all runs. However, the confidence scores in the submitted run #1 were based on η = 1.2 by mistake. 3
The viability of the basic approach of robust inferential entailment checking is witnessed by Table 1 which lists the results of MAVE in the answer validation exercise. ‘Accuracy’ measures the proportion of correct decision, and CWS is the confidence-weighted score. 3 Although the approach does not search for a minimal set of failed literals, but only skips literals according to a simple ‘longest partial proof’ strategy, the computed failed literal counts are obviously significant with respect to the validity of entailment: There is a consistent decrease in precision if more imperfections θ (usually skipped literals) are allowed, but also the intended boost in recall. The table further reveals that the two submitted runs (which admit one or two mismatches) represent the best compromise of all evaluation measures. Assuming provability of all literals (θ = 0) is too restrictive in terms of recall, while admitting θ = 3 or more mismatches considerably lowers precision.
MAVE features the use of question proofs for validating hypotheses, by comparing the answer part of the hypothesis with the lexical concepts in that snippet sentence which contributes most to the proof of the question. This mechanism is intended to increase recall when the hypothesis is syntactically ill-formed. In this case, no proof of the hypothesis is possible because no logical representation can be constructed. However, the question can usually be parsed so that a proof of the question can be tried. The hypothesis will then be compared with the answer determined by the proof of the question in a way which does not assume a parse of the hypothesis (i.e. only based on results of lexical analysis). To see the benefits of this technique, consider Table 2 which lists the results when no question-related indicators are used. 4 For θ = 1, the recall decreases by 9.6% when no question-related information is available; for θ = 2, the question 3For computing the confidence weighted score (CWS), σ = 8 and η = 1 were used throughout. Notice that for θ = 2, exactly the same results are obtained for η = 1 and η = 1.2, i.e. the numbers shown for θ = 2 indeed correspond to the submitted first run. 4i.e. when omitting the second argument of min in the definition of imp-score(p). 11.2% for θ = 1 and 10.0% for θ = 2) but remains on a high level, and we get an overall improvement as witnessed by the higher f-measure and accuracy in the submitted runs. Table 3 shows that this increase in performance can only be achieved when both hypothesis and question indicators are combined. The table lists the results of MAVE when no information about hypothesis provability is used.5 In fact, there is a clear decay in recall when deciding the validity of a hypothesis only based on the proof of the question and a subsequent matching with the hypothesis. Interestingly, the simplistic method of validating the hypothesis from a proof of the question and a comparison with the relevant snippet segment does not result in a loss of precision.
The definition of imp-score(p) also involves indicators (like hypo-triviality, hypo-collapse or question-lexical-focus) which serve to detect false positives. Table 4 shows the results obtained when omitting these indicators from the scoring function. Specifically, it demonstrates that the proposed indicators are effective in removing false positives, because precision drops by 14.4 percent when the 5i.e. when omitting the first argument of min in the definition of imp-score(p). false positive indicators are ignored. This effect is most marked when the recall base is small (most false positives like ‘Gianni Versace is Gianni Versace’ are tautologies and thus provable for θ = 0). Recall is not altered significantly, i.e. the indicators are sufficiently selective for removing mostly false examples. 4
We have presented the MAVE system for robust inferential answer validation in the MultiNet framework. Despite its small knowledge base, the system works reasonably well in the AVE exercise – mainly because most negative cases are strikingly false and easily recognized. Moreover, a relevant number of the positive cases need limited inference or are even trivial (i.e. constructed from a substring of the snippet). Thus AVE systems can be pretty simple-minded as long as QA systems use simple techniques, and they must become smarter only as the QA systems which generate the answers become smarter as well. Apart from that, the relative success of the MAVE prototype is explained by its robust proving strategy which tolerates a few mismatches and gaps in the coded knowledge. The most obvious improvement of MAVE will be the integration of large lexico-semantic resources like Germanet; this step is necessary to boost recall beyond 50%. Now that the annotated AVE 2006 corpus for German is available as a development collection, the design of improved scoring metrics and training of statistical classificators also become an option.