Trained data input system

• US 10,095,684 B2
• Filed: 03/30/2017
• Issued: 10/09/2018
• Est. Priority Date: 11/22/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Willson, Matthew James, Orr, Douglas Alexander Harper, Iso-Sipila, Juha, Fiscato, Marco
• Primary Examiner(s): ALBERTALLI, BRIAN LOUIS
• Application Number:
  US15/475,016
• Publication Number:
  US 20180143965A1
• Time in Patent Office: 558 Days
• 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/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G10L 25/30 using neural networks

Abstract

A data input system has a processor which receives user input comprising a sequence of one or more items and a language model which computes candidate next items in the sequence using the user input. A training engine trains the language model using data about a plurality of true words which a user intended to input using the data input system, and for each true word, at least one alternative candidate, being a word computed assuming imperfect entry of the true word to the data input system.

Claims

1. A data input system comprising:

a processor;

a language model implemented using the processor, which computes candidate next items in an input sequence of one or more items;

a training engine implemented using the processor which performs training of the language model using training data comprising a plurality of true words and at least one alternative candidate word for each of the plurality of true words,

wherein the plurality of true words comprises respective words intended to be input with a virtual keyboard,

wherein the at least one alternative candidate word for each true word comprises at least one word received from imperfect entry during attempted input of the true word with the virtual keyboard, and

wherein, as a result of the training, the language model is trained to reward discriminating between the plurality of true words and the at least one alternative candidate word for each of the plurality of true words.

2. The data input system of claim 1 wherein imperfect entry of the at least one word to the data input system comprises one or more of:

a corrupted entry of the at least one word, a partial entry of the at least one word, an ambiguous entry of the at least one word, an entry of the at least one word comprising noise.

3. The data input system of claim 1 wherein the language model is configured to recompute the candidate next items in response to the processor receiving additional user input comprising information about the input sequence of one or more items.

4. The data input system of claim 1 wherein the training engine optimizes a loss function and wherein the loss function comprises information about the alternative candidates.

5. The data input system of claim 1 wherein the training engine uses a sample-based discriminative loss function to train the language model.

6. The data input system of claim 1 wherein the language model is a neural network language model which takes any of the following features as input:

characters, words, n-grams.

7. The data input system of claim 1 comprising an alternative candidate generator configured to compute information about the at least one alternative candidate, the alternative candidate generator comprising an input model which generates the probability of an observed user input, given a true word.

8. The data input system of claim 7 wherein the input model is specific to any one or more of:

speech user input, text user input, a keyboard layout, a type of electronic device, a user, a group of users.

9. The data input system of claim 7 wherein the alternative candidate generator is configured to compute a probability distribution over alternative candidates using the input model.

10. The data input system of claim 9 wherein the training engine is configured to use samples from the probability distribution over alternative candidates as noise samples in a noise contrastive estimation training procedure.

11. The data input system of claim 1 comprising an alternative candidate generator implemented using the processor, the alternative candidate generator configured to compute alternative candidates by computing a similarity metric between a respective true word and items in a collection of items.

12. The data input system of claim 11 wherein the similarity metric is a string metric for measuring the difference between two strings.

13. The data input system of claim 11 wherein the similarity metric is a minimum number of single character edits to change one text item into another, interpolated with an empirical distribution over text items.

14. The data input system of claim 11 wherein the similarity metric is a minimum number of single character edits to change one text item into another, interpolated with a uniform distribution over all text items in a fixed vocabulary with the same spoken text representation as the respective true word, where the spoken text representation represents spoken text items by sound as pronounced in a spoken language so that text items which sound the same when spoken in the language have a similar representation.

15. The data input system of claim 1 wherein the training engine optimizes a loss function after having re-weighted the loss function using information about the alternative candidates.

16. A computer-implemented method performed by an electronic device, the method comprising:

receiving, at a processor, user input comprising a sequence of one or more items;

computing, using a language model, candidate next items in the sequence of one or more items;

training the language model using training data comprising a plurality of true words and at least one alternative candidate word for each of the plurality of true words,

wherein the plurality of true words comprises respective words intended to be input with a virtual keyboard,

wherein the at least one alternative candidate word for each true word comprises at least one word received from imperfect entry during attempted input of the true word with the virtual keyboard, and

wherein, as a result of the training, the language model is trained to reward discriminating between the plurality of true words and the at least one alternative candidate word for each of the plurality of true words.

17. The method of claim 16 comprising training the language model using noise contrastive estimation where the noise samples are computed as alternative candidates of true words assuming imperfect entry of the true words to the electronic device.

18. The method of claim 16 comprising using the language model to recompute the candidate next items in response to the processor receiving additional user input comprising information about the sequence of one or more items.

19. The method of claim 16 comprising computing information about the at least one alternative candidate using an input model which generates the probability of an observed user input, given a true item and where the input model is specific to any one or more of:

speech user input, text user input, a keyboard layout, a type of electronic device, a user, a group of users.

20. An electronic device comprising:

a processor which receives user input from a virtual keyboard, the user input comprising a sequence of one or more items;

a language model, implemented using the processor, which computes candidate next items in the sequence using the user input;

the language model having been trained using training data comprising a plurality of true words and at least one alternative candidate word for each of the plurality of true words,

wherein the plurality of true words comprises respective words intended to be input with the virtual keyboard,

wherein the at least one alternative candidate word for each true word comprises at least one word received from imperfect entry during attempted input of the true word with the virtual keyboard, and

wherein the language model is trained to reward discriminating between the plurality of true words and the at least one alternative candidate word for each of the plurality of true words.