Extracting facts from unstructured information

• US 10,354,188 B2
• Filed: 08/02/2016
• Issued: 07/16/2019
• Est. Priority Date: 08/02/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chalabi, Achraf Abdel Moneim Tawfik, Abdelbaki, Ahmed Mohamed Emad Morsi, Anderson, Brandon Robert, Abdel-Reheem, Eslam Kamal Abdel-Aal, Chen, Deqing, Gerguis, Michel Naim Naguib, Abdelaziz, Sayed Hassan Sayed, Marton, Yuval Yehezkel
• Primary Examiner(s): Gofman, Alex
• Application Number:
  US15/226,807
• Publication Number:
  US 20180039695A1
• Time in Patent Office: 1,078 Days
• Field of Search: None
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

A computer-implemented technique is described herein for extracting facts from unstructured text documents provided by one or more information sources. The technique uses a pipeline to perform this operation that involves, at least in part, providing a corpus of information items, extracting candidate facts from the information items, merging synonymous argument values associated with the candidate facts, organizing the candidate facts into relation clusters, and assessing the confidence level of the candidate facts within the relation clusters.

Claims

1. A system comprising:

a processing device; and

a computer-readable storage medium storing machine-readable instructions which, when executed by the processing device, cause the processing device to;

identify a plurality of sentences in an entity-tagged corpus that include at least two tagged entities, wherein the entity-tagged corpus is derived from a collection of information items that include unstructured information comprising the plurality of sentences;

parse the plurality of sentences to obtain parsed sentences representing parts of individual sentences as parse trees;

identify a plurality of relations in the parsed sentences, wherein respective relations identify a first argument value associated with a first named entity that corresponds to a subject expressed in a respective parsed sentence, a second argument value associated with a second named entity that corresponds to an object expressed in the respective parsed sentence, and a relation value which reflects a corresponding relationship expressed in the respective parsed sentence, the corresponding relationship being between the first named entity and the second named entity;

form one or more relation clusters based at least on the identified relations, respective relation clusters grouping together relations associated with a same first argument type expressed in the unstructured information, a same second argument type expressed in the unstructured information, and a same relation value expressed in the unstructured information;

generate confidence score information for the relations in said one or more relation clusters to provide scored relations, wherein the confidence score information reflects relative confidence that individual relations express factually true relationships between individual subjects and individual objects and the confidence score information is based at least on a parsing confidence reflecting confidence in the parsing of the plurality of sentences to obtain the parse trees;

output final extracted facts by selecting a subset of the scored relations based at least on the confidence score information; and

store the final extracted facts in a data store,

the final extracted facts in the data store being accessible via a user computing device coupled to a computer network.

2. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

extract the collection of information items from a body of network-accessible content, the collection of information items pertaining to a particular subject matter domain; and

derive the entity-tagged corpus from the collection of information items.

3. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

receive the collection of information items from one or more information feeds.

4. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

parse the plurality of sentences to obtain one or more candidate parse trees for each of the individual sentences; and

identify a selected parse tree from the candidate parse trees for each of the individual sentences.

5. The system of claim 4, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

identify a particular relation in a particular parsed sentence by using the selected parse tree for the particular parsed sentence to find a part of the particular parsed sentence that expresses the particular relation, a subject noun phrase head, and an object noun phrase head.

6. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

merge synonymous argument values within the parsed sentences to provide a set of argument-merged facts.

7. The system of claim 6, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

form a digest of unique argument values that appear in the parsed sentences, and relation information associated therewith, to provide a set of itemized entities;

provide pair score information for each pair of a particular first argument value and a particular second argument value within the itemized entities, to overall provide a set of scored entity pairs, each instance of pair score information reflecting an extent to which the particular first argument value is equivalent to the particular second argument value;

use the pair score information associated with the scored entity pairs to identify equivalent argument values, to provide a set of conflated relations; and

replace each group of argument values that have been assessed as being equivalent with a canonical argument value, to overall provide the argument-merged facts.

8. The system of claim 7, wherein the pair score information has plural score-related dimensions, including:

a first measure which reflects an extent to which relation information associated with the particular first argument value overlaps with relation information associated with the particular second argument value;

a second measure which reflects a text-based relation between the particular first argument value and the particular second argument value; and

third measure which reflects a given relation between a number of occurrences of the particular first argument value and a number of occurrences of the particular second argument value.

9. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

identify one or more partitions within the plurality of relations, each partition grouping together particular relations associated with a particular same first argument type and a particular same second argument type; and

identify one or more original clusters associated with each partition, each original cluster being associated with a particular relation value.

10. The system of claim 9, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

with respect to each partition;

identify at least two clusters within the partition, if any, that pertain to a same relation value; and

merge said at least two clusters into a single cluster.

11. The system of claim 10, wherein machine-readable instructions, when executed by the processing device, cause the processing device to:

identify said at least two clusters by forming an intersection of said at least two clusters, and determining whether the intersection satisfies a prescribed intersection threshold.

