Extracting structured knowledge from unstructured text

• US 9,110,882 B2
• Filed: 05/12/2011
• Issued: 08/18/2015
• Est. Priority Date: 05/14/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Overell, Simon, Tunstall-Pedoe, William
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): FINK, THOMAS ANDREW
• Application Number:
  US13/106,562
• Publication Number:
  US 20110307435A1
• Time in Patent Office: 1,559 Days
• US Class Current: 1/1
• 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 16/367 Ontology
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

Embodiments of the present invention relate to knowledge representation systems which include a knowledge base in which knowledge is represented in a structured, machine-readable format that encodes meaning. Techniques for extracting structured knowledge from unstructured text and for determining the reliability of such extracted knowledge are also described.

Claims

1. A computer-implemented method for extracting structured knowledge from unstructured text for use in a knowledge representation system, the knowledge representation system comprising a knowledge base that represents knowledge using a structured, machine-readable format, the structured, machine-readable format comprising fact triples, the method comprising:

identifying sentences in the unstructured text using one or more computing devices;

using the one or more computing devices, converting each of a subset of the sentences to one or more simplified assertion statements of the form;

subject noun phrase, verb phrase, object noun phrase;

converting each of a subset of the simplified assertion statements to a corresponding fact triple using the one or more computing devices, each fact triple being constructed from three knowledge base objects, the three knowledge base objects comprising two entity objects and a relationship object expressing a relationship between the two entity objects;

using the one or more computing devices, grouping the fact triples into a plurality of quarantine groups such that each of the fact triples is included in more than one of the quarantine groups, each quarantine group being defined by a corresponding one of a plurality of fact characteristics, a first one of the fact characteristics being that all of the fact triples in the corresponding quarantine group include a same one of the entity objects, a second one of the fact characteristics being that all of the fact triples in the corresponding quarantine group include a same one of the relationship objects;

determining a reliability for each quarantine group with reference to the knowledge base;

determining that more than one of the quarantine groups in which a first fact triple is included has at least a specified reliability; and

classifying the first fact triple as a reliable fact triple in response to determining that more than one of the quarantine groups in which the first fact triple is included has at least the specified reliability.

2. The method of claim 1 further comprising filtering first ones of the sentences unlikely to include an assertion that could be a basis for one of the simplified assertion statements.

3. The method of claim 2 wherein filtering the first sentences is done with reference to sentence features including one or more of sentence structure, words, punctuation, or sentence length.

4. The method of claim 1 wherein converting the subset of the sentences to simplified assertion statements comprises marking up first ones of the sentences to identify unique specific entities, the unique specific entities including one or more of dates, currencies, quantities, or named entities.

5. The method of claim 4 wherein the unique specific entities are already represented in the knowledge base.

6. The method of claim 4 wherein the unstructured text is included in a document, and the unique specific entities are identified within the document using Anaphora resolution.

7. The method of claim 1 wherein converting the subset of the sentences to simplified assertion statements comprises identifying parts of speech in each of the sentences in the subset.

8. The method of claim 7 wherein converting the subset of the sentences to simplified assertion statements comprises generating a parse tree for each of the sentences in the subset with reference to the corresponding parts of speech.

9. The method of claim 8 wherein the parse tree for each of the sentences in the subset of sentences is generated using one of a Deterministic Finite State Machine, a Non-Deterministic Finite State Machine, an LL-Parser, an LR-Parser, or a Probabilistic Parser.

10. The method of claim 8 wherein converting the subset of the sentences to simplified assertion statements further comprises identifying one or more sub-trees in each of the parse trees, and flattening and concatenating the sub-trees to generate the one or more simplified assertion statements.

11. The method of claim 1 wherein the knowledge representation system is a probabilistic system, the method further comprising quarantining fact triples for which the corresponding reliability is below a specified probability.

12. The method of claim 1 wherein the knowledge representation system is a non-probabilistic system, the method further comprising quarantining fact triples for which the corresponding reliability is a Boolean value indicating the fact triples are not reliable.

13. The method of claim 1:

wherein grouping the fact triples into a plurality of quarantine groups comprises adding each fact triple to a plurality of fact buckets, each fact bucket being defined by the corresponding fact characteristic shared by all fact triples added to that fact bucket; and

wherein determining the reliability for each quarantine group comprises;

for each fact bucket, determining whether each of a first number of fact triples added to that fact bucket is true or false with respect to the knowledge base; and

designating each fact bucket as one of reliable, unreliable, or unknown based on one or both of a first number of fact triples added to that fact bucket determined to be false, or a second number of fact triples added to that fact bucket determined to be true.

14. The method of claim 13 wherein the determining and designating steps are performed for each fact bucket each time N additional fact triples are added to that fact bucket.

15. The method of claim 14 wherein the determining step for each fact bucket is performed using the last M fact triples added to that fact bucket.

16. The method of claim 13 wherein the fact characteristic by which each of a subset of the fact buckets is defined comprises one of the following:

fact triples for which at least one of the two corresponding entity objects is the same;

fact triples for which the corresponding relationship object is the same;

