Methods and systems for generating natural language descriptions from data

• US 7,930,169 B2
• Filed: 01/17/2006
• Issued: 04/19/2011
• Est. Priority Date: 01/14/2005
• Status: Active Grant

• Current Assignee: Classified Ventures LLC (Cars.com, Inc.)
• Original Assignee: Classified Ventures LLC (Cars.com, Inc.)
• Inventors: Billerey-Mosier, Roger
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Adesanya; Olujimi A
• Application Number:
  US11/333,161
• Publication Number:
  US 20060178868A1
• Time in Patent Office: 1,918 Days
• Field of Search: 704/7, 704/9, 707/3, 707/100
• US Class Current: 704/9
• CPC Class Codes: G06F 40/56 Natural language generation
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

The invention is directed to a natural language generation (NLG) software system that generates rich, content-sensitive human language descriptions based on unparsed raw domain-specific data. In one embodiment, the NLG software system may include a data parser/normalizer, a comparator, a language engine, and a document generator. The data parser/normalizer may be configured to retrieve specification information for items to be described by the NLG software system, to extract pertinent information from the raw specification information, and to convert and normalize the extracted information so that the items may be compared specification by specification. The comparator may be configured to use the normalized data from the data parser/normalizer to compare the specifications of the items using comparison functions and interpretation rules to determine outcomes of the comparisons. The language engine may be configured to cycle through all or a subset of the normalized specification information, to retrieve all sentence templates associated with each of the item specifications, to call the comparator to compute or retrieve the results of the comparisons between the item specifications, and to recursively generate every possible syntactically legal sentence associated with the specifications based on the retrieved sentence templates. The document generator may be configured to select one or more discourse models having instructions regarding the selection, organization and modification of the generated sentences, and to apply the instructions of the discourse model to the generated sentences to generate a natural language description of the selected items.

Claims

1. A method for generating a natural language description of a user-selected item comparing the user-selected item to at least one comparison item, wherein the characteristics of both the user-selected item and the comparison item are defined by a plurality of specifications, the method comprising:

selecting the user-selected item from a list of items stored at a computer-readable storage medium and available for text generation;

selecting the at least one comparison item from the list of items;

retrieving the specifications for the user-selected item and the at least one comparison item from a computer-readable storage medium, each specification including a comparison function that compares the specification for the user-selected item to the specification for the comparison item and a plurality of sentence templates each having a recursive phrase structure including a plurality of coded phrases using one or more of the specification for the user-selected item or the specification for the comparison item;

comparing the specifications for the user-selected item to the specifications for the at least one comparison item at a processing unit operatively coupled to the computer-readable storage medium by evaluating each comparison function to determine a comparison function result;

assigning a textual representation to each comparison function result;

evaluating the plurality of sentence templates to generate at the processing unit a plurality of natural language sentences describing the user-selected item by recursively expanding the recursive phrase structure, wherein the natural language sentences include each assigned textual representation and a recursive expansion result explains the outcome of the comparisons in natural language;

combining at the processing unit the generated natural language sentences into a natural language document describing the user-selected item; and

at least one of outputting the natural language document to an output device operatively coupled to the processing unit and storing the natural language document to one of the computer-readable storage medium and a further computer-readable storage medium operatively coupled to the processing unit.

2. A method according to claim 1, wherein retrieving the specifications comprises:

retrieving specification information for the user-selected item and the at least one comparison item from the computer-readable storage medium; and

extracting values of each of the specifications from the retrieved specification information.

3. A method according to claim 1, comprising:

normalizing the retrieved specifications for the user-selected item and the at least one comparison item to a uniform format; and

comparing the normalized specification information for the user-selected item to the normalized specification information for the at least one comparison item.

4. A method according to claim 1, wherein the user-selected item is compared to a plurality of comparison items, the method comprising:

retrieving the specifications for the plurality of comparison items from the computer-readable storage medium;

merging the specifications for the plurality of comparison items into specifications defining a composite virtual comparison item;

