Graph long short term memory for syntactic relationship discovery

• US 10,255,269 B2
• Filed: 12/30/2016
• Issued: 04/09/2019
• Est. Priority Date: 12/30/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Quirk, Christopher Brian, Toutanova, Kristina Nikolova, Yih, Wen-tau, Poon, Hoifung, Peng, Nanyun
• Primary Examiner(s): Guerra-Erazo, Edgar X
• Application Number:
  US15/395,961
• Publication Number:
  US 20180189269A1
• Time in Patent Office: 830 Days
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 40/00 Handling natural language data speech analysis or synthesis, speech recognition G10L
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/263 Language identification
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

Long short term memory units that accept a non-predefined number of inputs are used to provide natural language relation extraction over a user-specified range on content. Content written for human consumption is parsed with distant supervision in segments (e.g., sentences, paragraphs, chapters) to determine relationships between various words within and between those segments.

Claims

1. A method for analyzing natural language text based on linguistic relationships, comprising:

receiving a graph long short term memory (LSTM) relation extractor;

receiving a selection of documents to query for syntactic relationships;

receiving a keyword tuple, the keyword tuple including multiple keywords and specifying a relationship between the keywords;

parsing the selection of documents to discover natural language segments that include the keywords;

in response to locating a given natural language segment, processing the segment according to the graph LSTM relation extractor to produce a relational score;

determining whether the relational score satisfies a relationship threshold;

in response to the relational score satisfying the relationship threshold, automatically returning the given natural language segment as responsive to the keyword tuple; and

without user input, adding the natural language segment to a knowledge base configured for searching according to at least two of one or more of the keywords and the relationship.

2. The method of claim 1, wherein searching of the knowledge base by relationship improves an accuracy of returns for the search.

3. The method of claim 2, wherein the knowledge base is configured for multi-task learning, wherein the segment is added to the knowledge base according to a first tuple having a first number of keywords and knowledge base is configured to return the segment in response to a second tuple that includes a second number of keywords, wherein the second number is less than the first number.

4. The method of claim 1, wherein in response to multiple natural language segments being discovered when parsing a given document, a given segment of the multiple natural language segments in which the key terms are closer together is selected as the given natural language segment.

5. The method of claim 1, wherein the natural language segments include multiple sentences.

6. The method of claim 1, wherein processing the given natural language segment according to the graph LSTM relation extractor further comprises:

determining linguistic relationships among words in the given natural language segment;

associating each word of the words in the given natural language segment with a graph LSTM unit; and

constructing, from multiple instances of the graph LSTM unit, an LSTM neural network according the semantic linguistic relationships, wherein each instance of the multiple instances receives input to a forget gate associated with a different instance of the graph LSTM unit associated with a term that precedes the word associated with the instance of the graph LSTM unit in the given natural language segment.

7. The method of claim 6, wherein the input received to the forget gate is weighted based on the linguistic relations of the term to the word in the given natural language segment.

8. The method of claim 6, wherein the graph LSTM unit includes:

a plurality of forget gates, wherein each forget gate of the plurality of the forget gates is configured to accept a hidden vector from one associated predecessor graph LSTM unit in the LSTM neural network.

9. The method of claim 1, wherein the relationship threshold is produced by processing the keyword tuple according to the graph LSTM relation extractor based on linguistic relation among the keywords.

10. The method of claim 1, wherein the linguistic relations include endophors, further comprising:

linking an endophor term to a cedent term; and

substituting the endophor term for the cedent term when processing the segment according to the graph LSTM relation extractor.

11. A system for analyzing linguistic relationships in natural language text, comprising:

a processor; and

a memory storage device including instructions that when executed by the processor are operable to provide a plurality of graph long short term memory (LSTM) units arranged in an LSTM neural network to provide entity relationships in natural language text, wherein each graph LSTM unit of the plurality of graph LSTM units is associated with a word vector from the natural language text and includes;

an input gate, operable to produce an input state by applying an input weight to the word vector and adding an input weighted sum of predecessor hidden vectors, wherein the predecessor hidden vectors are received from graph LSTM units preceding the graph LSTM unit in the LSTM neural network;

