Corso di Laurea in Corso di Laurea in INFORMATICA INFORMATICA

Dipartimento di Informatica - Università di Bari

Corso di Laurea in Corso di Laurea in

INFORMATICA INFORMATICA

INTELLIGENZA INTELLIGENZA

ARTIFICIALE ARTIFICIALE

(CdL di II Livello) (CdL di II Livello)

MODULO MODULO

Unificazione e Pattern Matching Unificazione e Pattern Matching

UNIFICAZIONE E PATTERN MATCHING

In Intelligenza Artificiale (A.I.), la maggior parte dei sistemi basati su conoscenza supporta un’operazione di base:

Il confronto di descrizioni (simboliche) (Unificazione o Matching)

“ L’unificazione è per l’A.I. (e per il calcolo simbolico) quello che l’addizione e la

moltiplicazione rappresentano per il calcolo

numerico” (Siekmann, 1990)

UNIFICAZIONE E PATTERN MATCHING

Ad esempio, è stato valutato che in molti sistemi di produzione il 90% del tempo di calcolo complessivo è dedicato ad operazioni di Matching.

L’unificazione è parte essenziale di operazioni più complesse, quali la risoluzione, la ricerca, il

controllo e costituisce il problema fondamentale per i sistemi che effettuano inferenze (sistemi esperti, dimostratori automatici di teoremi, risolutori di

problemi, sistemi di apprendimento, sistemi di produzioni, … ).

UNIFICAZIONE E PATTERN MATCHING

Il matching è un problema trasversale, comune a molte branche dell’A.I.:

programmazione logica, database intelligenti, elaborazione del linguaggio naturale,

apprendimento automatico, …

Di conseguenza, la ricerca di tecniche efficienti di matching riveste tuttora

un’importanza fondamentale per tutti coloro

che operano nel campo dell’A.I.

UNIFICAZIONE E PATTERN MATCHING

Il problema è stato formulato, affrontato e studiato da diversi ricercatori in modi

differenti.

Oggi sulla maggior parte delle macchine

dedicate all’A.I., l’unificazione è realizzata da

hardware specializzato o per mezzo di un set

di istruzioni veloci (CPU nei computer della V

generazione; macchina astratta di Warren: le

descrizioni da confrontare sono compilate

nel set di istruzioni della macchina).

UNIFICAZIONE E PATTERN MATCHING

TEORIA DELL’UNIFICAZIONE

L’unificazione è il procedimento attraverso cui si confrontano 2 o più strutture per

scoprire le loro somiglianze o differenze. Le strutture possono essere espresse in diversi formalismi: logica proposizionale, vettori di

caratteristiche, regole, strutture frame-like, FOPL, grafi, reti semantiche, …

Focalizzeremo la nostra attenzione su:

formule ben formate (fbf) in FOL

UNIFICAZIONE E PATTERN MATCHING

Breve richiamo di Logica (di ordine 1)

Def. 1 TERMINE

<termine> ::= <costante> | <variabile>|

<funzione n-aria>

( <termine>,…,<termine> )

n

UNIFICAZIONE E PATTERN MATCHING

Def. 2 Formula Atomica (o Atomo)

<formula atomica> ::= <predicato n-ario>

( <termine>,…,<termine> )

n

Unificazione

• La risoluzione si applica a clausole di base (ground)

– Problema: applicare la risoluzione a clausole contenenti variabili

• Non è sempre facile determinare se due atomi non possono essere veri contemporaneamente

Esempio: P(x,f(a)) v P(x, f(y)) v Q(y) e ¬P(z, f(a)) v ¬Q(z)

– Soluzione: Bisogna cercare delle sostituzioni di

termini alle variabili presenti nelle clausole genitore in modo tale che queste contengano atomi

complementari

UNIFICAZIONE E PATTERN MATCHING

Il problema dell’unificazione:

“dati 2 termini, s e t, esistono dei termini

che possono essere sostituiti alle variabili

che compaiono in s ed in t, in modo che i

termini così ottenuti siano identici?”

UNIFICAZIONE E PATTERN MATCHING

IN MODO PIU’ RIGOROSO:

Siano:

FU

= { a,b,c, … }

VAR = { x

,x

,x

,…}

FU

= { f,g,h,…}, n=1,2,…

Indichiamo con t

,t

