Semantic model for tagging of word lattices

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for tagging during speech recognition. A word lattice that indicates probabilities for sequences of words in an utterance is obtained. A conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear is obtained. The word lattice and the conditional probability transducer are composed to construct a word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words. The word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words is used to generate a transcription that includes the words in the utterance and the semantic tags for the words.

TECHNICAL FIELD

This document generally relates to speech recognition.

BACKGROUND

Automated speech recognition may be used to recognize words spoken by users. For example, a voice command enabled device may generate a transcription of what a user says and then determine whether the transcription includes any words that correspond to a voice command.

SUMMARY

This specification describes techniques, methods, systems, and other mechanisms for tagging words during speech recognition. In general, a semantic tagger may insert tags into a word lattice, such as a word lattice produced by a real-time large vocabulary speech recognition system. For example, the phrase “San Francisco” may appear in a path of a word lattice and tagged with metadata of “<cities>” before “San” and metadata of “</cities>” after “Francisco.”

Benefits of such a tagger may include the ability to rescore speech recognition hypotheses based on this metadata which may lead to better accuracy in automated speech recognition, as well as providing rich annotations to clients downstream which may lead to additional functionality of the clients using the annotations. The tagging may be performed for spoken search queries and voice commands, and tagging may be useful for building an intelligent assistant. For example, the tags may indicate which words correspond to triggers for commands and which words correspond to user provided parameters for commands.

The tagging may be performed by distilling a pre-existing very large named entity disambiguation (NED) model into a lightweight tagger. This may be accomplished by constructing a joint distribution of tagged n-grams from a supervised training corpus and then deriving a conditional distribution for a given lattice. The tagging may take a generative approach, modeling a joint distribution of n-grams with semantic tags and later deriving a conditional distribution for a given lattice. In another example, tagging may be performed by using a conditional distribution of tagged n-grams constructed directly from a supervised training corpus.

In a general aspect, a method for obtaining, from an automated speech recognizer, a word lattice that indicates probabilities for sequences of words in an utterance, obtaining a conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear, composing the word lattice and the conditional probability transducer to construct a word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words, and using the word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words to generate a transcription that includes the words in the utterance and the semantic tags for the words.

Implementations may include one or more of the following features. For instance obtaining, from an automated speech recognizer, a word lattice that indicates probabilities for sequences of words in an utterance may include providing an utterance to the automated speech recognizer that does not semantically tag words and receiving, from the automated speech recognizer, the word lattice that indicates probabilities for sequences of words in an utterance, where the word lattice does not include semantic tags for words in the word lattice. Obtaining a conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear may include obtaining the conditional probability transducer from a language model that is trained on a corpus of text that includes sequences of words and semantic tags for the words.

Obtaining a conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear may include obtaining joint probabilities for sequences of the words and the semantic tags for the words, obtaining marginal probabilities for sequences of the words, and obtaining the condition probability transducer from the joint probabilities and the marginal probabilities. Obtaining joint probabilities for sequences of the words and the semantic tags for the words may include obtaining joint probabilities from a language model that includes joint probabilities corresponding to a corpus of text that includes sequences of words and semantic tags for the words. Obtaining joint probabilities from a language model that includes joint probabilities corresponding to a corpus of text that includes sequences of words and semantic tags for the words may include generating an unweighted word lattice with semantic tags from the word lattice that indicates probabilities for sequences of words in an utterance and the semantic tags in the language model and composing the unweighted word lattice with semantic tags and the language model that includes joint probabilities corresponding to a corpus of text that includes sequences of words and semantic tags for the words.

Obtaining marginal probabilities for sequences of the words and the semantic tags for the words may include obtaining marginal probabilities from the joint probabilities. Obtaining marginal probabilities from the joint probabilities may include performing max-normalization so that the marginal probabilities represent pseudo-probabilities based on best tagging for a sentence. Obtaining the condition probability transducer from the joint probabilities and the marginal probabilities may include composing the joint probability and the inverse of the marginal probability. Obtaining the condition probability transducer from the joint probabilities and the marginal probabilities may include performing beam pruning to remove paths that do not satisfy a threshold conditional probability. Using the word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words to generate a transcription that includes the words in the utterance and the semantic tags for the words may include biasing the probability of a path in the word lattice based at least on a semantic tag in the path, selecting the path in the word lattice from among other paths in the word lattice based at least on the biased probability of the path, and generating a transcription from the selected path in the word lattice.

