Mini-Nuggets: Knowledge Base Requirements for Human-Like Thought

Scott Fahlman,   June 25, 2008
Categories:  AI, KR Issues    

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.