Intelligenza Artificiale - Parte B

Artificial Intelligence - Parte B

Riccardo La Marca

16 Aprile 2020

Contents

6 Logica del primo ordine 3

6.1 Sintassi della FOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

6.1.1 Modelli per la logica del primo ordine . . . . . . . . . . . . . . . . . . . . 3

6.1.2 I simboli della logica del primo ordine . . . . . . . . . . . . . . . . . . . . 4

6.1.3 Termini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

6.1.4 Formule atomiche e formule complesse . . . . . . . . . . . . . . . . . . . . 5

6.1.5 Quantificatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

6.2 Semantica della FOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

6.2.1 Termini vs. formule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6.2.2 Valutazione dei termini . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6.2.3 Valutazione delle formule . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

6.2.4 Soddisfacibilità, insoddisfacibilità, validità e modelli . . . . . . . . . . . . 14

6.3 Il mondo del wumpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

7 Inferenza nella FOL 16

7.1 Inferenza proposizionale e della FOL . . . . . . . . . . . . . . . . . . . . . . . . . 16

7.1.1 Regole di inferenza per i quantificatori . . . . . . . . . . . . . . . . . . . . 16

7.1.2 Riduzione all’inferenza proposizionale . . . . . . . . . . . . . . . . . . . . 19

7.2 Unificazione e lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7.2.1 Una regola di inferenza del primo ordine . . . . . . . . . . . . . . . . . . . 20

7.2.2 Unificazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

7.3 Concatenazione in avanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7.3.1 Clausole definite del primo ordine . . . . . . . . . . . . . . . . . . . . . . 22

7.3.2 Un semplica algoritmo di concatenazione in avanti . . . . . . . . . . . . . 23

7.3.3 Concatenazione in avanti efficiente . . . . . . . . . . . . . . . . . . . . . . 25

7.3.4 Fatti rilevanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

7.4 La risoluzione come regola di inferenza . . . . . . . . . . . . . . . . . . . . . . . . 26

8 Pianificazione classica 28

8.1 Definizione di pianificazione classica . . . . . . . . . . . . . . . . . . . . . . . . . 28

8.1.1 Il mondo dei blocchi - Toy problem . . . . . . . . . . . . . . . . . . . . . . 31

8.2 Algoritmi di pianificazione con ricerca nello spazio degli stati . . . . . . . . . . . 32

8.2.1 Ricerca in avanti nello spazio degli stati . . . . . . . . . . . . . . . . . . . 32

8.2.2 Ricerca all’indietro nello spazio degli stati . . . . . . . . . . . . . . . . . . 33

8.2.3 Euristiche per la pianificazione . . . . . . . . . . . . . . . . . . . . . . . . 34

8.3 Altri approcci classici alla pianificazione . . . . . . . . . . . . . . . . . . . . . . . 36

1

8.3.1 Pianificazione classica come problema SAT . . . . . . . . . . . . . . . . . 36

8.3.2 Pianificazione come deduzione FOL: situation calculus . . . . . . . . . . . 38

8.3.3 Pianificazione come soddisfacimento di vincoli . . . . . . . . . . . . . . . . 40

9 Incertezza 41

9.1 Agire in condizioni di incertezza . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

9.2 Le cause dell’incertezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

9.3 Gestione dell’incertezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

9.3.1 Incertezza e decisioni razionali . . . . . . . . . . . . . . . . . . . . . . . . 42

9.4 Probabilità in IA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

9.4.1 Indipendenza ed indipendenza condizionale . . . . . . . . . . . . . . . . . 46

9.5 Ragionamento probabilistico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

9.5.1 Rappresentazione della conoscenza in un dominio certo . . . . . . . . . . 49

9.5.2 Semantica delle reti bayesiane . . . . . . . . . . . . . . . . . . . . . . . . . 51

9.5.3 Inferenza esatta nelle reti bayesiane . . . . . . . . . . . . . . . . . . . . . 56

10 Decisioni semplici 60

10.1 Combinare credenze e desideri in condizioni di incertezza . . . . . . . . . . . . . 60

10.2 Le basi della teoria dell’utilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

10.2.1 Vincoli su preferenze razionali . . . . . . . . . . . . . . . . . . . . . . . . . 61

10.3 Funzioni di utilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

10.3.1 L’utilità del denaro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

10.3.2 Scale e valutazione di utilità . . . . . . . . . . . . . . . . . . . . . . . . . . 65

10.3.3 Funzioni di utilità multiattributo . . . . . . . . . . . . . . . . . . . . . . . 65

10.4 Reti di decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

