After a pause that was much longer than I had planned, I’m once again able to spend some time working on new articles for the Knowledge Nuggets blog. In this one, I will try to wrap up some themes that I introduced in earlier articles; then we will move on to new topics.

As for the photo, it doesn’t really have anything to do with the topic. People seem to like a bit of eye-candy in the blog, just for variety. I took this photo a few years ago in Marwood Hill Gardens, near Barnstaple in England – a highly recommended garden, by the way.

What this article is about

Despite the title, this article is not about super-intelligent, autonomous AI systems that might attempt to take over the world and that, if they succeed, might or might not decide to keep us humans around as pets. There has been a certain amount of discussion about this in recent months, triggered in part by an AAAI panel set up to look at such issues – and in part by a lot of sensationalized press accounts. Nothing sells papers like the threat of killer robots run amok.

I agree that those of us working on AI have a responsibility to consider the long-term human consequences of our work. Fortunately, we’ve got some time to think about this. AI systems are still a very long way from achieving even a child-like level of common sense and general planning ability. This article discusses one reason why progress has been so slow.

Slow progress toward the original goal of AI

If measured by the number of useful applications, tools, and vibrant spin-off fields it has produced, Artificial Intelligence has been a spectacular success. However, a lot of people (including me) believe that AI has been a disappointment in terms of achieving its original goal: to understand and, ultimately, to replicate the computational mechanisms responsible for human-like intelligence, in all its generality, flexibility, and resilience. In an earlier article I listed some of the major elements of intelligence that we still don’t understand after 50+ years of work on AI. In another article I echoed Ron Brachman’s call for continuing work on an integrated architecture for AI.

Back in the early days of the field, we seemed to be making good progress toward this goal. There were a number of key discoveries along the way: first, that computers could manipulate symbols as well as numbers; second, that search through a space of possibilities, with occasional backtracking, was a powerful and resilient way to solve many problems; third, that human-like performance is going to require a lot of knowledge, not just search-power; fourth, that it’s too tedious to assemble and organize by hand enough knowledge for broad, general intelligence, so we had better find ways to increase our store of knowledge by learning. But somehow, since the mid-1980’s, progress toward this central goal of AI seems to have run out of steam.

Why is that? Well, one explanation is that the funding climate changed. In the old days, there was steady, long-term support for research on the central problems of AI – not an enormous amount of funding, but enough to enable a small community of AI researchers to focus on the most challenging fundamental problems. This effort attracted some of the most brilliant minds in the field of computing. But times changed. Sponsors lost patience with basic, long-term AI research; they began demanding a focus on specific applications, with constant benchmarks, competitions, “go/no-go” decisions, and short-term deliverables. The patient, curiosity-driven funding that characterized the early days of AI is now very rare.

But that is only a part of the story. I think that we face a more fundamental problem: in an odd way, AI has been a victim of its own success. More specifically, the field’s success in producing useful but narrow technologies in particular areas – what I call “super-human AI” – has almost completely crowded out work on our original goal of creating flexible, integrated, human-like AI. We have seen one gold rush after another to exploit new, highly specialized technologies with their roots in AI. In the short run, this may be good for the field, since it pulls in both people and money; in the long run, I think it’s a serious problem.

“Super-Human” AI

What do I mean by “super-human AI”? I wrote briefly about this in an earlier article. The idea is that intelligence is really a bundle of many capabilities. It is possible (and is now very common) to have super-human performance in one of these areas, or a few of them, without having anything that resembles the breath, resilience, and resourcefulness of “merely human” intelligence.[1]

There are many examples of narrow super-human AI, but the story is similar for each. First, researchers grappling with some important problem within AI try a variety of approaches, inspired to some degree by the questions “How do humans perform this task?” or “What is really required to achieve human-like performance?” And then someone comes up with an elegant mathematical approach that, under certain conditions and with sufficient computing power, can produce results much better than an unaided human. In many cases, this leads to a commercially valuable technology. In some cases, it gives rise to an active field of investigation that takes on a life of its own, attracting many researchers, lots of funding, and spawning its own specialized conferences and journals.

There are many examples of these super-human AI technologies: computer algebra systems that can solve integrals that no unassisted human can handle; search-intensive chess programs that can consistently beat (almost) every human player; search engines that can browse and index the entire Internet, but without any understanding of the content; statistical machine translation systems that can produce useful (if imperfect) translations without ever considering the meaning of the text; statistical data-mining programs that can extract subtle regularities from a mountain of noisy data; poker-playing programs that employ powerful techniques from game theory; optimal or provably near-optimal planning systems; theorem-proving inference systems, with their guarantees of soundness, logical completeness, and provable consistency; and statistical inference systems that (if their models and input probabilities are correct) can very precisely infer the probabilities of various outcomes in a way that no unaided human can match.

This is great, but in every case (so far, at least) these developments contribute little or nothing toward achieving our original goal. The super-human techniques apply only to a very narrow set of problems, or the assumptions underlying the mathematical model are unrealistic in practice, or the method is too computationally demanding to be used on large problems – often problems that we humans can solve easily using our more informal approaches. Or all of the above. All of these systems are impressive, and many are commercially valuable, but none of them would be called intelligent, in the normal sense of that word. None of these systems can begin to match the common sense or flexible problem-solving ability of a young child.

An Example

To understand what’s going on here, let’s look at one of these areas – the evolution of AI planning and problem-solving systems – in a bit more detail. A lot of the early work in this area took an intuitive approach, informed to some degree by introspection about how we humans approach complex planning tasks.

The first problem was to represent the universe in which the planning is to take place, the allowable set of operations, and the preconditions and effects of each operation. (We still have not completely solved these representation problems, but that’s a topic for another article.) Given an adequate representation, the next problem is how to find a legal path from the current state to the goal. Sometimes a legal path is easily found; sometimes it requires a great deal of search and non-obvious application of the available operators.

Ideally, we would like both a reasonably efficient plan and a reasonably efficient planning process. One powerful idea is hierarchical planning: first, use high-level, abstract operators to sketch the outlines of a plan; then use more specific operators to fill in the details. Another powerful idea is to save a sequence of operations that is useful in one context, generalize it a bit, and to turn the sequence into a “macro-operator” that can be used in other problems.

These ideas were explored extensively in the early days of AI by systems such as GPS[2], STRIPS[3], ABSTRIPS[4], SOAR[5], and many others. My own BUILD program[6] (my MIT master’s thesis from 1973) was typical of early work in this area. BUILD tried to figure out a plan by which a (simulated) one-handed robot could build a specified structure on a table, given a collection of blocks. BUILD could be quite resourceful: it would first try a straightforward approach, placing the blocks one by one, starting from the bottom of the desired structure and working upward. But if the desired structure was unstable during the construction, it would consider more complex plans. It would try to use other blocks as scaffolding or temporary counterweights, and if that didn’t work it would try to build a sub-structure on the table and then lift the whole sub-assembly into place. BUILD would do some extra work to produce good plans – for example, it would eliminate redundant steps in the plan – but its plans were by no means optimal, and were never intended to be. It just returned the first reasonably good plan that worked. In that respect, it seemed very human-like in its planning.

Not long after BUILD was published, the AI planning field changed radically. Methods were developed that, for a certain limited class of problems, would guarantee optimal results, or results that were provably close to optimal. Other things being equal, that’s good: who wouldn’t prefer an optimal solution over one that is merely “good enough”? But, of course, other things were not equal. The optimal planning programs were very computationally demanding because the programs had to consider every possible solution – or formally exclude some parts of the search space where no optimal solution could possibly be hiding. For may problems of interest, these techniques were computationally intractable, or at least impossibly inefficient. So these techniques were limited to small problems in very clean, easy-to-model domains. In the real world, it makes little sense spend a lot of supercomputer time seeking an optimal solution to real-world problems when a single pothole – not represented in the model – could force the whole planning process to be re-run. (If you really care about optimality, a local patch to the plan isn’t good enough.) And, as all Pittsburghers know, potholes are everywhere.

Given these limitations, some of us felt that the obvious move would be to continue work on flexible, resourceful, trainable, “good enough” planning systems. After all, we humans don’t worry about optimal planning in our daily lives. “Good enough” planning is good enough for us, and we can show great cleverness and resiliency when things go wrong at execution time – as they so often do – forcing us to re-plan on the fly. We can even pass partially instantiated plans from one person to another via informal high-level recipes: “To get from CMU to the airport by car, take Fifth Avenue to the Parkway East (heading west), cross the Fort Pitt Bridge, and just follow the ‘Airport’ signs from there.”

But the idea of optimal or near-optimal solutions, built on a sound and elegant mathematical foundation of theorems and lemmas, was too alluring to pass up. Since the mid-1980’s, the planning field has been dominated by this approach. Most of the papers at planning conferences focus on how to deal with the resulting intractability, so that at least some problems of practical interest can be addressed. If an optimal solution is infeasible, you at least need to prove something about how close your technique can come to the optimum – impossible in most messy-real-world planning domains. So it is now difficult to publish planning results that do not address optimality concerns, and several generations of students have learned to take this approach for granted. Not only has a super-human sub-field of AI been spawned, but work on more human-like approaches to planning has mostly shriveled and died, unable to thrive in the shade of this mighty oak.

