Patent Description:
Discrete sequence processing is a central task of natural language understanding. A majority of natural language processing problems, such as part-of-speech tagging, chunking, named entity recognition, syntactic parsing, natural language inference, and extractive machine reading, are commonly formalized as sequence labeling and sequence classification task. Solutions to these problems improve numerous applications related to text understanding like dialog systems or information retrieval.

In recent years, natural language processing has been revolutionized by the application of recurrent neural networks. Recurrent neural networks comprising an encoder that reads each symbol of an input sequence sequentially to update its hidden states have become models of choice for natural language processing. After reading the end of the sequence, the hidden state of the recurrent neural network is a summary of the input sequence. Advantageously, the encoder operates bi-directionally and further comprises an attention mechanism to contextualize the hidden state of the encoder.

However, with methods of the state-of-the-art, recognizing long range dependencies between sentences and paragraphs of a text, which is a requirement for achieving automatic text comprehension, remains a difficult task. For example, performing global inference between a concept mentioned in different sections of a document remains challenging. Also, multi-hop inference is rarely handled by state-of-the-art systems.

Graph convolutional neural networks have been proposed to cope with the need for global inference in sentence understanding tasks, e.g. in <NPL>, <NPL>, or <NPL>.

These models require the input text to be transformed into graph structures, which represent words as nodes and include weighted links between nodes. However, in the state of the art, this transformation to a graph structure is performed in a hand-crafted manner, often employing diverse third party systems.

The present invention proposes a novel end-to-end graph convolutional neural network that transforms an input sequence of words into a graph via a convolutional neural network acting on an interaction matrix generated from the input sequence. In particular, in the proposed architecture, the graph structure is a latent dimension. The present invention further proposes a novel method of graph learning on the constructed graph. The constructed model is applied to tasks of sequence tagging and classification.

The disclosed approaches differ from similar approaches employing interaction matrices to model interaction between tokens as described in <NPL>, and <NPL>.

The disclosed approaches also differ from similar approaches of learning of latent relational graphs as proposed in <NPL>" to capture dependencies between pairs of data units from large-scale unlabeled data.

<NPL>, relates to a Multi-Task learning framework for Relation Extraction. The approach employs dependency parsing and entity type classification as auxiliary tasks and relation extraction as the target task. These tasks are simultaneously learnt from training instances to take advantage of inductive transfer between auxiliary tasks and the target task. A hierarchical neural network is constructed, which incorporates dependency and entity representations from auxiliary tasks into a more robust relation representation against the noisy labels.

The object of the present invention is to provide an end-to-end machine learning approach for parsing language entry to a computer.

This object is solved by the subject-matter of the independent claims.

Embodiments of the present invention are defined by the dependent claims.

In this disclosure, a novel end-to-end differentiable model of graph convolution is proposed. This approach allows the system to capture dependencies between words in an unsupervised manner. In contrast to methods of the prior art, the graph structure computed from the input sequence is a latent variable.

The described architecture allows for efficient multi-task learning in that the system learns graph encoder parameters only once and trains task-specific differentiable message-passing parameters by using the output of the graph encoders.

The proposed approach employs a fully differentiable pipeline for end-to-end message-passing inference composed with node contextualization, graph learning and a step of inference. The disclosed framework can be used in a multitask setting for joint graph encoder learning and possible unsupervised pre-training. The disclosed method enables extraction of grammatically relevant relationships between tokens in an unsupervised manner.

The disclosed neural network system may be applied to locate tokens in natural language sentences that correspond to keys of a database and to enter the identified tokens into the database under the respective key. The present invention may also be applied to provide labels for tokens of a natural language statement to a form interface such that the form interface may employ the labels of the tokens to identify and fill slots where a respective token is to be entered.

In an embodiment, a system for entering information provided in a natural language sentence to a computing device is provided. The natural language sentence, comprising a sequence of tokens, is processed by a contextualization layer configured to generate a contextualized representation of the sequence of tokens. A dimension-preserving convolutional neural network is configured to employ the contextualized representation to generate output corresponding to a matrix which is employed by a graph convolutional neural network as a set of adjacency matrices. The system is further configured to generate a label for each token in the sequence of tokens based on hidden states for the token in the last layer of the graph convolutional neural network.