,t

,… i termini costruiti a

partire dai precedenti insiemi, secondo la def. di termine data in precedenza.

TERM={ t

,t

,t

,…}

UNIFICAZIONE E PATTERN MATCHING

Def.3 SOSTITUZIONE

Una sostituzione σ è una funzione che ad ogni variabile associa un termine.

σ : VAR → TERM Si indica anche come:

σ = { (t

/x

) | x

∈ VAR, t

∈ TERM } o ancora:

σ = { x

← t

| x

∈ VAR, t

∈ TERM }

UNIFICAZIONE E PATTERN MATCHING

Per comodità, si definiscono anche i prolungamenti di σ su TERM e

sull’insieme delle formule ben formate del linguaggio (che, d’ora in poi,

indicheremo con FBF).

Continueremo ad indicare queste

funzioni con σ .

UNIFICAZIONE E PATTERN MATCHING

Quando, ad esempio, σ viene applicata ad un termine t, in cui compaiono le variabili x

, essa produce un nuovo termine, σ (t), ottenuto sostituendo tutte le occorrenze delle variabili x

con i termini t

corrispondenti. Oltre che con σ (t),

un’istanza di una sostituzione viene

indicata con: t σ .

UNIFICAZIONE E PATTERN MATCHING

ATTENZIONE

Non è lecito sostituire una variabile con un termine in cui compare quella

stessa variabile! (a meno che

permettiamo TERMINI INFINITI)

UNIFICAZIONE E PATTERN MATCHING

ESEMPIO di Sostituzione (lecita)

Sia t = f (g(a,b), x, y) un termine del linguaggio e σ ={ g(a)/x, c/y, y/z } una sostituzione.

Dalle definizioni date, si ha:

σ (t) = f(g(a,b),g(a),c).

UNIFICAZIONE E PATTERN MATCHING

DEF.4 Sostituzione Composta

Date due sostituzioni, δ e σ , si chiama

sostituzione composta da δ e σ , e si denota con ( σ ° δ ), la sostituzione ottenuta da δ e σ come segue:

• Modificando δ in modo che ai suoi termini sia applicata la sostituzione σ ;

• Aggiungendo a δ le coppie

(termine/variabile) in σ che hanno le

variabili non presenti tra le variabili in δ .

UNIFICAZIONE E PATTERN MATCHING

TEOREMA1

Fissato arbitrariamente un termine t e due sostituzioni σ e δ , risulta:

( σ ° δ ) (t) = σ ( δ (t)) Dimostrazione

Per esercizio.

UNIFICAZIONE E PATTERN MATCHING

ESEMPIO Sia t = f(x,y)

δ = {g(y,z)/x, a/y} σ={b/y, c/z}

Dalle regole (1) e (2) di formulazione di una sostituzione composta, si ha:

( σ ° δ ) = { g(b,c)/x, a/y, c/z }

È facile verificare che:

( σ ° δ ) (t) = σ(δ(t)) Si ha infatti :

(σ ° δ ) (t) = f(g(b,c),a)

σ(δ(t)) = σ( f(g(y,z),a) ) = f(g(b,c),a) Mentre:

δ(σ(t)) = δ(f(x,b)) = f(g(y,z),b) ≠ f(g(b,c),a) = σ(δ(t))

UNIFICAZIONE E PATTERN MATCHING

TEOREMA 2 L’operazione di

composizione delle sostituzioni è

associativa, ma non è commutativa, ossia fissate tre sostituzioni,

τ , δ , σ , risulta :

(( σ ° δ ) ° τ ) = ( σ ° ( δ ° τ ))

(σ ° δ ) ≠ (δ ° σ )

UNIFICAZIONE E PATTERN MATCHING

DEF.5 TERMINI UNIFICABILI –

UNIFICATORE – UNIFICAZIONE

Due termini, s e t, si dicono unificabili se esiste una sostituzione σ tale che :

σ( s) = σ( t)

In tal caso, si dice che σ è un unificatore

di s e t e σ( s) (o σ (t)) è un’unificazione

di s e t.

UNIFICAZIONE E PATTERN MATCHING

ESEMPIO 2 Dati: s = f (g(y,b), x) t = f(x, g(a,b)) ci chiediamo se s e t sono unificabili.

σ ={ g(a,b)/x, a/y } è un unificatore di s e t; si ha infatti:

