NEURAL QUESTION ANSWERING SYSTEM

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating a system output from a system input using a neural network system comprising an encoder neural network configured to, for each of a plurality of encoder time steps, receive an input sequence comprising a respective question token, and process the question token at the encoder time step to generate an encoded representation of the question token, and a decoder neural network configured to, for each of a plurality of decoder time steps, receive a decoder input, and process the decoder input and a preceding decoder hidden state to generate an updated decoder hidden state.

BACKGROUND

This specification relates to neural networks.

Some neural networks are recurrent neural networks. A recurrent neural network is a neural network that receives an input sequence and generates an output sequence from the input sequence. In particular, a recurrent neural network can use some or all of the internal state of the network from a previous time step in computing an output at a current time step.

SUMMARY

This specification describes a system implemented as computer programs on one or more computers in one or more locations. In particular, the system includes an encoder neural network configured to: receive an input sequence comprising a respective question token at each of a plurality of encoder time steps, and for each of the encoder time steps, process the question token at the encoder time step to generate an encoded representation of the question token. The system also includes a decoder recurrent neural network configured to, at each of a plurality of decoder time steps: receive a decoder input at the decoder time step, and process the decoder input and a preceding decoder hidden state to generate an updated decoder hidden state for the decoder time step. The system further includes a subsystem configured to: at each of the encoder time steps: determine whether the question token at the encoder time step satisfies one or more criteria for adding a variable representing the question token to a vocabulary of possible outputs; and when the question token at the encoder time step satisfies the one or more criteria, add the variable to the vocabulary of possible outputs and associate the encoded representation of the question token as an encoded representation for the variable. The subsystem is also configured to: at each of the decoder time steps: determine, from the updated decoder hidden state at the decoder time step and from respective encoded representations for possible outputs in the vocabulary of possible outputs, a respective output score for each possible output in the vocabulary of possible outputs, and select, using the output scores, an output from the vocabulary of possible outputs as a decoder output at the decoder time step.

Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. The system may be used to perform semantic parsing a large search space, such as a knowledge base. The system provides effective results, (i.e., answers to questions), on challenging semantic parsing datasets. For example, the system may receive questions as input, and provide answers to the questions efficiently, over a large search space. In some aspects, the system may take natural language as input and map the natural language input into a function. The function may be a sequence of tokens that reference functions, operations, or values stored in memory. In some aspects, the system may execute functions and/or partial functions to leverage semantic denotations during the search for a correct function that, when executed, generates an answer that corresponds to the natural language input. In some aspects, the system may execute functions and/or partial functions to leverage semantic denotations during the search for a correct function that, when executed, generates an answer that corresponds to the natural language input.

The system executes functions in a high level programming language using a non-differentiable memory. The non-differentiable memory enables the system to perform abstract, scalable, and precise operations, to provide answers to questions received as input. In some aspects, the non-differentiable memory is a key-variable memory that saves and reuses intermediate execution results. The system can be configured to provide a neural computer interface that detects and eliminates invalid functions, (i.e., functions that do not yield correct answers to corresponding questions), among the large search space. Additionally, the system is trained end-to-end and does not require feature engineering or domain-specific knowledge. The system integrates neural networks with a symbolic non-differentiable computing device to support abstract, scalable, and precise operations through a neural computing interface.

DETAILED DESCRIPTION

FIG. 1shows an example neural question answering system120. The neural question answering system120is an example of a system implemented as computer programs on one or more computers in one or more locations, in which the systems, components, and techniques described below are implemented.

The neural question answering system120is a machine learning system that receives system inputs and generates system outputs from the system inputs. For example, the system120may receive a natural language question112as a system input and generate an answer150to the natural language question as a system output. The question112may be provided to the neural question answering system120by a user device over a data communications network, e.g., the Internet, and the neural question answering system120may provide the answer150as a response to the received question112. The user device that provides input and receives output may be, e.g., a smartphone, a laptop, a desktop, a tablet, a smart speaker or other smart device, or any other type of user computer. In some implementations, a user of the neural question answering system120can submit the question as a voice query, and the neural question answering system120can provide a spoken utterance of the answer150as part of a response to the voice query, i.e., for playback by the user device.

Generally, the neural question answering system120generates answers to questions, e.g., the answer150, by executing functions140against a knowledge-base (KB)130. For example, the neural question answering system120may provide answers to questions about information stored in the KB130. The information stored in the knowledge base may be, for example, data identifying entities and attributes of the entities. For example, the KB130may be a collection of structured data that identifies attributes of entities of one or more types, e.g., people, places, works of art, historical events, and so on.

In some aspects, the neural question answering system120, after receiving the question110, the neural question answering system120searches a large search space of possible functions for a particular function that, when executed by the neural question answering system120against the information stored in the KB130, generates the answer150that corresponds to the received question110.

The neural question answering system120includes an encoder neural network122, a decoder neural network124, and a question answering subsystem126.

The encoder neural network122is a recurrent neural network, e.g., a gated recurrent unit neural network (GRU) or a long short-term memory neural network (LSTM), that receives the question112and maps each token in the question112to a respective encoded representation. That is, given a sequence of words in natural language format, the encoder neural network122maps each of the words in the input sequence to a respective encoded representation. The encoded representations are an ordered collection of numeric values, such as a vector of floating point values or a vector of quantized floating point values. In particular, at each encoder time step, the encoder neural network122receives the input at the time step and updates an encoder hidden state and generates the encoded representation for the input.

The decoder neural network124is also a recurrent neural network that is configured to, at each of multiple decoder time steps, receive a decoder input at the decoder time step and process the decoder input and the preceding decoder hidden state to generate an updated decoder hidden state for the decoder time step.

At each decoding time step, the question answering subsystem126uses the updated decoder hidden state to generate an output for the decoder time step. In particular, the outputs generated by the subsystem126are tokens from computer program expressions that include, for each of a plurality of functions, a function identifier for the function and possible arguments to the function. The question answering subsystem126may execute one or more of the particular functions, as defined by the outputs selected at the decoder time steps, to generate an answer, and the answer may be provided by the neural question answering system120as the answer150to the question112.

Specifically, the decoder neural network124is trained to generate decoder outputs that are used by the subsystem126to represent and refer to intermediate variables with values stored in the neural network system120. The neural network subsystem126stores the intermediate variables in a key-variable memory. In this instance, each intermediate variable includes an encoded representation v, and a corresponding variable token R that references the value in the memory.

In some aspects, the neural question answering system120uses the last hidden state of the encoder neural network122as the initial state of the decoder neural network124.

The encoder neural network122and the decoder neural network124are trained with weak supervision using an iterative maximum-likelihood (ML) procedure for finding pseudo-gold functions140that will bootstrap a REINFORCE algorithm. REINFORCE is used because the question answering subsystem126executes non-differentiable operations against the KB130, i.e., because the functions performed by the subsystem126are non-differentiable. As such, an end-to-end backpropagation training procedure can be problematic in training the question answering subsystem126.

Therefore, the question answering subsystem126is trained according to a REINFORCEMENT learning problem such as the following: given a question x, the state of the neural question answering system120, a particular action determined by the question answering subsystem126, and a reward124at each time step t ∈{0, 1 , . . . T} are (St, αt, rt). Due to the deterministic environment of the neural question answering system120, the state of the neural question answering system120is defined by the question x and the action sequence: st=(x, α0:t−1), where α0:t−1=(α0, . . . , αt−1) is the history of actions at time t.

A valid action at time t is αt∈A(st), where A(st) is a set of valid tokens output by the question answering subsystem126. In this instance, each action corresponds to a token, and the full history of actions α0:Tcorrespond to a function. The reward for a particular question, such as reward114for question112, can be referred to as rt−I[t−T]*F1(x,α0:T). The reward114may include one or more rewards that correspond to the natural language questions, and indicate how well the neural question answering system120answered the question112during raining. The reward is non-zero at the last decoding time step, and is the F1score computed by comparing the gold answer and the answer generated by executing the function α0:T. Therefore, the reward of function α0:Tis characterized by the following:

