Modular approach to building large language models

Methods for building arbitrarily large language models are presented herein. The methods provide a scalable solution to estimating a language model using a large data set by breaking the language model estimation process into sub-processes and parallelizing computation of various portions of the process.

BACKGROUND

Language models provide probabilities for sequences of words and are a primary component in most modern speech and language applications. These models are generated from a set of training data by counting the frequency of occurrence of sequences of n words in the training data (where n is an integer). Sequences of n words are referred to as n-grams. N-grams are classified based on the number of words included in the n-gram. For example, a unigram is a single word, a bigram is an ordered sequence of two words, a trigram includes three words, and a 5-gram includes five words. Because not all possible sequences of words will appear in the training data, back-off modeling techniques have been developed to assign estimated frequencies to non-appearing sequences.

Many such applications, in particular, automatic speech recognition (ASR) and machine translation (MT), have evolved over the past decade, offering high performance and usability. Today, despite extensive research on novel approaches, the standard back-off n-gram language model remains the model of choice in most applications due to its efficiency and reliability. Significant gains in performance are achieved by utilizing larger amounts of training data available for language modeling. However, very large data sets (e.g. data sets including billions of words) pose a computational challenge where one must be able to estimate billions of parameters. Systems and methods are needed for reducing the memory requirements of language models without reducing model accuracy.

SUMMARY

The invention, in various embodiments, addresses the computational challenge of estimating a language model using a large data set. More particularly, according to one aspect, the invention provides a scalable solution by breaking the language model estimation process into sub-processes and parallelizing computation of various portions of the process.

According to one aspect, the invention provides a method of building a language model which begins with providing a text and a first set of count files. Respective count files are associated with one or more corresponding text elements. A series of consecutive text elements is selected from the text to form an n-gram. The n-gram is assigned to one or more count files of the first set of count files based on the presence of a selected text element in the n-gram.

The process of assigning the n-gram to a count file includes, for example, increasing a count corresponding to the n-gram. The method may further include computing probability estimates for the n-grams assigned to the count files.

In one embodiment, the series of consecutive text elements used to form the n-gram includes a current text element and a history of text elements. The selected text element, i.e. the text element used to assign the n-gram to a count file, is the most recent text element in the history, where the history includes the text elements which occurred prior to the current text element. In constructing an n-gram, a predetermined number of the history text elements are included. For example, trigrams from the phrase “see Spot run to Jane” include “see Spot run”, “Spot run to”, and “run to Jane”. The last element of each trigram is the current text element (i.e. “run”, “to”, and “Jane”, respectively), and the second-to-last element being the most recent history element (i.e. “Spot”, “run”, and “to”, respectively). The trigrams may be denoted as (run|Spot, see), (to|run, Spot), and (Jane|to, run), respectively. Note that a text element may be a word, a comma, a period, a beginning-of-sentence marker, an end-of-sentence marker, or any other grammatical or formatting element. The n-grams are derived from text elements in the text.

In one embodiment, the series of text elements may comprise a single text element, and thus the n-gram is a unigram. In some implementations, unigrams are assigned to more than one count file of a set of count files. In one example, unigrams are assigned to each of the count files. In other embodiments, the n-gram may be a bigram, a trigram, a four-gram, a five-gram, a six-gram, a seven-gram, and eight-gram, or longer than an eight-gram.

According to one implementation, the method includes merging the first set of count files to a single count file. The method may also include a second set of count files, and each count file of the second set of count files may correspond to a respective count file of the first set of count files. In one embodiment, the method includes merging, in parallel, each count file of the first set of count files with each of the respective count files of the second set of count files. The second set of count files, in one embodiment, are populated with n-grams derived from a second text. According to various implementations, the method includes generating a language model from the first set of count files.

According to another aspect, the invention provides a method of building a language model. The method includes providing a first language model comprising a first set of data files and a second language model comprising a second set of data files. The language models are then merged in parallel.

In one embodiment, providing language model includes calculating a plurality of probabilities related to the likelihood of selected n-grams and storing the plurality of probabilities in data files corresponding to the language model. According to one embodiment, the data files are language model subsets.

According to one feature, the method includes generating a combined language model. The combined language model is generated by merging respective data files of the first language model with corresponding data files of the second language model. The corresponding data files are merged in parallel. In one embodiment, merging respective ones of the first set of data files with corresponding ones of the second set of data files includes interpolating corresponding probability measurements.

