Learning parsing rules and argument identification from crowdsourcing of proposed command inputs

• US 9,672,201 B1
• Filed: 04/27/2016
• Issued: 06/06/2017
• 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
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US15/140,133
• Time in Patent Office: 405 Days
• Field of Search: 704 1, 704 9, 704 10, 704257, 704270-275
• CPC Class Codes: G06F 3/167 Audio in a user interface, e.g. using voice commands for navigating, audio feedback
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/226 Validation
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: G10L 2015/223 Execution procedure of a spoken command

Abstract

Systems, methods and apparatus for learning parsing rules and argument identification from crowdsourcing of proposed command inputs. Crowdsourcing techniques to generate rules for parsing input sentences. A parse is used to determine whether the input sentence invokes a specific action, and if so, what arguments are to be passed to the invocation of the action.

Claims

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

accessing, by a data processing apparatus, data specifying a set of actions, each action defining a user device operation that is different from user device operations for each other action;

for each action;

accessing, by the data processing apparatus, a corresponding set of command sentences for the action, and for each command sentence, accessing user task response data classifying n-gram of the command sentence into at least a respective first set of n-grams belonging to non-terminal types and at least a second set of n-grams belonging to none of the non-terminal types;

generating, by the data processing apparatus, command grammars for the action, each of the command grammars defining non-terminals of each of the non-terminal types and at least one terminal defining at least one of the second set of n-grams; and

persisting the command grammars to a command model that facilitates, for each command grammar, the generation of an action score for the action from a parse of an input sentence using the command grammar, wherein the input sentence is a voice command phrase.

2. The computer-implemented method of claim 1, wherein:

each non-terminal type corresponds to a variable for the action; and

for each non-terminal type, a semantic yield of a non-terminal of the non-terminal type defines an argument of the variable for the action.

3. The computer-implemented method of claim 1, wherein the parse of the input sentence using the command grammar is a bottom-up parse.

4. The computer-implemented method of claim 1, wherein the command sentence is a voice command sentence.

5. The computer-implemented method of claim 1, wherein:

each non-terminal type corresponds to a variable for the action; and

for each non-terminal type, a semantic yield of a non-terminal of the non-terminal type defines an argument of the variable for the action.

6. 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, by the data processing apparatus, data specifying a set of actions, each action defining a user device operation that is different from user device operations for each other action;

for each action;

accessing, by the data processing apparatus, a corresponding set of command sentences for the action, and for each command sentence, accessing user task response data classifying n-gram of the command sentence into at least a respective first set of n-grams belonging to non-terminal types and at least a second set of n-grams belonging to none of the non-terminal types;

generating, by the data processing apparatus, command grammars for the action, each of the command grammars defining non-terminals of each of the non-terminal types and at least one terminal defining at least one of the second set of n-grams; and

persisting the command grammars to a command model that facilitates, for each command grammar, the generation of an action score for the action from a parse of an input sentence using the command grammar, wherein the input sentence is a voice command phrase.

7. The system of claim 6, wherein:

each non-terminal type corresponds to a variable for the action; and

for each non-terminal type, a semantic yield of a non-terminal of the non-terminal type defines an argument of the variable for the action.

8. The system of claim 6, wherein the parse of the input sentence using the command grammar is a bottom-up parse.

9. The system of claim 6, wherein the command sentence is a voice command sentence.

10. The system of claim 6, wherein:

each non-terminal type corresponds to a variable for the action; and

for each non-terminal type, a semantic yield of a non-terminal of the non-terminal type defines an argument of the variable for the action.

11. 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, by the data processing apparatus, data specifying a set of actions, each action defining a user device operation that is different from user device operations for each other action;

for each action;

accessing, by the data processing apparatus, a corresponding set of command sentences for the action, and for each command sentence, accessing user task response data classifying n-gram of the command sentence into at least a respective first set of n-grams belonging to non-terminal types and at least a second set of n-grams belonging to none of the non-terminal types;

generating, by the data processing apparatus, command grammars for the action, each of the command grammars defining non-terminals of each of the non-terminal types and at least one terminal defining at least one of the second set of n-grams; and

persisting the command grammars to a command model that facilitates, for each command grammar, the generation of an action score for the action from a parse of an input sentence using the command grammar, wherein the input sentence is a voice command phrase.

12. The non-transitory computer readable storage medium of claim 11, wherein:

each non-terminal type corresponds to a variable for the action; and

for each non-terminal type, a semantic yield of a non-terminal of the non-terminal type defines an argument of the variable for the action.

13. The non-transitory computer readable storage medium of claim 11, wherein the parse of the input sentence using the command grammar is a bottom-up parse.

14. The non-transitory computer readable storage medium of claim 11, wherein the command sentence is a voice command sentence.

15. The non-transitory computer readable storage medium of claim 11, wherein:

each non-terminal type corresponds to a variable for the action; and

for each non-terminal type, a semantic yield of a non-terminal of the non-terminal type defines an argument of the variable for the action.