CSCE 420 Lecture 21

« previous | Thursday, April 4, 2013 | next »

Defaults and Exceptions: Nonmonotonic Logic

FOL doesn't support exceptions to universally quantified rules

monotonicity: if you add sentences to KB, everything that was previously entailed is still entailed.

Default Logic

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1, \ldots, P_m / J_1, \ldots, J_m \rightarrow C}

J's represent:

"It is consistent to believe"
"If not provably false"
"If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_i} is false, then rule is blocked"
"Unless there is evidence to the contrary"

Bird(x) / Flies(x) → Flies(x)
Bird(tweety)
Bird(opus)
¬Flies(opus)

"Fixed-point semantics"

Start with a minimal model
elaborate and add consequences

KB with exceptions and contradictions is still allowed to be consistent

Circumscription

Usually, we write

∀x bird(x) → flies(x)
∀y dog(y) → barks(x)

But we add "abnormal predicates" that allows for exceptions:

∀x bird(x) ∧ ¬abnormal₁(x) → flies(x)
∀y dog(y) ∧ ¬abnormal₂(y) → barks(x)

"preferred" models are those that minimize abnormal assumptions:

bird(tweety)
bird(opus)
¬flies(opus)
dog(fido)
dog(snoopy)
¬barks(snoopy)

m1:
    abnormal₁(tweety)
    abnormal₁(opus)
    abnormal₂(fido)
    abnormal₂(snoopy)

m2:
    abnormal₁(opus)
    abnormal₂(snoopy)
    flies(tweety)
    barks(fido)

m2 has the fewest abnormal assumptions

Truth-Maintenance Systems

Assert and retract information (facts, observations, perceptions)
Keep track of dependencies
Graph structure: map facts to derived inferences (similar to a proof tree)
When a fact changes, consequences are propagated (belief updating, theory revision)

Semantic Networks

Visual (graph) representation of knowledge:

Figure 1. Semantic Network representing John and Mary

Mary is John's sister (Figure 1)

Nodes:

a
b
Mary
John
female persons
male persons
person

Edges

(a, Mary, name)
(b, John, name)
(a, b, sister)
(a, female persons, member)
(b, male persons, member)
(female persons, person, subset)
(male persons, person, subset)

Figure 2. 3-way gives event node.

How to represent three-argument predicates (Figure 2)?

gives(John, Mary, present):

added nodes: c, presents
added edges: (c, presents, member)
event node: giving event
- receiver: a
- giver: b
- object: c

Figure 3. Procedural lookup for How many legs does Mary have?

Semantic Networks handle defaults by inheritance, and handle exceptions by a "procedural lookup mechanism"

How many legs does Mary have? (Figure 3)

find Mary
follow (a, Mary, name)
follow (a, female persons, member)
follow (female persons, person, subset)
identify (person, 2, num_legs)

Figure 4. Procedural short-circuit lookup for How many legs does John have?

Procedural lookup: suppose John only has one leg; short-circuit the default lookup operation by defining (b, 1, num_legs) (Figure 4)

Problem: semantic networks don't scale well to real-world applications

Back to Prolog

Cannot directly assert negated facts

Closed-world assumption: everything not explicitly asserted is assumed to be false

took(joe, csce311). took(julie, csce315). lower_level(X) :- \+ took(X, 315).

This is enough to prove that Joe did not take CSCE 315

Intervally, Prolog handles Negation as Failure:

If top goal on stack is a negative literal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neg \phi} , then
Invoke side-call backchaining on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} , trying to prove it.
If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} fails, then original proof can proceed
Otherwise if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} succeeds, then original proof must back-track

Example program:

bird(tweety). penguin(opus).

bird(X) :- penguin(X).

flies(X) :- bird(X), \+ penguin(X).