Machine learning contextual approach to word determination for text input via reduced keypad keys

• US 7,103,534 B2
• Filed: 03/31/2001
• Issued: 09/05/2006
• Est. Priority Date: 03/31/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goodman, Joshua T.
• Primary Examiner(s): Hudspeth, David
• Assistant Examiner(s): Wozniak, James S.
• Application Number:
  US09/823,619
• Publication Number:
  US 20030023420A1
• Time in Patent Office: 1,984 Days
• Field of Search: 704/9, 704/1, 704/10, 704/257, 715/529, 715/534
• US Class Current: 704/9
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

Determination of a word input on a reduced keypad, such as a numeric keypad, by entering a key sequence ambiguously corresponding to the word, by taking into account the context of the word via a machine learning approach, is disclosed. Either the left context, the right context, or the double-sided context of the number sequence can be used to determine the intended word. The machine learning approach can use a statistical language model, such as an n-gram language model. The compression of a language model for use with small devices, such as mobile phones and other types of small devices, is also disclosed.

Claims

1. A method for determining a word entered using a reduced keypad, where each of one or more keys of the reduced keypad is mapped to a plurality of letters, the method comprising:

receiving key input corresponding to the entered word and at least one of a left context and a right context;

determining a list of possible words corresponding to the key input for the entered word, wherein each listed word is in a vocabulary or previously entered into a cache;

using a language model comprising probability values corresponding to sequence of word N-grams of a natural language to rank the listed words based on at least one of the left context and the right context of the key input; and

updating the language model with additional training using words entered into the cache.

2. The method of claim 1, wherein the reduced keypad is a numeric keypad.

3. The method of claim 1, wherein the key input has at least the left context, and the word corresponding to the key input is determined based in part on the left context of the key input.

4. The method of claim 1, wherein the key input has at least the right context, and the word corresponding to the key input is determined based in part on the right context of the key input.

5. The method of claim 1, wherein the key input has both the left context and the right context, and the word corresponding to the key input is determined based both on the left context and the right context of the key input.

6. The method of claim 1, wherein using the language model comprises using a word n-gram model.

7. The method of claim 6, wherein using the n-gram model comprises using a biagram model.

8. The method of claim 1, wherein updating the language model further comprises using a cache model.

9. The method of claim 1, wherein the language model comprises a compresses language model.

10. The method of claim 1, wherein the key input has at least the left context, and wherein the word corresponding to the key input is determined based in part on the left context of the key input, and wherein using the language model comprises using a bigram model as the language model, comprising the steps:

for each listed word determining a probability of the word given the left context, and adding the word and the probability of the word to an array of word-probability pairs; and

sorting the array of word-probability pairs in decreasing order of probability.

11. The method of claim 10, wherein updating the language model comprises using a cache model in addition to using the bigram model, such that the probability of the word is determined given the left context and the words entered in the cache.

12. The method of claim 10, wherein using the bigram model further comprises:

for each word in the vocabulary that is consistent with the key input as an initial part of the word, determining a probability of the word given the left context, and, upon determining that the probability so far determined, setting the greatest probability to the probability with the greatest probability to the word;

upon determining that the greatest probability is at least a number of times greater than a word of a first word-probability pair of the array of word-probability and the greatest probability as a new first word-probability pair before the first word-probability pair within the array.

13. The method of claim 12, wherein updating the language model comprises using a cache model in addition to using the bigram model, such that the probability of the word is determined given the left context and words entered in the cache.

14. The method of claim 1, wherein the key input has both the left context and the right context and has a plurality of number sequences where each sequence corresponds to a word, the plurality of words corresponding to the key input determined by using the language model based in part on both the left context and the right context of the key input.

15. The method of claim 1, wherein the language model comprises a compressed language model, the compressed language model compresses by performing a method comprising:

smoothing an uncompressed language model; and

,

pruning the uncompresses language model to yield the compressed language model.

16. The method of claim 15, wherein pruning the uncompressed language model comprises using one of:

count-cutoffs approach, a Rosenfeld pruning approach, and a Stolcke pruning approach.

17. The method of claim 15, wherein pruning the uncompressed language model comprises determining a normalization factor for each word in the uncompressed model only prior to pruning.

18. The method of claim 15, wherein pruning the uncompressed language model accounts for ambiguous words in the uncompressed model.

19. The method of claim 15, wherein pruning the uncompressed language model accounts for an effect of the pruning on key input accuracy.

20. The method of claim 1, and further comprising executing a computer program by a processor from a computer-readable medium to perform the steps of receiving key input, determining a list of possible words, using a language model, and updating the language model.

21. A computer-readable medium having instructions stored thereon for execution by a processor to perform a method for determining a word entered using a reduced keypad, where each of one or more input keys of the reduced keypad is mapped to a plurality of letters, the method comprising:

receiving key input corresponding to the word and a left context;