While REINFORCE assumes a stochastic policy, beam search may be used to train the neural question answering system120for gradient estimation. Therefore, a predetermined number of top-k action sequences, such as functions140, may be used in the beam with normalized probabilities. The use of the top-k action sequences used in the beam with normalized probabilities allows the neural question answering system120to be trained with sequences of tokens that have a high probability of yielding a correct answer to a given question. By training the neural question answering system120with sequences of tokens that have a high probability, the variance of the gradient may be reduced.

Additionally, the neural question answering system120is trained using iterative maximum-likelihood (ML). Iterative ML is used to search for good or correct functions140given fixed parameters, and to optimize the probability of the “best” function for producing a correct answer at a given point in time, (i.e., selecting an output from the vocabulary of possible outputs). For example, decoding is performed by the decoder neural network124with a large beam size. In this instance, a pseudo-gold function is declared based on the highest achieved reward with the shortest length, among functions140decoded in all previous iterations of decoding. The ML objective is further optimized so that a particular question is not mapped to a function if the question is found to not include a positive, corresponding reward.

Iterative ML is used during training to train for multiple epochs after each iteration of decoding. This iterative process includes a bootstrapping effect in which an efficient neural question answering system120leads to a better function (that yields the correct answer to a given question) through decoding, and a better function leads to an efficient neural question answering system through training.

Although a large beam size may be used in training, some functions140are difficult to find using the neural question answering system120, due to a large search space. The large search space may be addressed through the application of curriculum learning during the training. The curriculum learning is applied during training by gradually increasing the set of functions140used by the subsystem and the length of the function when performing iterative ML. However, the incorporation of iterative ML uses pseudo-gold functions140that make it difficult to distinguish between tokens that are related to one another. One way to aid in the differentiation between related tokens, is to combine iterative ML with REINFORCE to achieve augmented REINFORCE.

FIG. 2shows an example workflow200for a neural question answering system. The workflow200describes an end-to-end neural network that performs semantic parsing over a large search space such as a knowledge-base (KB). The workflow200includes a question210that is provided as input, a question answering subsystem215for processing the question210, a non-differentiable interpreter220, entities230, relations240, functions250, an output260or answer to the question210, and a KB270.

The question answering subsystem215represents a semantic parser as a sequence to sequence deep learning model. For example, the question answering subsystem215can provide answers to questions about information in the KB270by executing functions against the KB. By using semantic and syntactic constraints over a large search space, the question answering subsystem215may restrict the search space of logic forms to produce the correct answer to the corresponding question210.

The question210can include one or more questions that are input to the question answering subsystem215. In some aspects, the question210can include a natural language question such as “What is the largest city in the US?” In this instance, the question210may be provided to the question answering subsystem215for processing, to provide an answer the question210.

The question answering subsystem215can be configured to perform semantic parsing using structured data, such as data in the knowledge-base (KB)270. For example, the question answering subsystem215can be configured to perform voice to action processing, as a personal assistant, speech to text processing, and the like. Specifically, the question answering subsystem215can be configured to map received questions, such as question210, to predicates defined in the KB270. As such, the question answering subsystem215can process the semantics of a question that involves multiple predicates and entities230with relations240to the predicates. The semantics of the question210may be processed to select a function that can be executed to provide an answer to the question210.

The question answering subsystem215may use a neural computer interface that includes a non-differentiable interpreter220to process the natural language questions, such as question210. The non-differentiable interpreter220may be used as an integrated development environment to reduce the large search space (over the KB270) for the question210. For example, the interpreter220may be used by the question answering subsystem215to process the question210“What is the largest city in the US?”

