NEURAL NETWORK FOR KEYBOARD INPUT DECODING

• US 20160299685A1
• Filed: 04/10/2015
• Published: 10/13/2016
• Est. Priority Date: 04/10/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Breuel, Thomas, Alsharif, Ouais, Zhai, Shumin, Ouyang, Yu, Beaufays, Francoise, Schalkwyk, Johan
• Granted Patent: US 9,678,664 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0219 Special purpose keyboards
• CPC Class Codes: G06F 3/0233 Character input methods
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• 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 3/04895 Guidance during keyboard input operation, e.g. prompting
• 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
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

In some examples, a computing device includes at least one processor; and at least one module, operable by the at least one processor to: output, for display at an output device, a graphical keyboard; receive an indication of a gesture detected at a location of a presence-sensitive input device, wherein the location of the presence-sensitive input device corresponds to a location of the output device that outputs the graphical keyboard; determine, based on at least one spatial feature of the gesture that is processed by the computing device using a neural network, at least one character string, wherein the at least one spatial feature indicates at least one physical property of the gesture; and output, for display at the output device, based at least in part on the processing of the at least one spatial feature of the gesture using the neural network, the at least one character string.

Claims

1. A computing device comprising:

at least one processor; and

at least one module, operable by the at least one processor to;

output, for display at an output device operatively coupled to the computing device, a graphical keyboard;

receive an indication of a gesture detected at a location of a presence-sensitive input device, wherein the location of the presence-sensitive input device corresponds to a location of the output device that outputs the graphical keyboard;

determine, based on a neural network processing at least one spatial feature of the gesture, at least one character string, wherein the at least one spatial feature indicates at least one physical property of the gesture; and

output, for display at the output device, the at least one character string determined based on the neural network processing of the at least one spatial feature of the gesture using the neural network.

2. The computing device of claim 1, wherein the at least one module is operable by the at least one processor to:

input, into the neural network, a plurality of input values for a plurality of features, wherein the plurality of features includes the at least one spatial feature;

apply one or more functions of the neural network to the plurality of input values; and

determine, based at least in part on the neural network, one or more output values, wherein the least one character string is determined by the computing device based at least in part on at least one of the one or more output values.

3. The computing device of claim 2, wherein:

the one or more output values are one or more first output values,

the plurality of input values is a plurality of first input values, and

wherein the at least one module is operable by the at least one processor to;

store, in the neural network, state information that is based at least in part on the one or more first output values;

input, into the neural network, a plurality of second input values for the plurality of features, wherein the plurality of second input values are determined after the plurality of first input values;

apply the one or more functions of the neural network to the plurality of second input values;

determine, based at least in part on the state information, one or more second output values; and

determine, based at least in part on at least one of the one or more second output values, a second character string.

4. The computing device of claim 2,

wherein the plurality of input values is included in cells of a input matrix, wherein each respective column vector of the input matrix comprises a respective set of input values of the plurality of input values, wherein the respective set of input values corresponds to at least one of a particular gesture or portion of a particular gesture, and

wherein the plurality of output values is included in cells of an output matrix, wherein each respective column vector of the output matrix comprises a respective set of output values of the plurality of output values, wherein the respective set of output values indicates one or more probabilities of at least one or more characters or one or more character strings.

5. The computing device of claim 2, wherein the one or more output values indicate one or more probabilities of at least one or more characters or one or more character strings, wherein the at least one module is operable by the at least one processor to:

store a graph comprising a plurality of nodes and a plurality of edges, wherein each edge is coupled to one or more of the plurality of nodes;

map, to at least one respective edge of the plurality of edges, a character and a character cost that is based at least in part on a probability of the character, wherein the probability is included in the one or more probabilities,

wherein a path, in the graph, comprising a set of edges of the plurality of edges that interconnect a set of nodes of the plurality of nodes, represents a string of characters.

6. The computing device of claim 5, wherein the at least one module is operable by the at least one processor to:

determine, based at least in part on a language model, a probability of the string of characters represented by the path; and

map, to at least one respective edge of the set of edges of the plurality of edges and based at least in part on the probability of the string of characters, a language model cost.

7. The computing device of claim 1, wherein the neural network comprises a Long Short Term Memory that includes at least one memory block.

8. The computing device of claim 1, wherein the neural network comprises a Long Short Term Memory that includes a plurality of layers of memory blocks.

9. The computing device of claim 1, wherein the at least one module is operable by the at least one processor to:

perform at least one of auto-prediction, auto-correction, or auto-completion to generate the at least one character string.

