Querying a data graph using natural language queries

• US 10,810,193 B1
• Filed: 03/13/2013
• Issued: 10/20/2020
• Est. Priority Date: 03/13/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Subramanya, Amarnag, Pereira, Fernando, Lao, Ni, Blitzer, John, Gupta, Rahul
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Khoshnoodi, Fariborz
• Application Number:
  US13/801,598
• Time in Patent Office: 2,778 Days
• Field of Search: 707781, 707798
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Implementations include systems and methods for querying a data graph. An example method includes receiving a machine learning module trained to produce a model with multiple features for a query, each feature representing a path in a data graph. The method also includes receiving a search query that includes a first search term, mapping the search query to the query, and mapping the first search term to a first entity in the data graph. The method may also include identifying a second entity in the data graph using the first entity and at least one of the multiple weighted features, and providing information relating to the second entity in a response to the search query. Some implementations may also include training the machine learning module by, for example, generating positive and negative training examples from an answer to a query.

Claims

1. A computer-implemented method, the method comprising:

receiving, using at least one processor, a machine learning module trained to produce a model with multiple weighted features for a particular query, each weighted feature representing a path in a data graph and the weight of the feature being a probability of predicting a correct answer using the path;

receiving a search query that includes a first search term;

mapping the search query to the particular query;

mapping the first search term to a first entity in the data graph;

identifying, using the at least one processor, a second entity in the data graph using the first entity and at least one of the multiple weighted features; and

providing, using the at least one processor, information relating to the second entity in a response to the search query.

2. The method of claim 1, the method further comprising:

training the machine learning module to produce the model with multiple weighted features for the particular query.

3. The method of claim 2, wherein training the machine learning module includes:

generating noisy query answers; and

generating positive and negative training examples from the noisy query answers.

4. The method of claim 3, wherein generating the noisy query answers includes:

obtaining search results from a search engine for a document corpus, each result having a confidence score and wherein generating training examples includes;

selecting a predetermined number of highest scored documents as positive training examples; and

selecting a predetermined number of documents with a score below a threshold as negative training examples.

5. The method of claim 4, wherein obtaining search results includes reading search results from search records for past queries.

6. The method of claim 3, wherein generating positive and negative training examples includes:

performing entity matching on the noisy query answers; and

selecting entities that occur most often as positive training examples.

7. The method of claim 1 further comprising:

determining a confidence score for the second entity based on the weight of the at least one of the multiple weighted features.

8. The method of claim 7, wherein identifying the second entity in the data graph further includes:

selecting the second entity based on the confidence score.

9. The method of claim 8, wherein determining the confidence score for the second entity includes:

determining that two or more features connect to the second entity; and

using a combination of the weights of the two or more features as the confidence score for the second entity.

10. The method of claim 1, wherein the search query is a natural language query.

19. The method of claim 1, wherein mapping the search query to the particular query includes matching the search query to a query template for the particular query.

20. The method of claim 1, wherein mapping the search query to the particular query includes determining that the search query includes a word associated with the particular query.

21. The method of claim 1, wherein mapping the first search term to the first entity in the data graph includes:

determining that the search term maps to a plurality of entities, one of the plurality of entities being the first entity; and

selecting the first entity using entity resolution.

11. A computer-implemented method comprising:

training, using at least one processor, a machine learning module to map a query to multiple weighted features, each of the features representing one path in a data graph generating a possible query answer and being associated with a weight, the data graph having entities and edges and the weight being a probability of predicting a correct answer, the training occurring prior to receiving a user request matching the query;

receiving a user request matching the query;

determining, using the at least one processor, a first entity from the user request for the query, the first entity existing in the data graph;

providing the first entity and the query to the machine learning module;

receiving a subset of the multiple weighted features from the machine learning module;

identifying, using the at least one processor, a second entity in the data graph using the first entity and at least one of the subset of the multiple weighted features; and

generating a response to the user request that includes information relating to the second entity obtained using the subset of the multiple weighted features.

12. The method of claim 11, wherein training the machine learning module includes:

selecting positive examples and negative examples from the data graph for the query;

providing the positive examples, the negative examples, and the data graph to the machine learning module for training;

receiving the multiple weighted features from the machine learning module, each feature representing a walk in the data graph; and

storing at least some of the multiple weighted features in a model associated with the query.

13. The method of claim 12, wherein a path length for the walk is limited to a predetermined length, the path length being the number of edges traversed in the path for a particular feature.

14. The method of claim 12, wherein the positive examples and the negative examples are generated from search records for a document-based search engine.

15. The method of claim 12, wherein the multiple weighted features exclude features occurring less than a predetermined number of times in the data graph.

16. The method of claim 11, wherein generating the response to the user request includes:

determining a second entity in the data graph with a highest weight; and

including information from the second entity in the response.

17. The method of claim 16, wherein the weight of the second entity is the sum of the weight of each feature associated with the second entity.

18. The method of claim 11, wherein the query represents a cluster of queries.

22. The method of claim 11, wherein the query is a query template and receiving a request for the query includes:

receiving a search query from a user; and

determining that the search query matches the query template.

23. The method of claim 11, wherein the query represents a phrase associated with the machine learning module and receiving a request for the query includes:

receiving a search query from a user; and

determining that the search query corresponds to the phrase.