PROBLEMS IN KNOWLEDGE REPRESENTATION AND INFERENCE

Closed world assumption
The frame problem
The qualification problem
The monotonicity problem
Non-deductive inferences

%----------------------------------------------------------------------------

CLOSED WORLD ASSUMPTION:

Given a set of axioms S, there are some facts that S tells you nothing
about.  These facts are neither theorems of S, nor contradicted by S.

E.g., Given:
        for-all(x) [ RUSSIAN(x) => REDHEAD(x) ]
        for-all(x) [ REDHEAD(x) => not(BLOND(x)) ]
        RUSSIAN(IGOR)
        DUTCH(HANS)
      We can prove: REDHEAD(IGOR)
      We can contradict: BLOND(IGOR)
      We can neither prove nor contradict: REDHEAD(HANS)

CLOSED WORLD ASSUMPTION:
        Assume that the system knows or can derive everything that is true.
        Then anything that the system can't prove is false.

%----------------------------------------------------------------------------

FRAME PROBLEM - updating world models

Logic assumes that everything stays the same unless expressely stated.

This may not be true because:
        Representation may be incomplete
        Actions may have side effects

Example: John sat in his kitchen, drinking a cup of coffee.
                 Inferences: IN(JOHN,CHAIR)     SITTING(JOHN)
                             IN(JOHN,KITCHEN)   HOLDING(JOHN,CUP)
                             IN(JOHN,HOME)      IN(COFFEE,CUP)
                             ...                ...
                             ...                OWNS(JOHN,KITCHEN)
         John put on his coat and left for work.
                 Inferences: WEARING(JOHN,COAT)
                             IN(JOHN,OFFICE)
         But also negation/retraction of some previous inferences:
                             IN(JOHN,CHAIR)
                             IN(JOHN,HOME)
                     but not OWNS(JOHN,KITCHEN)

THE FRAME PROBLEM:
        Which facts/inferences should be undone when something happens?
        How should the world model be updated?

%----------------------------------------------------------------------------

QUALIFICATION PROBLEM

The closed world assumption states that everything is false unless explicitly
stated or derivable.

        Birds can fly.
        A turkey is a bird.
        Therefore turkeys can fly.

        The turkey on the Thanksgiving table is a turkey.
        Therefore the turkey on the Thanksgiving table can fly.

        This is wrong.  We need to QUALIFY the rule:
        Birds that are alive can fly.

        But what about penguins?
        Birds with pinned wings?
        Birds with feet in cement?

THE QUALIFICATION PROBLEM: It is impossible to write down every qualification
for every rule.

%----------------------------------------------------------------------------

MONOTONICITY PROBLEM

Adding a new (consistent) axiom never invalidates a previous proof.

    Therefore the number of theorems is monotonically non-decreasing.

    The practical problem: Inefficiency. The system may get bogged down in
    the ever increasing numbers of theorems it can prove.

    The theoretical problem: This prohibits DEFAULT REASONING or REASONING
    FROM INCOMPLETE KNOWLEDGE.

        Example: Suppose John, sitting in his office, wants to prove that his
        car will start when he leaves work to go home.  To prove this, he
        must assume that the car is in the same state in which he left it --
                -- hasn't been stolen
                -- gasoline hasn't vanished
                -- etc.
        In FOPC, John can't prove that he will be able to start his car,
        because the proof is based on an assumption that may be wrong.  We're
        not allowed to retract axioms in FOPC.

        In the real world, almost nothing is known for sure.  You want to be
        able to assume stuff and make inferences, and you want to be able to
        retract these inferences if you find out something to the contrary.

        Solution: NON-MONOTONIC LOGIC.

                Add a DEFAULT INFERENCE RULE:
                You may assume P if (not P) can't be proven.

                Keep a set of markers and pointers (DEPENDENCIES) so that the
                system can go back and retract inferences if the assumptions
                that they depend on are violated.

                The number of theorems in the system can now decrease as new
                knowledge comes in (thus "non-monotonic").

        Now John can assume that his car hasn't been stolen, as long as he
        doesn't know for sure (or can't infer for sure) that his car has been
        stolen.

%----------------------------------------------------------------------------

NON-DEDUCTIVE INFERENCES

DEDUCTIVE INFERENCE is "logically correct" or "provably correct".  But most
of the inferences we make every day are not of this type.

ABDUCTIVE INFERENCE: Conclusions are only plausibly true.

        Given:          q, p => q       sick(BILL), has-cancer(x) => sick(x)
                        ---------       ------------------------------------
        Infer/Assert:        p                     has-cancer(BILL)

        EXPLANATION, DIAGNOSIS, etc. are ABDUCTIVE.

INDUCTIVE INFERENCE: Given many instances of something, assume that the
generalized rule is true.  Not a "proof".

        If you see a hundred black ravens, you might assume that "all ravens
        are black".

AUTOEPISTEMIC INFERENCE:
        If I had a sister, I would know it.  Therefore, I don't have a sister.
        Have you ever shaken hands with Nixon?

NON-MONOTONIC INFERENCE: Conclusions are dependent on assumptions and may be
retracted when the assumptions are negated.  Since these assumptions are
often made by "default", this is also called DEFAULT INFERENCE.

        Will my car start today?  Yes (assuming there is gas in it).

%----------------------------------------------------------------------------

Copyright (c) Ashwin Ram, 1990-93
Assistant Professor, College of Computing
Georgia Institute of Technology, Atlanta, Georgia 30332-0280
E-mail: <ashwin@cc.gatech.edu>