This operation produces a smoothed, normalized language model from input ngram count FST. It smooths the model in one of six ways:
bins
and discount
parameters.
bins
parameters.
See Chen and Goodman (1998) for a discussion of these smoothing methods.
All of the smoothing methods can be used to build either a mixture model (in which higher order ngram distributions are interpolated with lower order ngram distributions) or a backoff model (using the backoff option, in which lower order ngram distributions are only used if the higher order ngram was unobserved in the corpus). Even though some of the methods are typically primarily used with either mixture or backoff smoothing (e.g., Katz with backoff), in this library they can be used with either. Note that mixture models are converted to a backoff topology by presumming the mixtures and placing the mixed probability on the highest order transition.
If the bins option is left as the default (1), then the number of bins for the discounting methods (katz,absolute,kneser_ney
) are set to method appropriate defaults (5 for katz
, 1 for absolute
).
The C++ classes are all derived from the base class NGramMake
.
ngrammake [options] [in.fst [out.fst]] method: type = string, one of: witten_bell (default)  absolute  katz  kneser_ney  presmoothed  unsmoothed backoff: type = bool, default = false bins: type = int64, default = 1 witten_bell_k, type = double, default = 1.0 discount_D, type = double, default = 1.0 

class NGramAbsolute ngram(StdMutableFst *countfst); 

class NGramKatz ngram(StdMutableFst *countfst); 

class NGramKneserNey ngram(StdMutableFst *countfst); 

class NGramUnsmoothed ngram(StdMutableFst *countfst); 

class NGramWittenBell ngram(StdMutableFst *countfst); 
In addition to the C++ simple usage above, optional arguments permit the passing of nondefault values for various parameters similar to the commandline version.
$ ngrammake method=kneser_ney earnest.cnts >earnest.kn.mod
StdMutableFst *counts = StdMutableFst::Read("in.fst", true); NGramKneserNey ngram(counts); ngram.MakeNGramModel(); ngram.GetFst().Write("out.mod");
The presmoothed method normalizes at each state based on the ngram count of the history, which is only appropriate under specialized circumstances, such as when the counts have been derived from strings with backoff transitions indicated.
Carpenter, B., 2005. Scaling highorder character language models to gigabytes. In Proceedings of the ACL Workshop on Software, pages 86–99.
Chen, S., Goodman, J., 1998. An empirical study of smoothing techniques for language modeling. Technical report, TR1098, Harvard University.
Katz, S. M., 1987. Estimation of probabilities from sparse data for the language model component of a speech recogniser. IEEE Transactions on Acoustics, Speech, and Signal Processing 35 (3), 400–401.
Kneser, R., Ney, H., 1995. Improved backingoff for mgram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). pp. 181–184.
Ney, H., Essen, U., Kneser, R., 1994. On structuring probabilistic dependences in stochastic language modeling. Computer Speech and Language 8, 1–38.
Witten, I. H., Bell, T. C., 1991. The zerofrequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory 37 (4), 1085–1094.