σ(s) = f( g(a,b), g(a,b) ) = σ(t) E dunque s e t sono unificabili.

UNIFICAZIONE E PATTERN MATCHING

ESEMPIO 3 Dati: s = f(x,g(y)) t = f(x,g(b)) s e t sono unificabili e σ = { b/y } è un unificatore.

Ma è l’unico unificatore di s e t ?

Anche δ={ a/x, b/y } è un unificatore di s e t e, inoltre, è facile verificare che esistono molti altri unificatori di s e t.

Tuttavia, comunque scegliamo un unificatore per s e t, ci accorgiamo che σ risulta essere il più semplice. Si ha, infatti: δ = { τ ° σ } ove τ = { a/x }.

UNIFICAZIONE E PATTERN MATCHING

Inoltre, si può dimostrare che, se θ è un unificatore di s e t, esiste una

sostituzione ψ tale che:

θ = ( ψ ° σ ) ( θ è un’istanza di σ )

UNIFICAZIONE E PATTERN MATCHING

DEF 6 UNIFICATORE PIU’ GENERALE ( MGU = Most General Unifier ) o UNIFICATORE PIU’ SEMPLICE

Dati due termini, s e t, e un unificatore σ di s e t, si dice che σ è l’unificatore più generale di s e t se, per ogni altro unificatore δ di s e t, esiste una sostituzione τ tale che :

δ=(τ ° σ)

(Chang and Lee, 73; Lloyd, 84)

UNIFICAZIONE E PATTERN MATCHING

Intuitivamente, possiamo pensare al

MGU come al “più semplice” tra tutti gli unificatori di due termini dati.

Il problema dell’unificazione consiste nel trovare (se esiste) l’MGU di due

termini.

UNIFICAZIONE E PATTERN MATCHING

UNIFICAZIONE E TEORIA DELLA COMPUTABILITA’

TEOREMA 3 (senza dimostrazione)

Il problema dell’unificazione è decidibile nelle Teorie del I ordine.

TEOREMA 4 (Goldfarb, 1981)

Il problema dell’unificazione è indecidibile nelle Teorie di ordine ω , ω ≥ 2 (Riduzione al X problema di Hilbert) (Nel 1972, C.L. Lucchesi e nel 1973 G.P. Huet avevano già

scoperto indipendentemente l’indecidibilità del problema per ω ^{≥ 3)}

UNIFICAZIONE E PATTERN MATCHING

TEOREMA 5 L’MGU di due termini del linguaggio di una Teoria del I ordine, se esiste, è unico. (Teoria unitaria) DIMOSTRAZIONE Per esercizio.

NOTA: Il Teorema 5 cessa di valere se i simboli di

funzione che compaiono all’interno dei termini godono di una delle seguenti proprietà (o di entrambe):

• f (x,y) = f ( y,x ) Commutatività

• f (f(x,y),z) = f(x,f(y,z)) Associatività

UNIFICAZIONE E PATTERN MATCHING

In altre parole, in una teoria di

equazioni (equational theory), in cui

agli assiomi di una teoria del I ordine

(algebra libera dei termini = absolutely

free term algebra) si aggiunge almeno

una delle equazioni (C) ed (A), possono

esistere diversi MGUs di 2 termini.

UNIFICAZIONE E PATTERN MATCHING

UNIFICAZIONE DI FBF

DEF. PERMUTAZIONE

Sia A = { k ∈ ℕ | ≤ k ≤ n }. Una permutazione p di A è una qualsiasi funzione biunivoca

p: A → A.

DEF. LETTERALE

<letterale>::= <formula atomica> | ¬<formula atomica>

UNIFICAZIONE E PATTERN MATCHING

DEF. FORMULE ATOMICHE UNIFICABILI Siano a ed a’ due atomi:

a = P (t

,t

,…,t

) a’= Q (t

’,t

’,…,t’

)

a e a’ si unificano se esiste una sostituzione σ tale che: σ (a)= σ (a’).

Questa condizione è equivalente al seguente insieme di condizioni:

1) P = Q 2) n = m 3) esiste una sostituzione σ

tale che ∀i ∈ {1,2,…,n} : σ (t

) = σ (t’

)

UNIFICAZIONE E PATTERN MATCHING

OSSERVAZIONE