The Problem

And that, I think, is the problem. AI is one field with two very different sets of goals. It would be healthy for the field if these two approaches could co-exist: one set of researchers working on various super-human areas of AI and another set working on the original core problem of broad, human-like intelligence. These efforts could reinforce one another, and some people would move back and forth between them in the course of a career. Unfortunately, it seldom works out that way, for two reasons:

First, when one of these super-human technologies takes off, it creates a sort of gold rush that attracts a lot of talent and resources away from the core problems of AI. In recent years, it seems that 80-90% of the people at the big AI conferences are working on super-human AI problems, not on human-like AI. So it is little wonder that progress on the core problems has slowed down.

Second, researchers in some of these super-human areas develop a certain contempt for the less elegant human-like approaches in the same or neighboring areas: their own work is based on elegant mathematics and clean abstractions – the approach is scientific and principled – while those working on less formal approaches to human-like AI are just messing around. “That’s the sort of thing we did in the old days, before we understood how to properly frame the problem. Anyone still messing with those ad hoc approaches must be doing so out of ignorance, unaware of all the amazing progress that has taken place in AI.”

Well, OK, there has been amazing progress, and we should build on that whenever we can. But in most cases, we’re not talking about the same area of research. There is a place for optimal planning, but we also need to understand human-like good-enough planning, which is faster and much more flexible. There is an important place for theorem-proving, but (as I have argued elsewhere), we need something more quick-and-dirty if we want our systems to read the daily newspaper. And so on.

Unless and until these super-human approaches can be extended to cover the kinds of large, messy, hard-to-formalize tasks that we humans handle with such aplomb, we have to keep working on these things, by whatever scruffy means are necessary. Maybe some of these problems can be handled by techniques that will ultimately be formalized and wrapped in elegant theory, or maybe they are inherently messy, but any reasonable person must admit that AI still contains many challenging problems that don’t fit into the elegant theoretical frameworks we have today.

One might argue that these super-human techniques are more valuable than understanding and emulating human-like intelligence. After all, we already have plenty of humans, so why not just focus on the areas where machines can extend human capabilities? I think there is some merit in that argument, but it would be a shame to let the scramble for super-human capabilities crowd out the quest for human-like AI.

The quest to understand and replicate human-like intelligence remains as one of the great intellectual challenges of mankind – one of the last great mysteries. Yes, this problem has proven to be more difficult than we thought it would be, and the solution is unlikely to rest on a foundation of clean, beautiful mathematics, but that should not discourage us. If, along the way to understanding intelligence, we can create some valuable technologies that provide super-human performance in specific narrow domains, that’s a bonus. AI as a field may pause occasionally to take advantage of these new technologies, but we should not let them divert us from the ultimate goal. Better yet, we can combine these technologies to get the best of both worlds: flexible, resourceful human-like systems with a “telepathic” link to an array of super-human tools, for the times when those tools are applicable.

And then we can go back to worrying about the death robots. ;-)

It is not my goal here to present a tutorial on first-order logic (FOL), resolution theorem proving, or the decidability and tractability of inference in FOL and in all the various subsets and supersets of FOL that have been proposed over the years. There is not enough space for this in a short article, and I certainly am not the best person to explain these issues. There are many good tutorials on these topics, both online and in the published literature, and most of those tutorials offer pointers to original sources for those who want to dig deeper. One good entry point, which ties these topics explicitly to the concerns of practical knowledge representation, is the book Knowledge Representation and Reasoning, by Ron Brachman and Hector Levesque, mentioned in an earlier article in this blog. So in this article I will assume some prior knowledge of FOL and related matters; readers totally lacking such a background will probably find this article to be impenetrable and uninteresting.

First-Order Logic for KR

When faced with the problem of representing symbolic knowledge in a computer, most researchers immediately turn to First-Order Logic (FOL). It seems the obvious choice. This approach rests on a solid mathematical foundation, built up by great minds since the time of Aristotle. There is a very solid theory telling us what FOL can represent and what kinds of inference are possible in this logic. John McCarthy, with the publication of his 1959 paper Programs with Common Sense, and in much of his subsequent work, gave the just-created field of AI a mighty push in this direction, and away from the rather messy and obscure embedding of knowledge in programs that most of the early pioneers of the AI field had engaged in.[1]

For the inference procedure, it seems natural to choose something like resolution theorem-proving[2], with its guarantees of sound inference and logical completeness. The basic idea is simple: if you want to determine whether proposition X is true (provable) relative to a given knowledge base (KB), assert not-X and see if the KB is inconsistent given that addition. If so, X must be true. Note, however, that this inserts a potentially very expensive step into the procedure for even simple queries: “determine whether the entire KB is now consistent”. In many cases where X is true, a well-designed inference algorithm will terminate quickly, having found some inconsistency that derives from not-X. However, proving that no inconsistency exists, even by the most circuitous path through the assertions and predicates of the KB, can take a long time. In more expressive logical systems, the search may not terminate at all.

There is the added problem that if some inconsistency was already present in the KB before not-X was added, the system will agree that any statement X must be true, even if it is something absurd like “one equals two”. So when using resolution, or any other logically complete inference method, knowledge-base hygiene is all-important: inconsistency must be kept out at all costs. This can be a problem when combining large bodies of information from multiple sources with varying degrees of reliability. But if we have a sufficiently fast procedure for testing the KB for global consistency (as we must have when using resolution), the problem of KB hygiene can be solved, though perhaps at great computational cost.

Speed and Scalability vs. Expressiveness

Here’s the big problem: it has been proven that logically complete inference in a full first-order logic system is computationally intractable. By intractable, we mean that the time required for the worst cases grows exponentially with the size of the KB. Over the years, some very clever inference engines have been developed that speed up typical-case queries by caching partial results or by ruling out parts of the KB that are (provably) not relevant to a given query, but the fundamental problem of intractability remains. The practical consequence is that a system based on full FOL and logically complete inference cannot grow to the very large size that we need for most interesting real-world KB applications.

When faced with this problem, most recent researchers in the KR field have turned to more restricted, less expressive logical systems than full FOL. There are many possible tradeoffs between tractability/scalability and expressiveness, and KR conferences are full of papers analyzing and advocating various points in the space of possible tradeoffs. A rather complicated alphabet soup of abbreviations has grown up in the theoretical KR community for describing the various expressive mechanisms that are included or not included in a given KR system[3].

The OWL notation, which currently seems to be the most popular KR system in actual use (especially for “semantic web” applications, since it has been blessed by the Worldwide Web Consortium), is actually a family of languages. OWL-Lite is a very restricted form of OWL that is tractable and for which reasonably fast inference engines exist. Some popular inference engines are Racer, FaCT, and KAON2.

However, in OWL-Lite it is impossible to express much of the knowledge that we need to express for real applications. OWL-DL, based on Description Logics, is somewhat more expressive: OWL-DL is itself a family with multiple versions, corresponding to the various ways in which description logics can be restricted. Some versions of OWL-DL are theoretically tractable and some are not; of the theoretically tractable versions of OWL, some fit into existing “fast” inference engines, and some do not. OWL-Full is more expressive still, but does not generally work with the inference engines that have been developed for description logics.

This research on the agonizing tradeoffs between scalability and expressiveness is valuable, but for our purposes in the Scone project – and for any other KB system with similar practical goals – these tradeoffs are beside the point. For human-like reasoning on real-world problems with a large KB, we need both scalability to very large size and expressiveness that is greater – not less – than is provided by first-order logic.

Regarding scalability, the core inferences that occur frequently in the KBS must be not only tractable, but fast. Even if a logical system can produce results in polynomial time, that is not good enough if the polynomial involves high-degree terms or large coefficients. If the KB is to scale to the size required for human-like common sense – or beyond – we need more-or-less constant-time responses for most kinds of queries, and linear-time response (or near-linear time) for most of the rest.

Of course, there is no magic approach for solving provably intractable inference problems. Some difficult reasoning problems will always require exponential or high-degree polynomial time, no matter what we do. But I would argue that these are not the inference problems that we need to solve frequently in the course of everyday human-like reasoning. So instead of holding the KBS design hostage to the worst-case performance of these most-difficult problems, we could instead optimize the KBS for the easier problems – the ones that we humans routinely solve with no apparent display of mental effort – and banish the more difficult problems to a specialized theorem-proving or puzzle-solving module, where they won’t bog down our reasoning when we want to determine, for example, whether Clyde the elephant has a heart.

Regarding expressiveness: as mentioned in the previous article, and as we will explore in more detail in future articles, a real-world human-like KBS needs higher-order constructs (i.e. the ability to refer to assertions as objects in the KB and to reason about the assertions themselves), multiple overlapping contexts (which really are just a convenient re-packaging of the higher-order constructs), and default reasoning with exceptions (non-monotonic constructs). If we add any of these features to our knowledge representation system, it takes us beyond the intractability of FOL and into the space of undecidability – that is, if we try to apply a logically complete inference method like resolution, it may not return an answer at all for some queries, no matter how long we wait.

Three Major Goals: Pick Any Two

So that’s the problem. We want three things from a practical KR system: (1) logical completeness and provable consistency; (2) speed and scalability; and (3) enough expressive power to cover all of our needs for representing common-sense knowledge. There is a well-established body of theory that says we can’t have all three properties at once. So researchers must choose which of these goals to give up (or at least to compromise on).

