Patent Description:
<CIT> describes systems for neural machine translation, one of the systems including an encoder neural network with an input forward LSTM layer, an input backward LSTM layer, and a plurality of hidden LSTM layers, as well as a decoder subsystem.

The Transformer model is described in <NPL>.

This specification describes systems that implement a Universal Transformer.

Universal Transformers address, among others, the shortcomings described in the Background, above. Instead of the common sequence-aligned recurrence, the Universal Transformer is recurrent in depth, while employing self-attention to combine information from different parts of sequences.

The Universal Transformer combines the desirable parallelizability of self-attentive feed-forward models with an inductive bias well suited to a range of algorithmic and natural language problems. By tying parameters across layers (depth), the Universal Transformer can be seen as iteratively refining its encoding of the sequence by applying a recurrent transformation in parallel over all symbols in the sequence for several steps (in depth).

The Universal Transformer has additional computationally advantageous features. For example, unlike the Transformer model, the Universal Transformer is computationally universal, meaning that the model can be used to simulate any Turing machine. In addition, number of computational steps of the Universal Transformer can be varied dynamically after training because the model shares weights across its sequential computational steps. Thus, the depth employed by the model can be scaled dynamically to the size and/or complexity of the input sequence.

In experiments on several tasks, the Universal Transformer consistently improves significantly over both a feed-forward Transformer and an LSTM (Long short-term memory) recurrent neural network.

An adaptive variant of the Universal Transformer employs an adaptive computation time mechanism per position in the sequence. When running for a fixed number of steps the Universal Transformer is equivalent to a Transformer whose parameters are tied across layers. In its adaptive form, however, the Universal Transformer can effectively interpolate between the feed-forward, fixed depth Transformer and a gated, recurrent architecture running for a number of steps dependent on the input data. In experiments, the adaptive variant achieves state of the art results on multiple language understanding tasks.

The Universal Transformer optionally applies a dynamic Adaptive Computation Time (ACT) halting mechanism at each position of the sequence. ACT mechanisms are described in Graves, Adaptive computation time for recurrent neural networks, arXiv preprint arXiv: <NUM>, <NUM>, available at https://arxiv. org/pdf/<NUM>.

The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages.

A Universal Transformer system of the type described can be used to implement autoregressive sequence-to-sequence models wherever such models are used to generate outputs. Examples of applications of autoregressive models include machine translation of one natural language to another, summarization of natural language text, in which the outputs are sequences of words in sentences, speech to text, and text to speech, involving sequences of words and phonemes. Other example applications include image generation, language modeling, and parsing, e.g., constituency parsing. Other examples include applications based on sequences of images, including applications in self-driving cars and robotics control. For example, from a sequence of inputs, e.g., images, of or from a physical system, real or virtual, that includes such model, can output a sequence of actions for controlling a machine operating in or with the physical system.

The techniques can be implemented advantageously in computer systems with GPUs and other accelerator hardware to exploit the parallel computational structure of the Universal Transformer.

<FIG> is a diagram that illustrates the operations of an example Universal Transformer on a sequence. The computational structure illustrated in <FIG> can be used to implement an encoder or a decoder on an encoder computer system or a decoder computer system having one or more computers in one or more locations. For simplicity, the example will be described as being implemented on a system of one or more computers. As described above, the computational structure of the Universal Transformer can be implemented on parallel processing systems, with each computational resource of a parallel processing system performing the operations of one or more positions in the sequence.

In general, to implement either an encoder or a decoder, the system can perform a same series of encoding or decoding operations over M sequence positions, possibly in parallel, for T iterations. As will be described in more detail below, in some implementations the system can adaptively devote more computing resources to some positions and less resources to other positions. In some implementations, the system uses the same parameter values across all positions and all time steps.