Nel caso in cui l’ordine tra i termini del predicato P non abbia importanza, ossia P è commutativo (es. “equal”), si modifica la definizione di

unificazione tra atomi come segue:

a ed a’ si unificano se:

• P = Q 2) n = m 3) esistono una permutazione p dei primi n numeri naturali positivi ed una

sostituzione

σ tale che ∀ i ∈ {1,2,…,n} : σ ( t

) = σ( t’

).

UNIFICAZIONE E PATTERN MATCHING

DEF. LETTERALI UNIFICABILI

Siano l ed l’ due letterali. l ed l’ si unificano se esiste una sostituzione σ tale che:

σ( l ) = σ ( l’ ).

Esempio

l

= ¬ went ( John, south(x))

l

= ¬ went ( y, south (America))

si unificano ed il loro unificatore (che è anche

l’MGU) è: σ = { America/x, John/y }

UNIFICAZIONE E PATTERN MATCHING

DEF. UNIFICABILITA’ DI CONGIUNTI DI LETTERALI Siano c e c’ due congiunti di letterali:

c = l₁ ∧ l₂ ∧ … l_k c’= l’₁ ∧ l’₂ ∧ … l’_h

c e c’ si unificano se esiste una sostituzione σ tale che:

σ(c)=σ(c’).

Le condizioni scritta sopra è equivalente al seguente insieme di condizioni:

• k = h ed esistono una permutazione p sui primi k numeri naturali positivi ed una sostituzione

σ tale che ∀ i ∈ {1,2,…,k} : σ (l_i) = σ(l’_p(i)).

UNIFICAZIONE E PATTERN MATCHING

ESEMPIO

c1 = P (f(x

), h(x

,f(x

)) ∧ Q(h(x

),x

)

c2 = Q (h(g(x

)),g(x

)) ∧ P(x

,h(g(x

),x

)) si unificano e il loro MGU è:

σ={ g(x

)/x

, g(x

)/x

, f(x

)/x

} OSSERVAZIONE

Le condizioni perché due congiunti di letterali

siano unificabili non sono equivalenti a quelle

richieste per l’unificazione di due insiemi di

letterali.

UNIFICAZIONE E PATTERN MATCHING

L={ l₁,l₂,…,l_k } ed L’={ l’₁,l’₂,…,l’_h }

Insieme di letterali, L ed L’ sono unificabili se esiste una sostituzione σ tale che:

σ( L ) = σ ( L’ )

Infatti, consideriamo il seguente esempio:

c= P(f(x), y) ∧ P (f(a),b)L={P(f(x),y),P(f(a),b}

c'= P(f(z), w) L={P(f(z),w)}

Si vede chiaramente che esiste:

σ= {a/x, b/y, a/z, b/w } tale che:

σ(L) = σ (L’) = { P (f(a),b) }

mentre c e c’ non sono unificabili poiché k ≠ h, secondo la def. di unificabilità di congiunti di letterali.

UNIFICAZIONE E PATTERN MATCHING

DEF. UNIFICABILITA’ DI FBF IN FORMA NORMALE DISGIUNTIVA

Siano d e d’ due fbf in forma normale disgiunta:

d = c₁ v c₂ v … c_m d’= c’₁ v c’₂ v … c’_n

d e d’ si unificano se esiste una sostituzione σ tale che:

σ ( d ) = σ ( d’ )

Analogamente a quanto detto in precedenza, la condizione sopra equivale a richiedere che:

1) m = n 2) esistono una permutazione p dei primi m numeri naturali positivi ed una sostituzione σ ∋′ ∀ i

∈ {1,2,…,m} : σ (c_i) = σ(c’_p(i)).

UNIFICAZIONE E PATTERN MATCHING

ESEMPIO

d = red ( x

) v ontop ( x

, x

)

d’ = ontop (head(x4), neck) v red (car(John))

Si unificano ed il loro MGU è :

σ = { head ( x

) / x

, neck / x

, car (John) /x

}

UNIFICAZIONE E PATTERN MATCHING

ESERCIZIO

Stabilire se le seguenti coppie di fbf si unificano. Se sì, fornire l’MGU, altrimenti spiegare brevemente perché non si unificano.

• Color (Tweety, Yellow) Color(x,y)

• Color (Tweety, Yellow) Color(x,x)

