Sistemi Intelligenti

Sistemi Intelligenti 2022

Contents

1 Introduzione 6

1.1 Turing Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Strong e Weak AI 7

3 Agenti e Ambienti 7

3.1 Caratteristiche dell'ambiente . . . . . . . . . . . . . . . . . . . 8

4 Non-AI software 9

5 AI software 9

6 Automazione vs Autonomia 10

7 Razionalità di un agente 11

8 Quali classi di problemi si prestano ad essere risolti dall'AI? 12

9 Risoluzione automatica di problemi 12

9.1 Obiettivi e ricerca . . . . . . . . . . . . . . . . . . . . . . . . . 13

9.2 Denizione formale di un problema . . . . . . . . . . . . . . . 14

9.3 Metodi di ricerca non informati - Blind Search . . . . . . . . . 14

9.3.1 Grafo di ricerca . . . . . . . . . . . . . . . . . . . . . . 15

9.4 Nodi creati e nodi esplorati . . . . . . . . . . . . . . . . . . . 16

9.5 Criteri di valutazione delle strategie . . . . . . . . . . . . . . . 16

9.6 Lista delle strategie . . . . . . . . . . . . . . . . . . . . . . . . 17

9.7 Ricerca in ampiezza . . . . . . . . . . . . . . . . . . . . . . . . 17

9.7.1 Valutazione della ricerca in ampiezza . . . . . . . . . . 17

1

9.8 Ricerca a costo uniforme . . . . . . . . . . . . . . . . . . . . . 18

9.8.1 Valutazione dell'algoritmo di ricerca a costo uniforme . 18

9.9 Ricerca in profondità senza backtracking . . . . . . . . . . . . 19

9.10 Ricerca in profondità con Backtracking . . . . . . . . . . . . . 19

9.10.1 Valutazione della ricerca in profondità . . . . . . . . . 19

9.11 Variante: Ricerca a profondità limitata . . . . . . . . . . . . . 20

9.11.1 Potenziali problemi . . . . . . . . . . . . . . . . . . . . 20

9.12 Iterative Deepening . . . . . . . . . . . . . . . . . . . . . . . . 20

9.12.1 Valutazione dell'iterative deepening . . . . . . . . . . . 21

9.13 Ricerca bidirezionale . . . . . . . . . . . . . . . . . . . . . . . 21

9.13.1 Valutazione della Ricerca bidirezionale . . . . . . . . . 22

10 Metodi di ricerca informati 22

10.1 Ricerca Greedy (avara) . . . . . . . . . . . . . . . . . . . . . . 23

10.1.1 Problemi . . . . . . . . . . . . . . . . . . . . . . . . . . 23

10.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

∗

A

10.2.1 Pseudocodice di . . . . . . . . . . . . . . . . . . . . 24

∗

A

10.3 Ottimalità di . . . . . . . . . . . . . . . . . 25

per gli alberi

∗

A

10.3.1 Dimostrazione . . . . . . . . . . . . . . . . . . . . . . . 25

10.4 Ottimalità di per i gra . . . . . . . . . . . . . . . . . . . . 27

∗

A

10.4.1 Considerazioni su . . . . . . . . . . . . . . . . . . . 28

∗

A

10.4.2 Considerazioni sull'euristica . . . . . . . . . . . . . . . 28

10.5 Euristiche monotone ed ammissibili . . . . . . . . . . . . . . . 29

10.6 Funzioni euristiche . . . . . . . . . . . . . . . . . . . . . . . . 29

10.6.1 Valutazione della bontà di un'euristica . . . . . . . . . 29

11 Strategie di ricerca con avversario 31

11.1 Dierenze con la ricerca informata e con la ricerca blind . . . 32

11.2 Possibili approcci . . . . . . . . . . . . . . . . . . . . . . . . . 32

11.3 Costruzione delle strategie . . . . . . . . . . . . . . . . . . . . 33

11.3.1 Funzione di valutazione . . . . . . . 34

valoreMinimax(n)

11.3.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . 35

