2 Background

We next describe some of the key technologies we employ. Our effort is based on answer set programming (ASP) technology (Gelfond and Kahl Reference Gelfond and Kahl2014), specifically, its goal-directed implementation in the s(ASP) system. ASP supports nonmonotonic reasoning through negation as failure that is crucial for modeling commonsense reasoning (via defaults, exceptions and preferences) (Gelfond and Kahl Reference Gelfond and Kahl2014). We assume that the reader is familiar with the basic notations of natural language processing (NLP). Expositions of NLP can be found elsewhere (Jurafsky Reference Jurafsky2000).

Answer Set Programming (ASP): An answer set program is a collection of rules of the form -

\begin{equation*}l_0 \leftarrow l_1, \;...\,, \;l_m, \; not \, l_{m+1}, \;...\,, \; not\, l_n. \end{equation*}

where each l_i is a literal (Gelfond and Kahl Reference Gelfond and Kahl2014). In an ASP rule, the left-hand side is called the head and the right-hand side is the body. Constraints are ASP rules without a head, whereas facts are rules without a body. The variables start with an uppercase letter, while predicates and constants begin with a lowercase letter. We will follow this convention throughout the paper. The semantics of ASP is based on the stable model semantics of logic programming (Gelfond and Lifschitz Reference Gelfond and Lifschitz1988). ASP supports negation as failure (Gelfond and Kahl Reference Gelfond and Kahl2014) permitting it to elegantly model commonsense reasoning, default rules, exceptions, etc. which is responsible for CASPR’s sophistication.

s(ASP) system: s(ASP) (Marple et al. Reference Marple, Salazar and Gupta2017) is a query-driven, goal-directed implementation of ASP. A query-driven implementation is indispensable for automating commonsense reasoning, as traditional grounding and SAT-solver based implementations of ASP has limited scalability. There are three major advantages of using s(ASP): s(ASP) does not ground the program, which makes CASPR framework fast and scalable, it only explores the parts of the knowledge-base needed to answer a query, and it provides justification for an answer.

Stanford CoreNLP tools: Stanford CoreNLP (Manning et al. Reference Manning, Surdeanu, Bauer, Finkel, Bethard and McClosky2014) is a set of tools for natural language processing. CASPR uses the Parts-of-Speech (POS) tagger, Dependency Parser, and Named Entity Recognizer (NER) tool from this set (Jurafsky Reference Jurafsky2000). Based on the context, POS tagger generates the necessary parts of speech such as noun, verb, adjective, etc., for each sentence. It also identifies the question type for each question (e.g. what, where, how) and disambiguated words (e.g. block as a verb vs. block as a noun). The NER tool captures the entities present in the sentence such as location, time, etc. A dependency graph is eventually generated that shows the grammatical relations between words in the sentence. Dependency relations follow enhanced universal dependency annotation (Schuster and Manning Reference Schuster and Manning2016). Figure 1 shows an example of POS tagging and dependency graph of a question.

Fig 1. Example of POS tagging and dependency graph.

WordNet: WordNet is one of the most commonly used resources in English. It is a lexical database consisting of sense-relations between English words. WordNet consists of multiple databases, one each for nouns, verbs, adjectives and adverbs. WordNet also contains a set of near-synonyms called synsets. Each database contains a set of lemmas ^{Footnote 2} , each one annotated with a set of senses. A typical entry for the noun “lion” in WordNet yields the different senses shown in Figure 2.

Fig 2. Entry for the concept of lion in WordNet.

3 CASPR: System architecture

CASPR is composed of two main sub systems: the Knowledge Generation System and the Query Generation System. The architecture, as illustrated in Figure 3, consists of a common resource framework shared by both these systems consisting of NLP tools such as Stanford Core NLP Tools, WordNet API as well as modules for pre-processing input text.

Fig 3. System architecture.

