Natural Language Question Answering System And Method Based On Deep Semantics

• US 20110320187A1
• Filed: 06/28/2011
• Published: 12/29/2011
• Est. Priority Date: 06/28/2010
• Status: Active Grant

• Current Assignee: Skyscanner Ltd. (Trip.com Group Ltd.)
• Original Assignee: Experienceon Ventures SL (Trip.com Group Ltd.)
• Inventors: Motik, Boris, Niñerola, Sergio Antonio Berná, Garcia, Pablo Castellanos, González-Cadenas, Carlos
• Granted Patent: US 11,068,657 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

In a computer system, systems and methods for automatically answering natural language questions using deep semantics are provided. Methods include receiving a natural language question, mapping it into one or more deductive database queries that captures one or more intents behind the question, computing one or more result sets of the question using one or more deductive database queries and a deductive database and providing one or more result sets. Systems include natural language question compilers and deductive databases. The natural language question compiler is configured to receive a natural language question and map it into one or more deductive database queries that capture one or more intents behind the question. The deductive database is configured to receive the mapped one or more deductive database queries, compute one or more result sets of the question using the one or more deductive database queries, and provide one or more result sets.

Claims

1. A method comprising:

receiving one or more ontologies and a fact database as inputs;

loading and storing at least one ABox fact from the input ontologies in the fact database;

deriving additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database; and

storing the derived ABox facts in the fact database.

2. The method of claim 1 wherein the ontologies are represented in a DOL language.

5. The method of claim 1 wherein deriving additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database is performed by means of a complete reasoning method.

6. The method of claim 5 wherein deriving additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database by means of a complete reasoning method further comprises:

converting the TBox axioms of the input ontologies into a rule set;

rewriting the rules with function symbols with equivalent rules without function symbols;

converting temporal rules into non-temporal rules;

replacing the individuals referred to by name with individuals referred to by identifier;

rewriting the regular rules with the precomputed join rules;

removing from the rule set those rules containing predicates identified as nonmaterializable, and unfolding the references to such predicates in the remaining rules;

computing the strongly connected components of the rule set;

generating an evaluation plan for evaluating all the strongly connected components;

transforming the evaluation plan into an SQL script; and

deriving the new ABox facts by executing the SQL script in the fact database.

7. The method of claim 1 wherein deriving additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database is performed by means of an incremental reasoning method.

3. A method comprising:

receiving a deductive database query, one or more ontologies and a fact database as inputs;

translating the deductive database query into an SQL query using the one or more ontologies;

computing the results of the SQL query over the fact database; and

providing the results of the deductive database query.

4. The method of claim 3 wherein the deductive database queries are represented in a DQL language.

8. The method of claim 3 wherein translating the deductive database query into an SQL query using the one or more ontologies is performed by means of a basic query translation method.

9. The method of claim 3 wherein translating the deductive database query into an SQL query using the one or more ontologies is performed by means of an optimized translation method using EXISTS statements.

10. The method of claim 3 wherein translating the deductive database query into an SQL query using the one or more ontologies is performed by means of an optimized translation method using nested subqueries.

11. A system comprising:

a fact database configured to;

load, store and retrieve ABox facts;

a reasoner configured to;

receive one or more ontologies and a fact database as inputs;

derive additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database; and

store the derived ABox facts in the fact database;

a query answering engine configured to;

receive a deductive database query, one or more ontologies and a fact database as inputs;

translate the deductive database query into an SQL query using the one or more ontologies;

compute the results of the SQL query over the fact database; and

provide the results of the deductive database query.

12. The system of claim 11 wherein the ontologies are represented in the DOL language.

13. The system of claim 11 wherein the deductive database queries are represented in a DQL language.

14. The system of claim 11 wherein the reasoner is configured to derive additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database by means of a complete reasoning method.

15. The system of claim 14 wherein the reasoner is configured to:

convert the TBox axioms of the input ontologies into a rule set;

rewrite the rules with function symbols with equivalent rules without function symbols;

convert the temporal rules into non-temporal rules;

replace the individuals referred to by name with individuals referred to by identifier;

rewrite the regular rules with precomputed join rules;

remove from the rule set those rules containing predicates identified as nonmaterializable, and unfolding the references to such predicates in the remaining rules;

compute the strongly connected components of the rule set;

generate an evaluation plan for evaluating all the strongly connected components;

transform the evaluation plan into an SQL script; and

derive the new ABox facts by executing the SQL script in the fact database.