The operations of each time step at each position can include at least a self-attention process and a transition function. For example, at step t, the system can process the first element in the sequence, the hi representation 105a, using a self-attention process 112a and a transition function 114a. The system can then update the hi representation 105a and repeat the same steps for T iterations. Similarly, the system can process the second element in the sequence, the h<NUM> representation 105b, for T iterations using a self-attention process 112b followed by a transition function 114b and an update of the h<NUM> representation 105b. Likewise, the system can process the last element in the sequence, the hm representation <NUM>, for T iterations using a self-attention process <NUM> followed by a transition function <NUM> and an update of the hm representation <NUM>.

Although the computations for only three sequence positions are shown in <FIG>, the sequence can have any arbitrary length. Therefore, to improve computational performance the system can implement the computations on any appropriate parallel processing hardware. For example, each of the step operations can be implemented by different streaming multiprocessors of a GPU or different processing cores of a multicore CPU. Alternatively or in addition, each of the step operations can be performed by different computers in a distributed system.

As shown in <FIG>, the self-attention processes 112a-m for each sequence position can use as input the current representations of other sequence positions. In other words, at each step, the system can condition the output for a particular position on the representations so far generated for one or more other positions. When the operations are being performed with parallel processing, the representations can be stored in a centrally accessible location or broadcasted after each step to all processors performing the operations.

As will be described in more detail below, the self-attention process for the decoder can also include a second stage attention process that uses as input the final representations generated by the encoder.

<FIG> is a flowchart of an example process for encoding a source sequence. The example process can be performed by an appropriately programmed system of one or more computers in one or more locations. The process will be described as being performed by a system of one or more computers.

The system receives an input sequence (<NUM>). As described above, the Universal Transformer is widely applicable to a large collection of sequence-to-sequence learning tasks. Thus, the input sequence can be any appropriate input sequence of elements in a sequence-to-sequence learning task.

Common sequence-to-sequence learning tasks include question-answering tasks, in which case the input sequence is words in a question sentence; subject-verb agreement tasks, in which case the input sequence is words a natural language sentence; predicting missing target words, in which case the input sequence is one or more preceding natural language sentences; algorithmic tasks, in which case the input sequence can be a sequence of symbols, e.g., integers; program evaluation and memorization tasks, in which case the input is symbols in a computer program; machine-translation tasks, in which case the input is words of a natural language sentence in a first language.

The system generates respective initial representations of elements in the input sequence (<NUM>). For example, the system can generate a vector representation for each element in the input sequence. Thus, if the input sequence is of length m and the representations are d-dimensional, the system can initialize a matrix <MAT>, with m rows, one for each item of the input sequence, with the d elements of the representation of the item in the d columns of the matrix in the row. When the input elements are words, the system can generate the input representations that are respective word embeddings of the words in which the word embeddings are vector representations of the words.

The system then repeatedly revises the representations using a self-attention process and a transition function for multiple steps. Thus, the system revises the representations (<NUM>), and determines whether a stop-encoding condition is reached for each input element (<NUM>). In some implementations, the stop-encoding condition for each input element is a minimum number of revision steps T.

However, in sequence processing systems, certain symbols, e.g. some words or phonemes, are usually more ambiguous than others. Therefore, the system can dynamically determine to allocate more processing resources to these more ambiguous symbols. For example, the system can use Adaptive Computation Time as a mechanism for dynamically modulating the number of computational steps needed to process each input element. A Universal Transformer with dynamic halting thus modulates the number of computational steps needed to process each input symbol dynamically. The number of steps can be based on a scalar pondering value that is predicted by the model at each step. The pondering values are in a sense the model's estimation of how much further computation is required for the input symbols at each processing step.

Once the per-element recurrent block halts (indicating a sufficient number of revisions for that element), its representation is simply copied to the next step until all blocks halt or until a maximum number of steps is reached.

If the stop-encoding condition has not been met, the system performs another revision step (branch to <NUM>).

The system can apply the same series of operations iteratively on every step by recursively applying the same series of operations. In some implementations, the system also uses the same learned parameter values for each step.

