Representation of a deleted interpolation N-gram language model in ARPA standard format

A method and apparatus are provided for storing parameters of a deleted interpolation language model as parameters of a backoff language model. In particular, the parameters of the deleted interpolation language model are stored in the standard ARPA format. Under one embodiment, the deleted interpolation language model parameters are formed using fractional counts.

BACKGROUND OF THE INVENTION

The present invention relates to language models. In particular, the present invention relates to storage formats for storing language models.

Language models provide probabilities for sequences of words. Such models are trained from a set of training data by counting the frequencies of sequences of words in the training data. One problem with training language models in this way is that sequences of words that are not observed in the training data will have zero probability in the language model, even though they may occur in the language.

To overcome this, back-off modeling techniques have been developed. Under a back-off technique, if a sequence of n words is not found in the training data, the probability for the sequence of words is estimated using a probability for a sequence of n−1 words and a back-off weight. For example, if a trigram (wn−2wn−1wn) is not observed in the training data, its probability is estimated using the probability of the bigram (wn−1wn) and a back-off weight associated with the context (wn−2wn−1).

N-gram language models that use back-off techniques are typically stored in a standard format referred to as the ARPA standard format. Because of the popularity of back-off language models, the ARPA format has become a recognized standard for transmitting language models. However, not all language models have back-off weights. In particular, deleted interpolation N-gram models do not have back-off weights because they use a different technique for handling the data sparseness problem associated with language models. As a result, deleted interpolation language models have not been stored in the standard ARPA format. Because of this, it has not been easy to integrate deleted interpolation language models into language systems that expect to receive the language model in the ARPA format.

SUMMARY OF THE INVENTION

A method and apparatus are provided for storing parameters of a deleted interpolation language model as parameters of a backoff language model. In particular, the parameters of the deleted interpolation language model are stored in the standard ARPA format. Under one embodiment, the deleted interpolation language model parameters are formed using fractional counts.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

The present invention provides a technique for storing a language model generated through deleted interpolation in the standard ARPA format. In deleted interpolation, an N-gram probability is determined as a linear interpolation of a relative frequency estimate for the N-gram probability and a probability for a lower order n-gram. The probability of the lower order n-gram is similarly defined as an interpolation between the relative frequency probability estimate for the lower order n-gram and next lower order n-gram. This continues until a unigram probability is determined. Thus, the interpolation is determined recursively according to:
P(vk|vk−(n−1). . . vk−1)=(1−λn−1(vk−(n−1). . . vk−1))f(vk|vk−(n−1). . . vk−1)+λn−1(vk−(n−1). . . vk−1)P(vk|vk−(n−2). . . vk−1)  EQ. 1
where P(vk|vk−(n−1). . . vk−1) is the probability of the n-gram, λn−1(vk−(n−1). . . vk−1) is an interpolation weight that is a function of the context vk−(n−1). . . vk−1of the N-gram, f(vk|vk−(n−1). . . vk−1) is the relative frequency of the N-gram, which is the number of times the N-gram appears in the training text over the number of times the context of the N-gram appears in the training text, and P(vk|vk−(n−2). . . vk−1) is the probability of the next lower order n-gram, which is determined recursively using equation 1 with a weight λn−2(vk−(n−2). . . vk−1) that is a function of the context of the lower order n-gram. The recursion of Equation 1 ends with a unigram probability that is determined as:

P⁡(vk)=(1-λ0)⁢f⁡(vk)+λ0⁢1VEQ.⁢2
where P(vk) is the unigram probability, λ0is the unigram interpolation weight, f(vk) is the relative frequency for the unigram vk, which is the ratio of the number of times the unigram appears in the training text over the number of words in the training text, and |V| is the number of words in the vocabulary, which acts as a default unigram probability.

Using the recursion of Equations 1 and 2, the probability for the N-gram becomes an interpolation of relative frequencies for different orders of n-grams that are below the N-gram of interest. For example, for a trigram, the recursive interpolation produces:

P⁡(vk❘vk-2⁢vk-1)=(1-λ2⁡(vk-2⁢vk-1))⁢f⁡(vk❘vk-2⁢vk-1)+λ2⁡(vk-2⁢vk-1)⁢(1-λ1⁡(vk-1))⁢f⁡(vk❘vk-1)+λ2⁡(vk-2⁢vk-1)⁢λ1⁡(vk-1)⁢(1-λ0)⁢f⁡(vk)+λ2⁡(vk-2⁢vk-1)⁢λ1⁡(vk-1)⁢λ0⁢1VEQ.⁢3
Where P(vk|vk−2vk−1) is the trigram probability, f(vk|vk−2vk−1) is the relative frequency of the trigram in a training text, f(vk|vk−1) is the relative frequency of a bigram in the training text, f(vk) is the relative frequency of the unigram in the training text, |V| is the number of vocabulary words in the language model, and λ2, λ1, λ0are the context-dependent interpolation weights.

Under some embodiments, the counts used to determine the relative frequencies are not limited to integer valued counts and may include fractional values that are computed as the expected values of the counts. This is one advantage of deleted interpolation over other back−off methods, such as the Katz back-off method, which cannot be used on fractional (real valued) counts.

FIG. 2provides a graphical representation of the calculation of the N-gram probability using deleted interpolation. InFIG. 2, the intersection points between the lines represent the interpolation of a probability for an n-gram. For example, the unigram probability is determined at node200and the N-gram probability is determined at node220. At each node, a weighted relative frequency is added to the weighted probability determined at a lower node.

For example, beginning at node200, the interpolated unigram probability is determined as the weighted sum of the unigram relative frequency202and the default unigram probability204where weight206(1−λ0) is applied to relative frequency202and weight208(λ0) is applied to the default unigram probability204.

The probability at the next higher node210is the weighted sum of the relative frequency212for the bigram and the unigram probability of node204. A weight214(λ1(vk−1)), which is a function of the context of the bigram, is applied to the unigram probability of node204while a weight216(1−λ1(vk−1)) is applied to the relative frequency212.

This recursive summation continues upward until it reaches node220for the N-gram probability. The probability determined for node220is the weighted sum of the probability determined at node222for the next lower order n-gram and the relative frequency224of the N-gram, where the weight226applied to the lower order probability is λ(n−1)(vk−(n−1). . . vk−1) and the weight228applied to the relative frequency is 1−λ(n−1)(vk−(n−1). . . vk−1), which are both dependent on the context of the N-gram.

As can be seen fromFIG. 2, in order to determine the probabilities for an N-gram, the relative frequencies for the lower order n-grams and the weights for the contexts must be determined.FIGS. 3 and 4provide a block diagram and a flow diagram for determining these values.

In step400ofFIG. 4a training text300is divided into a main portion302and a check portion304. At step402, a relative frequency counter306parses main portion302into n-grams of varying orders from unigrams to the highest N-gram of interest. Relative frequency counter306then counts the relative frequency of each n-gram in each order of n-gram. This produces a set of n-gram relative frequency counts308for each n-gram in each order of n-gram.

At step404, the relative frequencies308are applied to an EM trainer310, which uses an expectation maximization algorithm to set the values for the weights, λn−1. . . λ0, so as to maximize the total probability of all of the highest order N-grams such that:

Where [λn−1. . . λ0] is the set of weights that maximize the probabilities of the highest order N-grams where the total probability is the product of the individual probabilities for each ith N-gram, where each individual probability is calculated using the recursive interpolation of Equations 1 and 2.

As noted above, the weights are functions of the contexts of the n-gram probabilities they are used to determine. To counteract data sparseness (which would lead to unreliable estimates) and at the same time reduce the computational complexity of the EM training, these weights are grouped into buckets based on the frequency counts of the context. Under one embodiment, ranges of frequency counts are grouped into the same weights. Thus, one λn−1may be for contexts that are seen between 16 and 32 times and one λn−1may be for contexts that are seen between 33 and 64 times. This results in a smaller set of weights that need to be trained and a smaller set of training text that is needed for training.

Note that since the weights are maximized against check data304, there will be n-grams in check data304that were not observed in main data302. Thus, the weights are set to anticipate unseen data.