11.3.3 Valutazione dell'algoritmo . . . . . . . . . . . . . . . . 36

11.4 Minimax con Potatura Alfa-Beta . . . . . . . . . . . . . . . . 36

11.4.1 Algoritmo Alfa-Beta . . . . . . . . . . . . . . . . . . . 37

11.4.2 Confronto fra alpha-beta pruning e minimax . . . . . . 38

11.4.3 Uso di alfa-beta pruning nei contesti real time . . . . . 39

2

12 Constraint Satisfaction Problems 41

12.1 CSP e problemi di ricerca . . . . . . . . . . . . . . . . . . . . 41

12.1.1 Domini delle variabili . . . . . . . . . . . . . . . . . . . 42

12.1.2 Arità dei vincoli . . . . . . . . . . . . . . . . . . . . . . 42

12.1.3 Vincoli vs Criteri di preferenza . . . . . . . . . . . . . 42

12.2 Blind search: brute force . . . . . . . . . . . . . . . . . . . . . 43

12.2.1 Generate and Test . . . . . . . . . . . . . . . . . . . . 43

12.2.2 Importanza della rappresentazione di un problema . . . 43

12.2.3 Ricerca in profondità con backtracking . . . . . . . . . 43

12.2.4 Ricerca con backtracking - Osservazioni . . . . . . . . . 44

12.2.5 Euristiche di scelta della variabile . . . . . . . . . . . . 45

12.3 Rendere informata la ricerca . . . . . . . . . . . . . . . . . . . 45

12.4 Tecniche e Proprietà per la propagazione di informazioni . . . 46

12.4.1 Forward Checking . . . . . . . . . . . . . . . . . . . . . 47

12.4.2 Node consistency . . . . . . . . . . . . . . . . . . . . . 47

12.4.3 Arc consistency . . . . . . . . . . . . . . . . . . . . . . 47

12.5 ARC-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

12.6 Commenti su Arc Consistency . . . . . . . . . . . . . . . . . . 49

12.7 Path Consistency . . . . . . . . . . . . . . . . . . . . . . . . . 49

12.8 Generalizzazione: k-consistency . . . . . . . . . . . . . . . . . 50

12.8.1 Vincoli Speciali . . . . . . . . . . . . . . . . . . . . . . 51

12.9 Migliorare ulteriormente il Backtracking . . . . . . . . . . . . 52

12.9.1 Costruzione di un conict set . . . . . . . . . . . . . . 53

12.9.2 Algoritmo Backjump . . . . . . . . . . . . . . . . . . . 53

13 Rappresentazione della Conoscenza 54

13.1 Programmazione di agenti basati sulla conoscenza . . . . . . . 55

13.2 Applicazione di meccanismi automatici sulla KB . . . . . . . . 55

13.3 Logica proposizionale . . . . . . . . . . . . . . . . . . . . . . . 58

13.3.1 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . 58

13.4 Background Knowledge come formule logiche . . . . . . . . . . 58

13.5 Come dimostrare la conseguenza logica . . . . . . . . . . . . . 59

13.5.1 Theorem Proving . . . . . . . . . . . . . . . . . . . . . 60

13.6 Formulazione come problema di ricerca nello spazio degli stati 62

13.7 Regola di risoluzione . . . . . . . . . . . . . . . . . . . . . . . 62

13.8 Clausole di Horn . . . . . . . . . . . . . . . . . . . . . . . . . 64

13.8.1 Forward Chaining . . . . . . . . . . . . . . . . . . . . . 64

13.8.2 Backward chaining . . . . . . . . . . . . . . . . . . . . 65

3

14 Logica del prim'ordine 66

14.1 Enumerazione dei modelli e conseguenza logica . . . . . . . . . 70

14.2 Termini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

14.3 Formule atomiche . . . . . . . . . . . . . . . . . . . . . . . . . 71

14.4 Quanticatori . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

14.5 DataBase semantics . . . . . . . . . . . . . . . . . . . . . . . . 72

