Method and apparatus for paraphrasing information contained in logical forms

• US 5,237,502 A
• Filed: 08/26/1991
• Issued: 08/17/1993
• Est. Priority Date: 09/04/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: White, Brian F., Bretan, Ivan P., Sanamrad, Mohammad A.
• Primary Examiner(s): Weinhardt, Robert A.
• Assistant Examiner(s): Poinvil, Frantzy
• Application Number:
  US07/750,169
• Time in Patent Office: 722 Days
• Field of Search: 364/419, 364/200 MS File, 364/900 MS File
• US Class Current: 704/1
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/56 Natural language generation

Abstract

A computer implemented system creates natural language paraphrases of information contained in a logical form, where the logical form may be a representation of a natural language expression. (Logical forms are widely used by database query systems and machine translation systems and are typically forms of first-order logic, with the possible addition of higher-order operators.) The paraphraser is implicitly defined via the BNF description of CLF (Baclis-Naur Forms) of Initial Trees and of the paraphrase rules. The paraphraser uses a technique for mapping logical forms to natural language. The natural language paraphrases which are created could be used either as input to a query system, as part of a machine translation system, or to generate natural language corresponding to an interpretation created by a natural language database query system of a user'"'"'s query for the purpose of verification of the paraphrase by the user.

Claims

1. A Method of paraphrasing information contained in logical forms in an information processing system, comprising the steps of:

mapping a logical form expression to a plurality of initial trees, each of said initial trees comprising nodes, said nodes comprising a) node names corresponding to linguistic categories, such as "noun", "verb", or "adjective", and b) a set of syntactic features, that is, pairs of attributes and their values;

applying a grammar to said initial trees, said grammar comprised of grammar rules and each of said grammar rules comprising a phrase structure recognition rule and a generation rule;

said application of said grammar comprising the step of parsing said initial trees as an unordered set by applying said phrase structure rules to said initial trees to create a syntactic tree having a plurality of nodes, one of which is identified as a top node; and

creating a paraphrase from said syntactic tree by;

i. selecting each of said nodes of said syntactic tree in order by traversing said syntactic tree, top-down;

ii. if said selected node was created by application of said grammar rules, using said associated generation rule to create translation strings;

iii. if said selected node was an initial tree, creating said translation strings by mapping said initial tree to a natural language string as a function of said initial tree'"'"'s categories and features which said grammar and said initial tree generator had placed on said initial tree;

iv. combining each of said created translation strings to create translation which is associated with said top node; and

v. selecting said translation string associated with said top node as said paraphrase of said syntactic tree.

2. Method as claimed in claim 1, wherein the step of creating said paraphrase comprises, traversing said syntactic tree from node to node, depth-first.

3. Method as claimed in claim 1, wherein the step of creating said paraphrase comprises, traversing said syntactic tree from node to node, breath-first.

4. Method as claimed in claim 1, wherein said natural language paraphrase is displayed.

5. Method as claimed in claim 1, wherein said phrase structure rules allow feature conditions and feature changes both up and down the tree.

6. Method as claimed in claim 5, wherein the step of creating said paraphrase comprises, traversing said syntactic tree from node to node, depth-first.

7. Method as claimed in claim 5, wherein the step of creating said paraphrase comprises, traversing said syntactic tree from node to node, breath-first.

8. Method as claimed in claim 5, wherein said natural language paraphrase is displayed.

9. A Method of paraphrasing information contained in logical forms in an information processing system, comprising the steps of:

mapping a logical form expression to a plurality of initial trees, each of said initial trees comprising nodes, said nodes comprising a) node names corresponding to linguistic categories, such as "noun", "verb",or "adjective", and b) a set of syntactic features, that is, pairs of attributes and their values;

applying a grammar to said initial trees, said grammar comprised of grammar rules and each of said grammar rules comprising a phrase structure recognition rule and a generation rule;

said application of said grammar comprising the steps of;

i. identifying a set of clusters of said initial trees, said set comprised of

     1) clusters which are subsets of another cluster of said set; and

     2) clusters which do not intersect with another cluster in said set;

ii. parsing each of said clusters comprising parsing said initial trees as an unordered set by applying said phrase structure rules to said initial trees to create a syntactic tree having a plurality of nodes, on eof which is identified as a top node; and

