...rigor understanding the intended semantics of such links. Since then, have attempted to work out a framework and a system for dealing rigorously with semantics in link-based representations and for efficiently organizing and retrieving information using such representations. This is an evolving activity in which many subtle (and some not-so-subtle) issues need to be addressed and adequately provided for. It's like solving a large puzzle in which many of the necessary pieces do not yet exist and so need to be invented. Moreover, the remaining pieces are mixed together with many distracting and misleading pieces that need to be recognized as such and set aside as pieces of other puzzles. In this article I will present some of the pieces of this puzzle, as I currently understand them, and describe how they came about, how they fit together, what problems they solve, and some of the things that the resulting framework can do. These ideas apply not just to explicitly link-based representations but also to many similar representations, referred to variously as frames with slots, entities with relationships, objects with attributes, tables with columns, and records with fields, and to the classes and variables of object-oriented data structures. I invite the reader to join me in the continuing evolution of these ideas.

This article expands on an invited talk I presented at the 2004 Principles of Knowledge Representation and Reasoning conference in Whistler, Canada. It was one of two inaugural talks in a new series on "Great Moments in Knowledge Representation." I was asked to talk about the paper "What's in a Link'--how it came to be, what was happening in the field at the time, and how the ideas have evolved since then. This gave me an opportunity to think about a number of ideas that led up to the writing of that paper--how they relate to each other and how they continue to develop. This article provides an opportunity to continue those thoughts.

Two of my fundamental assumptions will quickly become apparent: first that notations matter (and I hope to give you a feeling for why this is so), and second, that subsumption and generality play an important role in human-level reasoning. With respect to the first, I ask you to speculate how much of modern mathematics would have happened if we had been constrained to try it in roman numerals. In another dimension, you may be aware of algorithms that have different complexity if numbers are represented in unary notation rather than binary or decimal. In this article, I will illustrate how some key reasoning algorithms, and in particular how subsumption algorithms, can depend on the notations that we use to represent knowledge and how a proper combination of representation and algorithm can answer some of the following questions: How does a reasoning system find relevant pieces of information and relevant rules of inference when it knows millions of things? How does it acquire and organize millions of items of information? How does it integrate new information with previously existing information? How does it use its knowledge to impose structure on situations?

I will start by describing some background experiences and thoughts that preceded my writing the "What's in a Link" paper. These provided the perspective that I brought to the task. After that, I will present some of the key ideas from the paper and a discussion of how some of those ideas have matured since then. Finally, I will describe some practical applications of these ideas in the context of knowledge access and information retrieval and will conclude with some thoughts about where I think we can go from here.

A Perspective on Human-Level Reasoning

It appears that there are two kinds of reasoning that people do. I will characterize them roughly as rule-based and associative. When we're doing the former, we're aware of it, and it has steps that we can describe. We know we're doing something, and if it's complicated enough, we know that we're doing work and that we might make mistakes. When we do associative reasoning, however, it's largely below the level of consciousness, and it appears effortless. It takes clever psychological experiments to reveal how much work actually goes on at this subconscious reasoning level.

It's probably not an accident, therefore, that the structure of computer programs and the characteristics of logical formalisms tend to resemble the rule-based reasoning that we're aware of, and we've been relatively successful (modulo the combinatorics) at getting computers to do this kind of reasoning. On the associative side, however, it is much harder even to understand what people do, much less figure out how to get computers to do something equivalent to it.

When it comes to dealing with large amounts of knowledge, when a person has more knowledge, the person generally thinks better and is more effective at understanding the environment and functioning in it. When computers have more knowledge, they tend to bog down in searching through the additional facts and rules that have to be considered. I believe that this difference is due to something about the way people organize knowledge for efficient use, and I'd like to be able to get computers to do the same thing.

To give you an example of the kind of thing I have in mind, consider the following example. At one time I was trying to remember the name of a flute piece that my wife used to play, and the thing that kept coming to mind was Fahrenheit 451, which I knew was wrong. Fahrenheit 451 is a book about censorship and book burning, and the title is the temperature at which paper burns. Eventually I remembered that the piece I was trying to recall was called Density 21.5. Density 21.5 is the density of platinum, and the piece was written in honor of the first platinum flute. Both of these titles use essentially the same device, and this device is so unique that the first time we see it, we are likely to form a concept something like "a creative work whose title is the statement of the value of a physical property that has a semantic relationship to the work." When the second occurrence of this device was encountered, I apparently recognized the similarity at this abstract level, and the two facts were thus related to each other. When I later tried to recall the musical piece, something about the way my mind works was causing the abstractly similar book title to be recalled out of all of the millions of things that I know. This particular abstract generalization was triggered by my much more specific recall attempt. It happened effortlessly and with no conscious awareness of the process. This kind of retrieval is the capability that lets us recognize quickly what kind of situation we are facing, what to expect in that situation, what to do about it, and what other similar situations we have encountered. These capabilities are key to our successful adaptation to the world in which we live and are part of the essence of intelligence.

My goal is to discover a kind of "mental" organization of knowledge that would enable a computer to do a similar kind of retrieval from large knowledge bases (Woods 1986a). This is key to developing scalable knowledge-based systems. Without it, systems are limited in the amount of knowledge that they can handle, and projects like the semantic web will be unable to deal with truly web-scale knowledge.

