=Paper=
{{Paper
|id=Vol-2052/paper5
|storemode=property
|title=Machine Comprehension of Text Using Combinatory Categorial Grammar and Answer Set Programs
|pdfUrl=https://ceur-ws.org/Vol-2052/paper5.pdf
|volume=Vol-2052
|authors=Piotr Chabierski,Alessandra Russo,Mark Law,Krysia Broda
|dblpUrl=https://dblp.org/rec/conf/commonsense/ChabierskiRLB17
}}
==Machine Comprehension of Text Using Combinatory Categorial Grammar and Answer Set Programs==
https://ceur-ws.org/Vol-2052/paper5.pdf
Machine Comprehension of Text Using Combinatory Categorial
Grammar and Answer Set Programs
Piotr Chabierski, Alessandra Russo, Mark Law, and Krysia Broda
Department of Computing, Imperial College London, SW7 2AZ
{piotr.chabierski13, a.russo, mark.law09, k.broda}@imperial.ac.uk
Abstract Programs (ASP) from narratives written in English in
a general and principled manner, demonstrating how
We present an automated method for generat-
such a representation can be used to answer questions
ing Answer Set Programs from narratives writ-
ten in English and demonstrate how such a repre- about text. Similarly to (Baral, Dzifcak, and Son 2008),
sentation can be used to answer questions about the proposed approach relies on a transparent interface
text. The proposed approach relies on a transpar- between syntax and semantics of natural language of-
ent interface between the syntax and semantics of fered by Combinatory Categorial Grammars to trans-
natural language provided by Combinatory Cat- late the text to ASP. The outcome of this translation
egorial Grammars to translate text into Answer creates a form of knowledge base that, together with
Set Programs, hence creating a knowledge base background knowledge, can later be queried. However,
that, together with background knowledge, can the generation of ASP representations from text uses
be queried. an intermediate representation, called -ASP⇤ calcu-
lus, that di↵ers from the -ASP calculus proposed in
Introduction (Baral, Dzifcak, and Son 2008) in two ways. It is more
Machine comprehension of text is a long-term open general and can handle more advanced grammatical and
problem in Artificial Intelligence and can be assessed linguistic constructions such as, among others, relativi-
by a machine’s ability to answer questions about pas- sation, control and raising. It uses a general-purpose
sages of text. One of the main challenges is the capac- ASP representation language designed with the objec-
ity to automatically process the text and capture the tive of making it suitable for efficient automated learn-
natural language semantics. Various approaches have ing of common sense knowledge relevant to a given nar-
been proposed in the literature, e.g. (Bos et al. 2004), rative, by means of current state-of-the-art systems for
in particular for translating natural language sentences learning ASP programs (Law, Russo, and Broda 2014).
into first-order logic sentences. More recently, (Baral, Due to space limitations, this latter feature is outside
Dzifcak, and Son 2008) has followed a di↵erent direc- the scope of the paper. Our proposed fully automated
tion. Motivated by the need of expressing the (default) mechanism is also applicable to the generation of ASP
semantics of normative statements, Baral et al. have representation of a large class of questions, including
provided a first-step towards an automated way for polar questions and “wh-word” questions that require
translating natural language statements into ASP pro- single word answers. The main contributions of this
grams, by making use of an intermediate representation, paper are therefore:
called -ASP, to construct the semantic representation • a general-purpose ASP representation for narratives
of sentences from its constituents. The -ASP calcu- written in natural language
lus relies on a combinatory categorial grammar (CCG) • a -ASP⇤ calculus that covers complex linguistic phe-
derivation (Steedman 2000) to represent the syntactic nomena such as coordination, relativisation, control
structure of a sentence. To the best of our knowledge, and raising
although e↵ective in expressing normative statements, • a wide-coverage algorithm capable of performing
this approach is mainly confined to a specific dataset translation from natural language to ASP, and
of sentences. Consequently, the -ASP representation
is limited to the generation of domain-specific semantic • an automatic translation into ASP of questions re-
representations, and, as also pointed out by the authors quiring one-word answers (what, where, who, which).
in (Baral, Dzifcak, and Son 2008), it does not support The e↵ectiveness of the approach is demonstrated by
more complex linguistic constructs such as adverbs or using a publicly available dataset (Weston et al. 2015)
conjunction. as well as an hand-crafted set of sentences, specifically
This paper addresses these limitations by presenting designed to capture the various complex linguistic con-
a fully automated method for generating Answer Set structs supported by the approach.
Background set of syntactic combinatory rules specifies how adja-
In what follows, we outline the two main background cent constituents are combined. The most basic rules
formalisms used in our approach, namely answer set are forward (FA) and backward (BA) application:
programming and combinatory categorical grammars. FA (>): X/Y : f Y : a =) X : f (a)
BA (<): Y : a X\Y : f =) X : f (a)
Answer Set Programming (ASP) is an expressive
language for knowledge representation and reasoning, Composition combinatory rules allow two functor cate-
based on the stable model semantics (Gelfond and Lifs- gories to combine and produce another functor. Exam-
chitz 1988) and rooted in the field of non-monotonic rea- ple of a composition rule is forward composition (FC):
soning and logic programming (Lifschitz 2008). Within FC (> B): X/Y : f Y /Z : g =) X/Z : x.f (g(x))
the scope of this paper, Answer Set Programs are re-
stricted to normal logic programs. So, an ASP program Type-raising combinatory rules allow an argument cat-
is a set of normal rules of the form: egory Y to become a functor category X/(X\Y ) or
X\(X/Y ). Forward type-raising rule (FT) is given by:
r: h
|{z} b1 , b2 , . . . , bm , not bm+1 , . . . not bm+k
| {z } FT (> T): Y : a =) X/(X\Y ) : f.f (a)
head(r) body(r)
Composition together with type-raising rules are used
where h, b1 , b2 , . . . , bm and not bm+1 , . . . not bm+k are to handle coordination and non-local dependencies in-
positive and negated atoms respectively with not denot- troduced, for example, by relative clauses, which is il-
ing negation-as-failure. A fact is a rule whose body is lustrated by the following syntactic derivation for a rel-
empty (m = k = 0). ative clause: that Jack wanted, from a sentence: The
The Herbrand Base HB(P ) of an ASP program P car that Jack wanted was expensive.
is the set of all ground atoms constructed using predi-
cate symbols, constants and function symbols in P . An Jack
Herbrand interpretation of P assigns a truth value to NP wanted
>T
every atom in HB(P ) and is a model of P if for every that S/(S\N P ) (S\N P )/N P
>B
ground rule r in P such that body(r) is satisfied head(r) (N \N )/(S/N P ) S\N P
>
is true. An Herbrand model M of P is minimal if no N \N
proper subset of M is a model of P . Given an ASP pro-
gram P and a set M of ground atoms, the reduct P M The predicate structure can be obtained directly from
of P is the logic program obtained from P by removing the syntactic derivation, provided that the semantics of
every: lexical items, assigned by the lexicon, is known. Using
a CCG syntactic derivation and first-order logic aug-
• rule that has a literal not p in its body, where p 2 M mented with -calculus, for a sentence: Jack buys cars
• negated literal in the bodies of the remaining rules derivation of a first-order representation can be per-
formed as follows:
M is an answer set of P if it coincides with the minimal
Herbrand model of P M . buys cars
Jack (S\N P )/N P : x. y.buy(y, x) N P : cars
Combinatory Categorial Grammar (CCG) is >
N P : jack (S\N P ) : y.buy(y, cars)
an efficiently parsable grammar that enables semantic <
analysis of natural language by providing a transparent S : buy(jack, cars)
interface between syntax and semantics. In CCG, words
are assigned syntactic categories defining their syntac- Representing Natural Language in ASP
tic behaviour. The set of CCG categories comprises The signature of the ASP logical representation used in
of atomic categories and complex categories, recursively our approach, to express sentences written in English,
constructed from the atomic categories. Examples of consists of four classes of predicates: nominals, events,
atomic categories include: N (bare noun), N P (noun modifiers and prepositions. The name of each predi-
phrase) and S (sentence). Complex categories are of the cate is composed of an arity prefix, which indicates the
forms X/Y and X\Y and define functors that, when number of arguments taken by the corresponding word,
applied to an argument of category Y , produce a re- and a class suffix, which takes one of the four aforemen-
sult of category X. Directionality of the slash indicates tioned values. For example, a transitive verb buy is rep-
whether the argument has to occur immediately to the resented by the predicate: binaryEvent(e1 , buy, c1 , n0 )
left “/” or to the right “\” of the functor. For example, where the first argument e1 serves as an identifier, buy
(S\N P )/N P is the category of a transitive verb buy in is a lemma of the corresponding word and c1 , n0 are
a sentence Jack bought a car. arguments of the verb (agent and theme respectively).
CCG provides a surface-compositional interface be- For the sake of conciseness, throughout this paper the
tween syntax and semantics in which there is one-to- arity prefixes are skipped and nominals, events, modi-
one mapping between the rules of syntactic and seman- fiers and prepositions are abbreviated in the predicate
tic composition (Hockenmaier and Steedman 2007). A names as nom, ev, mod and prep respectively.
Preliminary Text Analysis Splitting text into sentences, tokenisation, lemma-
First, the input text is split into sentences and tokens. tisation, POS tagging, named entity recognition and
Subsequently, every word in the input text is tagged coreference resolution is performed using Stanford
with the following set of annotations: CoreNLP (Manning et al. 2014). For syntactic parsing
and semantic role labeling EasySRL (Lewis, He, and
• Lemma - inflection-free form of the word, used as an Zettlemoyer 2015) is used.
argument of the corresponding predicate
• Part-of-speech (POS) tag - used by the lexicon to -ASP⇤ Calculus
perform coarse division of words into classes -ASP⇤ calculus serves as an intermediate represen-
• Named entity tag - enriches the predicate structure tation between natural language and ASP. It follows
and allows to treat multi-word proper names as single the syntax of ASP but extends it with abstraction and
entities, e.g. Ei↵el Tower as eiffel_tower rather application as known from -calculus, which enables
than a nominal and a modifier compositional derivation of semantic representations of
• Coreference cluster - groups mentions of the same phrases and sentences from their constituents. -ASP⇤
entity in the text. Cluster identifiers are used to form expressions have the following general form:
identifiers of nominal predicates corresponding to en- [h1 , . . . hk ] v1 . . . vl . p1 (a11 , . . . a1r1 ), . . . pm (am m
1 , . . . arm ),
tity mentions, hence embedding coreference informa- | {z } | {z } | {z }
k heads l abstractors m predicates
tion in the predicate structure
w1 @(am+1 , . . . am+1 m+n
rm+1 ), . . . wn @(a1 , . . . am+n
rm+n )
• Semantic role - derived for predicate (verb) ar- |
1
{z }
guments. PropBank sense IDs (Kingsbury and n applications
Palmer 2002) are used to order predicate argu- where vi and wj are bound variables, arguments axy are
ments when generating predicate structure for verbs. bound variables or constants and pt are predicate names
For example, in a sentence: [Jack]ARG0 kicked [the included in the previously defined signature. Arities of
ball]ARG1 the transitive verb kicked is translated as: predicates and applications are denoted by r1 , . . . rm+n .
ev(e1 , kick, c0 , n0 ), were c0 and n0 are identifiers of Every predicate has a non-zero arity; however, applica-
Jack and the ball and they are ordered according to tions can take no arguments. In case of applications,
their sense IDs (0 and 1 respectively) bound variables wj are referred to as function place-
After annotating the text, a CCG parse tree is de- holders and are replaced by other -ASP⇤ expressions
rived for each sentence. The CCG parse tree is a binary to which arguments am+j j , . . . am+j
rm+j are applied. Predi-
tree whose leaf nodes correspond to lexical items and cates and applications constitute the body of a -ASP⇤
internal nodes to phrases, clauses or sentences. Leaves expression. Every -ASP⇤ expression has a non-empty
are identified by L as the first argument in the node’s set H of bound variables or constants, called expres-
descriptor, followed by the CCG category, POS tag and sion heads, which corresponds to the linguistic head of
the word itself. Descriptors of the internal nodes begin a phrase and can have more than one element to ac-
with the identifier T, followed by the CCG category. count for coordination. As an example, let us consider
Listing 1: CCG parse tree for a sentence A new and a -ASP⇤ expression for a transitive verb buy, given by:
safe car that Jack wanted to buy was really expensive. [e0 ] v1 . v0 .ev(e0 , buy, v0 , v1 ), (v1 ), (v0 )
1 Constant e0 is an identifier of the verb buy and also
2
3
a head of the expression. Bound variables v0 , v1 can
4 be replaced, via the process of application (described
5 further in this section), by constants and variables –
6
7 when the bound variable occurs as a predicate or ap-
8 plication argument, or by other -ASP⇤ expression –
9 when the bound variable is a function placeholder in
10
11 an application. The list of bound variables is followed
12 by an event predicate and two applications with no ar-
13
14
guments, which act as placeholders for the subject and
15 object of the verb buy.
16 For -ASP⇤ expression e, preds(e) and apps(e) de-
17
18 note the sets of all predicates and applications in e re-
19 spectively and abs(e) denotes the ordered list of bound
20 variables. The set of heads of e is denoted by He . For
21
22 p 2 preds(e), args(p) denotes the ordered list of argu-
23 ments of p; the same notation is used for applications.
24
25
Given two -ASP⇤ expressions e and f , the application
26 g = e@f , where v denotes the first bound variable in e,
27 is computed as follows:
• for every a 2 apps(e) of the form w@(b1 , b2 , . . . bk ), To ensure the same ordering of verb arguments for
if v = w, compute recursively f 0 = f @(b1 , b2 , . . . bk ), di↵erent grammatical constructions (for example pas-
which is equivalent to (((f @b1 )@b2 ) . . .)@bk , include sive vs. active voice) the arguments are ordered ac-
preds(f 0 ) and apps(f 0 ) in g, and set f = f 0 . If v 2 cording to their PropBank semantic role labels.
args(a), |Hf | copies of a are included in g and v in
the ith copy is replaced by the ith head of f . If v 6= w Word -ASP Expression
and v 62 args(a), unmodified a is included in g a [v0 ] v0 .(v0 )@(n0 )
new [v0 ] v0 .mod(new, v0 ), (v0 )
• for every p 2 preds(e), if v 2 args(p), |Hf | copies of
and [v2 , v1 ] v2 . v1 . v0 .(v2 )@(v0 ), (v1 )@(v0 )
p are included in g and v in the ith copy is replaced safe [v0 ] v0 .mod(saf e, v0 ), (v0 )
by the ith head of f . If v 62 p, p is included in g car [v0 ] v0 .nom(v0 , car), (v0 )
unmodified that [v0 ] v1 . v0 .(v1 )@(v0 )
• bound variables of g are given by: abs(g) = (abs(e) Jack [c0 ]nom(c0 , jack)
{v}) + abs(f ), where ‘ ’ denotes removal of an ele- really [v0 ] v0 .mod(really, v0 ), (v0 )
ment from a list and ‘+’ denotes list concatenation wanted [e0 ] v1 . v0 .ev(e0 , want, v0 , v1 ), (v1 )@(v0 )
to [v0 ] v0 .v0
• if v 2 He , Hg = (He \{v}) [ Hf . Otherwise, Hg = He
buy [e1 ] v1 . v0 .ev(e1 , buy, v0 , v1 ), (v1 ), (v0 )
Constant c is represented by an expression e such that was [v0 ] v0 .(v0 )
preds(e) = apps(e) = ;, abs(e) = [ ] and He = {c}. For expensive [expensive] v0 .mod(expensive, v0 ), (v0 )
variable v, expression e is modified so that abs(e) = [v].
Table 1: Lexicon entries for the lexical items from the
Lexicon example sentence.
In our approach, lexicon is an algorithm, which given
an input word together with the relevant annotations
(CCG category, POS tag, lemma, coreference cluster) Semantic Composition
derives the corresponding -ASP⇤ expression. -ASP⇤ The -ASP⇤ expression for a given phrase or sentence
expressions for content words and some prepositions is constructed bottom-up following the structure of the
consist of a single predicate and a di↵erent number CCG parse tree. For each leaf node, a -ASP⇤ expres-
of bound variables and applications. Each word is as- sion is assigned by the lexicon. For internal nodes, the
signed to one of five sub-lexicons (nominal, event, mod- relevant CCG combinatory rule is identified, based on
ifier, preposition, wh-word) based on the POS tag and the categories of the child nodes and used to derive
CCG category, which in turn determines the class of the the -ASP⇤ expression compositionally. All combina-
corresponding predicate. The arity of a predicate, for tory rules are realised using the -ASP⇤ expression:
all cases other than adverbs and some function words, is v0 . v1 .(v1 )@(v0 ). In case of type-raising rules, child
equal to the number of arguments of the CCG category node’s -ASP⇤ expression is assigned to v0 . For appli-
of the corresponding word. cation and composition rules child nodes’ -ASP⇤ ex-
Co-indexation is performed for the relevant CCG cat- pressions are identified as function and argument based
egories, such as the ones corresponding to raising and on their CCG categories, the former is assigned to v1
control verbs or relative pronouns. Our approach per- and the latter to v0 .
forms co-indexation for all categories listed in (Hocken- In our running example, the -ASP⇤ expression for a
maier and Steedman 2005) and it is realised via appli- noun phrase new and safe car is derived in three steps.
cation primitive of -ASP⇤ expressions. For example, Referring to Table 1, semantic representation for node
for a control verb wanted with a co-indexed CCG cate- in line 9 in Listing 1 is derived as follows:
gory: (S[dcl]\N Pi )/(S[to]\N Pi ) the -ASP⇤ expression
is: v1 . v2 .ev(e1 , want, v2 , v1 ), v1 @v2 . Cases when co- {[v2 , v1 ] v2 . v1 . v0 .(v2 )@(v0 ), (v1 )@(v0 )}@{
indexation has to be performed are identified by pattern [v3 ] v3 .mod(saf e, v3 ), (v3 )}
matching on CCG categories. ⌘ [v0 , v1 ] v1 . v0 .mod(saf e, v0 ), (v0 ), (v1 )@(v0 )
Application primitive is also used to translate co-
ordinate sentences whose constituents have the same For the node in line 7, we get the following expression:
CCG category. For example, in case of an adjective {[v0 , v1 ] v1 . v0 .mod(saf e, v0 ), (v0 ), (v1 )@(v0 )}@{
phrase new and safe the -ASP⇤ expression for coordi- [v2 ] v2 .mod(new, v2 ), (v2 )}
nator and is: [v2 , v1 ] v2 . v1 . v0 .(v2 )@(v0 ), (v1 )@(v0 ),
⌘ [v0 ] v0 .mod(saf e, v0 ), mod(new, v0 ), (v0 )
which is inferred from the CCG categories of the con-
juncts, namely (N/N ). In case of conjuncts that Finally, for the node in line 5, we get:
take more than one argument, such as transitive {[v0 ] v0 .mod(saf e, v0 ), mod(new, v0 ), (v0 )}@{
verbs buy and sell in the sentence: Jack buys and
[v1 ] v1 .nom(v1 , car), (v1 )}
sells oil, the number of arguments of applications oc-
curring in the -ASP⇤ expression is set accordingly: ⌘ [v1 ] v1 .mod(saf e, v1 ), mod(new, v1 ),
[v3 , v2 ] v3 . v2 . v1 . v0 .(v3 )@(v1 , v0 ), (v2 )@(v1 , v0 ). nom(v1 , car), (v1 )
Translation of Questions the given rule or some other predicate already included
Our approach for generating ASP representations from in the body. A set of facts, corresponding to the existen-
text is also applicable to polar questions and questions tial quantification, is also derived by applying Skolem
that require one word answer, such as questions starting constants to the -ASP⇤ expression. As an example,
with wh-words: what, where, who and which. let us consider a sentence: Jack and Jim enjoy opera,
For polar questions, the same translation approach, with the -ASP⇤ expression given by:
described so far, is used to derive the corresponding - [e0 ] v1 .nom(c1 , jack), nom(c2 , jim), nom(v1 , opera),
ASP⇤ expressions with the only di↵erences being that ev(e0 , enjoy, c1 , v1 ), ev(e0 , enjoy, c2 , v1 )
(inflected) auxiliary verbs: be, do and have are dis-
Using the previously described procedure, the -ASP⇤
carded (translated as the identity -ASP⇤ expression:
expression is converted to the following ASP program:
[v0 ] v0 .v0 ) and constants in the body of the -ASP⇤
expression which do not correspond to definite noun {ev(e0 , enjoy, c1 , X) nom(X, opera).
phrases are replaced with variables. The generated ev(e0 , enjoy, c2 , X) nom(X, opera).
predicates of -ASP⇤ expression form the body of an nom(c1 , jack). nom(c2 , jim). nom(f1 , opera).
ASP query rule: q body. Two additional rules of the
ev(e0 , enjoy, c1 , f1 ). ev(e0 , enjoy, c2 , f1 ).}
form ans(yes) q and ans(no) not q are included
to capture the yes and no answers respectively. If all The first two rules of the above program can be intu-
answer sets of the generated ASP program include the itively read as: Jack (Jim) enjoys everything that is an
same ground instance of the fact ans, then the corre- opera. The last two facts state that: there exists an
sponding value (namely yes or no) is returned as an opera that Jack and Jim enjoy and they allow us to an-
answer. Otherwise the answer UNKNOWN is returned. swer questions such as: What does Jack (Jim) enjoy?
In case of wh-questions requiring a one-word answer,
a query predicate is added, whose purpose is to map Exceptions and Default Persistence
the identifier to the actual word corresponding to the Natural language expressions are often associated with
answer. A rule, similar as to the case of polar ques- implicit information that does not follow directly from
tions, is also included, but this time with an additional their literal meaning and requires background knowl-
literal: ans(W ) nom(I, W ), body. In case the ans(·) edge to be interpreted correctly. To associate words in
predicate is not in any model of the program, UNKNOWN the text with their interpretations, a semantic predicate
answer is returned. is introduced for each predicate in the chosen signature.
For example, for the binary event predicate, the se-
-ASP⇤ to ASP Conversion mantic predicate is defined as: {sem ev(E, L, X, Y )
⇤
A -ASP representation, generated from a given text, ev(E, L, X, Y ), not ab ev(E, L, X, Y )}. Definitions of
may or may not contain bound variables. Hence, the semantic predicates specify an exception structure.
conversion of a -ASP⇤ into an ASP representations has Consider for instance the implicit negation introduced
to consider two cases. by the verb forget, like in the sentence: Jim forgot
In the first case, no bound variables are present. to take an umbrella. This implicit negation can be
Hence, the resultant -ASP⇤ expression consists exclu- captured by the following rule: {ab ev(E0 , L, X, Y )
sively of instantiated predicates - ones for which all sem ev(E1 , f orget, X, E0 ), ev(E0 , L, X, Y )}. When ap-
predicate arguments are constants. Therefore, each plied to the above example sentence, the rule has
predicate is converted directly to an ASP fact. The - the following grounding: {ab ev(e0 , take, c1 , n1 )
ASP⇤ expression derived for our running example falls sem ev(e1 , f orget, c1 , e0 ), ev(e0 , take, c1 , n1 )}, where c1
under this category, hence the following ASP program and n1 correspond to Jim and umbrella respectively.
Understanding and keeping track of persistence of
is generated: fluents over time plays an important role in text com-
{nom(c1 , jack). nom(n0 , car). mod(expensive, n0 ). prehension. In our approach we assume a linear time
structure in the narratives. Verbs occurring in the text
mod(saf e, n0 ). mod(new, n0 ). mod(really, e0 ). are associated with implicit time points which are rep-
ev(e0 , want, c1 , e1 ). ev(e1 , buy, c1 , n0 ).} resented in the generated ASP program by ground in-
stances of the predicate time(T, E). The argument T
In the second case, the list of bound variables in the is a positive number equal to the position of the verb,
resultant -ASP⇤ expression is non-empty, the expres- identified by E, in the text relative to the other verbs.
sion is converted to a set of normal rules and a set Persistence is captured using a set of rules motivated
of facts, which corresponds to universal and existential by Event Calculus (Kowalski and Sergot 1986), and for-
quantification of the given sentence. For each rule the malised as follows:
head is the predicate whose identifier is equal to one sem ev(E, L, X, Y ) f luent(T, L, X, Y ), time(T, E)
of the heads of the -ASP⇤ expression. The body of f luent(T, L, X, Y ) initiate(E, L, X, Y ), time(T, E)
each rule is composed incrementally by including every f luent(T1 , L, X, Y ) f luent(T2 , L, X, Y ),
predicate from the -ASP⇤ expression (di↵erent from
previous(T2 , T1 ), time(T1 , E),
the head predicate) which has a variable among its ar-
guments that is also an argument of either the head of not terminate(E, L, X, Y )
The truth value of the predicate f luent(T, L, X, Y ) to a theorem prover for recognising textual entailment
persists and can change over timepoints. It is (Bos and Markert 2005). The Boxer system uses -
parametrised by the timepoint T , lemma L of the corre- DRS (Discourse Representation Structure) formalism
sponding word, which is the name of the fluent, and ar- to derive semantic representation compositionally. The
guments of the word. For example, f luent(2, be, c1 , n2 ), first step of the translation algorithm is assignment of
where c1 and n2 are identifiers of Jim and kitchen -DRS expressions to the leaf nodes of the parse tree
means that Jim is in the kitchen at time 2 and he will generated for the sentence by the C&C parser. The
continue to be there until termination. Words that are lexicon is derived by manually specifying -DRS ex-
treated as fluents are specified by providing initiation pressions for the majority of the 409 CCG categories
and termination rules in the background knowledge. used by the C&C parser. Then, the combinatory rules,
expressed in terms of -DRS expressions are used to de-
Discussion rive the semantics for the internal nodes in a bottom-up
manner as dictated by the structure of the parse tree.
The dataset used for evaluating our approach consists The method for constructing semantic representations
of 22 sentences and short stories, 10 of which were hand- used by the system is a general-purpose one and can be
crafted, 5 were taken from (Baral and Dzifcak 2012), 5 applied to formalisms other than DRT. Finally, the -
from online news articles and 2 from STEP 2008 shared DRS is translated into first-order logic. Our approach
tasks dataset (Bos 2008a). Regarding the hand-crafted uses instead a di↵erent formalism, namely ASP rather
examples, correct representations were generated for 9 than first-order logic, which makes it arguably easier
out of 10. The remaining 12 examples consist of 18 sen- to perform inferences necessary in the task of question
tences and a correct predicate structure was generated answering. With regards to the translation algorithm,
for 14 of them and for the other 4 the main source of both our approach and the Boxer system generate the
errors was the CCG parser. Among the 14 sentences, lexicon based on a set of hand-crafted rules which rely
the representations were fully correct for 9 of them on the CCG category, part-of-speech tag, and lemma of
and for the other 5 some predicates were incorrectly the given word.
parametrised due to errors in coreference resolution, The -ASP calculus described in (Baral, Dzifcak, and
interpretation of noun phrases (distributive vs collec- Son 2008) is used to translate English sentences with
tive), semantics of prepositions and lack of support for normatives and exceptions into ASP. -ASP expres-
expletive sentences and di↵erent types of elliptical con- sions, similarly -DRS used by Boxer, extend the un-
structions. The results of the evaluation confirm that derlying formalism with application and abstraction as
our approach can correctly represent sentences with co- known from -calculus. Then, -ASP expressions are
ordination and non-local dependencies, use coreference used to build semantic representation of phrases and
information to resolve personal and possessive pronouns sentences compositionally. The -ASP expressions, as
and capture the semantics of di↵erent parts of speech. presented in (Baral, Dzifcak, and Son 2008), is con-
The question answering functionality of the system strained to a small subset of English consisting of nouns,
was evaluated on The (20) QA bAbI tasks (Weston et verbs and adjectives and does not support, among oth-
al. 2015) that we also used for learning common sense ers, adverbs, prepositions and conjunctions. In the sub-
knowledge using Inductive Logic Programming, which sequent work (Baral et al. 2011), a method for auto-
is however outside the scope of this paper. Our system matic generation of lexicon entries from training data
was evaluated on 10 tasks (tasks number: 1, 2, 5, 6, 8, specified as pairs (Si , Li ) where Si is the sentence and
9, 12, 15, 16, 18) which, among others, required correct Li the corresponding logical representation has been
representation of conjunction and generic sentences as proposed. Although the approach achieves favorable
well as temporal and default reasoning to be answered results on Geoquery database querying dataset and on
correctly. Using general (non task-specific) background a dataset of logical puzzles (Baral and Dzifcak 2012),
knowledge our system achieved 100.0% accuracy for 9 the generated logical representations are still domain-
tasks and 93.6% for the other task, which was task 16. specific and the proposed translation algorithm does
The lower accuracy on that task was due to its require- not handle binding and linguistic phenomena such as
ment for task specific background knowledge. coreference or non-local dependencies. In comparison,
our approach o↵ers a systematic treatment of adverbs,
Related Work coordination and non-local dependencies, which to the
The two approaches most related to out work are the best of our knowledge, (Baral, Dzifcak, and Son 2008)
Boxer system (Bos et al. 2004) and the -ASP calculus is not capable of. Di↵erent from -ASP, our approach
described in (Baral, Dzifcak, and Son 2008). The Boxer does not use a domain-specific logical representation,
system relies on C&C syntactic parser, which uses CCG bur rather a wide-coverage semantic parser, similarly
and Discourse Representation Theory (DRT) to gener- to the Boxer system.
ate first-order logic representations from texts written
in English. The system achieves more than 95% cov- Conclusion
erage of English newspaper texts (Bos 2008b) and the In summary, we have presented a novel approach for
generated logical representations are used as an input automatically generating ASP representation from text
and questions with single word answers, which makes with Boxer. In Proceedings of the 2008 Conference
use of the CCG’s transparent interface between syntax on Semantics in Text Processing, STEP ’08, 277–286.
and semantics of natural language. To support a wide- Stroudsburg, PA, USA: Association for Computational
coverage semantic parsing of text, we have generalised Linguistics.
the existing formalism of -ASP calculus into a general- Gelfond, M., and Lifschitz, V. 1988. The stable model
purpose -ASP⇤ calculus capable of handling additional semantics for logic programming. In Logic Program-
complex linguistic constructs. We have also shown how ming: Proceedings of the 5th International Conference,
additional common-sense background knowledge about 1070–1080. MIT Press.
persistence and exceptions can be represented and re-
Hockenmaier, J., and Steedman, M. 2005. CCGbank:
lated with the generated ASP representation of the text
User’s manual. Technical report, Department of Com-
in order to support the answers to questions that are
puter and Information Science, University of Pennsyl-
not directly expressed in text. We are currently explor-
vania.
ing the integration into our approach of current state-
of-the-art systems for learning ASP programs (Law, Hockenmaier, J., and Steedman, M. 2007. CCGbank: A
Russo, and Broda 2016) in order to automatically learn, corpus of CCG derivations and dependency structures
instead of hand-crafting, relevant common sense knowl- extracted from the Penn Treebank. Comput. Linguist.
edge from examples of question-answer pairs. Our pre- 33(3):355–396.
liminary results on this line of current work have been Kingsbury, P., and Palmer, M. 2002. From TreeBank
very promising. to PropBank. In Third International Conference on
Language Resources and Evaluation, LREC-02.
References Kowalski, R., and Sergot, M. 1986. A logic-based calcu-
Baral, C., and Dzifcak, J. 2012. Solving puzzles de- lus of events. New Generation Computing 4(1):67–95.
scribed in English by automated translation to answer Law, M.; Russo, A.; and Broda, K. 2014. Inductive
set programming and learning how to do that trans- learning of answer set programs. In European Workshop
lation. In Proceedings of the Thirteenth International on Logics in Artificial Intelligence, 311–325. Springer.
Conference on Principles of Knowledge Representation Law, M.; Russo, A.; and Broda, K. 2016. Iterative
and Reasoning, 573–577. AAAI Press. learning of answer set programs from context dependent
Baral, C.; Dzifcak, J.; Gonzalez, M. A.; and Zhou, J. examples. arXiv preprint arXiv:1608.01946.
2011. Using inverse lambda and generalization to trans- Lewis, M.; He, L.; and Zettlemoyer, L. 2015. Joint A*
late English to formal languages. In Proceedings of the CCG parsing and semantic role labelling. In Empirical
Ninth International Conference on Computational Se- Methods in Natural Language Processing.
mantics, IWCS ’11, 35–44. Stroudsburg, PA, USA: As- Lifschitz, V. 2008. What is Answer Set Programming?
sociation for Computational Linguistics. In Proceedings of the 23rd National Conference on Ar-
Baral, C.; Dzifcak, J.; and Son, T. C. 2008. Using An- tificial Intelligence - Volume 3, AAAI ’08, 1594–1597.
swer Set Programming and lambda calculus to charac- AAAI Press.
terize natural language sentences with normatives and Manning, C. D.; Surdeanu, M.; Bauer, J.; Finkel, J.;
exceptions. In Proceedings of the 23rd National Confer- Bethard, S. J.; and McClosky, D. 2014. The Stanford
ence on Artificial Intelligence, volume 2 of AAAI ’08, CoreNLP natural language processing toolkit. In As-
818–823. AAAI Press. sociation for Computational Linguistics (ACL) System
Bos, J., and Markert, K. 2005. Recognising textual Demonstrations, 55–60.
entailment with logical inference. In Proceedings of the Steedman, M. 2000. The Syntactic Process. Cambridge,
Conference on Human Language Technology and Em- MA, USA: MIT Press.
pirical Methods in Natural Language Processing, HLT
’05, 628–635. Stroudsburg, PA, USA: Association for Weston, J.; Bordes, A.; Chopra, S.; Rush, A. M.; van
Computational Linguistics. Merriënboer, B.; Joulin, A.; and Mikolov, T. 2015.
Towards AI-complete question answering: A set of pre-
Bos, J.; Clark, S.; Steedman, M.; Curran, J. R.; and requisite toy tasks. arXiv preprint arXiv:1502.05698.
Hockenmaier, J. 2004. Wide-coverage semantic repre-
sentations from a CCG parser. In Proceedings of the
20th International Conference on Computational Lin-
guistics, COLING ’04. Stroudsburg, PA, USA: Associ-
ation for Computational Linguistics.
Bos, J. 2008a. Introduction to the shared task on
comparing semantic representations. In Proceedings of
the 2008 Conference on Semantics in Text Processing,
STEP ’08, 257–261. Stroudsburg, PA, USA: Associa-
tion for Computational Linguistics.
Bos, J. 2008b. Wide-coverage semantic analysis