Parte 1: Ragionamento non monotono

(1)

Console, Botta - Dip. Informatica, Univ. Torino Non-monotonic reasoning 1

Non-monotonic reasoning

• Logica classica

– modella alcuni aspetti del modo di ragionare umano – ma richiede

• conoscenza completa • conoscenza consistente

• conoscenza “fissa” che non varia nel tempo

• Ragionamento in presenza di

– incompletezza – inconsistenza – conoscenza dinamica

è comune in molte attività umane

– si fanno assunzioni su conoscenza mancante

– si gestiscono inconsistenze rivedendo le proprie conoscenze (assunzioni) – si gestisce il cambiamento della conoscenza nel tempo

• Necessità di “logiche” per gestire questi aspetti

• Logica classica è monotona

– data teoria T tale per cui T |= p

– allora per qualunque A si ha che T ∪ A |= p quindi

– la conoscenza può solo aumentare

– in caso di inconsistenza la deduzione si banalizza – in caso di incompletezza non si arriva a conclusioni

• Necessità di ragionare in situazioni più complesse

– Comune avere a che fare con

• incompletezza: si fanno assunzioni

• inconsistenza: si rivede la propria conoscenza • conoscenza che si modifica nel tempo

(2)

• Un esempio

– A, B e C sono i sospettati per un delitto

– A ha un alibi perché risulta nel registro di un albergo in una città diversa – B ha un alibi perché era in visita da suo cugino

– C dice di essere stato ad una gara di sci Dalle informazioni possiamo concludere che (1) A non ha commesso il delitto

(2) B non ha commesso il delitto

(3) almeno uno tra A, B e C è il colpevole (ci risultano gli unici con movente) oss: (3) è stato dedotto in assenza di informazione contraria

ora veniamo a sapere che

(4) C è stato ripreso in immagini televisive della gara quindi

(5) C non ha commesso il delitto ma (1), (2), (3) e (5) sono inconsistenti

devo modificare le mie credenze: cugino di B ha mentito, oppure registro dell’albergo corrotto oppure altri possibili con movente

Esempi di forme di ragionamento comuni

• Ragionamento in assenza di evidenza contraria

– Ho una lista di persone presenti sulla scena del delitto – A non compare nella lista

– concludo che A non era presente

– in futuro potrei avere altra informazione che mi porterà a concludere che invece A era presente

Assunzione di mondo chiuso

• Ragionamento per default

– So che gli uccelli in generale volano – Tweety è un uccello

– concludo che Tweety vola

– in futuro potrei scoprire che Tweety è un pinguino e che i pinguini sono uccelli anormali che non volano

(3)

• Minimizzazione

– Azione A sposta un blocco da una posizione X a posizione Y – B è un blocco rosso in X

– Se eseguo A su B, avrò un blocco rosso in Y

– In realtà azione non mi diceva nulla sul fatto che B rimane dello stesso colore ma è ragionevole assumerlo

minimizzo i cambiamenti non giustificati ma in futuro potrei dovermi ricredere

• Abduzione

– so che l’influenza produce febbre e mal di testa – osservo un paziente con febbre e mal di testa – concludo che ha l’influenza

Inferenza non corretta dal punto di vista della logica classica – spiegazione delle osservazioni a partire dalla teoria

– in futuro potrei venire a sapere che anche la polmonite produce febbre, influenza e brividi e venire a sapere che il paziente ha anche i brividi – dovrò rivedere la mia conclusione e dire che il paziente ha la polmonite

• Ragionamento ipotetico

– Se giro la chiave in una auto che ha la batteria, l’auto si avvia – A è un’auto

– assumo che abbia la batteria e deduco che si avvia se giro la chiave – se in futuro vedo che non si avvia dovrò rivedere le mie assunzioni

• Gestione di inconsistenze (collegato al caso precedente)

– Esempio della storia di delitti vista sopra – Esempio dell’automobile visto prima In generale

