Knowledge representation, the ability to depict concepts, actions, and events in a meaningful way, is at the core of many issues in artificial intelligence today. The ability of the human mind to assimilate and synthesize huge amounts of data is in many ways related to the numerous inputs received from our many senses. We do not need to consciously translate visual input of a ball bouncing into a series of ones and zeroes. We do not need to manually code the entire environment in which each event we observe takes place. (Dreyfus, 1992) Our minds have the built-in ability to receive and process many types of data. Computers, however, do not have this advantage. Thus, knowledge representation becomes a key element in creating computers that can think.
Some success has been had in limited areas. Microworlds, areas of deliberately limited domain knowledge, can be created for computers that can then be coded to take into account all of the effects of their environment. Within these finite environments, the computer can learn and make decisions. However, outside of this little world, the computer is crippled, unable to "know" anything that is has not been told. The computer's inability to assimilate a "new" event - one that is not catalogued and cross-referenced in its code - is what so severely impairs its capacity for human-like thought and judgement.
So how do we mimic perception so that a computer might interpret new data? How can we cause a computer to perceive as we do? To this end, we must create an extensible representation of the world - a language of languages that will allow a computer capable of pattern matching at speeds we will never approach, to assimilate information in an appropriate and meaningful way. We need advanced mathematics to codify and clarify the problems (Minsky & Papert, 1969) but must maintain an awareness of the unique cognitive issues that we are attempting to mimic. (Dreyfus, 1992)
From Alan Turing's conception of AI (Copeland & Proudfoot, 1999) to the advances and robotics today, artificial intelligence (AI) is a wide and diverse field. Hence, the approaches to this problem of representation are many and vary greatly, from neural nets to data mining to expert systems. Philosophies also vary ranging from purely mathematical to psychological. Even the architecture varies from symbolic to situated development. This paper considers only three of the issues underlying the problem of knowledge representation:
1. Common sense
2. Language interpretation
3. Contextual relevance
For each of these issues, we shall consider the problems inherent to it, current work in the field, how each aspect has been applied, and how they relate to one another.
Common sense is a quality we often claim human beings have, but have difficulty defining. Knowing that if you touch something hot you will be burnt is common sense. But how does one extend this concept to a computer? Mcarthy (1959) defines a program to have common sense if it "automatically deduces for itself a sufficiently wide class of immediate consequences of anything it is told and what it already knows." We can at once see two consequences of this definition - the computer must be able to draw conclusions about a situation and it must be aware of similar situations. On the surface, this may appear a simple matter. However, when attempting to code common sense, the complexity involved quickly becomes apparent.
Let us take, as an example, the knowledge that touching something hot will burn you. The computer must understand the concept of "hot" - not a well-defined term. You may like your coffee hot, but not so hot as to burn you. So how hot is too hot? And how do you express this to a computer? Explicitly defining concepts is very difficult. Yet, it is also very useful. The more common sense we can get a computer to understand, the less we have to tell it. Medical programs would benefit greatly from the addition of common sense to make diagnosis easier without the exhaustive data entry that is currently prerequisite to make these programs meaningful (Szolovits, 1982).
Much of the problem in common sense AI comes from the fact that one cannot use a monotonic assumption. That is, you cannot rely on the fact that the entire knowledge base is known - you may receive knowledge, after the fact, that show that the original conclusion was incorrect. The CYC project constructed by Douglas Lenat at MCC (Microeletronics and Computer Technology Corporation) in 1984 attempts a monotonic approach to the common sense problem. This project involves a massive effort involving manually inputting millions of pieces of information. At this time, over one million facts have been entered - however Lenat expects that 100 million must be entered before the program can start to learn for itself and it is not yet clear that it would be more than a very efficient expert system (Copeland, 2000).
This completeness, or "closed world assumption" (Poole, Mackworth, & Goebel, 1998) is considered unrealistic by many when speaking of common sense reasoning. Certainly, the man-hours involved in the project are overwhelming. Other criticisms include that the system is ultimately arbitrary - that is, that the decision regarding what common sense knowledge is input into CYC is biased. In addition, the project itself is considered by some to be dangerous, in that it unrealistically romanticizes the possibilities of AI, causing public funding to be directed away from very real and immediate human problems, such at illiteracy (Locke, 1990).
More abstract work has been done to refine inference algorithms - those algorithms that allow computers to draw conclusions from existing information. Kifer (1998) derives a new type of constraint on queries called "superfiniteness" in an attempt to allow computers to better constrain facts and draw conclusions.
Other recent work in common sense deals with the ability to generalize definitions and use nonmonotonic reasoning. Amati, Aiello, and Pirri (1997) deal with this problem by including a context for the facts in question. They argue that classic definability - that is, taking every piece of information necessary to make the decision into account in the equations - is inadequate. Many concepts cannot be defined explicitly, like "game" due to the fact that they cannot meet a set of conditions for the concept to be defined. Other concepts are too general, such as "bird", so as to be sufficiently explained. To address this problem, the authors create a language (mathematical representational language, not a computer language) that has a self-referential ability - that is a language in which expressions "can be reasoned about in that same language itself." Using this approach underlines that fact that the common sense problem is a clear subset of the knowledge representation issue. The inferences that the computer makes based on the available data is crucial - but how we get that data into the computer, in a way that it can make use of it, is even more so.
Areas of applications for common sense include helpdesk software, medical diagnostics, and more. Anywhere inferences must be made based on common knowledge, one can find applications for common sense.
The challenges of common sense include recognizing the association between two facts as important (for example, the PATHFINDER program discussed in the following section) and dealing with the sheer amount of data that must be input to allow the computer to make meaningful associations, as with CYC.
Perhaps if we could communicate with the computer more directly, we could more easily input the necessary knowledge into the computer without the overhead of literal input. This hope brings us to the issue of language interpretation.
Language interpretation is the computer's ability to understand what a person says or writes. Analysis of language, breaking down the each sentence, and at times each word, into its components and determining what those components should be can be a challenging pursuit (Turchin, 2000). One approach to this problem is that of abduction (Norvig & Wilensky, 1994). This approach uses inference rules to suggest how one might compare statements to discover their true meaning.
Norvig and Wilensky critique three types of abduction models: Cost-based, probability-based, and coherence-based. Cost-based abduction assumes each word in a sentence has an associated weight or cost. Weights are adjusted based on whether the elements of the sentence represent new information. Then, based on a set of rules, the interpretation is made that creates the least cost. Probability-based abduction uses Bayesian probabilities associated with events to interpret a given set of statements. Coherence-based abductions associate two statements, based on proximity in input, to interpret the meaning of both. For example, "The cat sat on the couch. Susan had to vacuum." might be interpreted as indicating that Susan had to clean the couch because the cat had sat on it. Each of these models has serious limitations, failing to reflect the complexity of language in their interpretations. While cost-based and probability models lack a coherence, the coherence model lacks the ability to judge which statements should be associated. The authors conclude by suggesting that combining these approaches will yield more robust results.
Another recent study works to define the "utterance unit" (Traum & Heeman, 1996). By breaking down human speech into its smallest components, scientists hope to make processing language easier. Most work done in this area does not suggest a word by word analysis (although that has been proposed), but rather a breakdown at natural pauses in speech. Issues in making this distinction include "speech repairs" - instances in which a speaker repeats what they just said - or a "fresh start" - instances in which the speaker simply starts over. Traum and Heeman evaluate proposed measures of utterance units by looking at "grounding," defined in their paper as "the process of adding to common ground between conversants." They observe how this grounding behavior is a natural basis for utterance units.
Another concern in language interpretation involves limiting cumulative errors (Qu, et al, 1996). Since much dialog interpretation is based on context-based evaluations, one error quickly builds on another. Qu, et al, show that by basing inferences on grammatical rules, rather than contextual rules, the progressive error problem can be avoided. However, limiting contextual interpretation may itself cause a problem, since language clearly does not exist as a series of unrelated words.
Current projects in language interpretation include JANUS and TRAINS-95. JANUS is a system that provides real-time speech translation. Certainly speech translation is an excellent application of language interpretation advances, allowing people who do not share a common language to communicate. Many online services, such as Babelfish, provide this service for textual translations. But, just as the online translators are limited to a literal, word-by-word translation, JANUS is limited to a specific domain of speech (Gates, et al., 1996). TRAINS-95 was developed as "an intelligent planning assistant that is conversationally proficient in natural language." (Sikorski & Allen, 1996) This system also works in a limited domain (train route planning). These applications show promise, but their limitations prevent a wider use.
The Learning to Reason algorithms emphasize the need to integrate environmental dependence and, hence, contextual relevance (Khardon & Roth, 1997). More basic research deals with the propositional logic used by the languages, attempting to determine the relevance of one sentence to another (Lakemeyer, 1997).
Other representational research stresses the framework in which information is processed. Integrating visual input with textual descriptions allows creation of a more complete picture - and provides a scheme to mimic mental imagery (Glasgow, 1998).
Nouvelle AI (as contrasted to the previously discussed symbolic AI) may provide some of the most useful approaches to the contextual relevance problem. Nouvelle AI attempts to simulate not human level intelligence, but that of insects. This work rests on the assumption that complex behaviors are results of interactions between simple behaviors - a philosophy that finds its roots in psychological behavior analysis.
Developments in this area include robots, such as Allen and Herbert at the MIT AI Laboratory, that use dozens of sensors to receive input about the world around them (Copeland, 2000). They contain no internal model of behavior, but rather react to input as it is given to them. This "situated" approach to AI was described, early on by Dreyfus (1992), one of the strongest critics of symbolic AI.
And, in turn, understanding how to create better representations, may assist educators at all levels reach a larger audience, perhaps excluded previously by insufficient domain knowledge.
It seems clear that intelligent computer assistants, even hampered by limited domain knowledge, are useful. Unclouded by political motivations, emotions, or misleading experiences, these helpers may improve our ability to diagnose disease, recognize patterns in data, or even identify learning disorders. And, perhaps most importantly, in our quest to create these intelligent computers, we open the door to learning infinitely more about ourselves.
Amati, G., Aiello, L. & Pirri, F. (1997) Definability and commonsense reasoning. Artificial Intelligence 93. 169-199.
Borhcardt, G. (1994) Thinking Between the Lines. MIT Press: Massachusetts.
Conceptual Knowledge Markup Language, White Paper, [Online]. Available: http://wave.eecs.wsu.edu/WAVE/Ontologies/CKML/WhitePapers/CKML/CKML.html [2000, December 1].
Copeland, J. (2000) What is Artificial Intelligence? [Online]. Available: http://www.alanturing.net/pages/Referenc%20Articles/What%20%20AI.html [2000, December 1].
Copeland, J. & Proudfoot, D. (April 1999) Alan Turing's Forgotten Ideas in Computer Science. Scientific American, 99-103.
Doyle, J. & Dean, T. (1996) Strategic Directions in Artificial Intelligence ACM Computing Surveys 28(4). [Online]. Available: http://www.medg.lcs.mit.edu/ftp/doyle/sdai96.html [2000, December 1].
Dreyfus, H. (1992) What Computers Still Can't Do. MIT Press: Massachusetts.
Gates, D., Lavie, A., Levin, L., Waibel, A., Gavalda, M., Mayfeld, L., Woszczyna, M., & Zhan, P. (1996) End-to-End Evaluation in JANUS: A Speech-to-speech Translation System. Lecture Notes in Artificial Intelligence: Dialogue Processing in Spoken Language Systems. 195-208.
Giunchiglia, E., Kartha, G., Lifschitz, V. (1997) Representing action: indeterminacy and ramifications. Artificial Intelligence 95. 409-438.
Glasgow, J. (1998) A Computational Framework for Unifying Vision and Language. International Journal of Psychology 33(6). 421-437.
Khardon, R. & Roth, D. (1997) Learning to Reason Journal of the ACM 44(5). 697-725.
Kifer, M. (1998) On the Decidability and Axiomatization of Query Finiteness in Deductive Databases. Journal of the ACM 45(4). 588-633.
Kintsch, W. (1998) The Representation of Knowledge in Minds and Machines. International Journal of Psychology 33(6). 411-420.
Lakemeyer, G. (1997) Relevance from an epistemic perspective. Artificial Intelligence 97. 137-167.
Locke, C. (1990) Common Knowledge or Superior Ignorance? [Online]. Available: http://www.panix.com/~clocke/ieee.html [2000, December 1].
McCarthy, J. (1959) Programs with Common Sense. [Online]. Available: http://www.formal.stanford.edu/jmc/ [2000, December 1].
Minsky, M and Papert, S. (1969) Perceptrons. MIT Press: Massachusetts.
Norvig, P. & Wilensky, R. (1994) A Critical Evaluation of Commensurable Abduction Models for Semantic Interpretation. [Online]. Available: http://www.norvig.com/coling.ps [2000, December 1].
Poole, D., Mackworth, A., & Goebel, R. (1998) Computational Intelligence. Oxford University Press: New York.
Qu, Y., Eugenio, B., Lavie, A., Levin, L., & Rose, C. (1996) Minimizing Cumulative Error in Discourse Context. Lecture Notes in Artificial Intelligence: Dialogue Processing in Spoken Language Systems. 171-184.
Szolovits, P. (1982) Artificial Intelligence in Medicne. Chapter1 [Online]. Available: http://www.medg.lcs.mit.edu/ftp/psz/AIM82/ch1.html [2000, December 1].
Traum, D. & Heeman, P. (1996) Utterance Units in Spoken Dialogue. Lecture Notes in Artificial Intelligence: Dialogue Processing in Spoken Language Systems. 125-140.
Turchin, V. (no date) The Phenomenon of Science. Chapter 6: Logical Analysis of Language [Online]. Available: http://www.pespmc1.vub.ac.be/POS/Turchap6.html [2000, December 1].
Sikorski, T and Allen, J. (1996) A Task-Based Evaluation of the TRAINS-95 Dialogue System. Lecture Notes in Artificial Intelligence: Dialogue Processing in Spoken Language Systems. 207-220.
Vamos, T. (1995) A Strategy of Knowledge Representation for Uncertain Problems: Modeling Domain Expert Knowledge with Patterns. IEEE Transactions on Systems, Man, and Cybernetics 25(10). 1365-1370.