Construction, manipulation, and comparison of a multi-dimensional semantic space Number:7,152,031 from the United States Patent and Trademark Office (PTO) owispatent

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

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.

Patent Number: 7,152,031 Issued on 12/19/2006 to Jensen,   et al.

---

Inventors:	Jensen; Delos C. (Orem, UT), Carter; Stephen R. (Provo, UT)
Assignee:	Novell, Inc. (Provo, UT)
Appl. No.:	09/512,963
Filed:	February 25, 2000

---

Current U.S. Class:	704/10 ; 704/1; 704/9; 707/2; 707/3; 707/4; 707/5
Current International Class:	G06F 17/21 (20060101)
Field of Search:	704/9,10,1 707/100,2-6 715/530,531,532

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5276677		January 1994		Ramamurthy et al.
	5278980		January 1994		Pedersen et al.
	5317507		May 1994		Gallant
	5325298		June 1994		Gallant
	5539841		July 1996		Huttenlocher et al.
	5551049		August 1996		Kaplan et al.
	5619709		April 1997		Caid et al.
	5675819		October 1997		Schuetze
	5694523		December 1997		Wical
	5696962		December 1997		Kupiec
	5708825		January 1998		Sotomayor
	5721897		February 1998		Rubinstein
	5778362		July 1998		Deerwester
	5778378		July 1998		Rubin
	5778397		July 1998		Kupiec et al.
	5794178		August 1998		Caid et al.
	5799276		August 1998		Komissarchik et al.
	5822731		October 1998		Schultz
	5832470		November 1998		Morita et al.
	5867799		February 1999		Lang et al.
	5873056		February 1999		Liddy et al.
	5934910		August 1999		Ho et al.
	5940821		August 1999		Wical
	5963965		October 1999		Vogel
	5966686		October 1999		Heidorn et al.
	5970490		October 1999		Morgenstern
	5974412		October 1999		Hazlehurst et al.
	5991713		November 1999		Unger et al.
	6009418		December 1999		Cooper
	6078953		June 2000		Vaid et al.
	6105044		August 2000		De Rose et al.
	6108619		August 2000		Carter et al.
	6173261		January 2001		Arai et al.
	6205456		March 2001		Nakao
	6289353		September 2001		Hazlehurst et al.
	6295533		September 2001		Cohen
	6297824		October 2001		Hearst et al.
	6311194		October 2001		Sheth et al.
	6317708		November 2001		Witbrock et al.
	6317709		November 2001		Zack
	6356864		March 2002		Foltz et al.
	6363378		March 2002		Conklin et al.
	6459809		October 2002		Jensen et al.
	6470307		October 2002		Turney
	6513031		January 2003		Fries et al.
	6523026		February 2003		Gillis
	6615208		September 2003		Behrens et al.
	6675159		January 2004		Lin et al.

Other References