14.6 Interrogazione di KB in FOL . . . . . . . . . . . . . . . . . . . 73

14.6.1 Sostituzione . . . . . . . . . . . . . . . . . . . . . . . . 73

14.7 Ragionamento automatico in FOL . . . . . . . . . . . . . . . . 73

14.8 Proposizionalizzazione . . . . . . . . . . . . . . . . . . . . . . 74

14.8.1 Confronto fra IU e IE . . . . . . . . . . . . . . . . . . . 75

14.8.2 Problema delle funzioni . . . . . . . . . . . . . . . . . . 75

14.9 Guidare la scelta della sostituzione . . . . . . . . . . . . . . . 76

14.10Modus Ponens Generalizzato . . . . . . . . . . . . . . . . . . . 76

14.11Unicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

15 Clausole di Horn in FOL 78

15.1 Forward Chaining in FOL . . . . . . . . . . . . . . . . . . . . 78

15.1.1 Proprietà del Forward Chaining . . . . . . . . . . . . . 78

15.2 Backward Chaining in FOL . . . . . . . . . . . . . . . . . . . 78

15.2.1 Valutazione del Backward Chaining . . . . . . . . . . . 79

16 Lifting di Risoluzione e Refutazione 79

16.1 Valutazione della risoluzione . . . . . . . . . . . . . . . . . . . 80

17 Costruire una KB in FOL - Knowledge Engeneering 81

17.1 Concettualizzazione . . . . . . . . . . . . . . . . . . . . . . . . 81

17.2 T-box e A-box . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

18 Uso delle ontologie 83

18.1 Semantic Web . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

18.2 RDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

18.3 Costruzione di un'ontologia . . . . . . . . . . . . . . . . . . . 83

18.4 OWL 2 - Web Ontology Language . . . . . . . . . . . . . . . . 84

18.4.1 Semantica diretta . . . . . . . . . . . . . . . . . . . . . 84

18.4.2 Semantica basata su RDF . . . . . . . . . . . . . . . . 84

18.5 Modelli di conoscenza in OWL . . . . . . . . . . . . . . . . . . 84

18.6 Matching di ontologie . . . . . . . . . . . . . . . . . . . . . . . 85

4

18.6.1 Relazioni fra ontologie . . . . . . . . . . . . . . . . . . 85

18.7 OWL2 e DB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

19 Rappresentazione delle azioni 86

19.1 Situation Calculus . . . . . . . . . . . . . . . . . . . . . . . . 86

19.2 Assiomi di Applicabilità . . . . . . . . . . . . . . . . . . . . . 87

19.3 Assiomi di Eetto . . . . . . . . . . . . . . . . . . . . . . . . . 88

19.4 Inferenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

19.5 Frame Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 88

20 Agenti 89

20.1 Caratterizzazione dell'ambiente . . . . . . . . . . . . . . . . . 91

20.2 Architetture degli agenti . . . . . . . . . . . . . . . . . . . . . 92

20.3 Agenti reattivi semplici . . . . . . . . . . . . . . . . . . . . . . 92

20.4 Agenti basati su modello . . . . . . . . . . . . . . . . . . . . . 93

20.5 Agenti basati su obiettivi . . . . . . . . . . . . . . . . . . . . . 94

20.6 Agenti basati sull'utilità . . . . . . . . . . . . . . . . . . . . . 95

20.7 Agenti che apprendono . . . . . . . . . . . . . . . . . . . . . . 95

20.8 Multi-agent Systems . . . . . . . . . . . . . . . . . . . . . . . 95

21 Classicazione 96

21.1 Matrice di confusione . . . . . . . . . . . . . . . . . . . . . . . 97

21.2 Omogenità dei Test Set . . . . . . . . . . . . . . . . . . . . . . 98

21.3 Alberi Decisionali . . . . . . . . . . . . . . . . . . . . . . . . . 99

21.4 Costruzione di un albero decisionale - Algoritmo di Hunt . . . 99

21.5 Valutazione di un modello . . . . . . . . . . . . . . . . . . . . 103