In passing, it is worth noting here that many "knowledge-based systems" are actually what I have called "ignorance-based systems" because they rely on knowing only what they need to know to solve the problem and on not knowing the many potentially distracting things that could lead them down blind alleys and increase the combinatoric search for a solution. As a simple example, when writing grammars to parse sentences, it is much easier if the parser can assume that "I" is always a personal pronoun and "be," "am," and "are" are verbs. It becomes more difficult if the parser's dictionary also knows that "I" is the chemical element symbol for iodine, the roman numeral for one, the mathematical symbol for the square root of minus one, the name of the ninth letter of the alphabet, and even an Asian last name. These six choices can be multiplied by two for each occurrence of "be," "am," and "are" if the system also knows that "Be" is the chemical element symbol for Beryllium, that "am" is an abbreviation for "morning," and that an "are" is a measure of land area equal to one hundred square meters. If a reasoning system can handle this kind of additional and potentially distracting knowledge, then it is truly robust and scalable; otherwise, it can be thrown into combinatoric distraction by the addition of more knowledge.

History

My concern with semantics and meaning began in a seminar at Harvard University in which my eventual thesis advisor, Susumu Kuno, posed the problem of designing a natural language question-answering system to query a database. After some thought, it seemed to me that if one were going to get a computer to answer questions, then one had better know something about meaning, so I turned to the library and read a lot of philosophy: Tarski, Wittgenstein, Carnap, Quine, Church, and others. None of this told me what meaning was, however. The best I could find was essentially an operational test for whether one knew the meaning:

To know the truth conditions of a sentence is to know what is asserted by it--in usual terms, its "meaning"--Rudolf Carnap

But truth conditions are a very abstract thing and, in particular, an infinite thing--a mapping of all possible worlds into the values true or false. What could a computer use (or a person for that matter) that would meet this operational test? What could be stored in a finite memory that would encode the truth conditions for an infinite set of possible worlds?

The only thing I knew that would meet this test was some encoding of a procedure--a Turing machine, a production system, a recursive function definition--essentially a computer program for computing the truth values from the possible world itself. This idea, which I introduced in my thesis (Woods 1967) and called "procedural semantics" (Woods 1968), not only turned out to be a powerful way to build a practical question-answering system, but also solved a classical problem in the philosophy of language--how the meaning of a proposition could be connected to the actual physical world. In the procedural semantics framework, the meaning of a proposition (that is, the procedure expressing its truth conditions) could be embodied (stored) in a physical machine that used the procedure to operate on the physical world to compute the truth values. For example, a question about the inventory of bolts in a warehouse could be answered by a robotic system that actually went to the appropriate bin in the warehouse and counted the bolts. This pure idea turned out to be somewhat oversimplified, but a more refined version, using a notion of abstract procedures, which I presented in two essays on procedural semantics (Woods 1981 and Woods 1986b), turns out to come closer to being a viable theory of meaning. This more refined theory distinguishes between abstract procedures (possibly not even executable) that determine the meaning of a term and other (possibly fallible) recognition procedures that are ordinarily used to infer when the term is true or false.

The term procedural semantics has since been used by a variety of people with various meanings, often associated with representations that look like computer programs. This is opposed to taking abstract procedures as the semantic foundation for representations that could look like logical expressions or like network representations. I will have more to say about procedural semantics in a subsequent section of this article. For more information on the history of the idea and the so-called procedural versus declarative controversy, see Woods (1987b) and the preface to the published version of my thesis (Woods 1979).

This idea of procedural semantics became the basis of my Ph.D. thesis, "Semantics for a Question Answering System," which I finished in 1967 and was eventually published in 1979. In that thesis, I presented a methodology for mapping a parse tree for a natural language question into a computer program for computing its answer--essentially a natural language compiler. I argued for the separation of the parsing and semantic interpretation machinery from the back-end database and reasoning machinery by means of a general notation for expressing these procedures (what is now called a meaning-representation language). Prior to this, question-answering systems had usually transformed questions into the notation in which the data was represented, and questions were answered by pattern matching, equation solving, logical deduction, or database retrieval, depending on the representation chosen. For example, Robert Simmons (1965) describes a system that parsed a question into a tree structure, replacing the question word with a variable. This system answered questions by matching this structure against the parse trees for sentences from an encyclopedia and reported the value matched against the variable as the answer. While this worked well for many examples, in response to the question "What do worms eat?" this system found "Worms eat their way through the ground." In another example, Daniel Bobrow (1964) transformed sentences from high school algebra word problems into equations in algebra and answered questions by solving algebraic equations.

Incidentally, I developed the formalism of augmented transition network (ATN) grammars (Woods 1970 and Woods 1987a) in order to have a practical way of parsing English sentences into the kinds of parse trees that I needed as input to my semantic interpreter. At the time, Chomsky's theory of transformational grammar was a...

NOTE: All illustrations and photos have been removed from this article.



More articles from AI Magazine
The Artificial Intelligence and Interactive Digital Entertainment (AII..., December 22, 2007
Report on the SAT 2007 Conference on Theory and Applications of Satisf..., December 22, 2007
We need to find an IT Celebrity.(Editor's Note), December 22, 2007
Future of science--"we will have the power of the gods".(AI in the new..., December 22, 2007

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.