The Knowledge Generation System is mainly responsible for extracting knowledge from a natural language text and representing it as an answer set program. For extracting the knowledge from text and to gain more information about the input text, this component uses Stanford NLP tools like the POS Tagger, Stanford Dependency Parser, and the Stanford NER Tagger. Apart from these resources it also taps into the information that is provided by WordNet (Miller Reference Miller1995) and extracts knowledge from it, converting it into an answer set program. WordNet provides significant amount of commonsense knowledge about nouns. Unlike nouns, for verbs, at present, there are very few digital resources available that effectively represent the information that verbs convey and that also capture relationships between them (e.g. if we drop an object, it will fall to the ground). Such commonsense knowledge for verbs, thus, has to be modeled manually as an answer set program, and added to the common resource framework.

The Query Generation System automatically translates the question to an ASP query that can be executed against the ASP-coded knowledge-base generated from the textual passage augmented with ASP-coded commonsense knowledge. Execution is performed using the s(ASP) system. The solution found represents an accurate answer to the question. The query obtained from the natural language question is a conjunction of multiple sub-goals. If the query fails, then some of the sub-goals are systematically removed and the query re-executed to find less accurate answers (details are in Section 6). These less accurate answers are reported too, along with the level of accuracy (likely, possible, guess).

4 CASPR: Knowledge generation

The Stanford Dependency Parser is used to parse the pre-processed text. A semantic graph is generated using the Stanford Typed Dependencies representation (De Marneffe and Manning Reference De Marneffe and Manning2008; De Marneffe et al. Reference De Marneffe, Dozat, Silveira, Haverinen, Ginter, Nivre and Manning2014).

Following is the Stanford Dependency (SD) representation:

nsubj(carried-2, NASA-1), root(ROOT-0, carried-2), compound:prt(carried-2, out-3),

det(program-6, the-4), compound(program-6, Apollo-5), dobj(carried-2, program-6)

These dependencies map straightforwardly onto a directed graph representation in which words in the sentence are nodes in the graph and grammatical relations are edge labels. In English, most event-mentions correspond to verbs and most verbs are triggers to events. Although this is true in most cases there are other word groups that can trigger events as well. The different verbs in the sentence thus define various events that take place in the sentence and how these events are connected to each other. Consider a more complex example.

Figure 4 shows how various words in the example passage are connected to each other in the sentence. The main verbs of the sentence are “feature” and “let” connected by a coordinating conjunction. The verbs in Figure 4 represent the head of events in the sentence and are marked using event IDs. The various color regions denote the rough boundaries of these event regions. The semantic graph along with the event regions are used to create ASP facts and rules.

Fig 4. Semantic graph representing event regions.

4.2 Commonsense knowledge generation

We make use of additional knowledge sources such as the WordNet to gain supplementary information (commonsense knowledge) about the concepts in the input passage. CASPR uses the Hypernym relation from WordNet to build its ontology, coded as an answer set program.

To generate ontology rules, we use standard knowledge patterns from answer set programming like the preference pattern and the default reasoning pattern (Gelfond and Kahl Reference Gelfond and Kahl2014; Chen et al. Reference Chen, Marple, Salazar, Gupta and Tamil2016). In general a concept is represented in our work using the following signature:

concept(concept_instance, instance_sense)

For example: lion(simba, noun_animal).

Hypernyms can be used to infer various properties of and functions about concepts. Hypernyms make use of the generalization principle to transfer properties from more general concepts to their specific concepts. There are three steps required to do so (i) Identify the concepts from the passage and generate a hypernym graph; words may be used in multiple senses (e.g. the word lion has four commonly used senses); example graph for word lion highlighting 4 different senses is shown in Figure 5. (ii) Aggregate the concepts into common base concepts. (iii) Generate hypernym rules. Figure 6 shows ASP rules generated by CASPR for one of the senses of the concept lion. Due to the space constraint, we have omitted a few details, however more illustrations can be found in the thesis (Pendharkar Reference Pendharkar2018a).

Fig 5. Concept graph of hypernym relation.

Fig 6. ASP Rules representing the animal branch of “lion”.

