Logical Inference on Dependency-based Compositional Semantics

Ran Tian Yusuke Miyao Takuya Matsuzaki
National Institute of Informatics, Japan
{tianran,yusuke,takuya-matsuzaki}@nii.ac.jp

Abstract

Dependency-based Compositional Semantics (DCS) is a framework of natural language semantics with easy-to-process structures as well as strict semantics. In this paper, we equip the DCS framework with logical inference, by defining abstract denotations as an abstraction of the computing process of denotations in original DCS. An inference engine is built to achieve inference on abstract denotations. Furthermore, we propose a way to generate on-the-fly knowledge in logical inference, by combining our framework with the idea of tree transformation. Experiments on FraCaS and PASCAL RTE datasets show promising results.

1 Introduction

Dependency-based Compositional Semantics (DCS) provides an intuitive way to model semantics of questions, by using simple dependency-like trees []. It is expressive enough to represent complex natural language queries on a relational database, yet simple enough to be latently learned from question-answer pairs. In this paper, we equip DCS with logical inference, which, in one point of view, is “the best way of testing an NLP system’s semantic capacity” [].

It should be noted that, however, a framework primarily designed for question answering is not readily suited for logical inference. Because, answers returned by a query depend on the specific database, but implication is independent of any databases. For example, answers to the question “What books are read by students?”, should always be a subset of answers to “What books are ever read by anyone?”, no matter how we store the data of students and how many records of books are there in our database.

Thus, our first step is to fix a notation which abstracts the calculation process of DCS trees, so as to clarify its meaning without the aid of any existing database. The idea is to borrow a minimal set of operators from relational algebra [], which is already able to formulate the calculation in DCS and define abstract denotation, which is an abstraction of the computation of denotations guided by DCS trees. Meanings of sentences then can be represented by primary relations among abstract denotations. This formulation keeps the simpleness and computability of DCS trees mostly unaffected; for example, our semantic calculation for DCS trees is parallel to the denotation computation in original DCS.

An inference engine is built to handle inference on abstract denotations. Moreover, to compensate the lack of background knowledge in practical inference, we combine our framework with the idea of tree transformation [], to propose a way of generating knowledge in logical representation from entailment rules [], which are by now typically considered as syntactic rewriting rules.

We test our system on FraCaS [] and PASCAL RTE datasets []. The experiments show: (i) a competitive performance on FraCaS dataset; (ii) a big impact of our automatically generated on-the-fly knowledge in achieving high recall for a logic-based RTE system; and (iii) a result that outperforms state-of-the-art RTE system on RTE5 data. Our whole system is publicly released and can be downloaded from http://kmcs.nii.ac.jp/tianran/tifmo/.

2 The Idea

In this section we describe the idea of representing natural language semantics by DCS trees, and achieving inference by computing logical relations among the corresponding abstract denotations.

2.1 DCS trees

Figure 1: The DCS tree of “students read books”

student
ARG
Mark
John
Emily
…

book
ARG
A Tale of Two Cities
Ulysses
…

read
SUBJ	OBJ
Mark	New York Times
Mary	A Tale of Two Cities
John	Ulysses
…	…

Table 1: Databases of student, book, and read

DCS trees has been proposed to represent natural language semantics with a structure similar to dependency trees [] (Figure 1). For the sentence “students read books”, imagine a database consists of three tables, namely, a set of students, a set of books, and a set of “reading” events (Table 1). The DCS tree in Figure 1 is interpreted as a command for querying these tables, obtaining “reading” entries whose “SUBJ” field is student and whose “OBJ” field is book. The result is a set $\{\textit{John reads Ulysses},\ldots\}$ , which is called a denotation.

DCS trees can be extended to represent linguistic phenomena such as quantification and coreference, with additional markers introducing additional operations on tables. Figure 2 shows an example with a quantifier “every”, which is marked as “ $\subset$ ” on the edge $(\textbf{love})\texttt{OBJ-ARG}(\textbf{dog})$ and interpreted as a division operator $q_{\subset}^{\texttt{OBJ}}$ (§2.2). Optimistically, we believe DCS can provide a framework of semantic representation with sufficiently wide coverage for real-world texts.

Figure 2: DCS trees of “Mary loves every dog” (Left-Up), “Tom has a dog” (Left-Down), and “Tom has an animal that Mary loves” (Right).

The strict semantics of DCS trees brings us the idea of applying DCS to logical inference. This is not trivial, however, because DCS works under the assumption that databases are explicitly available. Obviously this is unrealistic for logical inference on unrestricted texts, because we cannot prepare a database for everything in the world. This fact fairly restricts the applicable tasks of DCS.

Our solution is to redefine DCS trees without the aid of any databases, by considering each node of a DCS tree as a content word in a sentence (but may no longer be a table in a specific database), while each edge represents semantic relations between two words. The labels on both ends of an edge, such as SUBJ (subject) and OBJ (object), are considered as semantic roles of the corresponding words¹¹The semantic role ARG is specifically defined for denoting nominal predicate.. To formulate the database querying process defined by a DCS tree, we provide formal semantics to DCS trees by employing relational algebra [] for representing the query. As described below, we represent meanings of sentences with abstract denotations, and logical relations among sentences are computed as relations among their abstract denotations. In this way, we can perform inference over formulas of relational algebra, without computing database entries explicitly.