The interpreter220may be used to extract entities230and relations240from the question210. Further, the interpreter220may be used to determine functions250to select in the generation of an answer to the question210. In this instance, the interpreter220may be used to extract the entity of US230A, the relations CityIn240A and Population240B, and the functions Hop250A, ArgMax250B, and Return250C. The entities230, relations240, and functions250will be discussed further herein.

The non-differentiable interpreter220may also be used to exclude invalid choices when mapping the question210to a particular function that is executed to generate an answer. The non-differentiable interpreter220may be used by the question answering subsystem215to remove potential answers that cause a syntax or semantic error. For example, the question answering subsystem215may use the non-differentiable interpreter220to perform syntax checks on arguments that follow particular functions250, and/or semantic checks between entities230and relations240.

The KB270can include data identifying a set of entities230, (i.e., US, Obama, etc.) and a set of relations240between the entities230, (i.e., CityinCountry, BeerFrom, etc.). The entities230and the relations240may be stored as triples in the KB270. In some examples, a triple may include assertions such as {entity A, relation, entity B} in which entity A is related to entity B by the relation in the triple.

The question answering subsystem215can be configured to produce and/or access a function250that is executed against the KB270to generate a correct answer or output to the question210. The potential answers to the question210may be generated by the execution of tokens from computer program expressions. The tokens may include a function identifier that corresponds to a particular function in the list of functions250, as well as a list of possible arguments to the particular function. For example, the question210may be “What is the largest city in the US?” In this instance, the question answering subsystem215may210extract the entity “US” and the relation “city in” from the question210. The question answering subsystem215can be configured to use the interpreter220to execute the Hop250A function with the entity US230A and the relation !Cityin240A. The question answering subsystem215may also extract the term “largest” from the question210to define a second relation Population240B to be used in combination to execute a second function250B.

The question answering subsystem215uses an encoder neural network and a decoder neural network to define functions250that take the entities230and relations240as input, to provide a correct answer to the question210as output260. Referring toFIG. 2, the question answering subsystem215executes the functions20A-C to generate the correct answer to the question210. In this instance, the question answering subsystem215generates NYC as the answer to the question210and provides NYC as output260.

FIG. 3is a flow diagram of an example process300for outputting an answer to an input question. For convenience, the process300will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural question answering system, e.g., the neural question answering system120of FIG.1, appropriately programmed in accordance with this specification can perform the process300.

At step310, the system receives an input sequence that includes multiple question tokens. The input sequence can correspond to a natural language question referencing one or more entities in a knowledge base (KB). The neural question answering system may receive the input sequence as a respective question token at each of a plurality of time steps.

At step320, the neural question answering system processes the question tokens using an encoder neural network. The neural question answering system uses the encoder neural network to generate an encoded representation of each of the question tokens. The neural question answering system generates the encoded representation by processing question tokens corresponding to the input sequence at each of a plurality of time steps. The processing of the input sequence to generate encoded representations of the input sequence is further described inFIG. 4. As part of processing the question tokens, the system also determines whether the question token at the encoder time step satisfies one or more criteria for adding a variable representing the question token to a vocabulary of possible outputs and, if so, adds the variable to the vocabulary of possible outputs and associate the encoded representation of the question token as an encoded representation for the variable. Adding variables to the vocabulary of possible outputs is also described below with reference toFIG. 4.

At step330, the neural question answering system processes the encoded representations of the inputs in the input sequence. The neural question answering system uses the decoder neural network to generate an answer to the question represented by the input sequence. The neural question answering system processes the encoded representation of the question tokens at each of a plurality of decoder time steps. In some aspects, the neural question answering system may use the decoder neural network to search a large search space for a particular function that, when executed by the neural question answering system, generates the answer that corresponds to the received input sequence or question.

In particular, at each decoder time step, the system generates a decoder input for the time step that includes, e.g., the encoded representation of the output at the preceding time step, processes the decoder input using the decoder neural network to generate an updated decoder hidden state, and then uses the decoder hidden state to select an output for the time step. When criteria are satisfied, the system executes a function from a set of functions using the decoder outputs that have been generated. When the processing has completed, the system selects the most recently generated function output as the system output for the input question. The processing of the encoded representations by the decoder neural network is further described inFIG. 5.

