Enhancing performance of structured lookups using set operations

• US 10,713,242 B2
• Filed: 06/19/2017
• Issued: 07/14/2020
• Est. Priority Date: 01/17/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boxwell, Stephen A., Filoti, Octavian F., Holzenberger, Nils R., Kumar, Ashok T., Leano, Rafael A., Parsley, Cheyenne E.
• Primary Examiner(s): Peach, Polina G
• Application Number:
  US15/627,181
• Publication Number:
  US 20180204136A1
• Time in Patent Office: 1,121 Days
• Field of Search: None
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/248 Presentation of query results
• 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/30 Semantic analysis
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

A computer-implemented method configured to train a system to be able to provide answers to questions that do not have a direct relationship established in a database.

Claims

1. A computer-implemented method for providing answers to questions that do not have a direct relationship established in a database, the computer-implemented method comprising:

receiving a training question and a training answer set to the training question;

determining a training question structure of the training question;

determining a training subject in the training question;

determining a plurality of paths in a database that links the training subject to a plurality of answer subsets, wherein an answer subset comprises at least one answer in the training answer set to the training question;

performing a relation scoring analysis on the plurality of answer subsets to determine a set operation and a combination of the answer subsets that yield a highest accuracy score when the set operation is applied to the combination of the answer subsets, wherein the relationship scoring analysis comprises determining a first combination of the answer subsets that yield a first highest accuracy score when a union set operation is applied, determining a second combination of the answer subsets that yield a second highest accuracy score when an intersection set operation is applied, comparing the first highest accuracy score to the second highest accuracy score, setting the first combination of the answer subsets and the union set operation as the set operation and the combination of the answer subsets that yield the highest accuracy score when first highest accuracy score is greater than the second highest accuracy score, and setting the second combination of the answer subsets and the intersection set operation as the set operation and the combination of the answer subsets that yield the highest accuracy score when second highest accuracy score is greater than the first highest accuracy score; and

storing a subset of the plurality of paths corresponding to the combination of the answer subsets that yield the highest accuracy score, the set operation performed on the combination of the answer subsets that yield the highest accuracy score, and the training question structure of the training question for use in providing answers to questions.

2. The computer-implemented method of claim 1, further comprising:

receiving a non-training question;

determining a subject in the non-training question;

determining a question structure of the non-training question;

determining whether there is a direct relationship established in the database for answering the non-training question;

determining an answer set associated with the direct relationship corresponding to the subject of the non-training question in response to determining that the direct relationship is established in the database for answering the non-training question; and

returning the answer set as an answer to the non-training question.

3. The computer-implemented method of claim 2, further comprising:

determining whether the question structure of the non-training question matches the training question structure of the training question in response to determining that there is no direct relationship established in the database for answering the non-training question;

retrieving, from the database, the combination of the answer subsets corresponding to the subject in the non-training question by applying the subset of the plurality of paths corresponding to the combination of the answer subsets having the highest accuracy score to the subject of the non-training question in response to determining that the question structure of the non-training question matches the training question structure of the training question;

applying the set operation on the combination of the answer subsets to generate a modified answer subset in response to the combination of the answer subsets being retrieved; and

returning the modified answer subset as the answer to the non-training question.

4. The computer-implemented method of claim 1, wherein the training question structure comprises a predicate that describes a relationship between the training subject and the training answer set.

5. The computer-implemented method of claim 4, wherein determining that the question structure of the non-training question matches the training question structure of the training question comprises determining that the predicate in the question structure of the non-training question is the same as or equivalent to the predicate in the training question structure of the training question.

6. The computer-implemented method of claim 1, wherein the relation scoring analysis comprises ranking the plurality of answer subsets based on a precision and a recall of the answer subsets in comparison to the answer set to the training question.

7. The computer-implemented method of claim 1, wherein the relation scoring analysis comprises:

determining whether a single answer subset from the plurality of answer subsets has a precision equal to one and a recall equal to one in comparison to the answer set to the training question; and

returning the single answer subset as the answer subset and terminating the relation scoring analysis in response to determining that the single answer subset has the precision equal to one and the recall equal to one.

8. The computer-implemented method of claim 1, wherein the relation scoring analysis further comprises:

performing the union set operation on the combination of the answer subsets for the answer subsets that have a recall of less than one in comparison to the answer set to the training question.

9. The computer-implemented method of claim 1, wherein the relation scoring analysis further comprises:

performing the intersection set operation on the combination of the answer subsets for the answer subsets that have a precision of less than one in comparison to the answer set to the training question.

10. The computer-implemented method of claim 1, wherein the database comprises of resource development framework (RDF) triples and wherein the database is not modified.

11. The computer-implemented method of claim 1, wherein the combination of the answer subsets comprises two answer subsets.

12. The computer-implemented method of claim 1, wherein the accuracy score is based on a harmonic mean of a precision and a recall of the combination of the answer subsets in comparison to the training answer set to the training question.