Markov-based sequence tagging using neural networks

Features are disclosed for using a neural network to tag sequential input without using an internal representation of the neural network generated when scoring previous positions in the sequence. A predicted or determined label (e.g., the highest scoring or otherwise most probable label) for input at a given position in the sequence can be used when scoring input corresponding to the next position the sequence. Additional features are disclosed for training a neural network for use in tagging sequential input without using an internal representation of the neural network generated when scoring previous positions the sequence.

BACKGROUND

Computing devices can be used to process a user's spoken commands, requests, and other utterances into written transcriptions. Models representing data relationships and patterns, such as functions, algorithms, systems, and the like, may accept audio data input (sometimes referred to as an input vector), and produce output (sometimes referred to as an output vector) that corresponds to the input in some way. In some implementations, a model is used to generate a probability or set of probabilities that the input corresponds to a particular language unit (e.g., phoneme, phoneme portion, triphone, word, n-gram, part of speech, etc.). For example, an automatic speech recognition (“ASR”) system may utilize various models to recognize speech, such as an acoustic model and a language model. The acoustic model is used to generate hypotheses regarding which words or subword units (e.g., phonemes) correspond to an utterance based on the acoustic features of the utterance. The language model is used to determine which of the hypotheses generated using the acoustic model is the most likely transcription of the utterance.

ASR systems commonly utilize Gaussian mixture models/hidden Markov models (“GMMs/HMMs”) to tag language units in sequences of natural language input. However, artificial neural networks may also be used. Scores in neural-network-based ASR systems are obtained by multiplying trained weight matrices, representing the parameters of the model, with vectors corresponding to feature vectors or intermediate representations within the neural network. This process is referred to as a forward pass. The output can be used to determine which language unit most likely corresponds to the input feature vector. Due to the sequential nature of spoken language, the correct output for a feature vector for a particular frame of audio data may depend upon the output generated for a feature vector for the sequentially previous frame of audio data. Some systems incorporate sequential aspects of language by using recurrent neural networks (“RNNs”). RNNs can produce output based in part on sequentially previous frame by accepting, as input, an internal representation of the RNN for the sequentially previous frame in addition to a feature vector for the current frame.

DETAILED DESCRIPTION

Introduction

The present disclosure is directed to sequence tagging with artificial neural networks using a Markov-model-based approach. Generally described, sequence tagging is often used in natural language processing, where input data corresponds to sequences of language units (e.g., phonemes, n-phones, words, n-grams, sentences, etc.). Each position or “token” of the sequence is “tagged” with a “label” corresponding to a specific language unit (e.g., a specific phoneme, word, part of speech, etc.). Although a classification approach may be used to tag individual tokens with corresponding labels, classification systems do not take into account the temporal and sequential dependencies inherent in natural language. Rather, classification systems typically tag individual tokens independently of other tokens in an input signal.

Some conventional systems use artificial neural networks as structured predictors to decode or tag sequences of tokens while taking into account the sequential nature of the input data. An artificial neural network, also referred to simply as a neural network, is a network containing at least one computational unit, known as a neuron or node, interconnected to other computational units. Conceptually, the nodes may be thought of as calculating output values as a function of a plurality of different input values. Typically, neural networks have multiple (e.g., two or more) layers of nodes, and nodes of adjacent layers may be connected to each other. A neural network may contain several layers, including an input layer, an output layer, and any number of intermediate or “hidden” internal layers. In speech recognition, the input layer may consist of a set of parameters (e.g., a feature vector) for a given time instance, such as a frame of audio data. A distribution of probabilities over all possible labels for the frame may be obtained by doing a forward pass. The forward pass involves multiplying large matrices representing the connection weights between nodes of adjacent layers by vectors corresponding to one or more feature vectors (from the input layer) or hidden representations (from the subsequent hidden layers).

