Character and word level language models for out-of-vocabulary text input

• US 9,047,268 B2
• Filed: 02/22/2013
• Issued: 06/02/2015
• Est. Priority Date: 01/31/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ouyang, Yu, Zhai, Shumin, Chelba, Ciprian Ioan
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): Sharma, Neeraj
• Application Number:
  US13/774,656
• Publication Number:
  US 20140214405A1
• Time in Patent Office: 830 Days
• Field of Search: 345/172, 345/169, 707/10, 704/9, 704/245, 704/276, 704/254, 704/251, 704/240, 704/231, 715/773, 715/816, 715/257, 382/229
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A computing device determines, based at least in part on indications of user input, scores for a first set of candidate strings and a second set of candidate strings. Each candidate string from the first set of candidate strings is in a lexicon. Candidate strings from the second set of candidate strings are not necessarily in the lexicon. The computing device determines the scores for the first set of candidate strings based on probabilities of the candidate strings being entered. For each candidate string from the second set of candidate strings, the computing device determines the scores for the candidate string based on probabilities of characters of the candidate string being entered. The computing device selects a candidate string based on the scores for the first and second sets of candidate strings and outputs, for display at the display device, the selected candidate string.

Claims

1. A method comprising:

receiving, by a computing device, an indication of user-inputted text;

storing, by the computing device, a lexicon that includes a set of in-lexicon candidate strings and does not include a set of out-of-lexicon candidate strings, wherein each of the in-lexicon candidate strings and each of the out-of-lexicon candidate strings is a respective word in a particular language;

for each respective in-lexicon candidate string of the set of in-lexicon candidate strings, determining, by the computing device, a respective score for the respective in-lexicon candidate string, wherein;

the respective score is based at least in part on a probability of the respective in-lexicon candidate string as a whole being entered, and

the probability of the respective in-lexicon candidate string being entered is affected by a word-level context of the respective in-lexicon candidate string that includes one or more character strings that precede the respective in-lexicon candidate string in the user-inputted text;

for each respective out-of-lexicon candidate string of the set of out-of-lexicon candidate strings, determining, by the computing device, a respective score for the respective out-of-lexicon candidate string, wherein the respective score for the respective out-of-lexicon candidate string is based at least in part on respective probabilities of individual characters in the respective out-of-lexicon candidate string being entered and is not based on word-level probabilities;

determining, by the computing device and based at least in part on the scores for the in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings, a combined set of candidate strings from the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings, the combined set of candidate strings including at least one in-lexicon candidate string from the set of in-lexicon candidate strings and at least one out-of-lexicon candidate string from the set of out-of-lexicon candidate strings;

outputting, by the computing device, at least a portion of the combined set of candidate strings for display; and

responsive to an indication of a selection of a candidate string from the combined set of candidate strings, outputting, by the computing device, for display in place of the user-inputted text, the selected candidate string.

2. The method of claim 1, wherein for a particular character of a particular out-of-lexicon candidate string from the set of out-of-lexicon candidate strings, a probability of the particular character being entered is based at least in part on one or more characters that precede the particular character in the particular out-of-lexicon candidate string.

3. The method of claim 1, further comprising, for each respective out-of-lexicon candidate string of the set of out-of-lexicon candidate strings, determining, by the computing device and based at least in part on past indications of user input, the probabilities of the individual characters in the respective out-of-lexicon candidate string being entered.

4. The method of claim 1, wherein:

for each respective in-lexicon candidate string from the set of in-lexicon candidate strings, the respective score for the respective in-lexicon candidate string is based at least in part on locations indicated by indications of user input and based at least in part on the probability of the respective in-lexicon candidate string being entered; and

for each respective out-of-lexicon candidate string from the set of out-of-lexicon candidate strings, the respective score for the respective out-of-lexicon candidate string is based at least in part on the locations indicated by the indications of user input and is based at least in part on the respective probabilities of the individual characters in the respective out-of-lexicon candidate string.

5. The method of claim 4, further comprising responsive to an indication of an additional indication of user input:

