N-gram model smoothing with independently controllable parameters
AssigneeMicrosoft Technology Licensing, LLC
InventorRobert Carter Moore
Life of this patent
Estimating the term…
Abstract
Described is a technology by which a probability is estimated for a token in a sequence of tokens based upon a number of zero or more times (actual counts) that the sequence was observed in training data. The token may be a word in a word sequence, and the estimated probability may be used in a statistical language model. A discount parameter is set independently of interpolation parameters. If the sequence was observed at least once in the training data, a discount probability and an interpolation probability are computed and summed to provide the estimated probability. If the sequence was not observed, the probability is estimated by computing a backoff probability. Also described are various ways to obtain the discount parameter and interpolation parameters.
Claims20
In a machine translation system or a speech recognition system, a method performed on at least one processor, comprising, processing an output candidate comprising a sequence of tokens for natural language input, including estimating an estimated probability for a token in the sequence of tokens based upon actual counts corresponding to a number of zero or more times that the sequence was observed in training data, including controlling interpolation parameters independently from controlling a discount parameter, and when the sequence was observed at least once, computing a discount probability based upon the discount parameter subtracted from a maximum likelihood probability estimate that is based upon a context corresponding to the sequence, computing an interpolation probability based upon one interpolation parameter and a smaller other context corresponding to the sequence, mathematically combining the discount probability with the interpolation probability to provide the estimated probability, and using the estimated probability to generate an alternative output for at least a portion of the natural language input.
One or more computer-readable storage devices having computer-executable instructions, which when executed perform steps, comprising, performing machine translation or speech recognition on natural language input by estimating a probability for a token in a natural language sequence of n tokens based upon a number of times the token was observed in training data following a natural language sequence of n−1 tokens using actual counts, including, when the number of times is greater than zero, computing the probability based upon count data, a discount parameter and interpolation weights in which the interpolation weights are not determined from the discount parameter and are computed based upon a smaller context than the natural language sequence of n−1 tokens, correcting the estimated probability for the token representing at least one output candidate for the natural language input by mathematically combining the discount probability with the interpolation probability to provide the estimated probability, and when the number of times is zero, computing the probability based upon a backoff weight.
A machine translation system or a speech recognition having one or more computer-readable storage devices having computer-executable instructions, which when executed perform steps, comprising:
- precomputing n-Gram probability estimates for natural language sequences that occur in a training corpus up to length n based upon actual counts, a discount parameter and an interpolation parameter, in which the discount parameter and the interpolation parameter are independently controllable, the discount parameter and the interpolation parameter to correct for overestimation and quantization, respectively, when smoothing the n-Gram probability estimates;
- storing the probability estimates in a probability estimates data structure;
- precomputing backoff weights for contexts that occur in the training corpus up to length n−1 in which the backoff weights are dependent only upon the contexts;
- storing the backoff weights in a backoff weights data structure;
- processing an output candidate for each token in a sequence of tokes corresponding to natural language input using providing an estimated probability for the token in a sequence of tokens, including by determining whether the sequence was observed in the training data, and
- if so, providing the estimated probability from the probability estimates data structure and
- if not, retrieving one or more precomputed backoff weights from the backoff weights data structure, retrieving one or more lower order probability estimates from the probability estimates data structure, and providing the estimated probability by computing a probability using the one or more retrieved backoff weights and one or more lower order probability estimates;
- and
- outputting natural language text based upon the estimated probability of each token.
Dependencies are inferred from the claim text.