SYSTEMS AND METHODS FOR STRUCTURED STEM AND SUFFIX LANGUAGE MODELS

• US 20160275941A1
• Filed: 08/31/2015
• Published: 09/22/2016
• Est. Priority Date: 03/18/2015
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: BELLEGARDA, Jerome R., YAMAN, Sibel
• Granted Patent: US 9,899,019 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/023 Arrangements for converting discrete items of information into a coded form, e.g. arrangements for interpreting keyboard generated codes as alphanumeric codes, operand codes or instruction codes
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

Systems and methods are disclosed for predicting words using a structured stem and suffix n-gram language model. The systems and methods include determining, using a first n-gram word language model, a first probability of a stem based on a first portion of a previously-input word in the received input. Using a second n-gram language model, a second probability of a first suffix may be determined based at least on a second portion the previously-input word in the received input. Further, a third probability of a second suffix different from the first suffix may be determined using a third n-gram language model based at least on a third portion of the previously-input word in the received input. A fourth probability of a predicted word may be determined based on the first, second and third probabilities. One or more predicted words may be determined and provided as an output to the user.

Claims

1. A non-transitory computer-readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by one or more processors of an electronic device, cause the electronic device to:

receive an input from a user;

determine, using a first n-gram language model, a first probability of a stem based at least on a first portion of a previously-input word in the received input;

determine, using a second n-gram language model, a second probability of a first suffix based at least on a second portion of the previously-input word in the received input;

determine, using a third n-gram language model, a third probability of a second suffix different from the first suffix based at least on a third portion of the previously-input word in the received input;

determine a fourth probability of at least one predicted word based on the first probability, the second probability and the third probability; and

provide an output of the at least one predicted word to the user based on the fourth probability.

2. The non-transitory computer-readable storage medium of claim 1, wherein to determine, using the third n-gram language model, the third probability of the second suffix different from the first suffix, the one or more program comprise instructions that cause the electronic device to determine, using a tense suffix n-gram language model, the third probability of a tense suffix based at least in part on a second tense suffix of the previously-input word.

3. The non-transitory computer-readable storage medium of claim 2, wherein determining the third probability of the tense suffix is further based at least in part on one or more unstemmed words including a temporal adverb.

4. The non-transitory computer-readable storage medium of claim 2, wherein the one or more program comprise instructions that cause the electronic device to perform a part-of-speech analysis on the previously-input word.

5. The non-transitory computer-readable storage medium of claim 2, wherein the one or more program comprise instructions that cause the electronic device to train the third n-gram language model based at least in part on a first dataset including filtered data expurgated from all stems, non-tense suffixes and non-information bearing words.

6. The non-transitory computer-readable storage medium of claim 1, wherein to determine, using the second n-gram language model, the second probability of the first suffix, the one or more program comprise instructions that cause the electronic device to determine, using a person suffix n-gram language model, the second probability of a person suffix based at least in part on a second person suffix and an unstemmed word of the previously-input word.

7. The non-transitory computer-readable storage medium of claim 6, wherein the one or more program comprise instructions that cause the electronic device to train the second n-gram language model based at least in part on a second dataset including stem and suffix data expurgated from all stems and non-person suffixes.

8. The non-transitory computer-readable storage medium of claim 1, wherein to determine, using the first n-gram language model, the first probability of the stem, the one or more program comprise instructions that cause the electronic device to determine, using a word stem n-gram language model, the first probability of the stem based at least in part on a second stem and an unstemmed word of the previously-input word.

9. The non-transitory computer-readable storage medium of claim 8, wherein the one or more program comprise instructions that cause the electronic device to train the first n-gram language model based at least in part on a second dataset including stem and suffix data expurgated from all suffixes.

10. The non-transitory computer-readable storage medium of claim 1, wherein the first n-gram language model, the second n-gram language model, and the third n-gram language model are non-contiguous.

11. The non-transitory computer-readable storage medium of claim 1, wherein the at least one predicted word includes the stem, a person suffix and a tense suffix.

12. The non-transitory computer-readable storage medium of claim 11,

wherein the first suffix is a person suffix and the second suffix is a tense suffix;

wherein the stem is associated with a stem category, and

wherein the stem category is associated with one or more suffixes including a second person suffix and a second tense suffix,

13. The non-transitory computer-readable storage medium of claim 12, wherein the one or more program comprise instructions that cause the electronic device to:

determine whether the person suffix and the tense suffix match the second person suffix and the second tense suffix; and

forego output of the predicted word in response to determining that the person suffix and the tense suffix do not match the second person suffix and the second tense suffix.

14. The non-transitory computer-readable storage medium of claim 1, wherein the one or more program comprise instructions that cause the electronic device to determine one or both of a case and an object of the previously-input word, and

wherein determining the second probability of the first suffix and the third probability of the second suffix using a respective one of the second n-gram language model or the third n-gram language model is further based on one or both of the case and the object.

15. The non-transitory computer-readable storage medium of claim 1, wherein to determine the fourth probability of the at least one predicted word, the one or more program comprise instructions that cause the electronic device to determine, based on the first probability, the second probability and the third probability, the probability of the at least one predicted word based on two or more words in the input.

16. The non-transitory computer-readable storage medium of claim 15, wherein the two or more words includes a string of recently entered words.

17. The non-transitory computer-readable storage medium of claim 1, wherein the received input is a typed input.

18. The non-transitory computer-readable storage medium of claim 1, wherein the received input is a voice input.

19. The non-transitory computer-readable storage medium of claim 1, wherein to provide the output of the at least one predicted word to the user, the one or more program comprise instructions that cause the electronic device to display the predicted word.

20. The non-transitory computer-readable storage medium of claim 1, wherein to provide the output of the at least one predicted word, the one or more program comprise instructions that cause the electronic device to provide an audible playback of the predicted word.

21. A method, comprising:

at an electronic device;

receiving an input from a user;

determining, using a first n-gram language model, a first probability of a stem based at least on a first portion of a previously-input word in the received input;

determining, using a second n-gram language model, a second probability of a first suffix based at least on a second portion of the previously-input word in the received input;

determining, using a third n-gram language model, a third probability of a second suffix different from the first suffix based at least on a third portion of the previously-input word in the received input;

determining a fourth probability of at least one predicted word based on the first probability, the second probability and the third probability; and

providing an output of the at least one predicted word to the user based on the fourth probability.

22. An electronic device comprising:

one or more processors;

a memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

receiving an input from a user;

determining, using a first n-gram language model, a first probability of a stem based at least on a first portion of a previously-input word in the received input;

determining, using a second n-gram language model, a second probability of a first suffix based at least on a second portion of the previously-input word in the received input;

determining, using a third n-gram language model, a third probability of a second suffix different from the first suffix based at least on a third portion of the previously-input word in the received input;

determining a fourth probability of at least one predicted word based on the first probability, the second probability and the third probability; and

providing an output of the at least one predicted word to the user based on the fourth probability.