Probabilistic model for natural language generation

• US 6,947,885 B2
• Filed: 01/11/2001
• Issued: 09/20/2005
• Est. Priority Date: 01/18/2000
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Bangalore, Srinivas, Rambow, Owen Christopher
• Primary Examiner(s): McFadden, Susan
• Assistant Examiner(s): Vo, Huyen X.
• Application Number:
  US09/758,483
• Publication Number:
  US 20020026306A1
• Time in Patent Office: 1,713 Days
• Field of Search: 704/1, 704/4, 704/9, 704/200, 704/252, 704/257, 715/533
• 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 natural language generator utilizes a stochastic process to choose a derivation tree according to a predetermined reference grammar, such as a 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 algorithm.

Claims

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

a tree choosing module, responsive to the input dependency syntax tree, for stochastically selecting tree-adjoining grammar trees for each node in the input dependency tree to create a semi-specified derivation tree, the tree choosing module including a tree model database for use in selection;

an unraveling module, responsive to the stochastically selected tree-adjoining grammar trees created by the tree choosing module and including a predetermined reference grammar database for creating from syntactic realizations a lattice of all possible linearizations of said trees using the reference grammar of said database; and

a linear precedence chooser module for selecting a most likely traversal path through the lattice as the natural language output of the generator.

2. The generator as defined in claim 1 wherein the linear precedence chooser module utilizes a Viterbi algorithm to select the most likely traversal path.

3. The generator as defined in claim 1 wherein the unraveling module includes a reference grammar database.

4. The generator as defined in claim 3 wherein the reference grammar database comprises an XTAG grammar database.