For many researchers, giving up the logical properties of completeness and provable consistency seems to be inconceivable – they don’t even discuss this as a choice – so they end up arguing endlessly about how much expressiveness to trade off for somewhat better speed and scalability. Often, they end up with the worst of both worlds: an awkward, inexpressive system that is still too slow to be used in many applications.

Some of the logicians in the KR field have effectively given up on scalability: they remain rooted in the logical tradition and continue to explore ever more complex and expressive logics, even if the resulting representations are intractable or undecidable.

And a few of us, unwilling to compromise either on expressiveness or scalability, have made the choice to give up on logically complete proof procedures and to reason in a more local and limited way. Our systems are not general theorem-provers, but they seem to support human-like common-sense reasoning quite well. In any case, given our goals, this is the only reasonable choice.[4]

Incomplete Inference

So what are the implications of this choice? On the plus side, giving up on logically complete inference is very liberating: the greater expressiveness available in an incomplete-inference system like Scone allows us to easily express and reason about general-knowledge statements and concepts that would be extremely difficult, if not impossible, in a system based on FOL or a tractable subset of FOL. In Scone it is easy to represent and reason about pink elephants and flightless birds, and to represent complex multi-context statements like “Tom believes that Fred knows Mary’s phone number, but Fred doesn’t really know it.” This expressive power makes it much easier to build up large bodies of knowledge in real-world domains, since we are not constantly fighting against the fundamental limitations of our descriptive machinery. Since our KBS is more expressive, we can import knowledge from representations such as OWL into Scone, though we cannot, in general, export Scone knowledge back into less expressive systems – some of it just can’t be represented there. Freed from the expressiveness/tractability dilemma, we can focus on making our system’s limited inference as fast and scalable as possible.

On the other hand, there will be some valid inferences that could be made from the knowledge in our KB that a system like Scone will never make – that’s the definition of incomplete inference. Scone’s reasoning is mostly local – it will not follow chains of inference to arbitrary depth. When faced with some loop (”Who shaves the barber?”), Scone ideally would flag this as a problematic case, but we cannot guarantee that all such cases will be detected. Sometimes Scone will just return one answer or the other. For human-like reasoning, that strikes me as good enough. I do the same thing. We all do, when we’re not in theorem-proving mode.

Scone can still catch most inconsistencies as they are entered into the KB. For example, if you say that Clyde is male and later that he is someone’s mother, implying that Clyde is female, that will be caught. However, more subtle inconsistencies may sneak into the KB unnoticed. If somehow we end up in a situation where Clyde is both male and female, then we will experience some local confusion regarding Clyde. (What restroom should Clyde use? What sort of sex organs does Clyde have?) But our local, limited inference machinery will then not go on to conclude that one equals two. So the lack of logical completeness is not always a bad thing.

The deductions made by the limited inference engine in our KBS are normally sound, as far as they go, but there are situations where an unsound conclusion can be reached. In a non-monotonic but incomplete reasoning system, this is unavoidable. For example, suppose that elephants are, by default, gray, but that Clyde is pink. Since our KBS supports exceptions, it is legal to cancel the inherited “Clyde is gray” property and to add the contradictory assertion “Clyde is pink”. Suppose, however, that the information about Clyde’s non-standard color is not stated directly, but is derived as the result of a long and circuitous chain of reasoning. In this case, when asked the color of Clyde, our KBS might quickly infer that Clyde is gray and, if we stop the reasoning too soon, might never discover any reason to retract this conclusion. The KBS would return gray as the color, and that is incorrect.

It is troubling to have unsound inferences in our system under any circumstances. However, default inference with exceptions is so valuable that, in my opinion, we cannot live without it in real-world domains. If you know a lot about elephants, it is unlikely that any individual elephant will fit the typical-elephant description without a few exceptions. And if you banish from the elephant description any property that is not universally true, you will be left with a very sparse and not very useful description. So I think that this particular kind of unsoundness is the lesser of evils – the only reasonable choice for a system that must solve real problems in messy, non-mathematical domains.

Again, I believe that this choice is quite consistent with human-like common-sense reasoning. In my daily life, I will often draw an invalid conclusion because I haven’t thought deeply enough about the problem – I have just applied the usual default instead of noticing that the case I’m dealing with is exceptional. We humans all do this in our day-to-day reasoning, whenever we’re not in ultra-careful theorem-proving mode.

Perhaps the greatest disadvantage of an incomplete-inference approach is that it is hard for us to make sweeping, closed-form statements describing exactly what inferences these systems can and cannot make. In most of these systems, the depth of reasoning depends in complicated ways on exactly what is in the KB and on parameters that govern how much time and effort should be spent on a query before the system gives up. So the incomplete-inference systems lack the satisfying mathematical elegance of the theorem-proving systems; in exchange, the offer speed, scalability and expressiveness. I think that each of us must choose which of these properties we value most, depending on our goals.

In Conclusion…

None of this is meant to suggest that researchers who cling tightly to the logically complete, theorem-proving approach are wrong to do so. Theorem proving – and, more recently, automated theorem proving – are among the crown jewels of human intellectual achievement. Theorem-proving enables us to reason far more deeply than we otherwise could, with a strong guarantee that, if our premises are correct, our conclusions are correct as well. Even for practical inference systems, this approach has some value. There are small but important reasoning problems for which intractability is not a fatal problem. And there are many uses for logic-based representation with limited expressive power. For example, a system like OWL-Lite may be sufficiently expressive for the Semantic Web as it is currently conceived by many: a simple hierarchical scheme to provide somewhat more meaningful labels for URLs and web pages.

So I have no problem with researchers who want to focus on exploring the limits and tradeoffs of logically complete inference systems. It’s important work, and perhaps they deserve the dominant position they currently occupy in the KR universe. But I do wish that they would regard those of us who have chosen to work on incomplete inference systems as equally serious researchers who have chosen a different approach for good reason, and not as ignorant or lazy bumblers who are too slow or too stubborn to perceive the One True Way.

It is rather annoying when the logic people start congratulating themselves for having taken a “principled” approach to representing one kind of knowledge or another, with the sneering implication that other approaches are “unprincipled” – just a collection of ad hoc design choices made more or less at random by people who don’t know any better. Principles are important. But if strict adherence to a particular set of principles leads you into a part of the design space that is provably worthless for many important real-world problems, maybe it’s time to look for some new principles.

This is the second mini-nuggets article: a collection of propositions, with some minimal explanation for each, on a given topic. The idea is to sketch out an overall approach or point of view quickly, without getting bogged down in a lot of detail or lengthy justification about each point. I will come back and expand on many of these points in later articles.

In the previous article, I gave some specific narrative examples illustrating the amazing capabilities of the human memory system, and I argued that these capabilities are at the core of human intelligence. Until we understand how this memory system works, precisely enough to build some approximation of it, our AI systems will never approach the breadth, flexibility, and common sense that we humans take for granted in our own thinking. (It all seems so easy for us that it took some time just to realize that there’s an interesting problem here.) This, in my opinion, is the single most important missing piece in our current understanding of intelligence, whether natural or artificial.

In this article I will try to enumerate some of the specific capabilities that a memory system or knowledge-base system (KBS)[1] must have in order to support human-like performance. I don’t expect this brief statement of positions to persuade anyone who is inclined toward another view. My goal here is just to provide a rough sketch of the overall approach that (as of this moment) looks best to me and my research group – an approach that we are working busily to implement in the Scone knowledge-base system.

One point before we dive in: I will be talking here about symbolic memory – the component that handles propositions like “the capital of Ohio is Columbus” or “the typical elephant hates snakes” or procedural knowledge like “the first step in making chocolate chip cookies is to let some butter soften to room temperature.”

The symbolic knowledge base is not the whole story of human-like memory. I believe that we have other – probably separate – memory mechanisms to deal with images and visual patterns (2D, 3D, and 4D), sounds and music, smells and tastes, low-level motion planning, and probably several other things. I will have more to say about these other memory components in a future article. Nor is this symbolic KBS meant to be an intelligent system in its own right: as we will see, the KBS is more than a passive repository of facts, but it is only the base upon which we can build higher-level planning and cognition, and intelligent applications of all kinds.

Some AI researchers, psychologists, and philosophers would argue that it makes no sense to study the human memory system (or an artificial KBS) in isolation, as a separate component distinct from the processes that use the knowledge. They argue that that intelligence and “consciousness” must be considered holistically if we are to make any sense of what is going on. I disagree: I believe that “divide and conquer” is a good approach whenever it can be applied without too much damage to the subject, and I believe that the division suggested here between the KBS and everything else is a natural one. My students and I have already seen ways in which understanding the KBS – what it contains and what it does – can help us to think more clearly about how the overall system works.

So with those caveats in mind, here we go:

· The knowledge base can be thought of as a semantic network, with nodes representing entities (physical objects like “elephant”, but also more abstract entities like “September” or “juggling”) and links representing the relational connections among these entities. We refer to nodes and links, collectively, as elements in the KBS. As we will see, the semantic network we contemplate here is much more precise in its representation and reasoning than the early, sloppy semantic networks in which it was often impossible to determine whether a node labeled “elephant” represented the typical elephant, some specific elephant, the set of all elephants, or the word “elephant”.[2] We need to represent all of these things, but in distinct ways.