creating a paraphrase from said syntactic tree by;

i. selecting each of said nodes of said syntactic tree in order by traversing said syntactic tree, top-down;

ii. if said selected node was created by application of said grammar rules, using said associated generation rule to create translation strings;

iii. if said selected node was an initial tree, creating said translation strings by mapping said initial tree to a natural language string as a function of said initial tree'"'"'s categories and features which said grammar and said initial tree generator had placed on said initial tree;

iv. combining each of said created translation strings to create a translation string which is associated with said top node; and

v. selecting said translation string associated with said top node as said paraphrase of said syntactic tree.

10. Method as claimed in claim 9, wherein the evaluating step comprises, traversing said syntactic tree from node to node, depth-first.

11. Method as claimed in claim 9, wherein the evaluating step comprises, traversing said syntactic tree from node to node, breath-first.

12. Method as claimed in claim 9, wherein said natural language paraphrase is displayed.

13. Apparatus for paraphrasing information contained in logical forms, in an inforamtion processing system said logical forms being typically first-order logic, with possible addition of higher-order operators, the apparatus comprising:

means for mapping the logical forms to a set of initial trees, each of said initial tree comprising nodes, said nodes comprising a) node names corresponding to linguistic categories, such as "noun", or "adjective", and b) a set of syntactic features, that is, pairs of attributes and their values;

means for applying a grammar, said grammar comprised of grammar rules, each of said grammar rules comprising a phrase structure rule and a generation rule;

said means for applying said grammar comprising parsing means for parsing said initial trees as an unordered set using said phrase structure rules, producing a syntactic tree having a plurality of nodes, one of said nodes being identified as a top node;

means for creating a paraphrase from said syntactic tree by selecting each of said nodes of said syntactic tree in order by traversing said syntactic tree, top-down, where said means comprises;

i. means for using said associated generation rule to create translation strings, said means for using applied if said selected node was created by application of said grammar rules;

ii. means for creating said translation strings by mapping said initial tree to a natural language string as a function of said initial tree'"'"'s categories and features which said grammar and said initial tree generator had placed on said initial tree, said means for creating applied if said selected node was an initial tree;

iii. means for combining each of said created translation strings to create a translation string which is associated with said top node;

iv. means for selecting said translation string associated with said top node as said paraphrase of said syntactic tree; and

v. means for displaying said selected translation string.

14. Apparatus for paraphrasing information contained in logical forms, in an information processing system said logical forms being typically first-order logic, with possible addition of higher-order operators, the apparatus comprising:

means for mapping the logical forms to a set of initial trees, each of said initial tree comprising nodes, said nodes comprising a) node names corresponding to linguistic categories, such as "noun", "verb", or "adjective", and b) a set of syntactic features, that is, pairs of attibutes and their values;

means for applying a grammar, said grammar comprised of grammar rules, each of said grammar rules comprising a phrase structure rule and a generation rule;

said means for applying said grammar comprising parsing means for parsing said initial trees as an unordered set using said phrase structure rules, producing a syntactic tree having a plurality of nodes, one of said nodes being identified as a top node;

means for pasing each of said clusters of said set in turn in the following sequence;

selecting a first cluster to be processed;

if the content of said first cluster is the smallest cluster containing a second cluster, then said second cluster is processed first, yielding one or more alalyses;

processing said first cluster;

means for parsing each of said initial trees in said clusters as an unordered set by applying said phrase structure rules to said initial trees to create a syntactic tree having a plurality of nodes, one of said nodes being identified as a top node;

means for evaluating said syntactic tree, said evaluation performed by selecting each of said nodes of said syntactic tree in order;

means for creating a paraphrase from said syntactic tree by selecting each of said nodes of said syntactic tree in order by traversing said syntactic tree, top-down, where said means comprises;

i. means for using said associated generation rule to create translation strings, said means for using applied if said selected node was created by application of said grammar rules;

ii. means for creating said translation strings by mapping said initial tree to a natural language string as a function of said initial tree'"'"'s categories and features which said grammar and said initial tree generator had placed on said initial tree, said means for creating applied if said selected node was an initial tree;

iii. means for combining each of said created translation strings to create a traslation string which is associated with said top node;

iv. means for selecting said translation string associated with said top node as said paraphrase of said syntactic tree; and

v. means for displaying said selected translation string.