10.4.1 Valutazione delle reti di decisione . . . . . . . . . . . . . . . . . . . . . . . 67

11 Apprendimento dalle osservazioni 68

11.1 Forme di apprendimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

11.2 Apprendimento induttivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

11.3 Apprendere alberi di decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

11.3.1 Alberi di decisione come elementi esecutivi . . . . . . . . . . . . . . . . . 70

11.3.2 Espressività degli alberi di decisione . . . . . . . . . . . . . . . . . . . . . 71

11.3.3 Induzione di alberi di decisione dagli esempi . . . . . . . . . . . . . . . . . 72

11.3.4 Valutare le prestazioni dell’algoritmo di apprendimento . . . . . . . . . . 76

12 Storico degli aggiornamenti 78

2

Chapter 6

Logica del primo ordine

Nell’ultimo capitolo della Parte A abbiamo visto come un agente basato sulla conoscenza potrebbe

rappresentare il mondo in cui opera e dedurre le azioni che deve intraprendere. Come linguaggio

di rappresentazione abbiamo usato la logica proposizionale, sufficiente per presentare i concetti

base della logica e degli agenti basati sulla conoscenza. Sfortunatamente, la logica proposizionale

è un linguaggio troppo poco potente per rappresentare la conoscenza in ambienti complessi in

modo compatto.

In questo capitolo prenderemo in esame la logica del primo ordine (FOL, First Order

Logic), che è sufficientemente espressiva per rappresentare buona parte della nostra conoscenza

comune.

6.1 Sintassi della FOL

Come ben sappiamo, per definire una logica, come prima cosa dobbiamo specificarne la sintassi

e nel seguito la semantica. Se ci ricordiamo la sintassi ci esprime se una frase, o meglio formula

della logica, sia ”ben formata” oppure no. Per fare questo abbiamo bisogno di specificare quali

sono queste formule, come si creano e di conseguenza dobbiamo presentare l’alfabeto della logica

che vogliamo descrivere (nel nostro caso la FOL). Prima di tutto però cominciamo specificando

in modo più preciso il modo in cui i mondi possibili della logica del primo ordine riflettono

l’impegno ontologico nei confronti di oggetti e relazioni.

6.1.1 Modelli per la logica del primo ordine

Ricorderete dal Capitolo 5 che i modelli di un linguaggio logico sono le strutture formali che

costituiscono i mondi possibili che possono essere presi in considerazione. Ogni modello collega

il vocabolario delle formule logiche ad elementi del mondo possibile, in modo che possa essere

determinata la verità di qualsiasi formula. Quindi, i modelli della logica proposizionale collegano

simboli a valori di verità predefiniti.

I modelli della logica del primo ordine sono molto più interessanti: per prima cosa, contengono

oggetti! Il dominio di un modello è l’insieme degli oggetti che contiene, chiamati appunti

elementi del dominio. Il dominio non deve essere vuoto: ogni mondo possibile deve contenere

almeno un oggetto. Gli oggetti del modello possono essere messi in relazione in molti mondi.

1

Formalmente, una relazione non è altro che un insieme di tuple di oggetti collegati . Alcuni

1 Una tupla è una collezione ordinata di oggetti, e si scrive racchiusa tra parentesi angolari.

3

tipi di relazioni si possono considerare meglio come funzioni, in quanto ogni dato oggetto può

essere collegato attraverso di esse a esattamente un altro oggetto. Se vogliamo essere formali,

dobbiamo dire che i modelli nella logica del primo ordine richiedono funzioni totali, ovvero che

ci dev’essere un valore per ogni tupla di input.

Fin qui abbiamo descritto gli elementi dei modelli per la logica del primo ordine. L’altra

parte essenziale di un modello è il collegamento tra questi elementi e il vocabolario delle formule

logiche, che spieghiamo nel seguito. Come prima cosa diamo la definizione di alfabeto della

FOL. V

Definizione 6.1.1. L’alfabeto della logica di primo ordine è dato da: insieme di variabili;

F P

un insieme di simboli di funzione; un insieme di simboli di predicato; connettivi

∀, ∃

logici (dalla logica proposizionale); i quantificatori quali ”per ogni” ed o ”esiste” denotati

rispettivamente quantificatore universale ed esistenziale.

6.1.2 I simboli della logica del primo ordine

Gli elementi sintattici base sono i simboli utilizzati per indicare gli oggetti, le relazioni e le

funzioni. Di conseguenza ce ne sono tre tipi: simboli di costante, che rappresentano gli oggetti;

simboli di predicato, che rappresentano le relazioni; simboli di funzione, che rappresentano

