Parsing rule generalization by n-gram span clustering

• US 9,092,505 B1
• Filed: 06/25/2013
• Issued: 07/28/2015
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Venugopal, Ashish, Uszkoreit, Jakob D., Bikel, Daniel M.
• Primary Examiner(s): Nguyen, Cam-Linh
• Application Number:
  US13/926,591
• Time in Patent Office: 763 Days
• Field of Search: 707/737
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

A method includes accessing command sentences stored in a data store, wherein each command sentence is a collection of n-grams and each command sentence includes at least one n-gram that is a non-terminal n-gram that maps to a non-terminal type, and wherein the command sentences include non-terminal n-grams that collectively map to a plurality of different non-terminal types; for each of the non-terminal types: identifying n-gram spans; determining clusters of the n-gram spans, each cluster including n-gram spans meeting a measure of similarity of n-grams spans that belong to the cluster; and for each cluster of n-gram spans, determining, from the n-gram spans belonging to the cluster, a new non-terminal type to which the terminal n-grams of the n-gram spans map.

Claims

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

accessing command sentences stored in a data store, wherein each command sentence is a collection of n-grams and each command sentence includes at least one n-gram that is a non-terminal n-gram that maps to a non-terminal type, and wherein the command sentences include non-terminal n-grams that collectively map to a plurality of different non-terminal types;

for each of the non-terminal types;

identifying n-gram spans, each n-gram span being a proper subset of a set of n-grams that constitute a command sentence and including a non-terminal n-gram of the non-terminal type and one or more terminal n-grams that do not map to a non-terminal type;

determining clusters of the n-gram spans, each cluster including n-gram spans meeting a measure of similarity of n-grams spans that belong to the cluster; and

for each cluster of n-gram spans, determining, from the n-gram spans belonging to the cluster, a new non-terminal type to which the terminal n-grams of the n-gram spans map.

2. The computer-implemented method of claim 1, further comprising accessing sets of command grammars associated with respective actions, each respective set of command grammars associated with one respective action, each action defining a user device operation that is different from user device operations for each other action, the command grammars defining non-terminals of each of the non-terminal types and terminals;

and

wherein identifying n-gram spans comprises identifying the proper subset of n-grams consumed by a command grammar.

3. The computer-implemented method of claim 2, further comprising:

for each of the command grammars, updating the portion of the command grammar that consumed an n-gram span that belongs to a cluster for which a new non-terminal type is determined with a non-terminal of the non-terminal type in place of a terminal n-gram that maps to the non-terminal type.

4. The computer-implemented method of claim 3, wherein determining clusters of the n-gram spans for each of the non-terminal types comprises:

selecting pairs of n-grams spans;

determining a similarity measure for each pair of n-gram spans, each similarity measure being a measure of similarity of the n-gram spans in the pair of n-grams spans to each other; and

clustering the n-gram spans based on the similarity measures.

5. The computer-implemented method of claim 4, wherein clustering the n-gram spans based on the similarity measures comprises:

iteratively selecting pairs of n-gram spans in an order according to their respective similarity measures until a convergence condition is met;

after each iterative selection;

determining whether any of the n-gram spans belonging to the pair of n-gram spans belong to a cluster;

for each pair of n-gram spans for which none of the n-gram spans of the pair belong to a cluster, creating a cluster the includes the n-gram spans;

for each pair of n-gram spans for which only one of the n-gram spans belong to a cluster, adding the other n-gram span of the pair to the cluster; and

for each pair of n-gram spans for which one of the n-gram spans belong to a first cluster and the other of the n-gram spans belong to a second cluster, merging the first and second clusters.

6. The computer-implemented method of claim 4, wherein determining a similarity measure for each pair of n-gram spans comprises:

determining the similarity measure, in part, based on a frequency of contextual co-occurrence of the n-gram spans in the command sentences.

7. The computer-implemented method of claim 4, wherein determining a similarity measure for each pair of n-gram spans comprises:

determining the similarity measure, in part, based on a frequency of action co-occurrence of the n-gram spans in the command sentences, the frequency of action co-occurrence being for an action and derived from only command sentences that are associated with the action.

8. The computer-implemented method of claim 1, wherein determining clusters of the n-gram spans for each of the non-terminal types, comprises:

selecting pairs of n-grams spans;

determining a similarity measure for each pair of n-gram spans, each similarity measure being a measure of similarity of the n-gram spans in the pair of n-grams spans to each other; and

clustering the n-gram spans based on the similarity measures.

9. The computer-implemented method of claim 8, wherein clustering the n-gram spans based on the similarity measures comprises:

iteratively selecting pairs of n-gram spans in an order according to their respective similarity measures until a convergence condition is met;

after each iterative selection;

determining whether any of the n-gram spans belonging to the pair of n-gram spans belong to a cluster;

for each pair of n-gram spans for which none of the n-gram spans of the pair belong to a cluster, creating a cluster the includes the n-gram spans;

for each pair of n-gram spans for which only one of the n-gram spans belong to a cluster, adding the other n-gram span of the pair to the cluster; and

for each pair of n-gram spans for which one of the n-gram spans belong to a first cluster and the other of the n-gram spans belong to a second cluster, merging the first and second clusters.

10. The method of claim 1, wherein each n-gram is a unigram.

