System and method for natural language generation

• US 20050267751A1
• Filed: 08/03/2005
• Published: 12/01/2005
• Est. Priority Date: 01/18/2000
• Status: Active Grant

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Bangalore, Srinivas, Rambow, Owen Christopher
• Granted Patent: US 7,231,341 B2
• Time in Patent Office: Days
• US Class Current: 704/242
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/56 Natural language generation

Abstract

A system, method and computer-readable medium for generating natural language utilizes a stochastic process to choose a derivation tree according to a predetermined grammar, such as tree-adjoined grammar (TAG). A word lattice is created from a single semi-specified derivation tree and the proper path (i.e., desired output string) is selected from the lattice using a least cost, or other appropriate algorithms.

Claims

1. A method for translating an input dependency syntax tree into a natural language output, the method comprising:

responsive to an input dependency syntax tree, stochastically selecting tree-adjoining grammar trees for each node in the input dependency syntax tree to create a semi-specified derivation tree;

responsive to the stochastically selected tree-adjoining grammar trees, creating from syntactic realizations a lattice of all possible linearizations of the trees using a reference grammar; and

selecting a most likely traversal path through the lattice as a natural language output.

2. The method of claim 1, wherein the step of stochastically selecting tree-adjoining grammar trees utilizes a tree model database

3. The method of claim 1, wherein the reference grammar is from a reference grammar database.

4. The method of claim 1, wherein:

the step of stochastically selecting tree-adjoining grammar trees is performed by a tree choosing module;

the step of creating a lattice is performed by an unraveling module; and

the step of selecting a most likely traversal path is performed by a linear precedence chooser module.

5. The method of claim 1, wherein selecting a most likely traversal path utilizes a Viterbi algorithm.

6. The method of claim 3, wherein the reference grammar database comprises an XTAG grammar database.

7. A computer-readable medium storing instructions for controlling a computing device to translate an input dependency syntax tree into a natural language output, the instructions comprising:

responsive to an input dependency syntax tree, stochastically selecting tree-adjoining grammar trees for each node in the input dependency syntax tree to create a semi-specified derivation tree;

responsive to the stochastically selected tree-adjoining grammar trees, creating from syntactic realizations a lattice of all possible linearizations of the trees using a reference grammar; and

selecting a most likely traversal path through the lattice as a natural language output.

8. The computer-readable medium of claim 7, wherein the step of stochastically selecting tree-adjoining grammar trees utilizes a tree model database

9. The computer-readable medium of claim 7, wherein the reference grammar is from a reference grammar database.

10. The computer-readable medium of claim 7, wherein:

the step of stochastically selecting tree-adjoining grammar trees is performed by a tree choosing module;

the step of creating a lattice is performed by an unraveling module; and

the step of selecting a most likely traversal path is performed by a linear precedence chooser module.

11. The computer-readable medium of claim 7, wherein selecting a most likely traversal path utilizes a Viterbi algorithm.

12. The computer-readable medium of claim 9, wherein the reference grammar database comprises an XTAG grammar database.

13. A computing device for translating an input dependency syntax tree into a natural language output, the computing device comprising:

a module configured, responsive to an input dependency syntax tree, to stochastically select tree-adjoining grammar trees for each node in the input dependency syntax tree to create a semi-specified derivation tree;

a module configured, responsive to the stochastically selected tree-adjoining grammar trees, to create from syntactic realizations a lattice of all possible linearizations of the trees using a reference grammar; and

a module configured to select a most likely traversal path through the lattice as a natural language output.

14. The computing device of claim 13, wherein the module configured to stochastically select tree-adjoining grammar trees further utilizes a tree model database

15. The computing device of claim 13, wherein the reference grammar is from a reference grammar database.

16. The computing device of claim 13, wherein:

the module configured to stochastically select tree-adjoining grammar trees is a tree choosing module;

the module configured to create a lattice an unraveling module; and

the module configured to select a most likely traversal path a linear precedence chooser module.

17. The computing device of claim 13, wherein the module configured to select a most likely traversal path utilizes a Viterbi algorithm.

18. The computing device of claim 15, wherein the reference grammar database comprises an XTAG grammar database.