• Color(Hat(Postman),Blue) Color(Hat(y),x)

• R(F(x),b) R(y,z)

• R(F(y),x) R(x,F(B))

• R(F(y),y,x) R(x,F(A),F(v))

• Loves(x,y) Loves(y,x)

L’ALGORITMO DI UNIFICAZIONE

La scoperta della stretta relazione tra deduzione logica e computazione dà nuovo impulso alla ricerca: la logica gioca un ruolo nell’informatica analogo a quello della

analisi in fisica. La logica dei predicati è un linguaggio di programmazione (Kowalski, 1979).

Computer della V generazione

(velocità in KLIPS: Logical Inference Per Second)

• Macchine per eseguire Linguaggi per la Programmazione Logica

• La CPU è un Algoritmo di Unificazione (in HW o in SW)

LA RAPPRESENTAZIONE DI TERMINI (STRUTTURE DI DATI)

RAPPRESENTAZIONE A STRINGA (Robinson, 1965)

• Un termine viene rappresentato come un array lineare, i cui elementi sono: simboli di funzione, variabili,

costanti, virgole e parentesi.

ESEMPIO

s= p(g(f(x)), h(f(x)))

) ) ) x ( f ( h , ) ) x ( f ( g ( p

LA RAPPRESENTAZIONE DI TERMINI (STRUTTURE DI DATI)

RAPPRESENTAZIONE AD ALBERO

Un termine viene rappresentato da un albero in cui ogni simbolo di funzione rappresenta la radice di un sottoalbero i cui figli sono gli argomenti di quella funzione.

Le variabili e le costanti presenti nel termine costituiscono le foglie dell’albero.

ESEMPIO

p

g h

f f

x x

LA RAPPRESENTAZIONE DI TERMINI (STRUTTURE DI DATI)

Le rappresentazioni a stringa e ad albero sono utilizzate per quelle applicazioni dell’unificazione che gestiscono termini non troppo complicati, ossia brevi e poco annidati.

SVANTAGGIO

Ignorano le strutture ( i sottotermini ) comuni.

ESEMPIO

Cosa accade quando si cerca di unificare:

s=p(g(f(x)), h(f(x)) e t=p(g(f(a)),h(f(a)))

Non c’è alcun bisogno di elaborare la seconda occorrenza di f(x) e di f(a), una volta fissata la sostituzione {a/x}.

Dunque, abbiamo bisogno di una rappresentazione più concisa.

LA RAPPRESENTAZIONE DI TERMINI (STRUTTURE DI DATI)

RAPPRESENTAZIONE A GRAFO

DAG = Directed Acyclic Graph. Se permettiamo che i nostri grafi contengano cicli, possiamo gestire termini infinitamente lunghi e l’unificazione può produrre sostituzioni che coinvolgono tali termini ( unificazione infinita)

f(x) è condiviso; lo sforzo per unificarlo con un altro sottotermine va fatto una sola volta!

Se i sottotermini non vengono condivisi può essere necessario generare strutture di ampiezza

esponenziale durante l’unificazione.

p

g h

f

x

Unificazione

• Processo di unificazione usato per scoprire se una formula atomica presa negata oppure no può corrispondere ad un’altra

– Sostituzione di variabili in entrambe le formule

atomiche con dei termini che renderebbero identiche le due formule atomiche

• Esistono diversi algoritmi per unificare un insieme finito di espressioni

– Falliscono quando l'insieme non può essere unificato

Unificazione

UNIFICA(L1,L2: espressioni in forma di lista) → SOST: sostituzioni usate per unificare L1 ed L2

se L1 o L2 è un atomo allora se L1 = L2 allora ritorna NIL se L1 è una variabile allora

se L1 compare in L2 allora ritorna Fallimento altrimenti ritorna { L1 ← L2 }

se L2 è una variabile allora

se L2 compare in L1 allora ritorna Fallimento altrimenti ritorna { L2 ← L1 }

Se lunghezza(L1) ≠ lunghezza(L2) allora ritorna Fallimento SOST ← NIL

Per i = 1 fino al numero di elementi di L1 esegui

S ← UNIFICA(i-esimo elemento di L1, i-esimo elemento di L2) se S = Fallimento allora ritorna Fallimento

se S ≠ NIL allora

applica S a ciò che rimane sia di L1 che di L2 SOST = concatena (S, SOST )

PATTERN MATCHING

Per molte applicazioni pratiche l’unificazione è un concetto troppo generale.

Una importante variante è rappresentata dal pattern matching o semplicemente matching.

DEF. Termini per cui esiste un Matching

( “confrontabili” ) MATCHER – MATCHING

Dati due termini, s e t, si dice che esiste un matching tra essi se esiste una sostituzione µ tale che :

µ(s) = t ( opp. µ(t) = s )

In tal caso, si dice che µ è un matcher di s e t e µ(s) ( risp. µ(t) ) è un matching di s e t

PATTERN MATCHING

In altre parole, un problema di matching è un problema di

unificazione in cui è lecito effettuare sostituzioni solo in uno dei due termini. ( continuano a valere i teoremi? )

Il matching è genericamente inteso come il processo attraverso cui si confrontano o più strutture per scoprire le loro

somiglianze o differenze.

Nella sua forma più semplice, le strutture, anche dette forme ( patterns ), vengono confrontate per stabilire se sono uguali ( e il matching è visto come funzione booleana ).

Nei sistemi intelligenti, il matching è utilizzato per diversi scopi:

classificazione, correzione, ritrovamento, decomposizione.

OSSERVAZIONE ( SUSSUNZIONE E MATCHING )

Il matching è un caso particolare della sussunzione. Siano s e t termini per cui esiste il matching µ

µ (s) = t ⇒ µ (s) ⊆ t ≝ s sussume t µ (s) = t ⇒ t ⊆ µ (s) ≝ t sussume s

“Condizione necessaria e sufficiente affinché esista un matching tra termini s e t è che s “sussuma t” e t “sussuma” s.

Pattern Matching

• Importante variante dell’unificazione

– Mira a porre in corrispondenza un’espressione con un’altra espressione modello (template)

Definizione

Dato un insieme di espressioni {E

} ed una

espressione E, esiste un matching fra {E

} ed E se esiste una sostituzione σ tale che

σ ({E

}) = E

– Tipicamente non si consente che le variabili occorrano in entrambe le espressioni poste in corrispondenza

Pattern Matching

• Le nostre operazioni di matching non sono di solito simmetriche

– Modello da porre in corrispondenza con un fatto

• Definizione più debole di matching

• L’oggetto modello corrisponde (matches) ad un oggetto fatto se la formula che descrive il

modello si unifica con qualche

sottocongiunzione delle formule del fatto oggetto

– Si ha “matching” solo se la formula che descrive il modello è derivabile da quella che descrive il fatto – t → σ(s)

Pattern Matching

Esempio

• OSSERVAZIONE:

– forma(c1,rettangolo)∧forma(c2,cerchio) ∧ forma(c3,cerchio) ∧ grandezza(c1,media) ∧ grandezza(c2,piccola) ∧ grandezza(c3,piccola)

• MODELLO:

∃x ∃y ∃z forma (x, rettangolo ) ∧ forma (y, cerchio ) ∧ forma (z, cerchio)

C1

C2 C3

Proprietà dell’unificazione e del Matching.

Per l’unificazione del ordine valgono le seguenti proprietà:

1) L’unificazione è monotona.

L’unificazione aggiunge proprietà, non le sottrae. E’ impossibile rimuovere informazione da una struttura unificandola con un’altra.

Non vale per la generalizzazione

1) L’unificazione è commutativa ed associativa.

L’ordine delle unificazioni è irrilevante per il risultato finale.

• L’unificazione non è distributiva rispetto alla generalizzazione (e viceversa).

• L’unificazione è un processo di fusione dei vincoli.

Se le strutture sono viste come una codifica di informazioni sui vincoli, l’unificazione dovrebbe essere considerata un

processo di fusione dei vincoli. L’unificazione individua anche i casi in cui determinati insiemi di vincoli sono inconsistenti.

L’unificazione è bidirezionale; il matching è unidirezionale.

Il processo di “binding” delle variabili può avvenire in entrambe le strutture di unificazione e compare anche nella invocazione delle funzioni dei linguaggi di programmazione imperativi.

l’unificazione gestisce strutture definite parzialmente.

L’unificazione accetta input che contengono variabili non istanziate ed i suoi output possono contenere variabili non istanziate.