At step340, the neural question answering system outputs the answer to the question. The answer may correspond to an answer of a natural language question. The answer can include one or more answers produced by functions that are executed by the neural question answering system, against the knowledge-base. For example, the neural question answering system provides answers to questions about information stored in the KB.

FIG. 4is a flow diagram of an example process400for adding a variable to a vocabulary of possible outputs. For convenience, the process400will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural question answering system, e.g., the neural question answering system120ofFIG. 1, appropriately programmed in accordance with this specification can perform the process400.

At step410, the neural question answering system receives an input sequence that includes multiple question tokens. The input sequence can correspond to a natural language question referencing one or more entities in a knowledge base (KB). The neural question answering system may receive the input sequence as a respective question token at each of a plurality of time steps.

At step420, the neural question answering system processes the question tokens using an encoder neural network. The neural question answering system uses the encoder neural network to generate an encoded representation of each of the question tokens. The neural question answering system generates the encoded representation by processing question tokens corresponding to the input sequence at each of a plurality of time steps.

At step430, the neural question answering system determines whether each question token satisfies one or more criteria for adding a variable representing the question token to a vocabulary of possible outputs. For example, the neural question answering system may be configured to determine whether the question token at each of a plurality of encoder time steps satisfies the one or more criteria. In some aspects, the neural question answering system is configured to determine whether the question token at the encoder time step identifies an entity that is represented in a knowledge base (KB). If the neural question answering system determines that the question token at the encoder time step identifies an entity that is represented in the KB, then the neural network system may add the variable representing the question token to a vocabulary of possible outputs and link the variable to the entity that is represented in the knowledge base.

At step440, for each question token that satisfied the criteria, the neural question answering system adds the variable to the vocabulary of possible outputs and associates the encoded representation of the question token as an encoded representation of the variable. As such, the neural question answering system can be configured to add the variable to the vocabulary of possible outputs, when the question token satisfies the one or more criteria, and associate the encoded representation as an encoded representation so that the variable may be accessed by the corresponding key. In this instance, the encoded representation may be used by the neural question answering system as a reference indicator that can be used to access the variable via the corresponding encoded representation.

FIG. 5is a flow diagram of an example process500for selecting an output from a vocabulary of possible outputs. For convenience, the process500will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural question answering system, e.g., the neural question answering system120ofFIG. 1, appropriately programmed in accordance with this specification can perform the process500.

At step510, the neural question answering system receives a decoder input.

At step520, the neural question answering system processes the decoder input using a decoder neural network to update a decoder hidden state of the decoder neural network.

At step530, the neural question answering system determines a respective output score for each possible output in a vocabulary of possible outputs. For example, the neural question answering system may be configured to determine the respective output scores at each of a plurality of decoder time steps. The neural question answering system can be configured to determine the output scores from an updated decoder hidden state at each decoder time step and from respective encoded representations for the possible outputs in the vocabulary of possible outputs. In some aspects, the neural question answering system is configured to determine the respective output score for each possible output in the vocabulary by applying a softmax over a respective logit for each of the possible outputs. The determination of respective output scores for each possible output in the vocabulary is further described inFIG. 7.

Generally, the vocabulary of possible outputs includes tokens from computer program expressions, and wherein the tokens include, for each of a plurality of functions, a function identifier for the function and possible arguments to the function, including variables that have already been added to the vocabulary during the processing of the question by the system.

At step540, the neural question answering system selects an output from the vocabulary of possible outputs. The neural question answering system may select the output from the vocabulary of possible outputs at each of a plurality of decoder time steps. In some aspects, the neural question answering system may select the output from the vocabulary of possible outputs based on the respective output scores. For example, the neural question answering system may select an output in the vocabulary of possible outputs with the greatest respective output score as the output. The selection of an output from a vocabulary of final outputs is further described inFIGS. 6 and 7.

