SEQUENCE EXPANDER FOR DATA ENTRY/INFORMATION RETRIEVAL

• US 20180143760A1
• Filed: 11/18/2016
• Published: 05/24/2018
• Est. Priority Date: 11/18/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Orr, Douglas Alexander Harper, Willson, Matthew James, Fiscato, Marco, Iso-Sipil, Juha, Osborne, Joseph, Withers, James Peter John
• Granted Patent: US 11,550,751 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 3/0233 Character input methods
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• 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: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: G06N 3/088 Non-supervised learning, e.g. competitive learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

An electronic device is described which has a user interface which receives an input comprising a sequence of target indicators of data items. The data entry system has a search component which searches for candidate expanded sequences of indicators comprising the target indicators. The search component searches amongst indicators generated by a trained conditional language model, the conditional language model having been trained using pairs, each individual pair comprising a sequence of indicators and a corresponding expanded sequence of indicators.

Claims

1. A data entry system comprising a processor and memory, the memory storing thereon computer-readable instructions that, when executed by the processor, cause the data entry system to perform operations comprising:

instantiating a user interface configured to receive an input comprising a sequence of target indicators of data items;

searching for candidate expanded sequences of indicators comprising the target indicators or translations of the target indicators;

wherein the searching comprises searching among indicators generated by a trained conditional language model trained using one or more pairs, the pairs comprising a sequence of indicators and a corresponding expanded sequence of indicators; and

rendering the candidate expanded sequences of indicators.

2. The data entry system of claim 1, wherein the conditional language model is formed using a neural network.

3. The data entry system of claim 1, wherein the searching is performed using a beam search which searches, at each place in the candidate expanded sequence of indicators, a set of indicators, the sets of indicators being found using the conditional language model.

4. The data entry system of claim 3, wherein:

the sets of indicators are found from the conditional language model;

the conditional language model comprises a neural network which comprises a sequence-to-sequence model;

further comprising inputting the target indicators to an encoder of the neural network and predicting indicators using a decoder of the neural network.

5. The data entry system of claim 1, wherein the data items comprise one or more of:

a word, an emoji, a pictogram, and an emoticon.

6. The data entry system of claim 1, wherein the user interface comprises a predictive keyboard and wherein at least one of the target indicators of data items is a word which has been corrected or completed by the predictive keyboard.

7. The data entry system of claim 1, wherein the searching is performed using a search algorithm for searching for candidate expanded sequences of indicators comprising the target indicators, the search algorithm applying a penalty based on the presence or absence of the target indicators in the candidate expanded sequences.

8. The data entry system of claim 1, wherein the searching is performed using at least one search algorithm to search for candidate expanded sequences of indicators comprising the target indicators, the search algorithm applying at least one constraint selected from:

a number of the target indicators, a sequence of the target indicators, a sequence of a subset of the target indicators, and a maximum number of indicators between target indicators.

9. The data entry system of claim 1, wherein the trained conditional language model comprises an encoder and a decoder, the encoder having been trained to generate a vector of numerical values which represent a meaning of a sequence of target indicators input to the encoder.

10. The data entry system of claim 9, wherein the encoder is a recurrent neural network and the vector of numerical values is a hidden state of the recurrent neural network.

11. The data entry system of claim 9, wherein the decoder comprises a neural network trained to receive the vector of numerical values from the encoder and to predict at least one data item.

12. The data entry system of claim 9, wherein the decoder has been trained using the pairs, each individual pair comprising a sequence of indicators and a corresponding expanded sequence of indicators.

13. The data entry system of claim 12, wherein the decoder has been trained using pairs obtained from empirically observed search query expansion data.

14. The data entry system of claim 12, wherein the decoder has been trained using pairs obtained from synthetic data computed by deleting words from sentences by detecting any one or more of:

high frequency words, words in a list of known stop-words, and words found to have high likelihood given a context of the words.

15. The data entry system of claim 1, wherein the user interface comprises a target indicator input field and a candidate expanded sequence of indicators field, and wherein the user interface comprises a toggle facility to enable a user to toggle between the target indicator input field and the candidate expanded sequence of indicators field.

16. A computer-implemented method comprising:

receiving, by a computing device, an input comprising a sequence of target indicators of data items;

using the target indicators to generate, by the computing device, indicators using a trained conditional language model, the conditional language model having been trained using pairs, the pairs comprising a sequence of indicators and a corresponding expanded sequence of indicators;

searching, by the computing device, for candidate expanded sequences of indicators comprising the target indicators or translations of the target indicators by searching amongst the indicators generated by the trained neural network; and

rendering, by the computing device, one or more of the candidate expanded sequences on a user interface communicatively coupled to the computing device.

17. The method of claim 16, further comprising using the candidate expanded sequences of indicators to facilitate data entry or information retrieval.

18. The method of claim 16, wherein the target indicators comprise emoji or pictograms and wherein the candidate expanded sequences of indicators comprise words such that the method facilitates generation of text by autistic or dyslexic users.

19. The method of claim 16, further comprising training the conditional language model using the pairs.

20. One or more computer-readable media storing thereon computer-executable instructions that, when executed by a computing system, cause the computing system to perform operations comprising:

receiving an input comprising a sequence of target indicators of data items;

using the target indicators to generate indicators using a trained conditional language model, the conditional language model having been trained using pairs, each of the pairs comprising a sequence of indicators and a corresponding expanded sequence of indicators; and

searching for candidate expanded sequences of indicators comprising the target indicators or translations of the target indicators by searching amongst the indicators generated by the trained conditional language model.