For example, at each revision step t from <NUM> to T, the system can compute an updated representation Ht. To do so, the system can apply a multihead dot product self-attention mechanism followed by a recurrent transition function. In some implementations, the system also uses residual connections around each of these computations and applies dropout and layer normalization. In some implementations, the system computes the updated representation of Ht according to:
<MAT>
where
<MAT>
where the Pt terms are two-dimensional (position, time) coordinate embeddings, obtained by computing vertically and horizontally the sinusoidal position embedding vectors according to:
<MAT>
<MAT>
for the position and the time step separately (pos) for each dimension (i). The system can then sum these component-wise before applying the self-attention process.

The self-attention process can be computed as a multihead self-attention with k heads according to:
<MAT>
where
<MAT>
the projections are the following learned parameter matrices:
<MAT>
and the attention is a scaled dot product attention computed according to:
<MAT>
where d is the number of columns of Q, K and V and the dimension of the symbol representations.

The system can tailor the transition function to the particular task. For example, the system can use a separable convolution or a fully-connected neural network having a single rectified-linear activation function between two linear transformations, applied position-wise, e.g., individually to each row of At.

After the stop-encoding condition is reached, e.g., after T steps, the system provides final representations to the decoder (<NUM>). In some implementations, the final output is a matrix of vector representations HT for the input sequence.

<FIG> is a flowchart of an example process for decoding a target sequence. As described above, the decoding process can share the same basic structure in depth as the encoder process, but performs an additional self-attention stage that uses the final encoder representations. As shown by <FIG> and <FIG>, the system can implement the Universal Transformer by running the encoder process with T steps once, followed by running the decoder process with N steps each autoregressively multiple times for each element in the target sequence. The example process can be performed by an appropriately programmed system of one or more computers in one or more locations. The process will be described as being performed by a system of one or more computers.

The system receives an initial target sequence (<NUM>). The system can generate the initial target sequence according to the task at hand. For example, tasks related to natural language processing and machine translation, the system can initialize an answer sequence. For tasks relating to algorithmic process and program evaluation, the system can initialize a sequence of symbols.

The system revises a representation of the next predicted element in the target sequence using two-stage self-attention and a transition function (<NUM>). The system can use the same structure as the encoder, with a first self-attention stage. The system can additionally apply a second self-attention stage using the final encoder representations of the input sequence using a multihead dot product attention function. In the second self-attention stage, the system can use queries Q obtained from projecting the decoder representations and keys K and values V obtained from projecting the encoder representations. The system can autoregressively determine each next symbol in the sequence, which means that each output in the target sequence is conditioned on all of the previously generated outputs in the target sequence.

The system determines whether a stop-decoding condition is met for the next element in the target sequence (<NUM>). In some implementations, the system uses a fixed number of steps N, which may or may not be equal to the number of steps T used by the encoder process.

Alternatively or in addition, the system can adaptively alter the number of steps in the decoding process for the next symbol depending on the position of the next symbol. For example, the system can apply the Adaptive Computation Time (ACT) halting mechanism at each position and copy the state to the next step after a block is halted, until all blocks are halted or the predetermined maximum number of steps have been performed.

If the stop-decoding condition is not met, the system again performs another step of revisions for the next element in the target sequence (branch to <NUM>).

Otherwise, the system determines whether there are more elements to decode (branch to <NUM>). In some implementations, the model is trained to generate a special end-of-sequence symbol when there are no more output elements to be decoded. Therefore, the system can continue the process until the decoder generates the end-of-sequence symbol.

If there are more elements to decode, the system begins revising a representation of the next element in the target sequence (branch to <NUM>).

If there are no more elements to decode, the system provides a final transformed output sequence (branch to <NUM>). To obtain the per-symbol target distributions at positions <NUM> through n, the system can apply an affine transformation O from the final state to an output vocabulary size, followed by the following softmax function: <MAT>.

During the training process, the system can perform teacher-forced training in which the decoder input is the target output shifted to the right by one position. The system can further mask the decoder self-attention distributions so that the model can only attend to positions to the left of any predicted symbol.

