Lattice semantic parsing

• US 9,280,970 B1
• Filed: 06/25/2013
• Issued: 03/08/2016
• 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): Lerner, Martin
• Application Number:
  US13/926,669
• Time in Patent Office: 987 Days
• Field of Search: 704/9, 704/242, 704/252, 704/254, 704/255, 704/257, 704/275
• US Class Current: 1/1
• CPC Class Codes: G10L 15/083 Recognition networks G10L15/142, G10L15/16 take precedence
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A language processing system uses a lattice parser that semantically parses a command input represented by a lattice. The parser receives a hypotheses space of outputs as encoded in a lattice. Annotations of the input are projected back into the lattice and then lattice parsing is performed to rectify with the annotations. Parsing rules are applied to path fragments in the lattice. The rules that successfully parse from the start node to the end node of the lattice are used to determine whether the command 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:

receiving, by a data processing apparatus, lattice parse data describing a lattice parse of a command sentence input at a user device as a voice command input sentence and converted to a plurality of terms, the lattice parse data defining a plurality of N nodes and edges connecting the N nodes, each respective edge corresponding to a respective term in the command sentence and connecting a respective first node to a respective second node, wherein one of the first nodes is a source node having only one edge corresponding to a first term in the command sentence and one of the second nodes is a sink node;

annotating each respective term of an edge as one of a terminal or a non-terminal;

accessing, by the data processing apparatus, a plurality of parsing rules, each parsing rule defined by one or more constituent parsing rules and each parsing rule associated with a particular action, wherein at least some of the paring rules include constituent parsing rules that include non-terminals, and wherein each particular action is an action to be taken by the user device in response to a successful parse of a command sentence by the parsing rule;

for each of the parsing rules, determining lattice spans of two or more nodes that define corresponding term spans in the command sentence that are consumed by one or more constituent parsing rules;

for each parsing rule for which the determined lattice spans from the source node to the sink node of the lattice parse, selecting the parsing rule as a candidate parse of the command sentence;

determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence; and

causing the determined action to be performed.

2. The computer-implemented method of claim 1, wherein for each of the parsing rules, determining lattice spans of two or more nodes that define corresponding term spans in the command sentence that are consumed by one or more constituent parsing rules comprises incrementally determining lattice spans on increasing node lengths until one of a lattice span from the source node to the sink node or a failure determine a lattice span from the source node to the sink node occurs.

3. The computer-implemented method of claim 2, wherein determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence comprises:

for each candidate parse, generating an action score for the parse; and

selecting the particular action associated with the candidate parse having a highest action score relative to the actions scores for the other candidate parses.

4. The computer-implemented method of claim 3, wherein generating an action score for a candidate parse comprises:

for each lattice span determined for a candidate parse, determining a lattice parse score; and

determining the action score for the candidate parse based on the lattice parse scores.

5. The computer-implemented method of claim 4, wherein determining a lattice parse score comprises determining a score that measures a confidence of a voice to text translation of terms to which the lattice parse corresponds.

6. The computer-implemented method of claim 1, wherein determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence comprises:

for each candidate parse, generating an action score for the parse; and

selecting the particular action associated with the candidate parse having a highest action score relative to the actions scores for the other candidate parses.

7. The computer-implemented method of claim 1, wherein each parsing rule is a grammar defining one or more non-terminals and terminals, each non-terminal being of one of a plurality of entity types.

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

receiving, by a data processing apparatus, lattice parse data describing a lattice parse of a command sentence input at a user device as a voice command input sentence and converted to a plurality of terms, the lattice parse data defining a plurality of N nodes and edges connecting the N nodes, each respective edge corresponding to a respective term in the command sentence and connecting a respective first node to a respective second node, wherein one of the first nodes is a source node having only one edge corresponding to a first term in the command sentence and one of the second nodes is a sink node;

annotating each respective term of an edge as one of a terminal or a non-terminal;

accessing, by the data processing apparatus, a plurality of parsing rules, each parsing rule defined by one or more constituent parsing rules and each parsing rule associated with a particular action, wherein at least some of the paring rules include constituent parsing rules that include non-terminals, and wherein each particular action is an action to be taken by the user device in response to a successful parse of a command sentence by the parsing rule;

for each of the parsing rules, determining lattice spans of two or more nodes that define corresponding term spans in the command sentence that are consumed by one or more constituent parsing rules;

for each parsing rule for which the determined lattice spans from the source node to the sink node of the lattice parse, selecting the parsing rule as a candidate parse of the command sentence;

determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence; and

causing the determined action to be performed.

9. The non-transitory computer readable storage medium of claim 8, wherein for each of the parsing rules, determining lattice spans of two or more nodes that define corresponding term spans in the command sentence that are consumed by one or more constituent parsing rules comprises incrementally determining lattice spans on increasing node lengths until one of a lattice span from the source node to the sink node or a failure determine a lattice span from the source node to the sink node occurs.

10. The non-transitory computer readable storage medium of claim 9, wherein determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence comprises:

for each candidate parse, generating an action score for the parse; and

selecting the particular action associated with the candidate parse having a highest action score relative to the actions scores for the other candidate parses.

11. The non-transitory computer readable storage medium of claim 10, wherein generating an action score for a candidate parse comprises:

for each lattice span determined for a candidate parse, determining a lattice parse score; and

determining the action score for the candidate parse based on the lattice parse scores.

12. The non-transitory computer readable storage medium of claim 11, wherein determining a lattice parse score comprises determining a score that measures a confidence of a voice to text translation of terms to which the lattice parse corresponds.

13. The non-transitory computer readable storage medium of claim 8, wherein determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence comprises:

for each candidate parse, generating an action score for the parse; and

selecting the particular action associated with the candidate parse having a highest action score relative to the actions scores for the other candidate parses.

14. The non-transitory computer readable storage medium of claim 8, wherein each parsing rule is a grammar defining one or more non-terminals and terminals, each non-terminal being of one of a plurality of entity types.

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

data processing apparatus to perform operations comprising;

receiving, by a data processing apparatus, lattice parse data describing a lattice parse of a command sentence input at a user device as a voice command input sentence and converted to a plurality of terms, the lattice parse data defining a plurality of N nodes and edges connecting the N nodes, each respective edge corresponding to a respective term in the command sentence and connecting a respective first node to a respective second node, wherein one of the first nodes is a source node having only one edge corresponding to a first term in the command sentence and one of the second nodes is a sink node;

annotating each respective term of an edge as one of a terminal or a non-terminal;

accessing, by the data processing apparatus, a plurality of parsing rules, each parsing rule defined by one or more constituent parsing rules and each parsing rule associated with a particular action, wherein at least some of the paring rules include constituent parsing rules that include non-terminals, and wherein each particular action is an action to be taken by the user device in response to a successful parse of a command sentence by the parsing rule;

for each of the parsing rules, determining lattice spans of two or more nodes that define corresponding term spans in the command sentence that are consumed by one or more constituent parsing rules;

for each parsing rule for which the determined lattice spans from the source node to the sink node of the lattice parse, selecting the parsing rule as a candidate parse of the command sentence;

determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence; and

causing the determined action to be performed.