This year, besides providing support to other groups participating in cross-language Question Answering (QA) tasks, and submitting runs both for the monolingual Italian and the cross-language Italian/English tasks, the ITC-irst participation in the CLEF campaign concentrated on the Answer Validation Exercise (AVE). The participation in the AVE task, with an answer validation module based on textual entailment recognition, is motivated by our objectives of (i) creating a modular framework for an entailment-based approach to QA, and (ii) developing, in compliance with this framework, a stand-alone component for answer validation which implements different approaches to the problem.
This year the ITC-irst activity on Question Answering (QA) has been concentrated on two main directions: system re-engineering and entailment-based QA. The objective of the re-engineering activity is to transform our DIOGENE QA system into a more modular architecture whose basic components are completely separated, easily testable with rapid turnaround of controlled experiments, and easily replaceable with new implementations. In this direction, our long-term ambition is to make all these components (or even the entire system) freely available in the future to the QA community for research purposes.
Adhering to this perspective, the objective of the research on entailment-based QA aims at
creating a stand-alone package for Answer Validation (AV), which implements different strategies
to select the best answer among a set of possible candidates. Besides our well tested statistical
approach to the problem, described in [
Up to date we are halfway in this ambitious roadmap, and unfortunately the results of our participation in CLEF reflect this situation. While most of the original system’s components are now separated from each other, little has been done to improve their performance, and a number of bugs still affect the overall system’s behavior. The main improvements concern the substitution of the MG search engine with Lucene (an open-source, cross-platform search engine, which allows for customizable document ranking schemes), and the extension of the Answer Extraction component with a new WordNet-based module for handling “generic” factoid questions (i.e. questions whose expected answer type does not belong to the six broad named entity categories currently handled by DIOGENE). Both these improvements, and the results achieved by DIOGENE in the Monolingual Italian and cross-language Italian/English tasks are presented in Section 5.
As for the AV problem, even though the new component based on textual entailment recognition has not been integrated in the new DIOGENE architecture, it has been separately evaluated within the CLEF-2006 Answer Validation Exercise (AVE). The description of such component, its role in the upcoming new DIOGENE architecture, together with the results achieved in the AVE task represent the focus of this paper (Sections 2, and 3, and 4).
ITC-irst also provided support to the University “A.I.Cuza” of Iasi, Romania, involved in the cross-language Romanian/English QA task. Such support (concerning the document retrieval, answer extraction, and answer validation phases) is not documented in the paper as it is based on the same components used for our QA submissions. 2
Answer validation is a crucial step in the Question Answering loop. After a question processing phase, where a natural language question is analyzed in order to extract all the information (e.g. relevant keywords, the expected answer type) necessary for the following steps of the process, a passage retrieval phase (where a ranked list of relevant passages is extracted from a target collection), and an answer extraction phase (where possible answers are extracted from the retrieved passages), QA systems are usually required to rank a large number of answer candidates, and finally select the best one.
The problem of answer ranking/validation has been addressed in different ways, ranging from the use of answer patterns, to the adoption of statistical techniques and other type checking approaches based on semantics.
Pattern-based techniques (see for example [
Statistical techniques [
Semantic type checking [
Most of the proposed approaches, however, are not completely suitable to model all the
linguistic phenomena that may be involved in the QA process. This particularly holds when the
challenge moves from factoid questions (questions for which a complete answer can be given in
a few words, usually corresponding to a named entity) to more complex ones (e.g. temporally
restricted questions, “why questions”, “how questions”). In order to capture the deeper semantic
phenomena that are involved in determining answerhood, more complex techniques that
approximate the forms of inference required to identify valid textual answers become necessary. In this
direction, a more complex approach has been recently proposed by [
Focusing on the answer validation problem, our work builds on the same hypothesis that recognizing a textual entailment relation between a question and its answer can enhance the whole QA process. The following Sections provide an overview of the problem, together with a description of the component designed for the participation to the AVE task at CLEF 2006.
While the language variability problem is well known in Computational Linguistics, a general
unifying framework has been proposed only recently in [
Recently, the task of automatically Recognizing Textual Entailment (rte) attracted a
considerable attention and has been included among the tasks of the PASCAL Challenge [
As the following examples illustrate, the task potentially covers almost all the phenomena involved in language variability. Entailment can in fact be due to lexical variations (example 1), syntactic variations (example 2), semantic inferences (example 3), or complex combinations of all these levels.
Due to the variety of phenomena involved in language variability, one of the crucial aspects for
any system addressing rte is the amount of knowledge required for filling the gap between T and
H. The basic inference technique shared by almost all the systems participating in PASCAL-rte is
the estimation of the degree of overlap between t and h. Such overlap is computed using a number
of different approaches, ranging from statistic measures like idf, to deep syntactic processing and
semantic reasoning. Some of them are relevant or similar to our methodology, as it will be described
in the rest of the paper. For instance, the system described in [
Similarly, in [
Finally, a method for recognizing textual entailment based on graph matching is described in
[
Our approach to rte (fully described in [
Edit operations are defined at the level of single nodes of the dependency tree (i.e. transformations on subtrees are not allowed in the current implementation). Since the tree edit distance algorithm adopted does not consider labels on edges, while dependency trees provide them, each dependency relation R from a node A to a node B has been re-written as a complex label B-R concatenating the name of the destination node and the name of the relation. All nodes, except the root of the tree, are re-labeled in such way. The algorithm is directional: we aim to find the better (i.e. less costly) sequence of edit operation that transform t (also called the source) into h (the target ). According to the constraints described above, the following transformations are allowed: • Insertion: insert a node from the dependency tree of h into the dependency tree of t.
When a node is inserted it is attached with the dependency relation of the source label. • Deletion: delete a node N from the dependency tree of t. When N is deleted all its children are attached to the parent of N. It is not required to explicitly delete the children of N as they are going to be either deleted or substituted on a following step. • Substitution: change the label of a node N1 in the source tree into a label of a node N2 of the target tree. Substitution is allowed only if the two nodes share the same part-of-speech. In case of substitution the relation attached to the substituted node is changed with the relation of the new node. 3.1.1
RTE System Architecture Our rte system is composed by the following modules, showed in Figure 1: (i) a text processing module, for the preprocessing of the input t/h pair; (ii) a matching module, which performs the mapping between t and h; (iii) a cost module, which computes the cost of the edit operations.
The text processing module creates a syntactic representation of a t/h pair and relies on a
sentence splitter and a syntactic parser. For sentence splitting we used MXTerm [
The matching module, which implements the edit distance algorithm described in Section
3.1, finds the best sequence of edit operations between the dependency trees obtained from t and
h. The entailment score of a given pair is calculated in the following way:
where ed(T , H) is the function that calculates the edit distance cost and ed(, H) is the cost of
inserting the entire tree′ h. A similar approach is presented in [
The matching module makes requests to the cost module in order to receive the cost of each single edit operation needed to transform t into h. For this purpose, we use different cost estimation strategies, based on the knowledge acquired from different linguistic resources. In particular: • Insertion. The intuition underlying insertion is that its cost is proportional to the relevance of the word w to be inserted. We measure the relevance in terms of information value (inverse document frequency (idf )), position in the dependency tree, and ambiguity (in terms of number of WordNet senses). • Deletion. Deleted words influence the meaning of already matched words. This requires that the evaluation of the cost of a deleted word is done after the matching is finished, with measures for estimating co-occurence (e.g. Mutual Information). • Substitution. The cost of substituting a word w1 with a word w2 can be estimated considering the semantic entailment between the words. The more the two words are entailed, the less the cost of substituting one word with the other. We have defined a set of entailment rules over the WordNet relations among synsets, with their respective probabilities. If A and B are synsets in WordNet 2.0, then we derived an entailment rule in the following cases: A is hypernym of B; A is synonym of B; A entails B; A pertains to B.
The difficulty of the rte task explains the relatively poor performance of the systems participating in the PASCAL Challenge. Most of them, in fact, achieved accuracy results between 52-58% at PASCAL1 and 55-65% at PASCAL2, with a random baseline of 50%. Even though our system’s performance is in line with these results, (55% at PASCAL 1 and 60.5% at PASCAL 2), our 60% accuracy on the QA pairs in the PASCAL2 test set demonstrates the potentialities of integrating rte in a QA system, and motivated our participation in the CLEF-2006 AVE task. 3.2
In terms of the approach to RTE previously described, the answer validation task can be attacked as follows:
A candidate answer ca to a question q is a correct answer if and only if the text from which ca is extracted entails the affirmative form of q, with ca inserted into the appropriate position.
Q:“Which country did Iraq invade in 1990? ” A:“Kuwait ” In our approach, the solution to the problem consists in determining if the text t from which ca is extracted (for instance: “The ship steamed into the Red Sea not long after Iraq invaded Kuwait in 1990.”), entails the affirmative form h of q (i.e. “Iraq invaded the country of Kuwait in 1990.”). Document
Answer Question Hypotheis Generator
RTE Module
YES/NO
A possible architecture of an answer validation component based on such rte-based approach is depicted in Figure 3.2. In such architecture, the edit distance algorithm is launched over the output of two pre-processing modules, namely the Text Extractor, and the Hypothesis Generator.
The former, in charge of producing t, extracts from the document containing the candidate answer several sentences that will serve as input to the rte module. As normally only one of these sentences contains the answer, the Text Extractor should be able to deal with different discourse phenomena (such as anaphora, ellipses, etc.) before constructing the final h to be passed to the rte module.
The latter, in charge of producing h, transforms the input question into its affirmative form
and inserts the answer on the proper position. To this aim, we developed a rule-based approach
which addresses the problem by converting the dependency tree of the question into a syntactic
template [
Finally, the rte module produces a YES/NO answer, together with a certain confidence score. 4
As the PASCAL and AVE evaluation scenarios are slightly different, the datasets provided by the organizers of the two challenges also differ. In particular, the input text portions (candidate answers) contained in the AVE dataset are document fragments extracted from the participants’ submissions to the CLEF QA track. Under these conditions, the complexity of the AVE task is undoubtedly higher due to the fact that: (i) there are no warranties about the syntactic correctness of those fragments; (ii) there are no constraints about their length, and (iii) the answer itself is not explicitly marked within them. As a consequence, under the rte-based framework proposed in the previous sections, the availability of a module for transforming the text portions (candidate answers) into valid t inputs for the RTE module becomes crucial.
Unfortunately we were not able to complete this module (the Text Extractor in Figure 3.2) in time for the AVE submission deadline. In order to submit a run, we used the text portions provided by the organizers as ts without any processing. As a result, we were not able to process the 129 pairs that actually didn’t contain text (but only document identifiers), and we assigned them a NO response in the final submission.
The results achieved by our system are reported in Table 1. These results are not satisfactory, as they they approximate the behavior of a random approach. As stated before, a huge drawback for our system is the missing module for converting the document fragments into valid ts for the rte component. The absence of such module led to a significant drop in the performance of the parser, which is a crucial component in our rte-based architecture. With these circumstances we can not draw definitive conclusions about the performance of our system, which requires at least a grammatically correct input. We assume that introducing the missing module we will significantly improve the performance of the system, allowing to reach results comparable with the ones obtained in the PASCAL 1 & 2 challenges.
Our participation in the CLEF-2006 QA task is the first step on the way of developing a new and improved DIOGENE system. The leading principle of this re-engineering activity is to create a modular architecture, open to the insertion/substitution of new components. Another long-term objective of our work on QA, is to make the core components of the system freely available to the QA community for research purposes. In this direction, new implementation guidelines have been adopted, starting from the substitution of Lisp with Java as the main programming language. As stated before, our choices we were led by the following objectives: 1. Modularity - Re-build the old monolithic system into a pipeline of modules which share common I/O formats (xml files). 2. Configurable - Allow for the capability of configuring the settings of the different modules with external configuration files. We have developed a common xml schema for configuration description. 3. Evaluation - Provide the capability of performing fine-grained evaluation cycles over the individual processing modules which compose a QA system. In order to make a step-tostep evaluation of our modules we started to build reference datasets. Having such, the results of each processing step can be compared against them. At this stage, we focus on factoid questions from the TREC-2002 and TREC-2003 testsets. Exploiting such data, for instance, we are now able to perform separate tests on the Document Retrieval and the Candidate Answer Extraction steps. In the new architecture, evaluation modules are completely detached from processing modules. The former are independent from specific datasets and/or formats, enabling a quick porting along with the evolution of the task.
In spite of the huge effort in the modularity direction (now all the system’s modules have been
completely detached), little has been done to improve the behavior of the core components. The
only improvements over the system described in [
As for document retrieval, this year’s novelty is the substitution of the MG search engine
[
As for answer extraction, we improved the candidate answers’ selection process by developing a more effective way to handle “generic” factoid questions (i.e. questions whose expected answer type does not belong to the six broad named entity categories previously handled by DIOGENE). Generic questions are now handled extracting as possible answer candidates all the hyponyms of the question focus that are found in the text passages returned by the search engine. For instance, given the question Q:“What instrument did Jimi Hendrix play?”, the answer extraction module will select “guitar” as a possible answer candidate as it is an hyponym of “instrument”, the focus of the question.
Apart from these modifications, the runs submitted to this year’s edition of the CLEF QA task (results are reported in Table 2) have been produced with the old system’s components, and reflect the “work-in-progress” situation of DIOGENE.
task Italian/Italian Italian/English