Adding Commonsense Knowledge Manually: Note that at the moment we are only using WordNet, however, other knowledge resources, such as YAGO (Mahdisoltani et al. Reference Mahdisoltani, Biega and Suchanek2015), VerbNet (Kipper et al. Reference Kipper, Korhonen, Ryant and Palmer2006), never-ending language learner (Mitchell et al. Reference Mitchell, Cohen, Hruschka, Talukdar, Betteridge, Carlson, Dalvi, Gardner, Kisiel, Krishnamurthy, Lao, Mazaitis, Mohamed, Nakashole, Platanios, Ritter, Samadi, Settles, Wang, Wijaya, Gupta, Chen, Saparov, Greaves and Welling2015), etc., can be incorporated as well to extract additional commonsense knowledge. Doing so is relatively straightforward, as it mostly involves syntactic transformation to ASP syntax. Note that, currently, commonsense knowledge about verbs is entered manually. An example of adding knowledge manually is the following:

The term Nikola

_Tesla is similar to Tesla:

_similar(tesla, nikola_tesla).

A team X can represent an organization Y, if X is possessed by Y:

event(E, represent, X, Y):- possess(Y, X), organization(Y), team(X),

not ab_event(E, represent, X, Y).

These handcrafted knowledge are represented using either ASP facts or as default rules with exceptions and also it uses generic predicate names. So, these manually entered commonsense knowledge added once can reside in the knowledge-base permanently and can be used in any other application without any change. This approach is very similar to humans, where we learn knowledge once, and may use it later in another context.

5 Word sense disambiguation

Word sense disambiguation (WSD) is the task of selecting the best sense out of a collection of senses applicable to a concept. When we query a concept from WordNet lexicon, we get a list of senses for a specific concept ordered from the most used to the least used. WSD is a very common problem in NLP applications and has many statistical solutions that have been developed. We develop a method using negation as failure, classical negation and preferences that models WSD correctly. Essentially, contextual knowledge is used to disambiguate the word sense, in a manner that humans use. We explain it next.

Representation of word senses: Word senses are represented using two different logic patterns in our work. Using both these patterns together, senses are selected for the various concepts in the text which activate their hypernym relations.

In a natural language, a concept (i.e. word) can have multiple senses and one of those senses must have been used in the sentence based on the textual context. The task is to identify that sense. The pattern discussed in this section tries to discover the correct sense for a concept using the characteristics of the sense. Its template can be given as follows:

c(X, $s_i$ ) :– c(X), characteristics( $s_i$ , X), not -c(X, $s_i$ ).

In the above template, we are trying to prove that “X is an instance of concept c with sense $s_i$ ”. Here every concept c has one or more senses denoted by $s_i$ . The above rule states that X is an instance of the concept c with the sense $s_i$ only if we can prove that X is some instance of concept c, X has all the characteristics required to be of sense $s_i$ , and we cannot prove that X is definitely not an instance of concept c with sense $s_i$ . Please note that the “characteristic” predicate becomes true for the instance X with sense $s_i$ iff it is supported by the knowledge represented from the passage (the context of the passage) in ASP form. Such rules are generated for every sense $s_i$ of the concept in the order of senses from the most used sense to the least used sense. The first term given by “c(X)” is responsible to short circuit and fail the rule if the instance X does not belong to the class c. The second term, “characteristics( $s_i$ , X)”, is the main predicate which tries to prove that X shows the characteristics of having sense $s_i$ . It is this predicate that can be added either manually or using other sources to prove the sense. The third term of the body is a strong exception against the head of the rule, that fails the rule if an exception is found against the application of the sense.

According to WordNet, the concept “tree” has three senses, S = {plant, diagram, person}, ordered according to their frequency of use. Thus, using the above-mentioned template for the sense the three rules generated for the tree concept can be given as follows

tree(X, plant) :- tree(X), characteristics(plant, X),

not -tree(X, plant).

tree(X, diagram) :- tree(X), characteristics(diagram, X),

not -tree(X, diagram).

tree(X, person) :- tree(X), characteristics(person, X),

not -tree(X, person).

Preference patterns for senses: We humans perform word sense disambiguation in our day-to-day life by taking cues from the context. Over a period of time we learn which senses are more common than others and develop a preference order. Consider a concept c having three senses s $_1$ , s $_2$ and s $_3$ ordered according to the frequency of their use from the most used to the least used. We first assume the sense to be s $_1$ , unless we know that s $_1$ is not the sense from some other source. Then we move on to the next sense s $_2$ unless we know that both s $_1$ and s $_2$ cannot be applicable. Then finally we choose s $_3$ . This process of elimination of senses and choosing senses according to preferences can be modeled as the following ASP code template.