· Elements in the KBS represent concepts, not words or word-definitions. So in Scone (and, we would argue, in the memory system of humans) the “elephant” node represents the concept of elephant, and is the anchor point for our description of the typical elephant: its parts, properties, relations, and behaviors. This conceptual representation is independent of the particular human-language descriptions or other ways in which this knowledge was originally expressed.

· A conceptual element may be associated with any number of names (words or phrases in some human language), and a name may be associated with many different meanings (concept nodes), so the mapping is many-to-many within a single human language. Some concepts may have no names. The set of concept nodes doesn’t change as we switch from one human language to another, but each new language will provide a new set of names and associations. If a word or phrase maps to more than one concept, we call it ambiguous or polysemous. This ambiguity must be resolved, at least tentatively, before we are ready to store the conceptual meaning of an utterance in the KBS. The conceptual representation does not preserve the original ambiguity, but represents one specific meaning. If a sentence is truly ambiguous we might store several possible meanings in the KBS, labeling them as distinct alternative choices. In any case, we will probably store the original natural-language form as well, at least for a short time, just in case we need to refer back to it to see if there could be an alternative meaning.

Many linguists and some AI researchers blur this distinction between linguistic expressions and conceptual representations. Some even claim that no separate conceptual representation exists, and that no representation can exist that is independent of language. This radical view leads to all sorts of problems and paradoxes.[3]

The Commonsense Computing project at MIT (affiliated with the Open Mind Project) has advocated building and using a knowledge base that is a collection of undigested English sentences.[4] Such a collection has its uses, but I believe that a language-independent, concept-level representation is essential for human-like thought. It is too hard to reason effectively with raw English expressions, full of ambiguities and unresolved references. In any case, we need a mechanism that can reason about the many concepts that, in a given human language, do not have conventional names. For example, we can easily represent and reason about the concept of “juggling while standing on one foot, blindfolded, during a hurricane” – for example, we can conclude that this activity is much more difficult than conventional juggling – but I would be very surprised to find a human language or subculture that has a name for this activity.

· The KBS must support at least simple kinds of search and inference; it cannot be a passive repository of entities and assertions. As described in the previous article, human memory appears to contain much more information than it explicitly contains; the extra information must be supplied by access-time inference, even though we have no subjective experience of doing significant mental work as these inferences take place. If we are told that Clyde is an elephant, we immediately appear to know that Clyde is gray, four-legged, has a liver, and so on. Our KBS must provide a similar capability for simple inference. It must also be able to support moderately complex searches, such as finding all the matching elements in the KB, given a list of features, even if the chosen elements have those features only by inheritance and not directly. We could do this search and inference in a separate module, distinct from the KBS, but it is much more efficient to build these operations into the KBS itself – then we can organize the representations in the knowledge base to speed up these operations.

· For human-like performance, the KBS must be capable of scaling up to a large size. As we saw above, the amount of information implicit in the knowledge base, and easily accessible to the KBS, is much larger than the amount of information explicitly present. But, even so, a large amount of explicit knowledge is still required. My best guess as to the size of the symbolic memory in a typical human is something like 10 million to 100 million elements (i.e. node and link equivalents, however the brain actually stores these). We will revisit this question in a future article. For now, the point is that the storage and inference machinery in our KBS had better be able to scale up to sizes like this.

· The KBS does not have to directly support more complex forms of reasoning, such as general theorem proving, optimal planning, Bayesian combination of probabilities, or puzzle solving. I would argue that these operations are not required for general human-like intelligence. Some humans have learned to do these things, and they are important capabilities for solving certain problems. But the vast majority of humans have not mastered these skills, and these people get along just fine, even in our complex society. Of course, these things may be going on deep in our cognitive machinery, even if we have no conscious access to them, but I see no evidence of that.

So, we may want to provide a theorem-proving or optimal-planning module as part of an AI application, but I do not believe that we need to build such capabilities into the KBS itself. As a general rule of thumb, we want the KBS to handle all the memory-related operations that appear to be almost effortless for humans, and not those things that require deep thought, advanced education, or a pencil and paper.

This is a controversial view. Many AI researchers equate inference with theorem-proving, almost as an article of faith. Their inference systems provide guarantees of logical completeness and provable consistency, but they pay a terrible price for this: if they cling to these guarantees, they cannot have a KBS that is both sufficiently expressive for human-like reasoning and computationally tractable – that is, able to scale up to a large size without exponential growth in the time required for inference. So we take the radical (to some) step of separating the fast, simple inference that is integral to the KBS from more general kinds general theorem proving that we view as optional. I will have more to say about this topic in a future article.

· The backbone of the network representation is the is-a hierarchy. The is-a relation determines class membership and is also the main pathway for inheritance of properties and descriptions.[5] So if there is a chain of is-a links from “Clyde” to “elephant” to “mammal” to “vertebrate” to “physical object” to “thing”, we know that Clyde is an instance of each of these types, and that Clyde should inherit the properties of the typical member of each of these types. If the typical vertebrate has a liver, Clyde has a liver.

· Multiple inheritance – the ability for a node to have is-a links to more than one immediate superior (more general) class – is essential in a KBS designed for human-like reasoning. In addition to being an elephant, Clyde may be a male, an adult, a circus performer, and an expert skateboarder, inheriting properties and other information from each of these descriptions. Some classes are defined as intersections of others: a “boy” is a child, male, human, while a “woman” is an adult, female, human. The type hierarchy in a programming language like Java may (barely) get away with only single inheritance, but for representing knowledge, multiple inheritance is crucial.

· The KBS must support default reasoning with exceptions. When we hear that Clyde is an elephant, we assume (because of inheritance) that Clyde is gray, has four legs, and eats only vegetation. Default reasoning of this kind is very important in any KBS – it’s a big part of the “value added” by including some inference mechanisms in the KBS. However, for a real-world KBS, there are very few general statements that do not have at least a few exceptions. We may be told explicitly that, unlike typical elephants, Clyde is white, is three-legged, and that he enjoys an occasional hamburger, but despite all that, Clyde is still an elephant and he still inherits all the other elephant properties. So we must be able to add these specific statements about Clyde and cancel or over-ride the conflicting default properties that would otherwise be inherited.

The use of exceptions is controversial in the knowledge representation community. Almost everyone agrees that exceptions are potentially very useful, and perhaps unavoidable, for real-world reasoning. But for knowledge representation systems whose inference is based on theorem-proving, this capability imposes a cost that many researchers consider unacceptable: any use of exceptions takes you into the realm of non-monotonic logic, which introduces many new problems and greatly increases the computational cost of inference. So most current knowledge representation systems exclude exceptions: if you add a statement to the knowledge base, it must be universally true; statements that admit exceptions, if they are allowed at all, are banished to some disreputable annex of the KBS, outside the purview of the core inference machinery.

Controversial it may be, but for human-like performance on real-world knowledge, there is really no option: statements with exceptions are too common to ignore or to consign to second-class status. There are too many flightless birds, white elephants, meat-eating plants, and honest politicians in the world – they may be rare, but we can’t just label them as inconceivable, nor can we give up the default reasoning that handles the non-exceptional cases. So we must bite the bullet and allow default reasoning with exceptions, whatever the cost. And, if we don’t cling to the assumptions of inference-as-theorem-proving, the cost is not so bad.

· The KBS must support meta-information and meta-reasoning about the statements themselves; statements must be first-class objects with properties that we can reason about. For many problem domains, it is very important to record certain information about the statements themselves: where they came from, what probability or level of confidence we assign to each, what various analysts and critics have said about specific statements or groups of statements, and so on. And, having reasoned about what statements we choose to believe in a given situation, we then must be able to go ahead and use only the “believed” statements in our reasoning. This kind of meta-reasoning is particularly important in domains such as military intelligence, in which the task is to draw conclusions from uncertain and often conflicting reports, but it comes up in all kinds of human reasoning – even in children’s stories – and we human are very good at this.

Once again, this choice is controversial in the knowledge representation community, since it takes us beyond the comfortable and well-understood domain of first-order logic. But, once again, it is unavoidable in a KBS designed for human-like reasoning in real-world situations.

· Each entity (node) in memory is a description; each subtype or instance is a virtual copy of that description. So far, we have spoken of properties being inherited through the is-a hierarchy. In fact, each entity (node) in memory is potentially a full description: it contains not just membership in superior classes and some properties, but also relations, parts and components, and relationships among those components. So, for example, the “elephant” node (representing the typical elephant) has a “predominant color” property of “gray”, one head, one nose (connected to the head), four legs, a “hates” relation to the “typical snake” node, and some typical activities such as eating and breathing.

When we say that Clyde is an elephant, we want Clyde to suddenly become a virtual copy of the typical-elephant description: henceforth, as far as queries to the KBS are concerned, we want Clyde to behave as if we had copied the entire “elephant” description, replacing “elephant” with “Clyde”. However, we don’t want make an actual copy: that requires a lot of effort, wastes memory in the KBS, and creates the maintenance problem of keeping many “elephant” copies up to date as we learn new things about the typical elephant. So this must be a virtual copy: the inference machinery built into the KBS must make it appear that the copy has been made, without actually doing that. It can be tricky to get this right, but it is really the fundamental operation in any well-behaved KBS, and a bit of introspection will persuade you that your own memory system is also creating virtual copies, or something very similar.

