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à