c(X, $s_p$ ) :- c(X), not -c(X, $s_p$ ),

-c(X, $s_1$ ), -c(X, $s_2$ ), …, -c(X, $s_{p-1}$ ),

not c(X, $s_{p+1}$ ), not c(X, $s_{p+2}$ ), …, not c(X, $s_n$ ).

The above skeleton is applied for all the senses of concept c in order of preference. The above template represents the rule generated for the $p^{th}$ sense of the concept c such that $1 < p < n$ , where n is the total number of senses of concept c. If p = 1 then the template omits the classical negation terms as follows:

c(X, $s_1$ ) :- c(X), not -c(X, $s_1$ ), not c(X, $s_2$ ),

not c(X, $s_3$ ), …, not c(X, $s_n$ ).

Similarly, if p = n, then the template omits the negation as failure terms, given as:

c(X, $s_n$ ) :- c(X), not -c(X, $s_n$ ), -c(X, $s_1$ ),

-c(X, $s_2$ ), … -c(X, $s_{n-1}$ ).

We can apply this pattern to the “tree” concept as an example. A tree can be a living object (plant), a diagram, or a person (Mr. Tree).

tree(X, plant) :- tree(X), not -tree(X, plant),

not tree(X, diagram), not tree(X, person).

tree(X, diagram) :- tree(X), not -tree(X, diagram),

-tree(X, plant), not tree(X, person).

tree(X, person) :- tree(X), not -tree(X, person),

-tree(X, plant), -tree(X, diagram).

This pattern is responsible for assigning at least one sense for every concept in the text. This preference pattern along with the property pattern mentioned previously helps disambiguate word sense just as humans do.

6 CASPR: Query generation from natural language question

Once knowledge has been generated from the text and auxiliary sources, our next task is to translate the question we want to answer into an ASP query.

Since a question is also a sentence, it is processed in the same way that any other sentence would be, as mentioned before in this paper. This means that a semantic graph is generated for every question, and event regions are created within the question assigning event ids to different parts of the question. To generate an ASP query from the semantic graph the following steps are applied: (i) Question understanding (ii) Generation of query predicates (iii) Applying base constraints (iv) Combining constraints. Currently, this module is only built to deal with simple interrogative sentences but can be extended to deal with more complex questions. In the following subsections, we have explained all the steps of ASP query generation process from natural language questions. For more details users are requested to refer to the thesis (chapter 7) (Pendharkar Reference Pendharkar2018a).

Question understanding: For analyzing questions, we obtain four kinds of information from the question, namely, the question word, the question type as mentioned in the previous section, the answer word or the focus of the question, and the answer type.

The question word is the Wh-word found in the question. In general, Wh-words can be found out by looking at the following POS Tags on the words: WDT, WP, WP$ and WRB. If none of the tags are found, then the questions may have a copula (Jurafsky Reference Jurafsky2000) as its question word or a modal as its question word. The question type contains a set of predefined question types that help in further processing. These include WHAT, WHERE, WHO, WHICH, WHEN, HOW_MANY, HOW_MUCH, HOW_LONG, HOW_FAR, and UNKNOWN. Once the main question word is found, we can use the word and its relations to determine the exact question type. The third type of information we try to extract is the answer word or the focus of the question. The answer word is the word in a question that tells us what kind of answer is expected from the question. Not all types of questions require an answer word, so in those cases this information is null. The fourth and the last information that we extract from the question is the answer type. The answer type depends on the question type. For most of the question types the required answer type is predefined. The answer types supported by the system are as follows SUBJECT, OBJECT, PLACE, PERSON, TIME, YEAR, DAY, MONTH, NUMBER (non-negative integers) and UNKNOWN. Table 1 shows expected answer types depending on question types. Please note that, in the table, “variable” answer type means it can be any type and not bounded by a domain of answers. With the help of this basic analysis, we start generating the predicates for query generation.

Table 1. Expected answer types for question types