16. The system of claim 11 wherein the reasoner is configured to derive additional ABox facts using at least one TBox axiom contained in the input ontologies and the ABox facts contained in the fact database by means of an incremental reasoning method.

17. The system of claim 11 wherein the query answering engine is configured to translate the deductive database query into an SQL query using the one or more ontologies by means of a basic query translation method.

18. The system of claim 11 wherein the query answering engine is configured to translate the deductive database query into an SQL query using the one or more ontologies by means of an optimized translation method using EXISTS statements.

19. The system of claim 11 wherein the query answering engine is configured to translate the deductive database query into an SQL query using the one or more ontologies by means of an optimized translation method using nested subqueries.

20. A method comprising:

receiving a natural language question as an input;

mapping the natural language question provided as an input into one or more deductive database queries that capture one or more intents behind the natural language question;

computing one or more result sets of the natural language question using one or more deductive database queries and a deductive database; and

providing one or more result sets of the natural language question.

21. The method of claim 20 wherein mapping the natural language question provided as an input into one or more deductive database queries that capture one or more intents behind the natural language question further comprises:

performing a semantic parsing of the natural language question by mapping the natural language question into one or more semantic hypergraphs that capture one or more meanings behind the natural language question; and

performing an intent detection of one or more semantic hypergraphs by transforming one or more semantic hypergraphs into one or more deductive database queries that capture the one or more intents behind the natural language question.

22. The method of claim 21 wherein the one or more semantic hypergraphs are represented in a DOL language.

23. The method of claim 21 wherein the one or more deductive database queries are represented in a DQL language.

24. The method of claim 21 wherein performing a semantic parsing of the natural language question by mapping the natural language question into one or more semantic hypergraphs that capture one or more meanings behind the natural language question further comprises:

tokenizing the natural language question by breaking down the natural language question into a list of tokens;

detecting named entities;

assigning syntactic and/or semantic metadata to the tokens;

creating temporary hypergraphs that will be used to hold all the intermediate transformations that are required to generate the semantic hypergraphs;

performing syntactic joining by combining tokens using syntactic information associated to them;

performing semantic joining by combining tokens using semantic information associated to them;

performing semantic scope resolution by applying the right semantic scope for operations, whose syntactic and semantic scope usually diverge; and

extracting the semantic hypergraphs from the temporary hypergraphs.

25. The method of claim 21 wherein performing an intent detection of one or more semantic hypergraphs by transforming one or more semantic hypergraphs into one or more deductive database queries that capture the one or more intents behind the natural language question further comprises:

replacing zero or more individuals of the semantic hypergraph with variables;

detecting the answer variables;

building a deductive database query using the semantic hypergraph and the answer variables; and

augmenting the deductive database query.

26. A system comprising:

a natural language question compiler configured to;

receive a natural language question as an input; and

map the natural language question provided as an input into one or more deductive database queries that capture one or more intents behind the natural language question;

a deductive database configured to;

receive the mapped one or more deductive database queries as input;

compute one or more result sets of the natural language question using the one or more deductive database queries; and

provide one or more result sets of the natural language question.

27. The system of claim 26 wherein the natural language question compiler comprises:

a semantic parser configured to;

receive a natural language question as an input; and

perform a semantic parsing of the natural language question by mapping the natural language question into one or more semantic hypergraphs that capture one or more meanings behind the natural language question;

an intent detector configured to;

receive one or more semantic hypergraphs as input; and

perform an intent detection of the one or more semantic hypergraphs by transforming the one or more semantic hypergraphs into one or more deductive database queries that capture the one or more intents behind the natural language question.

28. The system of claim 27 wherein the one or more semantic hypergraphs are represented in a DOL language.

29. The system of claim 27 wherein the one or more deductive database queries are represented in a DQL language.

30. The system of claim 27 wherein the semantic parser is configured to:

tokenize the natural language question by breaking down the natural language question into a list of tokens;

detect named entities;

assign syntactic and/or semantic metadata to the tokens;

create temporary hypergraphs that will be used to hold all the intermediate transformations that are required to generate the semantic hypergraphs;

perform syntactic joining by combining tokens using syntactic information associated to them;

perform semantic joining by combining tokens using semantic information associated to them;

perform semantic scope resolution by applying the right semantic scope for operations, whose syntactic and semantic scope usually diverge; and

extract the semantic hypergraphs from the temporary hypergraphs.

31. The system of claim 27 wherein the intent detector is further configured to:

replace zero or more individuals of the semantic hypergraph with variables;

detect the answer variables;

build a deductive database query using the semantic hypergraph and the answer variables; and

augment the deductive database query.