2.2 Abstract denotations

Abstract denotations are formulas constructed from a minimal set of relational algebra [] operators, which is already able to formulate the database queries defined by DCS trees.

For example, the semantics of “students read books” is given by the abstract denotation:

F_{1}=\textbf{read}\cap(\textbf{student}_{\texttt{SUBJ}}\times\textbf{book}_{% \texttt{OBJ}}),

where read, student and book denote sets represented by these words respectively, and $w_{r}$ represents the set $w$ considered as the domain of the semantic role $r$ (e.g. $\textbf{book}_{\texttt{OBJ}}$ is the set of books considered as objects). The operators $\cap$ and $\times$ represent intersection and Cartesian product respectively, both borrowed from relational algebra. It is not hard to see the abstract denotation denotes the intersection of the “reading” set (as illustrated by the “read” table in Table 1) with the product of “student” set and “book” set, which results in the same denotation as computed by the DCS tree in Figure 1, i.e. $\{\textit{John reads Ulysses},\ldots\}$ . However, the point is that $F_{1}$ itself is an algebraic formula that does not depend on any concrete databases.

Formally, we introduce the following constants:

•

$W$ : a universal set containing all entities.
•

Content words: a content word (e.g. read) defines a set representing the word (e.g. $\textbf{read}\!=\!\{(x,y)\;|\;read(x,y)\}$ ).

In addition we introduce following functions:

•

$\times$ : the Cartesian product of two sets.
•

$\cap$ : the intersection of two sets.
•

$\pi_{r}$ : projection onto domain of semantic role $r$ (e.g. $\pi_{\texttt{OBJ}}(\textbf{read})\!=\!\{y\;|\;\exists x;read(x,y)\}$ ). Generally we admit projections onto multiple semantics roles, denoted by $\pi_{R}$ where $R$ is a set of semantic roles.
•

$\iota_{r}$ : relabeling (e.g. $\iota_{\texttt{OBJ}}(\textbf{book})=\textbf{book}_{\texttt{OBJ}}$ ).
•

$q_{\subset}^{r}$ : the division operator, where $q_{\subset}^{r}(A,B)$ is defined as the largest set $X$ which satisfies $B_{r}\times X\subset A$ .²²If $A$ and $B$ has the same dimension, $q_{\subset}(A,B)$ is either $\emptyset$ or $\{*\}$ ( $0$ -dimension point set), depending on if $A\subset B$ . This is used to formulate universal quantifiers, such as “Mary loves every dog” and “books read by all students”.

An abstract denotation is then defined as finite applications of functions on either constants or other abstract denotations.

2.3 Statements

As the semantics of DCS trees is formulated by abstract denotations, the meanings of declarative sentences are represented by statements on abstract denotations. Statements are declarations of some relations among abstract denotations, for which we consider the following set relations:

Non-emptiness $A\neq\emptyset$ : the set $A$ is not empty.

Subsumption $A\subset B$ : set $A$ is subsumed by $B$ .³³Using division operator, subsumption can be represented by non-emptiness, since for sets $A$ , $B$ of the same dimension, $q_{\subset}(A,B)\neq\emptyset\Leftrightarrow A\subset B$ .

Roughly speaking, the relations correspond to the logical concepts satisfiability and entailment.

	example phrase	abstract denotation / statement
compound noun	pet fish	$\textbf{pet}\cap\textbf{fish}$
modification	nice day	$\textbf{day}\cap(W_{\texttt{ARG}}\times\textbf{nice}_{\texttt{MOD}})$
temporal relation	boys study at night	$\textbf{study}\cap(\textbf{boy}_{\texttt{SUBJ}}\times\textbf{night}_{\texttt{% TIME}})$
relative clause	books that	$\textbf{book}\cap\pi_{\texttt{OBJ}}(\textbf{read}$
	students read	$\cap(\textbf{student}_{\texttt{SUBJ}}\times W_{\texttt{OBJ}}))$
quantification	all men die	$\textbf{man}\subset\pi_{\texttt{SUBJ}}(\textbf{die})$
hypernym		$\textbf{dog}\subset\textbf{animal}$
derivation	all criminals commit	$\textbf{criminal}\subset\pi_{\texttt{SUBJ}}(\textbf{commit}\cap$
	a crime	$(W_{\texttt{SUBJ}}\times\textbf{crime}_{\texttt{OBJ}}))$
antonym		$\textbf{rise}\parallel\textbf{fall}$
negation	no dogs are hurt	$\textbf{dog}\parallel\pi_{\texttt{OBJ}}(\textbf{hurt})$

Table 2: Abstract denotations and statements

