P. Romani, Cosa Nostra e Ndrangheta. Schede descrittive sintetiche
Logiche descrittive M. Simi, 2005-2006 Categorie e oggetti Molti dei ragionamenti che si fanno sono...
-
Upload
silvana-drago -
Category
Documents
-
view
212 -
download
0
Transcript of Logiche descrittive M. Simi, 2005-2006 Categorie e oggetti Molti dei ragionamenti che si fanno sono...
Logiche descrittive
M. Simi, 2005-2006
Categorie e oggetti
Molti dei ragionamenti che si fanno sono sulle categorie piuttosto che sugli individui
Se organizziamo la conoscenza in categorie (e sottocategorie) è sufficiente classificare un oggetto, tramite le proprietà percepite, per inferire le proprietà della categoria|e a cui appartiene (ereditarietà)
Ontologie di dominio
Ontologia: modelli formali di un dominio di interesse
Le relazioni di sottoclasse organizzano la conoscenza in tassonomie (come in botanica, biologia, nelle scienze librarie …)
Molte delle idee delle reti semantiche e dei frame sono state raccolte in logiche specializzate
Queste logiche sono alla base delle proposte per il Web semantico
Il Web semantico
La visione di Tim Berners-Lee (1998): da un Web "sintattico" per la comunicazione tra persone al Web "semantico" come un grosso DB di oggetti strutturati comprensibili ai programmi
Agenti software che operano in Internet
Il livelli del Web semantico
I livelli del web semantico Unicode e URI XML interoperabiltà sintattica RDF (Resource Description Framework): per
descrivere relazioni semantiche tra risorse (livello delle asserzioni)
RDF schema: per vincolare domini e codomini delle relazioni, definire classi di oggetti, relazioni tra classi Schemi RDF per cataloghi di biblioteche, directory,
news, software, musica, foto, eventi, persone, oggetti in vendita ...
RDFS linguaggio per ontologie ma poco espressivo
Web semantico e linguaggi per ontologie
Linguaggi per l'aggiunta di un servizio inferenziale a RDF:
OIL gruppo europeo DAML-ONT gruppo americano DAML+OIL proposto come standard OWL: Web Ontology Language, standard
W3C. OWL evolve dalle logiche descrittive
Logiche descrittive
Possono essere viste come:1. Evoluzioni “logiche” di linguaggi di
KR basati sulle nozioni di frame e reti semantiche
2. Contrazioni della logica del prim’ordine (FOL) per ottenere migliori proprietà computazionali
LT come eredi di frame e reti semantiche Verso gli anni 80 si ha una sterzata
verso la logica delle reti semantiche Il processo di formalizzazione consiste
nel … riformulare i costrutti secondo i canoni
della logica eliminare i costrutti che non si prestano a
tale riformulazione (default ed eccezioni)
EsempioLa seguente è una formula di una delle LT: (and paper (atmost 2 author) (atleast 2 author))[paper372]equivalente a:
paper(paper372) x author(paper372, x) y author(paper372, y) x y author(paper372, z) (z x) (z y)
Concetti, ruoli, individui
Ogni LT è caratterizzata da operatori per la costruzione di termini di due tipi: concetti (corrispondenti a relazioni unarie)
con operatori and, or , not, all, some, atleast, atmost, … per la costruzione di concetti complessi
ruoli (corrispondenti a relazioni binarie)ed eventualmente operatori
individui (usati nelle asserzioni)
Una KB basata su logica terminologica
giornalista autore articolo (and (a-not libro) (all autore giornalista)) autore creatore
autore[Eco, l1] autore[Biagi, l2] giornalista[Biagi] (and libro (all autore giornalista))[a2]
KB T-BOX
A-BOX
Top scrittore librogiornalista
(and libro (all autore
giornalista)) bottom
a2
Top
creatore libro autore
giornalista
(and libro (all autore
giornalista))
bottom
La logica ALC : la sintassi dei termini<concetto> <spu>
|(top) |(bottom) |(and <concetto> …
<concetto>) |(not <concetto>) |(all <ruolo> <concetto>) |(some <ruolo>)
<ruolo> <spb><spu> simbolo di predicato unario<spb> simbolo di predicato binario
Semantica di ALC I(C) è un insieme di individui I(R) è un insieme di coppie di individui, una relazione
binaria I(top) D l’insieme universo I(bottom) { } l’insieme vuoto I(not C) = D I(C) il complemento I(and C1, … Cn) = I(C1) … I(Cn) intersezione I(all R C) = { x D | y <x, y> I(R) y I(C)} I(some R) = { x D | y <x, y> I(R)} Un’interpretazione I è un modello di un concetto C
sse I(C) { }. Lo stesso per i ruoli.
Esempio 1
(and articolo (some autore) (all autore giornalista))
“l’insieme degli articoli che hanno
almeno un autore, e i cui autori sono tutti giornalisti”
Esempio 2
(or padre madre)
persona
padre madre
Esempio 3
(and persona (some figlio))
{ x D | y <x, y> I(figlio)}
persona
(some figlio) p1
p2
figlio
<p1, p2><p1, p3><p2, p4>
…
Esempio 4
(and persona (all figlio femmina))
{x D | y <x, y> I(figlio) y I(femmina)}
persona
(all figlio femmina)
p1
figlio
<p1, p2><p1, p3><p2, p4><p2, p5>
…
femminap2 p3
p4
p5
Esempi di assiomi (T-BOX) Definizioni
genitore (some figlio) celibe (not coniugato) celibe (not (some moglie))
Specializzazioni padre (some figlio) madre (some figlio) gatto (and animale felino)
Esempi di asserzioni (A-BOX)
(not (some moglie))[giorgio] (and madre avvocato)[teresa] figlio[paolo, giorgio] moglie[teresa, giorgio]
La famiglia AL Diverse LD sono ottenute aggiungendo
altri costruttori di termini ad AL I principali sono:
U: (or C1 …Cn) E: (c-some R C)
C: (not C) N: (atleast n R) R: (and R1 …Rn) (atmost n R)
S spesso usato per ALC con ruoli transitivi
Il reticolo della famiglia AL
© Paolo Buongarzoni & Rossella
Problemi decisionali classici
Soddisfacibilità di una KB (KBS) Conseguenza logica di una KB:
il problema di decidere, dato C[i], se KB |= C[i], detto anche instance checking,
IC(KB, C[i])
Problemi decisionali per DL: CS
Soddisfacibilità di un concetto [CS(C)]: il problema di decidere se esiste un’interpretazione diversa dall’insieme vuoto
(father) è soddisfacibile; (and father (not father)) è insoddisfacibile
Problemi decisionali per DL: sussunzione
Sussunzione terminologica, o strutturale (SU): C1 sussume C2 [SU(C1, C2)]
sse per ogni interpretazione I, I(C2) I(C1)
Es. person sussume (and person (some child))
Sussunzione ibrida (HSU(KB, C1, C2)): come sopra ma si usano anche le definizioni nella KB
Es. Se student person T-BOX allora person sussume student
Riduzione tra problemi decisionali
I problemi decisionali non sono indipendenti tra di loro:
1. HSU({ }, C1, C2) SU(C1, C2) la sussunzione ibrida e strutturale coincidono se la T-BOX è vuota
2. SU(C1, C2) CS((and C2 (not C1)))la sussunzione strutturale può essere ricondotta alla soddisfacibilità di concetti
… e tutti possono essere ricondotti a KBS3. CS(KB, C) KBS(KB {C[i]}) (KB può essere
vuota)C è soddisfacibile sse KB {C[i]}, con i nuovo individuo, è una KB soddisfacibile
4. IC(KB, C[i]) KBS(KB {(not C)[i]}) Per vedere se KB |= C[i] basta vedere se aggiungendo (not C)[i], KB diventa insoddisfacibile
5. HSU(KB, C1, C2) KBS(KB {(and C2 (not C1))[i]})
C1 sussume C2 se aggiungendo (and C2 (not C1))[i], con i nuovo individuo, la KB è insoddisfacibile;
Esempi di riduzione di problemi
Per essere felici bisogna essere ricchi e sani
(e in alcuni casi non basta) T-BOX: Felice (and Ricco Sano)
1. Una persona ricca può essere infelice?
HCS(KB, (and Ricco (not Felice)) ) KBS(KB {(and Ricco (not Felice))[i]})
Esempi di riduzione di problemi (cont.)
2. I ricchi sono felici? HSU(KB, Felice, Ricco) KBS(KB {(and Ricco (not Felice))[i]})
3. Essere ricco e sano basta per essere felice?
HSU(KB, Felice, (and Ricco Sano)) KBS(KB {(and (and Ricco Sano)(not
Felice))[i]})
Sistemi deduttivi per DL
Algoritmi per determinare la sussunzione
La tecnica più diffusa è una variante dei tableaux semantici: una tecnica di propagazione di vincoli per la KBS (soddisfacibilità)
Tecnica di propagazione di vincoli
L’idea di base: ogni formula nella KB è un vincolo sulle interpretazioni affinché siano modelli di KB
I vincoli complessi si scindono in vincoli più elementari mediante regole di propagazione fino ad arrivare, in un numero finito di passi, a vincoli atomici
Se l’insieme di vincoli atomici contiene una contraddizione evidente (detta clash) allora la KB non è soddisfacibile, altrimenti abbiamo trovato un modello.
Vantaggi della tecnica
1. è semplice2. è costruttiva3. è modulare: una regola per ogni
costrutto4. è utile per progettare algoritmi di
decisione e per valutarne la complessità
La tecnica in dettaglio per AL
AL come ALC ma not solo davanti a concetti primitivi
1. Espansione delle definizioni: passo preliminare che consiste nel ridursi ad una KB=<A, { }> con solo la parte di asserzioni.Le asserzioni sono i vincoli iniziali
2. [Normalizzazione]3. Propagazione di vincoli
Eliminazione della KB Se KB=<A, D> Assunzione: D non contiene cicli nelle definizioni
Es. D={C (and C’ (some R’)), C’ (not C’’))} A={(all R C)[i]}I passo: eliminazione delle specializzazioni: C1 C2 diventa C1 (and C* C2) introducendo un
nuovo concetto primitivo C*II passo: sostituzione A’={(all R (and C’ (some R’)) )} A’’={(all R (and (and C* (not C’’)) (some R’)))}
Normalizzazione
Un insieme di vincoli si dice normale sse ogni occorrenza dell’operatore not è applicata ad un concetto primitivo.
Regole di normalizzazione: non necessarie per la nostra logica semplice AL
In logiche più complicate, ad esempio: (not (and C1, … Cn)) (or (not C1) …(not Cn)) (not (all R C)) (c-some R (not C))
Propagazione di vincoli per LT
Un vincolo è una espressione della forma C[s] o R[s1, s2], dove s, s1 e s2
sono costanti o variabili. Un insieme di vincoli è
soddisfacibile sse esiste una interpretazione che soddisfa ogni vincolo in .
Regole di propagazione
Regola di propagazione: è una funzione da un insieme di vincoli ad un insieme di vincoli.
Un insieme di vincoli è completo se nessuna regola di propagazione è applicabile ad esso.
Le regole di propagazione dipendono dal linguaggio: una regola per ogni costrutto.
Regole di propagazione per AL
and {C1[s], … , Cn[s]}se (and C1, … , Cn)[s] , e {C1[s], … , Cn[s]}
all {C[t]}se (all R C)[s] , R[s, t] e C[t]
some {R[s, x]}se (some R)[s] , e non esiste t tale che
{R(s, t)} e x è una nuova variabile
Osservazioni
Le regole and all some per AL sono deterministiche
Per linguaggi più complessi (con or, atmost) c’è bisogno di regole non deterministiche: la loro applicazione può risultare in più insiemi di vincoli alternativi
è soddisfacibile sse almeno uno degli insiemi di vincoli ottenuti lo è.
Clash per AL
Un clash per AL è un insieme di vincoli di uno dei seguenti tipi:
1. {(not M)[s], M[s]};2. {(bottom)[i]}
Esempio 1
KB=1={ (and Lavoratore Studente)[g],
(not Lavoratore)[g]}2= 1 { Lavoratore[g], Studente[g] } La base di conoscenza è insoddisfacibile
perché contiene un clash: (not Lavoratore)[g]
Lavoratore[g]
Esempio 2
KB=1={ (some Figlio)[g],
(all Figlio Lavoratore)[g] (all Figlio Studente)[g]}2 = 1 { Figlio[g, x]}
3 = 2 { Lavoratore [x] }
4 = 3 { Studente [x] }
completo e senza clashDa 4 è possibile ricavare un modello per KB.
Proprietà dell’algoritmo di PV
1.Il risultato è dimostrabilmente invariante rispetto all’ordine di applicazione delle regole.
2.Completezza: se una base di conoscenza KB è soddisfacibile, allora l’algoritmo termina producendo almeno un sistema di vincoli completo e senza clash, isomorfo a un modello finito di KB.
3. Correttezza: se l’algoritmo termina producendo almeno un sistema di vincoli completo e senza clash, allora la KB è soddisfacibile
OWL
OWL-DL euivalente a SHOINO: {Italia} nominali o singolettiH: haZio haParente gerarchia di
ruoliI: haFiglio Figliodi– ruolo inverso
Costruttori di OWL
Sintassi usata(and C1 ... Cn)(or C1 ... Cn)(not C)(or {C1} ... {Cn})(all P C)(some P C)(atmost n P)(atleast n P)
Assiomi OWL
Un esempio
Risultati di decidibilità e trattabilità
Consideriamo il problema della sussunzione. Trattabile Decidibile
Semicidibile
ALN ALCNR FOL ALC ALNI
PROP OWL-DL
soglia della soglia della
trattabilitàdecidibilità