Mahesh, Ontology Development for Machine Translation: Ideology and Methodology, Technical Report, Computing Research Laboratory, 1996, pp. 1-79. cited by examiner . Onyshkevych et al.,A lexicon for Knowledge-Based MT, US Department of Defense and Carnegie Mellon University, 1995, pp. 1-49. cited by examiner . Noam Chomsky, "Language and Thought," 1993, pp. 18-19, 22-27, 44-45, 60-61. cited by other . Jonathan Culler, "Ferdinand de Saussure--Revised Edition," 1986, pp. 38-57. cited by other . Umberto Eco, Marco Santambrogio and Patrizia Violi (Editors), "Meaning and Mental Representations," 1988, p. 221. cited by other . Donald W. Kahn, "Topology--An Introduction to the Point-Set and Algebraic Areas," 1975, pp. 10-15. cited by other . Paul R. Halmos, "Naive Set Theory," 1960, pp. 56-57, 66-69. cited by other . John G. Hocking and Gail S. Young, "Topology," 1961, pp. 6-7, 56-59, 68-71. cited by other . Umberto Eco, "Semiotics and the Philosophy of Language," 1984, pp. 46-87. cited by other . Noam Chomsky, "The Minimalist Program," 1995, pp. 13-65. cited by other . R. E. Edwards, "Functional Analysis--Theory and Applications," 1965, pp. 10-13, 32-33, 50-53, 62-65, 88-103, 174-203, 224-233. cited by other . Cognitive Science Laboratory at Princeton University, "WordNet--A Lexical Database for English," printed Feb. 10, 2000, selected pages from website. cited by other . Bartell, et al., "Latent Semantic Indexing is an Optimal Special Case of Multidimensional Scaling," Dept. of Computer Science & Engineering, University of California, San Diego, 1992, 7 pages. cited by other . Chomsky, "Language and Thought," 1993, pp. 18-19, 22-27, 44-45, 60-61. cit- ed by other . Chomsky, "The Minimalist Program," 1995, pp. 13-65. cited by other . Cook et al., "Chomsky's Universal Grammar--An Introduction," 1988, pp. 40-74, 131-272. cited by other . Culler, "Ferdinand de Saussure--Revised Edition," 1986 pp. 38-57. cited by other . Eco et al., "Meaning and Mental Representations," 1988, p. 221. cited by other . Eco, "Semiotics and the Philosophy of Language," 1984, p. 46-86. cited by other . Edwards, "Functional Analysis; theory and applications," 1965, pp. 10-13, 32-33, 50-53, 62-65, 88-103, 174-203, 224-233. cited by other . Halmos, "Naive Set Theory," Undergraduate Texts in Mathematics, 1968, pp. 56-57, 66-69. cited by other . Hocking, "Topology,", 1961, pp. 6-7, 56-59, 68-71. cited by other . Hutson, "Applications of Functional Analysis and Operator Theory," 1980, index, preface, and Table of Contents. cited by other . Kahn, "Topology: An Introduction to the Point-Set and Algebraic Areas," 1975, pp. 10-15. cited by other . Khare et al., "Capturing the State of Distributed Systems with XML," Oct. 26, 1997, pp. 1-12. cited by other . Lundquist et al., "Improving Relevance Feedback in the Vector Space Model," 1997, pp. 16-23. cited by other . Mostafa et al., "A Multilevel Approach to Intelligent Information Filtering: Model, System and Evaluation," ACM Transactions on Information Systems, vol. 15, No. 4, Oct. 1997, pp. 368-399. cited by other . Pesetsky, "Zero Syntax: experiencers and cascades," 1995, pp. 1-122. cited by other . Pejtersen, "Semantic Information Retrieval," Communications of the ACM, vol. 41, No. 5, Apr. 1998, pp. 90-92. cited by other . "Platform for Internet Content Selection (PICS)," http://www.w3.org, pp. 1-8. cited by other . Singh, "Unifying Heterogeneous Information Models," Tesserae Information Systems, Inc., http://citeseer.ist.psu.edu.com, pp. 1-13. cited by other . Smith, "Computers and human language," 1991, pp. 205-257. cited by other . "WordNet--a lexical database for the English language," Cognitive Science Laboratory, Princeton University, www.cogsci.princeton.edu, 2 pgs. cited by other.

Primary Examiner: Dorvil; Richemond
Assistant Examiner: Spooner; Lamont
Attorney, Agent or Firm: Marger Johnson & McCollom, P.C.

---

Claims

---

We claim:

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.

---

Description

---

This application is related to co-pending U.S. patent application Ser. No. 09/109,804, titled "METHOD AND APPARATUS FOR SEMANTIC CHARACTERIZATION," filed Jul. 2, 1998.

FIELD OF THE INVENTION

This invention pertains to determining the semantic content of a network, and more particularly to improving searching of the network.

BACKGROUND OF THE INVENTION

The Internet is about content. Content being accessed, published, indexed, analyzed, secured, purchased, stolen, vandalized, etc. Whether the content is white-papers, on-line books, catalogs, real-time games, address books, streaming audio and video, etc., it is content that people and cyber-agents are seeking. The future of the Internet lies not in bandwidth or capacity, but rather the ability to retrieve relevant content. Technology that allows fast and accurate access to relevant content will be used by the masses of carbon and silicon Internet users. Not because it is a better mouse-trap, but because controlled access to relevant content will allow the Internet to thrive, survive, and continue it's explosive growth. Fast and accurate semantic access to Internet content will determine who rules the next Internet era.

Caught between the sheer (and ever growing) volume of content, the huge and rapidly increasing number of Internet users, and a growing sophistication in the demands of those users, the current TCP/IP infrastructure and architecture is showing its inadequacies--it is a victim of its own success. One of the many strategies under consideration by the Internet community for redressing these inadequacies is to build intelligence into the network. Directory Services and Caching are two prime examples of intelligent network components. Adaptive routing with route caching is another example of an intelligent network component.

Yet another example of network intelligence that is receiving close attention these days is the characterization of content by its meaning (semantics). The obvious advantages that accrue with even a moderately successful semantic characterization component are such that almost everyone is tempted to dip a toe in the water. But assigning semantics to information on the Internet is the kind of undertaking that consumes vast amounts of resources.

