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
Top Related