<FIG> illustrates an example architecture of a Universal Transformer. As described above, the Universal Transformer includes a recurrent encoder block <NUM> and a recurrent decoder block <NUM>. Each of these blocks can be implemented using respective computing resources, and, as described above, the blocks can have multiple instances for each element in an input sequence.

For ease of illustration the encoder block <NUM> is illustrated in <FIG> as receiving a source sequence <NUM>. However, as described above, a system can use multiple instances of the encoder block for each element in the source sequence <NUM>, which can be executed for T steps in parallel. Thus, the representation of the source sequence <NUM> in <FIG> can be interpreted as a matrix with each row being a different representation of a different element in the source sequence <NUM>.

In operation, the encoder block <NUM> can receive the source sequence <NUM> and add position and timestep embeddings. The encoder block <NUM> can then perform a multihead self-attention process <NUM>, followed by layers of dropout <NUM> and layer normalization <NUM>. The encoder block <NUM> can then perform a transition function <NUM> followed by another layer of dropout <NUM> and layer normalization <NUM>.

The encoder block then repeats these operations for T steps, each time revising the representation of each element in the source sequence <NUM>. After T steps, the encoder block <NUM> provides the final representations of the elements in the source sequence <NUM> to the decoder block <NUM>. As described above, the number of steps for each input element can differ. For elements whose encoding block has halted, the system can simply copy the halted representation to the next step.

For ease of illustration, the decoder block <NUM> is illustrated in <FIG> as receiving a target sequence <NUM>. However, as described above, a system can use multiple instances of the decoder block for multiple steps for each element so far generated in the target sequence. In other words, the number of decoder blocks can grow as more elements are generated in the target sequence. The system can execute each of the decoder blocks for each of the elements in the target sequence in parallel.

In operation, the decoder block <NUM> can receive the target sequence <NUM> and add position and timestep embeddings. The decoder block <NUM> can then perform a multihead self-attention process <NUM>, followed by layers of dropout <NUM> and layer normalization <NUM>. The decoder block <NUM> can then perform a second stage of attention, with a multihead attention process <NUM> conditioned on the final representations generated by the encoder block <NUM>.

The decoder block <NUM> can then perform additional layers of dropout <NUM> and layer normalization <NUM> before performing a transition function <NUM>. The decoder block <NUM> can perform final layers of dropout <NUM> and layer normalization <NUM>.

The decoder block <NUM> can repeat these operations for multiple steps for each element in the target sequence. As described above, the number of steps can be dynamically selected by the model for each position to be decoded.

After the N steps of decoding have completed, the system applies a final softmax layer <NUM> to generate final output probabilities <NUM>.

<FIG> illustrates dynamic selection of a number of processing steps per element in a sequence. As shown, the sequence has four elements, each with a respective initial representation 505a, 505b, 505c, and 505d.

At step <NUM>, the system can generate in parallel four revised representations using respective encoder or decoder blocks for each position.

At step <NUM>, the block for position <NUM> halts, while the system generates three revised representations for the other positions.

At step <NUM>, the system generates three revised representations for the three positions that have not yet halted.

At step <NUM>, the block for position <NUM> halts. The system generates two revised representations for the other positions that have not halted at position <NUM> and position <NUM>.

The dashed lines in <FIG> represent the inputs to the self-attention process used to generate the revised representations. Thus, at step <NUM>, the system generates the revised representation for position <NUM> by using the representations of the other positions as input to the self-attention process. Notably, as shown in <FIG> the system uses the halted representation for position <NUM> from step <NUM>, while using representations from step <NUM> for positions <NUM> and <NUM>. In other words, the system can execute the self-attention process by using representations generated in different steps at different times.

At step <NUM>, the block for position <NUM> halts, and the system generates a revised representation only for position <NUM>.