– faccio assunzioni

– uso conoscenza per inferire nuove informazioni – se ho una inconsistenza devo

• ritrattare alcune delle assunzioni • rivedere la conoscenza

(4)

Ragionamento non-monotono

• Caratteristiche comuni delle forme di inferenza discusse

– non corrette dal punto di vista della logica classica

– defeasible, ossia conclusioni che potrebbero dover essere riviste in presenza di nuove informazioni

– in altri termini

ragionamento non monotono

• data teoria T

• inferisco informazione p: T |-i- p

|-i- sta ad indicare che uso forma di inferenza “i” non classica • in presenza di nuova informazione p potrebbe non essere più inferibile, ossia

– data nuova informazione A T ∪ A |-i- p

– si devono definire forme di inferenza diverse da quella classica (“modus ponens”)

Alcuni esempi di applicazioni in AI

• Rappresentazione della conoscenza

Rappresentazioni strutturate (frame o reti semantiche) prevedono – concetti (frame, nodi)

– proprietà di concetti (slot, …) – ereditarietà

Solo a volte

– proprietà sono necessarie – ereditarietà è stretta

Può in molti casi essere interessante definire – proprietà per default

– ereditarietà con cancellazione Esempio

uccelli proprietà_per_default volare passeri ISA uccelli

(5)

• Planning (reasoning about action)

– descrizione delle azioni

• precondizioni • effetti

– tre seri problemi

• qualification problem

– definire in modo completo l’insieme delle precondizioni di una azione – ragionare facendo assunzioni su tali precondizioni

• frame problem

– definire in modo preciso cosa non cambia come effetto dell’azione – ragionare per default su tali effetti (es. minimizzazione effetti) • ramification problem

– definire in modo preciso in che modo le cose cambiano come effetto delle azioni

– Metodi logici classici di rappresentazione delle azioni non funzionano (vedremo in planning)

• rappresentazioni procedurali

• rappresentazione mediante logiche non classiche

• Azioni, tempo, cambiamento

• Diagnosi

– data una base di conoscenza che descrive il sistema da diagnosticare – dato un insieme di osservazioni (sintomi)

– trovare un insieme di guasti (malattie) che spiegano le osservazioni

Processo di ragionamento abduttivo

• Interpretazione più in generale

• Data e knowledge bases

– contengono informazioni su un certo dominio (miniworld)

– assunzione comune che ciò che non è scritto esplicitamente è falso (CWA) permette di dare risposte ma in modo non-monotono

• Problem solving costruttivo (es. scheduling, design, …)

– ragionamento basato su assunzioni

• es. si prova a fare assunzioni sullo scheduling di un insieme di azioni • si rivedono le assunzioni in caso di problemi o inconsistenze

• Ragionamento con e su agenti

– rappresentazione e gestione di belief multipli

(6)

• Nel seguito vedremo alcuni approcci al non-monotonic reasoning

– Approcci basati su modelli minimali

• Closed World Assumption • Completamento e circoscrizione

– Default Reasoning – Abduzione

• e discuteremo brevemente alcune applicazioni

– reti semantiche con ereditarietà – ragionamento su azioni – diagnosi e interpretazione

• vedremo quindi i truth maintenance system

Modelli minimali

• Dato un insieme T di formule logiche nel linguaggio L

– interpretazione: mapping tra i simboli di L e un dominio

• simboli di funzione interpretati su funzioni • simboli di predicato su relazioni

– modello: interpretazione che soddisfa T

• Modelli preferiti

– un approccio alla logica non-monotona consiste nel definire dei criteri di ordinamento tra modelli e limitarsi quindi solo ai modelli “ottimali” (“preferiti”) rispetto a tali criteri

– un criterio di ordinamento: numero di atomi che sono veri

• Modelli minimali: M minimale se non esiste un altro modello M’ più

piccolo di M (ossia in cui meno atomi sono veri)

• Usare modelli preferiti (minimali) per definire logiche non monotone