Particular implementations can, in certain instances, realize one or more of the following advantages. A first advantage of particular implementations may be the ability to start with a very large model (or annotated training corpus) and scale down to an arbitrarily small size that provides fast tagging speed, which may make the approach practical for real-time speech recognition.

A second advantage of particular implementations may be handling of ambiguity. In a scenario of automatic speech recognition (ASR) word lattice rescoring, tagging a highly ambiguous sentence may split the sentence into numerous alternate tagged paths, each one improbable in an absolute sense. This fragmentation may hurt the entire hypothesis' chance of being chosen over a non-ambiguous hypothesis. Particular implementations may address this problem by supporting “max-normalization,” where probabilities are scaled such that the best tagging gets a “probability” of one, preserving n-best order. Additionally or alternatively beam pruning of improbable tags may be supported to avoid cluttering the lattice, which may lead to faster automated speech recognition as the lattice is smaller.

DETAILED DESCRIPTION

FIG. 1is a block diagram of an example system100for adding semantic tags to a word lattice. A word lattice may be a collection of nodes and arcs that connect the nodes, where nodes correspond to words or semantic tags and paths through the nodes along the arcs correspond to different sentences. A semantic tag may be a decorator for one or more words that indicates a semantic meaning for the one or more words. For example, the text “<colors>” and the text “</colors> may be a semantic tag that indicates any words that appear between correspond to a color, e.g., “<colors> green </colors>” indicating that green is a color. In another example, the text “<vehicles>” and the text “</vehicles> may be a semantic tag that indicates any words that appear between correspond to a vehicle, e.g., “<vehicles> airplane </vehicles>” indicating that airplane refers to a vehicle.

The system100for adding semantic tags to a word lattice includes an automated speech recognizer104, a tag insertion engine108, a conditional probability engine116, and a composer120. The automated speech recognizer104may receive an utterance from a user102and generate an utterance weighted word lattice without tags106. For example, the automated speech recognizer104may receive mel-frequency cepstral coefficients (MFCCs) for an utterance of “A Clockwork Orange” and output the word lattice shown inFIG. 4that includes a path for “A Clockwork Orange” and “A New York Orange,” among other paths, as further described below.

An utterance weighted word lattice without tags may be a word lattice that indicates probabilities for sequences of words in an utterance. Sequences of words that sound more similar to the utterance and that more frequently appear in a language model may correspond with higher indicated probabilities, and sequences of words that sound more dissimilar to the utterance and that less frequently appear in the language model may correspond with lower indicated probabilities.

The automated speech recognizer104may output a word lattice that does not include semantic tags in cases where the recognizer104is not trained on text that includes semantic tags. For example, the recognizer104may be trained on text from books where the text includes only sentences with words and does not include sentences with both words and semantic tags for the words.

The tag insertion engine108may obtain the utterance weighted word lattice without tags106and obtain the tagging grammar rules110, and provide an unweighted word lattice with tags112. For example, as further described below, the tag insertion engine108may obtain the utterance weighted word lattice without tags shown inFIG. 4, obtain the tagging grammar rules110in the form of the transducer for inserting entity tags into a word lattice shown inFIG. 3, and provide the unweighted word lattice with tags shown inFIG. 5.

The unweighted word lattice with tags112may be a word lattice with the same words as those that appear in the utterance weighted word lattice without tags106, but without weights on arcs between nodes and with additional nodes inserted for the various ways that the words may be semantically tagged. For example, the unweighted word lattice with tags shown inFIG. 5includes all the words in the utterance weighted word lattice shown inFIG. 4, and additionally includes nodes for “<cities>,” “</cities>,” “<colors>,” and “</colors>” and corresponding arcs for the added nodes.

The tagging grammar rules110may be rules that describe how words can be semantically tagged. For example, the tagging grammar rules may describe that “Orange” may be tagged with “<colors>” or “<fruits>”, or not tagged at all, and “Queen” can be tagged as “<bands>Queen</bands>” or “<governmental_figures>Queen </governmental_figures>,” or not tagged at all.