Accordingly, a need remains for a way to assign semantic meaning to data without consuming large quantities of resources, and for a way to improve semantic understanding as information develops.

SUMMARY OF THE INVENTION

To find a context in which to answer a question, a directed set is constructed. The directed set comprises a plurality of elements and chains relating the concepts. One concept is identified as a maximal element. Chains are established in the directed set, connecting the maximal element to each concept in the directed set. More than one chain can connect the maximal element to each concept. 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 can be used to determine how closely related pairs of concepts are in the directed set.

The foregoing and other features, objects, and advantages of the invention will become more readily apparent from the following detailed description, which proceeds with reference to the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1A shows a computer system on which the invention can operate.

FIG. 1B shows the computer system of FIG. 1A connected to the Internet.

FIG. 2 shows the computer system of FIG. 1A listening to a content stream.

FIG. 3 shows an example of set of concepts that can form a directed set.

FIG. 4 shows a directed set constructed from the set of concepts of FIG. 3 in a preferred embodiment of the invention.

FIGS. 5A 5G show eight different chains in the directed set of FIG. 4 that form a basis for the directed set.

FIG. 6 is a flowchart of a method to construct a directed set in the system of FIG. 1A.

FIG. 7 is a flowchart of a method to add a new concept to a directed set in the system of FIG. 1A.

FIG. 8 is a flowchart of a method to update a basis for a directed set in the system of FIG. 1A.

FIG. 9 is a flowchart of a method of updating the concepts in a directed set in the system of FIG. 1A.

FIGS. 10A and 10B show how a new concept is added and relationships changed in the directed set of FIG. 4.

FIG. 11 is a flowchart of a method using a directed set in the system of FIG. 1A to help in answering a question.

FIG. 12 is a flowchart of a method using a directed set in the system of FIG. 1A to refine a query.

FIG. 13 shows data structures for storing a directed set, chains, and basis chains, such as the directed set of FIG. 3, the chains of FIG. 4, and the basis chains of FIGS. 5A 5G.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 1A shows a computer system 105 on which a method and apparatus for using a multi-dimensional semantic space can operate. Computer system 105 conventionally includes a computer 110, a monitor 115, a keyboard 120, and a mouse 125. Optional equipment not shown in FIG. 1A can include a printer and other input/output devices. Also not shown in FIG. 1A are the conventional internal components of computer system 105: e.g., a central processing unit, memory, file system, etc.

Computer system 105 further includes a concept identification unit (CIU) 130, a chain unit (CU) 135, a basis unit (BU) 140, and a measurement unit (MU) 145. Concept identification unit 130 is responsible for identifying the concepts that will form a directed set, from which the multi-dimensional semantic space can be mapped. One concept is identified as a maximal element: this element describes (more or less concretely) every concept in the directed set. Chain unit 135 is responsible for constructing chains from the maximal element to all other concepts identified by concept identification unit 130. Basis unit 140 is responsible for selecting a subset of the chains to form a basis for the directed set. Because basis unit 140 selects a subset of the chains established by chain unit 135, basis unit 140 is depicted as being part of chain unit 135. However, a person skilled in the art will recognize that basis unit 140 can be separate from chain unit 135. Measurement unit 145 is responsible for measuring how concretely each chain in the basis represents each concept. (How this measurement is performed is discussed below.) In the preferred embodiment, concept identification unit 130, chain unit 135, basis unit 140, and measurement unit 145 are implemented in software. However, a person skilled in the art will recognize that other implementations are possible. Finally, computer system 105 includes a data structure 150 (discussed with reference to FIG. 13 below). The data structure is responsible for storing the concepts, chains, and measurements of the directed set.

FIG. 1B shows computer system 105 connected over a network connection 140 to a network 145. The specifics of network connection 140 are not important, so long as the invention has access to a content stream to listen for concepts and their relationships. Similarly, computer system 105 does not have to be connected to a network 145, provided some content stream is available.

FIG. 2 shows computer system 105 listening to a content stream. In FIG. 2, network connection 140 includes a listening device 205. Listening device 205 (sometimes called a "listening mechanism") allows computer system 105 to listen to the content stream 210 (in FIG. 2, represented as passing through a "pipe" 215). Computer system 105 is parsing a number of concepts, such as "behavior," "female," "cat," "Venus Flytrap," "iguana," and so on. Listening device 205 also allows computer system 105 to determine the relationships between concepts.