– intuizione: si considerano veri solo gli atomi che devono necessariamente essere veri

(7)

Closed World Assumption

• Una forma semplice di ragionamento non-monotono basata su

minimizzazione di modelli [Reiter, 78]

• Si assume vero solo ciò che deve essere vero; ogni altra cosa viene

assunta falsa

• Esempio

– database con indicazione delle città di residenza di un insieme di persone e delle persone che sono impiegate

abita(a,torino) impiegato(a) abita(b,torino)

abita(c,milano)

– molti modelli di questo insieme di formule

– secondo CWA si considerano vere solo le informazioni necessariamente vere (in questo caso quelle presenti nel database) e false tutte le altre

• impiegato(b) falso (in logica classica non potremmo concludere niente su tale fatto)

• abita(a,milano) falso

• Più in generale si deve considerare la chiusura deduttiva della teoria T

(e non solo gli atomi esplicitamente in T)

• Esempio

– T contiene le seguenti formule p(a), q(b), r(c), r(a) ∀X p(X) → q(X)

– modello minimale {p(a), q(a), q(b), r(a), r(c)} – per cui avremo che

• q(c) falso • r(b) falso

• Osservazione: in alcuni casi si possono avere più modelli minimali

– Esempio p(a)

∀X p(X) → q(X) ∨ r(X) – due modelli minimali

• M1 = {p(a), q(a)} • M2 = {p(a), r(a)}

(8)

• Regola di inferenza della closed world assumption

– assumere ¬P ogni volta che questo è consistente oppure da un punto di vista differente

– T |-cwa-¬P sse T |-/- P

• Una interpretazione della negazione diversa da quella della logica

classica

– negazione utilizzata in database

– negazione utilizzata nei linguaggi di programmazione logica

• utilizzano Negazione per fallimento • simile alla CWA

• più debole in quanto CWA non è computabile (T |-/- P è semi-decidibile) T |-NF-¬P sse ogni dimostrazione di P da T fallisce in modo finito • limitazione a clausole di Horn: garanzia di un unico modello minimale

• Esempio

∀X adulto(X) ∧ ¬impiegato(X) → disoccupato(X)

da adulto(a), impiegato(a), adulto(b) derivo disoccupato(b) – non corretto per logica classica

– defeasible (se vengo a sapere impiegato(b))

Completamento

• Modo alternativo per definire la stessa forma di ragionamento [Clark 78]

– data una teoria T (formata da clausole di Horn), definire una trasformazione sintattica Tc di T tale per cui i modelli di Tc coincidano con i modelli minimali di T

o

– l’inferenza classica su Tc coincida con l’inferenza sotto NF in T

o

– la negazione in Tc coincida con la negazione come fallimento in T

• Vantaggio: possibilità di usare logica classica

• Trasformazione sintattica

– intuitivamente: trasformare implicazioni in bi-implicazioni – più precisamente

date clausole di Horn

a1 → b(X), a2 → b(X), …, an → b(X) (con ai congiunzioni) costruire

(9)

• Esempio

p(a), q(b), r(c), r(a) ∀X p(X) → q(X) diventa ∀X (X=a) → p(X) ∀X (X=b) → q(X) ∀X p(X) → q(X) ∀X (X=a) → r(X) ∀X (X=c) → r(X) e quindi ∀X p(X) ↔ (X=a) ∀X q(X) ↔ (X=b ∨ p(X)) ∀X r(X) ↔ (X=a ∨ X=c)

– teoria trasformata ha un unico modello che coincide con il modello minimo della teoria di partenza

– da teoria trasformata posso concludere ¬q(c) o ¬ r(b) – OSS: funziona solo su clausole di Horn

Circumscription

• Un forma di minimizzazione più sofisticata

• Limitazioni di CWA

– opera in modo indipendente su ognuno dei predicati, senza considerare le interazioni

• es. p(a) ∨ p(b)

