Lattice semantic parsing

Patent metadata

Field	Value
Publication number	US-9280970-B1
Application number	US-201313926669-A
Country	US
Kind code	B1
Filing date	Jun 25, 2013
Priority date	Jun 25, 2013
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

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.

First claim

What is claimed is:

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 act

Assignees

• Google Inc

Inventors

• Uszkoreit Jakob D
• Liang Percy
• Bikel Daniel M

Classifications

• G10L15/1822 Primary

  Parsing for meaning understanding · CPC title

• G10L15/193

  Formal grammars, e.g. finite state automata, context free grammars or word networks · CPC title

• G10L15/083

  Recognition networks (G10L15/142, G10L15/16 take precedence) · CPC title