In this paper, we propose a class of graphs, the tripartite directed acyclic graphs (tDAGs), to model first-order rule feature spaces for sentence pair classification. We introduce an algorithm for computing the similarity in first-order rewrite rule feature spaces. Our algorithm is extremely efficient and, as it computes the similarity of instances that can be represented in explicit feature spaces, it is a valid kernel function.
If we want to learn textual entailment classifiers, we need to exploit first-order rules hidden in training instances. To positively exploit the training instance “Pediatricians suggest women to feed newborns breast milk” entails “Pediatricians suggest that newborns eat breast milk” (T2, H2) for classifying the above example, learning algorithms should learn that the two instances hide the first-order rule ρ = f eed Y Z → Y eat Z . The first-order rule feature space, introduced by [22], gives high performances in term of accuracy for textual entailment recognition with respect to other features spaces.
In this paper, we propose a class of graphs, the tripartite directed acyclic graphs
(tDAGs), that model first-order rule feature spaces and, using this class of graphs,
we introduce an algorithm for computing the similarity in first-order rewrite rule
feature spaces. The possibility of explicitly representing the first-order feature
space as subgraphs of tDAGs makes the derived similarity function a valid
kernel. With respect to the algorithm proposed in [
The paper is organized as follows. In Section 2, we firstly describe tripartite
directed acyclic graphs (tDAGs) to model first-order feature (FOR) spaces. In
Section 3, we then present the related work. In Section 4, we introduce the similarity
function for these FOR spaces. This can be used as kernel function in kernel-based
machines (e.g., support vector machines [4]). We then introduce our efficient
algorithm for computing the similarity among tDAGs. In Section 5, we analyze
the computational efficiency of our algorithm showing that it is extremely more
efficient than the algorithm proposed in [
Representing first-order rules and sentence pairs as tripartite directed acyclic graphs As first step, we want to define the tripartite directed acyclic graphs (tDAGs). This is an extremely important class of graphs for the first-order rule feature spaces we want to model. We want here to intuitively show that, if we model first-order rules and sentence pairs as tDAGs, determining whether or not a sentence pair can be unified with a first-order rewrite rule is a graph matching problem. This intuitive idea helps in determining our efficient algorithm for exploiting first-order rules in learning examples.
To illustrate the above idea we will use an example based on the above rule ρ= f eed Y Z → Y eat Z and the above sentence pair (T1, H1). The rule ρ encodes the entailment relation of the verb to feed and the verb to eat. If represented over a syntactic interpretation, the rule has the following aspect: VB NP NP · NP VP feed
· (a) NP
VP · · NP
VP VB NP eat
DT NN VB NP
NP
NNS VB
NP The farmer feed NNS NN NNS ·
Cows eat NN NNS cows animal extracts (b) animal extracts As in the case of feature structures [2], we can observe this rule as a graph. As we are not interested in the variable names but we need to know the relation between the right hand side and the left hand side of the rule, we can substitute each variable with an unlabelled node. We then connect tree nodes having variables with the corresponding unlabelled node. The result is a graph as the one in Figure 1(a). The variables Y and Z are represented by the unlabelled nodes between the trees.
In the same way we can represent the sentence pair (T1, H1) using graph with
explicit links between related words and nodes (see Figure 1(b)). We can link
words using anchoring methods as in [
Both rules and sentence pairs are graphs of the same type. These graphs are basically two trees connected through an intermediate set of nodes representing variables in the rules and relations between nodes in the sentence pairs. We will hereafter call these graphs tripartite directed acyclic graphs (tDAGs). The formal definition follows.
Definition tDAG: A tripartite directed acyclic graph is a graph G = (N, E) where • the set of nodes N is partitioned in three sets Nt, Ng, and A • the set of edges is partitioned in four sets Et, Eg, EAt , and EAg such that t = (Nt, Et) and g = (Ng , Eg) are two trees and EAt = {(x, y)|x ∈ Nt and y ∈ A} and EAg = {(x, y)|x ∈ Ng and y ∈ A} are the edges connecting the two trees.
S 2 NP 1
VP 2 NNS 1 VB 2
S P2 = h
Pediatricians suggest NP
VP NNS TO
VP women to VB NP 3
NP 4 feed NNS 3 NN 5 NN 4 newborns breast milk animal extracts
S 2 ,
NP 1
VP 2 NNS 1 VB 2
SBAR Pediatricians suggest IN
S that NP 3
VP NNS 3 VB NP 4 newborns eat NN 5 NN 4 breast milk i NP 1
VP P1 = h NNS VB NP 1
NP 3 , NNS 1 VB
NP 3
i Farmers feed NNS 1 NN 2 NNS 3
Cows eat NN 2 NNS 3 cows animal extracts
A tDAG is a partially labeled graph. The labeling function L only applies to the subsets of nodes related to the two trees, i.e., L : Nt ∪ Ng → L. Nodes in the set A are not labeled.
The explicit representation of the tDAG in Figure 1(b) has been useful to show that the unification of a rule and a sentence pair is a graph matching problem. Yet, it is complex to follow. We will then describe a tDAG with an alternative and more convenient representation. A tDAG G = (N, E) can be seen as pair G = (τ, γ) of extended trees τ and γ where τ = (Nt ∪A, Et ∪EAt ) and γ = (Ng ∪A, Eg ∪EAg ). These are extended trees as each tree contains the relations with the other tree.
As for the feature structures, we will graphically represent a (x, y) ∈ EAt and a (z, y) ∈ EAg as boxes y respectively on the node x and on the node z. These nodes will then appear as L(x) y and L(z) y , e.g., NP 1 . The name y is not a label but a placeholder representing an unlabelled node. This representation is used for rules and for sentence pairs. The sentence pair in Figure 1(b) is then represented as reported in Figure 2. 3
Automatically learning classifiers for sentence pairs is extremely important for applications like textual entailment recognition, question answering, and machine translation.
In textual entailment recognition, it is not hard to see graphs similar to
tripartite directed acyclic graphs as ways of extracting features from examples to feed
automatic classifiers. Yet, these graphs are generally not tripartite in the sense
described in the previous section and they are not used to extract features representing
first-order rewrite rules. In [
In [
In [22], tripartite directed acyclic graphs are implicitly introduced and
exploited to build first-order rule feature spaces. Yet, both in [22] and in [
In machine translation, some methods such as [
An efficient algorithm for computing the first-order rule
space kernel
In this section, we present our idea for an efficient algorithm for exploiting
firstorder rule feature spaces. In Section 4.1, we firstly define the similarity function,
i.e., the kernel K(G1, G2), that we need to determine for correctly using first-order
rules feature spaces. This kernel is strongly based on the isomorphism between
graphs. A relevant idea of this paper is the observation that we can define an
efficient way to detect the isomorphism between the tDAGs (Section 4.2). This
algorithm exploits the efficient algorithms of tree isomorphism as the one implicitly
used in [3]. After describing the isomorphism between tDAGs, We can present
the idea of our efficient algorithm for computing K(G1, G2) (Section 4.3). We
introduce the algorithms to make it a viable solution (Section 4.4). Finally, in
Section 4.5, we report the kernel computation presented by [
Kernel functions over first-order rule feature spaces The first-order rule feature space we want to model is huge. If we use kernel-based machine learning models such as SVM [4], we can implicitly define the space by defining its similarity functions, i.e., its kernel functions. We firstly introduce the first-order rule feature space and we then define the prototypical kernel function over this space.
The first-order rule feature space (F OR) is in general the space of all the possible first-order rules defined as tDAGs. Within this space it is possible to define the function S(G) that determines all the possible active features of the tDAG G in F OR. The function S(G) determines all the possible and meaningful subgraphs of G. We want that these subgraphs represent first-order rules that can be matched with the pair G. Then, meaningful subgraphs of G = (τ, γ) are graphs (t, g) where t and g are subtrees of τ and γ, respectively. For example, the subgraphs of P1 and P2 in Figure 2 are hereafter partially represented: S(P1) = { h i , h ,
i , h
S NP VP ,
S NP 1 VP
NP 1 NNS 1
NP 1 NNS 1
S feed NP
VP VB NP 1 NP 3 ,
S NP 1 VP
VB NP 3 eat i ,
VP h VB NP 1 NP 3 ,
feed and S(P2) = { h
S NP 1 VP
VB NP 3 eat
i , ... } S 2
S 2 , NP 1 VP 2
NP 1 VP 2 i , h
NP 1 NNS 1 ,
NP 1 NNS 1 i , h VB NP 3 NP 4 ,
i , ... } feed
VP
S NP 3 VP
VB NP 4 eat
In the FOR space, the kernel function K should then compute the number of
subgraphs in common. The trivial way to describe the former kernel function is
using the intersection operator, i.e., the kernel K(G1, G2) is the following:
K(G1, G2) = |S(G1) ∩ S(G2)|
(1)
This is very simple to write and it is in principle correct. A graph g in the
intersection S(G1) ∩ S(G2) is a graph that belongs to both S(G1) and S(G2). Yet, this
hides a very important fact: determining whether two graphs, g1 and g2, are the
same graph g1 = g2 is not trivial. For example, it is not sufficient to superficially
compare graphs to determine that ρ1 belongs both to S1 and S2. We need to use
the correct property for g1 = g2, i.e., the isomorphism between two graphs. We
can call the operator Iso(g1, g2). When two graphs verify the property Iso(g1, g2),
both g1 and g2 can be taken as the graph g representing the two graphs. Detecting
Iso(g1, g2) has an exponential complexity [
This complexity of the intersection operator between sets of graphs deserves a different way to represent the operation. We will use the same symbol but we will use the prefix notation. The operator is hereafter re-defined: ∩(S(G1), S(G2)) = {g1|g1 ∈ S(G1), ∃g2 ∈ S(G2), Iso(g1, g2)} 4.2
Isomorphism between tDAGs As isomorphism between graphs is an essential activity for learning from structured data, we here review its definition and we adapt it to tDAGs. We then observe that isomorphism between two tDAGs can be divided in two sub-problems: • finding the isomorphism between two pairs of extended trees • checking whether the partial isomorphism found between the two pairs of extended trees are compatible.
In general, two tDAGs, G1 = (N1, E1) and G2 = (N2, E2) are isomorphic (or match) if |N1| = |N2|, |E1| = |E2|, and a bijective function f : N1 → N2 exists such that these properties hold: • for each node n ∈ N1, L(f (n)) = L(n) • for each edge (n1, n2) ∈ E1 an edge (f (n1), f (n2)) is in E2 The bijective function f is a member of the combinatorial set F of all the possible bijective functions between the two sets N1 and N2.
The trivial algorithm for detecting if two graphs are isomorphic is exponential
[
Given two tDAGs G1 = (τ1, γ1) and G2 = (τ2, γ2) the isomorphism can be reduced to the problem of detecting two properties: 1. Partial isomorphism. Two tDAGs G1 and G2 are partially isomorphic, The partial isomorphism produces two bijective functions fτ and fγ. 2. Constraint compatibility. Two bijective functions fτ and fγ are compatible on the sets of nodes A1 and A2, if for each n ∈ A1, it happens that fτ (n) = fγ(n).
We can rephrase the second property, i.e., the constraint compatibility, as follows. We define two constraints c(τ1, τ2) and c(γ1, γ2) representing the functions fτ and fγ on the sets A1 and A2. The two constraints are defined as c(τ1, τ2) = {(n, fτ (n))|n ∈ A1} and c(γ1, γ2) = {(n, fγ (n))|n ∈ A1}. Two partially isomorphic tDAGs are isomorphic if the constraints match, i.e., c(τ1, τ2) = c(γ1, γ2).
For example, the fourth pair of S(P1) and the third pair of S(P2) are isomorphic as: (1) these are partially isomorphic, i.e., the right hand sides τ and the left hand sides γ are isomorphic; (2) both pairs of extended trees generate the constraint c1 = {( 1 , 3 ), ( 3 , 4 )}. In the same way, the second pair of S(P1) and the second pair of S(P2) generate c2 = {( 1 , 1 )} h B 1 C 1 , M 1
N 1 i , h , M 1
N 1 i } = ∩(Se(Pa), Se(Pb))|c1
A 1
I 1 N 2 N 1
A 1 B 1 B 2
A 1
B 1 C 1 = { ,
B 1 C 1
} × {
B 1 B 2 ∩(Se(γa), Se(γb))|c1
B 1 C 1
M 1 N 1
A 1 B 1 C 1
I 1 M 1 N 1 , M 1
N 1 N 2 N 1 , i , h B 1 C 1 , i , ,
M 1
N 1 i Pb = h B 1
C 1 ,
M 1
N 1 i B 1 B 2 C 1 C 2
M 2 M 1 N 2 N 1
B 1 B 2 C 1 C 3
M 3 M 1 N 2 N 1
General idea for an efficient kernel function As discussed above, two tDAGs are isomorphic if the two properties, the partial isomorphism and the constraint compatibility, hold. To compute the kernel function K(G1, G2) defined in Section 4.1, we can exploit these properties in the reverse order. Given a constraint c, we can select all the graphs that meet the constraint c (constraint compatibility). Having the set of all the tDAGs meeting the constraint, we can detect the partial isomorphism. We split each pair of tDAGs into the four extended trees and we determine if these extended trees are compatible.
We introduce this method to compute the kernel K(G1, G2) in the FOR space in two steps. Firstly, we give an intuitive explanation and, secondly, we formally define the kernel.
To give an intuition of the kernel computation, without loss of generality and for sake of simplicity, we use two non-linguistic tDAGs, Pa and Pb (see Figure 4), and the subgraph function Se(θ). This latter is an approximated version of S(θ) that generates tDAGs with subtrees rooted in the root of the initial trees of θ.
To exploit the constraint compatibility property, we define C as the set of all the relevant alternative constraints, i.e., the constraints c that are likely to be generated when detecting the partial isomorphism. For Pa and Pb, this set is C = {c1, c2} = {( 1 , 1 ), ( 2 , 2 )}, {( 1 , 1 ), ( 2 , 3 )} . We can then determine the kernel K(Pa, Pb) as:
K(Pa,Pb)=|∩(Se(Pa),Se(Pb))|=|∩(Se(Pa),Se(Pb))|c1 S ∩(Se(Pa),Se(Pb))|c2 | where ∩(Se(Pa), Se(Pb))|c are the common subgraphs that meet the constraint c. A tDAG g0 = (τ 0, γ0) in Se(Pa) is in ∩(Se(Pa), Se(Pb))|c if g00 = (τ 00, γ00) in Se(Pb) exists, g0 is partially isomorphic to g00, and c0 = c(τ 0, τ 00) = c(γ0, γ00) is covered by and compatible with the constraint c, i.e., c0 ⊆ c. For example in Figure 3, the first tDAG of the set ∩(Se(Pa), Se(Pb))|c1 belongs to the set as its constraint c0 = {( 1 , 1 )} is a subset of c1.
Observing the kernel computation in this way is important. Elements in ∩(Se(Pa), Se(Pb))|c already satisfy the property of constraint compatibility. We only need to determine if the partially isomorphic properties hold for elements in ∩(Se(Pa), Se(Pb))|c. Then, we can write the following equivalence: ∩(Se(Pa),Se(Pb))|c=∩(Se(τa),Se(τb))|c×∩(Se(γa),Se(γb))|c (2) Figure 3 reports this equivalence for the two sets derived using the constraints c1 and c2. Note that this equivalence is not valid if a constraint is not applied, i.e., ∩(Se(Pa), Se(Pb)) 6= ∩(Se(τa), Se(τb))×∩(Se(γa), Se(γb)). The pair Pa itself does not belong to ∩(Se(Pa), Se(Pb)) but it does belong to ∩(Se(τa), Se(τb))×∩(Se(γa), Se(γb)).
The equivalence (2) allows to compute the cardinality of ∩(Se(Pa), Se(Pb))|c using the cardinalities of ∩(Se(τa), Se(τb))|c and ∩(Se(γa), Se(γb))|c. These latter sets contain only extended trees where the equivalences between unlabelled nodes are given by c. We can then compute the cardinalities of these two sets using methods developed for trees (e.g., the kernel function KS (θ1, θ2) introduced in [3]). 4.3.2
Formal definition Given the idea of the previous section, it is easy to demonstrate that the kernel K(G1, G2) can be written as follows:
K(G1,G2)=|Sc∈C ∩(S(τ1),S(τ2))|c×∩(S(γ1),S(γ2))|c| where C is set of alternative constraints and ∩(S(θ1), S(θ2))|c are all the common extended trees compatible with the constraint c.
We can compute the above kernel using the inclusion-exclusion property, i.e., |A1 ∪ · · · ∪ An| = (−1)|J|−1|AJ | (3) where 2{1,...,n} is the set of all the subsets of {1, . . . , n} and AJ = Ti∈J Ai.
X J∈2{1,...,n}
To describe the application of the inclusion-exclusion model in our case, let firstly define:
KS (θ1, θ2, c) = |∩(S(θ1), S(θ2))|c| where θ1 can be both τ1 and γ1 and θ2 can be both τ2 and γ2. Trivially, we can demonstrate that:
K(G1, G2) = =PJ∈2{1,...,|C|} (−1)|J|−1KS(τ1,τ2,c(J))KS(γ1,γ2,c(J)) where c(J ) = Ti∈J ci.
Given the nature of the constraint set C, we can compute efficiently the previous equation as it often happens that two different J1 and J2 in 2{1,...,|C|} generate the same c, i.e.
c = \ ci = \ ci i∈J1 i∈J2 Then, we can define C∗ as the set of all intersections of constraints in C, i.e. C∗ = {c(J )|J ∈ 2{1,...,|C|}}. We can rewrite the equation as:
K(G1, G2) = X KS (τ1, τ2, c)KS (γ1, γ2, c)N (c) where
c∈C∗ N (c) =
X J∈2{1,...,|C|} c=c(J) (−1)|J|−1 (4) (5) (6) (7) (8)
The complexity of the above kernel strongly depends on the cardinality of C and the related cardinality of C∗. The worst-case computational complexity is still exponential with respect to the size of A1 and A2. Yet, the average case complexity [20] is promising.
The set C is generally very small with respect to the worst case. If F(A1,A2)
are all the possible correspondences between the nodes A1 and A2, it happens
that |C| << |F(A1,A2)| where |F(A1,A2)| is the worst case. For example, in the
case of P1 and P2, the cardinality of C = {( 1 , 1 )}, {( 1 , 3 ), ( 3 , 4 ), ( 2 , 5 )}
is extremely smaller than the one of F(A1,A2) = {{( 1 , 1 ), ( 2 , 2 ), ( 3 , 3 )}, {( 1 , 2 ),
( 2 , 1 ), ( 3 , 3 )}, {( 1 , 2 ), ( 2 , 3 ),( 3 , 1 )}, ..., {( 1 , 3 ),( 2 , 4 ),( 3 , 5 )}}. In Section 4.5
we argue that the algorithm presented in [
Moreover, the set C∗ is extremely smaller than 2{1,...,|C|} due to the above property (6).
We will analyze the average-case complexity with respect to the worst-case complexity in Section 5. 4.4
Enabling the efficient kernel function The above idea for computing the kernel function is extremely interesting. Yet, we need to make it viable by describing the way we can determine efficiently the three main parts of the equation (7): 1) the set of alternative constraints C (Section 4.4.1); 2) the set C∗ of all the possible intersections of constraints in C (Section 4.4.2); and, finally, 3) the numbers N (c) (Section 4.4.3). 4.4.1
Determining the set of alternative constraints The first step of equation (7) is to determine the alternative constraints C. We can here strongly use the possibility of dividing tDAGs in two trees. We build C as Cτ ∪ Cγ where: 1) Cτ are the constraints obtained from pairs of isomorphic extended trees t1 ∈ S(τ1) and t2 ∈ S(τ2); 2) Cγ are the constraints obtained from pairs of isomorphic extended trees t1 ∈ S(γ1) and t2 ∈ S(γ2).
The idea for an efficient algorithm is that we can compute the C without explicitly looking at all the subgraphs involved. We instead use and combine the constraints derived comparing the productions of the extended trees. We can compute then Cτ with the productions of τ1 and τ2 and Cγ with the productions of γ1 and γ2. For example (see Figure 2), focusing on the τ , the rule N P 3 → N N 2 N N S 3 of G1 and N P 4 → N N 5 N N S 4 of G2 generates the constraint c = {( 3 , 4 ), ( 2 , 5 )}.
Using the above intuition it is possible to define an algorithm that builds an alternative constraint set C with the following two properties: 1. for each common subtree according to a set of constraints c, ∃c0 ∈ C such that c ⊆ c0; 2. @c0, c00 ∈ C such that c0 ⊂ c00 and c0 6= ∅. 4.4.2
The set C∗ is defined as the set of all possible intersections of alternative constraints in C. Due to the property (6) discussed in Section 4.3, we can empirically demonstrate that the average complexity of the algorithm for computing C∗ is not bigger than O(|C|2). Yet, again, the worst case complexity is exponential. 4.4.3
Determining the values of N (c) The multiplier N (c) (Eq. 8) represents the number of times the constraint c is considered in the sum of equation 5, keeping into account the sign of the corresponding addend. It is possible to demonstrate that:
N (c) = 1 − X
Nc0 c0∈C∗ c0⊃c (9) This recursive formulation of the equation allows us to easily determine the value of N (c) for every c belonging to C∗. It is possible to prove this property using set properties and the binomial theorem. The proof is omitted for lack of space. 4.5
Reviewing the strictly related work
To understand if ours is an efficient algorithm, we compare it with the algorithm
presented by [
max c∈F(A1,A2)
KS (τ1, τ2, c)KS (γ1, γ2, c) (10) where F(A1,A2) are all the possible correspondences between the nodes A1 and A2 of the two tDAGs as the one presented in Section 4.3. This formulation of the kernel has the worst case complexity of our formulation, i.e., Eq. 7.
For computing the basic kernel for the extended trees, i.e. KS (θ1, θ2, c) we use
the model algorithm presented by [22] and refined by [
In this section we want to empirically estimate the benefits in terms of the
computational cost of our algorithm with respect to the algorithm proposed by [
Average computing time analysis For the first set of experiments, the source of examples is the one of the recognizing textual entailment challenge, i.e., RTE2 [1]. The dataset of the challenge has 1,600 sentence pairs.
The computational cost of both K(G1, G2) and Kmax(G1, G2) depends on the number of placeholders n = |A1| of G1 and on m = |A2| the number of placeholders of G2. Then, in the first experiment we want to determine the relation between the computational time and the factor n × m. Results are reported in Figure 5(a) where the computation times are plotted with respect to n × m. Each
K(G1, G2) Kmax(G1, G2)
K(G1, G2) Kmax(G1, G2) ms
s point in the curve represents the average execution time for the pairs of instances having n×m placeholders. As expected, the computation of the function K is more efficient than the computation Kmax. The difference between the two execution times increases with n × m.
We then performed a second experiment that determines the relation of the total execution with the maximum number of placeholders in the examples. This is useful to estimate the behavior of the algorithm with respect to its application in learning models. Using the RTE2 data, we artificially build different versions with increasing number of placeholders. We then have RTE2 with one placeholder at most in each pair, RTE2 with two placeholders, etc. The number of pairs in each set is the same. What changes is the maximal number of placeholders. Results are reported in Figure 5(b) where the execution time of the training phase in seconds (s) is plotted for each different set. We see that the computation of Kmax is exponential with respect to the number of placeholders and it becomes intractable after 7 placeholders. The computation of K is instead more flat. This can be explained as the computation of K is related to the real alternative constraints that appears in the dataset. The computation of the kernel K then outperforms the computation of the kernel Kmax. 5.2
Accuracy analysis As Kmax that has been demonstrated very effective in term of accuracy for RTE and K compute a slightly different similarity function, we want to show that the performance of our more computationally efficient K is comparable, and even better, to the performances of Kmax. We then performed an experiment taking as training all the data derived from RTE1, RTE2, and RTE3, (i.e., 4567 training exKernel
Kmax
K amples) and taking as testing RTE-4 (i.e., 1000 testing examples). The results are reported in Table 1. As the table shows, the accuracy of K is higher than the accuracy of Kmax. There are two main reasons. The first is that Kmax is an approximation of K. The second is that we can now consider sentence pairs with more than 7 placeholders. Then, we can use the complete training set as the third column of the table shows. 6
We presented an interpretation of first order rule feature spaces as tripartite directed acyclic graphs (tDAGs). This view on the problem gave us the possibility of defining a novel and efficient algorithm for computing the kernel function for first order rule feature spaces. Moreover, the resulting algorithm is a valid kernel as it can be written as dot product in the explicit space of the tDAG fragments. We demonstrated that our algorithm outperforms in term of average complexity the previous algorithm and it yields to better accuracies for the final task. We are investigating if this is a valid algorithm for two general directed acyclic graphs.
[1] R. Bar-Haim, I. Dagan, B. Dolan, L. Ferro, D. Giampiccolo, and I. Magnini, Bernardo Szpektor. The second pascal recognising textual entailment challenge. In Proceedings of the Second PASCAL Challenges Workshop on Recognising Textual Entailment. Venice, Italy, 2006. [2] B. Carpenter. The Logic of Typed Feature Structures. Cambridge University Press,
Cambridge, England, 1992. [3] M. Collins and N. Duffy. New ranking algorithms for parsing and tagging: Kernels over discrete structures, and the voted perceptron. In Proceedings of ACL02. 2002. [4] C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:1–25, 1995. [5] I. Dagan and O. Glickman. Probabilistic textual entailment: Generic applied modeling of language variability. In Proceedings of the Workshop on Learning Methods for Text Understanding and Mining, Grenoble, France, 2004.