• da CWA si concludono ¬p(a) e ¬p(b) !!!

– va bene in applicazioni in cui si conoscono gli individui

• Limitazioni del completamento

– va bene solo su clausole di Horn

• Molte varianti della circoscrizione sono state definite

– [McCarthy, 80] – [McCarthy, 85] – [Lifschitz, 85]

• In ogni caso idea base è la stessa: aggiungere nuovi assiomi alla teoria

T in dipendenza dell’insieme di predicati che si vogliono minimizzare

(eventualmente in modo dipendente, o con priorità)

(10)

• Assiomi di circoscrizione

– tecnicamente complessi

– formule del secondo ordine che specificano per il predicato P da minimizzare che la sua estensione deve essere la più piccola consistente con la base di conoscenza

– permettono di minimizzare

• più predicati simultaneamente

• più predicati secondo una priorità (ad esempio, prima minimizzare un predicato P, poi tra i modelli minimi per P scegliere quelli minimi per un altro predicato Q)

• Esempio

– Data T con p(a) ∧ p(b), la circoscrizione di p in T produce l’assioma aggiuntivo∀X (p(X) → X=a ∨ X=b )

caso simile al completamento

– Data T con p(a) ∨ p(b), la circoscrizione di p in T produce l’assioma aggiuntivo ∀X (p(X) → X=a) ∨ ∀X (p(X) → X=b)

Default logic

• [Reiter 80]

• formalizza una delle più comuni forme di ragionamento non-monotono:

capacità di fare assunzioni o arrivare a conclusioni in assenza di evidenza

contraria (ossia per default)

• Default theory

– T: insieme di formule della logica classica – D: insieme di default, ossia regole del tipo

con il seguente significato

se A è vero e B è consistente allora concludi C Caso particolare: i default normali

se A è vero ed è consistente assumere B allora concludi B

C B A : B B A :

(11)

• Esempi

• Default sono regole di inferenza

– data teoria di default (T,D)

• deduzione in T permette di inferire nuova informazione

• default sono applicabili per inferire (in modo defeasible) altra informazione

• Estensione di una default theory (T,D)

insieme massimale consistente che si può ottenere applicando la

chiusura deduttiva in T e applicando regole di default

– equiv.: insieme massimale di default ground applicabili

– massimale: nessun default ultertiormente applicabile senza violare il vincolo di consistenza

• Oss: in generale (T,D) può avere più estensioni

• Oss: default sono visti come regole di inferenza, non come formule

della teoria logica

• A inferibile da (T,D) se A è in tutte le estensioni di (T,D)