Generating query predicates: Using the information that we gathered during Question Understanding, we start generating predicate facts for all the words in the question. We will use predicates mentioned previously in the paper as a reference. There are some changes that need to be made in a few predicates, for example, event predicate, property predicate, etc. Others (possess, mod, and named entity predicates) are generated as discussed earlier.

Event predicate: The event predicate in general can be given as follows-

event(event_id, trigger_verb, actor, participant)

In case of a sentence from a passage, we mark each verb with an event id and it helps to represent the knowledge around that verb by mapping them with the event id. Whereas, for a question, the event id is unknown, so we put a variable in place of the event id. The trigger verb is in the question that triggers the predicate generation. The actor acts like the subject of the verb and the participant are the object or the modifier. The participants can be obtained from the direct object (dobj) relations of the verb. There are various ways in which we can obtain the actor or the subject in any event.

1. event(E1, own, X1, O1), _similar(walt_disney, O1).

2. event(E1, own, _, O1), _property(E1, own, _by, X1), _similar(walt_disney, O1).

3. event(E1, own, _, _), _relation(X1, E1, _clause), _similar(walt_disney, O1).

Here, X1 variable binds the output and O1 variable is used internally to prove the sub-goals.

Property predicate: Property predicates are generated from verbs and nouns that are modified by nominal phrases in the sentence. Here, like the event predicate, we are unaware of the event_id and hence it will be set as a variable. The modified_entity is the noun or the verb that triggered the predicate generation. The preposition here can either be obtained from the case relation or can be left blank (_). The modifier is the head of the nominal modifier that can be used to constraint the query. If the modifier is the answer word, then we replace the word with the answer tag ( $X_k$ ).

Similar predicate: The similar predicate models the concept of similarity between entities in which one entity is so like the other one that they can replace each other. The similar predicate thus models one of the principles of commonsense reasoning where we as humans make use of the similarity relationship while reasoning (referring to Albert Einstein as just Einstein). Some rules for the similar predicate are as follows:

1. 1. Abbreviations of concepts are similar to each other for example, NYPD and New York Police Dept. _similar(X, Y) :- _abbreviation(X, Y). _similar(X, Y) :- _abbreviation(Y, X).

2. 2. Instances of concepts are similar to each other for example, Mercedes is similar to a car _similar(X, Y) :- _is(X, Y).

3. 3. Similarity follows transitivity for example, New York, NY, New York City and NYC are all interchangeable concepts that similar to each other. _similar(X, Y) :- _similar(X, Z), _similar(Z, Y).

Generating base constraints: Base constraints are generated at the end after all the constraints from the question have been generated. The term constraint here refers to constraints that arise due to the type of the answer, for example, if the expected answer is a person, then the variable holding the answer is restricted (constrained) to one of the persons mentioned in the passage. Constraints, thus, are sub-goals whose conjunction produces an answer to the question. Each sub-goal can be thought of as putting a constraint on the acceptable answers. For the following cases we generate the base constraints as follows.

TIME $\rightarrow$ time( $X_k$ )

DAY $\rightarrow$ day( $T_k$ , $X_k$ ), time( $T_k$ )

MONTH $\rightarrow$ month( $T_k$ , $X_k$ ), time( $T_k$ )

YEAR $\rightarrow$ year( $T_k$ , $X_k$ ), time( $T_k$ )

PLACE $\rightarrow$ location( $X_k$ ) or location( $X_k$ , noun_location)

PERSON $\rightarrow$ person( $X_k$ ) or person( $X_k$ , noun_person)

In case the answer type is UNKNOWN, we may expect the answer to be a specific concept represented by the answer word. In such cases the base constraint comes from the answer word itself.

UNKNOWN $\rightarrow$ concept( $X_k$ )

for example, company( $X_k$ ) or city( $X_k$ )

Combining constraints: After generation of the predicates from the question and the base constraints from answer type we combine all the constraints to create the final query. This can be best explained with an example.

?- event(E2, bear, S2, O2), _similar(nikola_tesla, S2),

property(E2, bear, on, X2), time(X2).

?- event(E2, bear, _, O2), _property(E2, bear, _by, S2),

_similar(nikola_tesla, S2), property(E2, bear, on, X2), time(X2).