appunto le funzioni. Ogni simbolo di predicato e di funzione ha una specifica arità che ne indica

2

il numero di argomenti .

Vediamo qualche esempio di simboli di funzione con i loro significati ”intuitivi”: zero/0

(simbolo di costante), succ/1 dove succ(X) è il numero naturale X + 1, socrate/0 rappresenta

l’individuo ”Socrate” e padre/1 dove padre(X) rappresenta il padre dell’individuo X.

Presentiamo adesso qualche esempio di simboli di predicati: doppio/2 dove doppio(X, Y ) rap-

presenta che il numero naturale Y è il doppio di X, somma/3 dove somma(X, Y, Z) rappresenta

che il numero naturale Z è la somma di X ed Y, uomo/1 dove uomo(X) mi dice che l’individuo

X è un uomo e mortale/1 dove mortale(X) mi rappresenta che l’individuo X è mortale.

6.1.3 Termini

A partire dall’alfabeto si può definire il linguaggio della logica del primo ordine. Questo linguaggio

ha una struttura sintattica più complessa di quello della logica proposizionale: la sua definizione

induttiva dovrebbe essere effettuata in due passi, prima definendo il linguaggio dei termini, e

dopo il linguaggio delle formule che presenteremo nella prossima sezione.

Un termine è un’espressione logica che si riferisce ad un oggetto. I simboli di costante sono

quindi termini, ma non è sempre il caso di assegnare un simbolo distinto a ogni oggetto: ad

esempio, nel linguaggio di tutti i giorni useremo l’espressione ”la gamba sinistra di Marco” e non

le daremo certo un nome specifico. Questo è proprio lo scopo dei simboli di funzione; invece di

usare un simbolo di costante, potremo scrivere GambaSinistra(M arco). Nel caso generale, un

termine complesso è formato da un simbolo di funzione seguito da una lista tra parentesi dei suoi

argomenti, costuiti a loro volta da termini. Diamo adesso una definizione più formale di cosa sia

un termine.

2 I simboli di costante hanno arità nulla, pari a 0, e sono più vicini alle lettere proposizionali.

4

Definizione 6.1.2. L’insieme dei termini è definito induttivamente come segue:

ˆ V

Ogni variabile in è un termine

ˆ F

Ogni simbolo di costante in è un termine

ˆ ∈ F)