12. The system of claim 10, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

iteratively identify and merge the at least two clusters until no additional clusters can be merged, to overall provide said one or more relation clusters.

13. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

generate the confidence score information for each particular relation in said one or more relation clusters based at least on a first set of feature values and a second set of feature values,

the first set of feature values including subsystem-originating confidence score information that is provided by one or more prior subsystems in a pipeline of operations defined by the system, and

the second set of feature values provides a statistical measure of the occurrence of the particular relation and/or a part thereof within the collection of information items.

14. The system of claim 1, wherein the machine-readable instructions, when executed by the processing device, cause the processing device to:

use a domain classifier to select the collection of information items for a particular subject matter domain.

15. A method implemented by one or more computing devices, the method comprising:

receiving a collection of information items from one or more information sources via a computer network, the information items presenting unstructured information;

identifying a plurality of sentences in the unstructured information that mention at least two entities;

parsing the plurality of sentences in the unstructured information to obtain parsed sentences representing parts of individual sentences as parse trees;

identifying a plurality of relations in the parsed sentences, wherein respective relations identify a first argument value associated with a first named entity that corresponds to a subject expressed in a respective parsed sentence, a second argument value associated with a second named entity that corresponds to an object expressed in the respective parsed sentence, and a relation value which reflects a corresponding relationship between the first named entity and the second named entity expressed in the respective parsed sentence;

merging synonymous argument values within the plurality of relations to provide a set of argument- merged facts;

forming relation clusters based at least on the argument-merged facts, individual relation clusters grouping together relations associated with a same first argument type identified from the unstructured information, a same second argument type identified from the unstructured information, and a same relation value identified from the unstructured information;

generating confidence score information for the relations in said relation clusters to provide scored relations, the confidence score information reflecting at least a parsing confidence in the parsing of the plurality of sentences to obtain the parse trees;

outputting final extracted facts by selecting a subset of the scored relations based at least on the confidence score information; and

providing access to the final extracted facts to one or more knowledge-consuming computer-implemented applications.

16. The method of claim 15, wherein said generating confidence score information comprises:

determining a classification confidence reflecting relative confidence in which the information items are classified as being related to a specific target domain;

determining an entity recognition confidence reflecting relative confidence that the first named entity and the second named entity of each relation are named entities;

determining an entity merging confidence reflecting relative confidence in the merging of the synonymous argument values;

identifying a first number of occurrences of the first named entity of each relation in the collection of information items;

identifying a second number of occurrences of the second named entity of each relation in the collection of information items; and

identifying a third number of occurrences of each relation in the collection of information items.

17. The method of claim 15, wherein said merging comprises:

forming a digest of unique argument values that appear in the plurality of relations, to provide a set of itemized entities;

providing pair score information for each pair of a particular first argument value and a particular second argument value within the itemized entities, to overall provide a set of scored entity pairs, each instance of pair score information reflecting an extent to which the particular first argument value is equivalent to the particular second argument value;

using the pair score information associated with the scored entity pairs to identify equivalent argument values, to provide a set of conflated relations; and

modifying the plurality of relations by replacing each group of argument values that have been assessed as being equivalent with a canonical argument value, to provide the argument-merged facts.

18. The method of claim 15, wherein said forming comprises:

identifying one or more partitions within the argument-merged facts, each partition grouping together relations associated with a particular same first argument type, and a particular same second argument type;

identifying one or more original clusters associated with each partition, each original cluster being associated with a particular relation value;

identifying, for each partition, at least two clusters, if any, that pertain to a same relation value; and

merging, for each partition, said at least two clusters into a single cluster.

19. The method of claim 15, wherein said generating comprises:

generating the confidence score information for each particular relation in said relation clusters based at least on a first set of feature values and a second set of feature values,

the first set of feature values including subsystem-originating confidence score information that is provided by one or more prior subsystems in a pipeline of operations performed by the method, and

the second set of feature values provides a statistical measure of the occurrence of the particular relation and/or a part thereof within the collection of information items.

20. A computer-readable storage medium storing computer-readable instructions, the computer-readable instructions, when executed by one or more processor devices, performing acts comprising:

receiving a collection of information items from one or more information sources via a computer network, the information items presenting unstructured information;

identifying a plurality of sentences in the unstructured information that mention at least two entities;

parsing the plurality of sentences in the unstructured information to obtain parsed sentences representing parts of individual sentences as parse trees;

identifying a plurality of relations between entities in the parsed sentences, wherein respective relations identify a first argument value associated with a first entity that corresponds to a subject expressed in a respective parsed sentence, a second argument value associated

with a second entity that corresponds to an object expressed in the respective parsed sentence, and a relation value which reflects a corresponding relationship between the first entity and the second entity expressed in the respective parsed sentence;

generating confidence score information for individual relations to provide scored relations, the confidence score information reflecting at least a parsing confidence in the parsing of the plurality of sentences to obtain the parse trees; and

outputting final extracted facts by selecting a subset of the scored relations based at least on the confidence score information.