Probabilistic model for 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.

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.