We describe a method for recognizing textual entailment that uses the length of the longest common subsequence (LCS) between two texts as its decision criterion. Rather than requiring strict word matching in the common subsequences, we perform a flexible match using automatically generated paraphrases. We find that the use of paraphrases over strict word matches represents an average F-measure improvement from 0.22 to 0.36 on the CLEF 2006 Answer Validation Exercise for 7 languages.
Recognizing textual entailment has recently generated interest from a wide range of Natural
Language Processing related research areas, such as automatic summarization, information extraction
and question answering. Advances have been made with various techniques, such as aligning
syntactic trees and word overlap. While there is still much room for improvement, Vanderwende
[
Proposed directions to cross this boundary include using logical inference, background
knowledge and paraphrasing [
In this example, text and hypothesis use different words to express the same meaning. Although deep inference is required to recognize that a mother is part of the family, and that daughter and baby in this context most likely refer to the same person, most variation occurs on the surface level. For instance, announced in the hypothesis could be replaced by said without changing its meaning. Similarly, the phrases the United States and the US would not be matched by a system relying solely on word overlap.
The criterion that our system uses to decide whether a text entails a hypothesis is the length of the longest common subsequence (LCS) between the passages. Rather than identifying the LCS using word matching, our system employs an automatic paraphrasing method that extends matches to synonymous, but non-identical phrases. We automatically generate our paraphrases by extracting them from bilingual parallel corpora.
Whereas many systems use dependency parsers and other linguistic resources that are only available for a limited number of languages, our system employes a method that is comparatively language independent. For this paper we extract paraphrases in Dutch, English, French, German, Italian, Spanish, and Portuguese.
The paraphrase extraction algorithm is described in section 2. Section 3 describes how the entailment score is calculated, and how paraphrases are generated in the entailment detection system. The results of our participation in the CLEF2006 Answer Validation Exercide (henceforth AVE) are described in section 4. We will wrap up with a conclusion and suggestions for future work in section 5. 2
Paraphrases are alternative ways of conveying the same information. The automatic generation
of paraphrases has been the focus of a significant amount of research lately [
Bannard and Callison-Burch extract paraphrases from a parallel corpus by equating English
phrases which share a common foreign language phrase. English phrases are aligned with their
foreign translations using alignment techniques drawn from recent phrase-based approaches to
statistical machine translation [
The method is multilingual, since it can be applied to any language which has a parallel corpus.
Thus paraphrases can be easily generated for each of the languages in the CLEF AVE task using the Europarl corpus. 3
The longest common subsequence (LCS) is used as a measure of similarity between passages.
LCS is also used by the ROUGE [
LCS(T, H) = max { |Q| | Q ⊆ T ; Q ⊆ H; (ti = hk ∈ Q ∧ tj = hl ∈ Q ∧ j > i) → l > k} (4)
From the LCS, the entailment score LCS(T, H)/|H| is derived. In order to account for variation in natural language text, the LCS is measured after paraphrasing the hypothesis. The underlying 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 random longest common subseq.
LCS after paraphrasing random longest common subsequence
LCS after paraphrasing dependency tree alignment precision recall
idea is that whenever a paraphrase of the hypothesis exists which entails the text, the hypothesis itself also entails the text.
We attempted to extract paraphrases for every phrase in the hypothesis of up to 8 words. Note that by “phrase” we simply mean sequence of words. Figure 2 shows all paraphrases that we were able to extract for the example hypothesis. After generating these candidate mappings we iteratively transform the hypothesis to be closer to the text by substituting in paraphrases. At each iteration, the substitution is made which constitutes the greatest increase of the entailment score. To prevent overgeneration, a word which was introduced in the hypothesis by a paraphrase substitution cannot be substituted itself. The process stops when no more substitutions can be made which positively affect the entailment score. By example, the following paraphrase of the hypothesis from section 1 is obtained by a number of substitutions.
Hypothesis: Clonaid announced that mother and daughter would be returning to the US on
Monday.
Substitutions: the US → the United States returning → return said → announced would be → is on Monday → Monday Paraphrased hypothesis: Clonaid said that mother and daughter is return to the United States Monday. 6
In this case, paraphrasing caused the length of the LCS to increase from 43% ( 14 ) to 77% ( 1103 ). The words in italics are the words which are aligned with the text sentence, i.e. which are part of the longest common subsequence. Table 2 shows a number of CLEF AVE pairs for which paraphrases are were to recognize entailment.
In order to judge whether a hypothesis is entailed by a text we see if the value of the entailment
score, LCS(T, H)/|H|, is greater than some threshold value. Support vector machines [
a
fte r
a ph
the Question Answering subset of the RTE2 data set [
We compared the performance of the paraphrasing method with two baselines on seven languages within the the CLEF 2006 Answer Validation Exercise. The first baseline is a system which decides at random with a probability distribution reflecting the corpus distribution of entailment values. The second baseline is a system which measures the longest common subsequence of text and hypothesis. Given the fact that paraphrasing is a form of query expansion, we expected that precision drops and recall increases when using paraphrases. Figure 3 (left) shows that this is indeed the case, but that the system using paraphrases shows considerably better overall performance, as indicated by the F-measure, compared to plain LCS.
For Dutch, Spanish and English, we made a syntactic analysis of each sentence using the
parsers of [
We showed that paraphrases can boost the performance of an entailment recognition system relying on the longest common subsequence to decide for entailment. Our method is applicable to a wide range of languages, since no language specific natural language analysis or background knowledge is used other than paraphrases automatically extracted from bilingual parallel corpora. Although our system performs similarly to a syntax based system, we showed that there is relatively little overlap between the sets of correctly recognized pairs of both systems. This indicates that information conveyed by paraphrases and syntax are largely complementary for the task of recognizing entailment.
In the future we plan to investigate three things: a combination of syntax-based and paraphrasebased approaches to entailment recognition, improved methods for determining the entailment threshold, and further enhancements to paraphrase extraction techniques, such as taking syntax into account.
This work is funded by the Interactive Multimodal Information Extraction (IMIX) program of the Netherlands Organization for Scientific Research (NWO).