Construction, manipulation, and comparison of a multi-dimensional semantic space

• US 7,152,031 B1
• Filed: 02/25/2000
• Issued: 12/19/2006
• Est. Priority Date: 02/25/2000
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Carter, Stephen R., Jensen, Delos C.
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US09/512,963
• Time in Patent Office: 2,489 Days
• Field of Search: 704/9, 704/10, 704/1, 707/100, 707 2- 6, 715/530, 715/531, 715/532
• US Class Current: 704/10
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A directed set can be used to establish contexts for linguistic concepts: for example, to aid in answering a question, to refine a query, or even to determine what questions can be answered given certain knowledge. A directed set includes a plurality of elements and chains relating the concepts. One concept is identified as a maximal element. The chains connect the maximal element to each concept in the directed set, and more than one chain can connect the maximal element to any individual concept either directly or through one or more intermediate concepts. A subset of the chains is selected to form a basis for the directed set. Each concept in the directed set is measured to determine how concretely each chain in the basis represents it. These measurements for a single concept form a vector in Euclidean k-space. Distances between these vectors can be used to determine how closely related pairs of concepts are in the directed set.

Claims

1. A method for building a directed set to allow a user of a computer system to find a context in which to answer a question, the method comprising:

identifying a plurality of concepts to form a directed set, wherein only one concept is a maximal element;

establishing directed links between pairs of concepts in the directed set, the directed links defining “

is a”

relationships between the concepts in the pairs of concepts, so that each concept is either a source or a sink of at least one directed link;

establishing chains in the directed set from the maximal element to each other concept, where for each pair of concepts in each chain, one of the pair of concepts is a lineal ancestor of the other of the pair of concepts;

selecting one or more chains in the directed set as a basis; and

measuring how concretely each concept is represented in each chain in the basis.

2. A method according to claim 1 further comprising creating a state vector for each concept in the directed set, wherein each state vector includes as its components measures of how concretely the concept is represented in each chain in the basis.

3. A method according to claim 2 wherein creating a state vector for each concept in the directed set includes measuring a distance between the state vectors for each pair of concepts.

4. A method according to claim 3, wherein measuring a distance between the state vectors for each pair of concepts includes measuring a Euclidean distance between the state vectors for each pair of concepts.

5. A method according to claim 1 further comprising introducing a new concept into the directed set.

6. A method according to claim 5 wherein introducing a new concept includes:

adding a new chain from the maximal element to the new concept; and

measuring new distances from the new concept to each chain in the basis.

7. A method according to claim 1 further comprising:

discarding the chains in the basis; and

re-selecting one or more chains in the directed set as a new basis.

8. A method according to claim 7, wherein:

discarding the chains in the basis includes discarding the chains in the basis independent of any document; and

re-selecting one or more chains in the directed set as a new basis includes re-selecting one or more chains in the directed set as the new basis independent of any document.

9. A method according to claim 1 further comprising:

receiving new information about a first concept in the directed set; and

updating the directed links for the first concept.

10. A method according to claim 9 wherein updating the directed links includes at least one of:

a) removing an existing chain from the maximal element to the first concept; and

b) establishing a new chain from the maximal element to the first concept, where for each pair of concepts in the new chain, one of the pair of concepts is a lineal ancestor of the other of the pair of concepts.

11. A method according to claim 1 wherein identifying a plurality of concepts includes:

listening to a content stream; and

parsing the concepts from the content stream.

12. A method according to claim 1 wherein establishing chains in the directed set from the maximal element to each other concept includes:

listening to a content stream;

identifying a relationship between a first concept and a second concept from the content stream; and

establishing a chain from the maximal element to the first concept through the second concept to model the relationship between the first and second concepts.

13. A method according to claim 1, wherein establishing directed links includes:

establishing a first directed link from a second concept to a first concept; and

establishing a second directed link from a third concept to the first concept.

