Parsing annotator framework from external services

• US 9,183,196 B1
• Filed: 06/25/2013
• Issued: 11/10/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, Bikel, Daniel M.
• Primary Examiner(s): Neway, Samuel G
• Application Number:
  US13/926,915
• Time in Patent Office: 868 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

A language processing system uses annotation services that are external to the language processing system to identify n-grams that identify entities in an input sentence. The n-grams are annotated by the annotation services. The annotations are used to determine which n-grams, if any, correspond to instances of an entity type (e.g., values for a variable or terminals for a non-terminal). After determining which n-grams correspond to entity types, parse initializations are generated for parsing rules and parses for each rule are attempted. The rules that successfully parse are 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, the method comprising:

providing, by a data processing apparatus, a command input sentence having a plurality of n-grams to a plurality of annotation services, wherein each annotation service identifies, in the command input sentence, n-grams that identify an entity of an entity type that is particular to the annotation service, and wherein the entity type for each annotation service is different from the entity type of each other annotation service;

receiving from each annotation service annotations of n-grams in the command input sentence, each annotation identifying one or more n-grams in the command input sentence that identify an entity of the entity type particular from the annotation service;

determining, from the command input sentence and the annotations, a plurality of parsing initializations, each parsing initialization being the command input sentence and at least one of the annotations of n-grams in the command input sentence;

for each parsing initialization, parsing the command input sentence by a plurality of parsing rules, wherein;

each parsing rule is a grammar defining one or more non-terminals and terminals, each non-terminal being of one of the entity types of the annotation services and not including list of each instance of the entity type;

each parsing rule is associated with a particular action to be performed by a user device in response to a successful parse of a command input sentence by the parsing rule, and where a plurality of different actions are associated with a respective plurality of different parsing rules; and

a complete parse of the command input sentence by parsing rule occurs when the one or more terminals and non-terminals completely consumes all n-grams of the command input sentence, and a complete parse yields a successful parse, and an incomplete parse of the command input sentence does not consume all n-grams of the command input sentence and yields an unsuccessful parse; and

determining from only the parsing rules that yield a successful parse an action to be performed by a user device for the command input sentence.

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

determining each parsing initialization comprises replacing, for each annotation, the annotated n-grams of the command input sentence with a non-terminal of the entity type of the annotation service.

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

4. The computer-implemented method of claim 2, wherein determining from the parsing rules that yield a successful parse the action to be performed by a user device for the command input sentence comprises, for each grammar, the generation of an action score for the action from a bottom-up parse of the command input sentence using the grammar and a parsing initialization that matches the grammar.

5. The computer-implemented method of claim 2, 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 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 a data processing apparatus, a command input sentence having a plurality of n-grams to a plurality of annotation services, wherein each annotation service identifies, in the command input sentence, n-grams that identify an entity of an entity type that is particular to the annotation service, and wherein the entity type for each annotation service is different from the entity type of each other annotation service;

receiving from each annotation service annotations of n-grams in the command input sentence, each annotation identifying one or more n-grams in the command input sentence that identify an entity of the entity type particular from the annotation service;

determining, from the command input sentence and the annotations, a plurality of parsing initializations, each parsing initialization being the command input sentence and at least one of the annotations of n-grams in the command input sentence;

for each parsing initialization, parsing the command input sentence by a plurality of parsing rules, wherein;

each parsing rule is a grammar defining one or more non-terminals and terminals, each non-terminal being of one of the entity types of the annotation services and not including a list of each instance of the entity type;

each parsing rule is associated with a particular action to be performed by a user device in response to a successful parse of a command input sentence by the parsing rule, and where a plurality of different actions are associated with a respective plurality of different parsing rules; and

a complete parse of the command input sentence by parsing rule occurs when the one or more terminals and non-terminals completely consumes all n-grams of the command input sentence, and a complete parse yields a successful parse, and an incomplete parse of the command input sentence does not consume all n-grams of the command input sentence and yields an unsuccessful parse; and

determining from only the parsing rules that yield a successful parse an action to be performed by a user device for the command input sentence.

7. The non-transitory computer readable storage medium of claim 6, wherein:

determining each parsing initialization comprises replacing, for each annotation, the annotated n-grams of the command input sentence with a non-terminal of the entity type of the annotation service.

8. The non-transitory computer readable storage medium of claim 7, wherein the command input sentence is a voice command input sentence.

9. The non-transitory computer readable storage medium of claim 7, wherein determining from the parsing rules that yield a successful parse the action to be performed by a user device for the command input sentence comprises, for each grammar, the generation of an action score for the action from a bottom-up parse of the command input sentence using the grammar and a parsing initialization that matches the grammar.

10. The non-transitory computer readable storage medium of claim 7, 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 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 a data processing apparatus, a command input sentence having a plurality of n-grams to a plurality of annotation services, wherein each annotation service identifies, in the command input sentence, n-grams that identify an entity of an entity type that is particular to the annotation service, and wherein the entity type for each annotation service is different from the entity type of each other annotation service;

receiving from each annotation service annotations of n-grams in the command input sentence, each annotation identifying one or more n-grams in the command input sentence that identify an entity of the entity type particular from the annotation service;

determining, from the command input sentence and the annotations, a plurality of parsing initializations, each parsing initialization being the command input sentence and at least one of the annotations of n-grams in the command input sentence;

for each parsing initialization, parsing the command input sentence by a plurality of parsing rules, wherein;

each parsing rule is a grammar defining one or more non-terminals and terminals, each non-terminal being of one of the entity types of the annotation services and not including a list of each instance of the entity type;

each parsing rule is associated with a particular action to be performed by a user device in response to a successful parse of a command input sentence by the parsing rule, and where a plurality of different actions are associated with a respective plurality of different parsing rules; and

a complete parse of the command input sentence by parsing rule occurs when the one or more terminals and non-terminals completely consumes all n-grams of the command input sentence, and a complete parse yields a successful parse, and an incomplete parse of the command input sentence does not consume all n-grams of the command input sentence and yields an unsuccessful parse; and

determining from only the parsing rules that yield a successful parse an action to be performed by a user device for the command input sentence.

12. The system of claim 11, wherein:

determining each parsing initialization comprises replacing, for each annotation, the annotated n-grams of the command input sentence with a non-terminal of the entity type of the annotation service.

13. The system of claim 12, wherein the command input sentence is a voice command input sentence.

14. The system of claim 12, wherein determining from the parsing rules that yield a successful parse the action to be performed by a user device for the command input sentence comprises, for each grammar, the generation of an action score for the action from a bottom-up parse of the command input sentence using the grammar and a parsing initialization that matches the grammar.

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