Discovery of inference rules from text

• US 7,146,308 B2
• Filed: 04/05/2001
• Issued: 12/05/2006
• Est. Priority Date: 04/05/2001
• Status: Expired due to Fees

• Current Assignee: Dekang Lin, Patrick Pantel
• Original Assignee: Dekang Lin, Patrick Pantel
• Inventors: Pantel, Patrick, Lin, Dekang
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Shortledge, Thomas E.
• Application Number:
  US09/826,355
• Publication Number:
  US 20030004915A1
• Time in Patent Office: 2,070 Days
• Field of Search: 704/10, 704/8, 704/2, 704/7, 704/4, 704/9, 455/406, 455/407, 455/408, 455/415, 455/550.1, 455/565, 455/566, 379/114.01, 379/114.03, 379/114.09, 379/114.21, 379/114.22, 379/114.23, 379/114.26, 379/140
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

The present invention provides a facility for discovering a set of inference rules, such as “X is author of Y≈X wrote Y”, “X solved Y≈X found a solution to Y”, and “X caused Y≈Y is triggered by X”, by analyzing a corpus of natural language text. The corpus is parsed to identify grammatical relationships between words and to build dependency trees formed of the relationships between the words. Paths linking words in the dependency trees are identified. If two paths tend to link the same sets of words, their meanings are taken to be similar. An inference rule is generated for each pair of similar paths. The output of the inventive system is a set of inference rules and a database in which to store these inference rules. The rules generated by the system are interpretable by machines and used in other applications (e.g. information extraction, information retrieval, and machine translation).

Claims

1. A method of building a database from text, the method comprising the steps of:

parsing text to identify paths formed by concatenated relationships between words in the text; and

generating a database of inference rules comprising pairs of semantically equivalent paths by associating, in a computer, paths with each other based on a similarity measure between the paths.

2. The method of claim 1 in which the similarity measure is based on the frequency of occurrence of words in the paths.

3. The method of claim 2 in which the words are at the end points of the paths.

4. The method of claim 1 in which the step of associating paths with each other comprises the step of counting occurrences of words at the end points of specific paths.

5. The method of claim 4 in which the step of associating paths comprises the step of comparing counts of occurrences of words and associating paths based on the counts of occurrences of the words.

6. The method of claim 5 in which paths are associated only when the similarity measure exceeds a threshold.

7. A method of information retrieval, the method comprising the steps of:

initiating a search for electronic information; and

expanding the search by reference to associated paths in a database constructed according to the method of claim 1.

8. The method of claim 7 in which the search is initiated from a location remote from the location of the database.

9. The method of claim 7 in which, in the method steps of claim 1, the similarity measure is based on the frequency of occurrence of words in the paths.

10. The method of claim 9, in which, in the method steps of claim 1, the words are at the end points of the paths.

11. The method of claim 7 in which, in the method steps of claim 1, the step of associating paths with each other comprises the step of counting occurrences of words at the end points of specific paths.

12. The method of claim 11 in which the step of associating paths comprises the step of comparing counts of occurrences of words and associating paths based on the counts of occurrences of the words.

13. The method of claim 12 in which paths are associated only when the similarity measure exceeds a threshold.

14. Computer readable media containing instructions for carrying out the method steps of claim 1.

15. Computer readable media of claim 14 in which, in the instructions for carrying out the method steps of claim 1, the similarity measure is based on the frequency of occurrence of words in the paths.

16. Computer readable media of claim 15 in which, in the instructions for carrying out the method steps of claim 1, the words are at the end points of the paths.

17. Computer readable media of claim 14, in which the instructions for carrying out the step of associating paths with each other comprise instructions for carrying out the step of counting occurrences of words at the end points of specific paths.

18. Computer readable media of claim 17 in which the instructions for carrying out the method step of associating paths comprise instructions for carrying out the method step of comparing counts of occurrences of words and associating paths based on the counts of occurrences of the words.

19. Computer readable media of claim 18 in which, in the instructions for carrying out the method steps, paths are associated only when the similarity measure exceeds a threshold.