Parsing rule generalization by N-gram span clustering

• US 9,489,378 B1
• Filed: 07/06/2015
• Issued: 11/08/2016
• 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:
  US14/792,112
• Time in Patent Office: 491 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, comprising:

accessing command sentences stored in a data store, wherein each command sentence is a set of n-grams that constitute the command sentence and each command sentence includes a plurality of n-grams, wherein the command sentences include n-grams that collectively map to a plurality of n-gram types;

for each of the n-gram 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 first n-grams of the n-gram type and one or more second n-grams that do not map to any of the plurality of n-gram types;

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 type to which the n-grams of the n-gram spans map.

2. The computer-implemented method of claim 1, further comprising accessing sets of parsing rules associated with respective actions, each respective set of parsing rules associated with one respective action, each action defining a user device operation that is different from user device operations for each other action, the parsing rules defining n-grams of each of the n-n-gram types and n-grams that are not of the n-gram types;

and

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

3. The computer-implemented method of claim 2, wherein determining clusters of the n-gram spans for each of the n-gram 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.

4. The computer-implemented method of claim 3, 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.

5. The computer-implemented method of claim 3, 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.

6. The computer-implemented method of claim 3, 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.

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

8. The computer-implemented method of claim 7, 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.

9. 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 set of n-grams that constitute the command sentence and each command sentence includes a plurality of n-grams, wherein the command sentences include n-grams that collectively map to a plurality of n-gram types;

for each of the n-gram 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 first n-grams of the n-gram type and one or more second n-grams that do not map to any of the plurality of n-gram types;

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 type to which the n-grams of the n-gram spans map.

10. The computer-implemented method of claim 9, further comprising accessing sets of parsing rules associated with respective actions, each respective set of parsing rules associated with one respective action, each action defining a user device operation that is different from user device operations for each other action, the parsing rules defining n-grams of each of the n-n-gram types and n-grams that are not of the n-gram types;

and

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

11. The computer-implemented method of claim 10, wherein determining clusters of the n-gram spans for each of the n-gram 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.

12. The computer-implemented method of claim 11, 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.

13. The computer-implemented method of claim 11, 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.

14. The computer-implemented method of claim 11, 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.

15. The computer-implemented method of claim 9, 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 computer-implemented method 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. 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 set of n-grams that constitute the command sentence and each command sentence includes a plurality of n-grams, wherein the command sentences include n-grams that collectively map to a plurality of n-gram types;

for each of the n-gram 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 first n-grams of the n-gram type and one or more second n-grams that do not map to any of the plurality of n-gram types;

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 type to which the n-grams of the n-gram spans map.