Similarly, at step <NUM>, the system generates a revised representation for position <NUM> using representations generated on three different steps: the representation from step <NUM> for position <NUM>, the representation from step <NUM> for position <NUM>, and the representation from step <NUM> for position <NUM>.

The final output of the process is then the collection of the final halted representations at each position.

As described above, systems and methods described herein may be applied to a variety of technical tasks, a few of which will now be described in more detail.

For example, for question-answering tasks the goal is to answer a question given a number of English sentences that encode potentially multiple supporting facts. The goal is to measure various forms of language understanding by requiring a certain type of reasoning over the linguistic facts presented in each story. A standard Transformer does not achieve good results on this type of task. To encode the input, the system can first encode each fact in the story by applying a learned multiplicative positional mask to each word's embedding, and summing up all embeddings. Models can either be trained on each task separately ("train single") or jointly on all tasks ("train joint"). The system can embed the question in the same way, and then feed the Universal Transformer with these embeddings of the facts and questions. Over <NUM> runs with different initializations and using the best model based on performance on the validation set, both the Universal Transformer and Universal Transformer with dynamic halting achieve state-of-the-art results on all tasks in terms of average error and number of failed tasks. TABLE <NUM> summarizes the results.

For subject-verb agreement tasks, the goal is to predict number-agreement between subjects and verbs in English. This task acts as a proxy for measuring the ability of a model to capture hierarchical dependency structure in natural language sentences. The system can use a language modeling training setup, i.e., a next word prediction objective, followed by calculating the ranking accuracy of the target verb at test time. The Universal Transformer was evaluated on subsets of the test data with different task difficulty, measured in terms of agreement attractors - the number of intervening nouns with the opposite number from the subject (meant to confuse the model). For example, given the sentence," The keys to the cabinet," the objective during training is to predict the verb are (plural). At test time, the ranking accuracy of the agreement attractors is evaluated: i.e. the goal is to rank "are" higher than is in this case. The best LSTM with attention from the literature achieves <NUM>% on this task, which outperforms a regular Transformer. The Universal Transformer significantly outperforms standard Transformers and achieves an average result comparable to the current state of the art (<NUM>%). However, the Universal Transformers (and particularly with dynamic halting) perform progressively better than all other models as the number of attractors increases. TABLE <NUM> summarizes the results.

For language modeling tasks, the goal is to predict missing target words, in which case the input sequence is one or more preceding natural language sentences. The dataset was specifically designed so that humans are able to accurately predict the target word when shown the full context, but not when only shown the target sentence in which it appears. It therefore goes beyond language modeling and tests the ability of a model to incorporate broader discourse and longer term context when predicting the target word. The task was evaluated in two settings: as language modeling (the standard setup) and as reading comprehension. In the former (more challenging) case, a model was simply trained for nextword prediction on the training data, and evaluated on the target words at test time. In other words, the model was trained to predict all words, not specifically challenging target words. In the latter setting, the target sentence (minus the last word) was used as query for selecting the target word from the context sentences. In this task, the Universal Transformer achieves state-of-the-art results in both the language modeling and reading comprehension setup, outperforming both LSTMs and normal Transformers. In this experiment, the control set was constructed similar to the language modeling development and test sets, but without filtering them in any way, so achieving good results on this set shows a model's strength in standard language modeling.

For algorithmic tasks, the goal is to perform a symbol transformation from one sequence to another, e.g. Copy, Reverse, and integer Addition. In an experiment in which the model was trained with sequences of length <NUM> and evaluated on sequences of length <NUM>, the system trained Universal Transformers using positions starting with randomized offsets to further encourage the model to learn position-relative transformations. The Universal Transformer outperformed both LSTM and the normal Transformer by a wide margin on all three tasks.

For learning-to-execute tasks, e.g., program evaluation and memorization, the Universal Transformer was evaluated on tasks indicating the ability of a model to learn to execute computer programs. These tasks include program evaluation tasks (program, control, and addition), and memorization tasks (copy, double, and reverse). Without using any curriculum learning strategy during training and without using target sequences at test time, the Universal Transformer achieves perfect scores in all the memorization tasks and also outperforms both LSTMs and Transformers in all program evaluation tasks by a wide margin.