?- event(E2, bear, _, _), _relation(S2, E2, _clause),

similar(nikola_tesla, S2), property(E2, bear, on, X2), time(X2).

?- _start_date(S2, X2), _similar(nikola_tesla, S2), time(X2).

In this sentence, we have the special predicates

_start

_date applying the constraints of time spans on the entity “Nikola Tesla”.

Query confidence classes: Ideally, we would want to be able to answer all questions with most number of constraints applied on the query so that we have a strong justification for the answer, but this is not always the case. In natural language the same questions can be posed in multiple different ways using synonymous concepts. This makes it more difficult to answer questions. Thus, it is better to make any question answering system robust enough, so that it fails gracefully. Once such attempt has been made in the query generation module by introducing the concept of confidence classes on the generated queries and by relaxing constraints on the queries to make the query more flexible. The queries that were generated in the previous section represent the most constrained queries. If an answer is found to one of those queries, then the system has the most confidence in the answer. In the absence of an answer the system starts removing constraints on the query (i.e. starts dropping sub-goals from the query) and relaxing the constraints on the query with the aim of obtaining some answer. The queries are designed in such a way that it always produces an answer along with its confidence class. Currently, queries have been divided into 4 confidence classes that range from most confident Class I to the least confident Class IV:

Certain (Class I): These kinds of queries have all the constraints included in the natural language question. The query may contain fact predicates, subordinate constraints, answer predicates and base constraints. This class has the highest confidence level. If an answer is produced, it is a correct answer.

Likely (Class II): These kinds of queries are executed when a certain answer is not produced. They do not contain any fact predicates. Fact predicates are all the predicates in the queries that do not contain any variables. Such predicates come from the question or the named entity tagger and act as constraints.

Possible (Class III): These kind of queries are executed when a likely answer is not produced. They only contain the answer predicates and base constraints. This means that the fact predicates and any subordinate constraints that do not contain the answer tag ( $X_k$ ) are removed.

Guess (Class IV): These kind of queries are executed when a possible answer is not produced. They only contain the base constraints (rest of the sub-goals are dropped). Answers from these queries are not very reliable as they can be thought of as guesses. This class has the lowest confidence.

Confidence class-based queries generated for the question “In what borough of New York City is ABC headquartered?” are shown below:

Certain (Class I) Queries:

?- _property(E2, borough, of, new_york_city), _property(E2, headquarter, _by, S2),

_property(E2, headquarter, in, X2), _similar(abc, S2), borough(X2, _),

event(E2, headquarter, _, O2), organization(abc).

?- _property(E2, borough, of, new_york_city), _property(E2, headquarter, in, X2),

_relation(S2, E2, _clause), _similar(abc, S2),

event(E2, headquarter, _, _), organization(abc), borough(X2, _).

?- _property(E2, borough, of, new_york_city), _property(E2, headquarter, in, X2),

_similar(abc, S2), event(E2, headquarter, S2, O2),

organization(abc), borough(X2, _).

Likely (Class II) Queries:

?- _property(E2, borough, of, new_york_city), _property(E2, headquarter, _by, S2),

_property(E2, headquarter, in, X2), _similar(abc, S2),

event(E2, headquarter, _, O2), borough(X2, _).

?- _property(E2, borough, of, new_york_city), _property(E2, headquarter, in, X2),

_relation(S2, E2, _clause), _similar(abc, S2),

event(E2, headquarter, _, _), borough(X2, _).

?- _property(E2, borough, of, new_york_city), _property(E2, headquarter, in, X2),

_similar(abc, S2), event(E2, headquarter, S2, O2), borough(X2, _).

Possible (Class III) Queries:

?- _property(E2, headquarter, in, X2), borough(X2, _).

Guess (Class IV) Queries:

?- borough(X2, _).

These four class of queries will produce four different answers, from 100% correct answer to a guess. Class I query response will be “Manhattan,” since ABC Corp is located in the burrough of Manhattan. That’s the correct (and most specific) answer. For Class II query, the constraint “organization/1” is dropped, and so if there is another entity (not an organization) that is called ABC, then the burrough where its headquartered will be produced as the answer. For Class III query, most constraints are dropped and a burrough containing any headquarter of any entity will be named, while for Class IV query, any arbitrary burrough located anywhere will be named. We are attempting to emulate a human who tries to give a possible answer, which could be a wild guess, if he/she does not possess adequate information.