fact triples that originate from the same source;

fact triples that originate from the same individual;

fact triples having common lexical elements;

or

fact triples translated from corresponding ones of the simplified assertion statements using a common translation template.

17. The method of claim 1 further comprising filtering fact triples where one or more of the following is true:

the fact triple is inconsistent with the knowledge base;

the fact contradicts the knowledge base;

the fact is of a controversial nature;

the two entity objects for the fact triple correspond to the same entity;

one of the two entity objects for the fact triple is not already included in the knowledge base;

an existential object is referred to in the sentence from which the fact triple was generated;

the fact triple has already been determined to be unreliable;

the fact triple refers to a derivatively-named object;

one or more system components used to parse the sentence from which the fact triple was generated has since been suppressed;

or

one or both of the two entity objects for the fact triple refers to a person solely by either a first name or a second name.

18. The method of claim 1 wherein the unstructured text includes a question and a corresponding answer, the method further comprising at least partially translating the question, extracting additional information from the answer using the at least partially translated question, and generating one of the fact triples using at least the partially translated question and the additional information extracted from the answer.

19. The method of claim 18 wherein the question is a yes-or-no question, wherein at least partially translating the question comprises translating the question to an intermediate fact triple, and wherein generating one of the fact triples comprises determining a polarity for the intermediate fact triple with reference to the additional information extracted from the answer.

20. The method of claim 18 wherein at least partially translating the question comprises translating the question to an intermediate fact triple in which one of the two corresponding entity objects comprises an unknown entity object, and wherein generating one of the fact triples comprises replacing the unknown entity object in the intermediate fact triple with a known entity object determined from the additional information extracted from the answer.

21. The method of claim 18 wherein the question requires a response not suited for representation in the knowledge base, the method further comprising disambiguating one or more entities identified in the partially translated question and referenced in the answer.

22. The method of claim 1 wherein for each of a subset of the fact triples the two entity objects of the fact triple respectively correspond to the subject noun phrase and the object noun phrase of the corresponding simplified assertion statement.

23. A system for extracting structured knowledge from unstructured text for use in a knowledge representation system, the knowledge representation system comprising a knowledge base that represents knowledge using a structured, machine-readable format, the structured, machine-readable format comprising fact triples, the system comprising one or more computing devices configured to:

identify sentences in the unstructured text;

convert each of a subset of the sentences to one or more simplified assertion statements of the form;

subject noun phrase, verb phrase, object noun phrase;

convert each of a subset of the simplified assertion statements to a corresponding fact triple, each fact triple being constructed from three knowledge base objects, the three knowledge base objects comprising two entity objects and a relationship object expressing a relationship between the two entity objects; and

group the fact triples into a plurality of quarantine groups such that each of the fact triples is included in more than one of the quarantine groups, each quarantine group being defined by a corresponding one of a plurality of fact characteristics, a first one of the fact characteristics being that all of the fact triples in the corresponding quarantine group include a same one of the entity objects, a second one of the fact characteristics being that all of the fact triples in the corresponding quarantine group include a same one of the relationship objects;

determine a reliability for each quarantine group with reference to the knowledge base;

determine that more than one of the quarantine groups in which a first fact triple is included has at least a specified reliability; and

classify the first fact triple as a reliable fact triple in response to determining that more than one of the quarantine groups in which the first fact triple is included has at least the specified reliability.

24. The system of claim 23 wherein the one or more computing devices are further configured to filter first ones of the sentences unlikely to include an assertion that could be a basis for one of the simplified assertion statements.

25. The system of claim 24 wherein the one or more computing devices are configured to filter the first sentences with reference to sentence features including one or more of sentence structure, words, punctuation, or sentence length.

26. The system of claim 23 wherein the one or more computing devices are configured to convert the subset of the sentences to simplified assertion statements by marking up first ones of the sentences to identify unique specific entities, the unique specific entities including one or more of dates, currencies, quantities, or named entities.

27. The system of claim 26 wherein the unique specific entities are already represented in the knowledge base.

28. The system of claim 26 wherein the unstructured text is included in a document, and the unique specific entities are identified within the document using Anaphora resolution.

29. The system of claim 23 wherein the one or more computing devices are configured to convert the subset of the sentences to simplified assertion statements by identifying parts of speech in each of the sentences in the subset.

30. The system of claim 29 wherein the one or more computing devices are configured to convert the subset of the sentences to simplified assertion statements by generating a parse tree for each of the sentences in the subset with reference to the corresponding parts of speech.

31. The system of claim 30 wherein the parse tree for each of the sentences in the subset of sentences is generated using one of a Deterministic Finite State Machine, a Non-Deterministic Finite State Machine, an LL-Parser, an LR-Parser, or a Probabilistic Parser.

32. The system of claim 30 wherein the one or more computing devices are further configured to convert the subset of the sentences to simplified assertion statements by identifying one or more sub-trees in each of the parse trees, and flattening and concatenating the sub-trees to generate the one or more simplified assertion statements.