14. A computer-readable medium containing a program to build a directed set to allow a user of a computer system to find a context in which to answer a question, the program comprising:

identification software to identify a plurality of concepts to form a directed set, wherein only one concept is a maximal element;

chain-establishment software to establish chains in the directed set from the maximal element to each other concept, where for each pair of concepts in each chain, one of the pair of concepts is a lineal ancestor of the other of the pair of concepts;

chain-selection software to select one or more chains in the directed set as a basis; and

measurement software to measure how concretely each concept is represented in each chain in the basis.

15. A storage medium for storing a lexicon as a directed set for use by an application program to establish a context for a query, the storage medium comprising:

a data structure stored in the storage medium, the data structure including the lexicon and including;

a plurality of concepts stored in the storage medium, wherein only one concept is a maximal element;

at least one chain extending from the maximal element to each concept, wherein the at least one chain includes an ordered subset of the concepts, beginning with the maximal element and ending with the other concept, where for each pair of concepts in each chain, one of the pair of concepts is a lineal ancestor of the other of the pair of concepts;

a plurality of distances between pairs of concepts;

at least one chain identified as a chain in a basis for the directed set; and

measurements of how concretely each concept is represented in each chain in the basis.

16. An apparatus on a computer system to build a directed set to allow a user of the computer system to find a context in which to answer a question, the apparatus comprising:

a data structure to store the directed set;

an identification unit to identify a plurality of concepts in the directed set, wherein the directed set includes only one maximal element;

a chain unit to establish chains in the directed set from the maximal element to each other concept, where for each pair of concepts in each chain, one of the pair of concepts is a lineal ancestor of the other of the pair of concepts;

a basis unit to select one or more chains in the directed set as a basis; and

a measurement unit to measure how concretely each concept is represented in each chain in the basis.

17. An apparatus on a computer system to build a directed set to allow a user of the computer system to determine what questions can be answered using a given context, the apparatus comprising:

a data structure to store the directed set;

an identification unit to identify a plurality of concepts in the directed set, wherein the directed set includes only one maximal element;

a chain unit to establish chains in the directed set from the maximal element to each other concept, where for each pair of concepts in each chain, one of the pair of concepts is a lineal ancestor of the other of the pair of concepts;

a basis unit to select one or more chains in the directed set as a basis; and

a measurement unit to measure how concretely each concept is represented in each chain in the basis.

18. An apparatus on a computer system to enable a user of the computer system to find a context in which to answer a question, the apparatus comprising:

a directed set stored in the computer system, the directed set including a plurality of first concepts, only one maximal element, and at least one basis chain extending from the maximal element to each one the other concepts, where for each pair of first concepts in each basis chain, one of the pair of first concepts is a lineal ancestor of the other of the pair of first concepts;

an input for receiving a content stream;

a listening mechanism listening to the content stream and parsing the content stream into second concepts; and

a measurement mechanism measuring distances between pairs of the second concepts according to the plurality of first concepts and the basis chains of the directed set.

19. An apparatus according to claim 18, wherein:

the apparatus further comprises a network connection; and

the input for receiving the content stream is coupled to the network connection.

20. An apparatus according to claim 18, wherein the measurement mechanism includes:

a state vector constructor converting each second concept into a state vector in Euclidean k-space; and

measuring means for measuring the distance between state vectors corresponding to the second concepts according to the plurality of first concepts and the basis chains of the directed set.

21. An apparatus according to claim 20, wherein the measuring means includes Euclidean measuring means for measuring a Euclidean distance between state vectors corresponding to the second concepts according to the plurality of first concepts and the basis chains of the directed set.

22. An apparatus according to claim 18, the directed set further including a directed link to a third concept from a fourth concept, the directed link establishing an “

is a”

relationship between the third concept and the fourth concept.

23. An apparatus according to claim 22, the directed set further including a second directed link to the third concept from a fifth concept, the directed link establishing an “

is a”

relationship between the third concept and the fifth concept.