Probability-based approach to recognition of user-entered data

• US 9,612,669 B2
• Filed: 01/04/2016
• Issued: 04/04/2017
• Est. Priority Date: 08/05/2008
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Cecil, Matthew, Sharan, Santosh, Lachapelle, Jason
• Primary Examiner(s): COLUCCI, MICHAEL C
• Application Number:
  US14/987,065
• Publication Number:
  US 20160116994A1
• Time in Patent Office: 456 Days
• Field of Search: 704 9, 704 10, 704236, 704500, 704270, 725 40, 715810, 715257, 4555501, 455413, 4554041, 382187, 379 8801, 345172, 345169, 341 22, 200600
• 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/189 Automatic justification
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A method for entering keys in a small key pad is provided. The method comprising the steps of: providing at least a part of keyboard having a plurality of keys; and predetermining a first probability of a user striking a key among the plurality of keys. The method further uses a dictionary of selected words associated with the key pad and/or a user.

Claims

1. A computer-implemented method for text input, the method comprising:

receiving a sequence of input characters corresponding to a user actuating multiple areas of an input device;

computing a first probability for a candidate word of multiple words in a dictionary,

wherein the first probability for the candidate word is computed by combining multiple character difference probabilities,

wherein each character difference probability is computed, for each selected character in the sequence of input characters, by applying a probability distribution that indicates, for the selected character, that a character of multiple characters of the candidate word was intended when the area of the input device corresponding to the selected character was actuated;

obtaining a second probability for the candidate word,

wherein the second probability for the candidate word indicates a likelihood, independent of the sequence of input characters, of occurrence of the candidate word; and

in response to receiving the sequence of input characters, selecting the candidate word, using one or more processors, based on a combination of the first probability for the candidate word and the second probability for the candidate word.

2. The computer-implemented method of claim 1,

wherein the likelihood indicated by the second probability for the candidate word is based at least in part on one or more of:

a determination of a frequency with which the candidate word occurs,

a sentence context into which the candidate word, when selected, will be used;

a measurement of item availability, wherein the item corresponds to the candidate word;

or

any combination thereof.

3. The computer-implemented method of claim 2,

wherein the likelihood indicated by the second probability for the candidate word is based at least in part on the measurement of item availability;

and

wherein the measurement of item availability is a proportion of an item corresponding to the candidate word in an inventory.

4. The computer-implemented method of claim 1, wherein the likelihood indicated by the second probability for the candidate word is based at least in part on a grammatical rule.

5. The computer-implemented method of claim 1, wherein values in the probability distribution are customized based on one or more of:

a category associated with the user;

an analysis of input previously provided by the user;

or

any combination thereof.

6. The computer-implemented method of claim 1, wherein values in the probability distribution are customized based on:

a category associated with the user compromising handedness of the user,

wherein the user is identified as being a right-handed user; and

wherein values in the probability distribution are customized to right-handed users.

7. The computer-implemented method of claim 1,

wherein the input device is a touch screen;

and

wherein at least one of the multiple areas of the touch screen shows a representation of a keyboard key.

8. The computer-implemented method of claim 1, further comprising using a dictionary to select the candidate word.

9. The computer-implemented method of claim 1, further comprising performing a learning phase that computes values of a probability matrix used to compute the first probability, wherein the values of the probability matrix are computed based at least in part on observed user behavior.

10. The computer-implemented method of claim 1, further comprising performing a learning phase that computes values of a probability matrix used to compute the first probability, wherein the values of the probability matrix are computed based at least in part on observed user behavior,

wherein the probability matrix is an N by N matrix where N is a number of keys represented by the input device;

and

wherein an entry at position (I, J) in the probability matrix is a probability that the J^th key was intended when the I^th key was pressed.

11. A non-transitory computer-readable storage medium storing instructions that, when executed by a computing system, cause the computing system to perform operations for text input, the operations comprising:

receiving a sequence of input characters corresponding to a user actuating multiple keys represented on an input;

computing a character probability for a candidate word of multiple words in a dictionary,

wherein the character probability for the candidate word is computed by combining character difference probabilities, and

wherein each character difference probability is computed, for each selected character of multiple characters in the sequence of input characters, by applying a probability distribution that indicates, for the selected character, that a character in the candidate word was intended when the key corresponding to the selected character was actuated; and

in response to receiving the sequence of input characters, selecting the candidate word, using a processor, based on the character probability for the candidate word.

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

wherein the operations further comprise obtaining a second probability for the candidate word,

wherein the second probability for the candidate word indicates a likelihood, independent of the sequence of input characters, of occurrence of the candidate word;

and

wherein selecting the candidate word is further based on the second probability for the candidate word.

13. The computer-readable storage medium of claim 11,

wherein the operations further comprise obtaining a second probability for the candidate word,

wherein the second probability for the candidate word indicates a likelihood, independent of the sequence of input characters, of occurrence of the candidate word;

wherein selecting the candidate word is further based on the second probability for the candidate word; and

wherein the likelihood indicated by the second probability for the candidate word is based at least in part on one or more of;

a determination of a frequency with which the candidate word occurs,

a sentence context into which the candidate word, when selected, will be used;

or

any combination thereof.

14. The computer-readable storage medium of claim 11,

wherein the operations further comprise obtaining a second probability for the candidate word,

wherein the second probability for the candidate word indicates a likelihood, independent of the sequence of input characters, of occurrence of the candidate word;

wherein selecting the candidate word is further based on the second probability for the candidate word; and

wherein the likelihood indicated by the second probability for the candidate word is based at least in part on a grammatical rule.

15. The computer-readable storage medium of claim 11, wherein values in the probability distribution are customized based on one or more of:

a category assigned to the user;

an analysis of input previously provided by the user;

or

any combination thereof.

16. The computer-readable storage medium of claim 11,

wherein the probability distribution is customized for left-handed users and;

wherein the probability distribution is selected based on a determination of left-handedness of the user.

17. A system for text input comprising:

a memory;

one or more processors;

a touch screen configured to receive a sequence of input characters corresponding to a user actuating multiple virtual keys represented on the touch screen; and

a word selector configured to, using the one or more processors;

compute a probability for a candidate word of multiple words in a dictionary,

wherein the probability for the candidate word is computed by combining character difference probabilities, and

wherein each character difference probability is computed, for each selected character of multiple characters in the sequence of input characters, by applying a probability distribution that indicates, for the selected character, that a character in the candidate word was intended when the key corresponding to the selected character was actuated; and

in response to receiving the sequence of input characters, select the candidate word based on the probability for the candidate word.

18. The system of claim 17,

wherein the word selector is further configured to obtain a second probability for the candidate word,

wherein the second probability for the candidate word indicates a likelihood, independent of the sequence of input characters, of occurrence of the candidate word;

and

wherein selecting the candidate word is further based on the second probability for the candidate word.

19. The system of claim 17,

wherein the word selector is further configured to obtain a second probability for the candidate word based at least in part on a grammatical rule,

wherein the second probability for the candidate word indicates a likelihood, independent of the sequence of input characters, of occurrence of the candidate word;

and

wherein selecting the candidate word is further based on the second probability for the candidate word.

20. The system of claim 17,

wherein the probability distribution is customized for left-handed users and;

wherein the probability distribution is selected based on a determination of left-handedness of the user.