One type of neural network used in structured prediction is a recurrent neural network (“RNN”). An RNN is a specific type of neural network that preserves an internal state (e.g., a hidden layer) of the neural network for use in tagging subsequent tokens in a sequence. The internal state preserved from processing input data for one position in the sequence can be input back into the RNN to process input data for a subsequent position in the sequence, thereby providing sequential information earlier in the sequence being decoded/tagged. For example, when an RNN is used to decode audio input in an automatic speech recognition (“ASR”) system, the preserved internal state is based on all previous positions in the sequence, rather than some finite number of previous positions, and can therefore capture long (potentially infinite) dependencies within natural language input. However, the training of RNNs can be more complex and less scalable than other forms of non-recurrent neural networks because the internal representations generated during processing of prior positions in a sequence must be provided during training. Accordingly, training of RNNs typically requires processing training data in the proper sequence so that the internal representations can be generated and preserved for use in processing input for subsequent positions. In addition, using intermediate representations of inputs for prior positions may not completely or adequately capture the predicted label for the prior position in the sequence.

Some aspects of the present disclosure relate to using a neural network to tag sequential input without using an internal representation of the neural network generated when scoring previous positions in the sequence. Instead, a predicted or determined label (e.g., the highest scoring or otherwise most probable label) for input at a finite, predetermined number of previous positions in the sequence can be used when scoring input corresponding to a subsequent position in the sequence (e.g., the label for only the immediately preceding position in the sequence can be used when scoring input for any particular position in the sequence). Accordingly, the neural network does not need to be an RNN, but may instead by any neural network that is configured to operate on a feature vector corresponding to a position in a sequence plus additional data regarding a predicted or determined label for the previous position in the sequence. In this way, the neural network may be used in a Markov-model-based decoding process because the neural network obeys the Markov assumption (the probability distribution of future states depends only on the present state and not on the sequence of events that precede the present state). For example, a deep neural network (“DNN”) may be trained to calculate, for an input feature vector corresponding to a particular time instance or frame of audio data, a local probability distribution for all possible labels using the predicted label for the previous time instance or frame of audio data in an input signal. In contrast, an RNN would calculate a probability distribution using an intermediate representation of the RNN from the previous time instance or frame of audio data from the input signal. The intermediate representation of the RNN may be based on any number of previous time instances because no conversion to a single predicted label has occurred. Accordingly, the RNN would not obey the Markov assumption.

Additional aspects of the present disclosure relate to using a neural network obeying the Markov assumption in a Viterbi decoding process. Generally described, a Viterbi decoding process involves calculating, for each position in a sequence, a separate local distribution of probabilities for all possible labels based on any or all possible labels for the previous position in the sequence. Repeated calculations of such local distributions for each position in the sequence can be used to generate a graph of results (e.g., a lattice or trellis), where the connections between states at different positions of the sequence each correspond to a probability that a specific label at one position follows a specific label at the immediately preceding position. The highest-scoring path (or n-best scoring paths) through the graph can be selected and provided to downstream processes and consumers. Viterbi decoding processes are commonly used in hidden Markov model (“HMM”) based natural language processing.

Further aspects of the present disclosure relate to training neural networks for use in sequence tagging without requiring each individual training data input (e.g., each feature vector corresponding to an individual sequential position) to be processed sequentially. Training of conventional RNNs requires input of not just the training data feature vector for a particular position of the sequence, but also an internal RNN representation from the prior position in the sequence. Accordingly, training data must be generated sequentially to obtain the internal RNN representations for each training data feature vector, or the RNN must be sequentially trained so that the internal RNN representations for previous positions can be determined during training. However, because Markov-based neural networks rely only on the label predicted for the previous position in the sequence, the training data may be generated automatically so long as the correct label for each position in the sequence is known. In addition, training of the neural network may proceed in any order, because each training data feature vector and correct previous label are known ahead of time, and the correct previous label does not need to be generated by processing the sequentially previous training data feature vector. In this way, Markov-based neural networks can be trained on subsets of training data, training data provided in random or non-sequential order, etc.

Still further aspects of the present disclosure relate to various neural network architectures for Markov-based neural networks. In some embodiments, a neural network may be designed to accept, as input, a feature vector for a particular position in a sequence, and data indicating the predicted label for the previous position in the sequence. For example, the data indicating the predicted label for the previous position may be an array with an element for each possible label, where each element is set to 0 except the element corresponding to the predicted previous label, which is set to 1. In other embodiments, a neural network may be designed accept, as input, a feature vector for a particular position in the sequence without any additional data. The neural network can then generate multiple distributions, such as an array including a separate distribution for each possible previous label. In further embodiments, a feature vector for a particular position in the sequence may be input to multiple neural networks, such as a separate neural network for each possible previous label.