Under some embodiments, the training text300may be re-segmented in a different manner and the relative frequency counts may be re-determined for the new grouping of text. These new frequency counts may then be applied to the EM trainer310to re-determine the values of the weights. When re-determining the values of the weights, the algorithm begins with the estimates of the weights determined at the previous iteration. Such iterations may be repeated until the weights reach stable values. After the desired number of iterations has been formed, a set of weights312is stored together with the final set of relative frequency counts308as a deleted interpolation model314at step406. This deleted interpolation model may be used to determine probabilities for new text by parsing the text into the different order n-grams, searching for the appropriate weights for each of the contexts and performing the calculation of the interpolated probability using Equations 1 and 2.

The interpolation represented by Equations 1 and 2 is substantially different from the techniques used with the more widely accepted backoff language models, which are typically represented in the standard ARPA format. Instead of using a linear interpolation to determine the probability for an N-gram, the more widely accepted backoff language models use a substitute probability for any N-gram that cannot be located in the model. This substitute probability is based on a lower order model and a backoff weight associated with the context of the probability that can not be located. Thus, instead of performing an interpolation, the more standard backoff language models simply replaces an N-gram probability with a lower order n-gram probability.

FIG. 5provides a flow diagram of a method for determining a probability for an N-gram using a backoff model of the prior art. At step500ofFIG. 5, a search is performed to determine if a probability for the N-gram is located in the backoff language model. If the probability is present for the N-gram, the probability is returned at step502. If the probability for the N-gram is not found at step500, a backoff weight associated with the context of the N-gram is located at step504. At step506, a search is performed to determine if the backoff language model includes a probability for the next lower order n-gram. For example, if the top order N-gram was a trigram, step506would search for a probability for the bigram. If the probability for the next lower order n-gram can not be found at step506, the process returns to step504to locate the backoff weight for the context of the next lower order n-gram. For example the backoff weight for the context of the bigram. The process then returns to step506to search for a probability for the next lower order n-gram. Thus, if a bigram probability had been searched for previously at step506, a unigram probability would be searched for upon returning to step506.

Once a probability is found for an n-gram at step506, the probability is multiplied by all of the backoff weights that were encountered in iterations through steps504and506to form the probability for the N-gram at step508.

As can be seen inFIG. 5, in order to calculate a language model probability for an N-gram using the standard backoff language model, the probabilities of various orders of n-grams must be searched for as well as the backoff weights for the contexts of those n-grams. The standard ARPA format for the backoff language models provides a standard format that allows the same search algorithms to be used to find the necessary probabilities and backoff weights regardless of the particular backoff language model that is being used. For example, if two vendors provide two separate backoff language models in the ARPA format, the same code can be used to determine probabilities from both language models.

FIG. 6provides a diagram of the layout of the standard ARPA format for backoff language models. InFIG. 6, the standard format includes a header tag600and an ending tag602. Below header tag600is a list604that includes a separate entry for each order of n-gram. Each entry indicates the number of n-grams for that order of n-grams that is present in the language model. For example, entry606indicates that there are n1unigrams and entry608indicates that there are nN N-grams.

Below list604are a set of section, with one section for each order of n-gram. Each section is headed with a separate tag such as tag610for unigrams, tag612for bigrams, and tag614for N-grams, where N is the top order of n-grams in the language model.

Below each heading for the different orders of n-grams, there is a list of entries, one for each n-gram of that order. Each entry includes the probability of the n-gram, the n-gram, and for n-grams of orders other than the top order, a backoff weight. For example, under unigram heading610, entry618includes a probability622for a unigram620and a backoff weight616. Note that backoff weight616is associated with word620when word620is used as a context in a bigram. Similarly, entry624under bigram heading612includes a bigram probability626for the bigram628consisting of words v1v2and a backoff weight630associated with words v1v2being used has the context of a trigram. Typically, the probabilities and the backoff weights are stored in log base10format.

For entries under top order n-gram heading614, there are no backoff weights. Thus, for entry632there is just a probability634, and an n-gram v1. . . vn636.

ComparingFIG. 2withFIG. 6, it is not clear that an interpolation model such as the one shown inFIG. 2can be stored in the standard ARPA format ofFIG. 6.FIG. 7provides a flow diagram of a method for storing a deleted interpolation model in the standard ARPA format under one embodiment of the present invention.

