Natural language translation techniques
First Claim
Patent Images
1. A computer program product for translating natural language input to a machine-readable format for processing by a knowledge base, the computer program product comprising one or more non-transitory computer-readable media having computer program instructions stored therein, the computer program instructions being configured such that, when executed, the computer program instructions cause one or more computing devices to:
- receive a text string derived from natural language input;
generate an input graph for the text string, the input graph representing a plurality of different subsets of words in the text string;
retrieve a template graph representing a plurality of translation templates associated with the knowledge base, each translation template being for translating matching natural language input to the machine-readable format, and each translation template corresponding to at least one of a plurality of terminal nodes in the template graph, wherein each terminal node of the template graph has an associated template priority that is based on the corresponding translation template, and wherein each internal node of the template graph is labeled with an identifier of a highest priority template that can be reached from that point in the template graph;
generate an intersection graph from the input graph and the template graph, each node in the intersection graph representing a tuple of corresponding nodes in the input and template graphs;
process the intersection graph to identify one or more candidate terminal nodes of the intersection graph, the template priorities associated with the terminal nodes of the template graph causing processing of the intersection graph to proceed preferentially along edges of the intersection graph leading to terminal nodes of the intersection graph that represent terminal nodes of the template graph that correspond to the highest priority templates;
generate a score for each terminal node of the template graph that corresponds to one of the candidate terminal nodes of the intersection graph, each score based at least in part on a probability that the text string corresponds to an intended meaning of the natural language input, and a translation template corresponding to the terminal node of the template graph;
select a first terminal node of the template graph based on the one or more scores, a first translation template corresponding to the first terminal node of the template graph;
translate the text string using the first translation template thereby generating a machine-readable translation that accurately represents a semantic meaning of the natural language input;
process the machine-readable translation using structured data to generate a result;
generate a natural language response using the result; and
present the natural language response to a user on a client device.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques are described for translating natural language input to a machine-readable form that accurately represents the semantic meaning of the input intended by the user.
-
Citations
20 Claims
-
1. A computer program product for translating natural language input to a machine-readable format for processing by a knowledge base, the computer program product comprising one or more non-transitory computer-readable media having computer program instructions stored therein, the computer program instructions being configured such that, when executed, the computer program instructions cause one or more computing devices to:
-
receive a text string derived from natural language input; generate an input graph for the text string, the input graph representing a plurality of different subsets of words in the text string; retrieve a template graph representing a plurality of translation templates associated with the knowledge base, each translation template being for translating matching natural language input to the machine-readable format, and each translation template corresponding to at least one of a plurality of terminal nodes in the template graph, wherein each terminal node of the template graph has an associated template priority that is based on the corresponding translation template, and wherein each internal node of the template graph is labeled with an identifier of a highest priority template that can be reached from that point in the template graph; generate an intersection graph from the input graph and the template graph, each node in the intersection graph representing a tuple of corresponding nodes in the input and template graphs; process the intersection graph to identify one or more candidate terminal nodes of the intersection graph, the template priorities associated with the terminal nodes of the template graph causing processing of the intersection graph to proceed preferentially along edges of the intersection graph leading to terminal nodes of the intersection graph that represent terminal nodes of the template graph that correspond to the highest priority templates; generate a score for each terminal node of the template graph that corresponds to one of the candidate terminal nodes of the intersection graph, each score based at least in part on a probability that the text string corresponds to an intended meaning of the natural language input, and a translation template corresponding to the terminal node of the template graph; select a first terminal node of the template graph based on the one or more scores, a first translation template corresponding to the first terminal node of the template graph; translate the text string using the first translation template thereby generating a machine-readable translation that accurately represents a semantic meaning of the natural language input; process the machine-readable translation using structured data to generate a result; generate a natural language response using the result; and present the natural language response to a user on a client device. - View Dependent Claims (2)
-
-
3. A computer-implemented method for translating a text string derived from natural language input to a machine-readable format, comprising:
-
using one or more computing devices, generating an input graph for the text string, the input graph representing a plurality of different subsets of words in the text string; using the one or more computing devices, retrieving a template graph representing a plurality of translation templates, each translation template being for translating matching natural language input to the machine-readable format, and each translation template corresponding to at least one of a plurality of terminal nodes in the template graph, wherein each internal node of the template graph is labeled with an identifier of a highest priority template that can be reached from that point in the template graph; using the one or more computing devices, generating an intersection graph from the input graph and the template graph, each node in the intersection graph representing a tuple of corresponding nodes in the input and template graphs; using the one or more computing devices, processing the intersection graph according to template priorities associated with the nodes of the template graph thereby identifying one or more candidate terminal nodes of the intersection graph, the template priorities associated with the terminal nodes of the template graph causing processing of the intersection graph to proceed preferentially along edges of the intersection graph leading to terminal nodes of the intersection graph that represent terminal nodes of the template graph that correspond to the highest priority templates; using the one or more computing devices, selecting a terminal node in the template graph that corresponds to one of the one or more candidate terminal nodes of the intersection graph based at least in part on a probability associated with the selected terminal node of the template graph that the text string corresponds to an intended meaning of the natural language input, wherein a first translation template corresponds to the selected terminal node of the template graph; using the one or more computing devices, translating the text string using the first translation template thereby generating a machine-readable translation that accurately represents a semantic meaning of the natural language input; using the one or more computing devices, processing the machine-readable translation using structured data to generate a result; using the one or more computing devices, generating a natural language response using the result; and using the one or more computing devices, presenting the natural language response to a user on a client device. - View Dependent Claims (4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A computing system for translating a text string derived from natural language input to a machine-readable format, comprising one or more computing devices configured to:
-
generate an input graph for the text string, the input graph representing a plurality of different subsets of words in the text string; retrieve a template graph representing a plurality of translation templates, each translation template being for translating matching natural language input to the machine-readable format, and each translation template corresponding to at least one of a plurality of terminal nodes in the template graph, wherein each internal node of the template graph is labeled with an identifier of a highest priority template that can be reached from that point in the template graph; generate an intersection graph from the input graph and the template graph, each node in the intersection graph representing a tuple of corresponding nodes in the input and template graphs; process the intersection graph according to template priorities associated with the nodes of the template graph thereby identifying one or more candidate terminal nodes of the intersection graph, the template priorities associated with the terminal nodes of the template graph causing processing of the intersection graph to proceed preferentially along edges of the intersection graph leading to terminal nodes of the intersection graph that represent terminal nodes of the template graph that correspond to the highest priority templates; select a terminal node in the template graph that corresponds to one of the one or more candidate terminal nodes of the intersection graph based at least in part on a probability associated with the selected terminal node of the template graph that the text string corresponds to an intended meaning of the natural language input, wherein a first translation template corresponds to the selected terminal node of the template graph; translate the text string using the first translation template thereby generating a machine-readable translation that accurately represents a semantic meaning of the natural language input; process the machine-readable translation using structured data to generate a result; generate a natural language response using the result; and present the natural language response to a user on a client device. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification