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

• US 7,406,416 B2
• Filed: 03/26/2004
• Issued: 07/29/2008
• Est. Priority Date: 03/26/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chelba, Ciprian, Acero, Alejandro, Mahajan, Milind
• Primary Examiner(s): Hudspeth; David R.
• Assistant Examiner(s): Rider; Justin W
• Application Number:
  US10/810,254
• Publication Number:
  US 20050216265A1
• Time in Patent Office: 1,586 Days
• Field of Search: 704/240
• US Class Current: 704/240
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

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.

Claims

1. A method of storing parameters of a deleted interpolation language model, the method comprising:

obtaining a set of parameters for the deleted interpolation language model, wherein the parameters of the deleted interpolation language model allow an N-gram probability to be determined as a linear interpolation of a relative frequency estimate for the N-gram and a probability for a lower order n-gram; and

storing at least one parameter for the deleted interpolation language model as a parameter for a backoff language model, wherein the backoff language model replaces an N-gram probability with a lower order n-gram and a backoff weight for any N-gram that cannot be located in the backoff language model.

2. The method of claim 1 wherein storing at least one parameter for a deleted interpolation language model comprises storing a relative frequency of a sequence of words as a probability for a sequence of words in the backoff language model.

3. The method of claim 2 wherein storing an interpolated probability comprises determining that a relative frequency for the sequence of words is greater than a threshold before storing the interpolated probability as a probability.

4. The method of claim 3 wherein storing a relative frequency comprises determining that the relative frequency is greater than a threshold before storing the relative frequency as a probability.

5. The method of claim 2 wherein storing an interpolated probability comprises determining that the sequence of words forms a context for an n-gram in the backoff language model before storing the interpolated probability as a probability.

6. The method of claim 1 wherein storing at least one parameter for a deleted interpolation language model comprises storing an interpolation weight for the deleted interpolation model as a backoff weight for the backoff language model.

7. The method of claim 6 wherein storing the interpolation weight further comprises storing a sequence of words associated with the interpolation weight in a same entry as the interpolation weight.

8. The method of claim 1 wherein obtaining a set of parameters comprises training a set of interpolation weights.

9. The method of claim 8 wherein training a set of interpolation weights comprises training a separate weight for each of a set of frequency count ranges.

10. The method of claim 1 wherein storing at least one parameter for the deleted interpolation language model comprises storing the at least one parameter to produce a data structure that conforms to the ARPA format for backoff language models.

11. A computer-readable storage medium having encoded thereon computer-executable instructions for performing steps comprising:

identifying a parameter for a deleted interpolation language model that forms probabilities through interpolations of values; and

placing the parameter in a data structure as a backoff parameter for a backoff language model that substitutes a weighted lower order n-gram probability for an N-gram probability when the N-gram cannot be located in the backoff language model.

12. The computer-readable storage medium of claim 11 wherein placing the parameter in a data structure comprises determining that the parameter should be included as part of the backoff language model.

13. The computer-readable storage medium of claim 12 wherein determining that the parameter should be included as part of the backoff language model comprises determining that a frequency of a sequence of words in a training text exceeds a threshold.

14. The computer-readable storage medium of claim 12 wherein determining that the parameter should be included as part of the backoff language model comprises determining that a sequence of words associated with the parameter forms a context in an n-gram stored in the data structure.

15. The computer-readable storage medium of claim 11 wherein placing a parameter in a data structure comprises placing a relative frequency as a probability for an n-gram.

16. The computer-readable storage medium of claim 11 wherein placing a parameter in a data structure comprises placing an interpolation weight as a backoff weight for a context.

17. The computer-readable storage medium of claim 11 wherein the data structure conforms to the ARPA standard for backoff language models.

18. A method for constructing a language model, the method comprising:

using deleted interpolation to train parameters for a language model;

storing at least some of the trained parameters in a data structure conforming to the ARPA format for backoff language models.

19. The method of claim 18 wherein storing at least some of the trained parameters comprises storing parameters that are associated with sequences of words that appear in a training text more than a threshold amount.

20. The method of claim 18 wherein storing at least some of the trained parameters comprises storing parameters that arc associated with sequences of words that appear as context words in an n-gram stored in the data structure.