Although the examples and embodiments described herein will focus, for the purpose of illustration, on using neural networks to process natural language input in an automatic speech recognition system (e.g., using DNNs as acoustic models or language models) or a natural language understanding system (e.g., using DNNs to perform named entity recognition), one skilled in the art will appreciate that the techniques described herein may be applied to other processes, methods, or systems. For example, the techniques may be used with other types of neural networks, with neural networks used for purposes other than automatic speech recognition or natural language understanding, etc. Various aspects of the disclosure will now be described with regard to certain examples and embodiments, which are intended to illustrate but not limit the disclosure.

Example Neural Network

FIG. 1depicts an illustrative neural network100configured to generate output (e.g., a distribution of label probabilities) for a position in a sequence using input data indicating a label or predicted label for a sequentially previous position in the sequence. The neural network100includes an input layer102, any number of internal hidden layers104, and an output layer106.

In one specific, non-limiting example, the input layer may correspond a feature vector120extracted from an input signal, such as a frame of audio data, a word from a sentence, or the like. Illustratively, the feature vector120may be named xt, where t corresponds to a particular time instance or other position within a sequence of positions. In addition, the input may include previous label data122that corresponds to, or is derived from, output generated by the neural network100for a feature vector of a previous position in the sequence. For example, the previous label data122may be named st-1, where t−1 corresponds to the time instance or other position immediately preceding t in the sequence. The previous prediction data122can indicate the label that was predicted for the previous frame, word, etc. The output layer106may correspond to a local probability distribution over all possible labels for the current position within the sequence. A forward pass through the neural network100may be performed to process the input through the hidden layers104to produce the output, which may be named yt. Although the neural network100shown inFIG. 1includes 2 hidden layers, there may be any number of hidden layers104. In some embodiments, there may be between three and seven hidden layers104. Each layer of the neural network100may consist of any number of nodes. In some embodiments, one or more layers may include tens, hundreds, or thousands of different nodes corresponding to different trainable parameters of the neural network. In many cases, a neural network may have substantially more parameters (e.g., two to ten times more parameters) than a traditional GMM/HMM model, thereby providing a greater degree of sensitivity and control.

In some embodiments, as shown, the previous label data122may be generated as part of a decoding process110. For example, an ASR or NLU system may be decoding a sequence of words. The system may have used the neural network100to generate a probability distribution yt-1for a feature vector corresponding to a position at time t−1 within an input signal. The system may then proceed to use the neural network100to generate a probability distribution ytfor the feature vector corresponding to the next position at time t within the input signal. Rather than input the previously determined probability distribution yt-1or some internal representation of the neural network at time t−1, as would be done with an RNN, the decoding process110may instead use the specific label was assigned to the previous position at t−1. Illustratively, the process110may indicate the label by providing previous label data122as an array of elements, each element corresponding to a possible label. The element corresponding to the label for the previous position at t−1 may be set to some predetermined value (e.g., 1), while the elements corresponding to the other labels may be set to some default value (e.g., 0). In this way, the neural network100may account for the sequential nature of the input data (e.g., the feature vector xt) by determining the probability distribution over all labels for the position at time t based on the label for the previous position at time t−1. In addition, because the previous label data122indicates the previous label without indicating how the previous label was determined and without indicating any earlier labels (e.g., labels at time t−2 or earlier), the neural network100obeys the Markov assumption and can be used as a Markov model in Markov-model-based sequence tagging.

FIG. 2is a decoding diagram200illustrating the use of a neural network in Markov-model-based sequence tagging, also referred to herein as decoding. The horizontal axis202of the decoding diagram200corresponds to the sequential positions x1, x2, x3. . . xnof an input signal over time from left (earlier) to right (later). The vertical axis204of the decoding diagram200corresponds to the possible labels y1, y2, y3, and y4that may be assigned to each positions in the sequence. Each of the nodes in the decoding diagram200corresponds to a particular state in Markov-model-based decoding. For example, state210corresponds to position x2in the sequence when the previous position x1has been labeled y1. Each connection between two different states corresponds to a probability that the later state followed the earlier state. For example, connection208between states210and224corresponds to the probability that, at position x3, the previous position x2has been labeled y3.

