TEXT SUGGESTION USING A PREDICTIVE GRAMMAR MODEL

• US 20160371250A1
• Filed: 06/16/2015
• Published: 12/22/2016
• Est. Priority Date: 06/16/2015
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: RHODES, ALEXANDER CHRISTAN
• Application Number:
  US14/740,999
• Publication Number:
  US 20160371250A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

The technology described herein can improve the operation of a computerized text entry system (e.g., keyboard, speech to text) by making grammatically correct auto-complete suggestions as a user enters text. The technology described herein builds and uses a set of generalized rules that make the auto-complete feature sensitive to the context of what has already been typed, particularly at the level of a sentence or phrase. The technology described herein receives one or more words within a partially completed sentence and outputs one or more contrastive grammatical categories that the next word may be if the final sentence is to be grammatical.

Claims

1. A method that generates an auto-complete word, the method comprising:

receiving from a user through a text input mechanism characters forming one or more words that form a first portion of a sentence;

determining a contrastive grammatical category for each of the one or more words;

identifying a phrase structure rule within a generative grammar model that starts with a sequence of contrastive grammatical categories that match the sequence of contrastive grammatical categories formed by the one or more words;

for each of a plurality of contrastive grammatical categories, determining a cost for a rightward expansion of the phrase structure rule to add a next word of an individual contrastive grammatical category to the sentence;

determining a next contrastive grammatical category for the next word in the sentence by selecting the individual contrastive grammatical category having a lowest cost of rightward expansion out of the plurality of contrastive grammatical categories; and

outputting for display to the user one or more auto-complete words within the next contrastive grammatical category.

2. The method of claim 1, wherein the method further comprises receiving a textual input comprising one or more characters that form less than all of the next word in the sentence, and wherein the one or more auto-complete words begin with the one or more characters.

3. The method of claim 1, wherein the one or more auto-complete words are received from a probabilistic language model, wherein the probabilistic language model assigns a probability that the next word is grammatically correct and the generative grammar model makes a binary decision whether a word is grammatically correct.

4. The method of claim 1, wherein the cost of rightward expansion is determined using an A* algorithm.

5. The method of claim 1, wherein cost=original cost×

greediness<sup>−

depth</sup>.

6. The method of claim 5, wherein greediness is between 1 and 5.

7. The method of claim 1, wherein the one or more words is four words.

8. A computing system comprising:

a processor;

computer storage memory;

a touchscreen display;

a composition application programmed to receive textual input from a user typing on a touchscreen keyboard displayed on the touchscreen display, the textual input comprising a first word in a sentence;

a probabilistic language model component programmed to generate a plurality of possible next words in the sentence, each word ranked according to a probability assigned by the probabilistic language model;

a generative grammar model component that is programmed to determine a contrastive grammatical category for the next word in the sentence having a lowest cost to complete a grammatical sentence;

a reordering component that is programmed to assign a new rank to the possible next words using the contrastive grammatical category and the rank assigned by the probabilistic language model; and

an auto-complete interface component that is programmed to output for display through the touchscreen display, a subset of the plurality of the possible next words in the sentence, the subset displayed in an auto-complete graphical user interface, the subset comprising words assigned above a threshold new rank.

9. The system of claim 8, wherein the auto-complete interface component is programmed to receive a selection of one of the subset of possible words and communicate the selection to the composition component.

10. The system of claim 8, wherein the lowest cost to complete a grammatical sentence is determined using a top-down approach.

11. The system of claim 8, wherein the lowest cost to complete a grammatical sentence is determined using a bottom-up approach.

12. The system of claim 8, wherein the contrastive grammatical category associated with the next word is one of several contrastive grammatical categories that could form the grammatical sentence.

13. The system of claim 12, wherein the reordering component eliminates possible next words that are not within one of several contrastive grammatical categories that could form the grammatical sentence.

14. The system of claim 8, wherein the reordering component reduces a rank of individual possible next words that are within one of several contrastive grammatical categories that could form the grammatical sentence that have above a threshold cost.

15. The system of claim 14, wherein said cost=original cost×

greediness<sup>−

depth</sup>.

16. A method of suggesting a grammatically correct auto-complete word to a user, the method comprising:

referencing a corpus of words that are each assigned to one or more contrastive grammatical categories;

referencing a corpus of grammatically correct text;

generating a corpus of normalized text by segmenting the grammatically correct text into sentences;

generating a plurality of grammatical sequences by replacing words within the corpus of normalized text with tags corresponding with the words'"'"' contrastive grammatical category within the corpus of words;

generating a plurality of rule sets by collapsing the grammatical sequences according to constituency within each grammatical sequence; and

generating a predictive generative grammar model by generalizing the plurality of rule sets using a similarity function.

17. The method of claim 16, wherein a pair of tags with the highest significance is collapsed first when generating the plurality of rule sets.

18. The method of claim 16, wherein significance of a tag sequence is the probability of the sequence AB divided by the product of the individual probabilities of A and B, where A and B are contrastive grammatical categories, and the probabilities are based on rate of occurrence within the corpus of grammatically correct text.

19. The method of claim 16, wherein the corpus of grammatically correct text is generated using one or more novels.

20. The method of claim 16, wherein a single rule is generated by collapsing a sentence comprising more than ten words in into the single rule.