Providing an explanation of a missing fact estimate

Patent metadata

Field	Value
Publication number	US-10318540-B1
Application number	US-201615393769-A
Country	US
Kind code	B1
Filing date	Dec 29, 2016
Priority date	Dec 30, 2013
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

Systems and methods are disclosed for providing an explanation of an estimate for information missing from a data graph. An example method may include receiving a query that requests information for a first entity and receiving an estimate for the information, the estimate being based on a plurality of features of a joint distribution model. The method may include determining respective contribution scores for the plurality of features, selecting a quantity of the features with highest contribution scores, generating, using the selected quantity of features, an explanation for the estimate; and providing the explanation and the estimate as part of a search result for the query.

First claim

What is claimed is:

1. A method comprising:
determining, using at least one processor, that information for an entity is absent from a data graph;
determining, using the at least one processor, an estimate for the information based on a plurality of features from a joint distribution model related to the information;
selecting a subset of the plurality of features, wherein selecting the subset comprises: determining a contribution value for each of the plurality of features, clustering the plurality of features based on common factors, aggregating at least one of the plurality of features, calculating a new contribution value for the at least one aggregated feature, and determining which of the plurality of features has a highest contribution value;
receiving, using the at least one processor, a query that requests the information for the entity;
generating an explanation based on the selected subset of features; and
providing the explanation and the estimate as part of a search result for the query.

2. The method of claim 1 , wherein selecting the subset further includes:
selecting the feature with the highest contribution value when the highest contribution value meets a threshold; and
selecting a quantity of features with highest contribution values when the combination of the contribution values meets the threshold.

3. The method of claim 2 , wherein determining the contribution value for a particular feature includes:
determining a first estimate for the information using the particular feature;
determining a second estimate for the information without using the particular feature; and
determining a difference between the first estimate and the second estimate.

4. The method of claim 1 , wherein the contribution value for a particular feature is related to a statistical descriptor associated with the particular feature.

5. The method of claim 1 , wherein the subset is a first subset and selecting the subset includes:
determining that a second subset of the plurality of features are related;
aggregating the contribution values for the features in the second subset; and
selecting the second subset as the first subset, so that the explanation and estimate reflect the aggregation.

6. The method of claim 1 , further comprising: storing members of the subset and the estimate as nodes in the data graph, the estimate linked to the entity and the members linked to the estimate.

7. The method of claim 1 , wherein the query is received prior to determining that the information is absent, and the determining of the estimate is performed in response to receiving the query.

8. The method of claim 1 , further comprising:
analyzing search records to determine that the information has previously been requested for other entities; and
determining whether the information is absent for the entity in response to determining that the information has previously been requested.

9. The method of claim 1 , further comprising adding the estimate to the data graph so that the estimate is linked to the entity via a relationship indicating that the estimate is not verified.

10. The method of claim 9 , further comprising, for each feature in the subset of the plurality of features, adding the feature in the data graph, and linking the feature to the estimate.

11. A computer program product tangibly embodied in a non-transitory storage medium, the computer program product including instructions that when executed cause a processor to perform operations including:
determining, using at least one processor, that information for an entity is absent from a data graph;
determining, using the at least one processor, an estimate for the information based on a plurality of features from a joint distribution model related to the information;
selecting a subset of the plurality of features, wherein selecting the subset comprises: determining a contribution value for each of the plurality of features, clustering the plurality of features based on common factors, aggregating at least one of the plurality of features, calculating a new contribution value for the at least one aggregated feature, and determining which of the plurality of features has a highest contribution value;
receiving, using the at least one processor, a query that requests the information for the entity;
generating an explanation based on the selected subset of features; and
providing the explanation and the estimate as part of a search result for the query.

12. The computer program product of claim 11 , wherein selecting the subset further includes:
selecting the feature with the highest contribution value when the highest contribution value meets a threshold; and
selecting a quantity of features with highest contribution values when the combination of the contribution values meets the threshold.

13. The computer program product of claim 12 , wherein determining the contribution value for a particular feature includes:
determining a first estimate for the information using the particular feature;
determining a second estimate for the information without using the particular feature; and
determining a difference between the first estimate and the second estimate.

14. The computer program product of claim 11 , wherein the contribution value for a particular feature is related to a statistical descriptor associated with the particular feature.

15. The computer program product of claim 11 , wherein the subset is a first subset and selecting the subset includes:
determining that a second subset of the plurality of features are related;
aggregating the contribution values for the features in the second subset; and
selecting the second subset as the first subset, so that the explanation and estimate reflect the aggregation.

16. The computer program product of claim 11 , the operations further comprising: storing members of the subset and the estimate as nodes in the data graph, the estimate linked to the entity and the members linked to the estimate.

17. The computer program product of claim 11 , wherein the query is received prior to determining that the information is absent, and the determining of the estimate is performed in response to receiving the query.

18. The computer program product of claim 11 , the operations further comprising:
analyzing search records to determine that the information has previously been requested for other entities; and
determining whether the information is absent for the entity in response to determining that the information has previously been requested.

19. The computer program product of claim 11 , the operations further comprising adding the estimate to the data graph so that the estimate is linked to the entity via a relationship indicating that the estimate is not verified.

20. The computer program product of claim 19 , the operations further comprising, for each feature in the subset of the plurality of features, adding the feature in the data graph, and linking the feature to the estimate.

Assignees

• Google Inc
• Google Llc

Inventors

• Chechik Gal
• Leviathan Yaniv
• Manor Ran El
• Tzur Yoav
• Segalis Eyal
• Farkash Efrat
• Matias Yossi

Classifications

• G06F16/2462

  Approximate or statistical queries · CPC title

• G06F16/248 Primary

  Presentation of query results · CPC title

• G06F16/245 Primary

  Query processing · CPC title