But how is a computer, such as computer system 105 in FIGS. 1A, 1B, and 2 supposed to understand what the data it hears means? This is the question addressed below.

Semantic Value

Whether the data expressing content on the network is encoded as text, binary code, bit map or in any other form, there is a vocabulary that is either explicitly (such as for code) or implicitly (as for bitmaps) associated with the form. The vocabulary is more than an arbitrarily-ordered list: an element of a vocabulary stands in relation to other elements, and the "place" of its standing is the semantic value of the element. For example, consider a spoon. Comparing the spoon with something taken from another scene--say, a shovel--one might classify the two items as being somewhat similar. And to the extent that form follows function in both nature and human artifice, this is correct! The results would be similar if the spoon were compared with a ladle. All three visual elements--the spoon, the shovel and the ladle--are topologically equivalent; each element can be transformed into the other two elements with relatively little geometric distortion.

What happens when the spoon is compared with a fork? Curiously enough, both the spoon and the fork are topologically equivalent. But comparing the ratio of boundary to surface area reveals a distinct contrast. In fact, the attribute (boundary)/(surface area) is a crude analog of the fractal dimension of the element boundary.

Iconic Representation

Fractal dimension possesses a nice linear ordering. For example, a space-filling boundary such as a convoluted coastline (or a fork!) would have a higher fractal dimension than, say, the boundary of a circle. Can the topology of an element be characterized in the same way? In fact, one can assign a topological measure to the vocabulary elements, but the measure may involve aspects of homotopy and homology that preclude a simple linear ordering. Suppose, for visual simplicity, that there is some simple, linearly ordered way of measuring the topological essence of an element. One can formally represent an attribute space for the elements, where fork-like and spoon-like resolve to different regions in the attribute space. In this case, one might adopt the standard Euclidean metric for .sup.2 with one axis for "fractal dimension" and another for "topological measure," and thus have a well-defined notion of distance in attribute space. Of course, one must buy into all the hidden assumptions of the model. For example, is the orthogonality of the two attributes justified, i.e., are the attributes truly independent?

The example attribute space is a (simplistic) illustration of a semantic space, also known as a concept space. Above, the concern was with a vocabulary for human visual elements: a kind of visual lexicon. In fact, many researchers have argued for an iconic representation of meaning, particularly those looking for a representation unifying perception and language. They take an empirical positivist position that meaning is simply an artifact of the "binding" of language to perception, and point out that all writing originated with pictographs (even the letter "A" is just an inverted ox head!). With the exception of some very specialized vocabularies, it is an unfortunate fact that most iconic models have fallen well short of the mark. What is the visual imagery for the word "maybe"? For that matter, the above example iconic model has shown how spoons and forks are different, but how does it show them to be the same (i.e., cutlery)?

Propositional Representation

Among computational linguists, a leading competitive theory to iconic representation is propositional representation. A proposition is typically framed as a pairing of an argument and a predicate. For example, the fragment "a red car" could be represented prepositionally as the argument "a car" paired with the predicate "is red." The proposition simply asserts a property (the predicate) of an object (the argument). In this example, stipulating the argument alone has consequences; "a car" invokes the existential quantifier, and asserts instances for all relevant primitive attributes associated with the lexical element "car."

How about a phrase such as "every red car"? Taken by itself, the phrase asserts nothing--not even existence! It is a null proposition, and can be safely ignored. What about "every red car has a radio"? This is indeed making an assertion of sorts, but it is asserting a property of the semantic space itself; i.e., it is a meta-proposition. One can not instantiate a red car without a radio, nor can one remove a radio from a red car without either changing the color or losing the "car-ness" of the object. Propositions that are interpreted as assertions rather than as descriptions are called "meaning postulates."

At this point the reader should begin to suspect the preeminent role of the predicate, and indeed would be right to do so. Consider the phrase, "the boy hit the baseball."

nominative: the boy.fwdarw.(is human), (is .about.adult), (is male), (is .about.infant), etc.

predicate: (hit the baseball).fwdarw. verb: hit.fwdarw.(is contact), (is forceful), (is aggressive), etc. d.o.: the baseball.fwdarw.(is round), (is leather), (is stitched), etc.

