Sequence modeling via segmentations

1 . A method of translating an input sequence representing a human-language sequence in a first language into an output sequence representing a human-language sequence in a second language, the method comprising performing, by one or more hardware processors, operations comprising:

training a first set of artificial neural networks, on training examples each comprising a training input sequence and an associated training output sequence;

using a trained second set of artificial neural networks to generate the input sequence from the human-language sequence in the first language, the second set of neural networks comprising a local reordering layer for locally reordering an embedded representation of the human-language sequence in the first language;

using a beam search algorithm to determine the output sequence from the input sequence based on the trained first set of artificial neural networks, wherein the output sequence comprises vectors identifying words or sub-units of words in the second language;

mapping the output sequence onto human-language output in the second language; and

providing the human-language output,

wherein the training comprises:

for each training example, computing a probability of the associated training output sequence by performing operations including:

operating, for valid segmentations of the training output sequence into segments, instances of a first recurrent neural network of the first set of artificial neural networks on the training input sequence to compute output-segment probabilities for the segments; and

using dynamic programming recursions, computing the probability of the training output sequence as a sum of probabilities of the valid segmentations of the training output sequence into segments, wherein the probability of each valid segmentation is a product of the output-segment probabilities computed for the segments of the training output sequence for the respective segmentation; and

using backpropagation to update network weights of the first set of artificial neural networks based on gradients of the probabilities of the training output sequences of the training examples.

2 . The method of claim 1 , wherein the output-segment probabilities depend on respective concatenations of preceding output segments, and wherein the operations for computing the probability of the training output sequence further include using a second recurrent neural network of the first set of artificial neural networks to compute encodings of the respective concatenations of preceding output segments.

3 . The method of claim 1 , wherein computing the probability of the training output sequence comprises recursively computing forward and backward probabilities for two-way output-sequence partitioning.

4 . The method of claim 1 , wherein, in computing the output-segment probabilities, an output-segment length is limited to a specified maximum value.

5 . The method of claim 1 , wherein, in computing the output-segment probabilities and in computing gradients of the output-segment probabilities during the backpropagation, contributions computed for longer output segments are reused during computations for shorter output segments contained in the respective longer output segments.

6 . The method of claim 1 , wherein the beam search algorithm comprises, for each element of the input sequence, performing a left-to-right beam search and thereafter merging any identical partial candidate output sequences obtained for multiple respective segmentations of the output sequence.

7 . The method of claim 1 , wherein the output sequence is modeled as monotonically aligned with the input sequence and as having a number of segments equal to a number of elements in the input sequence, empty segments being permitted.

8 . The method of claim 1 , wherein an output element of the local reordering layer is computed as a non-linear transformation of a weighted linear combination of elements of the embedded representations within an input window, each element being weighted in the weighted linear combination by gate values that depend on all elements within the input window.

9 . The method of claim 1 , wherein the second set of neural networks further comprises a word-embedding layer that generates the embedded representation of the human-language sequence in the first language by word embedding.

10 . The method of claim 1 , wherein the second set of neural networks further comprises a bidirectional recurrent neural network that generates the input sequence from the reordered embedded representation.

11 . One or more non-transitory machine-readable media storing:

data defining a trained first set of artificial neural networks, the first set of artificial neural networks modeling, for an output sequence admitting of segmental structure, a distribution of a probability of the output sequence over possible output sequences, wherein:

the probability of the output sequence is a sum of probabilities of all valid segmentations of the output sequence into segments,

the probability of each valid segmentation is a product of output-segment probabilities of the individual segments of the output sequence for the respective segmentation, and

the first set of artificial neural networks models distributions of the output-segment probabilities with respective instances of a recurrent neural network having an associated softmax layer;

data defining a trained second set of artificial neural networks modeling generation of encoded input sequences from human-language sequences in the first language, the second set of neural networks comprising a local reordering layer for locally reordering embedded representations of the human-language sequences in the first language; and

instructions for execution by one or more hardware processors, the instructions, when executed by the one or more hardware processors, causing the one or more hardware processors to perform operations for translating human-language input from a first language to a second language, the operations comprising:

encoding, with the trained second set of artificial neural networks, the human-language input into an encoded input sequence;

using a beam search algorithm to determine the output sequence from the encoded input sequence based on the trained first set of artificial neural networks, wherein the output sequence comprises vectors identifying words or sub-units of words in the second language;

mapping the output sequence onto human-language output in the second language; and

providing the human-language output.

12 . The one or more machine-readable media of claim 11 , wherein the beam search algorithm comprises, for each element of the encoded input sequence, performing a left-to-right beam search and thereafter merging any identical partial candidate output sequences obtained for multiple respective segmentations of the output sequence.

13 . A system comprising:

one or more hardware processors; and

one or more machine-readable media storing instructions for execution by the one or more hardware processors, the instructions, when executed by the one or more hardware processors, causing the one or more hardware processors to perform operations for translating an input sequence representing a human-language sequence in a first language into an output sequence representing a human-language sequence in a second language, the operations comprising:

training a first set of artificial neural networks on training examples each comprising a training input sequence and an associated training output sequence;

using a trained second set of artificial neural networks to generate the input sequence from the human-language sequence in the first language, the second set of neural networks comprising a local reordering layer for locally reordering an embedded representation of the human-language sequence in the first language;

using a beam search algorithm to determine the output sequence from the input sequence based on the trained first set of artificial neural networks, wherein the output sequence comprises vectors identifying words or sub-units of words in the second language;

mapping the output sequence onto human-language output in the second language; and

providing the human-language output,

wherein training the first set of artificial neural networks comprises:

for each training example, computing a probability of the associated training output sequence by performing operations including:

operating, for valid segmentations of the training output sequence into segments, instances of a first recurrent neural network of the first set of artificial neural networks on the training input sequence to compute output-segment probabilities for the segments; and

using dynamic programming recursions, computing the probability of the training output sequence as a sum of probabilities of the valid segmentations of the training output sequence into segments, wherein the probability of each valid segmentation is a product of the output-segment probabilities computed for the segments of the output sequence for the respective segmentation; and

using backpropagation to update network weights of the first set of artificial neural networks based on gradients of the probabilities of the training output sequence of the training examples.