· The KBS must be able to support many distinct but overlapping world-models (contexts) at once. We humans are quite adept at creating and working with multiple world-models. We use these in many ways: exploring possible futures, alternative or “what if” possibilities (including entire fictional universes, such as the Harry Potter universe), and different states of the real world at different times. We also use these to represent the states of another human’s belief or knowledge, and to reason about what that person might conclude or might do, given that belief-set. From a young age, we are able to reason about situations like this:

“The three pigs are safe inside the brick house. The wolf is outside, and the pigs know it. The wolf pretends to leave. The pigs believe this deception and open the door… You can guess what happens next!”

It should be clear that in order to understand this simple story, the reader must be able to reason about what the pigs know and believe (pre-deception), what they believe and act upon (post-deception), what the wolf intends the pigs to believe, and so on.

So to achieve human-like performance, a KBS must be able to represent each of these distinct world models at once, moving freely between them and reasoning about what would be true in each. To entertain a “what if X?” hypothesis, we must be able to create a context in which X is true and then explore the consequences, but we do not want to mix X into the set of things that we believe to be true in current reality.

Note that these contexts are distinct – each one differs from the others in some specific ways – but they overlap: in each of the contexts in the pig story, we know that brick-houses are wolf-proof unless the inhabitants open the door. So we want each new context to begin life as a virtual copy of some other context, and then we add or cancel statements as needed. We will have much more to say about this in future articles.

· In addition to static knowledge, the KBS must support episodic memory: the ability to store and reason about events, actions, and plans. Again, this is central to human reasoning ability. It appears that we use the same episodic-memory representation for many tasks. First, we need a way of representing and reasoning about event sequences that we have observed. In the course of a lifetime, we will collect a large number of these. Sometimes we will just know the sequence of events, or a partially-observed sequence; often (as with out own plans) we will know the higher-level motivations as well. Second, we can use the same representation for recognizing familiar plan-templates when we observe a few steps in the plan. Third, we can use all these stored plans and sequences as templates or recipes to guide our own planning, or our estimates of what some other actor may do next. We want our human-like KBS to have all these capabilities as well.

This is a very big topic that I will address in future articles. For now, let me just say that the virtual-copy mechanism will be crucial in representing actions, events, and plans at various levels of abstraction, and that the multiple context mechanism will provide the means for reasoning “before” and “after” world-models, and the state of the universe after each step in a plan.

So that is our preliminary wish-list for a KBS that can support human-like reasoning. There is much more to say about each of these points, and many more points I might have added, but I hope that this is enough to give you a general idea of what my students and I are trying to achieve in our wok on knowledge representation in general and on Scone in particular. It is a rather different wish-list from that of most other researchers in the knowledge representation field, but we think it is a coherent and productive set of goals.

A key point: when I speak of human-like intelligence, I am talking about human-like capabilities, not necessarily human-like implementation. I want to focus on the breadth, flexibility, and the amazing search and inference capabilities of human memory, and not necessarily on how this is implemented in the marvelous pile of neuro-stuff that is the human brain. If we could understand the general principles and mechanisms of human memory, at some level of abstraction, that would guide us both in trying to understand what the structures of the brain are doing, and also in trying to implement similar capabilities using the very different electronic hardware that is available today – or it would tell us what kind of hardware we really need in order to do this job.

So I suggest that we – some of us, anyway – approach this problem not as neuroscientists or as cognitive psychologists, but as computer scientists: Here is what the system must do; we know that this is possible (humans can do it), so what algorithms, data structures, and organizing principles are required to do the job? Oh, and as computer scientists, we must understand this well enough to implement it – no hand-waving or vague metaphors about shadows on the wall of a cave are allowed in our final theory, though we might make good use of metaphorical reasoning along the way. That is the challenge.

Note that it’s possible – some would say probable, in this case – that we will come up with models that cannot be implemented, in any practical sense, on today’s computing hardware. That’s OK. But if we come up with the answer that the problem is computationally impossible or intractable in some fundamental way, we need to look again at how we are framing the problem, because at least one solution exists.

(Well, the brain could be using magic or some as-yet-undiscovered kind of physics, but we should only accept that conclusion if we’re absolutely certain, through proof or exhaustive search, that no solution exists in computation as we know it. And, today, we are very far from being able to make that claim, despite the ravings of some dilettante physicists and mathematicians who have wandered into the field.)

When I say that we are focused on the capabilities of human memory and not on implementation, I don’t mean to suggest that we should ignore the findings if neuroscientists and cognitive psychologists, just that we should not be constrained by them. There may be many possible ways to build a human-like memory, but at present we have only one example, so we should learn what we can from it. A few examples:

· The brain apparently does what it does using millisecond-speed components (neuron firings and protein bindings), but with a huge degree of parallelism. So that’s a clue.

· While access to the human memory is fast, creating new memories is much slower, at least in the long-term, symbolic part of memory – maybe one or a few new items can be permanently saved per second.

· In humans (especially in aging computer science professors) some memories just vanish, but for many more we seem to lose some of the access threads, or these become inactive until something “reminds” us of the item we are looking for; then we can easily repair the thread. I might be able to picture a certain actor who has appeared in recent pirate movies and remember a dozen other movies he has been in, but be unable to access his name until someone says, “Rhymes with ‘strep’.” (We might prefer to construct an artificial intelligence without this partial-forgetting phenomenon, making it super-human in that respect. That might work, or we might find that this decay of access paths is not a hardware limitation, but that it is somehow essential to the operation of a human-like memory.)

So what are the important aspects of human-like symbolic[1] memory that I am so eager to capture? Let me try to illustrate the problem here with an example or two, and in a near-future article I will try to enumerate some particular abilities and features. Here is a description I’ve been using for a long time, in various forms. It first appeared in my 1977 Ph.D. thesis[2] at the MIT AI Lab:

Suppose I tell you that a certain animal – let’s call him Clyde – is an elephant. You accept this simple assertion and file it away with no apparent display of mental effort. And yet, as a result of this transaction, you suddenly appear to know a great deal about Clyde. You can tell me, with a fair degree of certainty, how many legs he has, what color he is, and whether he would be a good pet in a small third-floor apartment. You know not only that he has eyes, but what they are used for, and what it implies if they are closed. If I try to tell you that Clyde builds his nest in a tree or that he amuses himself by hiding in a teacup, you will immediately begin to doubt my credibility. And you can do this very quickly and easily, with none of the sort of apparent mental effort that would accompany, say, adding two four-digit numbers. This effortlessness may be an illusion, but it is a compelling one.