In some implementations, tag insertion engine108may obtain the tagging grammar rules110in the form of a transducer that represents potential ways to tag words in a grammar, compose the utterance weighted word lattice without tags106and the transducer that represents potential ways to tag words in a grammar, and provide the result as the unweighted word lattice with tags112. For example, the tag insertion engine108may compose the weighted word lattice shown inFIG. 4with the transducer shown inFIG. 3.

The conditional probability engine116may obtain the unweighted word lattice with tags112and obtain a language model with conditional probabilities114, and output a word lattice with tags and conditional probabilities118. For example, the conditional probability engine116may obtain the unweighted word lattice with tags112shown inFIG. 5, obtain a language model that treats semantic tags and words as text in a sentence and indicates conditional probabilities for next text in a sentence based on previous text in a sentence, and output the word lattice with conditional pseudo-probabilities shown inFIG. 8. The word lattice with tags and conditional probabilities118may include paths with weights corresponding to conditional probabilities118where the weights are based on how frequently text of a next node appears after a sequence of text previously appears.

In some implementations, the conditional probability engine116may output the word lattice with tags and conditional probabilities118by composing the unweighted word lattice with tags112and the language model with conditional probabilities114. For example, the conditional probability engine116may output the word lattice with tagged sentence probabilities shown inFIG. 8by composing the unweighted word lattice with tags shown inFIG. 5and a language model that treats semantic tags and words as text in a sentence and indicates conditional probabilities for next text in a sentence based on previous text in a sentence.

In some implementations, the conditional probability engine116may obtain the language model with conditional probabilities114from a language model with words and semantic tags that indicates joint probabilities but does not indicate conditional probabilities. For example, the language model with conditional probabilities114may be obtained from an initial language model constructed from training on a corpus of text that includes both words and semantic tags, where to reduce the size of the initial language model only joint probabilities are stored and not conditional probabilities. This may be done due to storage efficiency and the convenience of using existing language model infrastructures to train and test. In the example, the conditional probability engine116may determine marginal probabilities for the given input word lattice from the joint probabilities stored in the initial language model, and then determine the conditional probabilities114for the given input word lattice by composing the joint probabilities and the inverse of the marginal probabilities.

In some implementations, the conditional probability engine116may additionally use beam pruning and max-normalization when obtaining the language model with conditional probabilities114. For example, the conditional probability engine116may remove paths in the language model with conditional probabilities that are more than a threshold cost greater than a path with a least cost. In another example, the conditional probability engine116may normalize the weight of paths in the language model with conditional probabilities so that a cost of a path with a lowest cost is the same as a cost of a corresponding path in the utterance weighted word lattice without semantic tags.

In another implementation, the language model with conditional probabilities114may be obtained from other approaches. For example, the system100may train a neural network with a corpus of text that includes words and semantic tags for the words and have the neural network output the language model with conditional probabilities114.

The composer120may obtain the word lattice with tags and conditional probabilities118and the utterance weighted word lattice without tags106and output an utterance weighted word lattice with tags122. For example, the composer120may obtain the word lattice with conditional pseudo-probabilities shown inFIG. 8and the utterance weighted word lattice without tags106shown inFIG. 4, and output the result as the weighted word lattice with tags122show inFIG. 9.

The utterance weighted word lattice with tags122may be a word lattice that includes paths for representations of a sentence with different words and different semantic tags for the words, where the paths indicate a probability that the path is correct based at least on the utterance and how frequently the sequences of words occur with the semantic tags. For example, an utterance weighted word lattice with tags112may be the word lattice with tagged sentence probabilities shown inFIG. 9.

Obtaining the utterance weighted word lattice with tags122may be advantageous as speech recognition hypotheses may be rescored based on tags to result in more accurate transcriptions. For example, if an utterance including a city is expected, then the costs of paths without a tag of “<cities>” may increase relative to costs of paths with a tag of “<cities>.” In another example, the tags in the lattice122may be used by downstream clients. For example, the tags may indicate specific trigger commands in a vocabulary of a downstream client and the downstream client may use the tags to identify the specific trigger commands. Additionally, obtaining the lattice122by, as described above, starting with a very large model or annotated training corpus and scaling down to an arbitrarily small size may provide fast tagging speed that is practical for real-time speech recognition.

FIG. 2is a flowchart of an example process200for adding semantic tags to a word lattice. The following describes the process200as being performed by components of the system100that are described with reference toFIG. 1. However, the process200may be performed by other systems or system configurations.