for each word in a vocabulary that is consistent with the key input, determining an n-gram probability of the word given the left context, and adding the word and the n-gram of the word to an array of word-probability pairs, wherein the n-gram probabilities are stored in a language model trained at least in part on words entered in a cache, the language model comprising n-gram probabilities corresponding to sequences of words in a natural language;

determining the word corresponding to the key input as a word of a word-probability pair within the array of word-probability pairs having a greatest probability; and

updating the language model based on words previously entered into the cache.

22. The medium of claim 21, wherein the reduced keypad is a numeric keypad.

23. The medium of claim 21, wherein determining the word corresponding to the key input comprises:

sorting the array of word-probability pairs in decreasing order of probability; and

determining the word corresponding to the key input as a word of a first word-probability pair within the array of word-probability pairs.

24. The medium of claim 21, the method further initially comprising, for each word in the cache that is consistent with the key input, determining a probability of the word given the left context, and adding the word and the probability of the word to an array of word-probability pairs.

25. The medium of claim 21 the method further comprising prior to determining the word corresponding to the key input:

for each word in the vocabulary is consistent with the key input as an initial part of the word, determining a probability of the word given the left context, and, upon determining that the probability is greater than a greatest probability so far determined, setting the greatest probability to the probability and a greatest probability word associated with the greatest probability to the word;

upon determining that the greatest probability is significantly more likely than a word of a first word-probability pair of the array of word probability-pairs, adding the greatest probability word associated with the greatest probability and the greatest probability as a new first word-probability pair to the array.

26. The medium of claim 25 the method further initially comprising prior to determining the word corresponding to the key input, for each word in the cache that is consistent with the key input as an initial part of the word, determining a probability of the word given the left context, and, upon determining that the probability is greater than the greatest probability so far determined, setting the greatest probability to the probability and a greatest probability word associated with the greatest probability to the word.

27. A method for determining a word entered using a reduced keypad, wherein each of one or more keys of the reduced keypad is mapped to a plurality of letters, the method comprising:

receiving key input corresponding to the word and at least one of a left context and a right context;

determining the word corresponding to the key input by using a compressed language model based one or more of the at least one of the left context and the right context of the key input, wherein the language model comprises probabilities corresponding to N-gram word sequences of a natural language;

updating the language model with additional training using at least words previously entered in a cache; and

compressing the language model by performing the steps of;

smoothing the language model; and

pruning the language model to yield the compressed language model.

28. The method of claim 27, wherein the reduced keypad is a numeric keypad.

29. The method of claim 27, wherein pruning the uncompressed language model comprises using one of:

count-cutoffs approach, a Rosenfeld pruning approach, and a Stolcke pruning approach.

30. The method of claim 27, wherein pruning the uncompressed language model comprises determining a normalization factor for each word in the uncompressed model only prior to pruning.

31. The method of claim 27, wherein pruning the uncompressed language model accounts for ambiguous words in the uncompressed model.

32. The method of claim 27, wherein pruning the uncompressed language model accounts for an effect of the pruning on key input accuracy.

33. The method of claim 27, and further comprising executing a computer program by a processor from a computer-readable medium to perform the steps of receiving key input;

training a language model using words entered in a cache;

compressing the language model; and

determining the word corresponding to the key input.

34. An apparatus comprising:

a plurality of keys, each of one or more of the keys mapped to a plurality of letters, the plurality of keys used to enter key input corresponding to a word and at least one of a left context and a right context; and

,

a word-determining logic designed to construct a list of possible words corresponding to the entered word and ranking the listed words to determine the word corresponding to the key input by using a language model based on one or more of the at least one of the left context and the right context of the key input, wherein the language model comprises N-gram probability values corresponding to sequences of words in a natural language, and wherein the language model is updated based on words previously entered into a cache by a user.

35. The apparatus of claim 34, further comprising a display on which the at least one of the left context and the right context, and the word corresponding to the key input, are displayed.

36. The apparatus of claim 34, wherein the apparatus is a telephone.

37. The apparatus of claim 36, wherein the apparatus is a mobile telephone.

38. The apparatus of claim 36, wherein the apparatus is one of:

a cellular telephone, a corded telephone, a cordless telephone, a digital telephone, and a radio telephone.

39. The apparatus of claim 34, wherein the apparatus is one of:

a pager, a desktop computer, a laptop computer, a handheld device, a personal-digital assistance (PDA) device, and a remote control device.

40. The apparatus of claim 34, and further comprising a computer-readable medium that stores the word-determining logic comprising a computer program for execution by a processor.

41. The apparatus of claim 34, wherein the key input has at least the left context, and the word corresponding to the key input is determined by the word-determining logic by training the language model based in part on the left context of the key input.

42. The apparatus of claim 34, wherein the key input has at least the right context, and the word corresponding logic by training the language model based in part on the right context of the key input.

43. The apparatus of claim 34, wherein the key input has both the left context and the right context, and the word corresponding to the key input is determined by the word-determining logic by training the language model based in part on both the left context and the right context of the key input.

44. The apparatus of claim 34, where the word-determining logic updates the language model using a cache model.