The phrase has been transformed into two sets of attributes: the nominative attributes and two subsets of predicate attributes (verb and object). This suggests stipulating that all propositions must have the form (n: n.epsilon.N, p: p.epsilon.P), where N (the set of nominatives) is some appropriately restricted subset of (P) (the power set of the space P of predicates). N is restricted to avoid things like ((is adult) and (is .about.adult)). In this way the predicates can be used to generate a semantic space. A semantic representation might even be possible for something like, "The movie The Boy Hit the Baseball hit this critic's heart-strings!"

Given that propositions can be resolved to sets of predicates, the way forward becomes clearer. If one were to characterize sets of predicates as clusters of points in an attribute space along with some notion of distance between clusters, one could quantify how close any two propositions are to each other. This is the Holy Grail.

Before leaving this section, observe that another useful feature of the propositional model is hierarchy of scope, at least at the sentence level and below. Consider the phrase, "the boy hit the spinning baseball." The first-tier proposition is "x hit y." The second-tier propositions are "x is-a boy," and "y is-a baseball." The third-tier proposition is "y is spinning." By restricting the scope of the semantic space, attention can be focused on "hitting," "hitting spinning things," "people hitting things," etc.

Hyponymy & Meaning Postulates--Mechanisms for Abstraction

Two elements of the lexicon are related by hyponymy if the meaning of one is included in the meaning of the other. For example, the words "cat" and "animal" are related by hyponymy. A cat is an animal, and so "cat" is a hyponym of "animal."

A particular lexicon may not explicitly recognize some hyponymies. For example, the words "hit," "touch," "brush," "stroke," "strike," and "ram" are all hyponyms of the concept "co-incident in some space or context." Such a concept can be formulated as a meaning postulate, and the lexicon is extended with the meaning postulate in order to capture formally the hyponymy.

Note that the words "hit" and "strike" are also hyponyms of the word "realize" in the popular vernacular. Thus, lexical elements can surface in different hyponymies depending on the inclusion chain that is followed.

Topological Considerations

Now consider the metrization problem: how is the distance between two propositions determined? Many people begin by identifying a set S to work with (in this case, S=P, the set of predicates), and define a topology on S. A topology is a set O of subsets of S that satisfies the following criteria:

Any union of elements of O is in O.

Any finite intersection of elements of O is in O.

S and the empty set are both in O.

The elements of O are called the open sets of S. If X is a subset of S, and p is an element of S, then p is called a limit point of X if every open set that contains p also contains a point in X distinct from p.

Another way to characterize a topology is to identify a basis for the topology. A set B of subsets of S is a basis if

S=the union of all elements of B,

for p.epsilon.b.sub..alpha..andgate.b.sub..gamma., (b.sub..alpha., b.sub..gamma..epsilon.B), there exists b.sub..lamda..epsilon.B such that p.epsilon.b.sub..lamda. and b.sub..lamda. b.sub..alpha..andgate.b.sub..gamma..

A subset of S is open if it is the union of elements of B. This defines a topology on S. Note that it is usually easier to characterize a basis for a topology rather than to explicitly identify all open sets. The space S is said to be completely separable if it has a countable basis.

It is entirely possible that there are two or more characterizations that yield the same topology. Likewise, one can choose two seemingly closely-related bases that yield nonequivalent topologies. As the keeper of the Holy Grail said to Indiana Jones, "Choose wisely!"

The goal is to choose as strong a topology as possible. Ideally, one looks for a compact metric space. One looks to satisfy separability conditions such that the space S is guaranteed to be homeomorphic to a subspace of Hilbert space (i.e., there is a continuous and one-to-one mapping from S to the subspace of Hilbert space). One can then adopt the Hilbert space metric. Failing this, as much structure as possible is imposed. To this end, consider the following axioms (the so-called "trennungaxioms"). T.sub.0. Given two points of a topological space S, at least one of them is contained in an open set not containing the other. T.sub.1. Given two points of S, each of them lies in an open set not containing the other. T.sub.2. Given two points of S, there are disjoint open sets, each containing just one of the two points (Hausdorff axiom). T.sub.3. If C is a closed set in the space S, and if p is a point not in C, then there are disjoint open sets in S, one containing C and one containing p. T.sub.4. If H and K are disjoint closed sets in the space S, then there are disjoint open sets in S, one containing H and one containing K.

Note that a set X in S is said to be closed if the complement of X is open. Since the intention is not to take the reader through the equivalent of a course in topology, simply observe that the distinctive attributes of T.sub.3 and T.sub.4 spaces are important enough to merit a place in the mathematical lexicon--T.sub.3 spaces are called regular spaces, and T.sub.4 spaces are called normal spaces--and the following very beautiful theorem: Theorem 1. Every completely separable regular space can be imbedded in a Hilbert coordinate space.

