System and method for natural language generation

• US 7,562,005 B1
• Filed: 03/22/2007
• Issued: 07/14/2009
• Est. Priority Date: 01/18/2000
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Rambow, Owen Christopher, Bangalore, Srinivas
• Primary Examiner(s): Vo, Huyen X.
• Application Number:
  US11/689,749
• Time in Patent Office: 845 Days
• Field of Search: 704/257, 704/200, 704/242, 704/232, 704/270, 704/270.1, 704/243, 704 1- 10, 704/251, 704/256, 704/255
• US Class Current: 704/1
• 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 generating natural language output, the method comprising:

executing instructions in a computing device to create a semi-specified derivation tree by selecting tree-adjoining grammar trees for each node in an input dependency syntax tree;

executing instructions in a computing device to create a lattice of all possible linearizations of the selected tree-adjoining grammar trees; and

executing instructions in a computing device to generate natural language output by selecting a most likely traversal path through the created lattice.

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

3. The method of claim 1, wherein the lattice is created using a reference grammar.

4. The method of claim 3, wherein the reference grammar is from a reference grammar database comprising an XTAG grammar database.

5. The method of claim 1, wherein:

the step of 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.

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

7. A tangible computer-readable medium storing instructions for controlling a computing device to generate natural language output, the instructions comprising:

creating a semi-specified derivation tree by selecting tree-adjoining grammar trees for each node in an input dependency syntax tree;

creating a lattice of all possible linearizations of the trees using a reference grammar; and

generating natural language output by selecting a most likely traversal path through the created lattice.

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

9. The tangible computer-readable medium of claim 7, wherein the lattice is created using a reference grammar.

10. The tangible computer-readable medium of claim 9, wherein the reference grammar is from a reference grammar database comprising an XTAG grammar database.

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

the step of 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.

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

13. A computing device for generating a natural language output, the computing device comprising:

the processor;

a module configured to control the computer device to create a semi-specified derivation tree by selecting tree-adjoining grammar trees for each node in an input dependency syntax tree;

a module configured to control the computing device to create a lattice of all possible linearizations of the selected tree-adjoining grammar trees; and

a module configured to control the computing device to generate natural language output by selecting a most likely traversal path through the created lattice.

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

15. The computing device of claim 13, wherein the lattice is created using a reference grammar.

16. The computing device of claim 15, wherein the reference grammar is from a reference grammar database comprising an XTAG grammar database.

17. The computing device of claim 13, wherein:

the module configured to control the computing device to select tree-adjoining grammar trees is a tree choosing module;

the module configured to control the computing device to create a lattice is an unraveling module; and

the module configured to control the computing device to select a most likely traversal path is a linear precedence chooser module.

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