Inferencing using disambiguated natural language rules

• US 7,136,807 B2
• Filed: 08/26/2002
• Issued: 11/14/2006
• Est. Priority Date: 08/26/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Mueller, Erik T.
• Primary Examiner(s): {hacek over (S)}mits, Talivaldis Ivars
• Assistant Examiner(s): Ng, Eunice
• Application Number:
  US10/228,122
• Publication Number:
  US 20040039564A1
• Time in Patent Office: 1,541 Days
• Field of Search: 704/9, 700/49, 706/8, 706/60
• US Class Current: 704/9
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method and structure for automatically producing bridging inferences that join two related input sentences, by applying a lexicon and ontology data structure to a first input sentence to produce first input tagged sentences, applying the lexicon and ontology data structure to a second input sentence to produce second input tagged sentences, matching each first input tagged sentence to first rules, generating first inferred tagged sentences from the first rules, matching the first inferred tagged sentences to second rules, generating second inferred tagged sentences from the second rules, matching the second inferred tagged sentences to third rules, generating third inferred tagged sentences from the third rules, and so on, until a final inferred tagged sentence matches any second input tagged sentence. For each final inferred tagged sentence matching a second input tagged sentence, a bridging inference path is produced as output comprising a first input tagged sentence, a first inferred tagged sentence, a second inferred tagged sentence, a third inferred tagged sentence, and so on, and a final inferred tagged sentence. The first inferred tagged sentence in the briding inference path is the particular first inferred tagged sentence that resulted from application of a first rule to the first input tagged sentence. For the second through the last inferred tagged sentences in the bridging inference path, each inferred tagged sentence in the bridging inference path is the particular inferred tagged sentence that resulted from application of a rule to the previous inferred tagged sentence in the bridging inference path.

Claims

1. A method of automatically producing bridging inferences that join two related input phrases, said method comprising:

applying a lexicon and ontology data structure to a first input phrase to produce a first tagged input phrase;

matching said first tagged input phrase to first rules;

generating first inferred phrases from said first rules;

matching said first inferred phrases to second rules;

generating second inferred phrases from said second rules;

applying said lexicon and ontology data structure to a second input phrase to produce a second tagged input phrase;

selecting a first rule of said first rules and a second rule of said second rules that causes a second inferred phrase of said second inferred phrases to match said second tagged input phrase; and

recording, as a bridging inference path, said first rule and said second rule, wherein said first rule and said second rule each comprise a pattern element comprising a lexical entry and an optional variable.

2. The method in claim 1, further comprising providing disambiguated natural language rules.

3. The method in claim 1, further comprising providing rules that are disambiguated as to part of speech, word sense, and coreference.

4. The method in claim 1, further comprising providing rules having:

a first portion;

a connector; and

a second portion.

5. The method in claim 4, further comprising providing connectors comprising one of “

causes,”

“

triggers,” and

“

has-plan.”

6. The method in claim 4, wherein said matching of said first tagged input phrase to first rules comprises matching said first tagged input phrase to said first portion of ones of said first rules, and said first inferred phrases comprise said second portion of matched ones of said first rules.

7. The method in claim 1, further comprising providing said lexicon and ontology data structure to have one or more lexical entries, concepts, and character strings.

8. The method in claim 1, further comprising providing said lexicon and ontology data structure to have:

maps from said character strings to said lexical entries;

maps from said lexical entries to said concepts;

maps from said concepts to said lexical entries; and

maps from said concepts to said concepts.

9. A method of automatically producing predictive inferences from an input phrase, said method comprising:

applying a lexicon and ontology data structure to said input phrase to produce a tagged input phrase;

matching said tagged input phrase to rules;

generating inferred phrases from said rules, wherein said rules comprise a pattern element comprising a lexical entry and an optional variable.

10. The method in claim 9, further comprising providing said rules as disambiguated natural language rules.

11. The method in claim 9, further comprising providing said rules such that said rules are disambiguated as to part of speech, word sense, and coreference.

12. The method in claim 9, further comprising providing said rules to have:

a first portion;

a connector; and

a second portion.

13. The method in claim 12, further comprising providing connectors comprising one of “

causes,”

“

triggers,” and

“

has-plan.”

14. The method in claim 12, wherein said matching of said tagged input phrase to said rules comprises matching said tagged input phrase to said first portion of ones of said rules, and said inferred phrases comprise said second portion of matched ones of said rules.

