We present an automated method for generating Answer Set Programs from narratives written in English and demonstrate how such a representation can be used to answer questions about text. The proposed approach relies on a transparent interface between the syntax and semantics of natural language provided by Combinatory Categorial Grammars to translate text into Answer Set Programs, hence creating a knowledge base that, together with background knowledge, can be queried.
Machine comprehension of text is a long-term open
problem in Artificial Intelligence and can be assessed
by a machine’s ability to answer questions about
passages of text. One of the main challenges is the
capacity to automatically process the text and capture the
natural language semantics. Various approaches have
been proposed in the literature, e.g.
This paper addresses these limitations by presenting
a fully automated method for generating Answer Set
Programs (ASP) from narratives written in English in
a general and principled manner, demonstrating how
such a representation can be used to answer questions
about text. Similarly to
In what follows, we outline the two main background formalisms used in our approach, namely answer set programming and combinatory categorical grammars. Answer Set Programming (ASP) is an expressive language for knowledge representation and reasoning, based on the stable model semantics (Gelfond and Lifschitz 1988) and rooted in the field of non-monotonic reasoning and logic programming (Lifschitz 2008). Within the scope of this paper, Answer Set Programs are restricted to normal logic programs. So, an ASP program is a set of normal rules of the form: r :
h h|ea{dz(}r) b1, b2, . . . , bm, not bm+1, . . . not bm+k | } bod{yz(r) where h, b1, b2, . . . , bm and not bm+1, . . . not bm+k are positive and negated atoms respectively with not denoting negation-as-failure. A fact is a rule whose body is empty (m = k = 0).
The Herbrand Base HB(P ) of an ASP program P is the set of all ground atoms constructed using predicate symbols, constants and function symbols in P . An Herbrand interpretation of P assigns a truth value to every atom in HB(P ) and is a model of P if for every ground rule r in P such that body(r) is satisfied head(r) is true. An Herbrand model M of P is minimal if no proper subset of M is a model of P . Given an ASP program P and a set M of ground atoms, the reduct P M of P is the logic program obtained from P by removing every: • rule that has a literal not p in its body, where p 2 M • negated literal in the bodies of the remaining rules M is an answer set of P if it coincides with the minimal Herbrand model of P M .
Combinatory Categorial Grammar (CCG) is an eciently parsable grammar that enables semantic analysis of natural language by providing a transparent interface between syntax and semantics. In CCG, words are assigned syntactic categories defining their syntactic behaviour. The set of CCG categories comprises of atomic categories and complex categories, recursively constructed from the atomic categories. Examples of atomic categories include: N (bare noun), N P (noun phrase) and S (sentence). Complex categories are of the forms X/Y and X\Y and define functors that, when applied to an argument of category Y , produce a result of category X. Directionality of the slash indicates whether the argument has to occur immediately to the left “/” or to the right “\” of the functor. For example, (S\N P )/N P is the category of a transitive verb buy in a sentence Jack bought a car.
CCG provides a surface-compositional interface between syntax and semantics in which there is one-toone mapping between the rules of syntactic and semantic composition (Hockenmaier and Steedman 2007). A set of syntactic combinatory rules specifies how adjacent constituents are combined. The most basic rules are forward (FA) and backward (BA) application: FA (>): X/Y : f BA (<): Y : a
Y : a =) X\Y : f =)
X : f (a) X : f (a) Composition combinatory rules allow two functor categories to combine and produce another functor. Example of a composition rule is forward composition (FC): FC (> B): X/Y : f Y /Z : g =) X/Z : x.f (g(x)) Type-raising combinatory rules allow an argument category Y to become a functor category X/(X\Y ) or X\(X/Y ). Forward type-raising rule (FT) is given by: FT (> T): Y : a =)
X/(X\Y ) : f.f (a) Composition together with type-raising rules are used to handle coordination and non-local dependencies introduced, for example, by relative clauses, which is illustrated by the following syntactic derivation for a relative clause: that Jack wanted, from a sentence: The car that Jack wanted was expensive.
that (N \N )/(S/N P )
J ack
N P
S/(S\N P ) N \N > T S\N P
wanted (S\N P )/N P > > B The predicate structure can be obtained directly from the syntactic derivation, provided that the semantics of lexical items, assigned by the lexicon, is known. Using a CCG syntactic derivation and first-order logic augmented with -calculus, for a sentence: Jack buys cars derivation of a first-order representation can be performed as follows:
N P : jack buys (S\N P )/N P : x.y.buy
(S\N P ) : y.buy (y, cars) < cars (y, x) N P : cars >
The signature of the ASP logical representation used in our approach, to express sentences written in English, consists of four classes of predicates: nominals, events, modifiers and prepositions. The name of each predicate is composed of an arity prefix, which indicates the number of arguments taken by the corresponding word, and a class sux, which takes one of the four aforementioned values. For example, a transitive verb buy is represented by the predicate: binaryEvent(e1, buy, c1, n0) where the first argument e1 serves as an identifier, buy is a lemma of the corresponding word and c1, n0 are arguments of the verb (agent and theme respectively). For the sake of conciseness, throughout this paper the arity prefixes are skipped and nominals, events, modifiers and prepositions are abbreviated in the predicate names as nom, ev, mod and prep respectively.
First, the input text is split into sentences and tokens. Subsequently, every word in the input text is tagged with the following set of annotations: • Lemma - inflection-free form of the word, used as an argument of the corresponding predicate • Part-of-speech (POS) tag - used by the lexicon to perform coarse division of words into classes • Named entity tag - enriches the predicate structure and allows to treat multi-word proper names as single entities, e.g. Ei↵el Tower as eiffel_tower rather than a nominal and a modifier • Coreference cluster - groups mentions of the same entity in the text. Cluster identifiers are used to form identifiers of nominal predicates corresponding to entity mentions, hence embedding coreference information in the predicate structure • Semantic role - derived for predicate (verb) arguments. PropBank sense IDs (Kingsbury and Palmer 2002) are used to order predicate arguments when generating predicate structure for verbs. For example, in a sentence: [Jack]ARG0 kicked [the ball]ARG1 the transitive verb kicked is translated as: ev(e1, kick, c0, n0), were c0 and n0 are identifiers of Jack and the ball and they are ordered according to their sense IDs (0 and 1 respectively)
After annotating the text, a CCG parse tree is derived for each sentence. The CCG parse tree is a binary tree whose leaf nodes correspond to lexical items and internal nodes to phrases, clauses or sentences. Leaves are identified by L as the first argument in the node’s descriptor, followed by the CCG category, POS tag and the word itself. Descriptors of the internal nodes begin with the identifier T, followed by the CCG category. Listing 1: CCG parse tree for a sentence A new and safe car that Jack wanted to buy was really expensive. 1 <T S[ dcl ]> 2 <T NP > 3 <L (NP/N) DT A> 4 <T N> 5 <T N> 6 <T (N/N)> 7 <L (N/N) JJ new > 8 <T ((N/N )\( N/N))> 9 <L CONJ CC and > 10 <L (N/N) JJ safe > 11 <L N NN car > 12 <T (N\N)> 13 <L ((N\N )/( S[ dcl ]/ NP )) WDT that > 14 <T (S[ dcl ]/ NP)> 15 <T (S[x ]/( S[x]\ NP ))> 16 <T NP > 17 <L N NNP Jack > 18 <T ((S[ dcl ]\ NP )/ NP)> 19 <L ((S\NP )/( S\NP )) RB really > 20 <T ((S[ dcl ]\ NP )/ NP)> 21 <L ((S[ dcl ]\ NP )/( S[to ]\ NP )) VBD wanted > 22 <T ((S[to ]\ NP )/ NP)> 23 <L ((S[to ]\ NP )/( S[b]\ NP )) TO to > 24 <L ((S[b]\ NP )/ NP) VB buy > 25 <T (S[ dcl ]\ NP)> 26 <L ((S[ dcl ]\ NP )/( S[ adj ]\ NP )) VBD was > 27 <L (S[ adj ]\ NP) JJ expensive >
Splitting text into sentences, tokenisation, lemmatisation, POS tagging, named entity recognition and coreference resolution is performed using Stanford CoreNLP (Manning et al. 2014). For syntactic parsing and semantic role labeling EasySRL (Lewis, He, and Zettlemoyer 2015) is used.
-ASP⇤ Calculus | k h{ezads } l|abst{rzactor}s | -ASP⇤ calculus serves as an intermediate representation between natural language and ASP. It follows the syntax of ASP but extends it with abstraction and application as known from -calculus, which enables compositional derivation of semantic representations of phrases and sentences from their constituents. -ASP⇤ expressions have the following general form: [h1, . . . hk] v 1 . . . v l . p1(a11, . . . ar11 ), . . . pm(a1m, . . . armm ), m pre{dzicates } } |
n appl{iczations where vi and wj are bound variables, arguments ayx are bound variables or constants and pt are predicate names included in the previously defined signature. Arities of predicates and applications are denoted by r1, . . . rm+n. Every predicate has a non-zero arity; however, applications can take no arguments. In case of applications, bound variables wj are referred to as function placeholders and are replaced by other -ASP⇤ expressions to which arguments ajm+j , . . . armm++jj are applied. Predicates and applications constitute the body of a -ASP⇤ expression. Every -ASP⇤ expression has a non-empty set H of bound variables or constants, called expression heads, which corresponds to the linguistic head of a phrase and can have more than one element to account for coordination. As an example, let us consider a -ASP⇤ expression for a transitive verb buy, given by: [e0]v 1.v 0.ev(e0, buy, v0, v1), (v1), (v0) Constant e0 is an identifier of the verb buy and also a head of the expression. Bound variables v0, v1 can be replaced, via the process of application (described further in this section), by constants and variables – when the bound variable occurs as a predicate or application argument, or by other -ASP⇤ expression – when the bound variable is a function placeholder in an application. The list of bound variables is followed by an event predicate and two applications with no arguments, which act as placeholders for the subject and object of the verb buy.
For -ASP⇤ expression e, preds(e) and apps(e) denote the sets of all predicates and applications in e respectively and abs(e) denotes the ordered list of bound variables. The set of heads of e is denoted by He. For p 2 preds(e), args(p) denotes the ordered list of arguments of p; the same notation is used for applications. Given two -ASP⇤ expressions e and f , the application g = e@f , where v denotes the first bound variable in e, is computed as follows: • for every a 2 apps(e) of the form w@(b1, b2, . . . bk), if v = w, compute recursively f 0 = f @(b1, b2, . . . bk), which is equivalent to (((f @b1)@b2) . . .)@bk, include preds(f 0) and apps(f 0) in g, and set f = f 0. If v 2 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 and v 62 args(a), unmodified a is included in g • for every p 2 preds(e), if v 2 args(p), |Hf | copies of p are included in g and v in the ith copy is replaced by the ith head of f . If v 62 p, p is included in g unmodified • bound variables of g are given by: abs(g) = (abs(e) {v}) + abs(f ), where ‘ ’ denotes removal of an element from a list and ‘+’ denotes list concatenation • if v 2 He, Hg = (He\{v}) [ Hf . Otherwise, Hg = He Constant c is represented by an expression e such that preds(e) = apps(e) = ; , abs(e) = [ ] and He = { } c . For variable v, expression e is modified so that abs(e) = [v].
In our approach, lexicon is an algorithm, which given an input word together with the relevant annotations (CCG category, POS tag, lemma, coreference cluster) derives the corresponding -ASP⇤ expression. -ASP⇤ expressions for content words and some prepositions consist of a single predicate and a di↵erent number of bound variables and applications. Each word is assigned to one of five sub-lexicons (nominal, event, modifier, preposition, wh-word) based on the POS tag and CCG category, which in turn determines the class of the corresponding predicate. The arity of a predicate, for all cases other than adverbs and some function words, is equal to the number of arguments of the CCG category of the corresponding word.
Co-indexation is performed for the relevant CCG
categories, such as the ones corresponding to raising and
control verbs or relative pronouns. Our approach
performs co-indexation for all categories listed in
Application primitive is also used to translate coordinate sentences whose constituents have the same CCG category. For example, in case of an adjective phrase new and safe the -ASP⇤ expression for coordinator and is: [v2, v1]v 2.v 1.v 0.(v2)@(v0), (v1)@(v0), which is inferred from the CCG categories of the conjuncts, namely (N/N ). In case of conjuncts that take more than one argument, such as transitive verbs buy and sell in the sentence: Jack buys and sells oil, the number of arguments of applications occurring in the -ASP⇤ expression is set accordingly: [v3, v2]v 3.v 2.v 1.v 0.(v3)@(v1, v0), (v2)@(v1, v0).
To ensure the same ordering of verb arguments for di↵erent grammatical constructions (for example passive vs. active voice) the arguments are ordered according to their PropBank semantic role labels.
Word
a new and safe car that Jack really wanted to buy was expensive -ASP Expression [v0]v 0.(v0)@(n0) [v0]v 0.mod(new, v0), (v0) [v2, v1]v 2.v 1.v 0.(v2)@(v0), (v1)@(v0) [v0]v 0.mod(saf e, v0), (v0) [v0]v 0.nom(v0, car), (v0) [v0]v 1.v 0.(v1)@(v0)
[c0]nom(c0, jack) [v0]v 0.mod(really, v0), (v0) [e0]v 1.v 0.ev(e0, want, v0, v1), (v1)@(v0)
[v0]v 0.v0 [e1]v 1.v 0.ev(e1, buy, v0, v1), (v1), (v0)
[v0]v 0.(v0) [expensive]v 0.mod(expensive, v0), (v0)
The -ASP⇤ expression for a given phrase or sentence is constructed bottom-up following the structure of the CCG parse tree. For each leaf node, a -ASP⇤ expression is assigned by the lexicon. For internal nodes, the relevant CCG combinatory rule is identified, based on the categories of the child nodes and used to derive the -ASP⇤ expression compositionally. All combinatory rules are realised using the -ASP⇤ expression: v 0.v 1.(v1)@(v0). In case of type-raising rules, child node’s -ASP⇤ expression is assigned to v0. For application and composition rules child nodes’ -ASP⇤ expressions are identified as function and argument based on their CCG categories, the former is assigned to v1 and the latter to v0.
In our running example, the -ASP⇤ expression for a noun phrase new and safe car is derived in three steps. Referring to Table 1, semantic representation for node in line 9 in Listing 1 is derived as follows: [v3]v 3.mod(saf e, v3), (v3)} For the node in line 7, we get the following expression: [v2]v 2.mod(new, v2), (v2)} ⌘ [v0]v 0.mod(saf e, v0), mod(new, v0), (v0) Finally, for the node in line 5, we get: {[v0]v 0.mod(saf e, v0), mod(new, v0), (v0)}@{ [v1]v 1.nom(v1, car), (v1)} ⌘ [v1]v 1.mod(saf e, v1), mod(new, v1), nom(v1, car), (v1)
Our approach for generating ASP representations from text is also applicable to polar questions and questions that require one word answer, such as questions starting with wh-words: what, where, who and which.
For polar questions, the same translation approach, described so far, is used to derive the corresponding ASP⇤ expressions with the only di↵erences being that (inflected) auxiliary verbs: be, do and have are discarded (translated as the identity -ASP⇤ expression: [v0]v 0.v0) and constants in the body of the -ASP⇤ expression which do not correspond to definite noun phrases are replaced with variables. The generated predicates of -ASP⇤ expression form the body of an ASP query rule: q body. Two additional rules of the form ans(yes) q and ans(no) not q are included to capture the yes and no answers respectively. If all answer sets of the generated ASP program include the same ground instance of the fact ans, then the corresponding value (namely yes or no) is returned as an answer. Otherwise the answer UNKNOWN is returned.
In case of wh-questions requiring a one-word answer, a query predicate is added, whose purpose is to map the identifier to the actual word corresponding to the answer. A rule, similar as to the case of polar questions, is also included, but this time with an additional literal: ans(W ) nom(I, W ), body. In case the ans(·) predicate is not in any model of the program, UNKNOWN answer is returned.
-ASP⇤ to ASP Conversion A -ASP⇤ representation, generated from a given text, may or may not contain bound variables. Hence, the conversion of a -ASP⇤ into an ASP representations has to consider two cases.
In the first case, no bound variables are present. Hence, the resultant -ASP⇤ expression consists exclusively of instantiated predicates - ones for which all predicate arguments are constants. Therefore, each predicate is converted directly to an ASP fact. The ASP⇤ expression derived for our running example falls under this category, hence the following ASP program is generated: {nom(c1, jack). nom(n0, car). mod(expensive, n0). mod(saf e, n0). mod(new, n0). mod(really, e0). ev(e0, want, c1, e1). ev(e1, buy, c1, n0).}
In the second case, the list of bound variables in the resultant -ASP⇤ expression is non-empty, the expression is converted to a set of normal rules and a set of facts, which corresponds to universal and existential quantification of the given sentence. For each rule the head is the predicate whose identifier is equal to one of the heads of the -ASP⇤ expression. The body of each rule is composed incrementally by including every predicate from the -ASP⇤ expression (di↵erent from the head predicate) which has a variable among its arguments that is also an argument of either the head of the given rule or some other predicate already included in the body. A set of facts, corresponding to the existential quantification, is also derived by applying Skolem constants to the -ASP⇤ expression. As an example, let us consider a sentence: Jack and Jim enjoy opera, with the -ASP⇤ expression given by: [e0]v 1.nom(c1, jack), nom(c2, jim), nom(v1, opera), ev(e0, enjoy, c1, v1), ev(e0, enjoy, c2, v1) Using the previously described procedure, the -ASP⇤ expression is converted to the following ASP program: {ev(e0, enjoy, c1, X) ev(e0, enjoy, c2, X) nom(X, opera).
nom(X, opera). nom(c1, jack). nom(c2, jim). nom(f1, opera). ev(e0, enjoy, c1, f1). ev(e0, enjoy, c2, f1).} The first two rules of the above program can be intuitively read as: Jack (Jim) enjoys everything that is an opera. The last two facts state that: there exists an opera that Jack and Jim enjoy and they allow us to answer questions such as: What does Jack (Jim) enjoy?
Natural language expressions are often associated with implicit information that does not follow directly from their literal meaning and requires background knowledge to be interpreted correctly. To associate words in the text with their interpretations, a semantic predicate is introduced for each predicate in the chosen signature. For example, for the binary event predicate, the semantic predicate is defined as: {sem ev(E, L, X, Y ) ev(E, L, X, Y ), not ab ev(E, L, X, Y )}. Definitions of semantic predicates specify an exception structure. Consider for instance the implicit negation introduced by the verb forget, like in the sentence: Jim forgot to take an umbrella. This implicit negation can be captured by the following rule: {ab ev(E0, L, X, Y ) sem ev(E1, f orget, X, E0), ev(E0, L, X, Y )}. When applied to the above example sentence, the rule has the following grounding: {ab ev(e0, take, c1, n1) sem ev(e1, f orget, c1, e0), ev(e0, take, c1, n1)}, where c1 and n1 correspond to Jim and umbrella respectively.
Understanding and keeping track of persistence of fluents over time plays an important role in text comprehension. In our approach we assume a linear time structure in the narratives. Verbs occurring in the text are associated with implicit time points which are represented in the generated ASP program by ground instances of the predicate time(T, E). The argument T is a positive number equal to the position of the verb, identified by E, in the text relative to the other verbs. Persistence is captured using a set of rules motivated by Event Calculus (Kowalski and Sergot 1986), and formalised as follows: sem ev(E, L, X, Y )
f luent(T, L, X, Y ), time(T, E) f luent(T, L, X, Y )
initiate(E, L, X, Y ), time(T, E) f luent(T1, L, X, Y ) f luent(T2, L, X, Y ), previous(T2, T1), time(T1, E), not terminate(E, L, X, Y ) The truth value of the predicate f luent(T, L, X, Y ) persists and can change over timepoints. It is parametrised by the timepoint T , lemma L of the corresponding word, which is the name of the fluent, and arguments of the word. For example, f luent(2, be, c1, n2), where c1 and n2 are identifiers of Jim and kitchen means that Jim is in the kitchen at time 2 and he will continue to be there until termination. Words that are treated as fluents are specified by providing initiation and termination rules in the background knowledge.
The dataset used for evaluating our approach consists
of 22 sentences and short stories, 10 of which were
handcrafted, 5 were taken from
The question answering functionality of the system was evaluated on The (20) QA bAbI tasks (Weston et al. 2015) that we also used for learning common sense knowledge using Inductive Logic Programming, which is however outside the scope of this paper. Our system was evaluated on 10 tasks (tasks number: 1, 2, 5, 6, 8, 9, 12, 15, 16, 18) which, among others, required correct representation of conjunction and generic sentences as well as temporal and default reasoning to be answered correctly. Using general (non task-specific) background knowledge our system achieved 100.0% accuracy for 9 tasks and 93.6% for the other task, which was task 16. The lower accuracy on that task was due to its requirement for task specific background knowledge.
The two approaches most related to out work are the
Boxer system
The -ASP calculus described in
In summary, we have presented a novel approach for automatically generating ASP representation from text and questions with single word answers, which makes use of the CCG’s transparent interface between syntax and semantics of natural language. To support a widecoverage semantic parsing of text, we have generalised the existing formalism of -ASP calculus into a generalpurpose -ASP⇤ calculus capable of handling additional complex linguistic constructs. We have also shown how additional common-sense background knowledge about persistence and exceptions can be represented and related with the generated ASP representation of the text in order to support the answers to questions that are not directly expressed in text. We are currently exploring the integration into our approach of current stateof-the-art systems for learning ASP programs (Law, Russo, and Broda 2016) in order to automatically learn, instead of hand-crafting, relevant common sense knowledge from examples of question-answer pairs. Our preliminary results on this line of current work have been very promising.
Bos, J.
2008b.
Wide-coverage semantic analysis with Boxer. In Proceedings of the 2008 Conference on Semantics in Text Processing, STEP ’08, 277–286. Stroudsburg, PA, USA: Association for Computational Linguistics.
Gelfond, M., and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proceedings of the 5th International Conference, 1070–1080. MIT Press.
Hockenmaier, J., and Steedman, M. 2005. CCGbank: User’s manual. Technical report, Department of Computer and Information Science, University of Pennsylvania.
Hockenmaier, J., and Steedman, M. 2007. CCGbank: A corpus of CCG derivations and dependency structures extracted from the Penn Treebank. Comput. Linguist. 33(3):355–396.
Kingsbury, P., and Palmer, M. 2002. From TreeBank to PropBank. In Third International Conference on Language Resources and Evaluation, LREC-02. Kowalski, R., and Sergot, M. 1986. A logic-based calculus of events. New Generation Computing 4(1):67–95. Law, M.; Russo, A.; and Broda, K. 2014. Inductive learning of answer set programs. In European Workshop on Logics in Artificial Intelligence, 311–325. Springer. Law, M.; Russo, A.; and Broda, K. 2016. Iterative learning of answer set programs from context dependent examples. arXiv preprint arXiv:1608.01946. Lewis, M.; He, L.; and Zettlemoyer, L. 2015. Joint A* CCG parsing and semantic role labelling. In Empirical Methods in Natural Language Processing.
Lifschitz, V. 2008. What is Answer Set Programming? In Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 3, AAAI ’08, 1594–1597. AAAI Press.
Manning, C. D.; Surdeanu, M.; Bauer, J.; Finkel, J.; Bethard, S. J.; and McClosky, D. 2014. The Stanford CoreNLP natural language processing toolkit. In Association for Computational Linguistics (ACL) System Demonstrations, 55–60.
Steedman, M. 2000. The Syntactic Process. Cambridge, MA, USA: MIT Press.
Weston, J.; Bordes, A.; Chopra, S.; Rush, A. M.; van Merri¨enboer, B.; Joulin, A.; and Mikolov, T. 2015. Towards AI-complete question answering: A set of prerequisite toy tasks. arXiv preprint arXiv:1502.05698.