The process200includes obtaining, from an automated speech recognizer, a word lattice that indicates probabilities for sequences of words in an utterance (202). For example, the tag insertion engine108may obtain the utterance weighted word lattice without tags106from the automated speech recognizer104receiving acoustic features of an utterance “A Clockwork Orange.”

In some implementations, obtaining, from an automated speech recognizer, a word lattice that indicates probabilities for sequences of words in an utterance includes providing an utterance to the automated speech recognizer that does not semantically tag words and receiving, from the automated speech recognizer, the word lattice that indicates probabilities for sequences of words in an utterance, where the word lattice does not include semantic tags for words in the word lattice. For example, the automated speech recognizer104may be trained on a corpus of text that did not include semantic tags so the language model of the automated speech recognizer104is unable to identify potential semantic tags for words in an utterance.

The process200includes obtaining a conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear (204). For example, the conditional probability engine may obtain a language model with semantic tags and conditional probabilities114.

In some implementations, obtaining a conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear includes obtaining the conditional probability transducer from a language model that is trained on a corpus of text that includes sequences of words and semantic tags for the words. For example, the system100may generate the language model with conditional probabilities114from training a neural network with a corpus of text that includes sequences of words with semantic tags for the words.

In some implementations, obtaining a conditional probability transducer that indicates a frequency that sequences of both the words and semantic tags for the words appear includes obtaining joint probabilities for sequences of the words and the semantic tags for the words, obtaining marginal probabilities for sequences of the words, and obtaining the condition probability transducer from the joint probabilities and the marginal probabilities. For example, the system100may obtain the word lattice expanded with candidate entity tags and joint probabilities shown inFIG. 6, obtain the word lattice with marginal pseudo-probabilities shown inFIG. 7from the word lattice shown inFIG. 6, and obtain the word lattice with conditional pseudo-probabilities shown inFIG. 8from composing the word lattice shown inFIG. 6and the inverse of the word lattice shown inFIG. 7.

The process200includes composing the word lattice and the conditional probability transducer to construct a word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words (206). For example, the composer120may compose the utterance weighted word lattice without tags106shown inFIG. 4and the word lattice with tags and conditional probabilities118shown inFIG. 8to construct the word lattice shown inFIG. 9.

The process200includes using the word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words to generate a transcription that includes the words in the utterance and the semantic tags for the words (208). For example, the system100may generate a single transcription of “A Clockwork Orange” from the path in the word lattice shown inFIG. 9that indicates a cost that is lower than the cost of other paths in the word lattice.

In some implementations, using the word lattice that indicates probabilities for sequences of both the words in the utterance and the semantic tags for the words to generate a transcription that includes the words in the utterance and the semantic tags for the words includes biasing the probability of a path in the word lattice based at least on a semantic tag in the path, selecting the path in the word lattice from among other paths in the word lattice based at least on the biased probability of the path, and generating a transcription from the selected path in the word lattice. For example, if the system100is expecting an utterance that includes a term for a city, the system100may one or more of decrease a cost of paths that include a node for “<cities>”, e.g., decrease costs for the path for “A <cities> New York </cities> Orange” and the path for “A <cities> New York </cities> <colors>Orange </colors>,” and increase a cost of paths that do not include a node for “<cities>,” e.g., increase costs for the path for “A Clockwork Orange” and the path for “A Clockwork <colors> Orange </colors>.”

A detailed example of system100follows where the semantic tags added are entity tags.

Training the Tagging Model

A language model that models a joint distribution PT(s, t) may be trained, where the subscript T denotes a language model trained on data with entity tags, s is a sentence, and t represents a particular way of tagging.s. The language model may be trained by starting with a pre-existing very large (e.g., over 1 Terabyte) discriminative NED model, which can be thought of as a black box that can annotate large volumes of training data in an offline, batched manner. Additionally or alternatively a large corpus annotated through other means, such as human-introduced tags, may be used.

The NED model may support more than 10,000 semantic collections, or classes, organized into hierarchical relationships with multiple inheritance. For the purpose of building a fast and compact tagger, the collections may be reduced to a flat set, e.g., 200, 300, 1000, or some other number, of classes by agglomerating sibling collections into their parent. Agglomeration may be based on (1) cosine similarity between members of a collection and the entire collection using a context window of three tokens to the left and right; (2) in-class entropy, dropping collections heavily dominated by a few members; (3) frequency over an annotated sample, or some other approach.

