Unsupervised relation detection model training

• US 10,073,840 B2
• Filed: 12/20/2013
• Issued: 09/11/2018
• Est. Priority Date: 12/20/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hakkani-Tur, Dilek Z., Tur, Gokhan, Heck, Larry Paul
• Primary Examiner(s): Han, Qi
• Application Number:
  US14/136,919
• Publication Number:
  US 20150178273A1
• Time in Patent Office: 1,726 Days
• Field of Search: 704 9, 704 1, 704 7, 704 10
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

A relation detection model training solution. The relation detection model training solution mines freely available resources from the World Wide Web to train a relationship detection model for use during linguistic processing. The relation detection model training system searches the web for pairs of entities extracted from a knowledge graph that are connected by a specific relation. Performance is enhanced by clipping search snippets to extract patterns that connect the two entities in a dependency tree and refining the annotations of the relations according to other related entities in the knowledge graph. The relation detection model training solution scales to other domains and languages, pushing the burden from natural language semantic parsing to knowledge base population. The relation detection model training solution exhibits performance comparable to supervised solutions, which require design, collection, and manual labeling of natural language data.

Claims

1. A method of automatically generating natural language patterns based on a knowledge graph, the method comprising:

selecting a relation from a knowledge graph;

extracting at least a first pair of words from the knowledge graph, wherein the first pair of words is connected by the relation;

receiving a set of documents as a search result based on a first query, wherein the first query comprises at least one instruction to select documents based on the first pair of words;

extracting, from the set of documents, at least one textual snippet based on the first query, wherein the at least one textual snippet includes at least in part the first pair of words;

extracting a second query from a query click log, wherein the query click log comprises at least one search query against at least a part of the set of documents and at least one link to at least one document, and wherein the second query is associated with at least one link to the at least one document containing the at least one textual snippet;

generating a first set of training patterns, wherein the first set of training patterns is based on association between the at least one textual snippet and the relation;

generating a second set of training patterns, wherein the second set of training patterns is based on association between the second query and the relation;

generating a third set of natural language patterns for the knowledge graph, wherein generating the set of natural language patterns further comprises selectively combining the first set of training patterns and the second set of training patterns based on at least one weight between the first set of training patterns and the second set of training patterns; and

applying the generated third set of natural language patterns to the knowledge graph to automatically train a natural language dialog system.

2. The method of claim 1, further comprising training a relation detection model using the set of natural language patterns for the knowledge graph.

3. The method of claim 1 wherein associating the at least one textual snippet further comprises:

retrieving all properties associated with the relation, wherein the properties comprise entities and corresponding relations;

comparing the properties to the at least one textual snippet; and

annotating the at least one textual snippet containing matches to entities from the properties with the corresponding relations.

4. The method of claim 1 further comprising interpolating the set of natural language patterns;

and

labeling the at least one snippet with additional relations from a set of additional relations using the relation classifier.

5. The method of claim 4 wherein the set of additional relations comprises relations with a high probability of appearing in a conversational input.

6. The method of claim 1 wherein the set of documents is on the World Wide Web.

7. The method of claim 1 wherein the relation and the pair of words form a triple.

8. A computer readable storage device containing computer executable instructions which, when executed by a computer, perform a method for training a relation detection model without supervision, the method comprising:

selecting a relation from a knowledge graph;

extracting at least a first pair of words from the knowledge graph, wherein the first pair of words is connected by the relation;

receiving a set of documents as a search result based on a first query, wherein the first query comprises at least one instruction to select documents based on the first pair of words;

extracting, from the set of documents, at least one textual snippet based on the first query, wherein the at least one textual snippet includes at least in part the first pair of words;

extracting a second query from a query click log, wherein the query click log comprises at least one search query against at least a part of the set of documents and at least one link to at least one document, and wherein the second query is associated with at least one link to the at least one document containing the at least one textual snippet;

generating a first set of training patterns, wherein the first set of training patterns is based on association between the at least one textual snippet and the relation;

generating a second set of training patterns, wherein the second set of training patterns is based on association between the second query and the relation;