comparing the specifications for the user-selected item to the specifications for the composite virtual comparison item at the processing unit; and

generating a plurality of natural language sentences describing the user-selected item, wherein the text of the natural language sentences is determined based on the outcome of the comparisons of the specifications of the user-selected item to the specifications of the composite virtual comparison item.

5. A method according to claim 1, wherein the specifications for an item comprise a plurality of specification values, and wherein comparing the specifications of the items comprises:

comparing a specification value of the user-selected item to the corresponding specification value for the at least one comparison item; and

applying an associated interpretation rule to the outcome of the comparison of the specification values to determine the comparison function result.

6. A method according to claim 1, wherein each specification includes an associated meta-rule having an evaluation condition based on values of at least one specification for the user-selected item, the method comprising:

evaluating the evaluation condition of the meta-rule using specification values of both the user-selected item and the comparison item; and

generating a natural language sentence in response to determining that the evaluation of the meta-rule is met by the values of the specification for the user-selected item and the comparison item.

7. An apparatus structured to generate a natural language description of a user-selected item comparing the user-selected item to at least one comparison item, wherein the characteristics of both the user-selected item and the comparison item are defined by a plurality of specifications, the apparatus comprising:

a processing unit; and

a memory device operatively coupled to the processing unit, the memory device storing a software program structured to cause the processing unit to;

retrieve the specifications for the user-selected item and the at least one comparison item from one of the memory device and a storage medium operatively coupled to the processing unit, each specification including a comparison function that compares the specification for the user-selected item to the specification for the comparison item and a plurality of sentence templates each having a recursive phrase structure including a plurality of coded phrases using one or more of the specification for the user-selected item or the specification for the comparison item,

compare the specifications for the user-selected item to the specifications for the at least one comparison item by evaluating each comparison function to determine a comparison function result,

assign a textual representation to each comparison function result;

evaluate the plurality of sentence templates to generate a plurality of natural language sentences describing the user-selected item by recursively expanding the recursive phrase structure, wherein the natural language sentences include each assigned textual representation and a recursive expansion result explains the outcome of the comparisons in natural language, and

combine the generated natural language sentences into a natural language document describing the user-selected item.

8. An apparatus according to claim 7, wherein the software program is further structured to cause the processing unit to:

retrieve specification information for the user-selected item and the at least one comparison item from one of the memory device and the storage medium; and

extract values of each of the specifications from the retrieved specification information.

9. An apparatus according to claim 7, wherein the software program is further structured to cause the processing unit to:

normalize the retrieved specifications for the user-selected item and the at least one comparison item to a uniform format; and

compare the normalized specification information for the user-selected item to the normalized specification information for the at least one comparison item.

10. An apparatus according to claim 7, wherein the user-selected item is compared to a plurality of comparison items, the software program is further structured to cause the processing unit to:

retrieve the specifications for the plurality of comparison items from one of the memory device and the storage medium;

merge the specifications for the plurality of comparison items into specifications defining a composite virtual comparison item;

compare the specifications for the user-selected item to the specifications for the composite virtual comparison item; and

generate a plurality of natural language sentences describing the user-selected item, wherein the text of the natural language sentences is determined based on the outcome of the comparisons of the specifications of the user-selected item to the specifications of the composite virtual comparison item.

11. An apparatus according to claim 7, wherein the specifications for an item comprise a plurality of specification values, and wherein the software program is further structured to cause the processing unit to:

compare a specification value of the user-selected item to the corresponding specification value for the at least one comparison item; and

apply an associated interpretation rule to the outcome of the comparison of the specification values to determine the comparison function result.

12. An apparatus according to claim 7, wherein each specification includes an associated meta-rule having an evaluation condition based on values of at least one specification for the user-selected item, and wherein the software program is further structured to cause the processing unit to:

evaluate the evaluation condition of the meta-rule using specification values of both the user-selected item and the comparison item; and

generate a natural language sentence in response to determining that the evaluation of the meta-rule is met by the values of the specification for the user-selected item and the comparison item.