re-determining, by the computing device, the scores for the in-lexicon candidate strings;

re-determining, by the computing device, the scores for the out-of-lexicon candidate strings;

re-selecting, by the computing device and based at least in part on the scores for the in-lexicon candidate strings and the out-of-lexicon candidate strings, a candidate string from among the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings; and

outputting, by the computing device, the re-selected candidate string for display.

6. The method of claim 4, wherein at least one of the indications of user input indicates a location that does not correspond to a virtual key associated with a character in a selected character string.

7. The method of claim 4, wherein the indications of user input comprise an indication of a sliding gesture at a portion of a display device that displays a virtual keyboard.

8. The method of claim 1, wherein:

determining the combined set of candidate strings comprises;

ranking, by the computing device and based at least in part on the scores for the in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings, candidate strings in the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings; and

selecting, by the computing device, a highest-ranked candidate string from the in-lexicon candidate strings and the out-of-lexicon candidate strings.

9. The method of claim 8, wherein:

the method further comprises adapting, by the computing device and based at least in part on training data, a machine learning algorithm; and

ranking the candidate strings comprises applying, by the computing device, the machine learning algorithm to rank the candidate strings based at least in part on the scores for the in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings.

10. The method of claim 8, wherein ranking the candidate strings comprises ranking, by the computing device and based at least in part on the scores of the first in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings, and based at least in part on a probability that an out-of-lexicon character string follows a preceding character string, the candidate strings, wherein the out-of-lexicon character string is not in the lexicon.

11. The method of claim 8, wherein ranking the candidate strings comprises ranking, by the computing device and based at least in part on the scores of the in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings and based at least in part on a type of an active text field, candidate strings in the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings.

12. The method of claim 11, wherein ranking the candidate strings comprises:

responsive to determining that the active text field is a first type of text field, assigning, by the computing device, a first value to relative weights associated with in-lexicon candidate strings;

responsive to determining that the active text field is a different, second type of text field, assigning, by the computing device, a different, second value to the relative weights associated with the in-lexicon candidate strings; and

ranking, by the computing device and based at least in part on the values of the relative weights associated with the in-lexicon candidate strings, the candidate strings in the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings.

13. The method of claim 1, wherein outputting at least a portion of the combined set of candidate strings comprises outputting, by the computing device and for display, a selected candidate string in place of another already-displayed character string.

14. The method of claim 1,

wherein determining the combined set of candidate strings comprises selecting, by the computing device and based at least in part on the scores for the in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings, a plurality of candidate strings from among the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings;

wherein outputting at least a portion of the combined set of candidate strings comprises outputting, by the computing device and for display, the plurality of candidate strings; and

the method further comprising;

determining, by the computing device, that an indication of user input corresponds to a selection of a particular candidate string from the plurality of candidate strings; and

outputting, by the computing device and for display, the particular candidate string in an active text area of a graphical user interface.

15. The method of claim 1, wherein:

a finite state transducer (FST) includes arcs that correspond to characters; and

determining the scores for the out-of-lexicon candidate strings comprises determining, by the computing device and based at least in part on scores associated with followed arcs in the FST, a score for a particular out-of-lexicon candidate string in the set of out-of-lexicon candidate strings, wherein the followed arcs of the FST are arcs of the FST that correspond to characters of the particular out-of-lexicon candidate string, wherein for each respective one of the followed arcs, the score that corresponds to the respective followed arc is based at least in part on a probability of the character that corresponds to the respective followed arc.

16. The method of claim 1, wherein:

a finite state transducer (FST) includes arcs that correspond to characters and terminal nodes that correspond to character strings in the lexicon; and

determining the scores for the in-lexicon candidate strings comprises;

determining, by the computing device and based at least in part on locations indicated by indications of user input, a spatial score for a particular candidate string in the lexicon;

determining, by the computing device, a word-level language model (LM) score for the particular candidate string, wherein the word-level LM score for the particular candidate string is based at least in part on a probability of the particular candidate string given one or more character strings that precede an insertion point;

