Linguistically informed statistical models of constituent structure for ordering in sentence realization for a natural language generation system

• US 7,346,493 B2
• Filed: 03/25/2003
• Issued: 03/18/2008
• Est. Priority Date: 03/25/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smets, Martine, Moore, Robert C., Gamon, Michael, Ringger, Eric, Corston-Oliver, Simon
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Rider; Justin W.
• Application Number:
  US10/396,549
• Publication Number:
  US 20040193401A1
• Time in Patent Office: 1,820 Days
• Field of Search: 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/56 Natural language generation
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence

Abstract

The present invention is a tree ordering component within a sentence realization system which receives an unordered syntax tree and generates a ranked list of alternative ordered syntax trees from the unordered syntax tree. The present invention also includes statistical models of constituent structure employed by the tree ordering component in scoring the alternative ordered trees.

Claims

1. A tree ordering component within a sentence realization system which receives an unordered syntax tree and generates a scored and ranked list of alternative ordered syntax trees from the unordered syntax tree, the tree ordering component comprising:

a generative statistical model of constituent structure conditioned on features, having a formal structure, and whose parameters are estimated using a statistical estimation technique; and

a search component which receives the unordered syntax tree for a sentence to be generated, considers the set of possible alternative ordered syntax trees, and identifies which of the alternative ordered syntax trees has a highest probability according to the statistical model of constituent structure, the search component providing as an output a fully ordered syntax tree for use in generating the sentence.

2. The tree ordering component of claim 1, wherein in the statistical model of constituent structure the features have been selected by an automatic feature selection technique.

3. The tree ordering component of claim 1, wherein in the statistical model of constituent structure the parameters of the model are estimated by language modeling techniques.

4. The tree ordering component of claim 1, wherein in the statistical model of constituent structure the parameters of the model are estimated by maximum entropy techniques.

5. The tree ordering component of claim 1, wherein in the statistical model of constituent structure the parameters of the model are estimated by decision tree learning techniques.

6. The tree ordering component of claim 1, wherein in the statistical model of constituent structure the formal structure of the model is a Markov grammar having a particular orientation.

7. The tree ordering component of claim 6, wherein in the statistical model of constituent structure the model having Markov grammar structure is a joint model of constituent structure.

8. The tree ordering component of claim 6, wherein in the statistical model of constituent structure the model having Markov grammar structure is a conditional model of constituent structure.

9. The tree ordering component of claim 8, wherein in the statistical model of constituent structure a feature set of the model includes features of a constituent set defined as follows:

for a particular constituent of the unordered tree, during the ordering search, relative to one ordering hypothesis, the daughters of said constituent that remain to be ordered.

10. The tree ordering component of claim 9, wherein in the statistical model of constituent structure the features of the constituent set of interest include a size of that set.

11. The tree ordering component of claim 9, wherein in the statistical model of constituent structure the features of the constituent set of interest include a total number of occurrences of each syntactic category in that set.

12. The tree ordering component of claim 6, wherein in the statistical model of constituent structure the model structure is oriented as a head-driven Markov grammar.

13. The tree ordering component of claim 6, wherein in the statistical model of constituent structure the model structure is oriented as a left-to-right Markov grammar.

14. The tree ordering component of claim 6, wherein in the statistical model of constituent structure the model structure is oriented as a right-to-left Markov grammar.

15. The tree ordering component of claim 1, wherein in the statistical model of constituent structure the formal structure of the model is a binary conditional model.

16. The tree ordering component of claim 15, wherein in the statistical model of constituent structure a feature set of the model includes features of a constituent set defined as follows:

for a particular constituent of the unordered tree, during the ordering search, relative to one ordering hypothesis, the daughters of said constituent that remain to be ordered.

17. The tree ordering component of claim 16, wherein in the statistical model of constituent structure the features of the constituent set of interest include a size of that set.

18. The tree ordering component of claim 16, wherein in the statistical model of constituent structure the features of the constituent set of interest include a total number of occurrences of each syntactic category in that set.

19. The tree ordering component of claim 1, wherein in the statistical model of constituent structure a feature set of the model includes one or more lexical features of constituents in the unordered tree.

20. The tree ordering component of claim 1, wherein in the statistical model of constituent structure a feature set of the model includes one or more syntactic features of constituents in the unordered tree.

21. The tree ordering component of claim 1, wherein in the statistical model of constituent structure a feature set of the model includes one or more semantic features of constituents in the unordered tree.

22. The tree ordering component of claim 21, wherein in the statistical model of constituent structure a feature set of the model includes the semantic relation between the head of a given constituent in the unordered tree and the daughters of that constituent.

23. The tree ordering component of claim 1, wherein in the statistical model of constituent structure a feature set of the model includes a length in words of a particular constituent of the unordered tree.

24. The tree ordering component of claim 1, wherein in the statistical model of constituent structure a feature set of the model includes features of a constituent set defined as follows:

for a particular constituent of the unordered tree, during the ordering search, relative to one ordering hypothesis, the daughters of said constituent already ordered.

25. The tree ordering component of claim 24, wherein in the statistical model of constituent structure the features of the constituent set of interest include a size of that set.

26. The tree ordering component of claim 24, wherein in the statistical model of constituent structure the features of the constituent set of interest include a total number of occurrences of each syntactic category in that set.