33. The system of claim 23 wherein the knowledge representation system is a probabilistic system, and wherein the one or more computing devices are further configured to quarantine fact triples for which the corresponding reliability is below a specified probability.

34. The system of claim 23 wherein the knowledge representation system is a non-probabilistic system, and wherein the one or more computing devices are further configured to quarantine fact triples for which the corresponding reliability is a Boolean value indicating the fact triples are not reliable.

35. The system of claim 23 wherein the one or more computing devices are configured to:

group the fact triples into a plurality of quarantine groups by adding each fact triple to a plurality of fact buckets, each fact bucket being defined by the corresponding fact characteristic shared by all fact triples added to that fact bucket; and

wherein the one or more computing devices are configured to determine the reliability for each quarantine group by;

for each fact bucket, determining whether each of a first number of fact triples added to that fact bucket is true or false with respect to the knowledge base; and

designating each fact bucket as one of reliable, unreliable, or unknown based on one or both of a first number of fact triples added to that fact bucket determined to be false, or a second number of fact triples added to that fact bucket determined to be true.

36. The system of claim 35 wherein the one or more computing devices are configured to perform the determining and designating steps for each fact bucket each time N additional fact triples are added to that fact bucket.

37. The system of claim 36 wherein the one or more computing devices are configured to perform the determining step for each fact bucket using the last M fact triples added to that fact bucket.

38. The system of claim 35 wherein the fact characteristic by which each of a subset of the fact buckets is defined comprises one of the following:

fact triples for which at least one of the two corresponding entity objects is the same;

fact triples for which the corresponding relationship object is the same;

fact triples that originate from the same source;

fact triples that originate from the same individual;

fact triples having common lexical elements;

or

fact triples translated from corresponding ones of the simplified assertion statements using a common translation template.

39. The system of claim 23 wherein the one or more computing devices are further configured to filter fact triples where one or more of the following is true:

the fact triple is inconsistent with the knowledge base;

the fact contradicts the knowledge base;

the fact is of a controversial nature;

the two entity objects for the fact triple correspond to the same entity;

one of the two entity objects for the fact triple is not already included in the knowledge base;

an existential object is referred to in the sentence from which the fact triple was generated;

the fact triple has already been determined to be unreliable;

the fact triple refers to a derivatively-named object;

one or more system components used to parse the sentence from which the fact triple was generated has since been suppressed;

or

one or both of the two entity objects for the fact triple refers to a person solely by either a first name or a second name.

40. The system of claim 23 wherein the unstructured text includes a question and a corresponding answer, and wherein the one or more computing devices are further configured to at least partially translate the question, extract additional information from the answer using the at least partially translated question, and generate one of the fact triples using the at least partially translated question and the additional information extracted from the answer.

41. The system of claim 40 wherein the question is a yes-or-no question, and wherein the one or more computing devices are configured to at least partially translate the question by translating the question to an intermediate fact triple, and generate one of the fact triples by determining a polarity for the intermediate fact triple with reference to the additional information extracted from the answer.

42. The system of claim 40 wherein the one or more computing devices are configured to at least partially translate the question by translating the question to an intermediate fact triple in which one of the two corresponding entity objects comprises an unknown entity object, and generate one of the fact triples by replacing the unknown entity object in the intermediate fact triple with a known entity object determined from the additional information extracted from the answer.

43. The system of claim 40 wherein the question requires a response not suited for representation in the knowledge base, and wherein the one or more computing devices are further configured to disambiguate one or more entities identified in the partially translated question and referenced in the answer.

44. The system of claim 23 wherein for each of a subset of the fact triples the two entity objects of the fact triple respectively correspond to the subject noun phrase and the object noun phrase of the corresponding simplified assertion statement.

45. A computer program product for extracting structured knowledge from unstructured text for use in a knowledge representation system, the knowledge representation system comprising a knowledge base that represents knowledge using a structured, machine-readable format, the structured, machine-readable format comprising fact triples, the computer program product comprising one or more non-transient computer-readable media having computer program instructions stored therein and configured, when executed, to cause one or more computing devices to:

identify sentences in the unstructured text;

convert each of a subset of the sentences to one or more simplified assertion statements of the form;

subject noun phrase, verb phrase, object noun phrase;

convert each of a subset of the simplified assertion statements to a corresponding fact triple, each fact triple being constructed from three knowledge base objects, the three knowledge base objects comprising two entity objects and a relationship object expressing a relationship between the two entity objects; and

group the fact triples into a plurality of quarantine groups such that each of the fact triples is included in more than one of the quarantine groups, each quarantine group being defined by a corresponding one of a plurality of fact characteristics, a first one of the fact characteristics being that all of the fact triples in the corresponding quarantine group include a same one of the entity objects, a second one of the fact characteristics being that all of the fact triples in the corresponding quarantine group include a same one of the relationship objects;

determine a reliability for each quarantine group with reference to the knowledge base;

determine that more than one of the quarantine groups in which a first fact triple is included has at least a specified reliability; and

classify the first fact triple as a reliable fact triple in response to determining that more than one of the quarantine groups in which the first fact triple is included has at least the specified reliability.