generating a third set of natural language patterns for the knowledge graph, wherein generating the set of natural language patterns further comprises selectively combining the first set of training patterns and the second set of training patterns based on at least one weight between the first set of training patterns and the second set of training patterns; and

applying the generated third set of natural language patterns to the knowledge graph to automatically train a natural language dialog system.

9. The computer readable storage device of claim 8 wherein associating the at least one textual snippet further comprises:

selecting the smallest sequence of constituent elements in the at least one textual snippet that contains both words from the pair as the set of natural language patterns; and

replacing the both words in the set of natural language patterns with tokens from the knowledge graph corresponding to each of both words.

10. The computer readable storage device of claim 9 wherein the method further comprises associating a pair of words from the set of natural language patterns with additional relations when the pair of words corresponds to more than one relation.

11. A system comprising at least one processor in electronic communication with a computer readable storage device, the computer readable storage device storing instructions that, when executed, are capable of performing a method, the method comprising:

selecting a relation from a knowledge graph;

extracting at least a first pair of words from the knowledge graph, wherein the first pair of words is connected by the relation;

receiving a set of documents as a search result based on a first query, wherein the first query comprises at least one instruction to select documents based on the first pair of words;

extracting, from the set of documents, at least one textual snippet based on the first query, wherein the at least one textual snippet includes at least in part the first pair of words;

extracting a second query from a query click log, wherein the query click log comprises at least one search query against at least a part of the set of documents and at least one link to at least one document, and wherein the second query is associated with at least one link to the at least one document containing the at least one textual snippet;

generating a first set of training patterns, wherein the first set of training patterns is based on association between the at least one textual snippet and the relation;

generating a second set of training patterns, wherein the second set of training patterns is based on association between the second query and the relation;

generating a third set of natural language patterns for the knowledge graph, wherein generating the set of natural language patterns further comprises selectively combining the first set of training patterns and the second set of training patterns based on at least one weight between the first set of training patterns and the second set of training patterns; and

applying the generated third set of natural language patterns to the knowledge graph to automatically train a natural language dialog system.

12. The system of claim 11, further comprising training a relation detection model using the set of natural language patterns for the knowledge graph.

13. The system of claim 11 wherein associating the at least one textual snippet further comprises:

retrieving all properties associated with the relation, wherein the properties comprise entities and corresponding relations;

comparing the properties to the at least one textual snippet; and

annotating the at least one textual snippets containing matches to entities from the properties with the corresponding relations.

14. The system of claim 11 further comprising:

interpolating the set of natural language patterns and

labeling the at least one snippets with an additional relations from a set of additional relations using the relation classifier.

15. The system of claim 14 wherein the set of additional relations comprises relations with a high probability of appearing in a conversational input.

16. The system of claim 11 wherein the relation and the pair of words form a triple.

17. A method of automatically generating natural language patterns for a knowledge graph, the method comprising:

selecting a relation from a knowledge graph;

extracting at least a first pair of words from the knowledge graph, wherein the first pair of words is connected by the relation;

receiving a set of documents as a search result based on a first query, wherein the first query comprises at least one instruction to select documents based on the first pair of words;

extracting, from the set of documents, at least one textual snippet based on the first query, wherein the at least one textual snippet includes at least in part the first pair of words; and

associating the at least one textual snippet with the relation to form a set of natural language patterns for the knowledge graph.

18. The method of claim 17, further comprising:

extracting a second query from a query click log, wherein the query click log comprises at least one search query against the set of documents and at least one link to at least one document, and the second query is associated with at least one link to the at least one document containing the at least one textual snippet;

generating a first set of training patterns, wherein the first set of training patterns is based on association between the at least one textual snippet and the relation;

generating a second set of training patterns, wherein the second set of training patterns is based on association between the second query and the relation;

generating a set of natural language patterns for the knowledge graph, wherein generating the set of natural language patterns further comprises selectively combining the first set of training patterns and the second set of training patterns based on at least one weight between the first set of training patterns and the second set of training patterns; and

applying the generated set of natural language patterns to the knowledge graph to automatically train a knowledge graph-based natural language dialog system.