Abstract denotations and statements are convenient for representing semantics of various types of expressions and linguistic knowledge. Some examples are shown in Table 2.⁴⁴Negation and disjointness (“ $\parallel$ ”) are explained in §2.5.

2.4 Logical inference on DCS

Based on abstract denotations, we briefly describe our process to apply DCS to textual inference.

2.4.1 Natural language to DCS trees

To obtain DCS trees from natural language, we use Stanford CoreNLP⁵⁵http://nlp.stanford.edu/software/corenlp.shtml for dependency parsing [], and convert Stanford dependencies to DCS trees by pattern matching on POS tags and dependency labels.⁶⁶In [] DCS trees are learned from QA pairs and database entries. We obtain DCS trees from dependency trees, to bypass the need of a concrete database. Currently we use the following semantic roles: ARG, SUBJ, OBJ, IOBJ, TIME and MOD. The semantic role MOD is used for any restrictive modifiers. Determiners such as “all”, “every” and “each” trigger quantifiers, as shown in Figure 2.

{prooftree}\AxiomC

$\pi_{\texttt{OBJ}}(F_{4})=F_{3}\cap F_{7}$ \AxiomC $\pi_{\texttt{OBJ}}(F_{6})=\textbf{dog}\cap F_{7}$ \AxiomCT \UnaryInfC $F_{6}\neq\emptyset$ \AxiomCAxiom 4 \TrinaryInfC $\textbf{dog}\cap F_{7}\neq\emptyset$ \AxiomCT \UnaryInfC $\textbf{dog}\subset\pi_{\texttt{OBJ}}(F_{2})$ \AxiomC $\textbf{dog}\subset\textbf{animal}$ \AxiomCAxiom 8 \TrinaryInfC $\textbf{dog}\subset F_{3}$ \UnaryInfC $\textbf{dog}\cap F_{7}\subset F_{3}\cap F_{7}$ \AxiomCAxiom 6 \TrinaryInfC $F_{3}\cap F_{7}\neq\emptyset$ \AxiomCAxiom 4 \TrinaryInfC $F_{4}\neq\emptyset$

Figure 3: An example of proof using abstract denotations

2.4.2 DCS trees to statements

A DCS tree $\mathcal{T}=(\mathcal{N},\mathcal{E})$ is defined as a rooted tree, where each node $\sigma\in\mathcal{N}$ is labeled with a content word $w(\sigma)$ and each edge $(\sigma,\sigma^{\prime})\in\mathcal{E}\subset\mathcal{N}\times\mathcal{N}$ is labeled with a pair of semantic roles $(r,r^{\prime})$ ⁷⁷The definition differs slightly from the original , mainly for the sake of simplicity and clarity.. Here $\sigma$ is the node nearer to the root. Furthermore, for each edge $(\sigma,\sigma^{\prime})$ we can optionally assign a quantification marker.

Abstract denotation of a DCS tree can be calculated in a bottom-up manner. For example, the abstract denotation of H in Figure 2 is calculated from the leaf node Mary, and then:

Node love (Mary loves):
$F_{2}=\textbf{love}\cap(\textbf{Mary}_{\texttt{SUBJ}}\times W_{\texttt{OBJ}})$

Node animal (Animal that Mary loves):
$F_{3}=\textbf{animal}\cap\pi_{\texttt{OBJ}}(F_{2})$

Node have (Tom has an animal that Mary loves):
$F_{4}=\textbf{have}\cap(\textbf{Tom}_{\texttt{SUBJ}}\times(F_{3})_{\texttt{OBJ% }})$ .

Formally, suppose the root $\sigma$ of a DCS tree $\mathcal{T}$ has children $\tau_{1},\ldots,\tau_{n}$ , and edges $(\sigma,\tau_{1}),\ldots,(\sigma,\tau_{n})$ labeled by $(r_{1},r^{\prime}_{1}),\ldots,(r_{n},r^{\prime}_{n})$ , respectively. The abstract denotation of $\mathcal{T}$ is defined as:

[\![\mathcal{T}]\!]\!=\!w(\sigma)\cap(\bigcap_{i=1}^{n}\iota_{r_{i}}(\pi_{r^{% \prime}_{i}}([\![\mathcal{T}_{\tau_{i}}]\!]))\times W_{R_{\sigma}\setminus r_{% i}}),

where $\mathcal{T}_{\tau_{i}}$ is the subtree of $\mathcal{T}$ rooted at $\tau_{i}$ , and $R_{\sigma}$ is the set of possible semantic roles for content word $w(\sigma)$ (e.g. $R_{\textbf{love}}=\{\texttt{SUBJ},\texttt{OBJ}\}$ ), and $W_{R_{\sigma}\setminus r_{i}}$ is the product of $W$ which has dimension $R_{\sigma}\setminus r_{i}$ (e.g. $W_{\{\texttt{SUBJ},\texttt{OBJ}\}\setminus\texttt{SUBJ}}=W_{\texttt{OBJ}}$ ).