an output gate, operable to produce an output state by applying an output weight to the word vector and adding an output weighted sum of the predecessor hidden vectors;

a plurality of forget gates, wherein a number of forget gates equals a number of related words in a document segment associated with the word vector, wherein each forget gate of the plurality of forget gates is configured to receive an associated predecessor hidden vector from an associated predecessor graph LSTM unit in the LSTM neural network and to produce a forget state by applying a forget weight to the word vector and a weighting of the associated predecessor hidden vector;

a memory cell, operable to produce a memory state by multiplexing the input state with the word vector to which a memory weight is applied and a memory weighted sum of the predecessor hidden vectors is added, to which is added a sum of the forget weights produced by the plurality of forget gates multiplexed with an associated memory cell state of the associated predecessor graph LSTM units; and

wherein the graph LSTM unit transmits a hidden vector to successor graph LSTM units in the LSTM neural network, wherein the hidden vector is produced by multiplexing the output state with the memory state.

12. The system of claim 11, wherein the input gate, output gate, and memory gate are further configured apply sigmoid squashing functions to compress the sum of the predecessor hidden vectors.

13. The system of claim 11, wherein the weighting of the associated predecessor hidden vector is based on a dependency type between a word associated with the graph LSTM unit and a term associated with the associated predecessor hidden vector.

14. The system of claim 11, wherein the input weight, the output weight, the forget weight, and the memory weight are equal for each graph LSTM unit of the plurality of graph LSTM units.

15. The system of claim 11, wherein the word vector is retrieved from a dictionary in response to recognizing an associated word in the natural language text.

16. The system of claim 15, wherein the associated word recognized in the natural language text is not found in the dictionary, the system is further operable to:

assign a value for the word vector; and

add the associated word and the value to the dictionary.

17. A computer readable storage device including instructions for analyzing natural language text based on linguistic relationships, wherein the instructions comprise:

receiving a graph long short term memory (LSTM) unit;

receiving a training knowledge base, the training knowledge base including keywords that are associated according to a known relationship;

receiving a selection of documents;

parsing the selection of documents to discover natural language segments that include the keywords, wherein a first portion of the natural language segments exhibit the known relationship and a second portion of the natural language segments do not exhibit the known relationship; and

training the graph LSTM unit over a series of epochs, in which training comprises;

for each of the natural language segments discovered;

identifying a linguistic structure of a given natural language segment;

forming a neural network of instances of the graph LSTM unit having a structure based on the linguistic structure;

processing the keywords according to the neural network to produce a relational score;

comparing the relational score to a relational threshold to determine whether the neural network indicates the given segment exhibits the known relationship; and

for each epoch of the series of epochs, automatically adjusting at least one weighting of the graph LSTM unit for use in a next epoch of the series of epochs based on a number of the first portion determined to exhibit the known relationship and a number of the second portion determined to not exhibit the known relationship.

18. The computer readable storage device of claim 17, wherein the linguistic structure include endophors, further comprising:

linking an endophor term to a cedent term; and

substituting the endophor term for the cedent term when processing the keywords according to the neural network.

19. The computer readable storage device of claim 17, wherein the graph LSTM unit is configured for multi-task learning to discover sub-relations, wherein the graph LSTM unit has been trained with a first tuple having a first number of keywords and the query tuple includes a second number of keywords, wherein the second number is less than the first number.

20. The computer readable storage device of claim 17, wherein the relationship threshold is produced by processing the keywords associated according to the known relationship from the training knowledge base according to a training neural network of instances of the graph LSTM unit structured according to the known relationship.

21. The computer readable storage device of claim 17, wherein processing the given natural language segment according to the neural network of instances of graph LSTM units further comprises:

determining linguistic relationships among words in the given natural language segment;

associating each word of the words in the given natural language segment with an instance of the graph LSTM unit; and

wherein each instance of the graph LSTM unit receives input to a forget gate associated with a different instance of the graph LSTM unit associated with a term that precedes the word associated with the instance of the graph LSTM unit in the given natural language segment.