Se f è un simbolo di funzione (f t.c. f /n con n > 0 e t , . . . , t sono termini, allora

1 n

anche f (t , . . . , t ) è un termine.

1 n

Esempio

F {zero/0,

Siano = succ/1, socrate/0, padre/1} simboli di funzione e X, M iaV ariabile vari-

abili. Allora le seguenti sequenze di simboli sono termini

zero padre(padre(socrate))

M iaV ariabile padre(succ(X))

succ(zero) succ(succ(zero))

6.1.4 Formule atomiche e formule complesse

Ora che possiamo riferirci agli oggetti con i termini e alle relazioni con i simboli di predicato,

possiamo mettere insieme le due cose per dare origine a formule atomiche capaci di asserire

fatti, e tramite di queste e con l’uso dei connettivi logici e dei quantificatori, che presentiamo

nella sezione successiva, possiamo costruire anche le formule complesse. Diamo quindi una

definizione formale

Definizione 6.1.3. L’insieme delle formule è definito induttivamente come seguen

ˆ Se p è un simbolo di predicato di arità n > 0 e t , . . . , t sono termini, allora p(t , . . . , t )

1 n 1 n

è detta formula atomica.

ˆ Se φ e ψ sono formule, lo sono anche ∧

(φ) φ ψ

¬φ ⇒

φ ψ

∨ ⇐⇒

φ ψ φ ψ

ˆ 3

∈ V

Se φ è una formula e X allora anche (∀X φ) e (∃X φ) sono formule. .

Esempio

F {zero/0, P {doppio/2,

Siano = succ/1, socrate/0, padre/1} e = somma/3, mortale/1}

rispettivamente l’insieme dei simboli di funzione e l’insieme dei simboli di predicato, allora le

seguenti sequenze di simboli sono formule:

doppio(succ(succ(zero)), X)

∃X doppio(succ(succ(zero)), X)

∀X doppio(succ(succ(zero)), X)

3 Le parentesi non fanno parte delle formule create, sono state inserite solo per fare compromettere la leggibilità.

5

somma(succ(zero), zero, succ(zero))

∀X ∀Y ⇒

somma(X, X, Y ) doppio(X, Y )

∃Y ∧ ∀J ∃K

(∀X doppio(X, Y )) (∀I somma(I, J, K))

∧

mortale(socrate) mortale(padre(socrate))

X = socrate

⇒ ∧

(∀X uomo(X) mortale(X)) uomo(socrate)

Mentre le seguenti sequenze di simboli non sono formule

succ(zero)

mortale(mortale(socrate))

padre(mortale(X))

∃ socrate mortale(socrate)

∃X padre(X)

∧

zero zero

∧

X zero =

6.1.5 Quantificatori

Avendo a disposizione una logica basata sugli oggetti, è naturale che si desideri esprimere carat-

teristiche di intere collezioni di oggetti senza doverli enumerare uno per uno. I quantificatori

ci permettono di farlo. La logia del primo ordine comprende due quantificatori standard, quello

universale e quello esistenziale.

Quantificatore universale (∀)

Chiunque saprebbe riconoscere questo simbolo ed associarlo alla frase che comincia con ”per

ogni”. Nella logica del primo ordine ne facciamo uso per esprimere delle leggi generali che non

avremmo potuto esprimere nella logica proposizionale. Un esempio di formula che utilizza tale

simbolo è la seguente ∀ ⇒

x uomo(x) mortale(x)

la quale può essere tradotta con la frase ”per ogni x, se x è un uomo, allora x è mortale”, dove

4

∈ V

ovviamente x .

Intuitivamente la formula (∀ x P ), dove P è una qualsiasi espressione logica, afferma che

P è vera per ogni oggetto x. Più precisamente, (∀ x P ) è vera in un dato modello se P è vera

in tutte le possibile interpretazioni estese costruite a partire dall’interpretazione fornita nel

modello, dove ogni interpretazione estesa specifica un elemento del dominio a cui x fa riferimento.

Consideriamo i seguenti cinque mondi

→

x Riccardo Cuor di Leone

→

x Re Giovanni

→

x la gamba sinistra di Riccardo

→

x la gamba sinistra di Giovanni

→

x la corona

4 Un termine che non comprende variabili viene detto termine ground.

6

∀ ⇒

La formula universalmente quantificata x Re(x) P ersona(x) è vera nel modello originale

5

⇒

se la formula Re(x) P ersona(x) è vera in ognuno delle cinque interpretazioni estese .

Quantificatore esistenziale (∃)

La quantificazione universale permette di descrivere formule che riguardano tutti gli oggetti. In

modo analogo, è possibile formulare enunciati circa alcuni oggetti dell’universo senza citarli per

nome, usando un quantificatore esistenziale. Per dire ad esempio, che Re Giovanni ha una corona

sulla testa, scriviamo ∃ ∧

x Corona(x) SullaT esta(x, Giovanni)

∃ x si legge ”esiste x tale che...” o anche ”per qualche x ...”.

Intuitivamente, la formula (∃ x P ) afferma che P è vera per almeno un oggetto x. Più

precisamente, (∃ x P ) è vera in un dato modello se P è vera in almeno una Interpretazione

estesa che assegna a x un elemento del dominio.

Quantificatori annidati

Spesso vorremo esprimere formule più complesse utilizzando più quantificatori. Il caso più sem-

plice si ha quando i quantificatori sono dello stesso tipo: ad esempio, ”i fratelli sono consanguinei”

può essere scritto come: ∀ ∀ ⇒

x y F ratello(x, y) Consanguineo(x, y)

Quantificatori consecutivi dello stesso tipo possono essere scritti anche usando un solo quantifi-

catore con più variabili. Per dire, ad esempio, che la consanguineità è una relazione simmetrica,

possiamo scrivere: ∀ ⇐⇒

x, y Consanguineo(x, y) Consanguineo(y, x)

In altri casi potrà capitare di mescolare quantificatori diversi. Dire che ”ognuno ama qualcuno”

può essere scritto: ∀ ∃

x y Ama(x, y)

D’altra parte, per affermare che ”c’è qualcuno che è amato da tutti” scriviamo

∃ ∀

y x Ama(x, y)

L’ordine con cui sono scritti i quantificatori, quindi, è molto importante. Per rendere la formula

∀

più chiara possiamo inserire delle parentesi: x (∃ y Ama(x, y)).

Qualche confusione potrebbe nascere nel momento in cui diversi quantificatori sono applicati

alla stessa variabile: considerate la seguente formula

∀ ∨

x (Corona(x) (∃ x F ratello(Riccardo, x)))

Qui la x in (Fratello(Riccardo, x)) è quantificata esistenzialmente. La regola è che la variabile

”appartiene” al quantificatore più interno che la menziona; quindi non sarà più soggetta a nes-

sun’altra quantificazione.

5 Da notare che per adesso stiamo