System and method for joint optimization of language model performance and size

• US 7,275,029 B1
• Filed: 06/30/2000
• Issued: 09/25/2007
• Est. Priority Date: 11/05/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Mingjing, Chien, Lee-Feng, Gao, Jianfeng, Lee, Kai-Fu, Cai, Dong-Feng, Wang, Hai-Feng
• Primary Examiner(s): Edouard; Patrick N.
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US09/607,786
• Time in Patent Office: 2,643 Days
• Field of Search: 704/1, 704/4, 704/9, 704/257, 704/251, 704/10, 707/2, 707/3, 707/4
• US Class Current: 704/9
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A method for the joint optimization of language model performance and size is presented comprising developing a language model from a tuning set of information, segmenting at least a subset of a received textual corpus and calculating a perplexity value for each segment and refining the language model with one or more segments of the received corpus based, at least in part, on the calculated perplexity value for the one or more segments.

Claims

1. A method of using a tuning set of information to jointly optimize the performance and size of a language model, comprising:

providing a textual corpus comprising subsets wherein each subset comprises a plurality of items;

creating a Dynamic Order Markov Model data structure by assigning each item of the plurality of items to a node in the data structure, wherein the nodes are logically coupled to denote dependencies of the items, and calculating a frequency of occurrence for each item of the plurality of items;

segmenting at least a subset of a received textual corpus into segments by clustering every N-items of the received corpus into a training unit, wherein resultant training units are separated by gaps, and wherein N is an empirically derived value based, at least in part, on the size of the received corpus;

creating the tuning set from application-specific information;

(a) training a seed model via the tuning set;

(b) calculating a similarity within a sequence of the training units on either side of each of the gaps;

(c) selecting segment boundaries that maximize intra-segment similarity and inter-segment disparity;

(d) calculating a perplexity value for each segment based on a comparison with the seed model;

(e) selecting some of the segments based on their respective perplexity values to augment the tuning set;

iteratively refining the tuning set and the seed model by repeating steps (a) through (e) with respect to a threshold;

refining the language model based on the seed model;

generating the language model that is representative of the textual corpus for use by a host of applications; and

providing recognition of the textual corpus based on the language model.

2. A method according to claim 1, wherein the tuning set of information is comprised of one or more application-specific documents.

3. A method according to claim 1, wherein the tuning set of information is a highly accurate set of textual information linguistically relevant to, but not taken from, the received textual corpus.

4. A method according to claim 1, further comprising a training set comprised of at least the subset of the received textual corpus.

5. A method according to claim 4, further comprising:

ranking the segments of the training set based, at least in part, on the calculated perplexity value for each segment.

6. A method according to claim 1, wherein the calculation of the similarity within a sequence of training units defines a cohesion score.

7. A method according to claim 6, wherein intra-segment similarity is measured by the cohesion score.

8. A method according to claim 6, wherein inter-segment disparity is approximated from the cohesion score.

9. A method according to claim 1, wherein the calculation of inter-segment disparity defines a depth score.

10. A method according to claim 1, wherein the perplexity value is a measure of the predictive power of a certain language model to a segment of the received corpus.

11. A method according to claim 1, further comprising:

ranking the segments of at least the subset of the received corpus based, at least in part, on the calculated perplexity value of each segment; and

updating the tuning set of information with one or more of the segments from at least the subset of the received corpus.

12. A method according to claim 11, wherein one or more of the segments with the lowest perplexity value from at least the subset of the received corpus are added to the tuning set.

13. A method according to claim 1, further comprising:

utilizing the refined language model in an application to predict a likelihood of another corpus.

14. A storage medium comprising a plurality of executable instructions including at least a subset of which, when executed, implement a method according to claim 1.

15. A system comprising:

a storage medium having stored therein a plurality of executable instructions; and

an execution unit, coupled to the storage medium, to execute at least a subset of the plurality of executable instructions to implement a method according to claim 1.

16. The method as recited in claim 1, further comprising pruning the Dynamic Order Markov Model data structure.

17. A modeling agent comprising:

a controller, to receive invocation requests to develop a language model from a textual corpus comprising subsets wherein each subset comprises a plurality of items and to calculate a frequency of occurrence for each item of the plurality of items; and

a data structure generator, responsive to the controller to;

