Fuzzy extension of interval-based temporal sub-algebrasAlessandro Gonella

Università degli Studi di Padova

1) Introduzione - Non trattabilità di IAIA non è trattabile:● Verifica della consistenza e calcolo della rete minima

sono problemi NP-completi

Sottoclassi trattabili di IA:● SAc e SA, esprimibili con Point Algebra

Costo computazionale contenutoVS

Potere espressivo limitato

Introduzione - IAfuz

Creare un'estenzione fuzzy di IA:

● Ad ogni relazione atomica tra intervalli temporali viene associato un grado di preferenza in [0,1]

● E' possibile così indicare il grado di necessità di soddisfacibilità di una relazione

IAfuz è una generalizzazione di IA: stesso potere espressivo e stessa intrattabilità:

● Come per IA, è necessario trovare sub-algebra trattabile di IAfuz

Introduzione - IAfuz (2)● Si dimostrerà che PAc, PA, SAc e SA possono essere

estese in modalità fuzzy.

● Si dimostrerà che le estensioni fuzzy di SAc e SA sono sub-algebre trattabili di IAfuz

2) Interval AlgebraIn IA la conoscenza temporale è rappresentabile con un grafo:

● nodi rappresentano intervalli

● archi etichettati con le relazioni ugualmente possibili tra i 2 intervalli (13 relazioni possibili)

I1 (rel1, rel2, ...) I2

Interval Algebra (2)Singleton labelling di una rete IA N: assegnazione di una relazione atomica ad ognuno dei suoi archi.

Soluzione di N: singleton labelling che soddisfa tutti i vincoli della rete ed è consistente (le relazioni tengono)

SOL(N): insieme di soluzioni

Estensione fuzzy di IANel nostro approccio le relazioni tra due intervalli sono nella forma:

I1 (rel1[α1], rel2[α2], ...) I2

αi : grado di preferenza della relazione i-esima nell'intervallo [0,1]

degR(reli) = grado di preferenza assegnato dalla relazione R alla relazione atomica di Allen reli

Estensione fuzzy di IA (2)Abbiamo esteso IA ad una nuova algebra fuzzy IAfuz definita dall'insieme:

I = {b[α1], a[α2], m[α3], mi[α4], d[α5], di[α6], o[α7], oi[α8], s[α9], si[α10], f[α11], fi[α12], eq[α13]}

con αi ∈ [0,1], αi ∈ R, i = 1,..., 13

Ponendo invece αi ∈ {0,1} ri-otteniamo il framework classico

Chiusura di IAfuz rispetto a...● Data una relazione R, l'operatore di inversione R-1 è

definito come

R-1 = (rel1-1[α1],...,rel13

-1[α13]) dove reli

-1 è definito nella tabella di Allen

● Date due relazioni R' e R'', la congiunzione R = R' x R'' è definita come:

R = (rel1[α1],...,rel13[α13]) dove αi = min{α'

i,α''i} i ∈ {1,...,13}

Chiusura di IAfuz rispetto a... (2)

● La disgiunzione R = R' + R'':

R = (rel1[α1],...,rel13[α13]) dove αi = max{α'

i,α''i} i ∈ {1,...,13}

● Composizione R = R' ° R'':

R = (rel1[α1],...,rel13[α13])dove αi = maxj,k: reli ∈ {relj ° relk}

min{α'j,α

'k}

i,j,k ∈ {1,...,13}

ConsistenzaNella IA classica il singleton labelling parziale è localmente consistente se soddisfa tutti i vincoli

In IAfuz: consistenza locale graduata

Grado di un labelling singleton parziale s:

● Se l'assegnamento è inconsistente: degN(s)=0

● altrimenti degN(s) uguale al grado di preferenza del vincolo meno soddisfacente

Consistenza (2)

Una rete IAfuz è k-consistente se per ogni insieme di k-1 nodi, ogni assegnamento con un grado di consistenza locale α, è estensibile a qualsiasi altra k-esima variabile mantenendo lo stesso grado α.

Path consistency: k-consistency con k=3

Calcolo della rete minima equivalenteDue reti N1 e N2 sono equivalenti se coinvolgono le stesse variabili e per ogni singleton labelling completo s, degN1(s) = degN2(s)

La rete minima è quella "più esplicita" tra tutte le reti equivalenti

Una rete IAfuz N è minima sse per ogni relazione Rij tra due intervalli (Ii,Ij) e per ogni relazione relk[α] appartenente a Rij c'è un singleton labelling s di N che assegna relk a Rij e tale che degN(s) = α

3) Da PA a PAfuz

