Mining data for natural language system

• US 9,047,271 B1
• Filed: 02/28/2013
• Issued: 06/02/2015
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mengibar, Pedro J. Moreno, Epstein, Mark Edward, Biadsy, Fadi
• Primary Examiner(s): BRYAR, JEREMIAH A
• Application Number:
  US13/780,757
• Time in Patent Office: 824 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 2015/223 Execution procedure of a spoken command

Abstract

A method iteratively processes data for a set of actions, including: for each action: accessing a corresponding set of command sentences for the action, determining first n-grams that are semantically relevant for the action and second n-grams that are semantically irrelevant for the action, and identifying, from a log of command sentences that includes command sentences not included in the corresponding set of command sentences, candidate command sentences that include one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram; for each candidate command sentence, determining each third n-gram that is semantically relevant for an action to be a first n-gram, and determining each third n-gram that is semantically irrelevant for an action to be a second n-gram, and adjusting the corresponding set of command sentences for each action based on the first n-grams and the second n-grams.

Claims

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

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

iteratively processing data for the set of actions until a convergence condition is met, the iterative processing comprising;

for each action, accessing a corresponding set of command sentences for the action;

for each action, determining first n-grams that are semantically relevant for the action and second n-grams that are semantically irrelevant for the action in the correspond set of command sentences;

for each action, identifying, from a log of command sentences that includes command sentences not included in the corresponding set of command sentences, candidate command sentences that include at least one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram;

for each candidate command sentence, determining each third n-gram that is semantically relevant for an action to be a first n-gram, and determining each third n-gram that is semantically irrelevant for an action to be a second n-gram; and

for each action, adjusting the corresponding set of command sentences for the action based on the first n-grams and the second n-grams; and

in response to the convergence condition being met, persisting in a computer memory device, for each action, the corresponding set of command sentences.

2. The method of claim 1, wherein for each action, adjusting the corresponding set of command sentences for the action based on the first n-grams and the second n-grams comprises:

determining a first proper subset of the first n-grams that are determined to be most semantically relevant;

determining a second proper subset of the second n-grams that are determined to be most semantically irrelevant; and

selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset.

3. The method of claim 2, wherein selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset comprises:

scoring each candidate command sentence for semantic relevance to the action; and

selecting only the candidate command sentences having scores that meet a threshold indicating a minimum semantic relevance.

4. The method of claim 2, wherein selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset comprises:

providing candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset to one or more raters; and

selecting the candidate command sentences selected by the raters as being valid command sentences for the action.

5. The method of claim 2, wherein identifying candidate command sentences that include at least one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram comprises identifying candidate command sentences that include at least one first n-gram and only one third n-gram.

6. The method of claim 5, wherein the third n-gram is a unigram.

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

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

iteratively processing data for the set of actions until a convergence condition is met, the iterative processing comprising;

for each action, accessing a corresponding set of command sentences for the action;

for each action, determining first n-grams that are semantically relevant for the action and second n-grams that are semantically irrelevant for the action in the correspond set of command sentences;

for each action, identifying, from a log of command sentences that includes command sentences not included in the corresponding set of command sentences, candidate command sentences that include at least one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram;

for each candidate command sentence, determining each third n-gram that is semantically relevant for an action to be a first n-gram, and determining each third n-gram that is semantically irrelevant for an action to be a second n-gram; and

for each action, adjusting the corresponding set of command sentences for the action based on the first n-grams and the second n-grams; and

in response to the convergence condition being met, persisting in a computer memory device, for each action, the corresponding set of command sentences.

9. The non-transitory computer storage medium of claim 8, wherein for each action, adjusting the corresponding set of command sentences for the action based on the first n-grams and the second n-grams comprises:

determining a first proper subset of the first n-grams that are determined to be most semantically relevant;

determining a second proper subset of the second n-grams that are determined to be most semantically irrelevant; and

selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset.

10. The non-transitory computer storage medium of claim 9, wherein selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset comprises:

scoring each candidate command sentence for semantic relevance to the action; and

selecting only the candidate command sentences having scores that meet a threshold indicating a minimum semantic relevance.

11. The non-transitory computer storage medium of claim 9, wherein selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset comprises:

providing candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset to one or more raters; and

selecting the candidate command sentences selected by the raters as being valid command sentences for the action.

12. The non-transitory computer storage medium of claim 9, wherein identifying candidate command sentences that include at least one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram comprises identifying candidate command sentences that include at least one first n-gram and only one third n-gram.

13. The non-transitory computer storage medium of claim 12, wherein the third n-gram is a unigram.

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

iteratively processing data for the set of actions until a convergence condition is met, the iterative processing comprising;

for each action, accessing a corresponding set of command sentences for the action;

for each action, determining first n-grams that are semantically relevant for the action and second n-grams that are semantically irrelevant for the action in the correspond set of command sentences;

for each action, identifying, from a log of command sentences that includes command sentences not included in the corresponding set of command sentences, candidate command sentences that include at least one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram;

for each candidate command sentence, determining each third n-gram that is semantically relevant for an action to be a first n-gram, and determining each third n-gram that is semantically irrelevant for an action to be a second n-gram; and

for each action, adjusting the corresponding set of command sentences for the action based on the first n-grams and the second n-grams; and

in response to the convergence condition being met, persisting in a computer memory device, for each action, the corresponding set of command sentences.

15. The system of claim 14, wherein for each action, adjusting the corresponding set of command sentences for the action based on the first n-grams and the second n-grams comprises:

determining a first proper subset of the first n-grams that are determined to be most semantically relevant;

determining a second proper subset of the second n-grams that are determined to be most semantically irrelevant; and

selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset.

16. The system of claim 15, wherein selecting second candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset comprises:

scoring each candidate command sentence for semantic relevance to the action; and

selecting only the candidate command sentences having scores that meet a threshold indicating a minimum semantic relevance.

17. The system of claim 15, wherein selecting candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset comprises:

providing candidate command sentences that include at least one first n-gram from the first proper subset and at least one second n-gram from the second proper subset to one or more raters; and

selecting the candidate command sentences selected by the raters as being valid command sentences for the action.

18. The system of claim 15, wherein identifying candidate command sentences that include at least one first n-gram and a third n-gram that has not yet been determined to be a first n-gram or a second n-gram comprises identifying candidate command sentences that include at least one first n-gram and only one third n-gram.