CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Oct 14, 1998)

"Introduction to Knowledge Representation"

Motivation: To Handle Semantics the System Needs Knowledge


 

Various Methods of Knowledge Representation


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.
 
 


 

Fundamentals: Defining Objects in Class Hierarchies


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

tanimoto@cs.washington.edu