In step700ofFIG. 7, the relative frequencies and the weights, λ, of the deleted interpolation model are determined. The top order for a set of L-grams is selected at step702, where L is between 1 and N with N being the top order. At step704, an L-gram of the selected order is selected and at step706a determination is made as to whether the relative frequency of the selected L-gram is greater than zero. If it is greater than zero, the interpolation probability for the L-gram is calculated using equation 1 and is stored as the probability of the L-gram in the standard format. For example, an entry under top order heading614ofFIG. 6would be created with the probability, such as probability634, being set equal to the interpolated probability of the L-gram and the L-gram itself being placed in the L-gram field such as field636ofFIG. 6.

If the relative frequency of the L-gram is not greater than zero, the probability for the L-gram is not stored in the standard ARPA format.

After the probability for the L-gram has been stored at step708or after it has been determined that the relative frequency of the L-gram is not greater than zero, the method determines if there are more L-grams to consider for the top order of L-grams at step710. If there are more L-grams to consider, the processes returns to step704and selects the next L-gram. Steps706and708are then repeated for this new L-gram. Steps704,706,708, and710are repeated until all the L-grams of the top order have been processed.

Once all of the L-grams for the top order of L-grams have been processed at step710, the method determines if the current order of L-grams being processed is greater than zero at step712. If the order of L-grams currently being processed is greater than zero, the order is reduced by one to move to the next lower order at step714. An L-gram at this next lower order is then selected at step716.

At step718, the relative frequency of the selected L-gram is examined to determine if it is greater than zero. If it is not greater than zero, the process continues at step720where the higher order L-grams previously stored in the ARPA file are examined to determine if the present L-gram is a context of one of the higher order L-grams. If the L-gram is found as a context in a higher order L-gram at step720or the relative frequency of the L-gram is greater than zero at step718, the interpolated probability of the L-gram is stored as the probability of the L-gram in the ARPA file and the λ that is a function of the L-gram in the deleted interpolation model is stored as the backoff weight for the L-gram at step722. For example, if the λ's are functions of the relative frequencies of the L-grams, the λ associated with the relative frequency of the current L-gram is stored as the backoff weight. For example, if the L-gram is the bigram v1v2, the weight associated with bigrams that have a relative frequency equal to the relative frequency of v1v2is used as the backoff weight for the bigram v1v2and the interpolated probability is used as the probability of the bigram v1v2.

Thus, an L-gram is stored if its relative frequency is greater than zero, i.e. it was seen in the training data, and if it appears as a context for a higher order L-gram. By limiting the L-grams that are stored to those that meet these criteria, this embodiment of the present invention creates a compact language model in the backoff format.

An L-gram can appear as a context while having a relative frequency of zero in the training text if the relative frequencies are determined by setting the relative frequencies to zero if their initial relative frequency is below a threshold. For example, if an L-gram has a relative frequency of 0.02 and the threshold is set to 0.02, the relative frequency for the L-gram would be set to zero. This is done to reduce the size of the interpolation model.

The reason for storing an L-gram if it appears as a context in a higher order L-gram even though it has a relative frequency of zero is that since the L-gram appears as a context for a higher order L-gram, a backoff weight for this context will be needed in the language model.

After step722or if the current selected L-gram does not have a relative frequency greater than zero at step718and is not used as a context of a higher order L-gram at step720, the process determines if there are more L-grams of the current order at step724. If there are more L-grams at the current order, the next L-gram is selected at step716and steps718,720,722, and724are repeated. Steps716,718,720,722and724are repeated until all of the L-grams of the selected order have been processed.

When there are no more L-grams for the current order at step724, the process returns to step712to determine if the order is greater than zero. If the order is greater than zero, the next lower order is selected at step714and steps716-724are repeated for the L-grams in the new lower order. When the order is no longer greater than zero at step712, all of the orders of n-grams have been processed and the method ofFIG. 7ends at step726.

Thus, the method ofFIG. 7is able to represent a deleted interpolation n-gram model in the ARPA backoff standard format. This allows language models that are formed through the deleted interpolation technique to be integrated into language systems that expect to receive the standard ARPA format.