The neural question answering system repeats process500until a final output token from the vocabulary of possible outputs is selected as the decoder output. That is, in some examples, the tokens in the vocabulary include a special final output token. In this instance, the neural question answering system can determine whether the selected decoder output at the decoder time step is a special final output token. Additionally, or alternatively, the neural question answering system can select a most recently generated function output as the system output for an input sequence once the selected decoder output at the decoder time step is the special final output token.

FIG. 6is a flow diagram of an example process600for executing a function to determine a function output. For convenience, the process600will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural question answering system, e.g., the neural question answering system120ofFIG. 1, appropriately programmed in accordance with this specification can perform the process600.

At step610, the neural question answering system determines whether a selected decoder output is a final token in a computer program expression that identifies a function and one or more arguments to the function. The neural question answering system may be configured to determine whether the selected decoder output is a final token at each of a plurality of decoder time steps.

At step620, the neural question answering system executes the function with the one or more arguments as inputs to determine a function output. Once the function has been executed to generate a function output, the neural question answering system is configured to add a variable representing the function output to the vocabulary of possible outputs. Further, the neural question answering system may be configured to associate a decoder hidden state at the decoder time step at which the function was executed as an encoded representation for the variable. In this instance, the variable may be accessed by the neural question answering system using the encoded representation.

At step630, the neural question answering system adds a variable representing the function output to the vocabulary of possible outputs. The neural question answering system also associates the decoder hidden state at the decoder time step as an encoded representation for the variable. In some aspects, the neural question answering system associates each decoder hidden state with an encoded representation corresponding to a particular variable at each of the plurality of decoder time steps.

FIG. 7is a flow diagram of an example process700for selecting an output from a vocabulary of possible outputs using logits. For convenience, the process700will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural question answering system, e.g., the neural question answering system120ofFIG. 1, appropriately programmed in accordance with this specification can perform the process700.

At step710, the neural question answering system generates a context vector that corresponds to a weighted sum over encoded representations of question tokens. The neural question answering system can generate the context vector using the updated decoder hidden state at each of the decoder time steps. For example, the system can apply a conventional attention mechanism to the decoder output and the encoder representation to generate the weights for the weighted sum.

At step720, the neural question answering system generates an initial output vector. The neural question answering system can be configured to generate the initial output vector using the updated decoder hidden state and the context vector that corresponds to the weighted sum over the encoded representation of the question tokens. For example, the system can add, multiply, concatenate, or otherwise combine the decoder hidden state and the context vector to generate the initial output vector.

At step730, the neural question answering system calculates a similarity measure between the initial output vector and encoded representations for possible outputs in a vocabulary of possible outputs. The neural question answering system may calculate a similarity measure at each of a plurality of decoder time steps. Further, the neural question answering system can calculate the similarity measure for at least a plurality of the encoded representations.

At step740, the neural question answering system generates a logit for each possible output in the vocabulary of possible outputs. The neural question answering system may generate the logit for the possible outputs using the calculated similarity measure between the initial output vector and the respective encoded representations for possible outputs in the vocabulary of possible outputs.

At step750, the neural question answering system selects a valid output from the vocabulary of possible outputs using the logits.

In particular, before selecting the output, the system determines which outputs would be valid, i.e., which outputs would not cause a semantic error or a syntax error when following the preceding output in the output sequence, and then selects an output from only the valid possible outputs. For example, the system can select the valid output having the highest logit or set the logits for invalid outputs to negative infinity, apply a softmax the logits for the possible outputs to generate a respective probability for each possible output (with the probabilities for invalid outputs being zero due to the logits being set to negative infinity) and then sample an output in accordance with the probabilities.

Particular embodiments of the invention have been described. Other embodiments are within the scope of the following claims. For example, the steps recited in the claims can be performed in a different order and still achieve desirable results.