– vedremo poi modifiche di questa definizione ) ( ) ( : ) ( X flies X flies X bird ) ( ) ( : ) ( X guasto X guasto X circuito ¬ ¬ ) ( ) ( : ) ( X flies X normal X bird

• Esempio

– Teoria logica T ∀X pinguino(X) → uccello(X) ∀X passero(X) → uccello(X) ∀X pinguino(X) → ¬vola(X) ∀X uccello(X) → animale(X)

uccello(a) pinguino(b) passero(c) – Default D

– Estensione

uccello(a), animale(a)

pinguino(b), uccello(b), animale(b) passero(c), uccello(c), animale(c)

primo default applicabile per a e c, inconsistente applicarlo per b vola(a), vola(c)

secondo default applicabile per tutti faUova(a), faUova(b), faUova(c)

) ( ) ( : ) ( X vola X vola X uccello ) ( ) ( : ) ( X faUova X faUova X uccello

(12)

• Esempio: estensioni multiple

– Teoria logica T

quacchero(a) repubblicano(a) – Default D

– Esstensioni

I due default si bloccano a vicenda: l’applicazione di uno rende inconsistente l’applicazione dell’altro

Due estensioni

• E1: quacchero(a), repubblicano(a), pacifista(a) • E2: quacchero(a), repubblicano(a), ¬pacifista(a) – Per cui non si può inferire nulla riguardo a pacifista(a)

) ( ) ( : ) ( X pacifista X pacifista X quacchero ) ( ) ( : ) ( X pacifista X pacifista X no repubblica ¬ ¬

Inheritance networks

• Importante applicazione del ragionamento per default (e della default

logic, con variazioni)

• rappresentazioni strutturate di gerarchie di classi con proprietà

– in molti linguaggi solo proprietà necessarie che vengono ereditate – fondamentale poter rappresentare proprietà per default che possono essere

cancellate in sottoclassi (ereditarietà con cancellazione)

• Esempio

– uccelli, pinguini e volare visto prima

• Notazione grafica

uccello pinguino passero faUova animale vola default (defeasible) cancellazione nondeafult

(13)

• Consideriamo il caso con solo archi di default

p q (p ISA q) p q (p IS NOT A q) a q (a inst of q) a q (a NOT inst of q)

• Simili a default alla Reiter

q q p : q q p ¬ ¬ :

• Due forme di inferenza di base

p2 ... pN q

p1 p1 ISA q

p2 ... pN q

p1 p1 IS NOT A q

• Vari tipi di gerarchie

– ereditarietà singola VS ereditarietà multipla – cancellazione VS non cancellazione

• Caso interessante: ereditarietà multipla con cancellazione

• Problema: ambiguità:

– stesso problema di estensioni multiple della default logic pacifista

quacchero repubblicano nixon

– In alcuni casi può essere interessante selezionare solo alcune estensioni come plausibili (solo alcune inferenze)

– quindi avere un criterio di preferenza tra le estensioni – Esempio

uccello vola pinguino

– E1: pinguino vola – E2: pinguino non vola E2 è una inferenza da preferirsi

(14)

• Una regola: effettuare overriding: link diretti da una classe fanno

overriding di quelli ereditati

– ad esempio pinguino non vola per overriding della proprietà di volare della classe degli uccelli

• Una prima soluzione: inferenze basate sulla lunghezza dei cammini

– le inferenze su cammini più corti fanno overriding su quelle su cammini più lunghi

– risolve il caso dei pinguini

– non funziona in altri casi, ad esempio

grigio elefante

elefanteIndiano clyde

– Vorrei concludere che clyde non è grigio (proprietà della sottoclasse che fa overriding di quella della classe

– invece si hanno due inferenze plausibili

• Una soluzione alternativa: il concetto di distanza inferenziale

– rappresenta la preferenza tra estensioni che si vuole avere intuitivamente (vedi esempi prima)

– possono comunque rimanere estensioni multiple (vedi il caso del Nixon diamond)

• Inferenza credulous VS inferenza skeptical

Due forme di inferenza per affrontare il caso di estensioni multiple

– skeptical: rifiuto di trarre conclusioni in caso di ambiguità

• 1 sola estensione

– credulous: cercare di concludere il più cose possibile

• estensioni multiple e conclusioni ambigue

– Osservazione: la estensione di inferenza skeptical è diversa (è meno forte -restrittivo) dalla intersezione delle estensioni di inferenza credulous:

B P ... A fa preemption su C P ... A se C ... B

(15)

– Esempi

pacifista

• Skeptical: quacchero, repubblicano • Credulous: 2 estensioni

– repubblicano, quacchero, pacifista – repubblicano, quacchero, non pacifista

pacifista

anti-militarista

tifoso di calcio

• Skeptical: non concludendo nulla su pacifista concludo che Nixon è non antimilitarista (essendo un tifoso di calcio)

• non antimilatrista non è in tutte le estensioni

uomo

marine cappellano george

bevitore di birra • Due estensioni

– sulla destra cappellano IS NOT a bevitore di birra fa preemption su uomo IS A bevitore di birra – sulla sinistra nessuna preemption

• Il caso di archi di ereditarietà stretti

– simile ma archi stretti portano a inferenze non-defeasible su cui non si possono generare estensioni alternative e con cui i default devono essere consistenti

– Esempio

– Si può concludere che

• nixon è molto religioso (il fatto che è repubblicano non può generare estensioni multiple perchè l’altro arco è stretto)

• sono tutti motivati politicamente? … dipende dal tipo di inferenza • ... pacifista quacchero repubblicano nixon motivato politicamente molto religioso tom reagan

(16)

Reasoning about action e teoria del cambiamento

• Problema:

– Rappresentazione di azioni e dei loro effetti (ad esempio per un sistema di pianificazione)

– Ragionamento sulle azioni

• predizione degli effetti di insiemi di azioni

• pianificazione della sequenza di azioni per ottenere un obiettivo • interpretazione: quali azioni possono aver portato ad una data situazione

• Primo problema: il concetto di stato e la sua rappresentazione

– rappresentazione della situazione in cui si trova la parte del mondo che si sta modellando

– varie soluzioni possibili

– una soluzione usata frequentemente (e utile per analizzare i problemi): il

situation calculus

• Esempio rappresentare che in stato s il blocco a è sopra al blocco b – on(a,b,s)

– con reificazione. holds(on(a,b),s)

prendono il nome di fluent

• Secondo problema. La rappresentazione delle azioni

– azione = trasformazione di stato

– rappresentazione: nuovo stato come funzione dell’azione

• Esempio: azione che sposta un blocco B da posizione X a posizione Y nello stato S produce il nuovo stato S’= move(B, X, Y, S)

– Qualification problem: come rappresentare (tutte) le precondizioni di una azione

• in generale una azione può avere infinite precondizioni, ossia infinite situazioni in cui può fallire

• impossibile rappresentarle tutte: alcune anche difficili da prevedere

Una soluzione: usare logiche non standard

• precondizione generica • effetto della azione come default • inferenza defeasible

Esempio

• azione che sposta un blocco B da posizione X a posizione Y

– on(B, X, S) ∧¬ab(move(B, X, Y, S)) → on(B, Y, move(B, X, Y, S)) – holds(on(B, X),S) ∧¬ab(move(B, X, Y, S))

(17)

• Terzo problema: Frame problem, ossia come rappresentare gli effetti di

una azione

– azione modifica alcuni fluent

– come rappresentare il fatto che molti altri restano invariati

• Esempio se bianco(X,S) allora sarà anche bianco(X,move(X, Y, S))

– Frame axioms: specificano cosa non cambia

– anche in questo caso è opportuna una rappresentazione mediante default

• in generale molte cose non cambiano

• salvo sitazioni eccezionali (ad esempio nello spostamento sono passato sotto uno spruzzatore di vernice rossa)

– Varie soluzioni dal punto di vista tecnico – Esempio

holds(p(X),S) ∧¬ab(p(X), action1(S)) → holds(p(X), action1(S))

• Uso di logiche non monotone porta a problemi

– estensioni multiple di cui alcune non desiderate

• varie soluzioni, analizzeremo per il problema della predizione (il più

studiato); in altri problemi più critico (vedremo planning e abduzione)

• Un esempio famoso: lo Yale Shooting Problem

– esempio per mettere in evidenza i problemi legati al frame problem – istante iniziale:

• fucile scarico e tacchino vivo alive(fred) (¬dead(fred)) unloaded(gun) (¬load(gun))

– descrizione azioni (“default” in una qualche logica non monotona) • ¬ab(load(X,S)) → holds(loaded(X), load(X,S)))

• ¬ab(shoot(X,S)) → holds(dead(X), shoot(X,S))) • wait