21.5.1 Valutazioni fatte su test set: . . . . . . . . . . . . . . . 103

21.5.2 Confronto fra modelli diversi . . . . . . . . . . . . . . . 103

22 Classicatori a Regole 104

22.1 Calcolo della qualità di una regola . . . . . . . . . . . . . . . . 104

22.2 Produzione delle regole . . . . . . . . . . . . . . . . . . . . . . 105

22.2.1 Sequential Covering . . . . . . . . . . . . . . . . . . . . 105

22.3 Learn one rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

22.4 Lazy Learners . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

22.4.1 Calcolo della classe con KNN . . . . . . . . . . . . . . 107

5

23 Reti Neurali 108

23.1 Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

23.2 Apprendimento . . . . . . . . . . . . . . . . . . . . . . . . . . 108

23.3 Reti Neurali . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

23.4 Multi-Layer Perceptron . . . . . . . . . . . . . . . . . . . . . . 109

23.5 Apprendimento per le Reti Neurali . . . . . . . . . . . . . . . 110

23.6 Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . 111

23.6.1 Caso con un solo neurone di output . . . . . . . . . . . 111

23.7 Neuroni Hidden . . . . . . . . . . . . . . . . . . . . . . . . . . 111

1 Introduzione

Fino agli anni '50, tutto ciò che riguardava l'intelligenza articiale era rela-

tivo a speculazioni losoco-etiche, in quanto la tecnologia non permetteva

(neanche oggi siamo in grado di produrre un AI forte) di sperimentare diret-

tamente sulle macchine.

Ci si domanda su quali siano i requisiti per poter denire un agente arti-

ciale .

intelligente

Una macchina può "pensare" ed essere considerata intelligente?

ˆ Turing Test

ˆ

1.1 Turing Test

Ha come scopo quello di capire se un computer sia intelligente o meno.

Il test è articolato come segue: abbiamo una prima persona detta inter-

, posta di fronte ad un muro/tenda. Non può dunque vedere cosa si

locutore

cela dietro di esso/essa.

Dall'altro lato della tenda, abbiamo rispettivamente un computer (di cui

dobbiamo stabilire l'intelligenza) ed un'altra persona.

L'interlocutore può comunicare con l'altro lato della tenda solo testual-

mente.

La macchina viene denita intelligente nel momento in cui l'interlocutore

non è in grado di distinguere una risposta fornita dalla macchina

da una risposta fornita dalla persona .

Questo test è suciente per denire la macchina come ?

intelligente

In altre parole, 6

Il fatto che di fronte agli stessi input una macchina ed un uomo prod-

ucano gli stessi output, signica che entrambi cosa stanno

capiscono

facendo?

In questo caso stiamo facendo combaciare l'intelligenza con la compren-

capisca

sione. Possiamo facilmente smentire il fatto che il computer

cosa stia facendo, usando lo stesso scenario del Test di Turing,

ma al posto del computer mettiamo una persona che non parla

la lingua con cui sono scritti i testi a cui risponde, ma ha ricevuto

La persona non

istruzioni su come rispondere agli stimoli. comprende

il linguaggio, ma si comporta esattamente come una macchina di Turing.

.

Il Test di Turing non è un valido metro di intelligenza

2 Strong e Weak AI

1. Si tratta dello

Strong AI: è possibile riprodurre l'intelligenza umana?

studio del pensiero e del comportamento umano (scienze cognitive)

2. Weak AI: è possible trovare dei modi per risolvere dei problemi che,

Task-oriented:

se risolti da esseri umani, richiederebbero intelligenza?

si tratta dello studio del pensiero del comportamento razionale.

e

Si tratta di strumenti in grado di arontare un singolo problema alla

volta, e lo fanno come lo farebbe una persona, senza cercare di essere

Sono orientati alla risoluzione di problemi, ma sono in

una persona.

grado di risolvere un solo problema. Non sono intelligenti in senso lato,

a tutto tondo.

3 Agenti e Ambienti