La point algebra classica PA si basa sulla nozione di punti temporali:

● Tre relazioni di base: <, = e >

● Possibilità di esprimere 8 diverse relazioni: Ø, <, ≤, =, >, ≥, ≠, ?

Un particolare subset di PA è la PAc (PA senza ≠), che ha interessanti poprietà computazionali:

L'algoritmo di path-consistency ottiene la minimalità in tempo polinomiale [O(n3)]

Da PA a PAfuz (2)Definiamo PAfuz considerando punti invece di intervalli e relazioni PA invece di relazioni di Allen

● PAfuz è definito sull'insieme

I = {< [α1], = [α2], > [α3]} dove αi ∈ [0,1], αi ∈ R, i = 1, 2,

3

● PAcfuz è la subalgebra di PAfuz definita sull'insieme

I = {< [α1], = [α2], > [α3]} dove αi ∈ [0,1], αi ∈ R, i = 1, 2,

3α2≥ min {α1, α3}

Da PA a PAfuz (3)L'idea è di eliminare il corrispettivo fuzzy di ≠, che corrisponde alla classe di relazioni PAfuz (< [α1], = [α2], > [α3]) tali che α2 < α1 e α2 < α3

Formalizziamo la relazione tra PAfuz e PAcfuz

Data una relazione PAfuz (IAfuz) Rfuz, il suo α-taglio Rα è la relazione PA (IA) fatta di relazioni atomiche reli tali che degRfuz(reli) ≥ α

Proposizione 1: Data una relazione R ∈ PAfuz, R ∈ PAcfuz

sse ∀α ∈ [0, 1] Rα ∈ PAc

Da PA a PAfuz (4)● PAc

fuz è un algebra● La prova di completezza dell'algoritmo di Path-

Consistency di PAc può facilmente essere estesa a PAc

fuz

Quindi può essere provato che l'applicazione dell'algoritmo di path consistency a Pac

fuz trova la rete minima equivalente

Estenzione fuzzy dell'algebra dei puntiI risultati sulla tracciabilità delle point algebras valgono anche nel contesto dell'interval algebra

Sono state definite due sub-algebras di IA, dette SAc e SA relazionate con PAc e PA

Le relazioni SA e SAc sono quelle relazioni di IA esprimibili dalle relazioni di PA e PAc

Estenzione fuzzy dell'algebra dei punti (2)Tutte le proprietà computazionali di PA e PAc sono mantenute:

● SAc path consistent sono minimali

● minimalità di 4-subnetworks assicura minimalità di SA networks

Generalizziamo le definizioni di SAc e SA al framework fuzzy, studiando le relazioni tra le algebre classiche e le estenzioni fuzzy, chiamate SAc

fuz e SAfuz

Da relazione tra intervalli a rete PAfuz

Possiamo tradurre una relazione IAfuz tra due intervalli in una rete PAfuz che interessa i 4 endpoints:

Definizione: Consideriamo la classe delle reti PAfuz con 4 nodi, denotati con {I1

-,I1+,I2

-,I2+} , ed indichiamo le loro

relazioni binare come R12--, R12

-+, R12+-, R12

++, R11-+, R22

-+. SPA

fuz è la classe di reti tali che R11-+ = {< [α1]} e R22

-+ = {< [α2]}, dove α1, α2 ∈ [0,1]

Da relazione tra intervalli a rete PAfuz (2)Una rete N ∈ SPA

fuz verrà denotata dalla 6-tupla delle sue relazioni PAfuz.

N ha al più 13 distinte soluzioni con grado di soddisfacimento > 0, che corrispondono alle possibili disposizioni dei due intervalli IA.Chiamiamo questo set SOLIA ⊆ {<,=,>}6

Ogni elemento s ∈ SOLIA corrisponde ad una relazione atomica di IA

Chiamiamo fIA la funzione da SOLIA a IA

La sub-algebra SAfuz

Definizione 3: Sia R una relazione R ∈ IAfuz; R ∈ SAfuz sse ∃ N minima ∈ SPA

fuz tale che ∀ s ∈ SOLIA degN(s) = degR(fIA(s)). Denotiamo questa rete N con C(R).Ovvero, le relazioni SAfuz sono quelle che possono essere tradotte in reti PAfuz preservando lo stesso insieme di soluzioni cosi come lo stesso grado di soddisfacimento