A corpus of text, e.g., a corpus of two hundred billion search and voice command queries, may be annotated using the NED model. For example, semantic collection annotations may be mapped to the three classes, and opening and closing entity tags may be inserted around entities, e.g.: “how tall is <artists> taylor swift </artists>?”

The entity tags may be treated as regular words, and a Katz backoff n-gram language model (LM) trained on the annotated corpus. Before training, numeric entities such as telephone numbers and currencies may be aggregated into non-terminal symbols for generality. The LM may be entropy pruned to a target size of one hundred million n-grams and stored as an FST, with transition costs on each arc representing negative log probabilities.

Lattice Tagging Algorithm

While using PT(s, t) in a first-pass speech recognizer may automatically generate a word lattice with semantic tags in it, this may be impractical as non-determinism in PT(s, t) may introduce search errors, word accuracy reduction, and higher CPU utilization. Instead, tagging may be performed as a post-processing step on an input lattice L.

The essence of the lattice tagging algorithm may be to use Bayes' rule to derive the conditional distribution PT(t|s) from the joint PT(s, t) accomplished by dividing the joint probability by the marginal probability:

In Equation (1), each of the above terms is computed for an input lattice using FSTs. The input includes input lattice L, an acyclic, weighted automaton over words, a transducer C to insert entity tags into L, and the joint distribution PT(s, t).

L may be first determinized (with pruning to control the size of the output) and minimized. For example, if no path can be rescored in the second pass by ≥δ weight, all hypotheses that are ≥δ weight behind a best path may be pruned:
LOpt←min(detweight=δ(L))  (2)

Inserting Tags into the Lattice

To insert entity tags into LOpt, a grammatical “constrainer,” C, may be built. C may be an unweighted transducer whose input side accepts all untagged sentences and output side accepts optionally tagged sentences, subject to: (1) balanced open-close tags; (2) no nested tags; (3) text inside the tags corresponds to class instances observed in training data.

FIG. 3is a diagram of an example transducer for inserting entity tags into a word lattice. As shown inFIG. 3, the transducer includes a various nodes with arcs between the nodes that indicate pairs of words, tags, or wildcards. C may be constructed with a single master state that loops on any word in the language (represented by a wildcard label, σ) and on any observed instance of a permitted class, surrounded by open/close tags. Constraining the lattice in this manner may not only discard bad taggings, it may greatly reduce search space and give finer control over latency. Composing unweighted LOptwith C may yield an unweighted lattice representing all possible taggings of L:
LT←rmweight(LOpt)∘C(3)

FIG. 4is a diagram of an example word lattice for an utterance. The word lattice describes likelihoods that candidate transcriptions are correct for an utterance of “a clockwork orange.”FIG. 5is a diagram of an example word lattice expanded with candidate entity tags. The word lattice describes the various ways that the words in the LOptmay be tagged. Arc weights may be log probabilities and no weight may be represented by a probability of one.

Computing Joint Probability

Probabilities from the joint distribution PT(s, t) may be by composed with the unweighted lattice that represents all possible taggings of L.
LJ(s,t)←LT∘PT(s,t)  (4)

PTmay be a back-off LM and contain failure transitions denoted by the label ø that are followed when there is no match at the current FST state. A composition algorithm may be used that supports this functionality.

FIG. 6is a diagram of an example word lattice expanded with candidate entity tags and joint probabilities. The word lattice inFIG. 6may be LJ, an expanded lattice with the joint probabilities. For readability, arcs that have the same input and output label are displayed with only one label, e.g., “a:a” is displayed as “a”. The lattice is decorated with all possible taggings and whose arc weights are joint probabilities from PT(s, t).

Computing the Marginal Probability

The marginal probability, PT(s) may be computed with LJ. Computing PT(s) precisely from a cyclic automaton such as the entire LM PT(s, t) may be a non-trivial problem because the twins property. However, the marginal probability may be sufficiently calculated from just the (acyclic) lattice L:

To compute PT(SϵL), entity tags may be removed from the output arcs of LJby projecting on input, removing epsilons, determinizing, and combining all paths through the same words using the weighted determinization algorithm, which is guaranteed to terminate on acyclic inputs:
LM(s)←min(detweight=δ(rmeps(↑LJ)))  (6)

