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

• US 9,123,336 B1
• Filed: 06/25/2013
• Issued: 09/01/2015
• 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:
  US13/926,675
• Time in Patent Office: 798 Days
• Field of Search: 704/1, 704/9, 704/10, 704270-275
• US Class Current: 1/1
• 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 are disclosed. Crowdsourcing techniques are used 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:

providing, by the data processing apparatus to a first plurality of user devices, a first user interface that includes;

a first task definition describing a first user task to generate a command sentence for an action;

a first set of non-terminal fields, each non-terminal field in the set listing a non-terminal type and a terminal that parses to the non-terminal type; and

a command sentence input field in which a user-generated command sentence is input by the user;

receiving, by the data processing apparatus and from the plurality of user devices, user-generated command sentences input into the command sentence input field;

providing, by the data processing apparatus to a second plurality of user devices, a second user interface that includes;

one of the user-generated command sentences selected from the received user-generated command sentences;

the first set of non-terminal fields, each non-terminal field in the first set listing the non-terminal type and the terminal that parses to the non-terminal type;

a second task definition describing a second user task to classify each of a plurality of n-grams of the command sentence as belonging to one of;

the non-terminal types in the set of non-terminal types;

or

none of the non-terminal types in the set of non-terminal types;

receiving, by the data processing apparatus and from the second plurality of user devices, second user task response data classifying the n-grams of the command sentence, wherein for each non-terminal type at least a respective first set of n-grams are classified as belonging to the non-terminal type and at least a second set of n-grams are classified as belonging to none of the non-terminal types;

generating, by the data processing apparatus, command grammars for the action from the second user task response data, 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.

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

3. The computer-implemented method of claim 1, wherein the command model facilitates, for each command grammar, the generation of an action score for the action from a bottom-up parse of an input sentence using the command grammar.

4. 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.

5. 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:

providing, by the data processing apparatus to a first plurality of user devices, a first user interface that includes;

a first task definition describing a first user task to generate a command sentence for an action;

a first set of non-terminal fields, each non-terminal field in the set listing a non-terminal type and a terminal that parses to the non-terminal type; and

a command sentence input field in which a user-generated command sentence is input by the user;

receiving, by the data processing apparatus and from the plurality of user devices, user-generated command sentences input into the command sentence input field;

providing, by the data processing apparatus to a second plurality of user devices, a second user interface that includes;

one of the user-generated command sentences selected from the received user-generated command sentences;

the first set of non-terminal fields, each non-terminal field in the first set listing the non-terminal type and the terminal that parses to the non-terminal type;

a second task definition describing a second user task to classify each of a plurality of n-grams of the command sentence as belonging to one of;

the non-terminal types in the set of non-terminal types;

or

none of the non-terminal types in the set of non-terminal types;

receiving, by the data processing apparatus and from the second plurality of user devices, second user task response data classifying the n-grams of the command sentence, wherein for each non-terminal type at least a respective first set of n-grams are classified as belonging to the non-terminal type and at least a second set of n-grams are classified as belonging to none of the non-terminal types;

generating, by the data processing apparatus, command grammars for the action from the second user task response data, 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.

6. The non-transitory computer readable medium of claim 5, wherein the command model facilitates, for each command grammar, the generation of an action score for the action from a bottom-up parse of an input sentence using the command grammar.

7. The non-transitory computer readable medium of claim 5, 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 non-transitory computer readable medium of claim 5, 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.

9. 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;

providing, by the data processing apparatus to a first plurality of user devices, a first user interface that includes;

a first task definition describing a first user task to generate a command sentence for an action;

a first set of non-terminal fields, each non-terminal field in the set listing a non-terminal type and a terminal that parses to the non-terminal type; and

a command sentence input field in which a user-generated command sentence is input by the user;

receiving, by the data processing apparatus and from the plurality of user devices, user-generated command sentences input into the command sentence input field;

providing, by the data processing apparatus to a second plurality of user devices, a second user interface that includes;

one of the user-generated command sentences selected from the received user-generated command sentences;

the first set of non-terminal fields, each non-terminal field in the first set listing the non-terminal type and the terminal that parses to the non-terminal type;

a second task definition describing a second user task to classify each of a plurality of n-grams of the command sentence as belonging to one of;

the non-terminal types in the set of non-terminal types;

or

none of the non-terminal types in the set of non-terminal types;

receiving, by the data processing apparatus and from the second plurality of user devices, second user task response data classifying the n-grams of the command sentence, wherein for each non-terminal type at least a respective first set of n-grams are classified as belonging to the non-terminal type and at least a second set of n-grams are classified as belonging to none of the non-terminal types;

generating, by the data processing apparatus, command grammars for the action from the second user task response data, 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.

10. The system of claim 9, wherein the command model facilitates, for each command grammar, the generation of an action score for the action from a bottom-up parse of an input sentence using the command grammar.

11. The system of claim 9, 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.

12. The system of claim 9, 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.