To make any question answering system robust, so that it fails gracefully, we introduce the concept of confidence classes on the generated queries by relaxing constraints on the queries to make their execution more flexible. In the absence of an answer, the CASPR system starts removing constraints (sub-goals) in the query and relaxing it with the hope of executing it successfully and obtaining some answer. Currently, queries have been divided into 4 confidence classes:

Certain: These queries have all the constraints generated by our question processing module. If an answer is produced, it is a correct answer.

Likely: If a certain answer is not produced, all sub-goals that do not have variables are dropped.

Possible: If likely answer is not produced, then only the answer predicates and base constraints are included in the query (rest of the subgoals are dropped).

Guess: If possible answer is not produced, only base constraints are included in the query (rest of the subgoals are dropped).

As an example, suppose we ask the question: “When was Tesla born?”, given a biographical passage about Tesla. If the query that is formulated succeeds, it will produce the certain answer (1856). However, if for some reason the query fails, in the worst case, we would just retrieve any year in the passage and guess it as an answer. It should be noted that with enough knowledge, we are always guaranteed to produce the correct answer.

Note also that there are many other ways of relaxing constraints in the query to obtain less precise answers. The above is just one reasonable scheme.

7 CASPR: Results

The SQuAD Dataset (Rajpurkar et al. Reference Rajpurkar, Zhang, Lopyrev and Liang2016) contains more than 100,000 reading comprehensions along with questions and answers for those reading passages. SQuAD dataset uses the top 500+ articles from the English Wikipedia. These articles are then divided into paragraphs. We used the Dev Set v1.1 of the SQuAD Dataset to obtain comprehension passages for building a prototype for the proposed approach. This dataset has around 48 different articles with each article having around 50 paragraphs each. Out of the 48 different articles in the SQuAD dev set, 20 articles were chosen from different domains to help build the CASPR system (these 20 passages and associated questions can be found in github). These 20 articles are chosen in such a way that a lot of different domains were covered. We can roughly categorize these articles into 5 different categories: People articles, Scientific articles, Project/Event articles, Region articles and Misc. articles. Diversity is important as we have used these articles to understand the relations and that helps to craft the generic predicate rules. Using the 20 different articles mentioned above, the ASP code was generated for one paragraph from each article. Then, ASP queries were generated for all the questions in the dataset for these paragraphs. The results show the percentage of questions for which the answer generated from the ASP solver was present in the list of answers specified for the question in the SQuAD dataset. The results are summarized in Table 2. Our results show that approximately 77.76% of the questions are correctly answered. This shows that most of the knowledge, if not all, has been captured successfully in the ASP program generated for the passage. The ASP queries generated for the questions are very similar to the original question and convey the same meaning.

Table 2. Results for question answering

Note that the two main reasons why a query may fail to produce an exact (certain) answer are: (i) the parser used by CASPR fails to parse the question; and, (ii) missing commonsense knowledge about concepts in the question. With the help of common framework, knowledge from the passage is converted into an answer set program and the ASP query is generated from the natural language question. Commonsense knowledge bridges the gap between these two (the ASP query and the clauses from passage and question respectively). In the process of automatic commonsense knowledge generation, if appropriate knowledge is not generated for a concept present in the question, then CASPR will not be able to answer the question properly.

Note that our system has shown excellent execution performance on the 171 questions on 20 passages tried thus far: 80% of the questions were answered in 2 to 3 ms, while the rest were answered in a few seconds.

8 Contributions

The main contribution of this paper is an effective and efficient method for converting textual data into knowledge represented as an answer set program that can be processed on our query-driven s(ASP) ASP system. This includes developing a neo-davidsonian logic inspired generic calculus that helps represent knowledge, and using knowledge sources such as WordNet to acquire commonsense knowledge about terms found in the text to create a custom ontology for the problem. This automatic custom ontology generation process makes the CASPR system scalable. Yet another novelty is in showing how word sense disambiguation can be elegantly modeled using ASP. Our system is based on “truly understanding” the text just as humans do.