11. The method of claim 1, wherein the command sentences are voice command sentences.

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

accessing command sentences stored in a data store, wherein each command sentence is a collection of n-grams and each command sentence includes at least one n-gram that is a non-terminal n-gram that maps to a non-terminal type, and wherein the command sentences include non-terminal n-grams that collectively map to a plurality of different non-terminal types;

for each of the non-terminal types;

identifying n-gram spans, each n-gram span being a proper subset of a set of n-grams that constitute a command sentence and including a non-terminal n-gram of the non-terminal type and one or more terminal n-grams that do not map to a non-terminal type;

determining clusters of the n-gram spans, each cluster including n-gram spans meeting a measure of similarity of n-grams spans that belong to the cluster; and

for each cluster of n-gram spans, determining, from the n-gram spans belonging to the cluster, a new non-terminal type to which the terminal n-grams of the n-gram spans map.

13. The non-transitory computer readable storage medium of claim 12, further comprising accessing sets of command grammars associated with respective actions, each respective set of command grammars associated with one respective action, each action defining a user device operation that is different from user device operations for each other action, the command grammars defining non-terminals of each of the non-terminal types and terminals;

and

wherein identifying n-gram spans comprises identifying the proper subset of n-grams consumed by a command grammar.

14. The non-transitory computer readable storage medium of claim 12, further comprising:

for each of the command grammars, updating the portion of the command grammar that consumed an n-gram span that belongs to a cluster for which a new non-terminal type is determined with a non-terminal of the non-terminal type in place of a terminal n-gram that maps to the non-terminal type.

15. The non-transitory computer readable storage medium of claim 14, wherein determining clusters of the n-gram spans for each of the non-terminal types comprises:

selecting pairs of n-grams spans;

determining a similarity measure for each pair of n-gram spans, each similarity measure being a measure of similarity of the n-gram spans in the pair of n-grams spans to each other; and

clustering the n-gram spans based on the similarity measures.

16. The non-transitory computer readable storage medium of claim 15, wherein clustering the n-gram spans based on the similarity measures comprises:

iteratively selecting pairs of n-gram spans in an order according to their respective similarity measures until a convergence condition is met;

after each iterative selection;

determining whether any of the n-gram spans belonging to the pair of n-gram spans belong to a cluster;

for each pair of n-gram spans for which none of the n-gram spans of the pair belong to a cluster, creating a cluster the includes the n-gram spans;

for each pair of n-gram spans for which only one of the n-gram spans belong to a cluster, adding the other n-gram span of the pair to the cluster; and

for each pair of n-gram spans for which one of the n-gram spans belong to a first cluster and the other of the n-gram spans belong to a second cluster, merging the first and second clusters.

17. The non-transitory computer readable storage medium of claim 15, wherein determining a similarity measure for each pair of n-gram spans comprises:

determining the similarity measure, in part, based on a frequency of contextual co-occurrence of the n-gram spans in the command sentences.

18. The non-transitory computer readable storage medium of claim 15, wherein determining a similarity measure for each pair of n-gram spans comprises:

determining the similarity measure, in part, based on a frequency of action co-occurrence of the n-gram spans in the command sentences, the frequency of action co-occurrence being for an action and derived from only command sentences that are associated with the action.

19. The non-transitory computer readable storage medium of claim 12, wherein determining clusters of the n-gram spans for each of the non-terminal types, comprises:

selecting pairs of n-grams spans;

determining a similarity measure for each pair of n-gram spans, each similarity measure being a measure of similarity of the n-gram spans in the pair of n-grams spans to each other; and

clustering the n-gram spans based on the similarity measures.

20. The non-transitory computer readable storage medium of claim 19, wherein clustering the n-gram spans based on the similarity measures comprises:

iteratively selecting pairs of n-gram spans in an order according to their respective similarity measures until a convergence condition is met;

after each iterative selection;

determining whether any of the n-gram spans belonging to the pair of n-gram spans belong to a cluster;

for each pair of n-gram spans for which none of the n-gram spans of the pair belong to a cluster, creating a cluster the includes the n-gram spans;

for each pair of n-gram spans for which only one of the n-gram spans belong to a cluster, adding the other n-gram span of the pair to the cluster; and

for each pair of n-gram spans for which one of the n-gram spans belong to a first cluster and the other of the n-gram spans belong to a second cluster, merging the first and second clusters.

21. A system, comprising:

a data processing apparatus; and

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

accessing command sentences stored in a data store, wherein each command sentence is a collection of n-grams and each command sentence includes at least one n-gram that is a non-terminal n-gram that maps to a non-terminal type, and wherein the command sentences include non-terminal n-grams that collectively map to a plurality of different non-terminal types;

for each of the non-terminal types;

identifying n-gram spans, each n-gram span being a proper subset of a set of n-grams that constitute a command sentence and including a non-terminal n-gram of the non-terminal type and one or more terminal n-grams that do not map to a non-terminal type;

determining clusters of the n-gram spans, each cluster including n-gram spans meeting a measure of similarity of n-grams spans that belong to the cluster; and

for each cluster of n-gram spans, determining, from the n-gram spans belonging to the cluster, a new non-terminal type to which the terminal n-grams of the n-gram spans map.