determining, by the computing device and based at least in part on a number of arcs between a current node of the FST and a terminal node of the FST that corresponds to the particular candidate string, a look-ahead score for the particular candidate string; and

determining, by the computing device and based at least in part on the spatial score, the word-level LM score, and the look-ahead score, the score for the particular candidate string.

17. A computing device comprising one or more processors configured to:

receive an indication of user-inputted text;

store a lexicon that includes a set of in-lexicon candidate strings and does not include a set of out-of-lexicon candidate strings, wherein each of the in-lexicon candidate strings and each of the out-of-lexicon candidate strings is a respective word in a particular language;

for each respective in-lexicon candidate string of the set of in-lexicon candidate strings, determine a respective score for the respective in-lexicon candidate string, wherein;

the respective score for the respective in-lexicon candidate string is based at least in part on locations indicated by indications of user input and a probability of the respective in-lexicon candidate string as a whole being entered,

the probability of the respective in-lexicon candidate string being entered is affected by a word-level context of the respective in-lexicon candidate string that includes one or more words that precede the respective in-lexicon candidate string in the user-inputted text;

for each respective out-of-lexicon candidate string of the set of out-of-lexicon candidate strings, determine a respective score for the respective out-of-lexicon candidate string, wherein;

the respective score for the respective out-of-lexicon candidate string is based at least in part on the locations indicated by the indications of user input and respective probabilities of individual characters in the respective out-of-lexicon candidate string being entered and is not based on word-level probabilities;

determine, based at least in part on the scores for the in-lexicon candidate strings and the out-of-lexicon candidate strings, a combined set of candidate strings from among the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings, the combined set of candidate strings including at least one in-lexicon candidate string from the set of in-lexicon candidate strings and at least one out-of-lexicon candidate string from the set of out-of-lexicon candidate strings;

output at least a portion of the combined set of candidate strings for display; and

responsive to an indication of a selection of a candidate string from the combined set of candidate strings, output, for display in place of the user-inputted text, the selected candidate string.

18. A non-transitory computer-readable storage medium comprising instructions that, when executed by one or more processors of a computing device, configure the computing device to:

receive an indication of user-inputted text;

store a lexicon that includes a set of in-lexicon candidate strings and does not include a set of out-of-lexicon candidate strings, wherein each of the in-lexicon candidate strings and each of the out-of-lexicon candidate strings is a respective word in a particular language;

for each respective in-lexicon candidate string of the set of in-lexicon candidate strings, determine a respective score for the respective in-lexicon candidate string, wherein;

the respective score for the respective in-lexicon candidate string is based at least in part on locations indicated by indications of user input and a probability of the respective in-lexicon candidate string as a whole being entered, and

the probability of the respective in-lexicon candidate string being entered is affected by a word-level context of the respective in-lexicon candidate string that includes one or more words that precede the respective in-lexicon character string in the user-inputted text;

for each respective out-of-lexicon candidate string of the set of out-of-lexicon candidate strings, determine a respective score for the respective out-of-lexicon candidate string, wherein;

the respective score for the respective out-of-lexicon candidate string is based at least in part on one or more of the locations indicated by the indications of user input and probabilities of respective individual characters in the respective out-of-lexicon candidate string being entered,

for each respective character of the respective out-of-lexicon candidate string, the probability of the respective probability of the respective character being entered is based at least in part on one or more characters that precede the respective character, and the respective score for the out-of-lexicon candidate string is not based on a word-level context of the respective out-of-lexicon candidate string and is not based on word-level probabilities;

generate a combined set of candidate strings including at least one candidate string from the set of in-lexicon candidate strings and at least one candidate string from the set of out-of-lexicon candidate strings, wherein generating the combined set of candidate strings comprises;

ranking, based at least in part on the scores for the in-lexicon candidate strings and the out-of-lexicon candidate strings, candidate strings from the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings;

selecting, one or more highest-ranked candidate strings from among the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings; and

output the one or more highest-ranked candidate strings for display; and

responsive to an indication of a selection of a candidate string from the combined set of candidate strings, output, for display in place of the user-inputted text, the selected candidate string.