So, if there is a countable basis for S that satisfies T.sub.3, then S is metrizable. The metrized spaced S is denoted as (S, d).

Finally, consider (S), the set of all compact (non-empty) subsets of (S, d). Note that for u, v.epsilon.(S), u.orgate.v.epsilon.(S); i.e., the union of two compact sets is itself compact. Define the pseudo-distance .xi.(x, u) between the point X.epsilon.S and the set u.epsilon.(S) as .xi.(x, u)=min{d(x, y): y.epsilon.u}.

Using .xi. define another pseudo-distance .lamda.(u, v) from the set u.epsilon.(S) to the set v.epsilon.(S): .lamda.(u, v)=max{.xi.(x, v): x.epsilon.u}.

Note that in general it is not true that .lamda.(u, v)=.lamda.(v, u). Finally, define the distance h(u, v) between the two sets u, v.epsilon.(S) as h(u, v)=max {.lamda.(u, v), .lamda.(v, u)}.

The distance function h is called the Hausdorff distance. Since h(u, v)=h(v, u), 0<h(u, v)<.infin. for all u, v.epsilon.(S), u.noteq.v, h(u, u)=0 for all u.epsilon.(S), h(u, v).ltoreq.h(u, w)+h(w, v) for all u, v, w.epsilon.(S), the metric space ((S), h) can now be formed. The completeness of the underlying metric space (S, d) is sufficient to show that every Cauchy sequence {u.sub.k} in ((S), h) converges to a point in ((S),h). Thus, ((S), h) is a complete metric space.

If S is metrizable, then it is ((S), h) wherein lurks that elusive beast, semantic value. For, consider the two propositions, .rho..sub.1=(n.sub.1, p.sub.1), .rho..sub.2=(n.sub.2, p.sub.2). Then the nominative distance |n.sub.2-n.sub.1| can be defined as h({overscore (n.sub.1)}, {overscore (n.sub.2)}), where {overscore (n)} denotes the closure of n. The predicate distance can be defined similarly. Finally, one might define: |.rho..sub.2-.rho..sub.1|=(|n.sub.2-n.sub.1|.sup.2+|p.sub.2-p.sub.1|.sup.- 2).sup.1/2 Equation (1a) or alternatively one might use "city block" distance: |.rho..sub.2-.rho..sub.1|=n.sub.2-n.sub.1|+|p.sub.2-p.sub.1| Equation (1b) as a fair approximation of distance. Those skilled in the art will recognize that other metrics are also possible: for example: (.SIGMA.(.rho..sub.2,i-.rho..sub.1,i).sup.n).sup.1/n Equation (1c)

The reader may recognize ((S), h) as the space of fractals. Some compelling questions come immediately to mind. Might one be able to find submonoids of contraction mappings corresponding to related sets in ((S), h); related, for example, in the sense of convergence to the same collection of attractors? This could be a rich field to plow.

In a chain, for any pair of concepts, one concept is closer to the maximal element than the other; the concept closer to the maximal element can be considered a lineal ancestor of the other concept. (Conversely, the second concept can be considered a lineal descendant of the first concept.) The maximal element is, by definition, closer to itself than any of the other concepts; therefore, the maximal element can be thought of as a lineal ancestor of all other concepts in the directed set (and all other concepts in the directed set can be considered lineal descendants of the maximal element).

An Example Topology

Consider an actual topology on the set P of predicates. This is accomplished by exploiting the notion of hyponymy and meaning postulates.

Let P be the set of predicates, and let B be the set of all elements of 2.sup.2.sup.P, i.e., ((P)), that express hyponymy. B is a basis, if not of 2.sup.P, i.e., (P), then at least of everything worth talking about: S=.orgate.(b: b.epsilon.B). If b.sub..alpha., b.sub..gamma..epsilon.B, neither containing the other, have a non-empty intersection that is not already an explicit hyponym, extend the basis B with the meaning postulate b.sub..alpha..andgate.b.sub..gamma.. For example, "dog" is contained in both "carnivore" and "mammal." So, even though the core lexicon may not include an entry equivalent to "carnivorous mammal," it is a worthy meaning postulate, and the lexicon can be extended to include the intersection. Thus, B is a basis for S.

Because hyponymy is based on nested subsets, there is a hint of partial ordering on S. A partial order would be a big step towards establishing a metric.