Il binomio è un binomio imprescindibile: l'agente ha senso

agente-ambiente

solo se considerato in un ambiente, e l'ambiente è tale poichè composto da

agenti. 7

: astrazione che rappresenta un qualsiasi sistema che per-

Agente

cepisce il proprio ambiente tramite i sensori ed agisce su di esso tramite

i suoi attuatori.

L'iterazione base di un agente è la seguente:

Percepisce Delibera Agisce

→ →

A seconda dei sensori ed attuatori di un agente, posso avere un binomio

agente-ambiente più o meno funzionale.

Per intendiamo il processo interno di un agente tramite il quale

deliberare

stabilisce l'azione da compiere.

L'agente può essere dotato di sico oppure essere solo software, non è

prerogativa necessaria la sicità. L'azione svolta dall'agente può anche non

modicare l'ambiente in cui si trova. Può anche non compiere azioni.

3.1 Caratteristiche dell'ambiente

: può essere parziale o totale, in base al fatto che i sensori

Osservabilità

ˆ dell'agente diano accesso a tutti gli aspetti dell'ambiente rilevanti per

la deliberazione, o meno. , in base al fatto che lo stato successivo

Deterministico/Stocastico

ˆ sia determinato, o meno. (Stocastico: applicando più volte la stessa

azione nelle stesse circostanze, ottengo risultati diversi)

. Episodico: l'esperienza degli agenti è divisa

Episodico/Sequenziale

ˆ in episodi atomici, ovvero una singola percezione seguita da una singola

azione. Sequenziale: Attività composta da più passi, ognuna delle quali

inuenzerà le successive.

in base al fatto che l'ambiente non cambi mentre

Statico/Dinamico:

ˆ l'agente pensa, o meno.

: possono essere discreti o continui gli stati, tempo,

Discreto/Continuo

ˆ percezioni e azioni. : in base al fatto che nell'ambiente sia

Singolo agente/Multiagente

ˆ presente uno o più agenti. 8

N.B.: Vi è una connessione fra il fatto che un ambiente sia parzialmente

osservabile ed il fatto che sia stocastico. Spesso viene visto come

stocastico un ambiente che è parzialmente osservabile perchè

non si ha la percezione di quegli aspetti che renderebbero

deterministico il mondo.

4 Non-AI software

Risolve un singolo compito

ˆ Tipicamente strutturato come una sequenza di passi: scrivo un algo-

ˆ ritmo che risolva uno specico problema.

Esplico si facciano le cose.

come

ˆ

5 AI software

Separa una descrizione dichiarativa da un programma generale

ˆ Lo stesso programma è applicato a diverse descrizioni per risolvere

ˆ problemi diversi.

Viene esplicato il , fornendo una descrizione del mondo.

cosa

ˆ Viene dato lo

Non viene scritto come si risolva un problema.

ˆ stato iniziale, e l'obiettivo che deve essere raggiunto. Chiediamo al

software di trovare una soluzione, partendo da un risolutore generale

di problemi.

sono i numeri forniti dai sensori, sono grezzi e non correlati fra

Dato:

loro. Pezzo di conoscenza utile estratto dall'elaborazione

Informazione:

dei dati. È ciò che il dato rappresenta.

9

è ciò che ottengo dalle informazioni, correlandole fra

Conoscenza:

loro tramite delle relazioni. Per elaborare delle informazioni è neces-

sario rappresentarle.

ricezione dei dati e processamento che permette di es-

Percezione:

trarre informazioni da dei dati.

6 Automazione vs Autonomia

(Non-AI) sono sistemi automatici, guidati da algo-

Automazione:

ritmi. Consiste nella codica di una sequenza di passi eseguibili da un

sistema, senza che sia necessario l'intervento umano.

dare ad un agente articiale un compito, aspettandosi

Autonomia:

che lo risolva senza fornirgli un algoritmo risolutivo. Sarà compito

dell'agente stesso una soluzione. (Si trova su un piano di

ricercare

astrazione molto più a