15. The method in claim 9, further comprising providing said lexicon and ontology data structure to have one or more lexical entries, concepts, and character strings.

16. The method in claim 9, wherein said lexicon and ontology data structure comprises:

maps from said character strings to said lexical entries;

maps from said lexical entries to said concepts;

maps from said concepts to said lexical entries; and

maps from said concepts to said concepts.

17. A computer system with at least one memory and at least one central processing unit, said computer system having a lexicon and ontology data structure and a rule base data structure, each stored in said memory, wherein said lexicon and ontology data structure comprises:

at least one lexical entry, concepts, and character strings;

a first map from said character strings to said lexical entries;

a second map from said lexical entries to said concepts;

a third map from said concepts to said lexical entries; and

a fourth map representing a parent relationship from said concepts to said concepts,

wherein each lexical entry comprises a character string, part of speech, and sense number,

wherein each concept comprises a character string,

wherein said rule base data structure comprises at least one rules,

wherein said rule includes a left pattern, a connective, and a right pattern,

wherein a pattern comprises a list of pattern elements, and

wherein a pattern element comprises a lexical entry and an optional variable.

18. The computer system, as in claim 17, wherein said central processing unit is adapted to take, as input, a first input sentence and a second input sentence and produce, as output, at least one bridging inference path, each comprising a sequence of inferred tagged sentences, by finding at least one sequence of inferred tagged sentences in said rule base such that:

a first inferred tagged sentence in the bridging inference path results from application of a rule of said rules to said first input tagged sentence;

for a second inferred tagged sentence through a last inferred tagged sentence in the bridging inference path, each inferred tagged sentence in the bridging inference path results from application of one of said rules to a previous inferred tagged sentence in the bridging inference path; and

said last inferred tagged sentence in the bridging inference path matches said second input tagged sentence.

19. The computer system, as in claim 18, wherein said central processing unit conducts a unidirectional search from said first input sentence to said second input sentence.

20. The computer system, as in claim 18, wherein said central processing unit conducts a bidirectional search from said first input sentence to said second input sentence.

21. The computer system, as in claim 17, wherein said central processing unit is adapted to take, as input, one sentence and produce, as output, predictive inferences by applying rules to said input sentence such that:

a left pattern of a rule matches the input sentence; and

an output predictive inference comprises a right pattern of said rule instantiated with a connective that match said left pattern of said rule to said input sentence.

22. The computer system, as in claim 21, wherein said connective comprises one of causes, triggers, or has-plan.

23. A computer system with at least one memory and at least one central processing unit, said computer system having a lexicon and ontology data structure and a rule base data structure, each stored in said memory, wherein said lexicon and ontology data structure comprises:

at least one lexical entry, concepts, and character strings,

wherein each lexical entry comprises a character string, part of speech, and sense number,

wherein each concept comprises a character string,

wherein said rule base data structure comprises at least one rules,

wherein said rule includes a left pattern, a connective, and a right pattern,

wherein a pattern comprises a list of pattern elements, and

wherein a pattern element comprises a lexical entry and an optional variable.

24. The computer system, as in claim 23, wherein said central processing unit is adapted to take, as input, a first input sentence and a second input sentence and produce, as output, at least one bridging inference path, each comprising a sequence of inferred tagged sentences, by finding at least one sequence of inferred tagged sentences in said rule base such that:

a first inferred tagged sentence in the bridging inference path results from application of a rule of said rules to said first input tagged sentence;

for a second inferred tagged sentence through a last inferred tagged sentence in the bridging inference path, each inferred tagged sentence in the bridging inference path results from application of one of said rules to a previous inferred tagged sentence in the bridging inference path; and

said last inferred tagged sentence in the bridging inference path matches said second input tagged sentence.

25. The computer system, as in claim 24, wherein said central processing unit conducts a unidirectional search from said first input sentence to said second input sentence.

26. The computer system, as in claim 24, wherein said central processing unit conducts a bidirectional search from said first input sentence to said second input sentence.

27. The computer system, as in claim 23, wherein said central processing unit is adapted to take, as input, one sentence and produce, as output, predictive inferences by applying rules to said input sentence such that:

a left pattern of a rule matches the input sentence; and

an output predictive inference comprises a right pattern of said rule instantiated with a connective that match said left pattern of said rule to said input sentence.

28. The computer system, as in claim 27, wherein said connective comprises one of causes, triggers, or has-plan.