At this point, a concrete example of a (very restricted) lexicon is in order. FIG. 3 shows a set of concepts, including "thing" 305, "man" 310, "girl" 312, "adult human" 315, "kinetic energy" 320, and "local action" 325. "Thing" 305 is the maximal element of the set, as every other concept is a type of "thing." Some concepts, such as "man" 310 and "girl" 312 are "leaf concepts," in the sense that no other concept in the set is a type of "man" or "girl." Other concepts, such as "adult human" 315, "kinetic energy" 320, and "local action" 325 are "internal concepts," in the sense that they are types of other concepts (e.g., "local action" 325 is a type of "kinetic energy" 320) but there are other concepts that are types of these concepts (e.g., "man" 310 is a type of "adult human" 315).

FIG. 4 shows a directed set constructed from the concepts of FIG. 3. For each concept in the directed set, there is at least one chain extending from maximal element "thing" 305 to the concept. These chains are composed of directed links, such as links 405, 410, and 415, between pairs of concepts. In the directed set of FIG. 4, every chain from maximal element "thing" must pass through either "energy" 420 or "category" 425. Further, there can be more than one chain extending from maximal element "thing" 305 to any concept. For example, there are four chains extending from "thing" 305 to "adult human" 315; two go along link 410 extending out of "being" 435, and two go along link 415 extending out of "adult" 445. As should be clear, for any given directed link, one of the concepts is the source of the directed link, and the other directed link is the destination (or sink) of the directed link.

Some observations about the nature of FIG. 4: First, the model is a topological space. Second, note that the model is not a tree. In fact, it is an example of a directed set. For example, concepts "being" 430 and "adult human" 315 are types of multiple concepts higher in the hierarchy. "Being" 430 is a type of "matter" 435 and a type of "behavior" 440; "adult human" 315 is a type of "adult" 445 and a type of "human" 450. Third, observe that the relationships expressed by the links are indeed relations of hyponymy. Fourth, note particularly--but without any loss of generality--that "man" 310 maps to both "energy" 420 and "category" 425 (via composite mappings) which in turn both map to "thing" 305; i.e., the (composite) relations are multiple valued and induce a partial ordering. These multiple mappings are natural to the meaning of things and critical to semantic characterization. Finally, note that "thing" 305 is maxima indeed, "thing" 305 is the greatest element of any quantization of the lexical semantic field (subject to the premises of the model).

Metrizing S

FIGS. 5A 5G show eight different chains in the directed set that form a basis for the directed set. FIG. 5A shows chain 505, which extends to concept "man" 310 through concept "energy" 420. FIG. 5B shows chain 510 extending to concept "iguana." FIG. 5C shows another chain 515 extending to concept "man" 310 via a different path. FIGS. 5D 5G show other chains.

FIG. 13 shows a data structure for storing the directed set of FIG. 3, the chains of FIG. 4, and the basis chains of FIGS. 5A 5G. In FIG. 13, concepts array 1305 is used to store the concepts in the directed set. Concepts array 1305 stores pairs of elements. One element identifies concepts by name; the other element stores numerical identifiers 1306. For example, concept name 1307 stores the concept "dust," which is paired with numerical identifier "2" 1308. Concepts array 1305 shows 9 pairs of elements, but there is no theoretical limit to the number of concepts in concepts array 1305. In concepts array 1305, there should be no duplicated numerical identifiers 1306. In FIG. 13, concepts array 1305 is shown sorted by numerical identifier 1306, although this is not required. When concepts array 1305 is sorted by numerical identifier 1306, numerical identifier 1306 can be called the index of the concept name.

Maximal element (ME) 1310 stores the index to the maximal element in the directed set. In FIG. 13, the concept index to maximal element 1310 is "6," which corresponds to concept "thing," the maximal element of the directed set of FIG. 4.

Chains array 1315 is used to store the chains of the directed set. Chains array 1315 stores pairs of elements. One element identifies the concepts in a chain by index; the other element stores a numerical identifier. For example, chain 1317 stores a chain of concept indices "6", "5", "9", "7", and "2," and is indexed by chain index "1" (1318). (Concept index 0, which does not occur in concepts array 1305, can be used in chains array 1315 to indicate the end of the chain. Additionally, although chain 1317 includes five concepts, the number of concepts in each chain can vary.) Using the indices of concepts array 1305, this chain corresponds to concepts "thing," "energy," "potential energy," "matter," and "dust." Chains array 1315 shows one complete chain and part of a second chain, but there is no theoretical limit to the number of chains stored in chain array 1315. Observe that, because maximal element 1310 stores the concept index "6," every chain in chains array 1315 should begin with concept index "6." Ordering the concepts within a chain is ultimately helpful in measuring distances between the concepts. However concept order is not required. Further, there is no required order to the chains as they are stored in chains array 1315.