10. The computing device of claim 1, wherein the at least one module is operable by the at least one processor to:

train, based at least in part on a training set, the neural network prior to receiving the indication of the gesture detected at the location of the presence-sensitive input device.

11. The computing device of claim 1, wherein the computing device does not include a language model and a spatial model.

12. The computing device of claim 1, wherein the gesture is at least one of a tap gesture, continuous gesture, or combination of tap gesture and continuous gesture.

13. A computer-readable storage medium encoded with instructions that, when executed, cause at least one processor to:

output, for display at an output device operatively coupled to the computing device, a graphical keyboard;

receive an indication of a gesture detected at a location of a presence-sensitive input device, wherein the location of the presence-sensitive input device corresponds to a location of the output device that outputs the graphical keyboard;

determine, based on at least feature that is processed by the computing device using a neural network, at least one character string; and

output, for display at the output device, based at least in part on the processing of the at least feature that is processed by the computing device using the neural network, the at least one character string.

14. A method comprising:

outputting, by a computing device and for display at an output device operatively coupled to the computing device, a graphical keyboard;

receiving, by the computing device, an indication of a gesture detected at a location of a presence-sensitive input device, wherein the location of the presence-sensitive input device corresponds to a location of the output device that outputs the graphical keyboard;

determining, based on the gesture that is processed by the computing device using the neural network, at least one character string; and

outputting, by the computing device and for display at the output device, based at least in part on the processing of the gesture that is processed by the computing device using a neural network, the at least one character string.

15. The method of claim 14, further comprising:

inputting, into the neural network, a plurality of input values for a plurality of features, wherein the plurality of features includes the at least one spatial feature;

applying one or more functions of the neural network to the plurality of input values; and

determining, based at least in part on the neural network, one or more output values, wherein the least one character string is determined by the computing device based at least in part on at least one of the one or more output values.

16. The method of claim 15, wherein the one or more output values are one or more first output values, wherein the plurality of input values are a plurality of first input values, wherein the one or more output values are one or more first output values, wherein the method comprises:

storing, in the neural network, state information that is based at least in part on the one or more first output values;

inputting, into the neural network, a plurality of second input values for the plurality of features, wherein the plurality of second input values are determined after the plurality of first input values;

applying the one or more functions of the neural network to the plurality of second input values;

determining, based at least in part on the state information, one or more second output values; and

determining, based at least in part on at least one of the one or more second output values, a second character string.

17. The method of claim 15,

wherein the plurality of input values are included in cells of a input matrix, wherein each respective column vector of the input matrix comprises a respective set of input values of the plurality of input values, wherein the respective set of input values corresponds to at least one of a particular gesture or portion of a particular gesture, and

wherein the plurality of output values are included in cells of an output matrix, wherein each respective column vector of the output matrix comprises a respective set of output values of the plurality of output values, wherein the respective set of output values indicates one or more probabilities of at least one or more characters or one or more character strings.

18. The method of claim 15, wherein the one or more output values indicate one or more probabilities of at least one or more characters or one or more character strings, wherein the method comprises:

storing a graph comprising a plurality of nodes and a plurality of edges, wherein each edge is coupled to one or more of the plurality of nodes;

mapping, to at least one respective edge of the plurality of edges, a character and a character cost that is based at least in part on a probability of the character, wherein the probability is included in the one or more probabilities,

wherein a path, in the graph, comprising a set of edges of the plurality of edges that interconnect a set of nodes of the plurality of nodes, represents a string of characters.

19. The method of claim 18, further comprising:

determining, based at least in part on a language model, a probability of the string of characters represented by the path; and

mapping, to at least one respective edge of the set of edges of the plurality of edges and based at least in part on the probability of the string of characters, a language model cost.

20. The method of claim 14, wherein the neural network comprises a Long Short Term Memory that includes at least one memory block.

21. The method of claim 14, wherein the neural network comprises a Long Short Term Memory that includes a plurality of layers of memory blocks.

22. The method of claim 14, further comprising:

performing at least one of auto-prediction, auto-correction, or auto-completion to generate the at least one character string.

23. The method of claim 14, further comprising:

training, based at least in part on a training set, the neural network prior to receiving the indication of the gesture detected at the location of the presence-sensitive input device.

24. The method of claim 14, wherein the computing device does not include a language model and a spatial model.

25. The method of claim 14, wherein the gesture is at least one of a tap gesture, continuous gesture, or combination of tap gesture and continuous gesture.