– frame axioms (altri “default”)

• azione wait non cambia nulla

– holds(loaded(X),S) ∧¬ab(loaded(X), wait(S)) → holds(loaded(X), wait(S)) • azione load non cambia alive

– sequenza di azioni:

• t2= load(gun,t1), • t3= wait(t2) • t4=shoot(fred,t3)

(18)

• Due modi di applicare i frame axioms, ossia

Due estensioni nella formulazione del problema mediante logiche non

monotone

– fred è morto in t4

• fucile è carico in t2

• applicando frame axiom rimane carico in t3 e fred è vivo in t3 • quindi sparando fred rimane ucciso

– fred è vivo in t4

• applico frame axiom più volte per alive

• quindi deve essere abnormal che il fucile rimanga carico tra load e shoot

• varie soluzioni al problema

– minimizzazione cronologica: le cose anormali avvengono “il più tradi possibile”, questo porta a preferire estensione in cui fred muore

• controindicazione per altri problemi es. stolen car problem

– parcheggio auto

– azione di aspettare lascia l’auto dove è – azione furto fa sparire auto

– se non trovo auto concludo che è stata rubata all’ultimo momento

– Soluzioni basate sull’uso di negazione per fallimento invece di logiche di deafult o circoscrizione

• soluzione naturale del problema

