Method and system for compiling a lexical knowledge base

• US 7,383,169 B1
• Filed: 04/13/1994
• Issued: 06/03/2008
• Est. Priority Date: 04/13/1994
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vanderwende, Lucretia H., Heidorn, George E., Jensen, Karen, Dolan, William B., Richardson, Stephen D.
• Primary Examiner(s): Thomas; Joseph
• Application Number:
  US08/227,247
• Time in Patent Office: 5,165 Days
• Field of Search: 364/419.01, 364/419.08, 364/419.11, 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A lexical knowledge base is compiled automatically from a machine-readable source (such as an on-line dictionary or unstructured text). The preferred embodiment of the invention makes use of “backward linking,” by which inverse semantic relations are discerned from the text and used to augment the knowledge base. By this arrangement, on-line dictionaries and other texts can provide formidable sources of “common sense” knowledge about the world.

Claims

1. A method for generating a lexical knowledge base in a memory of a machine, said generating comprising the steps:

(a) parsing a segment of text to obtain a logical form corresponding thereto using a natural language parser associated with said machine;

(b) using said machine to extract from the logical form at least one complex semantic relation structure, the complex semantic relation structure including at least a headword, a semantic relation, and a value;

the value of said complex semantic relation structure including a primary value term, a lower level relation, and a lower level value term;

(c) storing in the lexical knowledge base in said machine memory the complex semantic relation structure in association with the headword; and

(d) augmenting the lexical knowledge base by;

(1) inverting the semantic relation structure; and

(2) storing in said memory, in association with the primary value term, the inverted complex semantic relation structure, said stored inverted complex semantic relation structure including the lower level relation and the lower level value term.

2. The method of claim 1 in which the natural language parser analyzes for at least 8 of the following semantic relations:

part, part_of, typical_subject, typical_subject_of, typical_object, typical_object_of, purpose, purpose_of, location_of, located_at, and synonym.

3. The method of claim 1 in which the parsing and extracting steps include:

(a) providing a natural language corpus;

(b) analyzing the corpus by machine to identify a set of text segments therein;

(c) automatically discerning from the text segments a first collection of complex semantic relation structures; and

(d) storing data from the first collection of complex semantic relation structures as part of the lexical knowledge base;

and in which the augmenting step includes;

(e) inverting the first collection of semantic relation structures to yield a second collection of corresponding, inverted semantic relation structures; and

(f) storing data from the second collection of corresponding, inverted semantic relation structures in said memory.

4. The method of claim 3 in which the parsing step includes string searching the corpus by machine to discern semantic relation structures.

5. A method for generating a lexical knowledge base in a machine, said generating comprising the steps:

(a) using a natural language parser associated with said machine to parse a segment of text to obtain a logical form;

(b) using said machine to extract from the logical form a semantic relation structure, the semantic relation structure including at least a headword, a semantic relation, and a value;

(c) storing in a memory associated with said machine the semantic relation structure in association with the headword in the lexical knowledge base; and

(d) augmenting the lexical knowledge base by;

(1) inverting the semantic relation structure; and

(2) storing, in association with the value, the inverted semantic relation structure.

6. The method of claim 5 in which the semantic relation structure includes at least one element in addition to a headword, a semantic relation, and a value.

7. The method of claim 6 in which:

the value of the extracted semantic relation structure includes a primary value term, a lower level relation, and a lower level value term; and

the augmenting of the lexical knowledge base includes storing in association with the primary value term the inverted semantic relation structure, said stored inverted semantic relation structure including the lower level relation and the lower level value term.

8. The method of claim 6 which includes providing an on-line dictionary from which the text is automatically parsed, the on-line dictionary providing a plurality of definitions for a given term, each of said definitions defining a sense of the term, said senses being numbered in the on-line dictionary, and in which the augmenting of the lexical knowledge base includes storing in association with the inverted semantic relation structure a dictionary sense number associated therewith.

9. The method of claim 6 in which the parser is a broad coverage parser.

10. The method of claim 6 in which the parsing step includes:

(1) applying a first set of rules to the segment of text to yield a syntactic structure corresponding thereto; and

(2) applying a second set of rules to the syntactic structure to produce the logical form.

11. The method of claim 5 which includes:

providing a natural language corpus;

using the machine to analyze the corpus to identify a collection of text segments therein;

performing steps (a)-(d) a first time on the identified text segments to produce an augmented lexical knowledge base, the augmentation of the knowledge base serving to enhance subsequent text parsing; and

performing steps (a)-(d) a second time on the identified texts to further augment the knowledge base;

wherein the augmentation of the lexical knowledge base by the first performance of steps (c) and (d) enhances the parsing of the texts in the second performance of step (a).

12. The method of claim 11 which includes:

when performing step (b) the first time, extracting a first set of semantic relations; and

when performing step (b) the second time, identifying a second set of semantic relations, the second set of semantic relations being different from the first.