When universal quantifiers are involved, we need to add division operators to the formula. If $(\sigma,\tau_{i})$ is assigned by a quantification marker “ $\subset$ ”⁸⁸Multiple quantifiers can be processed similarly., then the abstract denotation is⁹⁹The result of $[\![\mathcal{T}]\!]$ depends on the order of the children $\tau_{1},\ldots,\tau_{n}$ . Different orders correspond to readings of different quantifier scopes.

[\![\mathcal{T}]\!]\!=\!q_{\subset}^{r_{i}}(\pi_{R_{\sigma}\setminus\{r_{1},% \ldots,r_{i-1}\}}([\![\mathcal{T}^{\prime}]\!]),\pi_{r_{i}^{\prime}}([\![% \mathcal{T}_{\tau_{i}}]\!])),

where $\mathcal{T}^{\prime}$ is the same tree as $\mathcal{T}$ except that the edge $(\sigma,\tau_{i})$ is removed. For example, the abstract denotation of the first sentence of T in Figure 2 (Mary loves every dog) is calculated from $F_{2}$ (Mary loves) as

F_{5}=q_{\subset}^{\texttt{OBJ}}(\pi_{\texttt{OBJ}}(F_{2}),\textbf{dog}).

After the abstract denotation $[\![\mathcal{T}]\!]$ is calculated, the statement representing the meaning of the sentence is defined as $[\![\mathcal{T}]\!]\neq\emptyset$ . For example, the statement of “students read books” is $\textbf{read}\cap(\textbf{student}_{\texttt{SUBJ}}\times\textbf{book}_{\texttt% {OBJ}})\neq\emptyset$ , and the statement of “Mary loves every dog” is $q_{\subset}^{\texttt{OBJ}}(\pi_{\texttt{OBJ}}(F_{2}),\textbf{dog})\neq\emptyset$ , which is logically equivalent to $\textbf{dog}\subset\pi_{\texttt{OBJ}}(F_{2})$ .¹⁰¹⁰See Footnote 2,3.

2.4.3 Logical inference

W\neq\emptyset

A\cap B\subset A

B_{r}\times q^{r}_{\subset}(A,B)\subset A

\pi_{R}(A)\neq\emptyset\Leftrightarrow A\neq\emptyset

(A\subset B\;\&\;B\subset C)\Rightarrow A\subset C

(A\subset B\;\&\;A\neq\emptyset)\Rightarrow B\neq\emptyset

A\subset B\Rightarrow\pi_{R}(A)\subset\pi_{R}(B)

(C\subset A\;\&\;C\subset B)\Rightarrow C\subset A\cap B

Table 3: An excerpt of axioms

Since meanings of sentences are represented by statements on abstract denotations, logical inference among sentences is reduced to deriving new relations among abstract denotations. This is done by applying axioms to known statements, and approximately 30 axioms are implemented (Table 3). These are algebraic properties of abstract denotations, among which we choose a set of axioms that can be handled efficiently and enable most common types of inference seen in natural language.

For the example in Figure 2, by constructing the following abstract denotations:

Tom has a dog:
$F_{6}=\textbf{have}\cap(\textbf{Tom}_{\texttt{SUBJ}}\times\textbf{dog}_{% \texttt{OBJ}})$

Objects that Tom has:
$F_{7}=\pi_{\texttt{OBJ}}(\textbf{have}\cap(\textbf{Tom}_{\texttt{SUBJ}}\times W% _{\texttt{OBJ}}))$ ,

we can use the lexical knowledge $\textbf{dog}\subset\textbf{animal}$ , the statements of T (i.e. $\textbf{dog}\subset\pi_{\texttt{OBJ}}(F_{2})$ and $F_{6}\neq\emptyset$ ), and the axioms in Table 3,¹¹¹¹Algebraic identities, such as $\pi_{\texttt{OBJ}}(F_{4})=F_{3}\cap F_{7}$ and $\pi_{\texttt{OBJ}}(F_{6})=\textbf{dog}\cap F_{7}$ , are also axioms. to prove the statement of H (i.e. $F_{4}\neq\emptyset$ ) (Figure 3).

We built an inference engine to perform logical inference on abstract denotations as above. In this logical system, we treat abstract denotations as terms and statements as atomic sentences, which are far more easier to handle than first order predicate logic (FOL) formulas. Furthermore, all implemented axioms are horn clauses, hence we can employ forward-chaining, which is very efficient.

2.5 Extensions

Further extensions of our framework are made to deal with additional linguistic phenomena, as briefly explained below.

Negation

To deal with negation in our forward-chaining inference engine, we introduce one more relation on abstract denotations, namely disjointness $A\parallel B$ , meaning that $A$ and $B$ are disjoint sets. Using disjointness we implemented two types of negations: (i) atomic negation, for each content word $w$ we allow negation $\bar{w}$ of that word, characterized by the property $w\parallel\bar{w}$ ; and (ii) root negation, for a DCS tree $\mathcal{T}$ and its denotation $[\![\mathcal{T}]\!]$ , the negation of $\mathcal{T}$ is represented by $\mathcal{T}\parallel\mathcal{T}$ , meaning that $\mathcal{T}=\emptyset$ in its effect.