La subalgebra SAcfuz ⊆ SAfuz ⊆ IAfuz è composta dalle

relazioni che possono essere espresse con reti PAcfuz:

Definizione 4: Sia R una relazione R ∈ SAfuz; R ∈ SAcfuz

sse C(R) è una rete PAcfuz.

La sub-algebra SAfuz (2)Come per l'Interval Algebra classica, IAfuz è più espressiva della Point Algebra: solo un frammento di IAfuz può essere tradotto in PAfuz.

SAfuz e SAcfuz sono state definite tramite una

generalizzazione di SA e SAc: mantengono la stessa relazione presente tra PA e PAfuz e PAc e PAc

fuz.

Proposizione 2: Data una relazione IAfuz R, R ∈ SAfuz sse ∀α ∈ [0,1] Rα ∈ SA.

Proposizione 3: La proposizione 2 vale anche per SAcfuz

La sub-algebra SAfuz (3)Proposizione 4: SAfuz (SAc

fuz) è un'algebra rispetto alle operazioni di inversione, congiunzione e composizione

● Inversione: se I1 R I2, allora I2 R-1 I1

● Congiunzione e composizione: ○ Se * ∈ {⊗,◦} allora R = R1 * R2 sse ∀α ∈ [0, 1] Rα =

R1α* R2α

○ Se R1 e R2 sono relazioni SAfuz (SAcfuz) per la Prop. 2

(Prop. 3) R1α e R2α sono relazioni SA (SAc)○ SA (SAc) è un'algebra quindi Rα ∈ SA (Rα∈ SAc)...

La sub-algebra SAfuz (4)○ Tutti gli α-tagli di R appartengono a SA (SAc) e per

Prop. 2 (Prop. 3) R ∈ SAfuz (R ∈ SAcfuz)

Possiamo ora provare che le proprietà computazionali rilevanti sono mantenute nel framework fuzzy

5 - Due subalgebre trattabili di IAfuz

Dimostreremo che SAcfuz e SAfuz sono classi trattabili di

IAfuz, (mantengono le poprietà computazionali di SAc e SA)

Definizione 5: Data una rete IAfuz (PAfuz) N, il suo α-taglio Nα è la rete IA (PA) con gli stessi nodi di N, ma i cui vertici sono etichettati con gli α-tagli degli vertici corrispondenti di N

Proposizione 5: Una rete IAfuz (PAfuz) N è minima sse ∀α ∈ [0,1] Nα è minima

Proposizione 6: Una rete IAfuz (PAfuz) N è k-consistente sse ∀α ∈ [0,1] Nα è k-consistente

Proprietà computazionaliProposizione 7: Se una rete SAc

fuz è path-consistent, allora è anche minima

Prova: Sia N una rete SAcfuz path-consistent. Per le

proposizioni 3 e 5, ∀ α ∈ [0,1], Nα è una rete SAc path-consistent.Poichè le reti SAc path-consistent sono minime, tutti gli α-tagli di N sono minimi, e quindi lo è anche N (per la proposizione 5)

Proprietà computazionaliProposizione 8: Sia N una rete SAfuz. Se tutte le sue 4-subnetworks sono minime, allora N è minima

Prova:Per la proposizione 5, ∀ α ∈ [0,1], tutte le 4-subnetworks di Nα sono anch'esse minime.Per la proposizione 2, abbiamo che ∀ α ∈ [0,1], Nα è una rete SATenendo conto dei risultati per le reti SA classiche, tutti gli α-tagli di N sono minimiPer la proposizione 5, anche N è minima

AlgoritmiQueste proposizioni possono essere utilizzate per sviluppare un algoritmo polinomiale che calcola la rete minima equivalente ad una rete SAc

fuz o SAfuz N.

Per reti SAcfuz è sufficiente utilizzare l'algoritmo di path

consistency con complessità O(k*n3)

Per le reti SAfuz si può utilizzare una generalizzazione dei AAC, con complessità O(k*n4)

ConclusioniDiversamente da altri lavori della letteratura questo si focalizza sull'aspetto qualitativo della rappresentazione

Si è dimostrato come le proprietà computazionali delle subalgebre trattabili si possano estendere a IAfuz

Il prossimo passo è l'integrazione di questo framework qualitativo in uno quantitativo