Intelligenza Artificiale
Metodologie di ragionamento
Prof. M.T. PAZIENZA
a.a. 2003-2004
Agire come un umano: test di Turing
Definizione operativa:
1. Elaborazione del linguaggio naturale
2. Rappresentazione della conoscenza
3. Ragionamento logico
4. Apprendimento automatico
Sistemi di ragionamento logico
Sistemi che ragionano esplicitamente con e sulla
conoscenza che è stata precedentemente
rappresentata: la rappresentazione ed il
ragionamento costituiscono le caratteristiche
principali di tali sistemi.
Vantaggio: Modularità
la struttura di controllo è isolata dalla conoscenza
che è indipendente dalle altre componenti il
sistema
Sistemi di ragionamento logico
tipologie
• Dimostratori di teoremi e linguaggi di programmazione
logica
• Sistemi di produzioni
• Sistemi a frame e reti semantiche
• Sistemi di logica descrittiva (logiche terminologiche)
Sistemi di ragionamento logico
attività fondamentali
1.
Aggiungere un nuovo fatto alla Base di conoscenza (BdC) (a
seguito di inferenza)
2.
Derivare fatti implicati da una BdC arricchita da un nuovo fatto
3.
Decidere se una interrogazione è implicata da una BdC
4.
Decidere se una interrogazione è immagazzinata esplicitamente
in una BdC
5.
Aggiornare/Cancellare una frase in una BdC
Mantenimento / Recupero
Informazioni in una BdC
• Definire tipi di dato per formule e termini
(Per tipo di dato intendiamo l’applicazione
di un operatore OP ad una lista di
argomenti P(x), Q(x))
• Memorizzare un insieme di formule S
STORE(KB,S)
• Recuperare formule S
FETCH(KB,S)
Mantenimento / Recupero
Informazioni in una BdC
Es.
Memorizza formule come lista collegata di congiunti
TELL ,   
TELL ,   
Lista di elementi , , , 
Ricerca sequenziale dell’elemento della lista che combacia
con la query Q fino a soddisfacimento o fine lista. Tempo
di ricerca (fetch) O(n). Tempo di memorizzazione (store)
O(1) se senza controllo di duplicati (inserisci in coda),
O(n) con controllo
Mantenimento / Recupero
Informazioni in BdC TavolaHash
• Tavola hash di formule di letterali ground (senza
variabili)
• STORE equivale ad assegnare valore V/F ad una
entry/chiave della tavola; O(1)
• FETCH effettua la ricerca diretta nella tavola; O(1)
Problemi:
non si gestiscono formule complesse
non si gestiscono variabili in frasi
Tavole Hash complesse
Chiave-- simbolo predicato
1. Lista letterali positivi per il predicato
2. Lista letterali negativi per il predicato
3. Lista di formule con predicato in conclusione
4. Lista di formule con predicato in premessa
Indicizzazione basata su tavole risulta ottima con molti
simboli di predicato e poche clausole per simbolo
Base di conoscenza
•
•
•
•
•
Fratello(Riccardo,Giovanni)
Fratello(Ted,Jack)
…
…
…
Tavole Hash complesse
• ASK(KB,Brother(Jack,Ted))
Indicizzazione basata su alberi
• Necessaria con molte clausole per un dato
simbolo di predicato
• Indicizzare gli argomenti oltre ai simboli di
predicato. Il processo di ricerca coincide
con la visita (discesa) di un albero
Indicizzazione basata su alberi
Indicizzazione basata su alberi
L’indicizzazione basata su alberi è una
indicizzazione combinata, perché usa una
chiave combinata della sequenza di simboli del
predicato e di argomenti dell’interrogazione.
Problemi:
La ricerca esplode con variabili nella sequenza.
Soluzione:
Indicizzazione incrociata: indirizza i valori in
diversi posti e per risolvere una interrogazione
comincia la ricerca nel posto più promettente.
Algoritmi di unificazione
L’unificazione di due affermazioni permette di
effettuare inferenze
• Conosce (John, x)=> Odia (John,x)
• Conosce (John, Jane)
Inferenza
• Odia (John, Jane)
Per realizzare l’inferenza corretta è necessario chiamare
l’algoritmo di unificazione molte volte.
Sistemi di programmazione
logica
La programmazione logica vede
il programma ed i suoi input come affermazioni
logiche sul mondo,
e
il processo in cui si rendono esplicite le
conseguenze come processo di inferenza.
Logica come ling. rappr. conoscenza
Vantaggi
Precisione: l’interpretazione delle formule (semantica) è
ben definita. Ci sono regole di inferenza corrette e
complete.
Flessibilità: la conoscenza è rappresentata in modo
dichiarativo, può essere utilizzata per processi diversi.
Modularità: le conoscenze (asserzioni) sono tra loro
indipendenti. Possono essere aggiunte (eliminate) in
modo incrementale senza dover modificare tutta la BdC
Logica come ling. rappr. conoscenza
Limiti
Atemporalità: le asserzioni sono indipendenti dal tempo
(Es. Bella(maria) asserisce la bellezza di Maria
indipendentemente dal tempo
Conoscenze certe: si può predicare il vero o il falso solo di
una conoscenza di cui si è certi
Scarsa leggibilità: una stessa entità è rappresentata da
enunciati tra loro indipendenti, per cui non si può
ricostruire la conoscenza complessiva su essa
Inefficienza: il processo di dimostrazione ha complessità
esponenziale
Reti semantiche
Le reti semantiche si basano su una metafora
grafica: gli oggetti del mondo (“individui o
categorie”) sono nodi di un grafo e le
“relazioni tra di loro” (detti anche ruoli) sono
archi del grafo
I nodi sono organizzati in una struttura
tassonomica
Gli archi tra i nodi rappresentano relazioni
binarie di diversa tipologia tra le categorie di
oggetti coinvolte
Reti semantiche
La semantica di una rete semantica può essere
enunciata fornendo gli equivalenti in logica
del primo ordine per le asserzioni nel
linguaggio della rete.
Reti semantiche
Imprecisa natura delle reti semantiche legata
al fatto che non si distingue tra nodi che
rappresentano classi e nodi che
rappresentano oggetti individuali
Distinguere le relazioni di appartenenza:
• Is-a (elemento / istanza di una classe )
• a-kind-of (sottoclasse)
Reti semantiche e Prolog
is-a di un elemento m con la classe c è
rappresentato dal fatto c(m)
a-kind-of di una sottoclasse c con una
superclasse s è rappresentato da s(X):-c(X)
Reti semantiche
Reti semantiche
Reti semantiche
Necessità di etichettare e direzionare gli archi
per identificare univocamente la relazione
Es.
• Mario compra una barca
versus
• Una barca è comprata da Mario
Reti semantiche
Permettono di gestire la semantica di una
frase del linguaggio naturale distinguendo
• Struttura superficiale
da
• Struttura profonda
del discorso
Reti semantiche ed Ereditarietà
Nelle reti semantiche l’ereditarietà permette
una forma particolare di inferenza
• Se un oggetto appartiene ad una classe,
esso eredita tutte le proprietà di quella
classe
L’ereditarietà si applica anche ai link di tipo akind-of
Una sottoclasse eredita (per ciascun suo
elemento) tutte le proprietà della
superclasse
Reti semantiche
L’uso delle reti semantiche in cui i nodi
rappresentino azioni individuali e gli archi
rappresentino oggetti aventi ruoli diversi in tali
azioni permette di costruire grafi complessi per
rappresentare scenari completi
Rappresentazione di frasi complesse ed articolate
Reti semantiche
Si possono avere anche archi che rappresentano
relazioni temporali
Se due azioni diverse puntano allo stesso nodo
tempo, il tempo delle due azioni può essere
considerato contemporaneo (si ipotizza che le
azioni accadono istantaneamente)
Reti semantiche
Fare inferenza da una rete semantica prevede
la ricerca di cammini particolari (ogni arco
attiva cammini soddisfacenti domande
diverse)
Ereditarietà ed eccezioni
Per gestire le eccezioni degli elementi reali di una
classe, si considera la semantica di
Rel(R,A,B) valore di default,
ovvero significa che B è un valore di default della
relazione R per i membri di A, ma tale valore
può essere sovrascritto da altra informazione
(principio della ereditarietà con eccezioni)
Reificazione (una relazione R diventa un oggetto,
non un predicato) come alternativa
Sussunzione ed istanziazione
Sussunzione: è una relazione tra due concetti
Un concetto A sussume un concetto B se tutte le
istanze di B sono necessariamente anche istanze di
A. (corrisponde alla relazione di sottoinsieme:
AB)
Istanziazione: è una relazione tra una istanza ed un
concetto (corrisponde alla relazione insiemistica di
appartenenza: AB)
DalmataCani
LuckyDalmata
Transitività della relazione ISA
La relazione ISA è transitiva:
Se
A ISA B
e
B ISA C
allora
A ISA C
Ereditarietà
La transitività della relazione ISA consente di
utilizzare il meccanismo della ereditarietà:
tutte le proprietà definite per un concetto A sono
ereditate, valgono per tutti i concetti sussunti da A
L’ereditarietà dei ruoli permette di ottenere grandi
vantaggi:
• Non viene duplicata la conoscenza
• Facilita la manutenzione della BdC
Ereditarietà
Algoritmo di ereditarietà per trovare una proprietà p di
una entità E, p(E), in una BdC:
0. Assegna al nodo corrente N il valore di E
1. SE esiste un valore per la proprietà p(N)
ALLORA riporta quel valore e fermati
2. SE c’è un nodo C tale che N ISA C oppure N
istanza di C
ALLORA
2.1 Assegna il valore di C al nodo N
2.2 Ritorna al passo 1
ALTRIMENTI fermati: hai fallito
Ereditarietà multipla
Per ereditarietà multipla si intende la
possibilità che un oggetto appartenga a più
di una categoria e che quindi possa ereditare
proprietà lungo percorsi differenti
(possibili conflittualità)
Ereditarietà multipla
Inferenze conflittuali risolvibili con informazioni
aggiuntive
Espansioni / Aggiornamenti
• La logica del primo ordine usa la funzione TELL per
aggiornare una base di conoscenza godendo della
proprietà di monotonia.
• L’ereditarietà con eccezioni è non monotona.
• Le logiche non monotone permettono di affermare
che una proposizione P è considerata vera fin
quando qualche realtà aggiuntiva non consente di
dimostrare che P è falsa.
Relazioni n-arie
Relazioni binarie sono la rappresentazione
degli archi tra una coppia di nodi di un
grafo.
Relazioni n-arie saranno espresse da predicati
n-ari con una lista ordinata di argomenti con
nomi specifici. Ciò permette di esprimere i
casi di frasi complesse di un linguaggio
naturale-> Grafi Concettuali
WordNet Miller, 1990
• Risorsa lessicale organizzata a rete
semantica (circa 125.000 termini)
• Termini raggruppati in insiemi di sinonimi
(circa 100.000 synset )
• http://cogsci.princeton.edu/wn/online
Entità in WordNet Miller, 1990
Concept: language<communication
Definition:
a systematic means of communicating by the use
of sounds or conventional symbols
Language<communication
Communication<social relation
Social relation<relation
Relation<abstraction
WordNet: esempi d’uso
1. Espansione di interrogazioni con sinonimi
nella ricerca basata su parole chiave
2. Distanza tra parole
3. Classe del termine (persona, organizzazione,
luogo, misura,…)
Espressività
Nelle reti semantiche non è possibile
rappresentare:
negazione
disgiunzione
quantificazione
Reti semantiche: vantaggi
Relativamente facili da comprendere per le persone
Alquanto efficienti da elaborare automaticamente
Sufficientemente potenti per poter rappresentare idee
e concetti anche complessi
Possono essere estese a rappresentare concetti
modali e temporali
Reti semantiche: limiti
Poco espressive (necessarie reti di grandi
dimensioni e complessità per rappresentare
concetti)
Non dispongono di una semantica formale
(non esiste un insieme di convenzioni
universalmente accettato su ciò che una rete
rappresenta)
Rappresentazione interna
Slot-assertion notation
Il calcolo dei predicati permette di indicare le
relazioni funzionali dei termini (o significato)
a seconda della posizione che essi occupano
nella formula
Nella notazione a slot i vari argomenti (slot) di
un predicato sono espressi come asserzioni
separate
Rappresentazione interna
Frame notation
Si usa una notazione con slot etichettati in cui le asserzioni
vengono coordinate all’interno di un’unica struttura,
detta frame (invece di essere separate come nella notazione a slot) che
include tutte le informazioni dell’evento; in tal modo, si
ottiene anche l’effetto di isolarlo dal resto delle
informazioni (contemporaneamente fenomeno di sicurezza o protezione
dell’accesso ad informazione non autorizzata).
Nel caso di coordinamento di più eventi, la
rappresentazione a frame presenta delle difficoltà nella
identificazione delle relazioni.
Frame Minsky, 1975
Assunzione: la conoscenza è organizzata in strutture
mentali complesse, i frame
(Minsky: quando si incontra una situazione nuova o
imprevista, viene evocata dalla memoria una struttura
mentale complessa la quale, mediante un processo di
istanziazione, viene adattato alla situazione specifica e
fornisce una chiave di interpretazione per essa)
Struttura dati per rappresentare “stereotipi”, ruolo
fondamentale dei default
Frame Minsky, 1975
Un frame rappresenta una situazione stereotipale:
una volta selezionato, si adatta alla realtà
modificandosi
Un frame contiene anche informazioni di tipo
procedurale, che indicano come effettuare
azioni. (definiscono delle aspettative; es. a
ristorante ci si aspetta una situazione ed un
insieme di azioni di un tipo particolare)
Struttura di un frame
Invece di avere un numero imprecisato di archi uscenti da
un nodo, si definisce un numero prefissato di slot per
rappresentare gli attributi di un oggetto
Ad un frame è associato:
• un nome (che identifica univocamente il frame nella
BdC)
• una relazione ISA ad un frame di livello più alto (per
ereditare gli slot di un livello più alto)
Ogni oggetto è un membro / istanza di una classe cui è
collegato da un link is-a
La classe indica il numero di slot validi a livello di classe ed
il nome di ciascuno slot
Frame: struttura dati
Collezione di coppie slot-filler (attributo-valore)
I filler possono essere di diversi tipi:
•
•
•
•
valore specifico
condizione sul valore, riferimento ad un altro frame
valore default (in assenza di un valore specifico)
una procedura da attivare quando lo slot riceve un valore (ifadded) o è richiesto il valore dello slot (if-needed)
Slot particolari sono IS ed ISA
Esempio: frame paziente-pediatria
ISA: Frame: PERSONA
*Slot: Cognome-Nome valore ereditato
• valore: Rossi Mario
• if-added: caratteri
Slot: Data ingresso
• valore: 4-4-2004
• if-added: data
Slot: Reparto
• valore:
• default: Pediatria
*Slot: Data nascita valore ereditato
• valore: 25-10-2000
• if-added: data
Frame e ragionamento per default
Il ragionamento per default usa conoscenza che si
suppone valga anche in mancanza di informazione
esplicita: le conclusioni sono rivedibili una volta che
si disponga di informazione certa
L’informazione esplicita sovrascrive quella di default
I ragionamenti per default non sono inferenze
logicamente valide (non possono essere rappresentati
con la logica)
Categorie ed oggetti
La maggior parte dei ragionamenti che si fanno, si
applicano alle categorie piuttosto che agli
individui
Se la conoscenza è organizzata in categorie (e
sottocategorie), è sufficiente classificare un
oggetto, tramite le proprietà percepite, per inferire
le proprietà della categoria a cui appartiene
FrameNet
Risorsa costituita da collezioni di frasi annotate
sintatticamente e semanticamente, organizzata in
frame
Semantica basata su frame: il significato delle parole
scaturisce dal ruolo che esse hanno nella struttura
concettuale delle frasi
La conoscenza è strutturata in 16 domini generali:
time, space, communications, cognition. Health,…
http://www.icsi.berkeley.edu/framenet/
Tassonomie
Le relazioni di sottoclasse organizzano la conoscenza
in tassonomia (es. in botanica, biologia, nelle
scienze librarie,..)
Reti semantiche per rappresentare conoscenza sul
mondo-Ontologie
Ontologie di dominio = tassonomie specializzate
Script Schank e Abelson 1977
Gli script implementano l’idea di rappresentare azioni ed
eventi usando una rete semantica
Ovvero l’intero insieme di azioni coincide con la
descrizione di cammini stereotipali
Gli script fanno uso dell’idea di default dove alla classe
sono associate le regole di una qualche azione ed
all’istanza di una classe corrispondono le istanze delle
azioni; in mancanza di informazione esplicita, è ancora
possibile interpretare una situazione
Script / storie
Analogo alla descrizione di storie
L’idea è che l’informazione è fornita per punti
generali ed associata alla classe
Sarà possibile rispondere ad una molteplicità
di domande correlando i punti generali ad
un unico tema condiviso per quella
specifica domanda
Sussunzione ed istanziazione
Sussunzione: è una relazione tra due concetti
Un concetto A sussume un concetto B se tutte le
istanze di B sono necessariamente anche istanze di
A. (corrisponde alla relazione di sottoinsieme:
AB)
Istanziazione: è una relazione tra una istanza ed un
concetto (corrisponde alla relazione insiemistica di
appartenenza: AB)
DalmataCani
LuckyDalmata
Transitività della relazione ISA
La relazione ISA è transitiva:
Se
A ISA B
e
B ISA C
allora
A ISA C
Ereditarietà
La transitività della relazione ISA consente di
utilizzare il meccanismo della ereditarietà:
tutte le proprietà definite per un concetto A sono
ereditate, valgono per tutti i concetti sussunti da A
L’ereditarietà dei ruoli permette di ottenere grandi
vantaggi:
• Non viene duplicata la conoscenza
• Facilita la manutenzione della BdC
Ereditarietà
Algoritmo di ereditarietà per trovare una proprietà p di
una entità E, p(E), in una BdC:
0. Assegna al nodo corrente N il valore di E
1. SE esiste un valore per la proprietà p(N)
ALLORA riporta quel valore e fermati
2. SE c’è un nodo C tale che N ISA C oppure N
istanza di C
ALLORA
2.1 Assegna il valore di C al nodo N
2.2 Ritorna al passo 1
ALTRIMENTI fermati: hai fallito
Ereditarietà multipla
Si parla di ereditarietà multipla quando un
concetto eredita da più di un sopraconcetto
La rete semantica non è più un albero, ma un
grafo
Si possono verificare casi di inconsistenza,
spesso non risolvibili