Method of transforming natural language expression into formal language representation

• US 8,024,177 B2
• Filed: 09/28/2007
• Issued: 09/20/2011
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Meredith Family Revocable Trust
• Original Assignee: Cycorp, Inc.
• Inventors: Witbrock, Michael John, Deaton, Christopher James, Lenat, Douglas Bruce
• Primary Examiner(s): Neway; Samuel G
• Application Number:
  US11/864,730
• Publication Number:
  US 20090089045A1
• Time in Patent Office: 1,453 Days
• Field of Search: 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

This invention comprises a series of steps which transforms one or more natural language expressions into a single, well-formed formal language representation. Each natural language expression is partially parsed into simple fragments, each of which is then associated with one or more short formal expressions. Each formal expression is constructed in such a way as to contain one or more placeholder variables, each of which is associated with one or more attributes to constrain the types of entities that each variable can potentially represent. The resulting plurality of formal expressions is then filtered for relevance within a given context, and the surviving expressions manipulated based upon a plurality of rules, which are cognizant of the attributes associated with each variable contained therein. A user is then presented with the resulting plurality of formal expressions, whereupon the user optionally selects, rejects, adds to, logically connects and otherwise manipulates each member of said plurality. When the user is satisfied that the plurality represents an intended meaning, the formal expressions are combined into a single, formal representation.

Claims

1. A method of transforming natural language expression into formal language representation comprising the steps of:

partially parsing one or more natural language expressions;

associating one or more formal expressions with each parsed fragment;

selecting an appropriate subset of said formal expressions for user review;

converting said subset into suitable form for presentation to a user, wherein said suitable form comprises a plurality of natural language paraphrases;

presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset resulting in a plurality of formal expressions, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of presenting said plurality of natural language paraphrases to the user wherein the user indicates that certain placeholder variables within said natural language paraphrases represent the same entity and should be unified;

combining the resulting plurality of formal expressions into a single formal representation; and

compiling said single formal expression into one or more expressions suitable for querying a knowledge store.

2. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the steps of partially parsing by computer one or more natural language expressions into one or more parsed fragments, and associating one or more formal expressions with each parsed fragment, comprise the steps of:

identifying ontological entities associated with one or more natural language expressions; and

generating one or more formal expressions for each identified ontological entity.

3. A method of transforming natural language expression into formal language representation as recited in claim 2, wherein the step of identifying ontological entities associated with one or more natural language expressions comprises the steps of:

associating words and simple phrases within each natural language expression with one or more ontological entities;

filtering said ontological entities for relevance; and

adding one or more additional candidate ontological entities.

4. A method of transforming natural language expression into formal language representation as recited in claim 3, wherein the step of associating words and simple phrases within each natural language expression with one or more ontological entities comprises the steps of:

parsing short natural language phrases;

matching unparsed natural language words with a dictionary; and

associating found words and phrases with one or more ontological entities.

5. A method of transforming natural language expression into formal language representation as recited in claim 3, wherein the step of filtering ontological entities for relevance comprises the steps of:

disambiguating the ontological entities using a context-specific classification tree; and

marking those ontological entities as to their likely relevance.

6. A method of transforming natural language expression into formal language representation as recited in claim 3, wherein the step of adding one or more additional candidate ontological entities comprises the steps of:

associating certain ontological entities with additional ontological candidates based upon a context-specific set of rules; and

applying said associations to the existing plurality of ontological entities.

7. A method of transforming natural language expression into formal language representation as recited in claim 2, wherein the step of generating one or more formal expressions for each identified ontological entity comprises the steps of:

classifying each ontological entity as either predicate, collection or other;

associating each predicate-class ontological entity with a formal expression constructed by combining a predicate-determined template with a set of generated placeholder variables each uniquely representing a required argument; and

associating each collection-class ontological entity with a formal expression asserting that a uniquely generated placeholder variable X is an instance of said ontological entity.

8. A method of transforming natural language expression into formal language representation as recited in claim 7, further comprising the steps of:

classifying each placeholder variable of a given formal expression;

matching said classification with one or more ontological entities;

substituting said placeholder variable with said ontological entity; and

generating a new formal expression for each substitution or permutation thereof.

9. A method of transforming natural language expression into formal language representation as recited in claim 7, further comprising the steps of:

classifying each placeholder variable of a given formal expression;

matching said classification with one or more applicable rules;

for each match, adding an ontological entity, the type of which is determined by the applicable rule, to the plurality of identified ontological entities; and

generating a new formal expression for each ontological entity added.

10. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of selecting an appropriate subset of said formal expressions for user review comprises the steps of:

determining that two or more formal expressions contain placeholder variables which represent the same entity; and

unifying said arguments.

11. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of selecting an appropriate subset of said formal expressions for user review comprises the steps of:

determining that one or more formal expressions are not relevant within a given context; and

removing said formal expressions.

12. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of selecting an appropriate subset of said formal expressions for user review comprises the steps of:

determining that one or more formal expressions are not logically consistent with a set of axioms as stored within a context-specific and/or generalized knowledge base; and

removing said formal expressions.

13. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of natural language paraphrases to the user in such a way as to facilitate the grouping of said paraphrases into one or more composite representations, including but not limited to those formed using logical connectives such as conjunction, disjunction and negation.

14. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of natural language paraphrases to the user in such a way as to permit the user to indicate that certain natural language paraphrases and the formal expressions they represent should be removed.

15. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of natural language paraphrases to the user in such a way as to permit the user to add to said plurality of natural language paraphrases, along with the underlying formal expressions they represent.

16. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of converting by computer said subset into suitable form for presentation to a user comprises the step of:

generating a graphical representation for each formal expression.

17. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of graphical representations to the user in such a way as to facilitate the grouping of said graphical representations into one or more composite representations, including but not limited to those formed using logical connectives such as conjunction, disjunction and negation.

18. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of graphical representations to the user in such a way as to permit the user to indicate that certain placeholder variables within said graphical representations represent the same entity and should be unified.

19. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of graphical representations to the user in such a way as to permit the user to indicate that certain graphical representations and the formal expressions they represent should be removed.

20. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of presenting said suitable form to a user wherein the user selects, rejects, adds to, logically connects, and otherwise manipulates members of said subset comprises the step of:

presenting a plurality of graphical representations to the user in such a way as to permit the user to add to said plurality of graphical representations, along with the underlying formal expressions they represent.

21. A method of transforming natural language expression into formal language representation as recited in claim 1, wherein the step of combining the plurality of formal expressions into a single formal representation comprises the step of:

logically connecting two or more formal expressions, as directed by a user during a previous step, including but not limited to conjunction, disjunction and negation; and

conjoining any remaining formal expressions.

22. A method of transforming natural language expression into formal language representation as recited in claim 21, further comprising the steps of:

identifying one or more formal expressions marked for removal by a user during a previous step; and

removing said identified formal expressions.

23. A method of transforming natural language expression into formal language representation as recited in claim 21, further comprising the steps of:

identifying one or more formal expressions containing no placeholder variables; and

removing said identified formal expressions.