"Introduction to Knowledge Representation"
Knowledge: Not just data or
information, but information in a context in which it can be readily applied
to solve problems, perform tasks, etc.
1. Production rules.
2. ISA hierarchies.
3. Semantic networks.
4. Propositional logic statements.
5. Predicate logic statements.
6. Frames.
7. Other: neural nets, probabilistic
inference nets, raw text and images, sets of plans, evaluated states in
a search space.
1. Much knowledge is organized
around "common nouns" (common means "not proper").
E.g., in the sentence, "I live
in a house" the word "house" is a common noun. "House" refers
to a set of objects that have the particular property of being a possible
home to someone or something.
2. A particular house, like The White House, is an element of the set of houses. "The White House" is a proper noun phrase, referring to a particular house.
3. "Houses" typically refers to the class of houses. "a house" typically refers to an arbitrary member of the class... an arbitrary instance. This instance may stand for the whole class of houses in some situations, such as in a definition: "a house is a building".
4. "My house" or "Steve's house"
refers to a particular instance of the class of houses.
It refers to an element of the
set. It does NOT refer to a subset of the set.
"IS A" vs "IS IN"
We say that a house "is a" building, and we say that the White House "is a" house, but we do not use "is a" in the same way in these two cases.
In the first case, we're saying that the set of houses is a subset of the set of buildings.
In the second case, we're saying
that the White House is an element of the set of houses.
Partial Orders
The class inclusion relation is a partial order. This allows certain useful inferences to be made.
An igloo is a house.
A house is a building.
Therefore, an igloo is a building.
Let's assume there is some domain
(big set) of elements that we are potentially interested in.
For example, this could be the
set of all man-made objects. Let's denote it by S.
A partial order over a domain S is a binary relation (call it R) on S having three properties:
For all x in S,
x R x
--- R is reflexive
For all x and y in S,
if x R y
and y R x then x = y
--- R is antisymmetric
For all x, y, and z in S,
if x R y and
y R z then x R z
--- R is transitive
Transitive Closures and Transitive Reductions
Suppose our domain is S =
{ a, b, c}
Let Q by a binary relation
Q = { (a, a), (b, b), (c, c), (a, b), (b, c) }
Note: Q is not transitive.
To make it transitive, we have
to add the pair (a, c).
Given a binary relation Q, the transitive closure of Q is the smallest transitive relation containing Q.
Given a transitive relation R, the transitive reduction of R is the smallest relation whose transitive closure is R.
If R is transitive relation containing
lots of "shortcuts" then the transitive reduction of R may be a much more
efficient representation of R than explicitly listing all the elements
of R. For example, if R is a total order, then the explicit representation
of R takes O(n^2) pairs, while the transitive reduction of R uses only
O(n) pairs. Here n is the cardinality of the domain.
n = |S|.
The LINNEUS Program
Objectives: (1) Store an ISA hierarchy, obtaining each link from the user through a natural-language interface, and (2) Answer basic queries about the information, making certain kinds of inference when needed.
Input forms:
(a dog is a mammal)
I UNDERSTAND
(what is a dog)
A DOG IS A MAMMAL
(a mammal is an animal)
I UNDERSTAND
(is a dog an animal)
YES INDEED A DOG IS AN ANIMAL
(an animal is an organizm)
I UNDERSTAND
(why is a dog an organism)
BECAUSE A DOG IS A MAMMAL, A MAMMAL
IS AN ANIMAL, AND AN ANIMAL IS AN ORGANISM
(a dog is a pet)
I UNDERSTAND
(what is a dog)
A DOG IS A MAMMAL AND A PET
Last modified: October 14, 1998
Steve Tanimoto