Basis chains array 1320 is used to store the chains of chains array 1315 that form a basis of the directed set. Basis chains array 1320 stores chain indices into chains array 1315. Basis chains array 1320 shows four chains in the basis (chains 1, 4, 8, and 5), but there is no theoretical limit to the number of chains in the basis for the directed set.

Euclidean distance matrix 1325A stores the distances between pairs of concepts in the directed set of FIG. 4. (How distance is measured between pairs of concepts in the directed set is discussed below. But in short, the concepts in the directed set are mapped to state vectors in multi-dimensional space, where a state vector is a directed line segment starting at the origin of the multi-dimensional space and extending to a point in the multi-dimensional space.) The distance between the end points of pairs of state vectors representing concepts is measured. The smaller the distance is between the state vectors representing the concepts, the more closely related the concepts are. Euclidean distance matrix 1325A uses the indices 1306 of the concepts array for the row and column indices of the matrix. For a given pair of row and column indices into Euclidean distance matrix 1325A, the entry at the intersection of that row and column in Euclidean distance matrix 1325A shows the distance between the concepts with the row and column concept indices, respectively. So, for example, the distance between concepts "man" and "dust" can be found at the intersection of row 1 and column 2 of Euclidean distance matrix 1325A as approximately 1.96 units. The distance between concepts "man" and "iguana" is approximately 1.67, which suggests that "man" is closer to "iguana" than "man" is to "dust." Observe that Euclidean distance matrix 1325A is symmetrical: that is, for an entry in Euclidean distance matrix 1325A with given row and column indices, the row and column indices can be swapped, and Euclidean distance matrix 1325A will yield the same value. In words, this means that the distance between two concepts is not dependent on concept order: the distance from concept "man" to concept "dust" is the same as the distance from concept "dust" to concept "man."

Angle subtended matrix 1325B is an alternative way to store the distance between pairs of concepts. Instead of measuring the distance between the state vectors representing the concepts (see below), the angle between the state vectors representing the concepts is measured. This angle will vary between 0 and 90 degrees. The narrower the angle is between the state vectors representing the concepts, the more closely related the concepts are. As with Euclidean distance matrix 1325A, angle subtended matrix 1325B uses the indices 1306 of the concepts array for the row and column indices of the matrix. For a given pair of row and column indices into angle subtended matrix 1325B, the entry at the intersection of that row and column in angle subtended matrix 1325B shows the angle subtended the state vectors for the concepts with the row and column concept indices, respectively. For example, the angle between concepts "man" and "dust" is approximately 51 degrees, whereas the angle between concepts "man" and "iguana" is approximately 42 degrees. This suggests that "man" is closer to "iguana" than "man" is to "dust." As with Euclidean distance matrix 1325A, angle subtended matrix 1325B is symmetrical.

Not shown in FIG. 13 is a data structure component for storing state vectors (discussed below). As state vectors are used in calculating the distances between pairs of concepts, if the directed set is static (i.e., concepts are not being added or removed and basis chains remain unchanged), the state vectors are not required after distances are calculated. Retaining the state vectors is useful, however, when the directed set is dynamic. A person skilled in the art will recognize how to add state vectors to the data structure of FIG. 13.

Although the data structure for concepts array 1305, maximal element 1310 chains array 1315, and basis chains array 1320 in FIG. 13 are shown as arrays, a person skilled in the art will recognize that other data structures are possible. For example, concepts array could store the concepts in a linked list, maximal element 1310 could use a pointer to point to the maximal element in concepts array 1305, chains array 1315 could use pointers to point to the elements in concepts array, and basis chains array 1320 could use pointers to point to chains in chains array 1315. Also, a person skilled in the art will recognize that the data in Euclidean distance matrix 1325A and angle subtended matrix 1325B can be stored using other data structures. For example, a symmetric matrix can be represented using only one half the space of a full matrix if only the entries below the main diagonal are preserved and the row index is always larger than the column index. Further space can be saved by computing the values of Euclidean distance matrix 1325A and angle subtended matrix 1325B "on the fly" as distances and angles are needed.

Returning to FIGS. 5A 5G, how are distances and angles subtended measured? The chains shown in FIGS. 5A 5G suggest that the relation between any node of the model an