AUTOMATIC FACT VALIDATION

• US 20100306166A1
• Filed: 06/01/2009
• Published: 12/02/2010
• Est. Priority Date: 06/01/2009
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Pantel, Patrick, Jain, Alpa
• Application Number:
  US12/476,055
• Publication Number:
  US 20100306166A1
• Time in Patent Office: Days
• US Class Current: 706/55
• CPC Class Codes: G06N 5/041 Abduction

Abstract

The disclosed embodiments fulfill searches and determine the validity of a large set of noisy facts and rank the set of facts according to a validity score. Embodiments construct a fact graph by linking together facts that share a common relation structure and entity or instance of an argument. Facts are re-ranked and validated using link analysis processes which propagate weight (validity/authority) through the fact graph. The resulting weights for each fact are potentially combined with other scores (such as from fact extraction algorithms) in order to come up with a final ranking of the facts.

Claims

1. A computer system for providing search results to users, the computer system configured to:

identify arguments common to relations in a collection of data;

generate a group of relations based on the identified common arguments;

construct a graph based representation of facts using the generated group of relations and identified common arguments;

perform link analysis with a random walk technique over the constructed graph based representation of facts, generating a score for each graph based representation of a fact;

rank the facts in each relation by the generated score; and

provide a response to a search query, the response incorporating at least one ranked fact.

2. The computer system of claim 1, wherein the computer system is further configured to generate or reference a baseline ranked list of facts from baseline extraction scores.

3. The computer system of claim 2, wherein the baseline extraction scores are generated by performing an extraction without a subsequent link analysis comprising a random graph walk analysis.

4. The computer system of claim 2, wherein the baseline extraction scores are generated by performing an extraction with a subsequent link analysis comprising a random graph walk analysis.

5. The computer system of claim 2, wherein in order to rank the facts in each relation the computer system is configured to combine a baseline extraction score with a score determined by the link analysis.

6. The computer system of claim 5, wherein the computer system is configured to average a rank suggested by the baseline ranked list and a rank determined by the link analysis.

7. The computer system of claim 5, wherein the computer system is configured to perform a weighted average of a rank suggested by the baseline ranked list and a rank determined by the link analysis.

8. The computer system of claim 1, wherein in being configured to perform a link analysis the computer system is further configured to represent each fact as a node.

9. The computer system of claim 1, wherein in being configured to perform a link analysis the computer system is further configured to create an edge between nodes that share the same value for an argument common to the relations of the nodes.

10. The computer system of claim 1, wherein in being configured to perform a link analysis the computer system is further configured to assign scores to each node with the random walk technique.

11. The computer system of claim 9, wherein in being configured to perform a link analysis the computer system is further configured to calculate a strength of an edge between two nodes by combining the extraction score of both nodes connected by the edge.

12. The computer system of claim 1, wherein in being configured to provide a response to a search query incorporating at least one ranked fact, the computer system is configured to present the at least one ranked fact together with search results.

13. The computer system of claim 1, wherein in being configured to provide a response to a search query incorporating at least one ranked fact, the computer system is configured to determine if each of a plurality of search results is consistent with the at least one ranked fact.

14. The computer system of claim 13, wherein the computer system is further configured to rank the plurality of search results based in part upon the determined consistency with the at least one ranked fact, and to present the search results according to the rank based in part upon the determined consistency.

15. The computer system of claim 1, wherein the computer system is further configured to provide an advertisement in response to a search query, the advertisement evaluated for consistency with at least one ranked fact.

16. A computer system for providing search results to users, the computer system comprising a network of search provider servers configured to:

identify arguments common to relations in a collection of data;

generate a group of relations based on the identified common arguments;

construct graph based representation of facts using the generated group of relations and identified common arguments;

represent each graph based representation of a fact as a node;

create an edge between nodes that share the same value for an argument common to the relations of the nodes connected by the edge;

assign scores to each node representing a fact with a random walk technique;

rank the nodes and associated represented facts in each relation by the score; and

formulate and provide a response to a search query, the response incorporating at least one ranked fact.

17. The computer system of claim 16, wherein in being configured to perform a link analysis the computer system is further configured to calculate a strength of an edge between two nodes by combining the score of the nodes connected by the edge.

18. A computer system for providing search results to users, the computer system configured to:

identify arguments common to relations in a collection of data;

generate a group of relations based on the identified common arguments;

construct a graph based representation of facts using the generated group of relations and identified common arguments;

perform link analysis with a random walk technique over the constructed graph based representation of facts, generating a score for each graph based representation of a fact;

rank the facts in each relation by the generated score; and

evaluate search results for consistency with the ranked facts.

19. The computer system for providing search results to users of claim 18, the computer system further configured provide the search results in an order based in part upon the consistency with the ranked facts.