Trainable dynamic phrase reordering for natural language generation in conversational systems

• US 7,043,420 B2
• Filed: 12/11/2000
• Issued: 05/09/2006
• Est. Priority Date: 12/11/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ratnaparkhi, Adwait
• Primary Examiner(s): Chawan, Vijay
• Assistant Examiner(s): Shortledge, Thomas E.
• Application Number:
  US09/734,154
• Publication Number:
  US 20020116173A1
• Time in Patent Office: 1,975 Days
• Field of Search: 704/9, 704/7, 704/10, 704/258, 704/260
• US Class Current: 704/9
• CPC Class Codes: G06F 40/56 Natural language generation

Abstract

A system and method to facilitate natural language generation in a human-to-machine conversational system that produces written or spoken output. In one aspect, a user provides a scoring function and grammar rules including words and attributes. A method according to the present invention then generates possible reorderings of the words and attributes using the grammar rules and determines an optimal ordering of the words and attributes using the scoring function, which is then returned to the user.

Claims

1. A computer-based method of generating natural language, comprising the steps of:

receiving a concept comprising attributes and corresponding values of each of said attributes from a user;

receiving grammar rules from the user, each rule including a head, a phrase fragment, a direction and a condition, wherein each phrase fragment includes one of said attributes;

receiving a scoring function from the user;

generating possible natural language phrases using the grammar rules;

determining an optimal natural language phrase from the possible natural language phrases using the scoring function; and

returning said optimal natural language phrase to the user.

2. The method of claim 1, wherein the head is a word.

3. The method of claim 1, wherein the phrase fragment is a natural language phrase fragment.

4. The method of claim 1, wherein the direction indicates a location of the phrase fragment.

5. The method of claim 1, wherein the condition is a code fragment for restricting use of a rule.

6. The method of claim 1, wherein each attribute in the optimal natural language phrase is replaced with its corresponding value.

7. The method of claim 1, wherein the optimal natural language phrase is a highest scoring natural language phrase that is consistent with the grammar rules.

8. The method of claim 1, wherein the scoring function is a probability P of a phrase of length N based on the probability P of a word w_i conditioned on two previous words, w_i−

1 and w<sub>i−

2</sub>, the scoring function comprises the equation;

Π

_{i=1 . . . N}P(w_i|w<sub>i−

1</sub>,w<sub>i−

2</sub>).

9. The method of claim 1, wherein the attributes are variables.

10. The method of claim 4, wherein the direction indicates that the location of the phrase fragment is right of the head.

11. The method of claim 4, wherein the direction indicates that the location of the phrase fragment is left of the head.

12. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for generating natural language, the method comprising the steps of:

receiving a concept comprising attributes and corresponding values of each of said attributes from a user;

receiving grammar rules from the user, each rule including a head, a phrase fragment, a direction and a condition, wherein each phrase fragment includes one of said attributes;

receiving a scoring function from the user;

generating possible natural language phrases using the grammar rules;

computing a score for each of the natural language phrases using the scoring function;

returning the highest scoring natural language phrase to the user.

13. The program storage device of claim 12, wherein the head is a word.

14. The program storage device of claim 12, wherein the phrase fragment is a natural language phrase fragment.

15. The program storage device of claim 12, wherein the direction indicates a location of the phrase fragment.

16. The program storage device of claim 12, wherein the condition is a code fragment for restricting use of a rule.

17. The program storage device of claim 12, wherein each attribute in the optimal natural language phrase is replaced with its corresponding value.

18. The program storage device of claim 12, wherein the optimal natural language phrase is a highest scoring natural language phrase that is consistent with the grammar rules.

19. The program storage device of claim 12, wherein the scoring function is a probability P of a phrase of length N based on the probability P of a word w_i conditioned on two previous words, w_i−

1 and w<sub>i−

2</sub>, the scoring function comprises the equation;

Π

_{i=1 . . . N}P(w_i|w<sub>i−

1</sub>,w<sub>i−

2</sub>).

20. The program storage device of claim 12, wherein the attributes are variables.

21. A computer-based method of generating natural language, comprising the steps of:

receiving a concept comprising attributes and corresponding values of each of said attributes from a user;

receiving grammar rules from the user, each rule including a head, a phrase fragment, a direction and a condition, wherein each phrase fragment includes one of said attributes;

receiving a scoring function from the user;

generating a plurality of possible natural language phrases using the grammar rules;

determining an optimal natural language phrase from the plurality of possible natural language phrases using the scoring function; and

returning said optimal natural language phrase to the user;

wherein the head is a word;

wherein the phrase fragment is a natural language phrase fragment comprising a plurality of words;

wherein the direction indicates a location of the phrase fragment;

wherein the condition is a code fragment for restricting use of a rule using a binary evaluation during run-time.