The paper also proposes a framework for converting natural language questions into ASP queries. These queries can be run on the query-driven s(ASP) system to compute answers. The query generation framework is made robust through broadening of queries by dropping constraints, thus increasing the possibility that the question will indeed be answered (even though in the worst case the answer may just be a guess). This approach to handling question answering is yet another novelty of the proposed system.

9 Related works

With respective to related work, Cyc (Wikipedia contributors 2018) is one of the oldest AI project that attempts to model commonsense reasoning. In Cyc, knowledge is presented in the form of a vast collection of ontologies that consist of implicit knowledge and rules about the world that represents commonsense knowledge. The ontology of Cyc as of 2017 contains around 1,500,000 terms. This includes around 500,000 collections, 50,000+ predicates and around a million well known entities. Cyc’s language CycL made it efficient to represent commonsense knowledge in the project and determined how this knowledge is represented in the project. Cyc uses a community of agents consisting of multiple reasoning agents that rely on more than 1000 heuristic modules to solve inference problems. Cyc, however, does not work with natural language, though recently some efforts have been started. A potential problem with Cyc is knowing which agent to apply, and which heuristic to use. For a commonsense reasoning system to be successful, it has to be modeled in a very simple way. Otherwise, we may possess the individual pieces of knowledge to answer a given question, but may not be able to compose these pieces together to arrive at an answer. For this reason, CASPR represents knowledge using very few generic predicates and uses simple ASP-based reasoning patterns to compute answers. Our initial experiments suggest that our approach is effective.

The application of ASP to solve NLP tasks is not new. Vo-Baral have developed the NL2KR tool that allows natural language text to be translated to an answer set program. Similarly, the work by costantini shows how ASP code can be generated automatically from natural language using lambda calculus. Action language based approaches are also popular in translating natural language to ASP (Olson and Lierler Reference Olson and Lierler2019; Zhang et al. Reference Zhang, Benton and Inclezan2020) etc. Several other researchers have worked on applying ASP for NLP tasks and their efforts are reported in the first workshop on NLP and Automated Reasoning (Baral and SchÜller Reference Baral and SchÜller2013). Our approach has elements common with these efforts, however, our work is based on the query-driven s(ASP) predicate ASP engine, and thus is scalable and not constrained by limitations of grounding based implementations of ASP. The query-driven s(ASP) system is crucial to our success as, like the current work, our previous works in this direction show promising results in the domain of visual question answering (Basu et al. Reference Basu, Varanasi, Shakerin and Gupta2020) and natural language question answering (Basu et al. Reference Basu, Varanasi, Shakerin and Gupta2020; Basu et al. Reference Basu, Varanasi, Shakerin, Arias and Gupta2021).

There are many approaches to question answering based on machine learning (cf. SQuAD website (Rajpurkar et al. Reference Rajpurkar, Zhang, Lopyrev and Liang2016)). However, they are not based on actually understanding the text and so can only answer questions related to data they are trained on. CASPR, in contrast, understands the knowledge contained in the text and has shown promising results for a subset of the SQuAD dataset. It should be noted that machine learning based approaches are based on statistical techniques and pattern matching, and do not represent the knowledge inherent in the text in any form. There is nothing that corresponds to understanding of the text, in contrast to our approach where this understanding is represented as knowledge modeled in ASP. For this reason, we do not elaborate too much here on machine learning based approaches to question answering. Also, there are some machine comprehension efforts based on semantic lexicon (Clark et al. Reference Clark, Dalvi and Tandon2018) that work really well on procedural texts, however they may not work well on non-procedural, descriptive text. In addition, they do not perform nonmonotonic reasoning. In contrast, CASPR can handle both non-procedural texts and perform nonmonotonic reasoning.

A critical component of CASPR’s success is the s(ASP) query-driven, predicate ASP system that leads to three major advantages for CASPR: (i) only parts of the knowledge-base relevant to answering the question are explored during execution; (ii) justification for answers can be extracted from the justification tree produced by s(ASP); and, (iii) the question answering system is scalable, as no grounding of the program needs to be done as s(ASP) can execute predicates directly under the stable model semantics.