13. A non-transitory computer readable medium storing a software program structured to cause a server to:

retrieve a plurality of specifications for a user-selected item and for at least one comparison item from a storage medium, each specification including a comparison function that compares the specification for the user-selected item to the specification for the comparison item and a plurality of sentence templates each having a recursive phrase structure including a plurality of coded phrases using one or more of the specification for the user-selected item or the specification for the comparison item;

compare the specifications for the user-selected item to the specifications for the at least one comparison item by evaluating each comparison function to determine a comparison function result;

assign a textual representation to each comparison function result;

evaluate the plurality of sentence templates to generate a plurality of natural language sentences describing the user-selected item by recursively expanding the recursive phrase structure, wherein the natural language sentences include each assigned textual representation and a recursive expansion result explains the outcome of the comparisons in natural language, and

combine the generated natural language sentences into a natural language document having a natural language description of the user-selected item comparing the user-selected item to the at least one comparison item.

14. A natural language generation system for generating a natural language description of a user-selected item comparing the user-selected item to at least one comparison item, wherein the characteristics of each item are defined by a plurality of specifications, the system comprising:

a natural language generator server including a central processing unit, a non-transitory memory device, and an interface circuit, wherein the non-transitory memory device stores a plurality of modules executing on the central processing unit, the modules including;

a data parser/normalizer retrieving the specifications for the user-selected item and the at least one comparison item from a storage medium via the interface unit, each specification including a comparison function that compares the specification for the user-selected item to the specification for the comparison item and a plurality of sentence templates each having a recursive phrase structure including a plurality of coded phrases using one or more of the specification for the user-selected item or the specification for the comparison item;

a comparator comparing the specifications for the user-selected item to the specifications for the at least one comparison item by evaluating each comparison function to determine a comparison function result and assigning a textual representation to each comparison function result;

a language engine evaluating the plurality of sentence templates to generate a plurality of natural language sentences describing the user-selected item by recursively expanding the recursive phrase structure, wherein the natural language sentences include each assigned textual representation and a recursive expansion result explains the outcome of the comparisons in natural language; and

a document generator combining the natural language sentences generated by the language engine into a natural language document describing the user-selected item.

15. A natural language generation system according to claim 14, wherein the data parser/normalizer retrieves specification information for the user-selected item and the at least one comparison item from the storage medium, and extracts values of each of the specifications from the retrieved specification information.

16. A natural language generation system according to claim 14, wherein the data parser/normalizer normalizes the retrieved specifications for the user-selected item and the at least one comparison item to a uniform format, and wherein the comparator compares the normalized specification information for the user-selected item to the normalized specification information for the at least one comparison item.

17. A natural language generation system according to claim 14, wherein the user-selected item is compared to a plurality of comparison items, wherein the data parser/normalizer retrieves the specifications for the plurality of comparison items from the storage medium, and merges the specifications for the plurality of comparison items into specifications defining a composite virtual comparison item, wherein the comparator compares the specifications for the user-selected item to the specifications for the composite virtual comparison item, and wherein the language engine generates a plurality of natural language sentences describing the user-selected item, wherein the text of the natural language sentences is determined based on the outcome of the comparisons performed by the comparator of the specifications of the user-selected item to the specifications of the composite virtual comparison item.

18. A natural language generation system according to claim 14, wherein the specifications for an item comprise a plurality of specification values, wherein the comparator compares a specification value of the user-selected item to the corresponding specification value for the at least one comparison item, and applies an associated interpretation rule to the outcome of the comparison of the specification values to determine the comparison function result.

19. A natural language generation system according to claim 14, wherein each specification includes a meta-rule having an evaluation condition based on values of at least one specification for the user-selected item, and wherein the language engine evaluates the evaluation condition of the meta-rule using specification values of both the user-selected item and the comparison item, and generates the natural language sentence in response to determining that the evaluation of the meta-rule matches the values of the specification for the user-selected item and the comparison item.