In this paper we present the use of a ”general purpose” textual entaiment recognizer in the Answer Validation Exercise (AVE) task. Our system has been developed to learn entailment rules from annotated examples. The main idea of the system is the cross-pair similirity measure we defined. This similarity allows us to define an implicit feature space using kernel functions in SVM learners. We experimented with our system using different training and testing sets: RTE data sets and AVE data sets. The comparative results show that entailment rules can be learned from data sets, e.g. RTE, that are different from AVE. Moreover, it seems that better results are obtained using more controlled training data (the RTE set) that less controlled ones (the AVE development set). Although, the high variability of the outcome prevents us to derive definitive conclusions, the results of our system show that our approach is quite promising and improvable in the future.
a) H1: “At the end of the year, all solid insurance companies pay dividends” and b) H2: “At the end of the year, all solid companies pay cash dividends”, we can built two examples: (T1, H1) which is an evidence of a true entailment (positive instance) and (T1, H2) which is a negative evidence.
Our system extract rules from them to solve apparently not related entailments. For example, given the following text and hypothesis:
T3 ⇒ H3?
T3 H3 “All wild animals eat plants that have scientifically proven medicinal properties.” “All wild mountain animals eat plants that have scientifically proven medicinal properties.” we note that T3 is structurally (and somehow lexically similar) to T1 and H3 is more similar to H1 than to H2. Thus, from T1 ⇒ H1, we may extract rules to derive that T3 ⇒ H3.
The main idea of our model is that it relies not only on a intra-pair similarity between T and H but also on a cross-pair similarity between two pairs (T 0, H0) and (T 00, H00). The latter similarity measure along with a set of annotated examples allows the leaning model to automatically derive syntactic and lexical rules that can solve complex entailment cases.
In this paper, we experimented with our entailment recognition system [
In the remainder of this paper, Sec. 2 illustrates the related work, Sec. 3 introduces the complexity of learning entailment rules from examples, Sec. 4 describes our models, Sec. 6 shows the experimental results, and, finally, Sec. 7 derives the conclusions. 2
Although the textual entailment recognition problem is not new, most of the automatic approaches have
been proposed only recently. This has been mainly due to the RTE challenge events [
A first class of methods defines measures of the distance or similarity between T and H either assuming
the independence between words [
A second class of methods can give a solution to the previous problem. These methods generally
combine a similarity measure with a set of possible transformations T applied over syntactic and semantic
interpretations. The entailment between T and H is detected when there is a transformation r ∈ T so
that sim(r(T ), H) > α. These transformations are logical rules in [
In the introductory section, we have shown that, to carry out automatic learning from examples, we need to define a cross-pair similarity measure. Its definition is not straightforward as it should detect whether two pairs (T 0, H0) and (T 00, H00) realize the same rewrite rules. This measure should consider pairs similar when: (1) T 0 and H0 are structurally similar to T 00 and H00, respectively and (2) the lexical relations within the pair (T 0, H0) are compatible with those in (T 00, H00). Typically, T and H show a certain degree of overlapping, thus, lexical relations (e.g., between the same words) determine word movements from T to H (or vice versa). This is important to model the syntactic/lexical similarity between example pairs. H1 H2
PP IN At NP 0
PP IN At NP 0
PP
PP DT NN 0 IN NP 1 the end of DT NN 1 0 the year
1 DT NN 0 IN NP 1 the end of DT NN 1 0 the year
1
S NP 0 , DT JJ 2
NNS 2
VBP 3 all solid 2’ companies 2” , , NNS 4 dividends 4
NP 4 NNS 4 dividends 4 H3 All wild a’
NNS a VBP b
NP c animals a” eat b placnts
... properties S
S VP 3
NP a
VP b NP 0 , DT JJ 2
NN
NNS 2
VBP 3
DT JJ a
NN
NNS a VBP b
NP c all solid insurance companies 2’ 2” pay 3
All wild mountain animals a’ a” eat b placnts ... properties PP
NP 2
VP 3 At ... year DT JJ 2
NNS 2
VBP 3
NP 4 all solid 2’ companies 2” pay NN 3
NNS 4 cash dividends 4
NP a
VP b DT JJ a
NN
NNS a VBP b
NP c All wild mountain animals a’ a” eat b placnts ... properties
Indeed, if we encode such movements in the syntactic parse trees of texts and hypotheses, we can use
interesting similarity measures defined for syntactic parsing, e.g., the tree kernel devised in [
To consider structural and lexical relation similarity, we augment syntactic trees with placeholders which identify linked words. More in detail: - We detect links between words wt in T that are equal, similar, or semantically dependent on words wh in H . We call anchors the pairs (wt, wh) and we associate them with placeholders. For example, in Fig. 1, the placeholder 2” indicates the (companies,companies) anchor between T1 and H1. This allows us to derive the word movements between text and hypothesis. - We align the trees of the two texts T 0 and T 00 as well as the tree of the two hypotheses H 0 and H 00 by considering the word movements. We find a correct mapping between placeholders of the two hypothesis H 0 and H 00 and apply it to the tree of H 00 to substitute its placeholders. The same mapping is used to substitute the placeholders in T 00. This mapping should maximize the structural similarity between the four trees by considering that placeholders augment the node labels. Hence, the cross-pair similarity computation is reduced to the tree similarity computation.
The above steps define an effective cross-pair similarity that can be applied to the example in Fig. 1: T1 and T3 share the subtree in bold starting with S → NP VP. The lexicals in T3 and H3 are quite different from those T1 and H1, but we can rely on the structural properties expressed by their bold subtrees. These are more similar to the subtrees of T1 and H1 than those of T1 and H2, respectively. Indeed, H1 and H3 share the production NP → DT JJ NN NNS while H2 and H3 do not. Consequently, to decide if (T3,H3) is a valid entailment, we should rely on the decision made for (T1, H1). Note also that the dashed lines connecting placeholders of two texts (hypotheses) indicate structurally equivalent nodes. For instance, the dashed line between 3 and b links the main verbs both in the texts T1 and T3 and in the hypotheses H1 and H3. After substituting 3 with b and 2 with a , we can detect if T1 and T3 share the bold subtree S → NP 2 VP 3 . As such subtree is shared also by H1 and H3, the words within the pair (T1, H1) are correlated similarly to the words in (T3, H3).
The above example emphasizes that we need to derive the best mapping between placeholder sets. It can be obtained as follows: let A0 and A00 be the placeholders of (T 0, H0) and (T 00, H00), respectively, without loss of generality, we consider |A0| ≥ |A00| and we align a subset of A0 to A00. The best alignment is the one that maximizes the syntactic and lexical overlapping of the two subtrees induced by the aligned set of anchors.
More precisely, let C be the set of all bijective mappings from a0 ⊆ A0 : |a0| = |A00| to A00, an element c ∈ C is a substitution function. We define as the best alignment the one determined by cmax = argmaxc∈C (KT (t(H0, c), t(H00, i)) + KT (t(T 0, c), t(T 00, i)) (1) where (a) t(S, c) returns the syntactic tree of the hypothesis (text) S with placeholders replaced by means of the substitution c, (b) i is the identity substitution and (c) KT (t1, t2) is a function that measures the similarity between the two trees t1 and t2 (for more details see Sec. 4.2). For example, the cmax between (T1, H1) and (T3, H3) is {( 2’ , a’ ), ( 2” , a” ), ( 3 , b ), ( 4 , c )}. 4
In this section we describe how anchors are found at the level of a single pair (T , H) (Sec. 4.1). The anchoring process gives the direct possibility of implementing an inter-pair similarity that can be used as a baseline approach or in combination with the cross-pair similarity. This latter will be implemented with tree kernel functions over syntactic structures (Sec. 4.2). 4.1
The algorithm that we design to find the anchors is based on similarity functions between words or more
complex expressions. Our approach is in line with many other researches (e.g., [
Given the set of content words (verbs, nouns, adjectives, and adverbs) WT and WH of the two sentences T and H, respectively, the set of anchors A ⊂ WT × WH is built using a similarity measure between two words simw(wt, wh). Each element wh ∈ WH will be part of a pair (wt, wh) ∈ A if: 1. simw(wt, wh) 6= 0 2. simw(wt, wh) = maxwt0∈WT simw(wt0, wh) According to these properties, elements in WH can participate in more than one anchor and conversely more than one element in WH can be linked to a single element w ∈ WT .
The similarity simw(wt, wh) can be defined using different indicators and resources. First of all, two
words are maximally similar if these have the same surface form wt = wh. Second, we can use one of the
WordNet [
As result, given the syntactic category cw ∈ {noun, verb, adjective, adverb} and the lemmatized form lw of a word w, the similarity measure between two words w and w0 is defined as follows: 1 if w = w0∨ lw = lw0 ∧ cw = cw0 ∨ ((lw, cw), (lw0 , cw0 )) ∈ Ent∨ simw(w, w0) = ((lw, cw), (lw0 , cw0 )) ∈ Der∨ lev(w, w0) = 1 d(lw, lw0 ) if cw = cw0 ∧ d(lw, lw0 ) > 0.2 0 otherwise (2) It is worth noticing that, the above measure is not a pure similarity measure as it includes the entailment relation that does not represent synonymy or similarity between verbs. To emphasize the contribution of each used resource, in the experimental section, we will compare Eq. 2 with some versions that exclude some word relations. (3) (4)
The above word similarity measure can be used to compute the similarity between T and H. In line
with [
X (wt,wh)∈A simw(wt, wh) × idf (wh)
X idf (wh) wh∈WH where idf (w) is the inverse document frequency of the word w.
From the above intra-pair similarity, we can obtain the baseline cross-pair similarity based on only lexical information:
Klex((T 0, H0), (T 00, H00)) = s(T 0, H0) × s(T 00, H00) In the next section we define a novel cross-pair similarity that takes into account syntactic evidence by means of tree kernel functions. 4.2
Section 3 has shown that to measure the syntactic similarity between two pairs, (T 0, H0) and (T 00, H00), we should capture the number of common subtrees between texts and hypotheses that share the same anchoring scheme. The best alignment between anchor sets, i.e. the best substitution cmax, can be found with Eq. 1. As the corresponding maximum quantifies the alignment degree, we could define a cross-pair similarity as follows:
Kstruct((T 0, H0), (T 00, H00)) = max KT (t(H0, c), t(H00, i)) + KT (t(T 0, c), t(T 00, i) ,
c∈C
(5)
where as KT (t1, t2) we use the tree kernel function defined in [
Formally, given a subtree space F = {f1, f2, . . . , f|F|}, the indicator function Ii(n) is equal to 1
if the target fi is rooted at node n and equal to 0 otherwise. A tree-kernel function over t1 and t2 is
KT (t1, t2) = Pn1∈Nt1 Pn2∈Nt2 Δ(n1, n2), where Nt1 and Nt2 are the sets of the t1’s and t2’s nodes,
respectively. In turn Δ(n1, n2) = P|iF=|1 λl(fi)Ii(n1)Ii(n2), where 0 ≤ λ ≤ 1 and l(fi) is the number of
levels of the subtree fi. Thus λl(fi) assigns a lower weight to larger fragments. When λ = 1, Δ is equal to
the number of common fragments rooted at nodes n1 and n2. As described in [
The KT function has been proven to be a valid kernel, i.e. its associated Gram matrix is
positivesemidefinite. Some basic operations on kernel functions, e.g. the sum, are closed with respect to the set of
valid kernels. Thus, if the maximum held such property, Eq. 5 would be a valid kernel and we could use
it in kernel based machines like SVMs. Unfortunately, a counterexample illustrated in [
However, we observe that: (1) Kstruct((T 0, H0), (T 00, H00)) is a symmetric function since the set of
transformation C are always computed with respect to the pair that has the largest anchor set; (2) in [
In the previous section we have defined the intra and the cross pair similarity. The former does not show relevant implementation issues whereas the latter should be optimized to favor its applicability with SVMs. The Eq. 5 improvement depends on two factors: (1) its computation complexity; (2) the pruning of irrelevant information in large syntactic trees. The computational cost of cross-pair similarity between two tree pairs (Eq. 5) depends on the size of C. This is combinatorial in the size of A0 and A00, i.e. |C| = (|A0| − |A00|)!|A00|! if |A0| ≥ |A00|. Thus we should keep the sizes of A0 and A00 reasonably small.
To reduce the number of placeholders, we consider the notion of chunk defined in [
T ⇒ H T H Only the bold part of T supports the implication; the rest is useless and also misleading: if we used it to compute the similarity it would reduce the importance of the relevant part. Moreover, as we normalize the syntactic tree kernel (KT ) with respect to the size of the two trees, we need to focus only on the part relevant to the implication.
The anchored leaves are good indicators of relevant parts but also some other parts may be very relevant. For example, the function word not plays an important role. Another example is given by the word insurance in H1 and mountain in H3 (see Fig. 1). They support the implication T1 ⇒ H1 and T1 ⇒ H3 as well as cash supports T1 ; H2. By removing these words and the related structures, we cannot determine the correct implications of the first two and the incorrect implication of the second one. Thus, we keep all the words that are immediately related to relevant constituents.
The reduction procedure can be formally expressed as follows: given a syntactic tree t, the set of its nodes N (t), and a set of anchors, we build a tree t0 with all the nodes N 0 that are anchors or ancestors of any anchor. Moreover, we add to t0 the leaf nodes of the original tree t that are direct children of the nodes in N 0. We apply such procedure only to the syntactic trees of texts before the computation of the kernel function. 6
The experiments aim at determining if our system can learn rules required to solve the entailment cases
contained in the AVE data set. Although, we have already shown that our system can learn entailment
[
Our approach to study the above points is to train and experiment with our system and several data sets proposed in AVE as well as RTE1 and RTE2. The combination of training and testing based on such sets can give an indication on the learnability of general rules valid for different domain and different applications. 6.1
For the experiments, we used the following data sets:
Training set
We also created new sets by merging groups of the above four collections. For example, AV Ea ∪
RT E1 ∪ RT E2 stands for the set obtained as union of AV E a, RT E1 and RT E2. Moreover, to
implement our model (described in sections 4 and 5), we used the following resources:
• The Charniak parser [
This is one of the best figure method which provides a similarity score in the [
We assigned the maximum idf to words not found in the BNC.
• SVM-light-TK2 [
In all the experiments we used Koverall which combines the lexical and structural cross similarities. 6.2
1http://www.natcorp.ox.ac.uk/ 2SVM-light-TK is available at http://ai-nlp.info .uniroma2.it/moschitti/ • If we add the examples from the RTE challenges to the AV Eb training data, we obtain a good improvement, e.g. the system trained on AV Eb ∪ RT E2 improves the one trained on AV Eb of about 7% (38.98% vs. 31.85%). Adding RT E1 to the training data causes a decrease. This could be explained by the high impact of parameters. It is possible that the good setting for AV Eb ∪ RT E2 is not very good for AV Eb ∪ RT E1 ∪ RT E2. • Training on AV Ea and RTE data sets seems not helpful as the result using only AV Ea is higher, e.g. 35.36% vs. 32.38%. • Finally, training on RT E1 provides higher performance than training on RT E2 on both AV Ea and AV Eb test sets (see rows 10 and 11 vs 14 and 15). Moreover, their combined use (RT E1 ∪ RT E2) is helpful only if we select an opportune parameter j=0.9. This leads to the highest performance on AV Ea and AV Eb, i.e. 40.85% and 36.20%, respectively.
Given these preliminary results, we decided to use the best model obtained on RT E1 ∪ RT E2 to generate data of our CLEF submission. Moreover, as the AVE test set may have been statistically similar to the development set, we also submitted a run of the model trained on AV Ea ∪ AV Eb. The official results were 39.95% and 36.69%, respectively. These are quite in line with the analogous experiments shown in Table 1, i.e. training on RT E1 ∪ RT E2 and testing on AV Ea (40.85%) and training on AV Ea and testing on AV Eb (35.36). 6.2.1
Qualitative analysis The system we presented strongly uses syntactic interpretations of the example pairs. Then, its major bottleneck is the standard AVE process used to produce the affirmative form of the question given the answer provided by a the QA system. This process frequently generates ungrammatical sentences. The problem is clear just reading the first instances of the AVE development set. We report hereafter some of these examples. Each table reports the original question (Q), the text snippet (T ), and the affirmative form of the question used as hypothesis (H).
T ⇒ H Q T H T ⇒ H Q (id: 1) (id: 2) “When did Nixon resign?” “August, 1974 – Nixon resigns.” “Nixon resigned in 1974 – Nixon” T H H T ⇒ H Q T “What year was Halley’s comet visible?” “[...] 1909 Halley’s comet sighted from Cambridge Observatory. 1929 [...]” “In 1909 Halley was Halley’s comet visible ”
(id: 6) “Who is Juan Antonio Samaranch?” “International Olympic Committee President Juan Antonio Samaranch came strongly to the defense of China’s athletes, [...]” “Juan Antonio Samaranch is International Olympic Committee President Juan Antonio Samaranch came strongly to the defense of China ’s athletes ” We can observe that these examples have highly ungrammatical hypothesis. In the example (id 1), Nixon is repeated at the end of H. In the example (id 2), Halley is used as subject and as predicate. Finally, in the example (id 6) there is a large part of the hypothesis that is unnecessary and creates an ungrammatical sentence.
In this paper, we experimented with our entailment system [
The experiments show that few training examples and data sparseness produce a high variability of the results. In this scenario the parameterization is very critical and necessitates of accurate cross-validation techniques. The AVE results also show that our model can learn entailments from the RTE data sets (with a higher F1 than using only AVE data). This suggests that there are some general rules, valid cross domains and collections. The importance of such rules is still more evident if we consider that the distribution of positive and negative examples in the RTE and AVE data sets is quite different. This usually prevents statistical learning algorithms to carry out a correct generalization of the data.
In the future, we would like to carry out a throughout parameterization and continue investigating approaches to exploit data from difference sources of entailments.