For machine translation, the Universal Transformer was evaluated by training an English-German translation task. The Universal Transformer with a fully-connected recurrent transition function (instead of separable convolution) and without ACT improves by <NUM> BLEU over a Transformer and <NUM> BLEU over a Weighted Transformer with approximately the same number of parameters.

The Universal Transformer can also be adapted for use on other sequence-to-sequence tasks. One example application is speech-to-text conversion, in which case the input sequence is representations of sound waves and the output sequence is text in a particular language. Another example is text-to-speech conversion, in which case the input sequence is text, and the output sequence is representations of sound waves. Another example application is image generation. Another example application is robotic control. For example, in some implementations, the sequence of inputs may comprise images (e.g. images comprising pixel data), for instance images of or from a physical system, and the corresponding output may include a sequence of actions for controlling a machine or robot, which may operate in or with the physical system.

Embodiments of the subject matter and the actions and operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal, e.g., a machinegenerated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be or be part of a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them. A computer storage medium is not a propagated signal.

Data processing apparatus can include special-purpose logic circuitry, e.g., an FPGA (field programmable gate array), an ASIC (application-specific integrated circuit), or a GPU (graphics processing unit). The apparatus can also include, in addition to hardware, code that creates an execution environment for computer programs, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A computer program, which may also be referred to or described as a program, software, a software application, an app, a module, a software module, an engine, a script, or code, can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages; and it can be deployed in any form, including as a stand-alone program or as a module, component, engine, subroutine, or other unit suitable for executing in a computing environment, which environment may include one or more computers interconnected by a data communication network in one or more locations.

A computer program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub-programs, or portions of code.

The processes and logic flows described in this specification can be performed by one or more computers executing one or more computer programs to perform operations by operating on input data and generating output. The processes and logic flows can also be performed by special-purpose logic circuitry, e.g., an FPGA, an ASIC, or a GPU, or by a combination of special-purpose logic circuitry and one or more programmed computers.

Computers suitable for the execution of a computer program can be based on general or special-purpose microprocessors or both, or any other kind of central processing unit. The essential elements of a computer are a central processing unit for executing instructions and one or more memory devices for storing instructions and data. The central processing unit and the memory can be supplemented by, or incorporated in, special-purpose logic circuitry.

Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to one or more mass storage devices. The mass storage devices can be, for example, magnetic, magneto-optical, or optical disks, or solid state drives.

To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on, or configured to communicate with, a computer having a display device, e.g., a LCD (liquid crystal display) monitor, for displaying information to the user, and an input device by which the user can provide input to the computer, e.g., a keyboard and a pointing device, e.g., a mouse, a trackball or touchpad. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's device in response to requests received from the web browser, or by interacting with an app running on a user device, e.g., a smartphone or electronic tablet.

This specification uses the term "configured to" in connection with systems, apparatus, and computer program components. For special-purpose logic circuitry to be configured to perform particular operations or actions means that the circuitry has electronic logic that performs the operations or actions.

While this specification contains many specific implementation details, these should not be construed as limitations, but rather as descriptions of features that may be specific to particular embodiments of particular inventions.

Claim 1:
A system implemented by one or more computers, the system comprising:
an encoder configured to receive an input sequence of elements each having a respective initial input representation and to revise the input representations by iteratively applying a same series of operations to all the elements of the sequence, wherein the encoder is configured to apply the same series of operations iteratively by recursively applying the same series of operations, the operations applied to each element in parallel to the other elements of the sequence, revising the representations of the elements with each step in the recursion, for at most a predetermined maximum number of steps; and
a decoder configured to decode a target sequence of symbols y = (y1, ..., yn) autoregressively while at every step conditioning on the previously generated symbols and a final output of the encoder for the sequence.