In one implementation, each of the first set of data files is associated with a set of text elements, and each of the corresponding second set of data files is associated with the same set of text elements. According to one embodiment, the set of text elements may include words, commas, periods, beginning-of-sentence markers, end-of-sentence markers, and other grammatical and formatting elements.

In one implementation, the data files of the first set of data files and the data files of the second set of data files store probability measurements. The probability measurements indicate the probability of occurrence of various selected n-grams. In one implementation, a smoothing algorithm is used to assign probability estimates to additional n-grams that are not present in the data files. In some implementations, either instead of or in addition to a smoothing algorithm, back-off weights are calculated to assign probability estimates to a second set of n-grams that are not present in the data files.

According to one implementation, merging respective data files of the first set of data files with corresponding data files of the second set of data files results in a set of merged data files. Respective data files of the set of merged data files may then be pruned. According to one feature, the respective data files may be pruned in parallel.

Throughout the figures, the characters c, k, n, m and x are used in the reference numbers. These characters may represent any selected integer, with the same character representing the same selected integer throughout the figures.

DETAILED DESCRIPTION OF THE DRAWINGS

To provide an overall understanding of the invention, certain illustrative embodiments will now be described, including systems, methods and devices for building arbitrarily large language models. However, it will be understood by one of ordinary skill in the art that the systems and methods described herein can be adapted and modified for other suitable applications and that such other additions and modifications will not depart from the scope hereof.

Large language models are generally built using several corpora of data. Each corpus usually includes text data of a particular origin. For example, one corpus may include text taken from several years of Wall Street Journal newspapers. Another corpus may be transcribed speech from recorded telephone conversations. Each corpus may be used to build an independent language model, and these language models may be combined to form a larger, more accurate, language model.

Building large language models from text data typically involves two steps. First, n-gram counts are collected. An n-gram is a particular series of n text elements. An n-gram count is the number of occurrences of that n-gram observed in a corpus of text. Next, n-gram probabilities are estimated from the n-gram counts. N-gram probabilities are typically noted in the form p(wc|wh) and denote the probability of a current word wcappearing next given a history of previous words wh.

FIG. 1is a block diagram of a prior art method100of generating n-gram counts. The method100begins with a plurality of text files102a-102m. For each text file102a-102m, the n-grams (usually unigram, bigrams, and/or trigrams) occurring in the text files102a-102mare counted (step104a-104m), resulting in n-gram counts106a-106m. Next, the n-gram counts106a-106mare merged (step110), resulting in a merged n-gram count112. Merged n-gram count112includes the total number of occurrences of the n-grams observed in the combined set of text files102a-102m. According to this method, the individual n-gram counts106a-106mare serially merged to the merged n-gram count112.

FIG. 2is a block diagram of a method200of generating counts according to an illustrative embodiment of the invention. The method200begins with the provision of a plurality of text files202a-202m. Each text file202amay be an independent training corpus, or it may be a portion of a larger training corpus, which has been split into m files. The text files202a-202mare used to generate a set of k skeleton count files204a-204k, as explained in greater detail with respect toFIG. 3. Each skeleton count file204a-204kis associated with one or more text elements from the text files202a-202m. A text element associated with a particular skeleton count file is referred to herein as an “assigned element.”

For each text file202a-202m, occurrences of n-grams in the text files202a-202mare counted (208a-208m) resulting in n-gram counts210a-210m. Each n-gram count210a-210mincludes k count files, such as count files212a-212k, generated from text file202a, and214a-214k, generated from text file202m. The count files212a-212kand214a-214kcorrespond to the previously generated skeleton count files204a-204k. Each count file212a-212kand214a-214kincludes a subset of the n-gram counts210a-210m. The subset of a particular count file212a-212kand214a-214kis based on the assigned elements of a corresponding skeleton count file204a-204k. A count file includes the counts of all n-grams in which the most recent element in the history of an n-gram is one of the count file's assigned elements. For example, n-grams (*|wi−1), (*|wi−1, wi−2), . . . , (*|wi−1, . . . , wi−n+2), where * denotes a current word, wi−1denotes the immediately preceding word, wi−2denotes the word preceding word wi−1, etc., are added to the same count file, since they share the most recent history element wi−1. If an n-gram is not currently present in a count file, the n-gram is added to the file and given a count of one, while if the n-gram is already present in the count file, the count is increased by one. Respective count files212a-212kand214a-214kof the n-gram counts210a-210m, generated from the various text files202a-202m, include counts of corresponding n-grams. For example, the n-gram counts included in count file212acorrespond to the n-gram counts of count file214a, since both count files212aand214ahave the same set of assigned elements, and all n-grams from the respective text files202aand202mhaving one of the assigned elements as the most recent history element are included in the respective count file212aand214a. Similarly, the n-gram counts included in count file212bcorrespond to the n-gram counts of count file214b. And, the n-gram counts included in count file212kcorrespond to the n-gram counts of count file214k. Additionally, the count files may include a count of all unigrams in the corresponding text file.

The n-gram counts210a-210mfrom the text files202a-202mare merged in parallel at218a-218kby merging each count file212a-214kwith the respective corresponding count files212a-214kof the n-gram counts210a-210m. For example, count file212ais merged with214aat218a, in parallel with the merger of count file212bwith214bat218b, and count file212kwith214kat218k. This process results in the merged count220, having merged count files222a-222k.

According to various embodiments, the method200is performed on a conventional computer system having a processor, non-volatile storage (e.g. a hard drive or optical drive), and random access memory (RAM). In one example, the method200is performed on a personal computer with an Intel Pentium 4 (3 GHz) processor, 1 GB of RAM and a 200 GB hard drive. As described further in reference toFIG. 3, the skeleton count files204a-204kare generated such that the count files212a-214kare small enough such that the computer system can perform the merging in steps218a-218kwithout accessing the non-volatile storage of the computer system. Since corresponding count files (e.g.212aand214a) are merged independent of other count files (212b-212kand214b-214k), during merging, only one set of corresponding count files (e.g.212athrough214a) needs to be uploaded to RAM at a time, while the other count files (e.g.212b-212kthrough214b-214k) may be stored in non-volatile storage. Performing the merging step218in RAM increases efficiency and requires far less RAM than merging all n-gram counts at the same time.

Previous n-gram counting methods stored counts for all n-grams in a single data file. As this file can grow in size rapidly, such methods have often required pruning the count files (discarding the least-frequent n-grams) prior to estimating a language model to decrease count file size to fit into system RAM. By enabling the merging in steps218a-218kto occur without pruning, the method200prevents the decrease in accuracy inherent in prior language model creation methods.

FIG. 3is a block diagram of a method300of generating k skeleton count files310a-310kfrom m text files302a-302m. Text elements304a-304kare assigned to the skeleton count files310a-310kas described in relation toFIG. 2, resulting in lists of assigned elements. The number k of skeleton count files310a-310kmay be determined based on the amount of RAM available in the computer system. In various embodiments, about 10, about 25, about 50, about 75, about 100, about 150, about 200, about 250, or about 300 count files are used. To assign the text elements304a-304x, in one illustrative embodiment, the total number of occurrences of each text element304a-304xin the text files302a-302mis counted yielding counts306a-306x. The counts306a-306xare stored in memory with the corresponding text elements304a-304x. Alternatively, counts306a-306xare generated from a representative sample of text from one or more of the text files. For example, w1may occur 3 times, w2may occur 96 times, w3may occur 32 times, and wxmay occur 58 times. Depending in part upon the text element counts306a-306x, the text elements304a-304xare divided among the plurality of skeleton count files310a-310k. For example, text element304amay be assigned to skeleton count file310cand text element304cmay be assigned to skeleton count file310a, etc. The text elements304a-304xassociated with each skeleton count file310a-310kpreferably are assigned such that the count files that are derived from the skeleton count files310a-310k(e.g. the count files212a-214kofFIG. 2), will be of similar sizes after the assignment of all associated n-grams to the count files. Splitting the count data into count files of approximately equal size allows an even distribution of computational load among the merging processes218. In one embodiment, the approximate distribution is achieved by round-robin assignment of text elements. For example, the text element with the highest count is assigned to the first count file310a, the text element with the second highest count is assigned to the second count file310b, and so forth, with text element k+1 assigned back to the first count file310a.

Factors other than the number of times a text element occurs may contribute to the assignment of a text element to a skeleton count file. For example, the number of different text elements that may precede a selected text element may contribute to the assignment of the selected text element to a skeleton count file, with text elements that may be preceded by a large number of different text elements spread evenly among the skeleton count files310a-310k.