• semantica chiara solo per alcune classi di formule (clausole o clausole di Horn)

– Approcci non esclusivamente logici

• rappresentazione della azioni non in termini logici • vedremo in dettaglio nel planning

(19)

Abduzione

• Abduzione: inferenza per trovare la “migliore spiegazione” per un

insieme di osservazioni, data una teoria

– forma comune di inferenza in molte attività umane

– fondamentale in molte attività di problem solving, ad esempio: interpretazione, diagnosi, ma anche pianificazione, comprensione del linguaggio, apprendimento, …

– studiata in campo filosofico sin dal secolo scorso

• dal punto di vista logico

– deduzione: modus ponens – abduzione:

• A come spiegazione di B, data la teoria che A→ B

• inferenza non corretta dal punto di vista della logica classica (non truth-preserving)

– Osservazione: abduzione e induzione sono due forme di inferenza diverse (anche se spesso c’è confusione)

B A B A → A B B A →

• Più in generale, una definizione:

– data una teoria T (insieme di formule logiche)

– data una osservazione OBS (insieme di atomi ground - si può generalizzare al caso non ground) da spiegare

– una spiegazione E è un insieme di atomi ground tale per cui

• T ∪ E consistente • T ∪ E |— OBS

– spesso si richiede che E abbia altre proprietà che lo rendono una spiegazione interessante

• linguaggio predefinito (insieme dei simboli abducibili)

• primitivo (ossia contenga solo atomi non spiegabili da altri atomi) • minimale (non ridondante)

• minima cardinalità • costo minimo • …..

– Osservazione:

• alcune di queste condizioni in contrasto • può dipendere da applicazione

(20)

• Esempio

– T = {a → b, e → b , b ∧ c →d, e → f } – OBS = {d} – spiegazioni • E1 = {a, c} • E2 = {e, c}

• Abduzione e negazione nelle osservazioni

– OBS può contenere osservazioni negative

• esempio OBS1 = {d, ¬f }

– Solitamente trattate come negazione per fallimento

• T ∪ E consistente • T ∪ E |-NF- OBS

Nell’esempio

• E1 = {a, c}

• Abduzione e negazione nella teoria

– analogamente viene trattata come negazione per fallimento

• OSS: difficile fornire teorie per dare spiegazioni di eventi negati

(problema simile a quello della qualificazione)

Esempio

piove innaffiatore acceso

strada bagnata erba bagnata acqua nel tubo scarpe bagnate erba luccicante

Esempi di spiegazioni non ridondanti

• OBS = {erba luccicante}

– E1 ={piove} E2 ={innaffiatore acceso}

• OBS = {scarpe bagnate, acqua nel tubo}

– E1 ={innaffiatore acceso}

• OBS = {scarpe bagnate, ¬acqua nel tubo}

– E1 ={piove} E2={scarpe lavate}

• OBS = {scarpe bagnate, ¬strada bagnata}

– E1 ={innaffiatore acceso} E2={scarpe lavate}