In the case of ASR, standard probability normalization may be undesirable because the probability of a hypothesis divided among several equi-probable taggings may be unfairly handicapped with respect to a hypothesis with just one tagging during Viterbi decoding. Max-normalization, where probabilities are scaled such that the highest “probability” becomes one may be used to address this handicap. Max-normalization may be enabled by having min and det operators use arc costs in the tropical semiring, where probability addition is replaced with taking the maximum. The computed quantities are no longer true probabilities and may be referred to as pseudo-probabilities. Instead of representing the sum of joint probabilities of all taggings of a sentence, the modified L′M represents joint probability of the best tagging of each sentence:

FIG. 7is a diagram of an example word lattice L′Mwith marginal pseudo-probabilities.

Computing the Conditional Probability

The joint distribution LJmay be divided by the marginal LMto get the conditional. Division may be performed by inverting arc weights in the denominator and composing the numerator with it:
LC(t|s)←min(detwt.=δ′(inv(LM(s)−1∘LJ(s,t)))),  (8)
where inv denotes inversion of input and output arc labels and the superscript −1 denotes inverting arc weights. Using max-normalization may normalize by the cost of the best path as computed in (6), giving the best path a conditional pseudo-probability of one. Prune taggings more than δ′ beam behind optimal tagging(s) during the determinization step is also performed in (8).

FIG. 8is a diagram of an example word lattice with conditional pseudo-probabilities. The word lattice may be LCwith conditional pseudo-probabilities. As shown inFIG. 8, the best tagging of “a new york orange” is “a <cities> new york </cities> <color> orange </color>”, while the best tagging of “a clockwork orange” has no tags, as there are no movie title tags in the example constraining grammar. The best tagging of any sentence has a log cost of 0.

Applying the Conditional Probability

The conditional distribution may be applied to the original (optimized) word lattice:
LCombined←LC(t|s)∘LOpt(9).

Lcombinedmay contain the original weights of L modified by added tags.

FIG. 9is a diagram of an example word lattice with tagged sentence probabilities. The word lattice may be LCwith tagged sentence probabilities, projected on the input side. The best path through any word sequence has the same probability as in the original lattice L as shown inFIG. 4.

When using max-normalization, paths with optimal taggings may keep the original path probability in the lattice, preserving their n-best order.

In speech recognition, weights in the original lattice L may encode the probability P1st(s), i.e., the probability assigned to any path s by the first-pass LM, so LCombinedis equivalent to:
LCombined=PT(t|s)·P1st(s)  (10)

P1st(s) may be a more efficient sentence-level model than PT(s) because it does not contain tags. Thus a more accurate sentence-level model may be with best available tagging knowledge. As discussed above, obtaining the word lattice with tagged sentence probabilities may be advantageous as speech recognition hypotheses may be rescored based on tags to result in more accurate transcriptions. For example, if an utterance including a city is expected, then the costs of paths without a tag of “<cities>” may increase relative to costs of paths with a tag of “<cities>.” In another example, the tags may be used by downstream clients. For example, the tags may indicate specific trigger commands in a vocabulary of a downstream client and the downstream client may use the tags to identify the specific trigger commands. Additionally, obtaining the lattice, as described above, starting with a very large model or annotated training corpus and scaling down to an arbitrarily small size may provide fast tagging speed that is practical for real-time speech recognition.

Computing device1000includes a processor1002, memory1004, a storage device1006, a high-speed interface1008connecting to memory1004and high-speed expansion ports1010, and a low speed interface1012connecting to low speed bus1014and storage device1006. Each of the components1002,1004,1006,1008,1010, and1012, are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor1002can process instructions for execution within the computing device1000, including instructions stored in the memory1004or on the storage device1006to display graphical information for a GUI on an external input/output device, such as display1016coupled to high speed interface1008. In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices1000may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system).

The memory1004stores information within the computing device1000. In one implementation, the memory1004is a volatile memory unit or units. In another implementation, the memory1004is a non-volatile memory unit or units. The memory1004may also be another form of computer-readable medium, such as a magnetic or optical disk.

