Generating parse trees of text segments using neural networks

Patent metadata

Field	Value
Publication number	US-2017192956-A1
Application number	US-201615396091-A
Country	US
Kind code	A1
Filing date	Dec 30, 2016
Priority date	Dec 31, 2015
Publication date	Jul 6, 2017
Grant date	—

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating parse trees for input text segments. One of the methods includes obtaining an input text segment comprising a plurality of inputs arranged according to an input order; processing the inputs in the input text segment using an encoder long short term memory (LSTM) neural network to generate a respective encoder hidden state for each input in the input text segment; and processing the respective encoder hidden states for the inputs in the input text segment using an attention-based decoder LSTM neural network to generate a linearized representation of a parse tree for the input text segment.

First claim

What is claimed is:

1 . A method performed by one or more computers, the method comprising:
obtaining an input text segment comprising a plurality of inputs arranged according to an input order; processing the inputs in the input text segment using an encoder long short term memory (LSTM) neural network to generate a respective encoder hidden state for each input in the input text segment; and processing the respective encoder hidden states for the inputs in the input text segment using an attention-based decoder LSTM neural network to generate a linearized representation of a parse tree for the input text segment.

2 . The method of claim 1 , wherein the linearized representation of the parse tree for the input text segment is a sequence of symbols from a predetermined vocabulary of parse tree symbols arranged according to an output order.

3 . The method of claim 2 , wherein, for each position in the output order, the attention-based LSTM neural network is configured to process a current symbol to generate an attention vector over the encoder hidden states for the inputs and to process the attention vector to generate a set of output scores for the position.

4 . The method of claim 3 , wherein, for a first position in the output order the current symbol is a placeholder input and, for each other position in the output order, the current symbol is the symbol at the preceding position in the output order in the sequence of symbols.

5 . The method of claim 3 , wherein the set of output scores includes a respective score for each of the symbols in the predetermined vocabulary and a score for a predetermined output that is not in the predetermined vocabulary.

6 . The method of claim 5 , wherein processing the respective encoder hidden states for the inputs in the text segment using the attention-based decoder LSTM neural network comprises, for each position in the output order:
processing the current output through one or more decoder LSTM layers to update a current decoder hidden state of the attention-based decoder LSTM neural network to generate an initial updated decoder hidden state for the position in the output order; generating an attention mask for the position in the output order from the initial updated decoder hidden state for the position and the encoder hidden states for the inputs in the input text segment, wherein the attention mask includes a respective attention score for each of the encoder hidden states; combining the encoder hidden states for the inputs in the input text segment in accordance with the attention scores to generate the attention vector for the position; generating the set of output scores for the position in the output order using the attention vector for the position and the initial updated decoder hidden state for the position in the output order; and selecting an output for the position in the output order in accordance with the output scores.

7 . The method of claim 6 , further comprising, for the first position in the output order, initializing the current decoder hidden state using a final encoder hidden state.

8 . The method of claim 7 , wherein processing the inputs in the input text segment using the encoder LSTM neural network comprises:
reversing the input order; and processing the inputs in the input text segment using the encoder LSTM neural network according to the reversed input order, and wherein the final encoder hidden state is the encoder hidden state for the last input according to the reversed input order.

9 . The method of claim 7 , wherein processing the inputs in the input text segment using the encoder LSTM neural network comprises:
processing the inputs in the input text segment using the encoder LSTM neural network according to the input order, and wherein the final encoder hidden state is the encoder hidden state for the last input in the input order.

10 . The method of claim 6 , wherein generating the set of output scores for the position in the output order using the attention vector for the position and the initial updated decoder hidden state for the position in the output order comprises:
generating a final updated decoder hidden state for the position from the attention vector and the initial updated decoder hidden state; and generating the output scores from the final updated decoder hidden state for the position.

11 . The method of claim 6 , wherein processing the respective encoder hidden states for the inputs in the text segment using the attention-based decoder LSTM neural network comprises, for a last position in the output order:
determining that the selected output is the predetermined output that is not in the vocabulary and, in response, determining not to generate any additional outputs for the linearized representation and selecting the outputs before the last position in the output order as the linearized representation.

12 . The method of claim 1 , further comprising:
generating the parse tree for the input text segment from the linearized representation of the parse tree.

13 . The method of claim 1 , wherein the input text segment is a variable length input text segment.

14 . The method of claim 1 , wherein the parse tree is a tree that represents the syntactic structure of the text segment according to a context-free grammar, and wherein a linearized representation of a particular parse tree is generated by traversing the particular parse tree in a depth-first traversal order.

15 . The method of claim 1 , wherein each input in the text segment is either a word or a punctuation mark from the text segment.

16 . A system comprising one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
obtaining an input text segment comprising a plurality of inputs arranged according to an input order; processing the inputs in the input text segment using an encoder long short term memory (LSTM) neural network to generate a respective encoder hidden state for each input in the input text segment; and processing the respective encoder hidden states for the inputs in the input text segment using an attention-based decoder LSTM neural network to generate a linearized representation of a parse tree for the input text segment.

17 . The system of claim 16 , wherein the linearized representation of the parse tree for the input text segment is a sequence of symbols from a predetermined vocabulary of parse tree symbols arranged according to an output order.

18 . The system of claim 17 , wherein, for each position in the output order, the attention-based LSTM neural network is configured to process a current symbol to generate an attention vector over the encoder hidden states for the inputs and to process the attention vector to generate a set of output scores for the position.

19 . The system of claim 18 , wherein processing the respective encoder hidden states for the inputs in the text segment using the attention-based decoder LSTM neural network comprises, for each position in the output order:
processing the current output through one or more decoder LSTM layers to update a current decoder hidden state of the attention-based decoder LSTM neural network to generate an initial updated decoder hidden state for the position in the output order; generating an attention mask for the position in the output order from the initial updated decoder hidden state for the position and the encoder hidden s

Assignees

• Google Inc

Inventors

• Kaiser Lukasz Mieczyslaw
• Vinyals Oriol

Classifications

• G06F40/211 Primary

  Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars · CPC title

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title

• G10L25/30

  using neural networks · CPC title

• G06N3/0442

  characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU] · CPC title

• G06N3/09

  Supervised learning · CPC title