Referring back toFIG. 2, when assigning counts to count files212a-212kand214a-214k, it is not necessary for all text elements to have an explicit assignment to a skeleton count file204a-204k. In one implementation, any text element that does not have an explicit assignment is automatically mapped to a special “catch-all” skeleton file. Even though the number of such text elements can be large (i.e. all text elements that did not occur in the text files302a-302mthat were used for extracting the assigned elements), these elements are likely to be infrequent and, hence, will not be a big factor in memory usage.

FIG. 4is a block diagram of an exemplary count file400generated, for example, from text file202a. The exemplary count file400includes the counts410a-410c,414a-414cand418a-418c. Counts410a-410c, etc., correspond to n-grams408a-408c(bigrams),412a-412c(trigrams) and416a-416c(trigrams). The count file400also includes combined counts404a-404cof all unigrams402a-402cfrom a text file (e.g. text file202aofFIG. 2).

One of the text elements assigned to count file400is the word “Spot.” As shown in the figure, the bigrams408a-408chave “Spot” as the most recent text element in their history. Each bigram408a-408cincludes a current element which occurred after the word “Spot,” such as run (408a), jump (408b), and beg (408c). In generating the count file400, each time the word “Spot” was detected in the text file followed by the word “run”, the count410aof bigram (run|Spot) was incremented by one. According to the count file400, the text file from which the count file400was populated included the word “Spot” followed by the word “run” 25 times (410a). “Spot” was followed by the word “jump” 20 times (410b), and was followed by the word “beg” 5 times (410c).

The count file400also includes trigrams412a-412cand416a-416c. These trigrams412a-412cand416a-416calso have “Spot” as the most recent history element. They further include the element which occurred before “Spot” in the text file. For example, in the trigrams412a-412c, “Spot” is preceded by “see.” Again, various words may occur after “Spot,” including for example “run” (412a), “jump” (412b), and “beg” (412c). Thus, these trigrams represent the phrases “see Spot run,” which occurs 8 times (414a) in the input text file, “see Spot jump,” which occurs 10 times (414b) in the input text file, and “see Spot beg,” which occurs twice (414c) in the input text file. In another example, as shown in the trigrams416a-416cofFIG. 4, “Spot” is preceded by the word “watch.” These trigrams represent the phrases “watch Spot run,” which occurs 6 times (418a) in the input text file, “watch Spot jump,” which occurs 4 times (418b) in the input text file, and “watch Spot beg,” which occurs once (418c) in the input text file.

FIG. 5is a functional block diagram of a method of merging two exemplary count files502and504. The count files502and504are derived from two different text files, but were populated using the same list of assigned elements. Identical n-grams from the count files502and504are combined by adding their respective counts. For example, the bigram512a(run|Spot) of the count file502is identical to the bigram518a(run|Spot) of the count file504, and thus their respective counts514a(25) and520a(7) are added to result in the combined count524a(32) for the bigram522a(run|Spot) of the merged count file506. Similarly, the counts514band520bof the bigrams512band518b(jump|Spot) are added to result in the combined count524bfor the bigram522b, and the counts514cand520cof the bigram512cand518c(beg|Spot) are added to result in the combined count524cfor the bigram522c. N-grams unique to each text file are added to the merged count file506. As mentioned above, the corresponding count files of all the text files of a corpus are preferably merged in parallel.

According to one embodiment, after the n-gram count files have been merged, occurrence probability estimates are calculated for each n-gram to generate a language model. A language model includes a set of probabilities that a particular n-gram will occur in a previously unanalyzed input file (an occurrence probability). Smoothing and/or back-off algorithms are used to assign probabilities to n-grams that either were not observed in the training data or were discarded due to model size constraints, and to adjust the occurrence probabilities of the observed and saved n-grams accordingly. Smoothing provides a “smooth” (or “discounted”) probability estimate to the observed n-grams. The back-off algorithm is used to compute probabilities of unseen n-grams.

Most existing smoothing algorithms for estimation of n-gram language model probabilities can be expressed recursively as a linear interpolation of higher and lower order n-gram models (as further described in S. Chen and J. Goodman, “An empirical study of smoothing techniques for language modeling”, Center for Research in Computing Technologies, Harvard University, 1998), such as in equation 1, with a uniform 0thorder distribution:
p(wi|wi−1, . . . , wi−n+1)=p′(wi−1, . . . , wi−n+1)+y(wi−1, . . . , wi−n+1)p(wi|wi−1, . . . , wi−n+2)Equation 1. Computing n-gram probabilities by interpolating with lower order estimates.