(21)

• Relazione tra abduzione e deduzione

– intuitivamente abduzione corrisponde a invertire le implicazioni in una teoria deduttiva

– più precisamente si può dimostrare che

• siano E1, E2, … En le spiegazioni abduttive di OBS da T • allora si ha che, dato il completamento TC di T

TC ∪ OBS | E1 ∨ E2 ∨ … ∨ En – Esempio • T = {a → b, e → b , b ∧ c →d, e → f } • TC = {a ∨ e ↔ b , b ∧ c ↔ d, e ↔ f } • OBS = {d } – da TC ∪ OBS | b ∧ c ≡ (a ∨ e) ∧ c ≡ (a ∧ c) ∨ (e ∧ c) • OBS = {d, ¬f }

– da TC ∪ OBS | b ∧ c ∧ ¬e ≡ (a ∨ e) ∧ c ∧ ¬e ≡ (a ∧ c ∧ ¬e )

• Abduzione è una forma di inferenza defeasible

– basata su assunzione di completezza delle “cause”

Applicazioni del ragionamento abduttivo

• Diagnosi (vedremo più in dettaglio più avanti)

– abducibili = guasti – osservazioni = sintomi

– teoria: modello che collega i guasti (cause) alle loro conseguenze – Esempio

• OBS = {luci spente}

– E1 = {batteria scarica } E2 = {lampadina fluminata } • OBS = {luci spente, auto non parte}

– E1 = {batteria scarica }

• Pianificazione

– abducibili = azioni – osservazioni = goal

– teoria: modello che descrive gli effetti delle azioni batteria scarica

auto non parte luci spente lampadina fulminata

(22)

• Interpretazione

– abducibili = ipotesi

– osservazioni = fatti da interpretare

– teoria: modello che descrive relazioni tra le ipotesi e le loro conseguenze Esempio: interpretazione di immagini

r1

r2 c1

c2

– abducibili = {land(X), river(X), water(X), road(X), shore(X)}

– teoria: relazioni tra abducibili (caratteristiche geografiche) e forme geometriche Esempi

• river(X) ∧ river(Y) → ¬cross(X,Y) • river(X) ∨ road(X) ∨ shore(X) → linear(X)

– osservazioni: caratteristiche geometriche dell’immagine

– In questo modo le spiegazioni abducubli corrispondono a interpretazioni delle immagini

• Update di viste in basi di dati logiche (e relazionali)

– abducibili = predicati della base di dati estensionale – osservazioni = update intensionale (di una vista) – teoria: definizioni delle viste

– Esempio

• DB estensionale contiene le relazioni padre e madre padre(a,b)

padre(a,e) madre(c,b)

• viste definiscono altre relazioni nonno(X,Y) ← padre(X,Z) ∧ padre(Z,Y) …

• Update

– U ≡ nonno(a,f)

– devo trovare cosa aggiungere al DB estensionale in modo da rendere vero U

E1 = {padre(b,f)} E2 = {padre(e,f) }

(23)

• Strette relazioni tra abduzione e programmazione logica: Abductive

Logic Programming

– dato un programma P e un goal G

• G viene dimostrato e si calcola sostituzione di risposta OPPURE • si possono fare assunzioni su atomi abducibili

– Risposta è

• sostituzione

• insieme di assunzioni su abducibili

– (più complesso con negazione)

– Un modo per implementare il ragionamento abduttivo – [Kowalski ILC 92]

• Strette relazioni con ATMS

– ATMS è un strumento per ragionamento abduttivo

Conclusioni

• varie forme di ragionamento non-monotono per “simulare” forme di

ragionamento comuni (“common-sense”)

• varie proprietà di equivalenza tra le diverse logiche non-monotone

• Seri problemi di complessità computazionale nel ragionamento non

monotono

– intrattabile in quasi tutti i casi

– spesso livello di intrattabilità elevato (non solo NP, ma classi superiori della gerarchia di complessità)