Selection

Selection operators in relational algebra select a subset from a set to satisfy some specific properties. This can be employed to represent linguistic phenomena such as downward monotonicity and generalized quantifiers. In the current system, we implement (i) superlatives, e.g. $s_{highest}(\textbf{mountain}\cap(W_{\texttt{ARG}}\times\textbf{Asia}_{\texttt% {MOD}}))$ (the highest mountain in Asia) and (ii) numerics, e.g. $s_{two}(\textbf{pet}\cap\textbf{fish})$ (two pet fish), where $s_{f}$ is a selection marker. Selection operators are implemented as markers assigned to abstract denotations, with specially designed axioms. For example superlatives satisfy the following property: $A\subset B\;\&\;s_{highest}(B)\subset A\Rightarrow s_{highest}(B)=s_{highest}(A)$ . New rules can be added if necessary.

Coreference

We use Stanford CoreNLP to resolve coreferences [], whereas coreference is implemented as a special type of selection. If a node $\sigma$ in a DCS tree $\mathcal{T}$ belongs to a mention cluster $m$ , we take the abstract denotation $[\![\mathcal{T}_{\sigma}]\!]$ and make a selection $s_{m}([\![\mathcal{T}_{\sigma}]\!])$ , which is regarded as the abstract denotation of that mention. Then all selections of the same mention cluster are declared to be equal.

3 Generating On-the-fly Knowledge

Recognizing textual entailment (RTE) is the task of determining whether a given textual statement H can be inferred by a text passage T. For this, our primary textual inference system operates as:

1.

For a T-H pair, apply dependency parsing and coreference resolution.
2.

Perform rule-based conversion from dependency parses to DCS trees, which are translated to statements on abstract denotations.
3.

Use statements of T and linguistic knowledge as premises, and try to prove statements of H by our inference engine.

However, this method does not work for real-world datasets such as PASCAL RTE [], because of the knowledge bottleneck: it is often the case that the lack of sufficient linguistic knowledge causes failure of inference, thus the system outputs “no entailment” for almost all pairs [].

Figure 4: RTE system

The transparent syntax-to-semantics interface of DCS enables us to back off to NLP techniques during inference for catching up the lack of knowledge. We extract fragments of DCS trees as paraphrase candidates, translate them back to linguistic expressions, and apply distributional similarity to judge their validity. In this way, our framework combines distributional and logical semantics, which is also the main subject of and .

As follows, our full system (Figure 4) additionally invokes linguistic knowledge on-the-fly:

4.

If H is not proven, compare DCS trees of T and H, and generate path alignments.
5.

Aligned paths are evaluated by a similarity score to estimate their likelihood of being paraphrases. Path alignments with scores higher than a threshold are accepted.
6.

Convert accepted path alignments into statements on abstract denotations, use them in logical inference as new knowledge, and try to prove H again.

3.1 Generating path alignments

On-the-fly knowledge is generated by aligning paths in DCS trees. A path is considered as joining two germs in a DCS tree, where a germ is defined as a specific semantic role of a node. For example, Figure 5 shows DCS trees of the following sentences (a simplified pair from RTE2-dev):

T: Tropical storm Debby is blamed for deaths.
H: A storm has caused loss of life.

The germ $\texttt{OBJ}(\textbf{blame})$ and germ $\texttt{ARG}(\textbf{death})$ in DCS tree of T are joined by the underscored path. Two paths are aligned if the joined germs are aligned, and we impose constraints on aligned germs to inhibit meaningless alignments, as described below.

3.2 Aligning germs by logical clues

Two germs are aligned if they are both at leaf nodes (e.g. $\texttt{ARG}(\textbf{death})$ in T and $\texttt{ARG}(\textbf{life})$ in H, Figure 5), or they already have part of their meanings in common, by some logical clues.

To formulate this properly, we define the abstract denotation of a germ, which, intuitively, represents the meaning of the germ in the specific sentence. The abstract denotation of a germ is defined in a top-down manner: for the root node $\rho$ of a DCS tree $\mathcal{T}$ , we define its denotation $[\![\rho]\!]_{\mathcal{T}}$ as the denotation of the entire tree $[\![\mathcal{T}]\!]$ ; for a non-root node $\tau$ and its parent node $\sigma$ , let the edge $(\sigma,\tau)$ be labeled by semantic roles $(r,r^{\prime})$ , then define

[\![\tau]\!]_{\mathcal{T}}=[\![\mathcal{T}_{\tau}]\!]\cap(\iota_{r^{\prime}}(% \pi_{r}([\![\sigma]\!]_{\mathcal{T}}))\times W_{R_{\tau}\setminus r^{\prime}}).

Now for a germ $r(\sigma)$ , the denotation is defined as the projection of the denotation of node $\sigma$ onto the specific semantic role $r$ : $[\![r(\sigma)]\!]_{\mathcal{T}}=\pi_{r}([\![\sigma]\!]_{\mathcal{T}})$ .