13. The method of claim 12 in which only the first set of semantic relations includes “

hypernym.”

14. The method of claim 12 in which only the first set of semantic relations includes “

user,”

“

domain” and

“

manner.”

15. A machine-implemented method for generating a lexical knowledge base comprising the steps:

(A) using a computer to automatically process a text and identify at least a first semantic relation structure therein, said first semantic relation structure including at least four elements;

(B) using the computer to invert the first semantic relation structure to yield a second corresponding, inverted semantic relation structure; and

(C) storing data from the second semantic relation structure as part of a lexical knowledge base.

16. The method of claim 15 in which:

the identified semantic relation structure includes a headword, a primary relation, and a primary value;

the primary value includes a primary value term, a lower level relation, and a lower level value term; and

the storing includes storing in association with the primary value term the second semantic relation structure, said stored, second semantic relation structure including the lower level relation and the lower level value term.

17. The method of claim 15 which includes providing an on-line dictionary from which the text is parsed, the on-line dictionary providing a plurality of definitions for a given term, each of said definitions defining a sense of the term, said senses being numbered in the on-line dictionary, and in which the augmenting of the lexical knowledge base includes storing in association with the inverted semantic relation structure a dictionary sense number associated therewith.

18. The method of claim 15 in which the identifying step includes automatically parsing the text with a natural language parser, the parsing including:

applying a first set of rules to the text to yield a syntactic structure corresponding thereto;

applying a second set of rules to the syntactic structure to produce a corresponding logical form; and

extracting from the logical form said first semantic relation structure, said first semantic relation structure including at least a headword, a semantic relation, and a value.

19. The method of claim 18 in which the natural language parser analyzes for at least 8 of the following semantic relations:

part, part_of, typical_subject, typical_subject_of, typical_object, typical_object_of, purpose, purpose_of, location_of, located_at, and synonym.

20. The method of claim 15 in which the identifying step includes string searching the text to discern semantic relation structures.

21. The method of claim 15 in which:

step (A) includes;

(a) providing a natural language corpus;

(b) analyzing the corpus by machine to identify a set of text segments therein;

(c) automatically discerning from the text segments a first collection of semantic relation structures; and

(d) storing data from the first collection of semantic relation structures as part of the lexical knowledge base;

step (B) includes;

(e) inverting the first collection of semantic relation structures to yield a second collection of corresponding, inverted semantic relation structures; and

step (C) includes;

(f) augmenting the lexical knowledge base by storing data from the second collection of corresponding, inverted semantic relation structures.

22. The method of claim 21 which includes performing steps (a)-(f) a first time, the augmentation of the knowledge base resulting from performance of step (f) serving to enhance subsequent discernment of semantic relation structures, and then repeating steps (c)-(f) a second time;

wherein augmentation of the knowledge base by the first performance of step (f) enhances the discerning of semantic relation structures by the second performance of step (c).

23. The method of claim 22 which includes discerning a first set of semantic relation structures in the first performance of step (c), and discerning a second set of semantic relation structures in the second performance of step (c), the second set of semantic relations being different from the first.

24. The method of claim 23 in which only the first set of semantic relations includes “

hypernym.”

25. The method of claim 23 in which only the first set of semantic relations includes “

user,”

“

domain” and

“

manner.”

26. In a machine-implemented method of generating a lexical knowledge base comprised of using a computer to parse a collection of texts to identify semantic relation structures, and storing data from said semantic relation structures in the lexical knowledge base, an improvement comprising using the computer to iteratively parse the same collection of texts, successive parsings relying on successively enhanced versions of the lexical knowledge base, wherein semantic relations identified in one parsing operation serve to enhance discernment of semantic relations in subsequent parsing operations.

27. The method of claim 26 in which the iterative parsing includes:

(1) applying a first set of rules to the collection of texts to yield a collection of syntactic structures corresponding thereto;

(2) applying a second set of rules to the syntactic structures to produce corresponding logical forms; and

(3) applying a third set of rules to the logical forms to obtain semantic relation structures, said structures including at least one instance of a triple comprising a headword, a semantic relation, and a value.

28. A system comprising:

(a) machine-implemented means for parsing a segment of text to obtain a logical form;

(b) machine-implemented means for extracting from the logical form a semantic relation structure, the semantic relation structure including at least a headword, a semantic relation, and a value;

(c) computer memory defining a lexical knowledge base in which the semantic relation structure associated with the headword is stored; and

(d) means for augmenting the lexical knowledge base including means for;

(1) inverting the semantic relation structure; and

(2) storing, in association with the value, the inverted semantic relation structure.

29. The system of claim 28 in which:

the value of the extracted semantic relation structure includes a primary value term, a lower level relation, and a lower level value term; and

the means for augmenting includes means for storing in association with the primary value term the inverted semantic relation structure, said stored inverted semantic relation structure including the lower level relation and the lower level value term.

30. The apparatus of claim 28 in which the parsing means is a broad coverage parser.