In one illustrative example, a Markov-model-based decoding process may determine the part of speech for words at the positions in the sequence represented on the horizontal axis. The sequence of words may be “Expensive bait works better than cheap bait.” In this example, the word at position x2is “bait,” which can be either a noun or a verb depending upon the context. In particular, if the word at the immediately preceding position x1is an adjective (e.g., label y1), then it may be highly probably that “bait” is being used as a noun (e.g., “Expensive bait works better . . . ”) and should be labeled as such (e.g., label y3). However, if the word at the immediately preceding position x1is an adverb (e.g., label y2), then it may be highly probably that “bait” is being used as a verb (e.g., “Quickly bait the hook . . . ”) and should be labeled as such (e.g., label y4).

The decoding process can include calculating a local distribution of probabilities over all possible labels for x2when the previous word at x1has been labeled an adjective (e.g., the word “expensive” has been labeled y1). The decoding process can use a neural network, such as the neural network100inFIG. 1where the current position t=2. The input xtmay include the word at x2, “bait.” The input st-1may indicate that the previous label at x1was an adjective (label y1). The neural network100may then generate the local distribution ytfor t=2. In the decoding diagram200, the local distribution is represented as a set of connections206between state210at position x2and each state220,222,224and226at position x3. State210corresponds to label y1(e.g., that the word at the previous position x1in the sequence—“expensive”—is an adjective). The connections206to states220,222,224and226correspond to the probabilities that the word at position x2(“bait”) is an adjective, adverb, noun, or verb, respectively, based on the immediately preceding word at position x1being an adjective (label y1). Because “expensive” is indeed an adjective in this example, the connection208to state224may have the highest probability or score, indicating that the word “bait” should be labeled as a noun; the connections to each other state220,222and226may have a relatively low probability or score.

The decoding process can include calculating a local distribution of probabilities over all possible labels for x2for each remaining possible previous label for x1. For example, the decoding process can use the neural network100to generate a second local distribution ytfor t=2 using the input from x2and also previous label data102indicating that the label for x1was y2. In this example, the local distribution can be represented as a set of connections from state212to each of states220,222,224and226. As described in greater detail below, the process can be repeated for each remaining possible label y3and y4for x1, or from some subset thereof.

Process for Sequence Tagging Using Neural-Network-Based Markov Models

FIG. 3depicts an illustrative process300for sequence tagging using neural-network-based Markov models. A computing device may execute the process300to tag sequences of data, such as natural language units (e.g., phonemes, n-phones, words, n-grams, sentences, etc.) in an input signal (e.g., audio data, text, etc.). Advantageously, the process300includes processing sequential input data using a neural network trained to produce, for individual positions in the sequence, local probability distributions over a set of possible labels based at least partly on a label or predicted label for the previous position in the sequence.

The process300begins at block302. The process300may be implemented by a physical computing system, which may include one or more physical computing devices. The computing devices may implement one or more modules or components that perform the process300, such as hardware components or a combination of hardware and software components. Individual computing devices may include one or more hardware processors operative to communicate with a computer-readable memory, perform computer-executable instructions, receive and manipulate data, and produce output. The output may be provided for display on a video display, stored in a computer-readable storage medium, transmitted to another computing device over a communication network, or the like.

In one specific, non-limiting example, the process300may be embodied in a set of executable program instructions stored on one or more non-transitory computer-readable media, such as one or more disk drives or solid-state memory devices, of a physical computing system. When the process300is initiated, the executable program instructions can be loaded into memory, such as RAM, and executed by one or more hardware processors of the physical computing system. In some embodiments, the computing system may include multiple (e.g., two or more) computing devices, such as servers, and the process300or portions thereof may be executed by multiple servers, serially or in parallel.