For example, the abstract denotation of germ $\texttt{ARG}(\textbf{book})$ in Figure 1 is defined as $\pi_{\texttt{ARG}}(\textbf{book}\cap\pi_{\texttt{OBJ}}(\textbf{read}\cap(% \textbf{student}_{\texttt{SUBJ}}\times\textbf{book}_{\texttt{OBJ}})))$ , meaning “books read by students”. Similarly, denotation of germ $\texttt{OBJ}(\textbf{blame})$ in T of Figure 5 indicates the object of “blame” as in the sentence “Tropical storm Debby is blamed for death”, which is a tropical storm, is Debby, etc. Technically, each germ in a DCS tree indicates a variable when the DCS tree is translated to a FOL formula, and the abstract denotation of the germ corresponds to the set of consistent values [] of that variable.

Figure 5: Aligned paths (underscored by the solid lines) and aligned germs (joined by the dotted line)

The logical clue to align germs is: if there exists an abstract denotation, other than $W$ , that is a superset of both abstract denotations of two germs, then the two germs can be aligned. A simple example is that $\texttt{ARG}(\textbf{storm})$ in T can be aligned to $\texttt{ARG}(\textbf{storm})$ in H, because their denotations have a common superset other than $W$ , namely $\pi_{\texttt{ARG}}(\textbf{storm})$ . A more complicated example is that $\texttt{OBJ}(\textbf{blame})$ and $\texttt{SUBJ}(\textbf{cause})$ can be aligned, because inference can induce $[\![\mbox{{OBJ}}(\mbox{{blame}})]\!]_{\mbox{{T}}}$ = $[\![\mbox{{ARG}}(\mbox{{Debby}})]\!]_{\mbox{{T}}}$ = $[\![\mbox{{ARG}}(\mbox{{storm}})]\!]_{\mbox{{T}}}$ , as well as $[\![\mbox{{SUBJ}}(\mbox{{cause}})]\!]_{\mbox{{H}}}$ = $[\![\mbox{{ARG}}(\mbox{{storm}})]\!]_{\mbox{{H}}}$ , so they also have the common superset $\pi_{\texttt{ARG}}(\textbf{storm})$ . However, for example, logical clues can avoid aligning $\texttt{ARG}(\textbf{storm})$ to $\texttt{ARG}(\textbf{loss})$ , which is obviously meaningless.

3.3 Scoring path alignments by similarity

Aligned paths are evaluated by a similarity score, for which we use distributional similarity of the words that appear in the paths (§4.1). Only path alignments with high similarity scores can be accepted. Also, we only accept paths of length $\leq 5$ , to prevent too long paths to be aligned.

3.4 Applying path alignments

Figure 6: Tree transformation and generated on-the-fly knowledge (subsumption of denotations shown above the trees)