According to another embodiment, the system may further comprise a database interface configured to enter a token from the sequence of tokens in a database by employing the label of the token as a key. In this embodiment, the graph convolutional neural network is trained with a graph-based learning algorithm for locating, in the sequence of tokens, tokens that correspond to respective labels of a set of predefined labels.

In an alternative embodiment, the system may comprise a form interface configured to enter a token from the sequence of tokens in at least one slot of a form provided on the computing device, wherein the label of the token identifies the slot. In this embodiment, the graph convolutional neural network is trained with a graph-based learning algorithm for tagging tokens of the sequence of tokens with labels corresponding to a semantic meaning.

In embodiments, the graph convolutional neural network comprises a plurality of dimension-preserving convolution operators comprising a 1x1 convolution layer or a 3x3 convolution layer with a padding of one.

In other embodiments, the graph convolutional neural network comprises a plurality of dimension-preserving convolution operators comprising a plurality of DenseNet blocks. In a particular further embodiment, each of the plurality of DenseNet blocks comprises a pipeline of a batch normalization layer, a rectified linear units layer, a 1x1 convolution layer, a batch normalization layer, a rectified linear units layer, a kxk convolution layer, and a dropout layer.

In another embodiment, the matrix generated by the dimension-preserving convolutional neural network is a multi-adjacency matrix comprising an adjacency matrix for each relation of a set of relations, whereby the set of relations corresponds to output channels of the graph convolutional neural network.

In embodiments, the graph-based learning algorithm is based on a message-passing framework.

In a particular embodiment, the graph-based learning algorithm is based on a message-passing framework, wherein the message-passing framework is based on calculating hidden representations for each token and for each relation by accumulating weighted contributions of adjacent tokens for the relation. The hidden state for a token in the last layer of the graph convolutional neural network is obtained by accumulating the hidden states for the token in the previous layer over all relations.

In another particular embodiment, the graph-based learning algorithm is based on a message-passing framework, wherein the message-passing framework is based on calculating hidden states for each token by accumulating weighted contributions of adjacent tokens, wherein each relation of the set of relations corresponds to a weight.

In an aspect of the present invention, the contextualization layer comprises a recurrent neural network. The recurrent neural network may be an encoder neural network employing bidirectional gated rectified units.

In a particular embodiment, the recurrent neural network generates an intermediary representation of the sequence of tokens that is fed to a self-attention layer comprised in the contextualization layer.

In yet another embodiment the graph convolutional neural network employs a history-of-word approach that employs the intermediary representation.

According to an embodiment, a method for entering information provided as a natural language sentence to a computing device is provided, the natural language sentence comprising a sequence of tokens. The method comprises constructing a contextualized representation of the sequence of tokens by a recurrent neural network, processing an interaction matrix constructed from the contextualized representation by dimension-preserving convolution operators to generate output corresponding to a matrix, employing the matrix as a set of adjacency matrices in a graph convolutional neural network, and generating a label for each token in the sequence of tokens based on values of the last layer of the graph convolutional neural network.

The accompanying drawings are incorporated into the specification for the purpose of explaining the principles of the embodiments. The drawings are not to be construed as limiting the invention to only the illustrated and described embodiments or to how they can be made and used. Further features and advantages will become apparent from the following and, more particularly, from the description of the embodiments as illustrated in the accompanying drawings, wherein:.

<FIG> shows a natural language processing architecture <NUM> employing an end-to-end graph convolutional neural network according to an embodiment. The system comprises word encoder <NUM> configured to receive an input sequence of words or tokens, W = {w<NUM>, w<NUM>,. , wn}, where wi ∈ V with V being a vocabulary. W may form a sentence such as a declarative sentence or a question sentence. Word encoder <NUM> is configured to encode W in a set of vectors <IMG> that is provided to contextualization layer <NUM>. Contextualization layer <NUM> generates a contextualized representation of <IMG>. Output of contextualization layer <NUM> is inputted to dimension-preserving convolutional neural network <NUM> that produces a multi-adjacency matrix from the contextualized representation.

