Logica voor AI Defaults in Update Semantics

Logica voor AI
Defaults in Update
Semantics
22 jan ‘14
Frank Veltman
Thema
=
verwerken van zwakke
informatie in een
dyn. epi. setting
[email protected]
logicatwork.nl/lvai/
Journal of Phil. Logic, 25: 221-226, 1996.
Voor tentamen: §1-3, bonus: §4.
Redeneren met defaults
Redeneren met defaults
‘Klassieke Semantiek’
Betekenis van een zin φ, ||φ||, is
“dat wat hij oplegt aan de wereld”
(dat wat de waarheid van φ afdwingt).
Tweety is een vogel
—————————
Tweety kan vliegen
K(Tweety is een vogel) ∧ ¬K¬(Tweety kan vliegen)
——————————————————
B(Tweety kan vliegen)
… formalisering dankzij waarheidscondities (w ⊨ φ)
te specificeren … de betekenis is dan niks anders dan de
verzameling van ‘werelden’ waarin φ waar is:
!
|| φ || = {w | w ⊨ φ}
‘Klassieke Geldigheid’1
Een zin φ is een geldig gevolg van een aantal premissen
φ1,…,φn indien de waarheid van die premissen de waarheid
van φ afdwingen.
‘Dynamische Semantiek’
Betekenis van een zin φ,
φ
, is
“dat wat hij oplegt aan de toehoorder/ontvanger/lezer/…”
(hoe een toehoorder zijn kennistoestand aanpast om φ als
nieuwe informatie op te nemen ).
Betekenis van een zin φ is
“verandering die φ als update bewerkstelligt”
Belangrijke eis (hier): determinisme van updates!
φ1,…,φn ⊨ φ
!
‘Update Semantiek’
φ
= {⟨s,t⟩ | met t een min. wijziging/verandering van inf.
toestand s z.d.d. t de informatie φ bevat}
Notatie
s[φ] = toestand die ontstaat door s met φ ‘up-te-daten’
!
||φ1|| ⋂ … ⋂ ||φn|| ⊆ ||φ||
Indien in inf. toestand s φ geen verandering forceert, dan was
φ kennelijk al bekend. We zeggen dan dat s φ accepteert.
1. Eng: entailment (in LiA: valid inference).
Acceptatie (dyn. waarheid)
Indien in inf. toestand s φ geen verandering
forceert, dan was φ kennelijk al bekend. We
zeggen dan dat s φ accepteert:
Notatie
s⊩φ
Dyn. betekenis is context-afhankelijk!
Een text van zinnen φ1,…,φn kan nu
geïnterpreteerd worden als de verandering die het
forceert indien die zinnen (in de gegeven
volgorde) binnenkomen:
Dyn. gevolg is context-afhankelijk!
Een zin φ is een dynamisch gevolg (⊩)van een
text van zinnen φ1,…,φn indien φ geaccepteerd
wordt nadat de updates [φ1],…,[φn] in de gegeven
volgorde zijn doorgevoerd.
Veltman gebruikt twee definities:
s[φ1]…[φn]
φ1,…,φn ⊩2 φ
Definitie
s ⊩ φ s[φ] = s.
s[φ1]…[φn] ⊩ φ voor alle inf. toest. s
φ1,…,φn ⊩1 φ
0[φ1]…[φn] ⊩ φ
waarbij 0 de minimale inf. toest is.
N.B. Veltman definieert ook nog ⊩3, maar die is verder in het artikel niet van belang.
Ordening van inf. toestanden
In het artikel is ook de ordening van informatietoestanden belangrijk: s ≤ t betekent dat t
minstens zo informatief is als s.
s<t
Notatie
s ≤ t & niet t ≤ s.
Voorbeeld 1 “Might”
Voorbeeld 1 “Might”
Taal
=
L1A
=
prop. log. taal (L0A)
+
{might φ | φ ∈ L0A}
Inf. toestand
=
A-toestanden
=
PPA
=
Verzamelingen van deelverzameling van de
atomaire proposities (propositieletters).
N.B. ≤ is altijd een pre-orde = een refl. trans. relatie (niet per
se anti-symmetrisch … verschillende informatie toestanden
kunnen evt even informatief zijn.)
Voorbeeld 1 “Might”
Voorbeeld 1 “Might”
Updates
s≤t
Voorbeeld 1 “Might”
•
•
t⊆s
(toename van zekerheid)
•
•
Ad1: W = PA = verzameling van verzameling van atomen.
Ad2: Veltman gebruikt Griekse letters σ, τ voor informatie-toestanden voor dit voorbeeld.
Ad3: ~ is complement operatie: σ ~ τ = {A | A ∈ σ, A ∉ τ} .
Ad4: 1 = ∅ is de absurde informatie-toestand.
Toestanden niks anders dan S5-modellen, met 1 = ∅
toegevoegd.
0 = S5-model met PA als werelden en valuatie-functie
V: Vw(p) = 1 p ∈ w.
Voor prop. logische formules φ: s[φ] = {w ∈ s | w ⊨ φ},
eliminatie van ¬φ-werelden uit s.
Voor might-formules is een update een ‘test’: s blijft
ongemoeid indien s een φ-wereld bevat, en reduceert
tot de abs. toestand 1 als s geen φ-wereld bevat.
Exceptions and Expectations (§3)
Exceptions and Expectations (§3)
Exceptions and Expectations (§3)
Doel = modelleren van zwakke informatie op grond van
verwachtingen/vooroordelen (defaults)
Taal
=
L0A ⋃ {normally φ | φ ∈ L0A} ⋃ {presumably φ | φ ∈ L0A}
Harde
feiten
Zwakke
info
(defaults)
Test van zwakke
info
(defaults)
Exceptions and Expectations (§3)
De normale werelden nε in een verwachtingspatroon
ε zijn de minimale werelden volgens dat patroon.
Een verwachtingspatroon ε is nodig om default-informatie te
modelleren. Zo’n patroon vertelt dat indien v <ε w dat w een
uitzonderlijkere wereld is dan v.
Exceptions and Expectations (§3)
!
Incoherente patronen zijn patronen zonder deze
minimale/normale werelden.
Exceptions and Expectations (§3)
0 = ∅, 1 = {p},
2= {q}, 3 = {p,q}
4 = {r} 5 = {p,r}
6 = {q,r} 7 = {p,q,r}
Verwachtingspatroon loopt van links naar rechts. Werelden 0 en 5 zijn de
normale werelden.
!
De stippellijn geeft inf. toestand mbt harde informatie aan, dwz {3,4,6}
zijn de enige overgebleven werelden.
!
Waar het nu om gaat (igv zwakke informatie) zijn de `normaalste’
werelden van die werelden die nog mogelijk zijn: {3,6}. Dit worden de
optimale werelden genoemd in het artikel.
Zwakke info (defaults) e wordt ondersteunt door
een verwachtingspatroon ε indien verfijning van ε
met info e het patroon ε intact laat.
Verfijning ve verwachtingspatroon staat voor meer onderscheid op uitzonderlijkheid van
werelden (… het aanleren van vooroordelen …)
!
Verfijning ve patroon ε met info e, ε◦e, is het wegnemen van paren die een wereld die niet
overeenkomen met e als `normaler’ beoordelen dan die wel overeenkomen met e. Dit is de
manier om zwakke informatie te verwerken.
Exceptions and Expectations (§3)
Exceptions and Expectations (§3)
Exceptions and Expectations (§3)
harde upd. = eliminatie
zachte upd. = verfijning
testen v. zwakke info
Toestanden zijn nu paren, verz. werelden (harde info) en
verwachtingspatroon (zwakke info). Updates vinden nu plaats via
eliminatie van onzekerheden/werelden enerzijds (harde updates) en
verfijningen van het verwachtingspatroon anderzijds (zachte updates).
Exceptions and Expectations (§3)
Conditional Expectations (§4)
Conditional Expectations (§4)
default rules
!
Taal
=
L3A
=
L0A + {φ⤳ψ | φ,ψ ∈ L0A} + {presumably φ | φ ∈ L0A}
0 = ∅, 1 = {p},
2= {q}, 3 = {p,q}
0 = ∅, 1 = {p},
2= {q}, 3 = {p,q}
Zwakke
cond. info
(default rules)
Test van zwakke info
(ad: werkt niet als in §3)
Conditional Expectations (§4)
… het verlanglijstje …
Add: normally p = (p ∨ ¬p) ⤳ p.

Download Report