Accepted aligned paths are converted into statements, which are used as new knowledge. The conversion is done by first performing a DCS tree transformation according to the aligned paths, and then declare a subsumption relation between the denotations of aligned germs. For example, to apply the aligned path pair generated in Figure 5, we use it to transform T into a new tree T’ (Figure 6), and then the aligned germs, OBJ(blame) in T and SUBJ(cause) in T’, will generate the on-the-fly knowledge: $[\![\mbox{{OBJ}}(\mbox{{blame}})]\!]_{\mbox{{T}}}$ $\subset$ $[\![\mbox{{SUBJ}}(\mbox{{cause}})]\!]_{\mbox{{T'}}}$ .

Similar to the tree transformation based approach to RTE [], this process can also utilize lexical-syntactic entailment rules []. Furthermore, since the on-the-fly knowledge is generated by transformed pairs of DCS trees, all contexts are preserved: in Figure 6, though the tree transformation can be seen as generated from the entailment rule “X is blamed for death $\rightarrow$ X causes loss of life”, the generated on-the-fly knowledge, as shown above the trees, only fires with the additional condition that $X$ is a tropical storm and is Debby. Hence, the process can also be used to generate knowledge from context sensitive rules [], which are known to have higher quality [].

However, it should be noted that using on-the-fly knowledge in logical inference is not a trivial task. For example, the FOL formula of the rule “X is blamed for death $\rightarrow$ X causes loss of life” is:

\forall x;(\exists a;blame(x,a)\;\&\;death(a))\rightarrow\\ (\exists b,c;cause(x,b)\;\&\;loss(b,c)\;\&\;life(c)),

which is not a horn clause. The FOL formula for the context-preserved rule in Figure 6 is even more involved. Still, it can be efficiently treated by our inference engine because as a statement, the formula $[\![\mbox{{OBJ}}(\mbox{{blame}})]\!]_{\mbox{{T}}}$ $\subset$ $[\![\mbox{{SUBJ}}(\mbox{{cause}})]\!]_{\mbox{{T'}}}$ is an atomic sentence, more than a horn clause.

4 Experiments

In this section, we evaluate our system on FraCaS (§4.2) and PASCAL RTE datasets (§4.3).

4.1 Language Resources

The lexical knowledge we use are synonyms, hypernyms and antonyms extracted from WordNet¹²¹²http://wordnet.princeton.edu/. We also add axioms on named entities, stopwords, numerics and superlatives. For example, named entities are singletons, so we add axioms such as $\forall x;(x\subset\mbox{{Tom}}\;\&\;x\neq\emptyset)\rightarrow\mbox{{Tom}}\subset x$ .

To calculate the similarity scores of path alignments, we use the sum of word vectors of the words from each path, and calculate the cosine similarity. For example, the similarity score of the path alignment “OBJ(blame)IOBJ-ARG(death) $\approx$ SUBJ(cause)OBJ-ARG(loss)MOD-ARG(life)” is calculated as the cosine similarity of vectors blame+death and cause+loss+life. Other structures in the paths, such as semantic roles, are ignored in the calculation. The word vectors we use are from ¹³¹³http://code.google.com/p/word2vec/ (Mikolov13), and additional results are also shown using ¹⁴¹⁴http://metaoptimize.com/projects/wordreprs/ (Turian10). The threshold for accepted path alignments is set to $0.4$ , based on pre-experiments on RTE development sets.

4.2 Experiments on FraCaS

The FraCaS test suite contains 346 inference problems divided into 9 sections, each focused on a category of semantic phenomena. We use the data by , and experiment on the first section, Quantifiers, following . This section has 44 single premise and 30 multi premise problems. Most of the problems do not require lexical knowledge, so we use our primary textual inference system without on-the-fly knowledge nor WordNet, to test the performance of the DCS framework as formal semantics. To obtain the three-valued output (i.e. yes, no, and unknown), we output “yes” if H is proven, or try to prove the negation of H if H is not proven. To negate H, we use the root negation as described in §2.5. If the negation of H is proven, we output “no”, otherwise we output “unknown”.

The result is shown in Table 4. Since our system uses an off-the-shelf dependency parser, and semantic representations are obtained from simple rule-based conversion from dependency trees, there will be only one (right or wrong) interpretation in face of ambiguous sentences. Still, our system outperforms ’s probabilistic CCG-parser. Compared to and , our system does not need a pre-trained alignment model, and it improves by making multi-sentence inferences. To sum up, the result shows that DCS is good at handling universal quantifiers and negations.

	Single Prem.	Multi Prem.
Lewis13	70	50
MacCartney07	84.1	-
MacCartney08	97.7	-
Our Sys.	79.5	80.0

Table 4: Accuracy (%) on FraCaS

Most errors are due to wrongly generated DCS trees (e.g. wrongly assigned semantic roles) or unimplemented quantifier triggers (e.g. “neither”) or generalized quantifiers (e.g. “at least a few”). These could be addressed by future work.

	RTE2			RTE3			RTE4			RTE5
	Prec.	Rec.	Acc.	Prec.	Rec.	Acc.	Prec.	Rec.	Acc.	Prec.	Rec.	Acc.
Primary	70.9	9.8	52.9	73.2	7.3	51.1	89.7	5.2	52.3	82.6	6.3	52.5
+On-the-fly	57.6	66.5	58.8	63.7	64.6	63.0	60.0	57.4	59.6	69.9	55.7	65.8

Table 5: Impact of on-the-fly knowledge

4.3 Experiments on PASCAL RTE datasets

On PASCAL RTE datasets, strict logical inference is known to have very low recall [], so on-the-fly knowledge is crucial in this setting. We test the effect of on-the-fly knowledge on RTE2, RTE3, RTE4 and RTE5 datasets, and compare our system with other approaches.

4.3.1 Impact of on-the-fly knowledge

Results on test data are shown in Table 5. When only primary knowledge is used in inference (the first row), recalls are actually very low; After we activate the on-the-fly knowledge, recalls jump to over 50%, with a moderate fall of precision. As a result, accuracies significantly increase.

4.3.2 Comparison to other RTE systems

	RTE2	RTE3	RTE4	RTE5
Bos06	60.6	-	-	-
MacCartney08	-	59.4	-	-
Clark08	-	-	56.5	-
Wang10	63.0	61.1	-	-
Stern11	61.6	67.1	-	63.5
Stern12	-	-	-	64.0
Our Sys.	58.8	63.0	59.6	65.8

Table 6: Comparison with other systems

A comparison between our system and other RTE systems is shown in Table 6. Bos06 [] is a hybrid system combining deep features from a theorem prover and a model builder, together with shallow features such as lexical overlap and text length. MacCartney08 [] uses natural logic to calculate inference relations between two superficially aligned sentences. Clark08 [] is a logic-based system utilizing various resources including WordNet and DIRT paraphrases [], and is tolerant to partially unproven H sentences in some degree. All of the three systems pursue a logical approach, while combining various techniques to achieve robustness. The result shows that our system has comparable performance. On the other hand, Wang10 [] learns a tree-edit model from training data, and captures entailment relation by tree edit distance. Stern11 [] and Stern12 [] extend this framework to utilize entailment rules as tree transformations. These are more tailored systems using machine learning with many handcrafted features. Still, our unsupervised system outperforms the state-of-the-art on RTE5 dataset.

4.3.3 Analysis

Figure 7: Proportion of proven pairs and their precision, w.r.t. pieces of on-the-fly knowledge.

Summing up test data from RTE2 to RTE5, Figure 7 shows the proportion of all proven pairs and their precision. Less than 5% pairs can be proven primarily, with a precision of 77%. Over 40% pairs can be proven by one piece of on-the-fly knowledge, yet pairs do exist in which more than 2 pieces are necessary. The precisions of 1 and 2 pieces on-the-fly knowledge application are over 60%, which is fairly high, given our rough estimation of the similarity score. As a comparison, studied the proportion of proven pairs and precision by applying DIRT rules to tree skeletons in RTE2 and RTE3 data. The proportion is 8% with precision 65% on RTE2, and proportion 6% with precision 72% on RTE3. Applied by our logical system, the noisy on-the-fly knowledge can achieve a precision comparable to higher quality resources such as DIRT.

A major type of error is caused by the ignorance of semantic roles in calculation of similarity scores. For example, though “Italy beats Kazakhstan” is not primarily proven from “Italy is defeated by Kazakhstan”, our system does produce the path alignment “SUBJ(beat)OBJ $\approx$ OBJ(defeat)SUBJ” with a high similarity score. The impact of such errors depends on the data making methodology, though. It lowers precisions in RTE2 and RTE3 data, particularly in “IE” subtask (where precisions drop under $0.5$ ). On the other hand, it occurs less often in “IR” subtask.

Finally, to see if we “get lucky” on RTE5 data in the choice of word vectors and thresholds, we change the thresholds from $0.1$ to $0.7$ and draw the precision-recall curve, using two types of word vectors, Mikolov13 and Turian10. As shown in Figure 8, though the precision drops for Turian10, both curves show the pattern that our system keeps gaining recall while maintaining precision to a certain level. Not too much “magic” in Mikolov13 actually: for over 80% pairs, every node in DCS tree of H can be covered by a path of length $\leq 5$ that has a corresponding path of length $\leq 5$ in T with a similarity score $>0.4$ .

Figure 8: Precision-Recall curve.

5 Conclusion and Discussion

We have presented a method of deriving abstract denotation from DCS trees, which enables logical inference on DCS, and we developed a textual inference system based on the framework. Experimental results have shown the power of the representation that allows both strict inference as on FraCaS data and robust reasoning as on RTE data.

Exploration of an appropriate meaning representation for querying and reasoning on knowledge bases has a long history. Description logic, being less expressive than FOL but featuring more efficient reasoning, is used as a theory base for Semantic Web []. Ideas similar to our framework, including the use of sets in a representation that benefits efficient reasoning, are also found in description logic and knowledge representation community []. To our knowledge, however, their applications to logical inference beyond the use for database querying have not been much explored in the context of NLP.

The pursue of a logic more suitable for natural language inference is not new. For instance, has implemented a model of natural logic []. While being computationally efficient, various inference patterns are out of the scope of their system.

Much work has been done in mapping natural language into database queries []. Among these, the ( $\lambda$ -)DCS [] framework defines algorithms that transparently map a labeled tree to a database querying procedure. Essentially, this is because DCS trees restrict the querying process to a very limited subset of possible operations. Our main contribution, the abstract denotation of DCS trees, can thus be considered as an attempt to characterize a fragment of FOL that is suited for both natural language inference and transparent syntax-semantics mapping, through the choice of operations and relations on sets.

We have demonstrated the utility of logical inference on DCS through the RTE task. A wide variety of strategies tackling the RTE task have been investigated [], including the comparison of surface strings [], syntactic and semantic structures [], semantic vectors [] and logical representations []. Acquisition of basic knowledge for RTE is also a huge stream of research []. These previous works include various techniques for acquiring and incorporating different kinds of linguistic and world knowledge, and further fight against the knowledge bottleneck problem, e.g. by back-off to shallower representations.

Logic-based RTE systems employ various approaches to bridge knowledge gaps. proposes features from a model builder; proposes an abduction process; shows handcrafted rules could drastically improve the performance of a logic-based RTE system.

As such, our current RTE system is at a proof-of-concept stage, in that many of the above techniques are yet to be implemented. Nonetheless, we would like to emphasize that it already shows performance competitive to state-of-the-art systems on one data set (RTE5). Other directions of our future work include further exploitation of the new semantic representation. For example, since abstract denotations are readily suited for data querying, they can be used to verify newly generated assumptions by fact search in a database. This may open a way towards a hybrid approach to RTE wherein logical inference is intermingled with large scale database querying.

Acknowledgments

This research was supported by the Todai Robot Project at National Institute of Informatics.

References

Generated on Tue Jun 10 17:14:51 2014 by LaTeXML [LOGO]