“Elephant”, of course, is not the only concept that behaves in this way. The average person knows a huge number of concepts of comparable or greater complexity – the number is probably in the millions. Consider for a moment the layers of structure and meaning that are attached to concepts like lawsuit, birthday party, fire, mother, walrus, cabbage, or king. These are words we use casually in our daily lives, and yet each of them represents a very substantial package of information. In technical fields (except, perhaps, for the more austere parts of mathematics, the situation is the same. Consider how much you would have to tell someone in order to fully convey the meaning of concepts like meson, oscillator, hash-table, valence, ribosome, or leukemia. And yet, once these concepts are built up, they can be tossed around with abandon and can be used as the building blocks for concepts of even grater complexity.

The point is not just that we can handle large chunks of knowledge as though they were atoms; the important thing is that we can find our way through these complex, nested structures to whatever fact or relationship we might need at any given time, that we can do this in a very flexible way, and that we can somehow avoid having to look individually at each of the vast number of facts that could be – but are not – relevant to the problem at hand. If I tell you that a house burned down, and that the fire started at a child’s birthday party, you will think immediately of the candles on the cake and perhaps of paper decorations. You will not, in all probability, find yourself thinking about playing pin-the-tail-on-the-donkey, or about the color of the cake’s icing or about the fact that birthdays come once a year. These concepts are there when you need them, but they do not seem to slow down the search for a link between fires and birthday parties. If, hidden away somewhere, there is a sequential search for this connection, that search is remarkably quick and efficient, and it does not become noticeably slower as the knowledge base expands to its adult proportions.

So that’s the challenge, as I see it: To build a memory system or knowledge base that can support operations of this kind, on a very large scale, and that gives us access not only to the knowledge that is explicitly present, but the much larger body of knowledge that is implicitly present. This active knowledge base is not, by itself, an intelligent system, but it is the key missing piece – the piece that ties together our sensory systems, higher-level problem-solving modules, natural language processing, and all of our experiences: past, present, and imagined-future.

In future articles we will try to break down this problem and will begin to explore how we might implement a system of this kind.

Sometimes it is useful to post an article that is just a collection of mini-nuggets: a set of propositions, perhaps with some minimal explanation for each, on a given topic. The idea is to sketch out an overall approach or point of view quickly, without getting bogged down in a lot of detail or in lengthy justification. We can always come back later to fill in more detail, point by point.

This article concerns the Scone research group’s overall approach to natural language understanding. Some bits of this approach have been implemented in the natural-language tools we are building as a front end for the Scone knowledge-base system, but much of it is still planned or “under construction”. In any case, it seems useful to produce some kind of roadmap, even if it’s crude, general, incomplete, and subject to later revision.

I should mention that, while most of the points listed here seem obvious to me, many of them are controversial. Others may be generally accepted by researchers in language understanding, but not generally acted upon – that is, other researchers may agree that these are good ideas for the distant future, but in the meantime they feel it is more practical to follow some other path.

I should also mention that, in many cases, my rationale for favoring these propositions is rooted in introspection – what I can observe (or think I can observe) about how I handle various issues in language. Psychologists and linguists are justifiably wary of introspection arguments, which have often been shown to be incorrect or at least misleading. For example, introspection would suggest that multiplying two large numbers is computationally more demanding than vision or speech understanding, and we now know that is false – very false. However, when solid experimental information is lacking, I have found introspection to be a very powerful source of “search-guiding heuristics”, as we say in AI. A heuristic is a hint that gives us some guidance about where the good answers may be hiding in a large and confusing space of possibilities.

So: nobody should just accept these propositions as proven fact or even as a consensus within the field. I’m just trying to indicate my own best guesses, as of today, about the approaches that are most likely to lead to success. And I’m trying to show what part of the space my group is working in, thus providing some context for related posts that will come later.

One final point: I don’t claim that the point of view presented here is original or unique, though it is some distance from the current mainstream of natural-language research. These ideas have been gathered from many sources over the years, and in most cases it is hard for me to reconstruct the influences that went into this view. The work of Chris Riesbeck and his student Kevin Livingston on the DMAP system is pretty close in spirit to what we are doing.[1]

In case you’re wondering, the photo is of Rainbow the Guinea Pig, who is hereby designated as the patron saint of mini-nuggets. She produces them much faster than I can. OK, on with the show…

· The key problem is natural language understanding (NLU) – that is, converting spoken or written language to some language-independent, concept-based internal form that is easy to reason about. There are plenty of other natural-language problems one could work on, without going all the way to meaning, but NLU is the heart of the monster. If we don’t extract and represent the meaning, we can never understand the item well enough to answer questions, draw conclusions, or learn new deep knowledge from the text or speech. And if we do handle NLU, all the other natural-language applications – classification, summarization, even parsing – either fall out or can be done in a deeper and less brittle way. The NLU problem is difficult, but ultimately there is no way around it.

· The knowledge base must be a full partner in NLU, not just a place where you store the output of language processing. As I argued in a previous article, the language fragment itself contains only a minimal amount of information; in order to make sense of it, the listener must combine what was said with a large body of background information that is assumed to be known by both the speaker and the listener.

· Syntax is important – but mostly as a tie-breaker for possible meanings. For decades, a lot of NL researchers have focused on syntax and parsing, in part because of the influence of Noam Chomsky, and in part because this is an easier place to start than going after meaning. But syntax is just a tool, providing some hints about how a linear string of words should be folded into a tangled meaning network whose structure is far from linear. Syntax does play an important role in language: “Dog bites man” is different in meaning from “Man bites dog”, and syntax (or at least word-order) is the only difference between these two fragments. But an utterance like “You me lunch pizza tomorrow” is generally understandable, despite the almost complete lack of syntax. Meaning is doing all the work here: understanding how these words fit together into a larger structure would be impossible if “lunch” and “pizza” and “tomorrow” were concepts whose meanings were unknown to the listener.

· We want our NLU techniques to work well with non-grammatical text and speech. Linguists seem to be endlessly fascinated by the question of whether or not a sentence is correctly formed – in most of their papers, ill-formed sentences are consistently marked with the “asterisk of shame”. While it is interesting that people seem to be able to make consistent and confident correctness judgments about sentences (even if they speak a non-standard dialect of their language, so their judgement differs from that of the “experts”), that’s not nearly as important to us as the ability to extract as much meaning as possible, even from ill-formed utterances.

Recently, members of my research group have been working on understanding free-text fields in patient medical records. These are either hastily scribbled notes or notes that were hastily dictated and later transcribed by personnel with limited medical training. It is interesting that in a corpus of 100 such notes, there are only a few complete grammatical sentences. And yet other readers with medical training can almost always make sense of what the author was trying to say. That, I think, is the more interesting challenge.

· When in doubt, guess and go on, but be ready to backtrack and try again. A lot of NLP systems are organized as a strict pipeline: tokenization, morphology, parsing, and then semantic analysis (meaning), with no backtracking allowed. Other functions, such as spelling correction, ambiguity resolution, and reference resolution, may also be broken out into separate modules. I think that this one-way-flow approach is a bad one. In a strict pipeline, the upstream modules lack the information they need in order to come up with the best single result; instead, they must assemble and pass forward a data structure that lists all the “live” possibilities, with some sort of score for each. Then the downstream modules can narrow the list, throwing away the possibilities that don’t work at their level. The problem is that this data structure can grow to huge size, since the uncertainties tend to multiply. It is possible to come up with an efficient encoding for that large data structure, but the cost of encoding and decoding can be very high.

A better approach, I think, is for the upstream module to engage in a brief conversation with the downstream semantics (or knowledge base) module, trying to gather the information it needs in order to make a choice. And then it should just produce its best guess and pass that on. That guess will sometimes be wrong, so the upstream module must be ready to receive an error message kicked back from downstream: “That guess doesn’t work (for some specific reason). Please try again.” Implementing this loose, flexible control structure, supporting what we call non-local backtracking, does impose some cost, but I believe that this will be far less than the cost of building, passing forward, and unpacking a whole package of possibilities so that the upstream modules can wash their hands of any further responsibility. In most cases, the initial guess will turn out to be the right one, so “guess and go” can be very efficient.

· Probably something like a Construction Grammar is the best tool for handling syntax, given our goals and general approach. Think of a construction as a pattern to be matched against the incoming text – a sequence of certain specific words and some variables that are restricted as to the syntactic type and/or the semantic category of the filler: ( ?X{person} kicks ?Y{physical object}). When the construction is matched, it can produce some new structure in the knowledge base or a new composite language-object (e.g. a noun phrase) that can be matched by some other construction. Or it can initiate some processing, for example to resolve an ambiguity or to choose between two matching constructions. Or all of the above.

Construction grammars seem to be a good fit for us for several reasons: they can process language fragments in a bottom-up way, instead of insisting on having a correct and complete sentence; we can easily create special constructions to represent idiosyncratic or non-grammatical constructs that we encounter frequently; the matching (or potential matching) of a construction is a good time for us to check with the knowledge base to see if the emerging meaning makes sense; and the proponents of construction grammar tend to view language learning mostly as a process of bottom-up generalization, starting with specific utterances that have been encountered and then trying collect these into more general patterns.

Charles Fillmore and George Lakoff are often credited as the pioneers of construction grammars. A good treatment of CG, and of learning constructions by generalization, is the book Constructions at Work by Adele E. Goldberg. There are many variations on this theme: some of my students are fans of Radical Construction Grammar, a version proposed by William A. Croft; as of now, I’m agnostic about all these variations – I’m happy to go with whatever we can get working.

· Robust speech understanding depends on knowledge. There is currently a lot of work on improving the signal-processing levels of speech understanding systems with the goal of making these systems more robust under noisy conditions. Any progress on that front is welcome, but I believe that future improvement in this area is more likely to come from the application of knowledge.[2] The reason I can make out what someone is saying in a very noisy environment – so noisy that some words are completely obliterated – is that I usually can predict what a person is likely to say next. And if I think I have heard (or deduced) what the person said, I can immediately sanity-check my understanding against the current conversational context and my extensive background knowledge. If my interpretation doesn’t make sense in meaning-space, I can go back to the signal-processing level and ask it to come up with some other hypotheses.

· Process the text or speech eagerly, in order of arrival. This proposition is based on introspection, though I suspect that it would be easy to confirm this experimentally – that may already have been done.

I have a very strong sense that I am processing a speech stream more or less as it arrives, rather than waiting until a whole sentence is in hand so that I can apply a more global, top-down style of analysis. I have the same sense when I am reading text: I process English text left-to-right as I read it. The processing may lag the input by a few words, so that we can work at the phrase level rather than the word level. We will occasionally be forced to defer processing of some phrase until we get more information, but I think that we human listeners do as much processing as we can, as soon as we can. This seems like the best strategy if we want to follow the previous advice about robust speech, using background knowledge to help us identify and sanity-check the words we hear them.

A quick example. Here comes some text from a recipe, with the processing indicated by the comments in italics: “In a bowl…” OK, we’ve got a container here – a place where something is going to happen. The action or event is probably coming next. “…mix together…” OK, the action of mixing of ingredients often takes place in a bowl, so that fits our expectation. We’re probably going to get a list of ingredients next. “…the flour, salt, and sugar.” Here’s the list we were expecting. As discussed in an earlier post, the word ‘the’ indicates that we should already know what measures of flour, sugar, and salt are being referred to here. Probably these ingredients were listed, with the quantity of each, at the start of the recipe. Check whether we have seen this list. “Stir it gently.” The word ‘it” here must refer to the mixture in the bowl – the stuff being stirred. The knowledge base knows that stirring is a kind of mixing, and now we’re being told more about the manner of the mixing.

And so it goes. In addition to trying to resolve the referents for various phrases as we go along, the eager processor may also be asking “Why is the speaker telling me this?” and “Do I believe it?”

· To fully represent the “meaning payload” of natural language we need a representation significantly more expressive than first-order logic (FOL). We will have a lot more to say about this in future articles. For now I’ll just say that things like the temporal site of an action (indicated by verb tense), intention, belief, supposition, and meta-information about whether we believe a given statement all rely on mechanisms in Scone that lie outside the domain of conventional first-order logic, and far outside the realm of description logics such as OWL.

· Linguistic knowledge is distinct from world-knowledge, but it can be stored using the same knowledge-base mechanisms. The world-knowledge representations used in Scone are expressed in terms of concepts and relations, independent of how they are described in any human language. These are organized in a multiple-inheritance type hierarchy with exceptions. A Scone concept may be linked to one or more names (words or phrases) in English, and to additional names in other languages and dialects. These, too, live in a type hierarchy, but a different one: an action-verb is a verb is a word, and so on.

The name/meaning relation is many-to-many: even within a single language, an object may have many names, and a word may have many meanings. Similarly, larger linguistic patterns (e.g. construction grammar patterns) may be stored in the knowledge base, occupying their own multiple-inheritance taxonomy. “X kicks the bucket” is a kind of “X kicks Y”, but it is more specialized and, in this case, produces a different meaning.

· Ideally, we would like to use the same body of language knowledge for understanding and for generation. I’m not sure if we can do that efficiently, but it would certainly be a waste of space if we had separate knowledge structures for understanding and for speaking. In addition, if the input and output structures were distinct, we would have to worry about keeping them in synch.

In this article, I would like to expand that view just a bit: in addition to what a sentence (or other chunk of language) means, we must pay attention to what it does. That is, we must consider what inferences and procedures are triggered when a listener or reader encounters the utterance – that, too, is an important part of the payload. To illustrate what I mean by this, let’s consider a very simple and familiar example (at least to English speakers): the function of the definite and indefinite articles, “a”, “an”, and “the”.

Before we dive into this, let’s dispose of the “a” vs. “an” distinction. Functionally, these are really the same word. We use one form or the other depending on the initial phoneme (pronunciation, not spelling) of the following word.[i] If a consonant sound comes next, use “a”; if a vowel sound, use “an”. So for the remainder of this article, we’ll just refer to “a” or “an”, and whatever we say of one will be true of the other. These are the so-called indefinite articles, while “the” is the definite article.[ii]

OK, what do these words mean? Well… nothing, really: they’re what we call “function words”. So let’s look at the function.

Suppose you say to me, “While I was walking home today, the dog attacked me.” The use of the definite article here is a signal that you expect me to know (or be able to figure out) what dog you’re talking about. My mental machinery should go to work and try to figure out which dog this is. If I can’t figure it out, I should ask you for a clarification: “Wait… what dog?”

I might defer this query for a while to see whether you’re about to provide me with enough additional information to solve this problem: the next sentence fragment might be “… you know – that vicious schnauzer that lives next door.” But I don’t want to defer the clarification for too long – you have signaled that I am expected to know what dog you’re talking about, and your subsequent speech acts will assume that we’re both now focused on the same entity. When I finally do figure out what dog you mean, I might have to play catch-up on what you’ve been telling me, and if I wait too long my memory of your words may start to overflow or evaporate. (Then again, I might decide that I just don’t care what dog you’re talking about.)

The indefinite article behaves differently. Suppose you say, “While I was walking home today, a dog attacked me.” That’s a signal that you don’t expect me to know what dog you’re talking about. I’m supposed to create a new entity in my mental knowledge base – an instance of the type “dog” – and you’re probably going to tell me some additional information about this creature. (Otherwise, what you’re saying won’t be very interesting.) And, sure enough, such information arrives by the end of this sentence: this just-introduced dog has attacked you. From that I might deduce that you may have been injured, and that maybe we should both choose a different route in the future.

Once this new dog has been introduced and represented in the KB, you can then refer to this particular dog with the definite article: “The dog just wouldn’t stop.” You are now signaling that I should know what dog you mean, and unless there are other dogs in the conversation there should be no confusion.

I may later learn enough that I can equate this anonymous new dog with one I already have represented in my KB – a dog that I may already know something about: “I bet this dog is Chuckles, the ferocious miniature schnauzer, scourge of the neighborhood and relentless enemy of all mail-persons.” In Scone, we would use an EQ-link to equate the new dog-node to the existing “Chuckles” node, effectively merging the two stored descriptions. But at the time you say “a dog” you’re signaling that I’m not expected to identify dog. That will be your assumption as the conversation continues.

So these two little function words play a useful role in shaping descriptions and dialogs in English. Whenever we are referring to an anonymous member of some class, the use of a definite or indefinite article is mandatory in correct English. Of course, this being English, there are many odd exceptions to this rule, probably created to make life difficult for foreigners trying to learn the language. For example, in referring to a specific entity using a proper noun, we normally don’t include an article (”I’m going to Cuba.”) unless the name is some sort of collection (”I’m going to the Virgin Islands.”) – and the exceptions often have their own exceptions. The question of when to include or not to include an article seems to be one of the most difficult aspects of English for non-native speakers to master; the choice of which article to use, when you use one, seems not to be such a big problem.

It is interesting that the use of a definite or indefinite article is not mandatory (and may not even be possible) in other languages. Some languages indicate the same distinction with word order or morphology, but John McWhorter[iii] reports that only about 20% of the world’s human languages consistently mark this distinction in an explicit way. In the non-marking languages, the listener may have to do some extra work to figure out whether the dog in question is one he is expected to know about, but usually this can be figured out from other cues; if not, and if the distinction is important, the speaker can use some special marker, often a form of the word “that”, to resolve the ambiguity, but this is not a mandatory part of the grammar.

The point of all this is that these articles, like many other “function words”, have no meaning in the usual sense, but that they provide some sort of guidance for the listener’s mental processing of the utterance. Pronouns and all sorts of other references may trigger similar bursts of processing as we try to make sense of what we are being told or what we are reading.

So, to reiterate: If we want to truly understand an utterance or piece of text, we must pay attention to what each fragment means, and also to what it does.

===================

Why is this the case? In retrospect, it is perhaps not too surprising. The problems that AI researchers have so far attacked successfully are the ones that we humans must work hard to solve. We are aware of each step in the process. We write textbooks and manuals that describe, in considerable detail, how to perform these tasks. These are serial, conscious behaviors. On the other hand, the problems that have proven to be the hardest for AI have been the things that we humans can do “without any mental effort”: recognizing an object, understanding a spoken sentence, understanding (and being able to answer questions about) a “simple” children’s story. Whatever is going on when we do these things, we don’t have conscious access to it.

When we try to build machines and programs that do these jobs, we quickly discover how deep and complex these tasks really are. But the amazing thing is that we had to discover this. It’s not obvious to the five-year-old kid, reading or listening to a story about pigs, wolves, and construction materials, that he is doing something much harder (in some sense) than arithmetic or chess or interpreting nuclear magnetic resonance spectrograms. An awful lot of complex computation is going on as the kid makes sense of his story: sentences are being parsed, words are being disambiguated, motives and belief-states of the characters are being modeled, and so on, but the reader is mostly unaware of all this processing unless something goes wrong, or unless a partial solution pops up to the conscious level as a “flash of recognition”.[1]

In the early days of AI we were blissfully unaware that all this unconscious[2] processing was going on. I think that this explains, in part, why some early researchers in the AI field made predictions that, in retrospect, were wildly optimistic. These researchers were focused on the part of the problem they could see – the conscious, high-level, “difficult” part – and nobody realized until later that this was built on a hidden foundation that was doing a tremendous amount of work, but that somehow made that work seem “effortless”. After the first rush of AI and expert-system success (including many results of great commercial value) the field has paused for a while as we search for the principles and mechanisms that will allow us to replicate these hidden “core” capabilities.

In the meantime, there has been another wave of valuable AI applications based on statistical machine learning. Some of these results have been very impressive – search engines, adaptive control systems, and many kinds of data mining, just to name a few – but I would argue that these developments have not brought us much closer to understanding the core capabilities of human-like cognition, and in many ways they have been a major distraction.

So, we have had one wave of valuable AI applications based on symbolic “expert systems” technology and another wave based on statistical machine learning, but we are still far from implementing a broad, flexible, human-like intelligence. Some crucial capabilities seem to be missing. If we cannot yet implement these missing capabilities, can we at least list what they are?

Here is my own personal list of the fundamental missing capabilities that are necessary for human-like AI:

· The ability to assimilate and store large amounts of symbolic knowledge and to make that knowledge effective. By effective, I mean that the knowledge is in a form that supports reasoning, and that it plays a role in determining the system’s behavior.[3] It’s not enough just to stuff in the knowledge in the form of undigested English: it’s very hard to reason precisely using that sort of representation. So some sort of logic-like representation would appear to be necessary.

· The ability to take a set of features and expectations and find the best match (or a small number of plausible matches) from among a vast set of stored descriptions. This capability lies at the heart of many kinds of recognition: matching a stream of acoustic features against stored words and phrases; matching visual features against stored shape descriptions; matching observed actions against stored plan templates that might explain why these actions occurred; and so on. These matches are seldom perfect, so a brittle representation such as a hash table won’t do the job.

· A planning mechanism that exhibits the sort of flexibility and resourcefulness that we see in humans (and in many animals as well). By flexibility, I mean that when the system is blocked, it must fall back and choose an alternative path, perhaps combining its operators in novel ways. The planner must be robust in the face of incomplete knowledge and conditions that change at runtime, and it must be well integrated with the system’s store of world knowledge. The system should be able to learn new plan templates by observation or by being supplied with high level “recipes” – not detailed code. It is not necessary (or even particularly desirable) for the planning to be optimal; it just needs to be “good enough”.

· A learning paradigm that, over time, can provide the system with the vast amount of knowledge it will need – both symbolic knowledge and the “recipes” that are needed to create and understand new plans. Statistical learning will certainly play a role, but we also need mechanisms that “learn by being told” and that learn by observation – often from one or just a few examples.

· A flexible, integrated architecture to pull this all together. See my earlier article on this topic.

These are just the capabilities that I think are most important; there are many smaller ones, some of which depend on these.

As I said, this is my own personal list of “core” AI issues. I should point out that most of my colleagues in the AI field would come up with very different wish-lists. Among the capabilities that other researchers might highlight are further improvements in statistical learning; learning by mining the semantic web; optimal planning; coordination of many intelligent (or slightly intelligent) agents; solving of large constraint systems; more improvement at the lower sensory-motor levels; and building better interfaces between AI systems and humans, so that the AI systems can just stick to the things they do well. These are all excellent goals, but in my opinion they are not on the critical path. They don’t get us any closer to the heart of the monster.

While I can’t claim that I (or anyone else) has completely solved any of the issues on my list, I think we have made some progress, or at least have come up with some good ideas about how to make progress. Future articles will address each of these areas in greater depth.

======================

Not surprisingly, the book’s primary focus is on First-Order Logic and its more restrictive relatives. However, there is some coverage of other approaches and of issues that cause some difficulties for the logic-based approaches. So, overall, I find it to be an excellent and balanced presentation of the mainstream approaches and issues in the knowledge representation field.

For anyone with a serious interest in KR, but not much background, a good plan would be to read this book and understand most of it before considering the alternative approaches that I will be arguing for in this blog.

Given the occasion, the article necessarily contains some thoughts about the proper role of AAAI as an organization. Those may or may not be of interest to readers of this blog. But I believe that Ron’s arguments for the importance of an integrated attack on intelligence are right on the mark. As long as most AI researchers focus on only one small component of intelligence or one kind of problem, we will never have systems that exhibit human-like versatility in a complex, ever-changing environment.

The one area where I disagree with Ron is in his enthusiasm for evaluation and metrics in our work – a new-found enthusiasm, according to his article. It is true that our sponsors will often require detailed, quantitative performance measurements as a way to evaluate the success of the projects they fund. So we have to live with that.

It is also true that there are times when, if no scoring system were imposed on a research effort, we would have to invent one. That is often a good way to keep the project members focused and motivated, and there are times when a bit of competition (keeping score) is a good thing. In areas like statistical learning, appropriate metrics may be the only good way to tell if the system is working properly and doing something interesting.

However, I have seen too many promising research projects ruined or badly damaged by rigid metrics, rigidly applied. A “wild frontier” field like AI does not progress in slow and steady increments. Implementing a promising new idea usually requires that we take a step or two backward in our measurable performance before we get the great leap forward. Sometimes these new ideas will fail — that’s an important part of research. If we are in a situation where a particular performance metric must improve by a particular amount every year , with the threat of immediate project cancellation as the “incentive”, that creates a tremendous disincentive to try anything risky and innovative. I can think of no better way to ensure that a project will produce some routine progress, but no breakthroughs. And if the metrics are used to drive a competition – only the top few groups in each year’s competition will be funded for the next year – that guarantees that the competing groups will be secretive and unable to build on one another’s ideas.

Anyway, this blog is supposed to be about AI ideas and not about the management of research projects, so I’ll leave it at that. I do share Ron’s enthusiasm for “Grand Challenge” problems, whenever we can come up with good one. I’ll say more about that in a later post.

[1] The organization has since renamed itself the “Association for the Advancement of Artificial Intelligence”, keeping the AAAI acronym and properly reflecting AAAI’s evolution into an international organization.

Over time, human language has evolved into a beautifully effective and efficient tool for this task. We have developed all sorts of clever linguistic signals that indicate how a linear string of symbols should be folded back into a complex, tangled web of entities and statements about them. Prepositions probably rank right up there with fire as a great human invention (or perhaps, if you believe Chomsky, a great invention of biological evolution).

Because the channel is so narrow, I don’t want to waste precious bandwidth by telling you things that you already know. My goal is to use a stream of language to paint a thin veneer of new knowledge-structure over what I assume you already have in your head. To my computer-science colleagues, I know that I can use a word like “hashtable” without further explanation; to convey the same meaning to the (presumably) non-technical person sitting next to me on the bus might take a while. To my wife, I know that I can say, “Morty was sick again today”; to a stranger, I would go on to explain that Morty is our cat and that he has a chronic problem with hairballs. When two people meet for the first time and want to communicate, a good fraction of their speech acts are devoted to exchanging information about what each person already knows, so that subsequent conversation can be reasonably efficient (starting, sometimes, with “Do you speak English?” and then maybe “Have you heard the news today?”). If I guess wrong about what the other guy knows, I’ll have to backtrack and try again.

So in natural-language communication, we want to say as little as possible and rely as much as possible on shared background knowledge. Consider how much background knowledge is required to understand a short news item like this:

“In response to last Tuesday’s café bombing in Tel Aviv, Israeli tanks today crossed into the Gaza strip and demolished the houses of several suspected Hamas leaders before retreating under a hail of rocks and Molotov cocktails.”

If we wanted to create a headline for this story, we might go with “Israeli Army Retaliates” or “Angry Palestinian Mob”, but none of these words (except “Israeli”) appears in the original story. The passage does not even contain synonyms for these words. So to understand and label this brief fragment of text requires some knowledge of Israel, Palestine, Gaza, Tel Aviv, Hamas, tanks, and Molotov cocktails. It requires some understanding of concepts like terrorism and revenge. It requires the knowledge that crushing a house is a hostile act, likely to anger the owner and his friends. And so on…

I think it is clear that most linguists, computational linguists, and AI researchers have accepted for a long time that meaning – both the knowledge conveyed by an utterance and a large amount of background knowledge – is central to the enterprise of producing and understanding natural language. And most of them accept that meaning is really the key to most of the other operations that we want to perform on chunks of language: categorization, summarization, question answering, search, translation, and so on. But having accepted that, they see that collecting and representing very large amounts of knowledge efficiently and effectively is a very hard problem – perhaps the hardest unsolved problem in AI. So most of them go off and work on something else instead: parsing, morphology, meaning-free search engines, statistical translation based on parallel corpora, and so on. These are all valuable efforts, and some of them have yielded valuable results, but I think that many of these researchers would admit (if they feel like being honest) that they’re not really attacking the heart of the monster. They’re dancing around the edges of the really hard problem.

The amazing thing, really, is that a meaning-free bag-of-words model can work at all as a surrogate for meaning. The truly astounding thing is that these models (perhaps augmented with some additional shallow features) work well enough to produce truly useful tools – even supporting some huge, successful companies such as Google. But almost all of these technologies deliver only partial success – maybe 80% – because they are not really working in the same feature space as the humans who wrote the text and the humans who form the intended audience. So that last 20% error (or whatever) is going to be very hard to eliminate by meaning-free approaches.

In many domains, that’s OK. We all use Google (or some competitor) every day, and we’ve learned to live with the fact that a lot of the documents it retrieves for every search are not relevant – these are just documents that happened to have some of the right words. The result is still very useful, most of the time. But imagine having a search engine that actually reads all these documents, understands them to some degree, and that can answer questions about them. The reason that Google returns full pages and not just answers is that it depends on its human users to figure out whether a document really contains the answer to their question, and what that answer is.

The realization that, in an information-rich space like the Web, we can do so many useful things by statistical means – without really understanding anything – has led to a sort of gold rush. It has been an exciting time. There was (and still is) much low-hanging fruit, ready for harvesting. This gold rush has produced a lot of valuable technology and it has created a few great fortunes. But it has not brought us much closer to understanding the central problem of extracting and truly understanding the deep meaning of an utterance. And without that, I think we have no hope of eliminating that last tenacious component of the error.

As difficult as the task may be, we will not achieve real natural-language understanding until we confront the problem of representing meaning (including all the background knowledge) head on. The representation may be in some kind of logic, or a semantic network, or perhaps something more neural and fuzzy and distributed. Probably it will be all three at once: these may be just different viewpoints – different ways of characterizing (or implementing) the same underlying concepts. But whatever form the knowledge takes, we can’t get much farther without it.

We can’t go on indefinitely ignoring the elephant in the room. His name is Clyde, and he’s not going away.

This article was originally published as a position paper for the 2006 AAAI Fellows Symposium, celebrating 50 years of Artificial Intelligence as a field.  Copyright © 2006, Association for the Advancement of Artificial Intelligence.