Multi-adjacency matrix M describes relationships between each pair of words in W. Multi-adjacency matrix M is employed by graph convolutional neural network <NUM> in a message-passing framework for the update between hidden layers, yielding a label for each token in the sequence of tokens.

Describing the architecture illustrated in <FIG> in more detail, the sequence of words or tokens <IMG> may be retrieved from a user via an input module receiving typed input or employing speech recognition.

Word encoder <NUM> embeds words in <IMG> in a corresponding set of vectors <IMG> = {x<NUM>, x<NUM>,. Using a representation of vocabulary <IMG> words are converted to vector representations, for example via one hot encoding that produces sparse vectors of length equal to the vocabulary. These vectors may further be converted to dense word vectors of much smaller dimensions. In embodiments, word encoding using, for example, fasttext, as described in <NPL>. In other embodiments, Glove, as described in <NPL>, is employed. In yet further embodiments, word encoder <NUM> comprises trainable parameters and may be trained along with the further neural networks shown in <FIG> which are explained below. In other embodiments, word encoder <NUM> generates representations of <IMG> on a sub-word level.

Contextualization layer <NUM>, comprising recurrent neural network (RNN) <NUM>, and, optionally, self-attention layer <NUM> is configured to contextualize encoded sequence <IMG>. Contextualization layer <NUM> contextualize <IMG> by sequentially reading each xt and updating a hidden state of RNN <NUM>. More particularly, RNN <NUM> acts as an encoder that generates in its hidden states an encoded representation of the sequence S. In embodiments, RNN <NUM> may be implemented as a bi-directional gated recurring unit (biGRU) as described in <NPL>.

In this embodiment, RNN <NUM> sequentially reads each vector from the input sequence S and updates hidden states according to <MAT> <MAT> <MAT> where <MAT> is the vector of hidden states, <MAT> is an updated gate vector, <MAT> is a reset gate vector, ∘ is the element-wise product, and σg and σh are activation functions. In embodiments, σg is a sigmoid function and σh is the hyperbolic tangent function. Hence, RNN <NUM> reads each element of the input sequence S sequentially and changes its hidden state by applying a non-linear activation function to its previous hidden state, taking into account the read element. The non-linear activation transformation according to Eqs. (1a)-(1c) includes an update gate, zt, that decides whether the hidden state is to be updated with a new hidden state, and a reset gate, rt, that decides whether the previous hidden state is ignored. When appropriately trained, the final hidden state of RNN <NUM> corresponds to a summary of the input sequence <IMG> and thus also to a summary of input sentence <IMG>.

According to the biGRU implementation, RNN <NUM> performs the updates according to equations (1a) to (1c) twice, once starting from the first element of S to generate hidden state ht, and once with reversed update direction of equations (1a) to (1c) , i.e. replacing subscripts t-<NUM> with t+<NUM>, starting from the last element of S to generate hidden state ht. Then, the hidden state of RNN <NUM> is the concatenation [ht; ht].

The learning parameters of RNN <NUM> according to equations <NUM>(a) to <NUM>(c) are Wz, <MAT>, Uz, Ur, <MAT>, and bz, bz, <MAT>. By employing both reading directions, ht takes into account context provided by elements previous to xt and ht takes into account elements following xt.

In a further step of processing, contextualization layer <NUM> may comprise self-attention layer <NUM>. In an embodiment, a self-attention layer according to Yang et al. is employed, as described in <NPL>. Specifically, in this embodiment the transformations <MAT> <MAT> <MAT> are applied to the hidden states of RNN <NUM>. <NUM>(a) to <NUM>(c), σh is the hyperbolic tangent, <MAT> is a learned matrix. Calculating <MAT> hence involves scoring the similarity of ut with ut' and normalizing with a softmax function.

Dimension-preserving convolutional neural network <NUM> employs transformed sequence <MAT> yielded from contextualization layer <NUM>. The present disclosure proposes employing an interaction matrix X constructed from v to infer multi-adjacency matrix M of a directed graph by convolutional neural network <NUM>.

From the transformed sequence <MAT>, interaction matrix <MAT> is constructed according to <MAT> where ";" is the concatenation operation. From X, which is often termed an interaction matrix, dimension-preserving convolutional neural network <NUM> constructs matrix <MAT> which corresponds to a multi-adjacency matrix for a directed graph. The directed graph describes relationships between each pair of words of <IMG>. Here, |<IMG>| is the number of relations considered. In an embodiment, |<IMG>| = <NUM>. In other embodiments the number of relations is |<IMG>| = <NUM>, <NUM>, <NUM>, <NUM>, or <NUM>. In this manner, dimension-preserving convolution operators of dimension-preserving convolutional layer <NUM> are employed to induce a number of relationships between tokens of the input sequence W.

According to a particular embodiment, dimension-preserving convolutional layer is defined as fi,j,k = max(wkXi,j, <NUM>), which corresponds to a 1x1 convolution layer, which dimension-preserving convolutional layer is described in <NPL>. In another embodiment, dimension-preserving convolutional layer <NUM> comprises a 3x3 convolution layer with a padding of <NUM>.

In a specific embodiment, the <NUM> x <NUM> convolution layer employs Dense Net Blocks, as described in <NPL>. According to this embodiment, information flow between all layers of the dimension-preserving convolutional layer is improved by direct connections from any layer to all subsequent layers, so that each layer receives the feature maps of all preceding layers as input. In a further specific embodiment, each Dense Net Block comprises an input layer, a batch normalization layer, a ReLU unit, a 1x1 convolution layer, followed by yet another batch normalization, a ReLU unit, a kxk convolution layer, and a dropout layer.

Finally, a softmax operator is employed on the rows of the obtained matrix to achieve training stability and to satisfy the normalization constraint for an adjacency matrix of a directed graph. The number of output channels of the dimension-preserving convolution layer, as described above, allows the system to induce a set of relations between the tokens of the input sequence. Hence, word encoder <NUM>, contextualization layer <NUM>, and dimension-preserving convolutional layer <NUM> form a graph construction pipeline, generating a latent graph defined by multi-adjacency matrix M from input sentence <IMG>.

Multi-adjacency matrix M constructed by dimension-preserving convolutional layer <NUM> is employed by graph convolutional neural network <NUM> that is trained with a graph-based learning algorithm. Graph convolutional neural network <NUM> implements graph-based learning on a graph with nodes each corresponding to a word of <IMG> (or token from <IMG>) and having directed links defined by multi-adjacency matrix M. Graph convolutional neural network <NUM> defines transformations that depend on a type and a direction of edges of the graph defined by multi-adjacency matrix M.

In more detail, graph convolutional neural network <NUM> comprises L hidden layers having hidden states <MAT>, l = <NUM>,. The model employed is based on a modification of a relational graph convolutional neural network to near-dense adjacency matrices, as described in <NPL>.

The model employed according to embodiments is a special case of a differential message-passing framework. Differential message passing is defined by <MAT> where <MAT> is the hidden state of node vi and d(l) is the dimensionality of the representation of hidden layer l. In the general definition according to equation (<NUM>), Mi is the set of incoming messages for node vi, which is often chosen to be identical to the set of incoming edges at node vi. Incoming messages contribute according to a weighting function gm applied to the hidden states <MAT> and <MAT>.

In embodiments of the invention, <MAT> with a weight matrix W as proposed in Kipf and Welling.

In embodiments, the propagation model employed by graph convolutional neural network <NUM> is given by <MAT> where <MAT> is the set of indices of the neighbors of node i under relation r ∈ R and ci,r is a problem-specific normalization constant. In embodiments, ci,r is learned. In other embodiments, ci,r is chosen in advance.

As defined exemplarily in Eq. (<NUM>), graph convolutional neural network <NUM> employs a message-passing framework that involves accumulating transformed feature vectors of neighboring nodes <MAT> through a normalized sum.

Furthermore, to ensure that the representation of a node in layer l + <NUM> depends on a corresponding representation at layer l, a single self-connection is added to each node. Hence, updates of the graph convolutional layers consists of evaluating Eq. (<NUM>) in parallel for every node in the graph. In addition, multiple layers may be stacked to allow for dependencies across several relational steps.

According to another embodiment, graph convolutional neural network <NUM> employs a novel message-passing scheme termed separable message passing. Separable message passing treats each relation with a specific graph convolution. Separable message passing employs a parallel calculation of |<IMG>| hidden representations for each node. The hidden state for a token in the last layer is obtained by accumulating the |<IMG>| hidden representations for the token in the previous layer. In more detail, the separable message passing is defined by <MAT> <MAT> where Eq. (6a) is evaluated for all r ∈ R. In Eq. (6a), cr. i is a normalization constant as described above, and <MAT> and <MAT> are learned weight matrices.

Another embodiment of graph convolutional neural network <NUM> further employs a history-of-word approach as described in <NPL>.

In more detail, each node of the graph convolutional neural network is represented by the result of the concatenation <MAT>.

Training of the system of <FIG> firstly comprises training the graph construction pipeline of contextualization layer <NUM> and dimension-preserving convolutional neural network <NUM>. Training contextualization layer <NUM> comprises training RNN <NUM> and, optionally, training self-attention layer <NUM>.

Training of the system of <FIG> secondly comprises training graph convolutional neural network <NUM>. Trained contextualization layer <NUM> and trained convolutional neural network <NUM> can be employed for diverse tasks so that pipelines for different tasks can share the parameters of contextualization layer <NUM> and convolutional neural network <NUM>, reducing expense for training the system of <FIG> for specific tasks.

For example, the system explained with reference to <FIG> may be trained for specific tasks such as node classification and sequence classification which are central for natural language processing. For the task of node classification, the relational graph convolutional neural network layers are stacked with a softmax activation function on the output of the last layer, and the following cross entropy loss is minimized on all labelled nodes, <MAT> where Y is the set of node indices and <MAT> is the k-th entry of the network output for the i-th node. The variable tik denotes the ground truth label as obtained from the training set, corresponding to a supervised training of the system. The model with architecture as described above is trained using stochastic gradient descent of <IMG>.

In other embodiments, the training set is only partially annotated so that the model is trained in a semi-supervised mode.

When training the model with architecture according to <FIG> for sequence classification, the output of the relational graph convolutional layer is taken as input to a sequence classification layer. In one embodiment, a bi-directional long short-term memory layer, as explained in <NPL>, is employed. In another embodiment, a fully connected layer is employed. The fully connected layer takes the result of a max pooling computed over the dimensions of the output node sequence. In this embodiment the categorical cross entropy of the predicted label associated with each sequence is minimized.

When trained, the system described with reference to <FIG> is able to infer relationships between individual elements of the input sequence. In particular, the model can leverage explicitly modelled sentence-range relationships and perform inference from it in a fully differential manner.

During experiments performed on the system illustrated in <FIG>, ablation tests were performed to measure the impact of the pre-processing by the sequence contextualization by RNN <NUM> and self-attention layer <NUM>.

To demonstrate the quality of the model described above with reference to <FIG>, the system was trained for the tasks of named entity recognition and slot filling, which are both instances of a node classification task.

The system was trained for the named entity recognition task employing the dataset CoNLL-<NUM>, <NPL>. Each word is tagged with the predefined labels of Person, Location, Organization, Miscellaneous or Other. The employed training set comprises <NUM> sentences corresponding to <NUM> tokens. The employed validation set comprises <NUM> sentences and <NUM> tokens. The test set comprises <NUM> sentences and <NUM> tokens. In this task, the BIO annotation standard is employed. In this notation, the target variable counts a total of <NUM> distinct labels.

As a second demonstration, the system was trained for the slot filling task with the ATIS-<NUM> corpus. The task is to localize specific entities in a natural-language-formulated request, i.e. the input sentence. Thus, given a specific semantic concept, e.g. a departure location, the presence of a specific entry corresponding to the semantic concept is determined and the corresponding entry is identified. The system is trained to detect the presence of a particular information ("slot") in the input sequence <IMG> and to identify the corresponding information. For example, in the sentence "I need to find a flight for tomorrow morning from Munich to Rome", Munich should be entered into the slot of a departure location and Rome should be entered into the slot of an arrival location. Also in this task, the BIO annotation standard is employed. The corpus counts a total of <NUM> unique tags created from the original annotations according to methods described in <NPL>, wherein each word of the sequence is associated with a unique tag.

Table <NUM> gives details on parameters employed for training for the named entity recognition task (NER) and the slot filling task (SF).

In training for each task, the cross entropy loss according to Eq. (<NUM>) is minimized using the Adam optimization algorithm as stochastic gradient descent algorithm. Furthermore, a greedy-decoding method is employed for both tasks. The probability of each token being the first and the last element of the answer span is computed using two fully connected layers applied to the output of a biGRU computed over this concatenation.

Table <NUM> presents accuracy results for the named entity recognition task of the systems of the present disclosure in comparison with state-of-the-art systems. Table <NUM> displays results indicated as E2E-GCN of an embodiment employing a graph convolutional neural network employing message passing according to Eq. (<NUM>), and results indicated as E2E-Separable-GCN of an embodiment employing a graph convolutional neural network employing separable message passing according to Eq. (6a) and (6b).

Furthermore, it should be remarked that a majority of approaches of the comparative cases of Table <NUM> rely on steps involving manual intervention of the programmer, whereas results E2E-GCN and results E2E-GCN do not involve such steps but provide an end-to-end pipeline.

Table <NUM> presents results of the systems E2E-GCN and E2E-Separable-GCN for the slot filling task for ATIS-<NUM> in comparison with results of state-of-the-art systems by the achieved F<NUM> score, which is a measure of the accuracy of the classification.

Table <NUM> shows performance of the embodiment trained for named entity recognition and the embodiment trained for slot filling in dependence on the number of relations |<IMG>|. Table <NUM> shows accuracy achieved for the named entity recognition task and the F<NUM>-score for the slot filling task employing the E2E-Separable-GCN embodiment with varying number of relations |<IMG>|. As is apparent, the optimal number of relations is problem-dependent, as for the named entity recognition task nine relations achieves optimal performance, while for the slot filling task the F<NUM>-score further increases with the number of considered relations.

<FIG> illustrates entries of the multi-adjacency matrix for the sentence <IMG> "please list all flights from Nashville to Memphis on Monday morning" generated according to principles explained above for the slot filling task. The subfigures of <FIG> print greyscale-coded matrix values of <MAT> forr = <NUM>,.

<FIG> visualizes, for the same sentence <IMG> as above, relationships produced by a state-of-the-art dependency parser, while <FIG> visualizes the relationships captured by a multi-adjacency matrix according to an embodiment. <FIG> shows a result of a state-of-the-art dependency parser by <NPL>, code <NUM>.

To produce <FIG> from adjacency matrix <MAT> encoding the sentence <IMG>, the pair of tokens {wi, wj} of maximum value such that <MAT> is selected. <FIG> thus demonstrates that the disclosed neural networks system is capable of extracting grammatically relevant relationships between tokens in an unsupervised manner.

In comparing <FIG>, a number of important differences of the disclosed approach to dependency parsers of the state-of-the-art are highlighted. Firstly, most of the dependency parsers of the state-of-the-art use queue stack systems to control the parsing process which imposes several restrictions as being based on a projective parsing formalism. In particular, this approach of state-of-the-art dependency parsers implies that a dependency can have only one head, represented as the arrow-head in <FIG>. In contrast, the approach disclosed here allows dependencies that have several heads.

Furthermore, due to the recurrent mechanism adopted by state-of-the-art neural dependency parsers, long-range dependencies between tokens are hardly ever represented, as is apparent from <FIG>. This limitation of the state-of-the-art approaches prevents contextual information being passed across the sentence, whereas, as apparent from <FIG>, the approach described here allows sentence length dependencies to be modelled.

In the model architecture, as described with reference to <FIG>, these long range dependencies are propagated by the graph convolution model across the sentence, partially explaining the achieved improvements over state-of-the-art models.

Further embodiments will now be described in detail in relation to the above and with reference to <FIG> and <FIG>, which are functional block diagrams illustrating computer-implemented methods <NUM> and <NUM>, respectively.

Method <NUM> illustrated in <FIG> comprises training <NUM> the graph construction pipeline of RNN <NUM>, self-attention layer <NUM>, and dimension-preserving convolutional layer <NUM>.

Method <NUM> further comprises training <NUM> graph convolutional neural network <NUM> for a specific task, such as node classification or sequence classification. Training <NUM> graph convolutional neural network <NUM> includes evaluating a cross entropy loss such as cross entropy loss <IMG> from Eq. (<NUM>) for a training set and adjusting the hyperparameters of graph convolutional neural network <NUM>, for example by stochastic gradient descent to optimize <IMG>. Accuracy of the graph convolutional neural network <NUM> as currently trained may be evaluated on a validation set. Training may be stopped when the error on the validation dataset increases, as this is a sign of overfitting to the training dataset.

In embodiments, the graph construction pipeline and the graph convolutional neural network <NUM> are trained jointly employing the training set and the validation set.

In an embodiment, the specific task is database entry. For this specific task the training set may comprise natural language statements tagged with the predetermined keys of a database. In another embodiment, the specific task is filling out a form provided on a computing device. For this specific task the training set may arise from a specific domain and comprise natural language statements corresponding to a request. The requests may correspond to information required by the form. In the training set, words in a natural language statement may be tagged with a semantic meaning of the word in the natural language statement.

Training graph convolutional neural network <NUM> for a second specific task only requires repeating step <NUM> for the second specific task while employing the same trained pipeline of RNN <NUM>, self-attention layer <NUM>, and dimension-preserving convolutional layer <NUM>.

Method <NUM> illustrated in <FIG> relates to a method for entering information provided in a natural language sentence W to a computing device. More particularly, information provided in the natural language sentence W may be entered into a database stored on the computing device or may be entered in a form provided on the computing device.

Method <NUM> comprises employing neural networks trained according to the method <NUM> explained above. Method <NUM> includes receiving <NUM> the natural language sentence <IMG> from a user. The natural language sentence may be entered by any known input means, for example, by typing or via speech.

At step <NUM>, the natural language sentence <IMG> is encoded in a corresponding sequence of word vectors <IMG>, for example by word encoder <NUM> as explained above with reference to <FIG>.

At step <NUM>, a sequence of contextualization steps is performed to word vectors <IMG> to produce a contextualized representation of the natural language sentence. Contextualization <NUM> may employ feeding the word vectors to contextualization layer <NUM> as explained with reference to <FIG>.

At step <NUM> the contextualized representation is put through a dimension-preserving convolutional neural network, such as dimension-preserving convolutional neural network <NUM>, to construct multi-adjacency matrix M comprising adjacency matrices for a set of relations <IMG>.

At step <NUM>, the generated multi-adjacency matrix is processed by a graph convolutional neural network such as graph convolutional neural network <NUM>, described with reference to <FIG>. In embodiments, the employed graph convolutional neural network may employ message passing according to Eq. (<NUM>) or separable message passing according to Eq. (<NUM>).

Method <NUM> finally comprises step <NUM> of employing the output of the last layer of the graph convolutional neural network to enter a token from the natural language sentence in a database employing a label generated by the graph convolutional neural network as a key. In this embodiment, graph convolutional neural network <NUM> has been trained with a training set tagged with the keys of the database.

Another embodiment of the present invention is practiced when a user has opened a form such as a web form of an HTTP site. Entries of the web form are employed to identify slots to be filled by information contained in the natural language sentence corresponding to a request that may be served by the HTTP site. In this embodiment, method <NUM> includes step <NUM> of identifying the presence of one or more words of the natural language that correspond to entries required in the form, and filling one or more slots of the form with one or more identified words, respectively.

For example, using again the exemplary case of listing flights, as contained in the ATIS-<NUM> corpus, a web form may provide entries for a departure location and an arrival location and method <NUM> may comprise detecting the presence of a departure location and/or an arrival location in the natural language sentence, and filling the web form with the corresponding word from <IMG>.

The above-mentioned systems, methods and embodiments may be implemented within an architecture such as that illustrated in <FIG>, which comprises server <NUM> and one or more client devices <NUM> that communicate over a network <NUM> (which may be wireless and/or wired), such as the Internet, for data exchange. Server <NUM> and the client devices <NUM> each include a data processor <NUM> and memory <NUM>, such as a hard disk. Client devices <NUM> may be any devices that communicate with server <NUM>, including autonomous vehicle 902b, robot 902b, computer 902d, or cell phone 902e. More precisely, in an embodiment, the system according to the embodiments of <FIG> and <FIG> may be implemented by server <NUM>.

Server <NUM> may receive a training set and use processor <NUM> to train the graph construction pipeline <NUM>-<NUM> and graph convolutional neural network <NUM>. Server <NUM> may then store trained parameters of the graph construction pipeline <NUM>-<NUM> and graph convolutional neural network <NUM> in memory <NUM>.

For example, after graph construction pipeline <NUM>-<NUM> and graph convolutional neural network <NUM>, client device <NUM> may provide a received natural language statement to server <NUM>, which employs stored parameters of graph construction pipeline <NUM>-<NUM> and graph convolutional neural network <NUM> to determine labels for words in the natural language statement. Server <NUM> may then process the natural language statement according to the determined labels, e.g. to enter information in a database stored in memory <NUM> or to fill out a form and provide information based on the filled out form back to client device <NUM>. Additionally or alternatively, server <NUM> may provide the labels to client device <NUM>.

Some or all of the method steps described above may be implemented by a computer in that they are executed by (or using) a processor, a microprocessor, an electronic circuit or processing circuitry.

The embodiments described above may be implemented in hardware or in software. The implementation can be performed using a non-transitory storage medium such as a computer-readable storage medium, for example a floppy disc, a DVD, a Blu-Ray, a CD, a ROM, a PROM, and EPROM, an EEPROM or a FLASH memory. Such computer-readable media can be any available media that can be accessed by a general-purpose or special-purpose computer system. Generally, embodiments can be implemented as computer program products with a program code or computer-executable instructions, the program code or computer-executable instructions being operative for performing one of the methods when the computer program product runs on a computer. The program code or the computer-executable instructions may, for example, be stored on a computer-readable storage medium.

In an embodiment, not according to the claimed invention, a storage medium (or a data carrier, or a computer-readable medium) comprises, stored thereon, the computer program or the computer-executable instructions for performing one of the methods described herein when it is performed by a processor.

Claim 1:
A system for entering information provided in a natural language sentence to a database or to a form provided on a computing device, the natural language sentence comprising a sequence of tokens (W), the system comprising:
an encoder neural network (<NUM>) configured to encode the sequence of tokens (<IMG>) in a set of vectors (S);
a contextualization layer (<NUM>) configured to generate a contextualized representation of the sequence of tokens (W) from the set of vectors (S);
a dimension-preserving convolutional neural network (<NUM>) configured to employ the contextualized representation to generate output corresponding to a matrix (M); and
a graph convolutional neural network (<NUM>) configured to employ the matrix (M) as a set of adjacency matrices,
wherein the system is further configured to generate a label for each token in the sequence of tokens (<IMG>) based on hidden states for the token in the last layer of the graph convolutional neural network (<NUM>),
wherein the encoder neural network (<NUM>), the contextualization layer (<NUM>), and the dimension-preserving convolutional neural network (<NUM>) form a graph construction pipeline,
wherein the matrix (M) defines a graph structure which is a latent variable of the graph construction pipeline,
wherein the system further comprises:
a database interface (<NUM>) configured to enter a token from the sequence of tokens (<IMG>) into the database, wherein entering the token comprises employing the label of the token as a key, wherein the graph convolutional neural network (<NUM>) is trained with a graph-based learning algorithm for locating, in the sequence of tokens (<IMG>), tokens that correspond to respective labels of a set of predefined labels, or
a form interface (<NUM>) configured to enter, into at least one slot of the form provided on the computing device, a token from the sequence of tokens (<IMG>), wherein the label of the token identifies the slot, wherein the graph convolutional neural network (<NUM>) is trained with a graph-based learning algorithm for tagging tokens of the sequence of tokens (<IMG>) with labels.