Strictness of FOL
To reason from P(a) to Q(a), need either • factsaboutaitself
• universals,e.g.∀x(P(x)⊃Q(x))
– something that applies to all instances – all or nothing!
But most of what we learn about the world is in terms of generics
• e.g., encyclopedia entries for ferris wheels, violins, turtles, wildflowers
Properties are not strict for all instances, because
• genetic/manufacturingvarieties – early ferris wheels
• borderlinecases – toy violins
• imaginedcases – flying turtles
• casesinexceptionalcircumstances – dried wildflowers
• …
KR & R! © Brachman & Levesque 2005 Defaults
Generics vs. Universals
4 !Violins have four strings !! vs.
5 !All violins have four strings !! vs.
? !All violins that are not E1 or E2 or … have !four strings
! (exceptions usually cannot be enumerated) !
Similarly, for general properties of individuals ! !Alexanderthegreat:ruthlessness
! !Ecuador: exports
! !pneumonia: treatment ! !
Goal: beabletosayaPisaQingeneral, but not necessarily
! reasonable to conclude Q(a) given P(a) unless there is a good reason not to
!
Here: qualitative version (no numbers) !
KR & R! © Brachman & Levesque 2005 Defaults
Varieties of defaults
General statements
• statistical: Most P’s are Q’s.
People living in Quebec speak French.
• normal:! All normal P’s are Q’s. Polar bears are white.
• prototypical: The prototypical P is a Q. Owls hunt at night.
Representational
• conversational: Unless I tell you otherwise, a P is a Q.
– default slot values in frames
– disjointness in IS-A hierarchy (sometimes) – closed-world assumption (below)
Epistemic rationales
• familiarity: If a P was not a Q, you would know it.
– an older brother
– very unusual individual, situation or event • group confidence: All known P’s are Q’s.
! NP-hard problems unsolvable in poly time.
Persistence rationale
• inertia: APisaQifitusedtobeaQ.
– colours of objects
– locations of parked cars (for a while!)
KR & R! © Brachman & Levesque 2005 Defaults
Closed-world assumption
Reiter’s observation:
! There are usually many more -ve facts than +ve facts!
AirLine Example: flight guide provides
! DirectConnect(cleveland,toronto) !DirectConnect(toronto,northBay) DirectConnect(toronto,winnipeg) …
! but not: ¬DirectConnect(cleveland,northBay) Conversational default, called CWA:
! only +ve facts will be given, relative to some vocabulary
But note: KB ⎥≠ -ve facts
! would have to answer: “I don’t know”
Proposal: a new version of entailment
! KB ⎥=c α iff KB ∪Negs ⎥= α a common pattern:
KB‘= KB ∪Δ ! Negs = {¬p | p ground atomic and KB⎥≠ p}
! Note: relation to negation as failure Gives: KB ⎥=c +ve facts and -ve facts
‘ ‘where
KR & R! © Brachman & Levesque 2005 Defaults
Properties of CWA
For every sentence α without quantifiers, either KB ⎥=c α or KB ⎥=c ¬α (or both)
Why? Inductive argument:
• immediatelytrueforatomicsentences
• push¬in, e.g. KB⎥=¬¬α iff KB⎥=α
• KB⎥= (α∧β) iff KB⎥=αand KB⎥=β
• Say KB⎥≠c (α∨β).
ThenKB⎥≠c αand KB⎥≠c β.
So by induction, KB ⎥=c ¬α and KB ⎥=c ¬β. Thus, KB⎥=c ¬(α∨β).
CWA is an assumption about complete
knowledge
! never any unknowns, relative to vocabulary
In general, a KB has incomplete knowledge, ! e.g., if KB = (p∨ q), then KB ⎥= (p∨ q), but
KB⎥≠ p, KB⎥≠ ¬p, KB⎥≠ q, and KB⎥≠ ¬q But with CWA, always have:
! If KB⎥=c (α∨β),then KB⎥=c αor KB⎥=c β ! similar argument to above
KR & R! © Brachman & Levesque 2005 Defaults
Query evaluation
With CWA can reduce queries (without quantifiers) recursively to atomic case:
! !KB⎥=c (α∧β) iff KB⎥=c α and KB⎥=c β
! !KB⎥=c(α∨β)iffKB⎥=cαor KB⎥=cβ
‘ ‘KB⎥=c¬(α∧β)iffKB⎥=c¬αor KB⎥=c¬β
‘ ‘KB ⎥=c ¬(α∨β) iff KB ⎥=c ¬α and KB ⎥=c ¬β
‘ ‘KB⎥=c ¬¬α iff KB⎥=c α
! reduces to: KB ⎥=c λ, where λ is a literal
If KB ∪ Negs is consistent, get
! !KB⎥=c ¬α iff KB⎥≠c α
! reduces to: KB ⎥=c p, where p is atomic
If atomic wffs stored as a table, deciding whether or not KB ⎥=c α is like DB-retrieval:
• reducequerytosetofatomicqueries • solveatomicqueriesbytablelookup
Different from ordinary logic reasoning ! e.g. no reasoning by cases
‘ see “vivid reasoning” (discussed later)
KR & R! © Brachman & Levesque 2005 Defaults
Consistency
If KB is set of atoms, then KB ∪ Negs is always consistent
Also works if KB has conjunctions and if KB has -ve disjunctions
! If KB contains (¬p ∨ ¬q). Add both ¬p, ¬q. Problem when KB ⎥= (α ∨ β), but KB⎥≠ α and
KB⎥≠ β
‘ e.g. KB = (p∨q) Negs = {¬p,¬q}
‘ ‘so KB ∪ Negs is inconsistent
! !andforeveryα,KB⎥=cα!
Solution: only apply CWA to atoms that are “uncontroversial”
! One approach: GCWA
! Negs ={¬p | If KB⎥=(p∨q1 ∨…∨qn)
! ! ! then KB ⎥= (q1 ∨… ∨qn)}
! When KB is consistent, get:
– KB ∪Negs consistent
– everything derivable is also derivable by CWA
KR & R! © Brachman & Levesque 2005 Defaults
Quantifiers and Equality
So far, results do not extend to wffs with quantifiers
• can have KB ⎥≠c ∀x.α and KB ⎥≠c ¬∀x.α
• e.g. just because for every term t, we have
!! KB ⎥=c ¬DirectConnect(myHome, t) !does not mean that
! KB ⎥=c ∀x[¬DirectConnect(myHome, x)]
But may want to treat KB as providing complete information about what individuals exist
Define: KB ⎥=c2 α iff KB ∪Negs ∪Dc ∪Un ⎥= α
!
!
!
! Negs is as before
!Dc isdomainclosure:∀x[x=c1 ∨…∨x=cn],
!Un isuniquenames: (ci ≠cj), fori≠j ! ! where the ci are all the constants
! appearing in KB (assumed finite)
KB ⎥=c2 ∃x.α iff KB ⎥=c2 α[x/c],
Get:!
‘ ‘ ‘ ‘ for some c appearing in the KB
!
‘
!
KB ⎥=c2 ∀x.α iff KB ⎥=c2 α[x/c],
‘ ‘ ‘ forallcappearingintheKB
KB ⎥=c2 (c = d) iff c and d are the same constant
KR & R! © Brachman & Levesque 2005 Defaults
Non-monotonicity
Ordinary entailment is monotonic
! If KB ⎥= α,then KB*⎥= α, for any KB ⊆KB*
But CWA entailment is not monotonic
! CanhaveKB⎥=cα,KB⊆KB’,butKB’⎥≠cα
! e.g.!{p} ⎥=c ¬q, but {p, q} ⎥≠c ¬q !
Suggests study of non-monotonic reasoning
• startwithexplicitbeliefs
• generateimplicitbeliefsnon-monotonically, taking defaults into account
! e.g. Birds fly.
• implicitbeliefsmaynotbeuniquelydetermined ! vs. monotonic case: {α | KB |= α}
!
Will consider three approaches:
• circumscription
! interpretations that minimize abnormality
• defaultlogic
! KB as facts + default rules of inference
• autoepistemiclogic
! facts that refer to what is/is not believed
KR & R! © Brachman & Levesque 2005 Defaults
Minimizing abnormality
Idea:
! CWA makes the extension of all predicates as small as possible
! by adding negated literals
! Generalize: make extension of selected predicates as small as possible
! Ab predicates used to talk about defaults
Example:
! ∀x[Bird(x) ∧¬Ab(x) ⊃Fly(x)]
! All birds that are normal fly
! Bird(chilly), ¬Fly(chilly), Bird(tweety), (chilly ≠ tweety)
Would like Fly(tweety), but KB |≠ Fly(tweety) ! because there is an interp I where
!Φ(tweety) ∈ Φ(Ab)
Solution: consider only interps where Φ(Ab)
is as small as possible, relative to KB ! for example: need Φ(chilly) ∈ Φ(Ab)
Generalizes to many Abi predicates
KR & R! © Brachman & Levesque 2005 Defaults
Minimal Entailment
Given two interps over the same domain, I1 and I2 ! I1 ≤ I2 iff Φ1(Ab) ⊆ Φ2(Ab)’
! for every Ab predicate
! I1