At block304, the computing system executing the process300can receive sequential data to be tagged. In the example described above, the sequential data is a sentence including multiple words. The example above is illustrative only, and is not intended to be limiting. The neural-network-based Markov models and corresponding processing described herein may be used on any sequential input data, such as audio data of a user utterance, phoneme sequences produced by an ASR system, etc.

At block306, the computing system executing the process300can begin processing the input data by extracting features for a position in the sequence. In the example described above, a feature vector may be generated for the second position in the sequence, and may include the word “bait” (the first position in the sequence, corresponding to the word “expensive,” may have been processed in a previous iteration). Other features may be included in the feature vector (e.g., the previous word, the next word, etc.). The particular features and feature vectors described herein are illustrative only; many other types of features and feature vectors may be used.

At block308, the computing system executing the process300can determine which label corresponds to the previous position. In the example above, the previous position corresponds to the word “expensive,” and the predicted label was “adjective.” The label may be determined by examining the neural network output generated for the previous position. If the output includes a probability distribution over all possible labels, then the highest scoring label may be selected. In some embodiments, as shown inFIG. 1, an additional feature may be provided as input for the current position. The additional feature st-1may be an array with elements corresponding to each possible label. The element for the most probable label for the previous position (e.g., “adjective” in this example) can be set to some indicative value (e.g., 1), and the elements for the remainder of the labels can be set to some other value (e.g., 0).

At block310, the computing system executing the process300can process the features for the current position in the sequence by using neural network to generate local probability distribution over all possible labels. The neural network takes into account the label for the previous position, provided as described above or in some other manner.

At block312, the computing system executing the process300can determine whether there are additional predictions for the label corresponding to the previous position. If so, the process300can return to block308to generate a local distribution for the current position based on additional label prediction(s) for the previous position. In some embodiments, the process300can return to block308for each possible label that may be assigned to the previous position, regardless of the probability or score determined for the label when processing the previous position. For example, a decoding process may determine probabilities for each possible combination of labels for the sequence. The top-scoring path(s) can then be selected using, e.g., a Viterbi process. In some embodiments, the process300can return to block308for only a subset of possible labels (e.g., one or more, but fewer than all). For example, the top n-scoring labels may be selected, where n is some number or ratio. As another example, each label with a score exceeding some predetermined or dynamically determined threshold may be chosen, the process300can return to block308for each of those labels.

In some embodiments, the process300may not return to block308for other possible prior labels. Rather, blocks308and310may be executed in parallel (or some other asynchronous manner) for each possible prior label, or some subset thereof. For example, the neural networks illustrated inFIGS. 5 and 6may be used to generate local probability distributions for multiple possible prior labels in parallel, thereby reducing the total processing time and improving performance.

At block314, the computing system executing the process300can determine whether there are additional positions in the sequence to be processed. If so, the process300can return to block306for each remaining position.

At block316, the best scoring sequence or sequences of labels may be chosen. As described above, a Viterbi process may be used to select the best scoring sequence or n-best sequences. In some embodiments, other methods may be used to selected the best scoring label sequence(s).

Process for Training Neural-Network-Based Markov Models

FIG. 4depicts an illustrative process400for training a neural network for use in Markov-based decoding. Advantageously, the process400includes the generation of training data that may be used to train the neural network without requiring training to proceed in a predetermined sequence. Instead, each training data input vector (or other form of input data) may include features for a particular position in a sequence and also the correct label for the preceding position in the sequence. Accordingly, training data for a later position in a sequence may be used to train the neural network prior to (or in the absence of) training data for the immediately preceding position in the sequence.

The process400begins at block402. The process400may be implemented by a physical computing system, which may include one or more physical computing devices. The computing devices may implement one or more modules or components that perform the process400, such as hardware components or a combination of hardware and software components. In one specific, non-limiting example, the process400may be embodied in a set of executable program instructions stored on one or more non-transitory computer-readable media, such as one or more disk drives or solid-state memory devices, of a physical computing system. When the process400is initiated, the executable program instructions can be loaded into memory, such as RAM, and executed by one or more hardware processors of the physical computing system. In some embodiments, the computing system may include multiple (e.g., two or more) computing devices, such as servers, and the process400or portions thereof may be executed by multiple servers, serially or in parallel.

