Parsing rule augmentation based on query sequence and action co-occurrence

• US 9,299,339 B1
• Filed: 06/25/2013
• Issued: 03/29/2016
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Uszkoreit, Jakob D., Liang, Percy, Bikel, Daniel M., Chelba, Ciprian I.
• Primary Examiner(s): Lerner, Martin
• Application Number:
  US13/926,795
• Time in Patent Office: 1,008 Days
• Field of Search: 704/236, 704/237, 704/243, 704/244, 704/10
• US Class Current: 1/1
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

A language processing system identifies sequential command inputs in user session data stored in logs. Each sequence command input is a first command input followed by a second command input. The system determines user actions in response to each command input. For the second command input, an action was taken at the user device in response to the command input, and there is no parsing rule associated with the action that parses to the first command input. If there is a sufficient co-occurrence of the first and second command inputs and the resulting action in the logs, then a parsing rule for the action may be augmented with a rule for the first command input.

Claims

1. A computer-implemented method performed by a data processing apparatus, the method comprising:

accessing command input logs storing data defining user device sessions;

identifying, from the command input logs, user device sessions that each respectively store;

a sequence of two or more input sentences, each input sentence being one or more n-grams, and each input sentence having a respective ordinal position in the sequence, and wherein the sequence of two or more input sentences includes at least one pair of a first input sentence that precedes a second input sentence in ordinal position in the sequence; and

data indicating a first action performed by a user device from which the user device session occurred, the first action having been performed in response to the second input sentence being successfully parsed by a parsing rule that is associated with the first action;

identifying pairs of first and second input sentences from respective user device sessions that are indicative of an augmentation signal, comprising identifying pairs of first and second input sentence for which the first action is not performed in response to the first input sentence and is performed in response to the second input sentence; and

determining, from the identified pairs of first and second input sentences, first input sentences for which a parsing rule that is associated with the first action is to be generated;

wherein the determining first input sentences for which the parsing rule that is associated with the first action is to be generated comprises, for each first input sentence;

determining a co-occurrence measure for the occurrence of first input sentence and the occurrence of the first action for the second input sentence; and

determining a parsing rule that is associated with the first action is to be generated for the first input sentence when co-occurrence measure for the first input sentence and the first action meets a threshold value.

2. The computer-implemented method of claim 1, wherein identifying pairs of first and second input sentences that are indicative of the augmentation signal from respective user device sessions comprises, for each identified pair:

determining that, in response to the second input sentence being successfully parsed by a parsing rule that is associated with the first action, a confirmation request to perform the first action was presented at the user device and a confirmation in response to the confirmation request was received at the user device.

3. The computer-implemented method of claim 2, wherein identifying pairs of first and second input sentences that are indicative of the augmentation signal from respective user device sessions further comprises, for each identified pair:

determining that a second action that is different from the first action was not performed in response to the first input sentence being successfully parsed by a parsing rule that is associated with the second action.

4. The computer-implemented method of claim 2, wherein identifying pairs of first and second input sentences that are indicative of the augmentation signal from respective user device sessions further comprises, for each identified pair:

determining the first input sentence was not successfully parsed by a parsing rule.

5. The computer-implemented method of claim 1, wherein determining the co-occurrence measure for the first input sentence comprises:

grouping first input sentences that are determined to be similar to each other; and

determining that a cardinality of the group of first input sentences meets a threshold cardinality.

6. The computer-implemented method of claim 1, wherein determining the co-occurrence measure for the first input sentence comprises:

grouping second input sentences that are determined to be similar to each other;

grouping, from the identified pairs of first and second input sentences that include a second input sentence belonging to the group of second input sentences, first input sentences that are determined to be similar to each other; and

determining that a cardinality of the group of first input sentences meets a threshold cardinality.

7. The computer-implemented method of claim 6, wherein grouping second input sentences that are determined to be similar to each other comprises grouping second input sentences that are successfully parsed by a same rule.

8. The computer-implemented method of claim 6, wherein grouping second input sentences that are determined to be similar to each other comprises grouping second input sentences that are successfully parsed rules associated with the first action.

9. The computer-implemented method of claim 1, wherein the input sentences are generated from voice command inputs.

10. The computer-implemented method of claim 1, wherein the identified pairs of first and second input sentences are a proper subset of the pairs of first and second input sentences occurring in the user device sessions.

11. The computer-implemented method of claim 1, wherein the parsing rule is a grammar based rule.

12. A non-transitory computer readable storage medium storing instructions executable by a data processing apparatus and that upon such execution causes the data processing apparatus to perform operations comprising:

accessing command input logs storing data defining user device sessions;

identifying, from the command input logs, user device sessions that each respectively store;

a sequence of two or more input sentences, each input sentence being one or more n-grams, and each input sentence having a respective ordinal position in the sequence, and wherein the sequence of two or more input sentences includes at least one pair of a first input sentence that precedes a second input sentence in ordinal position in the sequence; and

data indicating a first action performed by a user device from which the user device session occurred, the first action having been performed in response to the second input sentence being successfully parsed by a parsing rule that is associated with the first action;

identifying pairs of first and second input sentences from respective user device sessions that are indicative of an augmentation signal, comprising identifying pairs of first and second input sentence for which the first action is not performed in response to the first input sentence and is performed in response to the second input sentence; and

determining, from the identified pairs of first and second input sentences, first input sentences for which a parsing rule that is associated with the first action is to be generated;

wherein the determining first input sentences for which the parsing rule that is associated with the first action is to be generated comprises, for each first input sentence;

determining a co-occurrence measure for the occurrence of first input sentence and the occurrence of the first action for the second input sentence; and

determining a parsing rule that is associated with the first action is to be generated for the first input sentence when co-occurrence measure for the first input sentence and the first action meets a threshold value.

13. The non-transitory computer readable storage medium of claim 12, wherein identifying pairs of first and second input sentences that are indicative of the augmentation signal from respective user device sessions comprises, for each identified pair:

determining that, in response to the second input sentence being successfully parsed by a parsing rule that is associated with the first action, a confirmation request to perform the first action was presented at the user device and a confirmation in response to the confirmation request was received at the user device.

14. The non-transitory computer readable storage medium of claim 13, wherein identifying pairs of first and second input sentences that are indicative of the augmentation signal from respective user device sessions further comprises, for each identified pair:

determining that a second action that is different from the first action was not performed in response to the first input sentence being successfully parsed by a parsing rule that is associated with the second action.

15. The non-transitory computer readable storage medium of claim 13, wherein identifying pairs of first and second input sentences that are indicative of the augmentation signal from respective user device sessions further comprises, for each identified pair:

determining the first input sentence was not successfully parsed by a parsing rule.

16. The non-transitory computer readable storage medium of claim 12, wherein determining the co-occurrence measure for the first input sentence comprises:

grouping first input sentences that are determined to be similar to each other; and

determining that a cardinality of the group of first input sentences meets a threshold cardinality.

17. The non-transitory computer readable storage medium of claim 12, wherein determining the co-occurrence measure for the first input sentence comprises:

grouping second input sentences that are determined to be similar to each other;

grouping, from the identified pairs of first and second input sentences that include a second input sentence belonging to the group of second input sentences, first input sentences that are determined to be similar to each other; and

determining that a cardinality of the group of first input sentences meets a threshold cardinality.

18. The non-transitory computer readable storage medium of claim 17, wherein grouping second input sentences that are determined to be similar to each other comprises grouping second input sentences that are successfully parsed by a same rule.

19. The non-transitory computer readable storage medium of claim 17, wherein grouping second input sentences that are determined to be similar to each other comprises grouping second input sentences that are successfully parsed rules associated with the first action.

20. A system, comprising:

a data processing apparatus; and

a non-transitory computer readable storage medium in data communication with the data processing apparatus storing instructions executable by the data processing apparatus and that upon such execution causes the data processing apparatus to perform operations comprising;

accessing command input logs storing data defining user device sessions;

identifying, from the command input logs, user device sessions that each respectively store;

a sequence of two or more input sentences, each input sentence being one or more n-grams, and each input sentence having a respective ordinal position in the sequence, and wherein the sequence of two or more input sentences includes at least one pair of a first input sentence that precedes a second input sentence in ordinal position in the sequence; and

data indicating a first action performed by a user device from which the user device session occurred, the first action having been performed in response to the second input sentence being successfully parsed by a parsing rule that is associated with the first action;

identifying pairs of first and second input sentences from respective user device sessions that are indicative of an augmentation signal, comprising identifying pairs of first and second input sentence for which the first action is not performed in response to the first input sentence and is performed in response to the second input sentence; and

determining, from the identified pairs of first and second input sentences, first input sentences for which a parsing rule that is associated with the first action is to be generated;

wherein the determining first input sentences for which the parsing rule that is associated with the first action is to be generated comprises, for each first input sentence;

determining a co-occurrence measure for the occurrence of first input sentence and the occurrence of the first action for the second input sentence; and

determining a parsing rule that is associated with the first action is to be generated for the first input sentence when co-occurrence measure for the first input sentence and the first action meets a threshold value.