On Knowledge Representation
[ |<br>Prev |<br>Index |<br>Next |<br>>>]
Saturday, July 13, 2013
On Knowledge Representation
The task of storing a phone number in an address book seems pretty<br>trivial on the surface, but it has stumped me for years. The<br>issue, of course, is not storing the number itself, but rather representing the context in which it applies.<br>The usual approach is to pigeonhole everyone into the common cases -- work, home, and<br>cell, or maybe a flexible list of tagged numbers.<br>But what if I want my address<br>book program to understand me (enough to give me the right number at<br>the right times) when I say that John's number during August<br>will be 555-1234 between 6 and 9pm except on days that it is raining<br>or if I am calling from out of state?
We humans are pretty good at describing things with natural language,<br>but getting computers to understand it is another matter.<br>Although rarely admitted, the problem is not writing a program that<br>understands natural language, but writing a program that<br>understands anything. That, in turn, is mostly about<br>representing knowledge in the first place--not for communication, but<br>in the mind of the program itself.
This essay is an exploration of that topic, with an eye toward<br>defining a good "machine language" for artificial intelligence,<br>but also just for understanding some of the common knowledge<br>representation paradigms (especially those used in programming<br>languages) in a broader context.
What is Knowledge?
Loosely, knowledge can be divided into two categories:<br>model, and state. A model is a representation of how things work,<br>of what is possible, of what things go together or don't, of what<br>is always and everywhere true. State is<br>a representation of how things are at a particular time and place.<br>In more mathematical terms, a model is a statistical distribution<br>over all possible states, saying which states are likely, which<br>impossible, and so on. Your model of the world is your intuitive sense for<br>how the world works. Your state is what you see, hear, think, feel, at<br>this particular moment, along with the state of the rest of the universe<br>around you.
Correspondingly, your memory comes in (at least) two distinct types:<br>conceptual memory,<br>which over time has learned to model the world--everything<br>from your ability to recognize a tree to your expectation<br>that someone will giggle when tickled--and instance<br>memory,<br>which lets you recall past states, your memory of particular things and times<br>in the past--such as that particular time your friend giggled when tickled.
The representation in our heads is obviously very general. Even from<br>single photograph, we can focus on the color of a dot, the make of the<br>car, or the relative size of the two dogs. Our understanding of the<br>scene goes far beyond just the items in it, but includes their relationships<br>to each other, and to many things beyond the scene itself. If a part of<br>the scene is obscured with a stain, we can easily imagine what might be<br>there. If asked to describe it, we could communicate it fairly concisely,<br>and someone else could imagine an approximation to it in their heads.
So how do we do it, why is it hard for a computer, and how can we fix that?
Let's start by looking at state representation since, as mentioned above, a model<br>can only be understood as a distribution over possible states, so if we<br>can't represent state we would be hard pressed to represent a model.
The State
Perhaps starting as early as childhood algebra, most of us learn to consciously<br>represent state through the analogy of things in containers. "X = 10" means<br>there is a particular thing--the number 10--in the X container. We might imagine<br>ten stones in a cup. We call X<br>a "variable" because it can hold different things. We call the things "values"<br>because the first things in containers were things of trade, and what we cared<br>about was their worth. In algebra, our goal is usually to infer what value the<br>container or variable holds. Later on in an office job we might create forms with spaces to fill in<br>values. In computer programs, we make complex, hierarchical structures of<br>containers, create new kinds of values which are pointers to other containers,<br>store collections of value in databases, and so on--the paradigm permeates<br>computer science. The analogy is so ubiquitous<br>that if ever it falls short of some task, we think in terms of augmenting or<br>adding to it rather than starting over with something else.
But even in that childhood algebra, we also saw things like "X
I say "gracefully" because clearly<br>we can contrive ways to do it, and we do: We can create a new kind of container<br>which holds representations of facts about other containers. So that the<br>whole expression "X<br>It is tempting here to say that "X knowledge we have<br>about state comes from observation or inference, both of which are usually<br>incomplete. If we read our weight as seventy kilos, we are not observing<br>"X = 70" but more typically something like "~69.5
Our childhood algebra...