Cluster and pruning-based language model compression

• US 6,782,357 B1
• Filed: 05/04/2000
• Issued: 08/24/2004
• Est. Priority Date: 05/04/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gao, Jianfeng, Goodman, Joshua
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/565,608
• Time in Patent Office: 1,573 Days
• Field of Search: 704/1, 704/9, 704/10, 704/255, 704/257
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

Cluster- and pruning-based language model compression is disclosed. In one embodiment, a language model is first clustered, such as by using predictive clustering. The language model after clustering has a larger size than it did before clustering. The language model is then pruned, such as by using entropy-based techniques, such as Rosenfeld pruning, or by using Stolcke pruning or count-cutoff techniques. In one particular embodiment, a word language model is first predictively clustered by a technique described as P(Z|xy)×P(z|xyZ), where a lower-case letter refers to a word, and an upper-cluster letter refers to a cluster in which the word resides.

Claims

1. A computer-implemented method for compressing a word language model comprising:

predictive clustering the word language model, such that the model after clustering has a larger size than before clustering and the word language model provides parameter values that describe the probabilities in a function P(Z|xy)×

P(z|xyz), where a lower-case letter refers to a word, and an upper-case letter refers to a cluster in which the word resides; and

,

pruning the word language model as clustered utilizing an entropy-based pruning technique.

2. The method of claim 1, wherein the entropy-based pruning technique comprises Stolcke pruning.

3. A computer-implemented method for compressing a language model comprising:

clustering the language model such that the language model provides parameter values that describe the probabilities in a function P(Z|xy)×

P(z|xyZ), where a lower-case letter refers to a word, and an upper-case letter refers to a cluster in which the word resides, such that the language model after clustering has a larger size than before clustering; and

,

pruning the language model.

4. The method of claim 3, wherein the language model comprises a word language model.

5. The method of claim 3, wherein clustering the language model comprises predictive clustering the language model.

6. The method of claim 3, wherein the model is further conditionally clustered, utilizing a technique described as P(Z|XY)×

P(Z|XYZ).

7. The method of claim 3, wherein pruning the language model comprises utilizing an entropy-based pruning technique.

8. The method of claim 7, wherein utilizing the entropy-based pruning technique comprises determining optimal pruning parameters.

9. The method of claim 7, wherein utilizing the entropy-based pruning technique comprises Stolcke pruning.

10. The method of claim 3, wherein pruning the language model comprises utilizing one of Rosenfeld pruning and a count-cutoff technique.

11. The method of claim 10, wherein pruning the language model further comprises determining optimal cutoff parameters.

12. A machine-readable medium having stored thereon data representing a language model compressed by performance of a method comprising:

clustering the language model utilizing a technique such that the language model provides parameter values that describe the probabilities in a function P(Z|XY)×

P(z|XYZ) where a lower-case letter refers to a word, and an upper-case letter refers to a cluster in which the word resides, such that the language model after clustering has a larger size than before clustering; and

pruning the language model.

13. The medium of claim 12, wherein clustering the language model further comprises predictive clustering the language model.

14. The medium of claim 13, wherein predictive clustering the language model comprises utilizing a technique described as P(Z|xy)×

P(z|xyZ), where a lower-case letter refers to a word, and an upper-case letter refers to a cluster in which the word resides.

15. The medium of claim 12, wherein pruning the language model comprises utilizing an entropy-based technique.

16. The medium of claim 15, wherein the entropy-based pruning technique comprises stolcke pruning.

17. The medium of claim 16, wherein Stolcke pruning the language model comprises determining optimal cutoff parameters.

18. The medium of claim 12, wherein pruning the language model comprises determining optimal cutoff parameters.

19. The medium of claim 12, wherein pruning the language model comprises utilizing one of:

a count-cutoff technique, and Rosenfeld pruning.

20. A machine-readable medium having data stored thereon representing a computer program designed to translate raw data into recognized data utilizing a language model, the language model compressed via performance of a method comprising:

clustering the language model utilizing a technique such that the language model provides parameter values that describe the probabilities in a function P(Z|xy)×

P(z|xyZ), where a lower-case letter refers to a word, and an upper-case letter refers to a cluster in which the word resides, such that the language model after clustering has a larger size than before clustering; and

pruning the language model.

21. The medium of claim 20, wherein clustering the language model comprises predictive clustering the language model.

22. The medium of claim 20, wherein the model is further conditionally clustered, utilizing a technique described as P(Z|XY)×

P(Z|XYZ).

23. The medium of claim 20, wherein pruning the language model comprises utilizing an entropy-based pruning technique.

24. The medium of claim 23, wherein utilizing an entropy-based pruning technique comprise determining optimal pruning parameters.

25. The medium of claim 20, wherein the entropy-based pruning technique comprises Stolcke pruning.

26. The medium of claim 20, wherein pruning the language model comprises one of:

utilizing a count-cutoff technique, and Rosenfeld pruning.

27. The medium of claim 20, wherein pruning the language model comprises utilizing a count-cutoff technique and determining optimal pruning parameters.

28. The medium of claim 20, wherein the raw data comprises raw graphical data, and the computer program comprises a handwriting recognition program.

29. The medium of claim 20, wherein the raw data comprises raw voice data, and the computer program comprises a speech recognition program.

30. A computerized system comprising:

an input device generating raw data;

a language model compressed via being first clustered utilizing a technique such that the language model provides parameter values that describe the probabilities in a function P(Z|XY)×

P(z|XYZ), where a lower-case letter refers to a word, and an upper-case letter refers to a cluster in which the word resides, such that the model after being clustered has a larger size than before being clustered, and then pruned; and

,

a computer program designed to translate the raw data into recognized data utilizing the language model.

31. The system of claim 30, wherein the language model is further predictively clustered.

32. The system of claim 30, wherein the language model is pruned utilizing an entropy-based pruning technique.

33. The system of claim 30, wherein the language model is pruned utilizing one of:

a count-cutoff technique, and Rosenfeld pruning.

34. The system of claim 30, wherein the raw data comprises raw graphical data, and the computer program comprises a handwriting recognition program.

35. The system of claim 30, wherein the raw data comprises raw voice data, and the computer program comprises a speech recognition program.

36. The system of claim 30, wherein the raw data comprises phonetic alphabet data, and the computer program comprises a program designed to convert the phonetic alphabet data to character alphabet data.

37. The system of claim 36, wherein the phonetic alphabet data comprises Chinese phonetic alphabet data.

38. The system of claim 36, wherein the phonetic alphabet data comprises Japanese phonetic alphabet data.