One example smoothing algorithm suitable for this calculation is the Knesser-Ney smoothing algorithm. Another example of a popular smoothing algorithm is the Witten-Bell smoothing algorithm.

A back-off algorithm, which can be combined with smoothing, allows lower order estimates p(wi|wi−1, . . . , wi−n+2) to be used when the explicit probability p(wi|wi−1, . . . , wi−n+1) is not present. The lower order estimates are scaled with the corresponding back-off weight bow(wi−1, . . . , wi−n+1). The back-off weights are chosen such that the overall model is normalized, i.e. occurrence probabilities for every n-gram context sum to 1. This can be achieved by using equation 2:

bow⁡(wi-1,…⁢,⁢wi-n+1)=1-∑w⁢⁢p(w⁢wi-1,…⁢,⁢wi-n+1)1-∑w⁢⁢p(w⁢wi-1,…⁢,⁢wi-n+2)Equation 2. Estimation of a back-off weight for a given context involves summing over all probabilities found in that context as well as the corresponding lower-order estimates.
According to one feature, the language model described herein includes the probability estimates derived directly from the counts and also those derived from the smoothing and back-off algorithms described above.

FIG. 6is a functional block diagram of a prior art method600of generating a language model620from multiple training corpora. Prior art language models have been trained using more than one input text corpus. The method generates a set of pruned merged counts602a-602nfor each input text corpus, as described inFIG. 1. The pruned merged counts602a-602nare used to estimate language models (steps604a-604n). The language models602a-602nare estimated using n-gram probability estimates derived directly from the merged counts602a-602n, as well as those derived using smoothing and back-off algorithms to assign probabilities to unobserved or pruned n-grams. A common strategy is to build separate language models606a-606nfrom each corpus and then combine these models via linear interpolation (step610). To perform interpolation, the probability of a word wigiven context h is computed as a linear combination of the corresponding n-gram probabilities from the corpus language models606a-606n:
p(wi|h)=Σsε{606a, . . . , 606n}λsps(wi|h)
for all n-grams that are present in any of the language models606a-606n(i.e. the union of all n-grams). The resulting interpolated language model612may then be pruned (step618), e.g. using the entropy criterion (S. Chen and J. Goodman, “An empirical study of smoothing techniques for language modeling”, Center for Research in Computing Technologies, Harvard University, 1998), to meet specific model size requirements. This results in the final pruned language model620. In some embodiments, especially if the language models606a-606nare large, interpolation of several models606a-606nmay exceed the computer's physical memory, and thus each model606a-606nis pruned prior to interpolation.

FIG. 7is a functional block diagram of a method700of generating a language model according to an illustrative embodiment of the present invention. The method700provides a means for creating large interpolated language models without requiring pruning prior to interpolation. The method700begins with the provision or generation of merged counts702a-702n. Each merged count includes k merged count files704a-704kand706a-706k, which are substantially the same as the merged count files222a-222kofFIG. 2. Corpus language models712a-712nare generated in parallel at step708for each of the merged counts702a-706k. Each corpus language model712a-712nincludes k corpus language model subsets. Each corpus language model subset714a-716kcorresponds to a merged count file704a-706k. For example, the corpus language model712aincludes the corpus language model subsets714a-714k, and the corpus language model712nincludes the corpus language model subsets716a-716k. The language model subsets714a-716kare generated for each merged count using the methodology described above, treating each merged count file704a-706kas an individual merged count.

The next step in the method700is interpolation of the corpus language models712a-712n(step718). Each of the corresponding corpus language model subsets714a-716a,714b-716b, and714k-716kare interpolated in k parallel interpolation processes720a-720k. The interpolation results in an interpolated language model722comprising k interpolated language model subsets724a-724k. Optionally, the interpolated language model722is pruned (step728) by pruning each of the interpolated language model subsets724a-724k. Pruning results in a pruned language model732including k pruned language model subsets734a-734k. The resulting language model, for example the interpolated language model722or the pruned language model732, may be stored either as k individual language model subset files, or combined into a single file.

Those skilled in the art will know or be able to ascertain using no more than routine experimentation, many equivalents to the embodiments and practices described herein. Accordingly, it will be understood that the invention is not to be limited to the embodiments disclosed herein, but is to be understood from the following claims, which are to be interpreted as broadly as allowed under the law.