At block404, the computing system executing the process400can obtain features for a particular position within a sequence. For example, the process400may be used to train a neural network using the example sentence described above. In this example, the computing system may obtain features for the second position, corresponding to the word “bait.”

At block406, the computing system executing the process400can obtain the known correct label for the current position. In the example above, the label is “noun.”

At block408, the computing system executing the process400can obtain a reference label for the position immediately preceding the current position, such as the known correct label for the previous position. In the example, above, the label is “adjective.” By using the known correct label for the previous position, the neural network can be trained to generate correct results for the current position without basing the results on an erroneous label for the prior previous position. In some embodiments, the computing system executing the process400may obtain a label for the previous position that is not known to be correct. Instead, a prediction for the previous label in the sequence may be generated (e.g., by using the neural network to generate the prediction based on training data for the previous position in the sequence). This predicted label may not be verified as being the known correct or “gold-standard” label, but may nevertheless be used during training for the current position. For example, the computing system executing the process400may process training data in one or more iterations using the known correct previous labels for each position in the sequence. The computing system may use back propagation to adjust the parameters of the neural network to produce the known correct results for the current position. After one or more iterations of this process, the computing system may then generate reference labels for prior positions in the training data (e.g., using the neural network to score those prior positions). The unverified or noisy data may then be used to train the subsequent positions in the sequence, and the neural network may continue to be trained in this manner as desired. In this way, any bias associated with always using the known correct prior label can be minimized or reduced.

At block410, the computing system executing the process400can process the features for the current position in the sequence to generate a local probability distribution based, at least in part, on the correct label for the previous position in the sequence.

At block412, the computing system executing the process400can train the neural network to correctly predict the known correct label for the current position. In some embodiments, the neural network may be trained to correctly predict the known correct label for the current position using a technique known as back propagation. In back propagation, parameters of the neural network (e.g., the matrices by which layers of the neural network are multiplied during a forward pass) are adjusted so that the neural network better discriminates between incorrect and correct labels.

At decision block414, the computing system executing the process400can determine whether there is additional training data to process. If not, the process400can end at block418. If there is additional training data, the process400can proceed to block416, where the computing system may repeat the training process for any additional training data input without being required to process the training data input in a predetermined sequence, which would not be possible using an RNN. For example, the process can be repeated for any previous or subsequent position in the current sequence in any order, for any position in any other sequence, etc. Individual training data inputs may be selected according to some predetermined or dynamically determined schedule, or they may be randomly selected.

Additional Embodiments

FIG. 5depicts another embodiment of a neural network500hat may be used in Markov-based sequence tagging. The neural network500includes an input layer502, any number of internal hidden layers504, and an output layer506. However, the neural network500is different than the neural network100described above because the neural network500inFIG. 5does not necessarily accept previous label data as input. Instead, the neural network500can accept an input feature vector for a particular position in a sequence and generate a separate local probability distribution for each possible label that may be applied to the previous position in the sequence. For example, the neural network500may take an input feature vector xt, and produce an array of local probability distributions, such as yt[1]512to yt[n]522(or yt[0] to yt[n−1], etc.), where n corresponds to the number of possible labels for position xt-1of the sequence.

FIG. 6depicts another embodiment of a neural network600that may be used in Markov-based sequence tagging. Conceptually, the neural network600may be thought of as multiple (e.g., two or more) different neural networks, and the feature vector xtmay be input into each network separately. The neural network600shown inFIG. 6includes networks610-620corresponding to each possible label for a previous position in the sequence. Each of the individual neural networks may be trained to produce probability distributions for a given position based on a different label corresponding to the previous position in the sequence. For example, neural network610may accept an input feature vector xt602, and process the feature vector though any number of internal hidden layers604to produce an output distribution606. The particular output distribution yt[1]612may be based on an assumption regarding the label for the previous position in the sequence (e.g., “adjective”). A different neural network620may produce an output distribution yt[n]622based on an assumption that the label for the previous position in the sequence was a different label (e.g., “adverb”). During training of the neural network600, only the particular neural network610-620that corresponds to the correct output may be modified using back propagation. In some embodiments, additional networks610-620may be modified accordingly.

Terminology