The storage device1006is capable of providing mass storage for the computing device1000. In one implementation, the storage device1006may be or contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. A computer program product can be tangibly embodied in an information carrier. The computer program product may also contain instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory1004, the storage device1006, or memory on processor1002.

The high speed controller1008manages bandwidth-intensive operations for the computing device1000, while the low speed controller1012manages lower bandwidth-intensive operations. Such allocation of functions is exemplary only. In one implementation, the high-speed controller1008is coupled to memory1004, display1016(e.g., through a graphics processor or accelerator), and to high-speed expansion ports1010, which may accept various expansion cards (not shown). In the implementation, low-speed controller1012is coupled to storage device1006and low-speed expansion port1014. The low-speed expansion port, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet) may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

The computing device1000may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server1020, or multiple times in a group of such servers. It may also be implemented as part of a rack server system1024. In addition, it may be implemented in a personal computer such as a laptop computer1022. Alternatively, components from computing device1000may be combined with other components in a mobile device (not shown), such as device1050. Each of such devices may contain one or more of computing device1000,1050, and an entire system may be made up of multiple computing devices1000,1050communicating with each other.

Computing device1050includes a processor1052, memory1064, an input/output device such as a display1054, a communication interface1066, and a transceiver1068, among other components. The device1050may also be provided with a storage device, such as a microdrive or other device, to provide additional storage. Each of the components1050,1052,1064,1054,1066, and1068, are interconnected using various buses, and several of the components may be mounted on a common motherboard or in other manners as appropriate.

The processor1052can execute instructions within the computing device1050, including instructions stored in the memory1064. The processor may be implemented as a chipset of chips that include separate and multiple analog and digital processors. Additionally, the processor may be implemented using any of a number of architectures. For example, the processor410may be a CISC (Complex Instruction Set Computers) processor, a RISC (Reduced Instruction Set Computer) processor, or a MISC (Minimal Instruction Set Computer) processor. The processor may provide, for example, for coordination of the other components of the device1050, such as control of user interfaces, applications run by device1050, and wireless communication by device1050.

Processor1052may communicate with a user through control interface1058and display interface1056coupled to a display1054. The display1054may be, for example, a TFT (Thin-Film-Transistor Liquid Crystal Display) display or an OLED (Organic Light Emitting Diode) display, or other appropriate display technology. The display interface1056may comprise appropriate circuitry for driving the display1054to present graphical and other information to a user. The control interface1058may receive commands from a user and convert them for submission to the processor1052. In addition, an external interface1062may be provide in communication with processor1052, so as to enable near area communication of device1050with other devices. External interface1062may provide, for example, for wired communication in some implementations, or for wireless communication in other implementations, and multiple interfaces may also be used.

The memory1064stores information within the computing device1050. The memory1064can be implemented as one or more of a computer-readable medium or media, a volatile memory unit or units, or a non-volatile memory unit or units. Expansion memory1074may also be provided and connected to device1050through expansion interface1072, which may include, for example, a SIMM (Single In Line Memory Module) card interface. Such expansion memory1074may provide extra storage space for device1050, or may also store applications or other information for device1050. Specifically, expansion memory1074may include instructions to carry out or supplement the processes described above, and may include secure information also. Thus, for example, expansion memory1074may be provide as a security module for device1050, and may be programmed with instructions that permit secure use of device1050. In addition, secure applications may be provided via the SIMM cards, along with additional information, such as placing identifying information on the SIMM card in a non-hackable manner.

The memory may include, for example, flash memory and/or NVRAM memory, as discussed below. In one implementation, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory1064, expansion memory1074, or memory on processor1052that may be received, for example, over transceiver1068or external interface1062.

Device1050may also communicate audibly using audio codec1060, which may receive spoken information from a user and convert it to usable digital information. Audio codec1060may likewise generate audible sound for a user, such as through a speaker, e.g., in a handset of device1050. Such sound may include sound from voice telephone calls, may include recorded sound (e.g., voice messages, music files, etc.) and may also include sound generated by applications operating on device1050.

The computing device1050may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a cellular telephone1080. It may also be implemented as part of a smartphone1082, personal digital assistant, or other similar mobile device.

Additionally computing device1000or1050can include Universal Serial Bus (USB) flash drives. The USB flash drives may store operating systems and other applications. The USB flash drives can include input/output components, such as a wireless transmitter or USB connector that may be inserted into a USB port of another computing device.