create a Dynamic Order Markov Model data structure by assigning each item of the plurality of items to a node in the data structure, wherein the nodes are logically coupled to denote dependencies of the items;

develop a seed model from a tuning set of information;

segment at least a subset of a received corpus, wherein the segments of the received corpus are a clustering of every N items of the received corpus into a training unit, wherein N is an empirically derived value based, at least in part, on the size of the received corpus, and the training units are separated by gaps;

calculate the similarity within a sequence of training units on either side of each of the gaps;

select segment boundaries that improve intra-segment similarity and inter-segment disparity;

calculate a perplexity value for each segment;

refine the seed model with one or more segments of the received corpus based, at least in part, on the calculated perplexity values;

iteratively refine the tuning set with segments ranked by the seed model and in turn iteratively update the seed model via the refined tuning set;

filter the received corpus via the seed model to find low-perplexity segments;

train the language model via the low-perplexity segments;

generate the language model that is representative of the textual corpus for use by a host of applications; and

provide recognition of the textual corpus based on the language model.

18. A modeling agent according to claim 17, wherein the tuning set is dynamically selected as relevant to the received corpus.

19. A modeling agent according to claim 17, the data structure generator comprising:

a dynamic lexicon generation function, to develop an initial lexicon from the tuning set, and to update the lexicon with select segments from the received corpus.

20. A modeling agent according to claim 17, the data structure generator comprising:

a frequency analysis function, to determine a frequency of occurrence of segments within the received corpus.

21. A modeling agent according to claim 17, the data structure generator comprising:

a dynamic segmentation function, to iteratively segment the received corpus to improve a predictive performance attribute of the modeling agent.

22. A modeling agent according to claim 21, wherein the dynamic segmentation function iteratively re-segments the received corpus until the language model reaches an acceptable threshold.

23. A modeling agent according to claim 21, the data structure generator further comprising:

a frequency analysis function, to determine a frequency of occurrence of segments within the received corpus.

24. A modeling agent according to claim 23, wherein the data structure generator selectively removes segments from the data structure that do not meet a minimum frequency threshold, and dynamically re-segments the received corpus to improve predictive capability while reducing the size of the data structure.

25. A modeling agent according to claim 17, wherein the data structure generator selectively prunes the Dynamic Order Markov Model data structure.

26. A method of jointly optimizing the performance and size of a language model, comprising:

providing a textual corpus comprising subsets wherein each subset comprises a plurality of items;

creating a Dynamic Order Markov Model data structure by assigning each item of the plurality of items to a node in the data structure, wherein the nodes are logically coupled to denote dependencies of the items, and calculating a frequency of occurrence for each item of the plurality of subsets;

segmenting one or more relatively large language corpora into multiple segments of N items, wherein N is an empirically derived value based, at least in part, on the size of the received corpus;

selecting an initial tuning sample of application-specific data, the initial tuning sample being relatively small in comparison to the one or more relatively large language corpora, wherein the initial tuning sample is used for training a seed model, the seed model to be used for ranking the multiple segments from the language corpora;

iteratively training the seed model to obtain a mature seed model, wherein the iterative training proceeds until a threshold is reached, each iteration of the training including;

updating the seed model according to the tuning sample;

ranking each of the multiple segments according to a perplexity comparison with the seed model;

selecting some of the multiple segments that possess a low perplexity; and

augmenting the tuning sample with the selected segments;

once the threshold is reached, filtering the language corpora according to the mature seed model to select low-perplexity segments;

combining data from the low-perplexity segments;

training the language model according to the combined data; and

generating the language model that is representative of the textual corpus for use by a host of applications; and

providing recognition of the textual corpus based on the language model.

27. The method as recited in claim 26, wherein the selecting an initial tuning sample comprises selecting a few application-specific documents.

28. The method as recited in claim 26, wherein the threshold comprises one of a predetermined size of the seed model or a sufficient application specificity of the seed model.

29. The method as recited in claim 26, further comprising pruning the language model utilizing an entropy based cutoff algorithm that uses only information embedded in the language model itself.

30. A storage medium comprising a plurality of executable instructions including at least a subset of which, when executed, implement a method according to claim 29.

31. The method as recited in claim 26, further comprising pruning the Dynamic Order Markov Model data structure.

32. A storage medium comprising a plurality of executable instructions including at least a subset of which, when executed, implement a method according to claim 26.