System and iterative method for lexicon, segmentation and language model joint optimization

• US 6,904,402 B1
• Filed: 06/30/2000
• Issued: 06/07/2005
• Est. Priority Date: 11/05/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Di, Shuo, Chien, Lee-Feng, Gao, Jianfeng, Huang, Chang-Ning, Cai, Dong-Feng, Wang, Hai-Feng, Lee, Kai-Fu
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/609,202
• Time in Patent Office: 1,803 Days
• Field of Search: 704/9, 704/257, 704/235, 704/1, 704/10, 704/255, 707/5
• US Class Current: 704/10
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

A method for optimizing a language model is presented comprising developing an initial language model from a lexicon and segmentation derived from a received corpus using a maximum match technique, and iteratively refining the initial language model by dynamically updating the lexicon and re-segmenting the corpus according to statistical principles until a threshold of predictive capability is achieved.

Claims

1. A method comprising:

developing an initial language model from a lexicon and segmentation derived from a received corpus; and

iteratively refining the initial language model by dynamically updating the lexicon and re-segmenting the corpus according to statistical principles until a threshold of predictive capability is achieved;

wherein;

iteratively refining the language model comprises;

re-segmenting the corpus by determining, for each segment, a probability of occurrence for that segment; and

updating the lexicon from the re-segmented corpus;

updating the lexicon comprises;

identifying a frequency of occurrence for each word of a lexicon in the received corpus; and

deleting the word with the smallest identified frequency from the lexicon; and

the method further comprises re-segmenting the deleted word into two or more smaller words and updating the lexicon with the re-segmented words.

2. A method according to claim 1, wherein developing an initial language model comprises:

generating a prefix tree data structure from items dissected from the received corpus;

identifying sub-strings of N items or less from the prefix tree data structure; and

populating the lexicon with the identified sub-strings.

3. A method according to claim 2, wherein N is equal to three (3).

4. A method according to claim 1, wherein determining the probability of occurrence for a segment is calculated using an N-gram language model.

5. A method according to claim 4, wherein the N-gram language model is a tri-gram language model.

6. A method according to claim 1, wherein determining the probability of occurrence for a segment is calculated using two prior segments.

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

determining whether the predictive capability of the language model improved as a result of the steps of updating and re-segmenting; and

performing additional updating and re-segmenting if the predictive capability improved until no further improvement is identified.

8. A method according to claim 1, wherein predictive capability is quantitatively expressed as a perplexity measure.

9. A method according to claim 8, wherein the language model is refined until the perplexity measure is reduced below an acceptable predictive threshold.

10. A method according to claim 1, further comprising utilizing the iteratively refined language model in an application to predict a likelihood of another corpus, wherein the application is one or more of a spelling and/or grammatical checker, a word-processing application, a language translation application, a speech recognition application, and the like.

11. 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.

12. A computer system comprising:

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

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

13. A storage medium comprising a plurality of executable instructions including at least a subset of which, when executed, implement the method according to claim 1, wherein developing the initial language model:

generates a prefix tree data structure from items dissected from the received corpus;

identifies sub-strings of N items or less from the prefix tree; and

populates the lexicon with the identified sub-strings.